Welcome to Narcissus's Blog!

这里是Narcissus的技术圈

二叉树

2018-07-28

Narcissus

剑指offer

二叉树

二叉树的下一个结点
对称的二叉树
按Z字型顺序打印二叉树

二叉树的下一个结点

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
	TreeLinkNode* GetNext(TreeLinkNode* pNode)
	{
		if (pNode == NULL)return NULL;
		TreeLinkNode*temp=NULL,*temp1=NULL;
		if (pNode->right != NULL)
		{
			temp = pNode->right;

			while (temp->left != NULL)
			{
				temp = temp->left;
			}
			return temp;
		}
		else if(pNode->next!=NULL)//因为给的可能是根节点，所以这里要判断下。
		{

			temp= pNode->next,temp1 = pNode;
			while (temp != NULL&&temp->left != temp1)//注意判断条件
			{
				temp1 = temp;
				temp = temp->next;
			}

		}

		return temp;
	}
};

思路注意这个题给了父节点的信息，所以不需要给二叉树的根节点信息，而当前节点可能是二叉树中的任一结点；分两种情况讨论：

有右子树，则返回右子树的最左节点；
没有右子树：
- 没有父节点，返回NULL
- 有父节点，是该父节点的左儿子，则返回父节点；
- 有父节点，但是不是该父节点的左儿子，一直向上找，要注意判断条件：while (temp != NULL&&temp->left != temp1)

对称的二叉树

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	bool isSymmetrical(TreeNode* pRoot)
	{
		if (pRoot == NULL)return true;
		return symmetrical(pRoot->left,pRoot->right);
	}
	bool symmetrical(TreeNode*left, TreeNode*right)
	{
		if ((!left) && (!right)) return true;
		if (!(left)||!(right))return false;
		return (left->val == right->val) && (symmetrical(left->left, right->right) && symmetrical(left->right, right->left));
	}//左子树的左子树个右子树的右子树对称；左子树的右子树和右子树的左子树对称；

};

按Z字型顺序打印二叉树

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	vector<vector<int> > Print(TreeNode* pRoot) {

		int depth = 0;

		vector<vector<int> > result;
		if (pRoot == NULL)return result;
		vector<TreeNode*>a;
		a.push_back(pRoot);
		print_level(a, depth, result);
		return result;
	}
	void print_level(vector<TreeNode*>a,int depth, vector<vector<int> >&result)
	{
		if (a.size() == 0)return;
		vector<int>level;
		vector<TreeNode*> temp;
		if (depth % 2 == 0)
		{
			for (int i = 0; i < a.size(); i++)
			{
				level.push_back(a[i]->val);//从前往后打印
                //用新的vector<TreeNode*> temp来存下一层的指针
				if (a[i]->left != NULL)temp.push_back(a[i]->left);
				if (a[i]->right != NULL)temp.push_back(a[i]->right);
			}
		}
		else
		{
			for (int i = a.size()-1; i>=0; i--)//从后往前打印
			{
				level.push_back(a[i]->val);
			}
			for (int i = 0; i < a.size(); i++)//用新的vector<TreeNode*> temp来存下一层的指针
			{

				if (a[i]->left != NULL)temp.push_back(a[i]->left);
				if (a[i]->right != NULL)temp.push_back(a[i]->right);
			}
		}
		depth++;
		result.push_back(level);//打印当前层结果
		print_level(temp,depth,result);//迭代调用
	}
};

思路按BFS的思路，但不同的是每一层迭代调用都用新的vector<TreeNode*> temp来存下一层的指针；

Read All

Word Embedding models VS. Distributed Semantic Models

2018-07-16

Narcissus

机器学习

NLP

若显示有问题，可查看pdf版

这篇文章主要讲了Word2Vec能够成功的一些因素，会和传统的分布式语义模型(DSMs)进行比较，并将一些技巧迁移到分布式模型上去，会显示出DSMs并不会比word2vec差，虽然这并不是新的见解，但由于这些传统方法在深度学习面前总是显得黯然失色，因此值得被再提及。这篇博客主要基于Improving Distributional Similarity with Lessons Learned from Word Embeddings 。

Glove模型

