一个AI小白如何理解近似匹配检索

在AI领域的相似度匹配中通常会接触很多新名词： ANN、KNN、HNSW、SQ8、Faiss、L2、L1、inner product...你可能会查了很多官方解释，但是：

--> 网上每个名词都告诉了是什么，我知道了他是什么，对，没错，我还是不知道它是什么

--> 根据用户手册，我Step by step成功完成了所有的实验，我依然不知道我在实验什么

--> 有业务场景讲解，与向量搜索/相似度匹配的关系是什么，没错，我也似乎连接不起来

今年有幸接触到“向量检索”领域，我也是从传统数据库/大数据到向量检索的小白，现在自认有一点点小入门，觉得还是挺有意思，把一些没太吃透的理解用一些“大白话”分享一下，大家可以当闲聊文章来看。

从一个家庭小故事开始

上周家里小孩有幸参加了杭州某机构组织了小孩子军警技能培训，机构为了满足家长们的朋友圈心态所以给小孩子们拍摄了“ 非常多帅气的照片”发到一个某图库中心，图库中心包含了所有小孩的照片，那么如何找到自己小孩的照片就是一个问题，我老婆似乎发现了一个新技能忍不住跟我show一下： 你看，我们上传一张咱们孩子的人脸，就可以从所有孩子中找到我们家孩子的帅气照了。

-->  没错，这就是传说中的“相似性搜索”/“近似搜索”，在技术层面也可以叫“向量搜索”

--> 为什么是“ 相似性搜索”：因为每个人会有表情变化、服装变化、侧面角度变化、距离变化、光线变化等等， 无法用传统意义上id=id的方式来匹配一个是否等于来确定唯一性（这里细节上我与家人探讨了为什么带着墨镜的小孩帅气照没识别出来，我理解人脸特征提取中比较重要信息会在眼角上）

--> 为什么技术上又是“向量搜索”：一张照片需要有一个体征提取过程，简单先理解为假设人脸上有100个特征，那么可以提取出来100个数据记录下来记录一个人脸（ 可先粗略理解为 每个特征数据点一般用一个float来表达），我们把它叫100维向量数据，所以匹配的时候就叫向量匹配。更形象点理解：假设人脸只有2个特征数据，取出来的2个数据（ 2个float数据）相当于在x、y轴二维平面的上的1个point点，相应的如果是3维就是在3维空间的一个point位置。

--> 如何理解特征提取过程（embedding）：特征提取方式与模型有关，不同的模型对同一张图片提取出来的特征维数和值都不一样，对于我们小白来讲，我们先理解到这个程度，咱们可以业余一点去理解就是一些距离、角度、位置、比例的信息组合（ 进一步还需要一些神经网络知识对变化的综合理解学习，否则无法对表情的变化无法去识别匹配，我们暂时先不关注太多否则很难理解），总之无论是一张图片、一段音频、一段文本、一个化学分子式可以embedding提取出多个特征点。接下来的内容，我们假设已经存在这些特征数据了，分析下这些数据做近似匹配。

从最简单的“1维”开始理解“相似匹配”

假设在传统数据库中，有1个表是学生成绩表，工作中会经常取出班级前三、前十、倒数前三、比谁成绩更好的人、平均分、最高分、最低分、成绩分布图、按照学生姓名精确或Like匹配取出学生成绩等业务。

有一个新的需求： 取出与“小明”同学数学成绩最接近的20个同学的成绩。传统解法一定是先取出小明同学的成绩，(每个同学成绩 - 小明同学的成绩)，然后对差值的绝对值做ORDER BY ASC以得到结果，结果就是：“ TOP 20个最接近小明同学数学成绩的同学名单”，没错这是最初级的一种相似度匹配。

学习过数据库的同学肯定要说这是全表扫描（暴搜），可以通过索引方式来优化，所以我们补充一下，传统B+ Tree Index如何处理这个问题：

1. 在“成绩列”上创建索引

2. 查询大于“小明成绩”的数据，并按照成绩排序的LIMIT 20，由于B+树叶子节点链表有序，所以问题比较好得到解决。

3. 同上，取出小于“小明成绩”的LIMIT 20

4. 在40个成绩差值中按照绝对值排序（这样数据量就比较小了）

不过大家应该看得出，即使B+树上玩一些小技巧也可以解决相关的问题，但是方法会显得十分笨拙不堪，且只能CASE BY CASE去解决具体问题。另外，如果维度上升到2维、4维呢？2维复杂度 = 1维复杂度+1维复杂性？应该没那么简单，我们在后面讲维度提升也许会有所理解。

