量化和近似最近邻搜索优化方案

二值哈希编码将原始高维数据特征投影为低维二值码，将近似最近邻搜索的计算复杂度降低到次线性甚至常数时间复杂度，而且在内存消耗问题上也很有优势。但是二值哈希的局限性表现在:优化目标中由于二值码的存在常常引入不连续项很难优化；而且二值码的表达能力有限，很多数据点与查询样本具有不同的汉明距离，在检索结果中不能被准确排序，影响了近似最近邻检索的精度。基于量化的编码将原始高维特征投影为码本中最近的码本单词(聚类中心)的整数索引，可以看作一种整数哈希方法。

一、量化和基于量化的近似最近邻搜索

与二值哈希编码相比，基于量化的近似最近邻搜索具有以下特点:

(1)量化编码的表达能力更优，而且目标函数不存在不连续项，优化过程相对更容易求解。

(2)量化编码同样具有内存占用低的优势。量化编码中每个数据样本被量化到最近的聚类中心，因此每个数据样本仅需要保存其最近的聚类中心的索引(通常为整数)，因此仅占用很低的内存。

(3)基于量化编码的相似性查询同样具有计算效率高的优势。检索时查询图像被量化到最近的聚类中心，因此相似性查询转变为聚类中心之间的距离计算。如果提前聚类中心之间的距离并存储在距离查找表中，那检索时仅需要查表操作，因此具有很高的计算效率。(www.xing528.com)

二、基于量化的近似最近邻搜索方法

基于量化的近似最近邻搜索可以分为传统方法和基于深度学习的方法。传统的量化方法采用人工设计的特征，可以分为无监督量化和监督量化。代表性的无监督量化方法主要包括乘积量化(product quantization，PQ)和组合量化(composite quantization，CQ)。其中，乘积量化将高维向量空间分解为有限个子空间的笛卡儿积，然后分别量化这些子空间，距离计算采用对称距离或非对称距离；乘积量化是在矢量量化(vector quantization，VQ)的基础上发展而来的量化方法，乘积量化器可以非常低的存储器/时间成本生成指数级的码本。何凯明团队进一步提出优化的乘积向量，通过在空间分解和量化码本方面最小化量化失真实现对乘积量化的优化，包含两种新的优化方法:一种是交替求解两个较小的子问题的非参数方法，另一种是在输入数据服从某种高斯分布的情况下保证获得最优解的参数化方法。组合量化提出一种新的复合量化的压缩编码方法，其思想是:利用从字典中选择的几个元素的组合来精确地近似一个向量，并由所选元素的索引组成的短代码来表示该向量，有效地利用短代码计算查询点到候选数据点的近似距离。代表性的监督量化方法包含监督组合量化(supervised composite quantization)等。监督组合量化提出了一种紧凑的编码方法——监督量化，该方法同时学习特征选择，将数据库点线性转换为低维判别子空间，并对变换后的空间中的数据点进行量化，优化准则是量化后的点不仅精确地逼近变换后的点，而且在语义上可分离。

随着深度学习的发展，人们利用深度神经网络端到端地进行特征提取和量化，以期获得更高的检索性能。这方面代表性工作包括:深度量化网络(deep quantization network，DQN)提出一种新的用于监督哈希的深度量化网络架构，该架构学习了与哈希编码兼容的深度图像表示，并在优化框架中形式化地控制量化误差；深度视觉语义量化(deep visual semantic quantization，DVSQ)是第一个从带标签图像数据和一般文本域的语义信息中学习深度量化模型的方法，主要贡献在于使用精心设计的混合网络和指定的损失函数共同学习深层视觉语义嵌入和视觉语义量化器，支持最大内积搜索，同时基于快速查找距离表的学习码本计算，实现图像高效检索；乘积量化网络(product quantization network，PQN)将视频数据的帧级特征学习、帧级特征聚合和视频级特征量化集成在一个神经网络中，其中乘积量化作为卷积神经网络的一个层，输入为来自低层的特征，输出为特征的量化结果；其它研究包括采用不对称三元组损失进行优化以提升视频检索性能等。

总体而言，相比二值哈希方法，目前基于量化的近似最近邻搜索的研究还比较有限。