大家好,我是不会写代码的纯序员 Chunel。今天,我想跟大家聊聊,我在Caiss中,对ANN算法做了哪些优化。
介绍 |
ANN(Approximate Nearest Neighbor)算法指的是用于解决海量高维向量中,相似度检索问题算法的集合,是一套算法簇的集合。主要分为:基于树的算法(如kdtree、annoy等),基于索引的算法(如ivf等)和基于图的算法(如HNSW、NSG等)。所需要解决的问题,无非是两个:
- 如何更快的在集合中查询到topK个相似向量
- 如何确保快速召回的topK个向量,尽可能的准确
近几年,大量实验已经证明,基于图的算法在这两个方面都有较大的优势。具体的性能比较,大家可以到年薪百万的知乎上搜索一下,这方面的对比还是比较多的。不过,那些曲线图看看就好,因为你很难通过那些对比数据,看出自己需要找的具体数据集合(比如:1000w个300维向量)的性能,而且不同算法的不同的参数设置,对最终的性能和效果的影响也是很大的。
我的意见是,如果数据量不是特别特别大的话(上亿级别,压垮服务器内存),就直接上Caiss
[Caiss源码链接]吧。Caiss底层是基于HNSW (Hierarchical Navigable Small World 平行可导航小世界)算法,性能和精度极大的优化的同时,方便上手,更是能帮你完全免掉参数设置的麻烦。
在这里,先简单罗列一些HNSW算法的信息,供大家参考:
下面进入正题,主要介绍一下本人在Caiss中做的模型和计算方面的优化。
模型优化 |
Question1:HNSW(包括所有的ANN算法)的功能是通过给定向量,搜索距离相近的向量,属于vec2vec的搜索。但在日常的开发任务,经常是需要label2label。举个例子,我们做图像搜索的时候,如果我们通过vec2vec的方式查询,需要第一步将传入的图片embedding成向量(vec),再通过这个vec在给定的向量池中快速找到距离最近的topK个vec,然后将这topK个vec映射回图片的标签,从而找到相似图片。这个流程对开发来说相对繁琐,而且还需要专门加入类似数据库的内容,用来记录label和vec对应的信息。
Solution1:为了解决来回映射的问题,Caiss在算法模型中引入了双向哈希结构,支持传入label直接在模型中映射成vec,也支持搜索到的近邻vec映射回对应的label。结果就是使用Caiss,在开发过程中只需要传入图像的label,就可以直接得到相似图片的label,极大的简化的工程链路。
Question2:在做ANN任务的时候,更头疼往往是算法和参数选取的问题。这么多种算法,每种算法又这么多参数。选什么算法,设什么参数,对搜索结果有什么影响,这样的问题想想就令人抓狂。特别是针对一些不太了解这些算法的开发人员来说,这简直就是灾难。
Solution2:为了更好的让大家入门并解决实际问题,Caiss中加入了自动训练的功能。不同于深度学习的神经网络算法,图搜索算法基本上都有一个特点,就是节点的出度(即一个点连接的周边点)越大,准确度越高,与之对应的是,搜索效率越低。基于这一点,Caiss在训练的过程中,屏蔽了算法参数选取的过程,直接根据用户设定的精确度(precision)信息进行多轮(epoch)迭代训练。并且在每次训练的时候,根据当前模型精确度与目标值的差距(span)自动调优参数,直到达到目标为止。
Question3:“增删查改”是搜索任务中最常见的需求。HNSW是基于平行图的搜索算法,在构图的时候点点相连。插入流程和构图流程基本相同,但是如果删除其中的某个节点,会引起整个图结构改动,最糟糕的情况甚至可能需要重新构图。
Solution3:为了解决删除的问题,Caiss在HNSW模型的模型中,加入了Trie(字典树)结构,将需要删除(忽略)的节点的label,放入Trie中。每次搜索的时候,相比topK值,多召回一些节点。如果召回的节点的label在Trie中,则在返回结果中过滤。
这样做主要有两个好处:一个是在删除的label数量巨大的时候,既节省了空间,又能够快速查询;第二个就是这种解决方法不会引发引擎算法模型的重建,而且还方便恢复之前删除的信息。
计算加速 |
计算海量向量相似度的过程,涉及到了超大量的浮点计算,非常吃计算性能。为了加速计算,Caiss引入了eigen计算和指令集计算,通过尽可能的减少中间计算过程,在工程层面极大的加速了查询速度。
此外,Caiss中还提供了机器学习中的降维(SVD)算法,在保证准确度基本不变的情况下,通过减少单个向量维度的方法,来降低计算量,从而加速查询过程。
还有,相似度计算的任务中,特别是在语义认知任务中,很大一部分都是基于cos距离来判断相似度。Caiss在计算cos距离的时候,将cos距离计算转换成inner(内积)距离计算,并且将单个vec和其多个邻近点vec的inner距离计算流程并行化。相比于直接计算cos中的开根号的方式,精确度无影响的同时,又极大的减少了计算量。
结束语 |
以上这些优化,保证了Caiss在模型和计算性能上,有了极大的优化。当然了这些还远不够,下一章纯序员会主要跟大家聊聊,Caiss在工程层面做了哪些优化,比如开辟缓存、实现并发、SQL和批量查询的引入等。大家继续期待哦。
还有就是,如果大家在使用Caiss的过程中遇到了什么问题,或者是有什么意见,请联系我。我会尽可能在周末有空的时候,跟大家一起去解决这些问题,并且努力把它做的更好。
[2020.11.08 by Chunel]
个人信息
微信: ChunelFeng
邮箱: chunel@foxmail.com
github地址: https://github.com/ChunelFeng