共计 5582 个字符，预计需要花费 14 分钟才能阅读完成。
导读：百度富媒体检索比对系统是一套基于 Ann(approximate nearest neighbor)检索和内容特色比对技术，旨在提供针对图像、音频、视频等多媒体资源的类似检索系统。包含离线训练、建库，在线特征提取、检索。目前百度富媒体检索比对系统除了承接了百度 FEED 所有视频、图像的反作弊、下发去重以及关联举荐和黄反等业务，另外还反对了包含视频搜寻、贴吧、文库在内的数十个业务方，撑持了千亿级数据规模。在数据规模、零碎性能、召回率和准确度上都处于领先地位。
全文 5612 字，预计浏览工夫 11 分钟。
一、背景
随着互联网和 AI 技术的倒退，网络信息的次要传输媒介，曾经从传统的网页文字倒退到图片、视频、音频等资源，绝对纯文字的网页，富媒体内容能传递更多的信息量，同时也带来更新的用户体验。随着富媒体内容急剧暴发, 了解这些实体内容，找到他们之间的类似关系，不仅可能对这些富媒体内容进行筛选和解决，还能够更好的被举荐和搜索引擎了解，更好的服务用户。
得益于神经网络的飞速发展，多媒体数据的检索问题通常能够转化为高维向量的相似性检索, 采纳 CNN(Convolutional Neural Network）的各种特色来形容这些多媒体资源的语义信息，基于 CNN 特征向量，将 query 与库中所有数据进行相关性计算，检索出相干的后果集。以图像为例，咱们首先会对存量图像，进行收录、筛选，计算它们的 CNN 特色，而后把这些 CNN 进行建库。当输出 query 图像，须要从历史库中检索出与之类似或雷同的图像时，咱们首先计算 query 图像的 CNN 特色，而后与历史库中的全量 CNN 特色进行计算（通常计算欧式或 cosin 间隔），选取间隔最近的 topk 个图像作为召回后果。通常状况下，咱们还会提取图像的视觉形容信息，来进行辅助后校验，进一步晋升召回的准确率。视频检索比对与图像相似，是在图像的根底上减少了关键帧的抽取，以及召回图像帧序列当前，会进行视频和音频级别的比对。
△图 1. 视频检索比对办法_
基于 CNN 特征向量的数据检索，数据量大、特色维度高以及要求响应工夫短。随着多媒体数据的快速增长，图像帧的数据量曾经达到千亿甚至万亿级别，在这种大规模数据集的检索上，传统的暴力计算尽管能满足准确度的需要，然而在计算资源和检索工夫的耗费上是微小和无奈承受的。为了升高搜寻的空间复杂度与工夫复杂度，在过来的十几年里研究者们找到了一种可供代替的计划：近似最近邻 (Approximate Nearest Neighbor) 检索办法。它们往往通过对向量汇合进行预处理，生成一些能够用来领导查找过程的常识，在查找时以就义肯定精度的形式减速查找过程。
二、整体架构
百度富媒体内容比对系统，是一套包含离线 ANN 训练、建库和模型训练，在线特色预估、检索比对等性能在内的通用多媒体资源检索比对系统，解决的资源包含图像、视频和音频。
__△__图 2. 整体架构
- cnn-service: 用来提取资源特色的模块，包含图像、视频和音频三种类型资源的特征提取;
- feature-sevicez: 对立特色模块，提供对立特征提取和缓存性能，对下层暗藏异构 cnn 特色，可配置化拜访指定 cnn-service;
- vs-image: 召回前，拜访 feature-service 计算 query 的特色，而后申请 as 获取 ann 检索召回后果，进行视频和音频级别的比对;
- bs: Ann 索引服务，通过 cnn 特色，计算 topk 召回，而后进行视觉特色后校验，最终失去召回后果。反对多分片和分片的自动更新、扩容;
- as: 反对 bs 多分片的并发拜访和异构索引的检索 merge;
- finger-builder: 资源入库对立入口，获取资源 cnn 特色数据，并写入 afs；
- index-builder: 定时 ann 索引建库；
三、利用场景
- B 端反作弊
- 作者上传、抓取视频全笼罩
- 每天过滤 60%+ 的反复视频，加重审核压力
- 高准确率，严格反作弊
- 百家号发文、UGC、小程序、贴吧等
- C 端下发去重
- 用户体验
- 原创爱护，生态建设
- 关联举荐
- 短带长，引入厂外长视频资源，可为用户关联以后视频的完整版
- 风控
- 涉政、黄反等敏感资源的辨认和屏蔽
__△__图 3. 业务利用
四、关键技术
1、ANN
ANN 搜寻办法通过将全空间宰割成很多小的子空间，在搜寻的时候，通过某种形式，疾速锁定在某一（几）子空间，而后在该（几个）子空间里做遍历，从而达到次线性的计算复杂度。正是因为缩减了遍历的空间大小范畴，从而使得 ANN 可能解决大规模数据的索引。常见的 ANN 检索算法有：
- 基于树的办法：经典实现为 KD-Tree、Annoy 等。Annoy 的外围是一直用选取的两个质心的法平面对空间进行宰割，最终将每一个辨别的子空间外面的样本数据限度在 K 以内通过将空间按维度进行划分，放大检索范畴的办法来减速，实用于空间维度较小的状况。
- 基于 Hash 的办法：经典实现为 LSH、PCAH 等，LSH 的核心思想是：在高纬度空间相邻的数据通过哈希函数的映射投影转化到低维空间后，他们落入同一个吊桶的概率很大而不相邻的数据映射到同一个吊桶的概率很小。在检索时将欧式空间的间隔计算转化到汉明空间，并将全局检索转化为对映射到同一个吊桶的数据进行检索，从而进步了检索速度。
- 矢量量化办法：PQ、OPQ 等，PQ 的次要思维是将特征向量进行正交合成，在合成后的低维正交子空间进行量化，采纳较小的码本进行编码，从而升高存储空间。
- 基于倒排索引的办法：IVF、IMI、GNO-IMI 等。
- 基于图的办法：NSW、HNSW、NSG 等。
2、GNOIMI
GNOIMI(The Generalized Non-Orthogonal Inverted Multi-Index)是百度内自研实现的 ANN 检索引擎，它通过聚类的形式将空间宰割成许多子空间。在检索的时候，通过某种形式，疾速锁定在某一（几）子空间，而后在该（几个）子空间里做遍历，从而达到次线性的计算复杂度。
CNN 特色通常特色维度高，保留全量数据特色所需内存与样本数据量成正比。对于千万级以上的数据集，通常面临内存受限的问题。GNOIMI 应用 PQ 乘积量化的办法，用一个无限子集对全量特色空间进行编码，达到大幅的升高内存耗费的目标。
1. 训练
1)空间宰割
GNOIMI 应用聚类的办法对训练集特征向量空间进行宰割。
用户保障原始特色数据无反复，从原始数据中随机抽样。抽样数据集个数小于等于 500w，。
对抽样样本进行 KMEANS 聚类，失去初始的一级聚类核心。计算抽样本与其所属一级子空间聚类核心的残差向量，在残差向量上进行 K -means 聚类，将残差向量空间分为 L 个子空间，失去二级聚类核心码本。一二级聚类核心将整个数据空间宰割为个子空间（cell），每个 cell 的聚类中心点定义为。任一训练集样本特征向量所属的 cell，满足。
空间宰割如图 4 所示，所有一级聚类核心共享二级聚类核心。
__△__图 4
因为二级聚类核心应用的是全量原始特色的残差向量，因此认为二级聚类核心在每个一级子空间内散布类似，全量原始特色数据共享二级聚类核心。这种办法被称为 NO-IMI(The Non-Orthogonal Inverted Multi-Index)。蓝色点为一级聚类中心点，红色点为个 cell 的聚类中心点。显然，cell 的形态和大小需依据数据分布可变，尤其是在全量特色数据空间同时存在稠密和密集区域时。引入参数矩阵，cell 的聚类中心点定义为。引入参数矩阵后 cell 散布如图 5 所示，cell 的形态和大小依据理论数据分布可变，空间宰割更合乎一级子空间内数据分布状况。参数矩阵是有全量数据计算失去的，因此更精确的形容数据分布，称这种办法为 GNO-IMI。
__△__图 5
2)乘积量化
计算抽样数据集中样本所属于的一二级间隔核心，失去样本与一二级聚类核心的残差数据集。将残差数据集分为 nsq 个空间，每个子空间特色维度为 feature\_dim/nsq，每个子空间别离进行 KMEANS 聚类，失去 256 个聚类核心(一个 char 占 8bit，可用一个 char 字长标记所有的聚类核心 ID)，失去每个子空间的码本。将 nsq 个子空间的子码本做笛卡尔积，失去整个数据集的 PQ 码本。
2. 建库
计算原始特征向量数据集中样本所属的一二级聚类核心。
计算原始特征向量数据集中样本与其所属的一二级聚类核心的残差。将残差向量分为 nsq 个子空间，在每个子空间内，计算该子特征向量间隔最近的聚类核心并记录聚类核心 ID，将 feature\_dim 维度的特征向量映射为 nsq 个聚类核心的 ID，可用 nsq 个聚类核心 ID 标识该特征向量。通常取 nsq = feature\_dim 进行四分之一量化，feature\_dim * sizeof(float) -> nsq *sizeof(char)。
在检索过程中，将 query 与该样本在每个子空间内的间隔，转化为与该样本间隔最近的聚类核心的间隔。因此，在检索过程中，无需加载原始特征向量，可升高检索过程中所须要的内存。
3. 检索
1) 特色进行归一化;
2) 计算 query 与一级聚类核心的间隔并排序;
3) 计算 query 与前 gnoimi\_search\_cells 个一级聚类核心下的二级聚类核心的间隔并排序，共计 gnoimi\_search\_cells * gnoimi\_fine\_cells\_count 个二级聚类核心;
4) 以优先队列的形式，从最近的二级聚类核心开始，顺次取出其下的样本，并计算 query 与这些样本的间隔，取满 neighbors\_count 个为止;
5) 排序后返回 topK 个样本和对应的间隔
4. 实现
ANN 的算法自身并不算简单，难点次要在实现上，GNOIMI 做了大量实现优化，简要介绍如下：
1）设计新的训练计划，从新组织一二级聚类核心的关系，在召回率稍微晋升的前提下，训练速度晋升 1000%。
2）对于 L2/COS 间隔空间下，任意三点满足三角不等式；在建库阶段，依据该特质，利用样本、一级聚类核心和二级聚类核心之间的两两间隔进行剪枝，可升高 95%+ 的计算量，建库速度晋升 550%+。
3）训练 & 建库所需内存大大降低，仅为 Faiss-IVF* 和 nmslib-HNSW 的 10%。
4）在检索阶段，空间宰割规模超过千万，计算 query 与二级聚类核心过程中，设计新的计算 & 排序逻辑，将百万级聚类核心的计算 & 排序时延管制在 2ms 内，升高 20 倍。计算 query 与样本间隔时，优化 PQ 量化计算过程，升高 800%+ 的计算量，整体吞吐晋升 30%+。
5. 利用
GNOIMI 与 IVF* 比拟时，应用雷同聚类核心个数及检索 doc 个数下，比拟检索工夫、召准和内存；与 HNSW 比拟时，在雷同检索工夫下，比拟召准和内存。
通过测评，百万数据量级雷同检索工夫内 GNOIMI 成果略低于 HNSW，远超 ivf，内存占用极小，HNSW 成果最优，但内存耗费最多。随着数据增多，维度增大，雷同检索工夫内 GNOIMI 成果相比其余更优，内存放弃低增长。
目前 GNOIMI 广泛应用于百度内各种场景，包含视频比对、图片 / 视频检索、FEED 等等场景，撑持规模上千亿特色，每天 PV 过 10 亿
3、HNSW
HNSW（Hierarchical Navigable Small World）是 ANN 搜寻畛域基于图的算法。它的前身是 NSW (Navigable-Small-World-Graph)。NSW 通过设计出一个具备导航性的图来解决近邻图发散搜寻的问题，但其搜寻复杂度依然过高，达到多重对数的级别，并且整体性能极易被图的大小所影响。HNSW 则是着力于解决这个问题。作者借鉴了 SkipList 的思维，提出了 Hierarchical-NSW 的构想。简略来说，依照肯定的规定把一张的图分成多张，越靠近下层的图，均匀度数越低，节点之间的间隔越远；越靠近上层的图均匀度数越高，节点之间的间隔也就越近（见下图 6）。
搜寻从最上层开始，找到本层间隔最近的节点之后进入下一层。下一层搜寻的起始节点即是上一层的最近节点，往返循环，直至找到后果。因为越是下层的图，节点越是稀少，均匀度数也低，间隔也远，所以能够通过十分小的代价提供了良好的搜寻方向，通过这种形式缩小大量没有价值的计算，缩小了搜索算法复杂度。更进一步，如果把 HNSW 中节点的最大度数设为常数，这样能够取得一张搜寻复杂度仅为 log(n) 的图。
__△__图 6. hnsw
HNSW 的一个显著长处是无需训练，在某些没有初始数据的场景十分好用。
目前百度内容侧应用的是 hnsw 的一种优化实现，在开源版本的根底上，做了很多优化，性能晋升了将近 3.6 倍。
五、比对技术
1. 图像比对
目前次要有两种表征图像的办法：部分特色点和图像 CNN 向量。
- 部分特色点：对图片的视觉形容，如 SIFT、ORB 等，对尺度、旋转、亮度放弃不变，视觉变动、防射变动、噪声也有肯定的稳定性。
- 图像 CNN 特色：对图像的语义特色，通常应用 CNN 分类模型等的最初几层网络输入。
△图 7
因而以后比对技术，采纳 CNN 特色筛选 + 视觉部分特色后校验
△图 8
2. 视频比对
视频比对复用了图像比对的技术，在帧检索的根底上减少了视频和音频级别的比对技术，次要是基于动静布局计算最佳匹配序列。
△图 9
六、总结
近年来，随着计算机技术的倒退，图片、视频、音频等富媒体信息的呈井喷式增长，内容检索比对技术在举荐、搜寻等各个领域也有了更宽泛的利用。本文对百度富媒体检索比对系统的基本原理和核心技术进行了一次全面的总览介绍，同时介绍了各模块的工作机制，包含：特征提取、离线训练建库、在线预估、检索比对等。它提供了一套通用的多媒体资源检索比对计划，保障了高召回、高精确和高性能。基于百度 FEED 和搜寻两大外围业务，它领有全网最大的数据规模和最丰盛的资源类型，涵盖了短视频、小视频、直播、图片等绝大数富媒体资源，服务于 30+ 产品线，为百度产品的成果晋升提供了无效的辅助。