为了解决这类问题，我们举一个更加形象的比喻例子，所有同学的成绩： 在0-100的直线上分布，小明同学的成绩在直线的一个位置，假设有一个方法，可以从小明成绩的位置向两端走，这是最直接能理解、也是追能够接受的一种方式，而最接近小明成绩的人也是“ 距离最近”的。

在真正工程落地的时候 1维的场景可以简单用类似B+树的方式来解决，如果有更高维度就不行了，在理解更高维度数据之前我们还是先在1维上尝试使用别的方式来处理这个问题，看看除B+树外是否有什么别的方式来完成这项工作。

从上图可以看出数据有“成堆”出现的可能，假设有一种办法可以将他们提前将顺序挨着的多个点组成小组，每个小组有个小组长（或者叫中心点），小明的成绩首先和每个小组长算距离，如果距离太长这个小组就直接淘汰，如果距离近就在小组内与小明判别成绩差，如下图所示：

大量的数据可以分布为有限数量的中心点，经过首轮筛选就可以排除掉大量的距离排序“太远”的中心点的Group数据。

每一个数据点也可能被多个GROUP的中心点划分到自己的分组中（在1维中最多到2个Group中），在高纬GROUP交叉会更多。

如何去构建分组的过程可认为是：选中心点，计算与中心点的距离、不断调整中心点，这里由于本人知识所限无法进一步展开给大家讲透。        

 所以，可以简单的认为近似匹配有点类似： 计算数据点再空间上的距离，真实意义上还有别的方式，我们可以先这样子简单理解。传统意义上的数据比对主要是：等于、大于、小于、不等于、IN、Like等行为，从数学公式上区别如下图所示（转载截图）：

维度到2维、高维

2维数据包含2个数据值，如：[0.01271, 0.05612] ，如果是3维：[0.01271, 0.05612, 0.08321] ，以此类推如果是128维，就是128个数据点。这样统一可以把它叫做：向量（Vector），而在向量世界里面，原本数据库的1维数据把它叫做：标量。

更简单点理解：我们假2维数据是平面上的x、y坐标，那么任何一个2维数据始终能在平面上能平面上找到一个合适的 Point“位置”，如下图所示：

相应的3维空间的point依然可以找到一个3维空间点的Point位置，如下图所示（请原谅我画图不够形象）：

至于4维数据，由于我们生活在3维空间无法完整理解4维空间的形态，所以我们只能用公式递推性继续向下探索一些事情。

--> 现实当中的维数一般是2的次方维：64、128、768、1024...

前面提到了“距离”，在二维平面上计算2个点距离，中学数学有一个公式：“欧氏距离”，当然欧氏距离同样可以用于计算三维、四维空间点与点之间的距离，在AI领域简单叫：L2距离，当然除此之外，还有：L1（Hanming距离）、IP（内积）、Jaccard等算法，可参考文档： Introduction - Milvus vector database documentation

通过大量科学实验和工程实践的经验总结，不同的数学公式在不同的业务场景下更适合解决相应的问题，例如L2就比较适合于解决视觉相关的图片、视频等数据。我们先不要想太多，我们就围绕欧式距离来讲，它的计算公式大致如下：

1维：就是平方再开放，相当于2个点的距离取绝对值

每增加1维：根据公式距离一定会在不断变大，因为在叠加下一个维度的距离平方值

以2维为例如下图所示：

图中红色点代表要找的起始位置，与1维不同的是，1维可以沿着左边、右边两个方向线性去寻找就近的数据，很容易通过B+树叶子节点链表来解决，但2维数据点在其周围360度任何0.00001度旋转方向上都有可能会有接近的点，程序上无法去穷举这种旋转的角度，同时也能看得出来增加1个维其复杂度叠加并不是简单的加法。

因此要寻找接近的点，通过欧式距离提供一种数学公式用于计算点与点之间的距离，不过我们是否将所有的点与检索的点一一匹配呢，在传统的数据库中就是表扫描复杂度为： rows，在向量匹配的过程中如果抛开硬软件优化，按照上述公式得到的计算复杂性应该就是： rows * dim * 2。

举个极端点的例子，假设10亿数据普通数据库全表扫描复杂度是10亿，如果是1024d的向量匹配，复杂度应该是1024 * 2 * 10亿 = 2000亿，所以如果不在技术上寻求一些解法，传统的手法只能在少部分场景通过堆硬件来解决，应为你没有办法在同等数据量上去增加2000倍的硬件开销。

要寻找到相近的点就是一种“工程算法”，这里面就需要构建索引，而对照前文在1维空间中的分组，我们如果在2维也用类似的方式来做，会是什么样的呢？

沿着这种思路同理构建高纬空间的分组，在检索的过程中就像一个图结构的检索过程，可理解为算法中的“Graph-based indexes”对应到AI里面的索引就是HNSW索引了，关于“Graph-based indexes”更专业的解释，以及还有“Hash-based indexes”、“Tree-based indexes”请关注文章： Accelerating Similarity Search on Really Big Data with Vector Indexing (Part II) - Zilliz Vector database learn

