【《标量量化算法综述》4400字】

标量量化算法综述标量量化算法是以哈希方法为基础的算法。广义的来讲，哈希方法是通过哈希函数把向量变成二值码，然后通过海明距离（HammingDistance）进行距离度量。这个方向的研究焦点集中在哈希函数的设计及其优化。哈希编码即将数据库中的高维向量转化为二进制向量，同时尽可能保持原始空间中点之间的距离关系。哈希编码就是采用某种映射的方式将包含n个向量的数据库矩阵D=Rnm映射为二进制矩阵H=Bnk，矩阵中每个值为二进制的0或1，k为二进制的码长。对于查询点q∈ℝm，采用同样的哈希方法将其映射为Hq∈Bk。两个二进制表达Hq1.1传统哈希学习方法在2014年之前，大多数哈希方法都依赖于传统的两步哈希框架：投影和量化。在投影阶段，使用k个哈希函数将原始空间中n个m维的点映射到k维的投影空间P中，该映射要尽可能保持原始空间中点间的相似度关系。在量化阶段，使用k个阈值将投影空间中的点映射到二进制空间B中，即将其每一维度映射为0或1。早期的哈希方法以Datar等人提出的LSHREF_Ref70609698\r\h[22]（LocalitySensitiveHashing）算法为代表，LSH算法用随机投影的方式把向量变成二值码。最初LSH在倒排索引（InvertedIndex）用于实现最近邻的快速搜索，后来更多地用于产生随机二值码。由于这种随机生成二值码的方法没有利用原始数据集来建立哈希函数，其检索精度不够理想。随后，大量的研究开始利用数据集来学习更好的哈希函数，其中Weiss等人提出的的谱哈希（SpectralHashing）算法REF_Ref73720830\r\h[23]便是早期工作之一，这种算法将最小化量化后的海明距离与原始向量相似度的乘积作为优化目标，将学习离散编码的问题转化为解特征函数的问题。Kulis等人提出了二值化重建嵌入方法REF_Ref70609893\r\h[24]（BinaryReconstructiveEmbedding），该方法以最小化距离重建误差为目标构建哈希码。后续还有Wang提出的Semi-SupervisedHashingREF_Ref70609916\r\h[25]等。这类方法的目标都是保持量化后离散编码的海明距离与原始向量的欧式距离足够接近，即保持相似技术路线。二进制哈希码量化问题主要通过控制量化误差提升检索性能。不同于保持相似，Gong等人受多类谱聚类松弛解离散优化算法启发，提出了迭代量化（ITQ，IterativeQuantization）REF_Ref70609947\r\h[26]方法。该方法直接优化二值编码，利用欧氏距离旋转的不变性，建立了最小化量化误差的目标函数，求解最优空间旋转矩阵与二值编码。相比谱聚类算法，ITQ无需数据集必须服从均匀分布的硬性条件，可以更好地控制量化误差。1.2深度哈希学习方法随着深度学习的发展，深度哈希学习方法受到越来越多的关注，此类方法以深度神经网络作为哈希函数。深度哈希学习方法相较传统的哈希方法有两点优势：（1）深度学习强力的表达能力能够学习到更为复杂的哈希函数。（2）深度哈希学习能够实现端到端的哈希编码，便于提高检索性能。深度哈希学习方法所解决的问题可以描述为：对于检索图像I，通过卷积神经网络模型FI;W得到其对应的深度视觉特征x∈ℝm，而深度哈希学习的目标就是找到一个非线性的哈希函数f:x→h∈−1,1K来编码，通过令其不断的接近标志函数深度哈希学习方法可以分为无监督以及监督深度哈希学习方法，两者的主要区别在于是否使用相似度语义信息标签S=s无监督深度哈希学习方法无监督深度哈希学习方法主要依赖于卷积神经网络模型以及生成对抗网络模型（GenerativeAdversarialNetworks，GAN）。其中，Lin等人基于卷积网络模型提出了DeepBitREF_Ref73567237\r\h[27]，该方法使用一系列的非线性投影函数计算二值描述子（BinaryDescriptors），并以保留原始图像的可区分信息，减少量化误差以及二值码均匀分布作为训练目标。图2.11SADH网络模型结构REF_Ref73567465\r\h[28]Shen等人提出了一种无监督深度哈希学习模型SADHREF_Ref73567465\r\h[28]（SimilarityAdaptiveDeepHashing）。如图2.11所示，SADH利用相似度矩阵有效保留了数据的相似度，优化学习到的二进制哈希码。SDAH首先利用深度学习模型构建相似度矩阵Aij，得到拉普拉斯矩阵： L=diagA1−A.并利用这个拉普拉斯矩阵来约束二值码B: minBTrBL除了基于卷积网络的无监督深度哈希学习模型外，一些方法使用GAN生成合成样本，令训练样本更加多样性，提升了深度哈希模型的泛化能力。其中，Cao等人提出了HashGANREF_Ref73567689\r\h[29]，如图2.12所示，该方法网络模型包含：生成器（Generator）、判别器（Discriminator）以及编码器（Encoder）。其中，生成器与判别器共享网络参数，通过降低对抗损失，提升模型的泛化能力。并在编码器中利用贝叶斯框架，通过引入余弦交叉熵损失与余弦量化损失进行哈希函数的无监督学习。图2.12HashGAN网络模型REF_Ref73567689\r\h[29]随后，Song等人在HashGAN的基础上提出了BGANREF_Ref73711767\r\h[30]，相比HashGAN，该方法主要探讨了二值码的训练方式以及损失函数的设计，并得到了两倍的检索性能提升。首先，在二值码的训练方式上，该方法提出了两个平滑的符号激活函数及其配套的平滑学习策略，对连续值进行二值化映射。其次，在损失函数设计方面，该方法的损失函数包括对抗损失、内容损失以及邻域结构损失。其中，邻域结构损失通过约束二值码的相似度矩阵，进而保持不同图像对二值码之间的相似度，令二值码具备一定的检索功能。监督哈希学习模型哈希学习（LearningtoHash）通过机器学习机制将原始特征数据映射成二进制离散编码。从原始特征空间的特征表示直接学习二进制离散编码是一个NP-hard问题。如图2.13所示，现有哈希学习方法中有两个一般性步骤：首先，利用哈希层对高维空间的特征数据进行降维转换，得到低维空间的实数向量。随后，对得到的实数向量进行离散化映射，进而得到离散二进制码。图2.13监督深度哈希学习模型一般性框架深度哈希学习同样依照上述的两个一般性步骤进行设计。当前有监督深度哈希学习模型基本框架包含三个部分，包括提取深度特征的骨干网络（Backbone）、对原始特征降维的的哈希层（HashLayer）以及损失函数（LossFunction）。其中，骨干网络是影响哈希学习检索精度的重要因素之一，骨干网络输出的视觉特征表达能力越强，包含的信息越多，检索精度越高。随着深度学习的发展，用于提取视觉特征的骨干网络也从早期的AlexNetREF_Ref70608160\r\h[5]、VGGNetREF_Ref70610136\r\h[31]发展到了现在表达能力更强的残差网络REF_Ref70609311\r\h[8]。绝大多数的哈希学习模型改变其骨干网络并不会影响其结构的完整性，因此哈希学习的研究大多聚焦于监督损失函数的设计以及二值码的训练方式。目前，绝大部分的深度哈希学习中二值码的训练方式可以分为两种：（1）基于连续值松弛（ContinuousRelaxation）的训练；（2）基于稀疏正则项的训练。基于连续值松弛的训练方式通过在哈希层添加sigmoid或tanh等标志函数（SignFunction）将原始特征映射到[0,1]或[-1,1]之间，测试阶段通过设定阈值0.5或0来得到二值编码。而基于稀疏正则项的训练方式是指在损失函数中添加正则项以约束哈希层的输出，并在测试阶段通过硬阈值量化得到二值编码。设计损失函数并控制量化误差是深度哈希学习中的重要一环。目前大部分的深度哈希方法基于度量学习技术对损失函数设计。其中，基于度量学习的监督损失的设计可以分为基于成对监督信息损失以及基于三元组监督信息损失。基于成对监督信息的深度哈希方法早期的深度哈希学习以成对的相似度保持（PairwiseSimilarityPreserving）作为监督约束。成对相似度保持通过包含相似信息的标签对生成相似性矩阵，并以此描述图像对之间的相似性信息。按损失函数的不同又可以分为基于平方损失以及交叉熵损失两种成对监督信息的利用方式。图2.14CNNH框架结构REF_Ref70610216\r\h[32]在基于平方损失的哈希学习方法中，Xia等人提出的CNNHREF_Ref70610216\r\h[32]以差值的形式最大程度的减少原始特征空间与海明空间的相似度或距离差异。如图2.14所示，该算法有两个阶段，第一阶段将相似矩阵分解为低维的哈希矩阵，得到每个样本对应的哈希编码。但是这个过程并没有学习到哈希函数，因此无法对新的图像进行哈希编码；第二阶段利用阶段一得到的哈希编码，以及每个样本对应的类别标签来训练网络，从而得到哈希函数。但该框架并不是端到端方法，其输入除了原始图像数据外，还需要第一阶段学习到的哈希编码，没有充分利用深度网络的学习能力。在基于交叉熵的哈希学习方法中以HashNetREF_Ref70610307\r\h[33]为代表方法。如图2.15所示，该方法利用连续值松弛近似得到二值编码，即利用增长平滑激活函数y=tanhβx中的参数β模拟离散的标志函数。在损失设计方面，HashNet基于交叉熵损失设计了加权成对交叉熵损失函数。实验结果表明，HashNet可以准确生成二进制哈希编码。图2.15HashNet网络结构REF_Ref70610307\r\h[33]然而，由于由于错误指定的损失函数，现有的哈希方法通常缺乏将相关图像集中在小的汉明球内的能力，因此它们对于汉明空间检索可能表现不佳。因此，DCHREF_Ref73485517\r\h[34]针对该问题联合优化损失函数和量化损失函数，并引入柯西先验来减小相似样本之间的相似度。Zhu等人提出的DHNREF_Ref70610229\r\h[35]提出了成对量化损失，利用成对量化损失优化成对交叉熵损失，但其无法精准定义二进制化前后的量化损失。除了使用平方损失函数与交叉熵损失函数外，Liu等人提出DSHREF_Ref70610197\r\h[36]根据海明距离，以原始特征空间与海明空间的相似乘积作为最小化优化目标。在二值码训练方式方面，DSH对实值输出正则化，令低维实值特征更加稀疏，最大化哈希码的可区分度。这种损失可以看做对哈希层的输入加入了对称的先验分布。基于三元组监督信息的深度哈希方法三元组损失实际上是有铰链损失函数改进而来，三元组由锚图像、与锚图像相似度高的图像、与锚图像相似度低的图像组成。该损失通过增大相似度低图像对之间的距离并减少相似度高图像对的距离来达到增大哈希码可区分度的目的。图2.16DNNH网络模型示意图REF_Ref70610279\r\h[37]其中，Lai等人基于三元组损失提出了DNNHREF_Ref70610279\r\h[37]。如图2.16所示，DNNH的分离编码模型包含两个部分：首先，为了减小二值码不同码值之间的冗余性，DNNH使用部分连接层代替全连接层，每个部分负责学习一个比特，各部分之间无连接。其次，为了保持特征空间与海明空间的相似程度，该方法引入了分段量化函数。在监督损失方面，该方法通过引入带有余量（Margin）三元组损失减少哈希编码的信息冗余，提升了输出二值码的检索精度。图2.17DTQ网络结构REF_Ref73485727\r\h[38]此外，Liu等人设计了DTQREF_Ref73485727\r\h[38]算法。如图2.17所示，该算法通过三元组量化损失减少二值码的冗余，并在网络中增大了相似图像对之间的哈希码相似性，增大了不相似图像对之间的哈希码距离。与其他哈希方法不同的是，DTQ引入了乘积量化中码书矩阵参数[C1,C2,…, Q=m=1与通过度量损失提升检索精度的方法不同，DSDHREF_Ref70610330\r\h[39]聚焦于二值码的优化算法，利用离散循环坐标下降算法进行二值码的优化训练。该方法的优势在于可以保持网络优化过程的离散型，但是这也导致了DSDH不能进行端到端的训练，在实际应用上具有一定的局限性。Lin提出的DBHREF_Ref70610291\r\h[40]利用分类损失（ClassificationLoss）进行相似度约束，但网络中的分类