比较向量相似度的思考

背景：当前问答模块思路是通过BERT将用户问题向量化后与收集的问答数据的问题也全部向量化，然后通过比较向量相似度，找出最相似的问题，进而给出该问题下的答案。

原有方法通过逐一比较余弦相似度，每个新的输入实例都需要与所有的训练实例计算一次相似度并排序。当训练集非常大的时候，计算就非常耗时、耗内存，导致算法的效率降低，系统响应时间过长。

那么如何快速从一个大规模的向量集合中找到与待比较向量最相似的向量呢？

问题描述：从向量集合A{x1, x2, x3, x4,,,xn},找到与向量y最相似的向量

以下是博主的一些探索：

从一个集合中找到与其最相似的元素，很容易可以想到KNN的思路，我们可以训练一个每个集合为单一元素的KNN模型，然后直接通过y找到最相似的即可。

当然没有这么简单。

我们直接用了更高级的KD-Tree。

kd树（k-dimensional树的简称），是一种对k维空间中的实例点进行存储以便对其进行快速搜索的二叉树结构。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

kd 树是每个节点均为k维数值点的二叉树，其上的每个节点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。

from sklearn.neighborsimport KDTree

print('构建KD tree')

k_dtree = KDTree(A, leaf_size=2)

dist, index = k_dtree.query(y, k=3)

但是发现实际效果并不好，找到的最相似的向量并不是我们期望的最相似向量，也就是我们通过余弦相似度比较的向量。

推测可能是由于kd-tree在高维数据上效果不好的原因（这里向量维度在768维），因此使用了BallTree

print('构建Ball tree')

ball_tree = BallTree(A, leaf_size=2)

dist, index = ball_tree.query(y, k=3)

发现效果仍然不好。

考虑kd tree原理，其实要做的是二分查找的思路，也就是给数据做了排序，如果可以排序，我们完全就可以用二叉搜索树，进而直接排序成列表然后二分查找也可以。而排序是基于欧式距离排序的，通过查看源码，我们知道KD tree的距离计算方式可以选择欧式距离，闵科夫斯基距离，曼哈顿距离等。

因此这里推测，可能由于BERT在构建词向量的时候就是通过cosine比较，而不是通过欧式距离的，所以导致转化成的向量不适合用欧式距离的计算方式去比较其相似度。

hanxiao的bert-as-service项目中比较句子相似度也是采用余弦相似度的比较方式，可能也是这种原因，没有采用比较欧式距离的方法。

whileTrue:

     query=input('your question:') 

     query_vec=bc.encode([query])[0] #compute normalized dot productasscore

     score=np.sum(query_vec*doc_vecs,axis=1)/np.linalg.norm(doc_vecs,axis=1) 

     topk_idx=np.argsort(score)[::-1][:topk]

     for idx in topk_idx:

          print('>%s\t%s'%(score[idx], questions[idx]))