按照真实情况可以提前淘汰掉距离非常远的小组，那么：如何选择性淘汰分组在召回率和Latency上做更多平衡，如何在向量匹配复杂度上做进一步的性能提升，如何降低维度提升带来时间成本指数级上升，这就是计算机工程落地的技术问题了，知识所限这里就不展开了。

关于距离的比较，如果A、B与目标C比较，如果1维A与C的距离比B与C的距离大，是不是第2维就不用比较了？然后并不是，我们举个极端一点的例子，假设C是[0, 0], A和B分别是：[3, 1], [1, 4]，显然第1维A比B距离更大，但是整体距离，B距离C的距离会更大。这又是在高纬空间比较，并不能用传统意义上的一维一维的比较方式来完成。

--> 但可以完全确定是维度增加后，距离比起上一个维度算出来的距离一定是增加的。

可能一些玩法

烟囱模式，一家公司基于业务场景CASE BY CASE做，基于特定业务场景做特定的优化，例如：某公司知道向量的维度、数据量后，将所有的向量全部装入多台机器的多个GPU当中成为底库，然后充分利用GPU的并行计算能力计算多维数据，加上机器也可以并行，就是疯狂用硬件成本来对抗业务要求，如果你需要更大的QPS，可以提供更多的副本来完成；当然这是一种玩法，还有更多基于具体场景的千百怪的玩法，从模型、embedding、存储、装载、检索计算都可以case by case做，即使在同领域内的可复用性也不高只能试。

半烟囱，应用成熟的一些套件，组合用户的需求，已有套件能完成的直接使用，不能完成的尽可能适配，不能适配的看能不能改，不能改的就自己做，业务层依然是烟囱式CASE BY CASE做，只是会少一些，有很多问题不用自己去做了。

分层模式，按照我自己的理解（还未有三方参考依据），层次大致会是这样子划分：

 1. 基础研究性的工作，我理解是高校、科学家、大厂的科学研究组织去探索新的数学算法的可能性，我理解科学家也都不是神，他们依然需要大量的论证和实验过程，不是推导出来人脸识别可以用什么数学公式来解决，更多还是“尝试和不断实验”的方式得到的结论，另外具体一些场景结论也有来自于工程界的实践经验反馈。

2. 基础设施产品，如果没有这一层，前文提到的诸多问题以及还有更多未提到的工程问题需要在每个业务里面去重复花费大量精力去解决，数学公式在计算机里面要么得不到充分的发挥、要么可能需要数倍的硬件成本，除非有一群数学领域和计算机领域两方面都很强的人，但大多也只是在某个公司基于场景解决问题，无法将其能力复制。如果有一群人专注在这个方面，解耦：数学算法、工程算法的有效结合，将其做成像引擎以前，类似数据库、NoSQL、大数据等，那么上层的AI应用型产品就变得更为简单直接。当然要做到这一点很不容易，没错，写了这么久憋不住的广告终于要发出来了^_^，国产自研向量检索引擎Milvus还是一个咱们的骄傲，在AI基础软件设施这个赛道上无论是开源热度、开源界AI赛代的影响力、用户的涉及面都是王者位置，具体请参考官网和开源代码地址： Vector database - Milvus    The Milvus Project · GitHub

3. 基于基础设施，现在的原子服务已经有很多，不过有了基础服务，这些原子服务的开发变得非常简单，可以少关注很多问题，更加关注于数学算法、数据本身的选择，构建一个原子应用的时间和维护成本就变得很低了，同时可以有单独的团队来维护和优化，在云上大部分可以交给云服务去完成（云服务的正式release尽情期待）。

4. 原子积木化的AI服务有了，距离真正的业务还差一步之遥了，帮助业务成功也还需要理解业务需要解决核心问题以帮助其成功，积木化的服务需要有很强的灵活性去调整细节，同时需要有比较标准化的接口和规格参数，这样在构建真实的业务应用的时候就会变得“可复制性”很高，否则会非常难用（还不如自己搞）。

这样以来即使是对应业务的解法可复制性并不高（种类可能上百种），但是每一种的解法的定制成本足够低（当然前提是： 每一层下面一层的积木需要足够好用），再结合现代的流程编排工具进一步降低定制成本，这一层大家依然可以在投入产出比上获得更高的收益率。

也许这是一种比较理想的共赢局面，AI这个道路很多未知的区域需要我们大家一起去探索，这个文章很多内容是我一个小白的理解，内容可能有错误的地方请大家“照死里拍砖”，我应该会“选择性接受”  ^_^，后续如果有幸获得更多理解后续再补充。