GloVe明确的做了SGNS(skip-gram with negative-sample)所含蓄表达的思想：将embedding 空间的向量偏移编码成语义信息。这在word2vec中是一个偶然的副产品，但却是Glove的目标。

Encoding meaning as vector offsets in an embedding space – seemingly only a serendipitous by-product of word2vec – is the specified goal of GloVe.

If we dive into the deduction procedure of the equations in GloVe, we will find the difference inherent in the intuition. GloVe observes that ratios of word-word co-occurrence probabilities have the potential for encoding some form of meaning. Take the example from StanfordNLP (Global Vectors for Word Representation), to consider the co-occurrence probabilities for target words ice and steam with various probe words from the vocabulary:

“As one might expect, ice co-occurs more frequently with solid than it does with gas, whereas steam co-occurs more frequently with gas than it does with solid.

Both words co-occur with their shared property water frequently, and both co-occur with the unrelated word fashion infrequently.

Only in the ratio of probabilities does noise from non-discriminative words like water and fashion cancel out, so that large values (much greater than 1) correlate well with properties specific to ice, and small values (much less than 1) correlate well with properties specific of steam. ”In this way, the ratio of probabilities encodes some crude form of meaning(粗糙的语义信息) associated with the abstract concept of thermodynamic phase. //第三行那个比例就包含的语义信息，比如k=solid的时候，$p(k ice)/p(k stream)$的值很大，说明ice更多的是和solid相关的，而stream则不太跟固体相关，这里就包含了一些热力学里面的语义信息。

However, Word2Vec works on the pure co-occurrence probabilities so that the probability that the words surrounding the target word to be the context is maximized..

Read All

论文阅读 Phrase Localization and visual relationship detection with comprehensive Image-language cues

2018-07-15

Narcissus

图像理解

SceneGraphGeneration
这篇文章主要是对phrase location（就是说输入图像和image caption来定位objects）来做的，后面又应用这个来做了一个关系检测的实验，我觉得这很可能是在后期做的一个补充。检测结果相对于前面看的几篇文章都要好。他这个创新点，主要是用了多种cues，并自己设计了有效的损失函数等，phrase lacation这里没有细看。

用了字幕数据，通过nlp进行parse sentence，phrase的解析得到entities、relationships、以及一些其他的linguistic cues。

1.文章思想

输入image和caption，用nlp tools处理代指关系，提取caption中的noun phrase和pair of entities。并做以下处理：
- 1）对于noun phrase（如red umbrella），根据appearance、size、position、attributes（形容词）等来为每一个候选的box计算一个single-phrase cue scores；
- 2）对于pair of entities（man carries a baby），则通过spatial model来对相应的candidate boxes计算score；
- 3）对于actio类的phrase，建立一个subject-verb和verb-object的 appearance models；
- 4）对于people、clothing、body parts之间的关系，phrase通常用来描述individuals，而且也是现有方法比较难定位其中的物体，因此对于这种phrase常常给与spetial treatment。
$Input Sentence and Image A man carries a baby under a red and blue umbrella next to a woman Cues I) Entities 2 CandZate Positi 3) Candidate BOX Size 4) S) Adjectives 6 Subject - Verb 7) Verb — Object 8 Verbs Examples man, woma n. man —4 person person man. man, . under. man. to. ) Cloth ing & Body P*tS Figure 1: Left: an image and caption, together with ground truth bounding boxes of entities (C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image001.png). Right: a list of all the cues used by our system, with colTesponding phræses from the sentence.$

2.文章用了多种组合的特征：

现有的一些工作要么只定位那些attribute phrase中的物体，要么只解决了possessive pronouns 等代指的关系，而本文：
- 1）we use pronoun cues to the full extent by performing pronominal coreference ；
- 2）ours is the only work in this area incorporating the visual aspect of verbs.
- 3） with a larger set of cues, learned combination weights, and a global optimization method for simultaneously localizing all the phrases in a sentence （就是说能同时解决一个sentence中的所有phrases）
3.从sentence 解析 phrases

linguistic cues corresponding to adjectives, verbs, and prepositions must be extracted from the captions using NLP tools. hey will be translated into visually relevant constraints for grounding. And we will learn specialized detectors for adjectives, subject-verb, and verb-object relationships ，we will train classifiers to score

