做了一个比赛,其中为了更好的构建负样本,需要计算不同句子之间的相似性,句子大概有100w+,句子向量是300维,中间踩了很多坑,记录一下。
暴力计算
最简单的idea是预分配一个100w x 100w的矩阵,一个个算就好了
当然实际情况是直接算不了,原因见下:
import numpy as np
np.zeros([1000000,1000000],dtype=np.float16)
numpy中的每个 float32 类型数据都占用 4 个字节,因此预分配这样的数组需要的总内存为
1000000 * 1000000 * 4 / 1024 / 1024 / 1024 / 1024 = 3.6379 TB
因此我们发现对于个人或者小团队来说这是非常不现实的事情,那么如何优化这一过程呢?
是否需要记录所有的数据?–》只计算 TOP k 的数据【比较傻的方案】
如果只是需要记录TOP k 的数据的话,那刚好可以分配一个较小的数组,再进行相似度的计算 【暴力计算】 《- 我后来用的方法
降维算法【一般方案】
word2vec对于每个word都生成了300维向量,直接计算300维向量之间的相似度运算量比较大,可以使用降维的方法
推荐:一些相关搜索算法/库【实际有用的方法】
推荐阅读:
-
topk相似度性能比较(kd-tree、kd-ball、faiss、annoy、线性搜索)
-
详解KDTree
-
kNN里面的两种优化的数据结构:kd-tree和ball-tree,在算法实现原理上有什么区别?
KD 树沿卡迪尔轴(即坐标轴)分割数据, ball 树在沿着一系列的 hyper-spheres 来分割数据
-
Paper: What is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?
论文的最终结论:
-
Faiss的Github Faiss-A library for efficient similarity search and clustering of dense vectors.
Faiss是Facebook开源的针对稠密向量提供高效相似度搜索和聚类的框架
找了下网上没有特别详细的Faiss原理性文章,推荐阅读Faiss的论文 Billion-scale similarity search with GPUs,或者这一篇文章也蛮详细的Facebook AI Similarity Search (FAISS), Part 1
参考文章:
7. 知乎 40w*40w的矩阵应怎样在内存中初始化?
8. CSDN 【Python】小谈 numpy 数组占用内存空间问题