浅析文本相似度

1 基于关键词匹配

1.1 N-gram 相似度

$$Similarity = |G_{N}(S)|+|G_{N}(T)|-2*|G_{N}(S)\cap G_{N}(T)|$$

　　其中， $G_{N}(S)$和 $G_{N}(T)$分别表示字符串S和T中N-Gram的集合，N一般取2或3。字符串距离越近，它们就越相似，当两个字符串完全相等时，距离为0。

1.2 Jaccard 相似度

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$
　　其中 $0\leq J(A,B)\leq 1$

2 基于向量空间

　　关于如何表达词意目前有三种方法，第一种的代表就是WordNet，它提供了一种词的分类资源但是缺少了词之间的细微区别，同时它也很难计算词之间的相似度；第二种就是Discrete representation，如One-hot representation，它的向量维度和词典的长度相同，因此向量维度可能十分高，同时由于向量之间本身正交，无法计算词之间的相似度；第三种就是Distributed representation，基本想法就是将每个词映射为一个固定长度的短向量（相对于one-hot representation而言），所有这些词构成一个词向量空间，每一个向量视为空间中的一个点，在这个空间引入“距离”，就可以根据词之间的距离来判断它们之间的相似性，代表方法如word2vec, LDA等。

2.1 Word2vec

2.2 TF-IDF

　　TF-IDF的核心思想是：在一篇文章中，某个词语的重要性与该词语在这篇文章中出现的次数成正相关，同时与整个语料库中出现该词语的文章数成负相关.
　　TF(term frequency)：词频，某一个给定的词语在该文件中出现的频率，表示一个词语与该文章的相关性。这个数字是对词数（term count）的归一化，以防止它偏向长的文件。
　　IDF(inverse document frequency)：逆向文件词频，表示一个词语出现的普遍程度。某一特定词语的idf，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取以10为底的对数得到。
　　一篇文章中某个词语的重要程度，可以标记为词频和逆向文件词频的乘积，

$$tfidf = tf * idf$$
　　通过计算出文档中每个词的TF-IDF值，然后结合相似度计算方法（一般采用余弦相似度）就可以计算两个文档的相似度。采用TF-IDF的前提是“文章的词语重要性与词语在文章中出现的位置不相关”。

2.3 LSA

//TODO

2.4 相似度计算

2.4.1 欧式距离

$$d = \sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}$$

2.4.2 曼哈顿距离

$$d = \sum_{i=1}^{n}|x_{i}-y_{i}|$$

2.4.3 余弦相似度

$$cos\theta = \frac{\sum_{i=1}^{n}x_{i}*y_{i}}{\sqrt{\sum_{i=1}^{n}x_{i}^{2} \sum_{i=1}^{n}y_{i}^{2}}}$$

2.4.4 其他

　　其他的相似度计算方法包括皮尔森相关系数、一般化的闵可夫斯基距离（当p=1时为曼哈顿距离，当p=2时为欧式距离）、汉明距离等。

3 基于深度学习

3.1 深度学习

3.2 DSSM

$$R(D,Q)=cosine(y_{Q},y_{D})=\frac{y_{Q}^{T}y_{D}}{||y_{Q}||||y_{D}||}$$
　　其中 $y_{Q}$和 $y_{D}$表示DNN输出层问句和文档的低维语义向量，然后通过softmax得到条件概率分布。
　　
　　 Word hashing
　　原始的问句或者文档是一个高维的向量，如向量的维度可能是词表的大小，当输入这些高维度的向量时神经网络可能无法训练。为了使得神经网络更好的训练，论文提出了减少DNN输入层向量维度的 Word hashing方法，也即上图中的word hashing层。
　　word hashing是一种基于字符的n-gram方法。如对good一词，首先添加开始和结尾的标记得到#good#，然后将该词分解为字符n-grams（如采用trigram: #go,goo,oog,od#），最后这个词就会被这些n-grams向量表示。
　　一种可能存在的问题是认为不同词的词向量冲突(collision)。但是经过作者的统计，如在500k维的one-hot编码基础上，采用字符级trigram时，向量维度可以降到30k维，且冲突率仅为0.0044%。