pairs of boxes based on spatial information 。

这个部分就是根据nlp提取一些形容词、动词、entities、relationships等language cues，具体的有点感觉，考虑了多种特殊的情况。

4.损失函数的构建

single phrase cues (SPC) measure the compatibility of a given phrase with a candidate bounding box, and phrase pair cues (PPC) ensure that pairs of related phrases are localized in a spatially coherent manner
- single phrase cues
- phrase-pair cues
5.同时进行多个phrase location的过程（测试过程）

6.关系检测任务

这个模型扩展到VRD任务上去，能有较好的zero-shot detection的作用。

用了以下几个CCA 模型，用的是fast rcnn在MSCOCO上面训练的模型：

7.VRD实验结果

$- b 一 h d - ; mitial 12 (C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image004.png)' CVA CCA 4 Sir Position 1837 15 , 一 1 43 7 CCA 4 Sir 一 271 一 - R 50 R 50$
Read All
论文阅读：Object Detection Using Scene-Level Context and Instance-Level Relationships

2018-07-10

Narcissus

图像理解

SceneGraphGeneration
SIN网络结构

网络结构解释

首先对输入图像利用faster-rcnn进行物体检测，得到一些ROIs,对ROI进行ROI pooling得到固定size的feature map,再经过全连接层映射成一些节点(nodes，即feature vector)，并两两组合得到edges，即得到object relationship context。对整个图像提取特征得到scene context。将两种context送入到GRU(选择GRU的原因是其具有记忆功能，能融合来自多方面的context，并传递到下一次更新中,即有消息传递功能)，这个GRU的原理如下：

$ht (C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image002.png) 1 (nodes') Figure 4. An illustration of GRU. update gate z selects whether the hi dden s tate ht is to updated with a new hi den state 11. The reset gate r decides whether the previous hidden ignored.$

这里r开关和z开关的详细定义及作用可看论文

全局context与局部context

对于每一个物体的定位，它利用了来自scene GRU的信息和Edge GRU的信息，如下：

形式化的表示为：

其中的空间位置特征表示为：

$(Xi — (Yi , log(C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image005.png ) , tog($

最后得到隐藏层t+1的特征表示（通过mean pooling 得到)：

$For node v', it receives messages both from the other nodes and scene context. Eventually we get the compre- hensive representation , which denotes the node state. In our current study, we empirical find that (C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image006.png) pooling and concatenation, so (8) where is the output of scene GRU, and h; +1 denotes the output of edge GRU.$

结果分析
- 量化结果是一个总体结果，肯定是好的，这个需要跑代码看，数据是否对。
- qualitative results
Scene module结果中比较值得一说的是failure case：将海里的airoplain识别成了boat，说明对这种罕见的场景来说scene context是不好的

$(C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image007.png) ru'hins dct"ted an with a (d) are detected (e) chair ted (n only a Figure 8. Qualitative results Baseline vs. Scene on VOC. In pair Of detection results (top vs. the top is based on baseline, and the is detection result of Scene,$
- Edge module的结果：定位错误的结果减少；能够减少重复检测的结果：
$(C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image008.png) aeroplane (b) Edge (d) Edge Figure 9. Analysis of 'Iöp-Ranked False Positives. Pie charts: fraction of detections that are correct (Cot) or false positive due to confusion With similar Objects (Simi, confusion with other VOC objects ((hh). or confusion with back- ground or unlatkled objects (BG)_ Len: results of the baseline Faster R -CNN, Right; results Of Edge, Loc errors are fewer than baseline on aemplane and bus.$

$(C:\Users\nian\OneDrive\NoteBook_posts\assets\clip_image009.png) are (b) of Edge (d r&lts of Edge Figure results Edge on VOC. In every pair of detection results. the left is based on bmseline. and the right is detection result Of Edge.$
- 结合两种context的结果：
题注
Read All
循环神经网络的梯度消失及梯度爆炸问题

2018-07-05

Narcissus

深度学习

RNN LSTM
- RNN的梯度消失、爆炸问题
RNN的梯度消失、爆炸问题
Read All