详解百度富媒体检索比对系统的关键技术

时间  2021-05-11 标签 算法 小程序 缓存 网络 架构 并发 app ide 函数 性能

图片

导读：百度富媒体检索比对系统是一套基于Ann(approximate nearest neighbor)检索和内容特征比对技术，旨在提供针对图像、音频、视频等多媒体资源的类似检索系统。包括离线训练、建库，在线特征提取、检索。目前百度富媒体检索比对系统除了承接了百度FEED全部视频、图像的反做弊、下发去重以及关联推荐和黄反等业务，另外还支持了包括视频搜索、贴吧、文库在内的数十个业务方，支撑了千亿级数据规模。在数据规模、系统性能、召回率和准确度上都处于领先地位。
算法

全文5612字，预计阅读时间11分钟。小程序

1、背景

随着互联网和AI技术的发展，网络信息的主要传输媒介，已经从传统的网页文字发展到图片、视频、音频等资源，相对纯文字的网页，富媒体内容能传递更多的信息量，同时也带来更新的用户体验。随着富媒体内容急剧爆发, 理解这些实体内容，找到他们之间的类似关系，不只可以对这些富媒体内容进行筛选和处理，还能够更好的被推荐和搜索引擎理解，更好的服务用户。
得益于神经网络的飞速发展，多媒体数据的检索问题一般能够转化为高维向量的类似性检索, 采用CNN(Convolutional Neural Network）的各类特征来描述这些多媒体资源的语义信息，基于CNN特征向量，将query与库中全部数据进行相关性计算，检索出相关的结果集。以图像为例，咱们首先会对存量图像，进行收录、筛选，计算它们的CNN特征，而后把这些CNN进行建库。当输入query图像，须要从历史库中检索出与之类似或相同的图像时，咱们首先计算query图像的CNN特征，而后与历史库中的全量CNN特征进行计算（一般计算欧式或cosin距离），选取距离最近的topk个图像做为召回结果。一般状况下，咱们还会提取图像的视觉描述信息，来进行辅助后校验，进一步提高召回的准确率。视频检索比对与图像相似，是在图像的基础上增长了关键帧的抽取，以及召回图像帧序列之后，会进行视频和音频级别的比对。
图片图片△图1. 视频检索比对方法

缓存

基于CNN特征向量的数据检索，数据量大、特征维度高以及要求响应时间短。随着多媒体数据的快速增加，图像帧的数据量已经达到千亿甚至万亿级别，在这种大规模数据集的检索上，传统的暴力计算虽然能知足准确度的需求，可是在计算资源和检索时间的消耗上是巨大和没法接受的。为了下降搜索的空间复杂度与时间复杂度，在过去的十几年里研究者们找到了一种可供替代的方案：近似最近邻(Approximate Nearest Neighbor)检索方法。它们每每经过对向量集合进行预处理，生成一些能够用来指导查找过程的知识，在查找时以牺牲必定精度的方式加速查找过程。

网络

2、总体架构

百度富媒体内容比对系统，是一套包括离线ANN训练、建库和模型训练，在线特征预估、检索比对等功能在内的通用多媒体资源检索比对系统，处理的资源包括图像、视频和音频。图片△图2. 总体架构
架构

  • cnn-service: 用来提取资源特征的模块，包括图像、视频和音频三种类型资源的特征提取;并发

  • feature-sevicez: 统一特征模块，提供统一特征提取和缓存功能，对上层隐藏异构cnn特征，可配置化访问指定cnn-service;app

  • vs-image: 召回前，访问feature-service计算query的特征，而后请求as获取ann检索召回结果，进行视频和音频级别的比对;ide

  • bs: Ann索引服务，经过cnn特征，计算topk召回，而后进行视觉特征后校验，最终获得召回结果。支持多分片和分片的自动更新、扩容;函数

  • as: 支持bs多分片的并发访问和异构索引的检索merge;性能

  • finger-builder: 资源入库统一入口，获取资源cnn特征数据，并写入afs；

  • index-builder: 定时ann索引建库；

3、应用场景

  • B端反做弊

    • 做者上传、抓取视频全覆盖

    • 天天过滤60%+的重复视频，减轻审核压力

    • 高准确率，严格反做弊

    • 百家号发文、UGC、小程序、贴吧等

  • C端下发去重

    • 用户体验

    • 原创保护，生态建设

  • 关联推荐

    • 短带长，引入厂外长视频资源，可为用户关联当前视频的完整版

  • 风控

    • 涉政、黄反等敏感资源的识别和屏蔽

图片△图3. 业务应用

4、关键技术

一、ANN

ANN搜索方法经过将全空间分割成不少小的子空间，在搜索的时候，经过某种方式，快速锁定在某一（几）子空间，而后在该（几个）子空间里作遍历，从而达到次线性的计算复杂度。正是由于缩减了遍历的空间大小范围，从而使得ANN可以处理大规模数据的索引。常见的ANN检索算法有：

  • 基于树的方法：经典实现为KD-Tree、Annoy等。Annoy的核心是不断用选取的两个质心的法平面对空间进行分割，最终将每个区分的子空间里面的样本数据限制在K之内经过将空间按维度进行划分，缩小检索范围的方法来加速，适用于空间维度较小的状况。

  • 基于Hash的方法：经典实现为LSH、PCAH等，LSH的核心思想是：在高纬度空间相邻的数据通过哈希函数的映射投影转化到低维空间后，他们落入同一个吊桶的几率很大而不相邻的数据映射到同一个吊桶的几率很小。在检索时将欧式空间的距离计算转化到汉明空间，并将全局检索转化为对映射到同一个吊桶的数据进行检索，从而提升了检索速度。

  • 矢量量化方法：PQ、OPQ等，PQ的主要思想是将特征向量进行正交分解，在分解后的低维正交子空间进行量化，采用较小的码本进行编码，从而下降存储空间。

  • 基于倒排索引的方法：IVF、IMI、GNO-IMI等。

  • 基于图的方法：NSW、HNSW、NSG等。


二、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亿

三、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倍。

HNSW 压测qps cpu 内存
基线开源版本 900 25 66G
检索优化 900 1.6 80G


5、比对技术


1.图像比对

目前主要有两种表征图像的方法：局部特征点和图像CNN向量。

  • 局部特征点：对图片的视觉描述，如SIFT、ORB等，对尺度、旋转、亮度保持不变，视觉变化、防射变化、噪声也有必定的稳定性。

  • 图像CNN特征：对图像的语义特征，一般使用CNN分类模型等的最后几层网络输出。

图片图片△图7


所以当前比对技术，采用CNN特征筛选+视觉局部特征后校验图片△图8


2.视频比对

视频比对复用了图像比对的技术，在帧检索的基础上增长了视频和音频级别的比对技术，主要是基于动态规划计算最佳匹配序列。
图片△图9


6、总结


近年来，随着计算机技术的发展，图片、视频、音频等富媒体信息的呈井喷式增加，内容检索比对技术在推荐、搜索等各个领域也有了更普遍的应用。本文对百度富媒体检索比对系统的基本原理和核心技术进行了一次全面的总览介绍，同时介绍了各模块的工做机制，包括：特征提取、离线训练建库、在线预估、检索比对等。它提供了一套通用的多媒体资源检索比对方案，保证了高召回、高准确和高性能。基于百度FEED和搜索两大核心业务，它拥有全网最大的数据规模和最丰富的资源类型，涵盖了短视频、小视频、直播、图片等绝大数富媒体资源，服务于30+产品线，为百度产品的效果提高提供了有效的辅助。

阅读原文：详解百度富媒体检索比对系统的关键技术

更多干货、内推福利，欢迎关注同名公众号「百度Geek说」～

联系我们 沪ICP备2021010478号-7