　　DSSM的训练中，神经网络层的参数$w$和$b$都是通过最大化点击数据的条件概率得到，公式如下：
　　

$$P(D|Q) = \frac{exp(\gamma R(D,Q))}{\sum _{{{D}'\in D}}exp(\gamma R(Q,{D}'))}$$
　　其中， $\gamma$是softmax函数的平滑因子，是训练中的一个经验值。在实际训练中，对于每一个问句共有5个文档对应，其中一个是点击文档，其余4个是随机选择的非点击文档。
　　文档的相关性采用人工标注，共分为5个分数(0-4)，其中4分表示最相关，0分表示最不相关。
　　
　　DSSM的优点在于1.直接利用了用户的点击数据；2. 得到的结果可以直接排序；但是缺点在于没有利用上下文信息。
　　
　　DSSM的扩展还包括CDSSM、DSSM-LSTM等，其中CDSSM在一定程度上弥补了上下文缺失的问题，结构上将DNN替换成CNN。
　　DSSM-LSTM中使用LSTM记录上下文。

3.3 ConvNet

3.4 Skip-thoughts Vectors

3.5 Tree-LSTM

　　论文中提到基于Tree-LSTM结构的两种模型，一种是Tree-LSTM Classification，另一种是Semantic Relatedness of Sentence Pairs。
　　（1）Tree-LSTM Classification
　　对树中结点$j$分类时，结合该结点的子树使用softamx分类器进行预测，分类器采用结点的隐状态$h_{k}$作为输入：
　　
　　损失函数采用负的对数似然损失函数，并且利用L2正则化。其中$m$是训练集的样本数量，上标$k$表示第k个标签结点，$\lambda$是L2正则化参数。
　　
　　（2）Semantic Relatedness of Sentence Pairs
　　在语义相似度计算中，首先把经过Tree-LSTM模型后的句子对表示为$h_{L}$和$h_{R}$，接着结合句子对$(h_{L},h_{R})$的距离和角度，利用神经网络来预测相似度得分。
　　
　　其中，$r^{T}=[1 2 ... K]$和绝对值函数都是基于单个值运算，其中，距离度量方法$h_{X}$和$h_{+}$都是基于实际经验，两者结合时会比单个度量方式更好。
　　在进行预测时，为了归一化输出值，定义如下分布p，满足$y=r^{T}p$：
　　
　　其中，$1\leq i\leq K$。损失函数采用带正则化项的KL散度，优化目标是让标签值$p$和预测值$\hat{p}_{\theta }$更接近，$m$表示训练句子对的数量，上标$k$表示第k个句子对。
　　
　　
　　对于Dependency Tree-LSTM模型，最大的问题在于训练数据的收集十分困难并且句法分析结果也不是在所有语言中都有。

3.6 Siamese LSTM/Manhattan LSTM/MaLSTM

3.7 Others

//TODO

4 参考文献

1. NLP点滴——文本相似度
2. 常用的相似度计算方法原理及实现
3. 基于Simase_LSTM的计算中文句子相似度经验总结与分享
4. 原创：Siamese LSTM解决句子相似度以及扩展(理论篇)
5. 论文《Leaning Deep Structured Semantic Models for Web Search using Clickthrough Data》
6. 论文《Siamese Recurrent Architecture for learning Sentence Similarity》
7. CNN在句子相似性建模的应用–模型介绍篇
8. 论文《Multi-Perspective Sentence Similarity Modeling with Convolutional Neural Networks》
9. 卷积神经网络(CNN)在句子建模上的应用
10. 《Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks》阅读笔记
11. 论文《Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks》
12. 基于TreeLSTM的情感分析
13. 论文《Skip-Thought Vectors》
14. cips2016+学习笔记︱简述常见的语言表示模型（词嵌入、句表示、篇章表示）