推荐系统-召回层-算法：近似最近邻搜索算法（ANN）【高维稀疏向量相似查找：LSH（SimHash/MinHash）用于离线场景】【稠密向量相似查找：Faiss（HNSW）、Annoy、ScaNN】

迈不过友情╰ 2023-09-28 17:32 10阅读 0赞

推荐系统-召回层-算法：近似最近邻搜索算法（ANN）【Approximate Nearest Neighbors】【海量数据相似数据查】【开源算法：Faiss、Annoy、ScaNN、Hnswlib】

在搜索的业务场景下，基于一个现有的数据候选集（dataset），需要对新来的一个或者多个数据进行查询（query），返回在数据候选集中与该查询最相似的 Top-K 数据。

当我们通过计算获得了每个物品的Embedding表示之后，最常遇到的一个问题就是在给定某个目标物品时，如何找出何其最类似的n个物品？

这一类问题被称为最近邻搜索问题，经过多年的发展，这个问题在业界也有诸多的解决方案。

目前最常用在推荐系统中的是近似最近邻检索算法（ANN）。

由于我们并不需要精确的知道某个物品的n个最相近的物品是什么，只要大致结果正确就行，因此可以采用许多办法来加速计算、减少时间和 空间复杂度。在这方面Facebook团队开源了FAISS，提供了诸多开箱即用的模型。

Google：the two-tower neural network model：

![在这里插入图片描述][e7296d98cbf2423fbe4a60e76bb0b787.gif_pic_center]  
最朴素的想法就是，每次来了一个新的查询数据（query），都遍历一遍数据候选集（dataset）里面的所有数据，计算出 query 与 dataset 中所有元素的相似度或者距离，然后精准地返回 Top K 相似的数据即可。

但是当数据候选集特别大的时候，遍历一遍数据候选集里面的所有元素就会耗费过多的时间，其时间复杂度是  O ( n ) O(n) O(n) 因此，计算机科学家们开发了各种各样的近似最近邻搜索方法（Approximate Nearest Neighbors）来加快其搜索速度，在精确率和召回率上面就会做出一定的牺牲，但是其搜索速度相对暴力搜索有很大地提高。

在这个场景下，通常都是欧式空间里面的数据，形如 ![在这里插入图片描述][e29d64f661724d9f8b712a5f5beeb109.png_pic_center]  
其中  n n n 是欧氏空间的维度。常用的距离公式包括：

![在这里插入图片描述][dd2061955d8e4bf7ab59ecfa1a75b038.png_pic_center]

欧氏空间的数据点聚类：

![在这里插入图片描述][a5300d64fb054eea87e39e87fee9875d.png_pic_center]  
在近似最近邻搜索（ANN）领域，有很多开源的算法可以使用，包括但不限于：

*  **Annoy**（Approximate Nearest Neighbors Oh Yeah）；
 *  **ScaNN**（Scalable Nearest Neighbors）；
 *  **Faiss**（Billion-scale similarity search with GPUs）；
 *  **Hnswlib**（fast approximate nearest neighbor search）；

ANN 的 benchmark：  
![在这里插入图片描述][f29066355abe4e2abdb259ac72871fc5.png_pic_center]

--------------------

参考资料：  
[近似最近邻搜索算法 ANNOY（APPROXIMATE NEAREST NEIGHBORS OH YEAH）][ANNOY_APPROXIMATE NEAREST NEIGHBORS OH YEAH]  
[ANN召回算法之IVFPQ][ANN_IVFPQ]  
[一文读懂 ANN][ANN]  
[爱奇艺视频推荐领域的ANN实践][ANN 1]  
[双塔DNN召回模型/DSSM算法][DNN_DSSM]

[e7296d98cbf2423fbe4a60e76bb0b787.gif_pic_center]: https://img-blog.csdnimg.cn/e7296d98cbf2423fbe4a60e76bb0b787.gif#pic_center
[e29d64f661724d9f8b712a5f5beeb109.png_pic_center]: https://img-blog.csdnimg.cn/e29d64f661724d9f8b712a5f5beeb109.png#pic_center
[dd2061955d8e4bf7ab59ecfa1a75b038.png_pic_center]: https://img-blog.csdnimg.cn/dd2061955d8e4bf7ab59ecfa1a75b038.png#pic_center
[a5300d64fb054eea87e39e87fee9875d.png_pic_center]: https://img-blog.csdnimg.cn/a5300d64fb054eea87e39e87fee9875d.png#pic_center
[f29066355abe4e2abdb259ac72871fc5.png_pic_center]: https://img-blog.csdnimg.cn/f29066355abe4e2abdb259ac72871fc5.png#pic_center
[ANNOY_APPROXIMATE NEAREST NEIGHBORS OH YEAH]: https://zhuanlan.zhihu.com/p/454511736
[ANN_IVFPQ]: https://zhuanlan.zhihu.com/p/378725270
[ANN]: https://www.imooc.com/article/323655
[ANN 1]: https://blog.csdn.net/DAMO_Proxima/article/details/115398806
[DNN_DSSM]: https://www.cnblogs.com/charlesblc/p/15932373.html