相似性搜索与词向量中的应用分析
参考论文《On Approximately Searching for Similar Word Embeddings》原文链接 发表于ACL2016
什么是相似性搜索
相似性搜索的概念是在n维空间中通过比较数据之间的相似性，寻找与输入点最接近的目标点。该技术被广泛应用在数据库、信息检索、模式识别、数据分析等各个领域。
相似性搜索包含两个大类：近邻搜索和范围搜索。以寻找你附近的火锅店为例，近邻搜索可以帮助你找到距离最近的n家火锅店，而范围搜索可以帮助找到1公里范围内所有的火锅店。下图中左边展示的是近邻搜索，右边是范围搜索。
最传统的相似性搜索方法是线性搜索，对于给定的数据集，通过一定的距离计算公式，计算数据集中所有数据点到输入点的距离，然后对计算后的距离进行排序，选择最近的结果作为相似性最高的输出。
在只有几千个点的低维度数据集上，这样的方法是ok的。但是当数据集是百万级甚至千万级的海量数据时，这种线性搜索的方案将会非常耗时。同时随着数据维度的增加，线性搜索也会带来维度灾难(Curse of dimensionality)，相似性搜索的性能会急速下降。
为了解决该问题，最常用解决方案就是对数据集使用索引技术。
索引技术
通过事先对数据集进行索引，从而达到高效搜索n维空间数据的目的。在相似性搜索中，数据索引的方案可以分为三大类，分别是哈希索引、树索引以及图索引。
哈希索引
哈希索引由于其简单的特性，经常被运用在自然语言处理上计算文本间的相似度。一种常用的索引方法是局部敏感哈希(Locality Sensitive Hashing，LSH)算法。LSH的核心思想是在哈希算法的过程中依旧在一定概率上保持数据原有的相似性，也就是说在原始数据集中距离较近的两个数据点，在LSH以后仍然很大概率非常接近。另外，LSH的方法通常更适合于范围搜索，而非近邻搜索。
下面是LSH函数h的条件：
1. 如果 d(x,y)<=d1，则 P(h(x)=h(y))>=p1
2. 如果 d(x,y)>=d2，则 P(h(x)=h(y))<=p2
树索引
树索引可以理解为将数据排列成树结构，在搜索过程中排除掉不符合要求的分支，从而提升搜索速度。
这里从R树开始入手了解一下树索引。如下图所示，我们将数据集按照数据值分配到9个子集中（红框），并确保每个子集拥有相同数目的数据。然后我们对每个子集重新划分更小的9个子集（蓝框）。循环往复直到最后的每个子集只拥有不超过9个数据点。这就是R树的整体概念，可以从二维延展到更高维。
kd树是另一种树索引方案，相对于R树在每一层将数据分发到多个子集不同的是，kd树每一级仅将空间划分为两个部分，划分的维度会根据每一部分数据的状态选择划分度最大的维度，循环往复将数据切分为各个小部分。kd树无法处理数据的添加和移除，但是具有实现方便且搜索速度快的特点。
FLANN（Fast library for approximate nearest neighbors）是一套树空间搜索的开源库，其采用的方案是在三种树索引方案中选择最优解（三种方案分别是随机kd树、k-means树以及前两者的混合方案）。目前FLANN支持C/C++、Matlab、Python等接口调用吗，使用起来也非常方便。
SASH（Spatial approximation sample hierarchy）是一种建立在随机采样数据上的层级结构加上数据链接的索引。数据准确性不是一定能够保证的，但是可以通过调整比例因子的参数来提高精度。SASH的大致原理是通过随机采样数据集中的数据，并对其建立树索引，然后对于未被随机采样到的数据集与树结构中的数据进行链接配对，从而完成完整数据的索引[如图]。在SASH的官网上可以下载C++的源码进行使用。
图索引
图索引的方法是通过近邻图寻找最近的节点。最近邻图(NNG)中的每一个点通过距离计算被连接到最接近的点上。下图是一个二维平面100个点的最近邻图，其中的每一个点都可以通过图结构寻找到自己的最邻近点。
最邻近图NNG是k邻近图(KNNG)在k等于1时候的一种特殊情况，由于需要对所有节点计算最邻近点，通常KNNG在构建的时候随着节点数量的上升会非常耗时。但在实际运用中，采用一种ANNG的方案可以大大优化构建过程。2015年基于ANNG发布的NGT的开源项目，也已经被应用在多项实际业务上了。
词向量中的相似性搜索
词嵌入
自从Mikolov在2013年发表了word2vec，由于其优秀的表现，将自然语言处理带入了一个新的阶段，词嵌入逐渐开始被大量应用于自然语言处理中。
词向量的本质是通过向量的方式来表示每一个词汇，最简单的方法是01向量，向量的维度为词的总数，第N个词可以表达为第N位为1，向量中其余的元素全部为0。形如： [0,0,0,……0,1,0,……0,0,0]。然而这样的表现方式基本不可用，因为维度实在太高。
word2vec等方案通过对一套语料库的训练，通过利用每个词与上下文间关系(可分为CBOW或Skip-gram方法)来进行的词嵌入(Word Embedding)。所谓的词嵌入，其实就是将超高维度抽象化的词向量嵌入到一个较低维度的空间中。当然除了word2vec，现在也有wordrank、GloVe等其它方案。在经过词嵌入处理后，可以把原本稀疏的高维度01词向量降到几百维左右的稠密向量空间中，并且保留住词与词之间的隐含关联。一个简单的例子是：可以在词空间中通过距离公式找出与某个词距离最接近的词，比如“麦当劳“，可能和它最接近的应该就是“肯德基““汉堡”之类的词汇。
在实际应用中我们经常需要在词向量空间中寻找与目标词距离最近的词向量。On Approximately Searching for Similar Word Embeddings这篇论文分别在各场景下对之前提到的LSH、FLANN、SASH、NGT进行了词向量应用中的测试比较，在这里我们看一下对比结果。
索引时间比较
首先我们看一下建立索引时间的比较。文中采用的是2015年的英文维基百科作为训练集产生的200维词向量作为基础，采用了三种距离公式，分别是欧式距离、归一化距离和余弦距离，对各个方案的索引时间进行比较。
结论可以发现采用欧氏距离时树索引FLANN的索引时间最短，仅需20分钟。而在归一化距离和余弦距离的情况下，代表图索引的NGT都具有更好的表现，分别是33.9分钟和155.4分钟。
搜索性能比较
(a) 分别对100、200、300维的词向量数据进行比较。理论上，在维度变得越来越高的时候SASH性能会更好，而FLANN和NGT在维度上升后性能会下降。在测试结果中(如下图所示)，在三种情况下，NGT均在更短的时间内取得了较高的准确率。
(b) 根据不同的近邻数量k值进行对比。当k取200时，SASH的性能下降明显。一个可能的原因是当划分的子空间不合适的时候，树索引的搜索性能会大大受到影响。
(c) 不同数据量的对比。下图是分别在数据量是100K、1M、2M的情况下的对比，效果依次是NGT、SASH、FLANN。
(d) 三种不同词向量的对比。分别是Mikolov使用skip-gram模型与负采样技术的word2vec训练产生的300维词向量；深度神经网络生成的200维词向量；GloVe生成的300维词向量。结果图中所示，在第三种情况下，所有的索引方案都比去前两种模型都差了不少，可以发现搜索效果非常容易受到词向量训练模型的影响。
(e) 最后文章对词向量运算做了一下比较，所谓的词向量运算是指：”巴黎”之于”法国”等于什么之于”日本”，正确答案应该是”东京”，而词向量运算本质上是计算 vec(“巴黎”)-vec(“法国”)+ vec(“日本”)，并搜索距离结果向量最近的那个词。
完整的测试内容感兴趣可以看原文，也可以结合自己的实际场景去测试一下各个方案在你自己的词向量上的表现效果。
