9.7 研究进展
哈希学习由 Salakhutdinov et al [13-14] 于 2007 年推介到机器学习领域 , 近几年迅速发展成为机器学习领域和大数据学习领域的一个研究热点[15-23] , 并广泛应用于信息检索[27-28] 、数据挖掘 [29-30] 、模式识别[31-32] 、多媒体信息处理 [33-34] 、计算机视觉 [35-36] 、推荐系统[37-38] , 以及社交网络分析 [39-40]等领域。
下面将对已有的代表性哈希学习方法进行简单介绍。
基于松弛的两步学习策略
由于从原空间中的特征表示直接学习得到二进制的哈希码是一个 NP 难问题[15] , 现在很多的哈希学习方法[15,18,20-21]都采用基于松弛 (relaxation) 的两步学习策略。第一步 , 将哈希码的学习过程从离散（二进制）空间松弛（relax）到实值空间中 , 得到一个度量学习 (metric learning) [41] 模型 , 然后利用该度量学习模型进行降维 , 得到一个低维空间的实数向量表示 ; 第二步 , 对得到的实数向量进行量化 ( 即离散化 ) 得到二进制哈希码。 现有的方法对第二步的处理大多很简单 , 即通过某个阈值函数将实数转换成二进制位。通常使用的量化方法为一个阈值为0 的符号函数 , 即如果向量中某个元素大于 0, 则该元素被量化为 1；如果小于或等于 0, 则该元素被量化为 0。 例如 , 假设样本在原空间中的特征表示为一个 5 维实数向量 (1.1, 2.3, 1.5, 4, 3.2), 经过某种度量学习 ( 通常把降维看成度量学习的一种 ) 处理后得到一个 3 维的实数向量 (1.8, -2.3, 0.6), 然后经过符号函数量化后 , 得到的二进制哈希码为 (1, 0, 1)。一般来说 , 度量学习阶段首先要构建学习模型 , 然后对模型参数进行优化和学习。
下面从学习模型、参数优化、量化策略三方面介绍基于松弛的两步学习策略的最新进展。
根据学习模型 ( 一般指度量学习阶段的模型 )是否利用样本的监督信息 ( 例如类别标记等 ), 现有的哈希学习模型可以分为非监督模型[19-21] 、半监督模型[18,42-43]和监督模型[31,44-45] 。非监督模型又可以进一步细分为基于图的模型[20]和不基于图的模型[19,21] , 监督模型又可以进一步细分为监督信息为类别标记的模型[31,44]和监督信息为三元组或者排序信息的模型[45] 。实际上 , 这每一个细分的类对应于机器学习中一个比较大的子方向 , 例如基于图的模型。由此可以看出 , 哈希学习实际上是一个覆盖范围非常广的研究领域，具有广阔的应用前景。此外 ,度量学习是机器学习领域的研究热点之一 , 而度量学习方面的工作刚好可以用来实现基于松弛的两步学习策略的第一步 , 因此目前很多哈希学习模型 ( 包括非监督、半监督和监督 ) 只是直接利用或者简单改进已有度量学习模型 , 然后采用上述的符号函数进行量化 , 得到哈希编码。经过一些探索[21,23,28] , 我们发现度量学习得到的结果通常是在模型目标函数的限制下使得信息损失最小 , 因此得到的总是最优的结果 ; 而在将度量学习应用到哈希学习中时 , 除了第一步的度量学习可能造成信息损失外 , 第二步量化过程的信息损失对性能的影响也非常大 , 有时甚至超过第一步造成的信息损失 , 因此 , 第一步度量学习得到的最优结果并不能保证最终量化后的二进制编码为最优。目前 , 很多哈希学习方法没有将量化过程中的信息损失考虑到模型构建中去。
现有的参数优化方法大概可以分为两类。第一类是采用与传统度量学习的优化方法类似的策略 ,对所有位对应的(实数)参数一次性全部优化[15,20] 。这种策略带来的一个不利后果是没办法弥补量化过程带来的信息损失, 有可能导致的结果是随着哈希码长度的增大 , 精确度反而下降。 第二类是避免一次性全部优化所有位对应的 ( 实数 ) 参数[18,23,42] , 而采用按位 (bitwise) 优化策略 , 让优化过程能够自动地弥补量化过程中损失的信息。实验结果表明 , 即使学习模型的目标函数相同 , 采用按位优化策略能取得比一次性全部优化所有参数的策略更好的性能。 但按位优化策略对模型目标函数有一定的要求和限制 , 比如目标函数可以写成残差的形式[23] 。目前 , 大部分哈希学习方法还是采取一次性全部优化所有参数的策略。
哈希学习与传统度量学习的一个本质的区别是需要量化成二进制码。现有的哈希学习方法大多采用很简单的量化策略 , 即通过某个阈值函数将实数转换成二进制位。 最近出现一些专门研究量化策略的工作[28,46-47] , 并且发现量化策略也会影响哈希学习方法的性能 , 至少与第一步的度量学习阶段同等重要。我们在文献 [28,46] 中 , 采用对度量学习阶段得到的每一个实数维进行多位编码的量化策略 , 取得了比传统的单位编码策略更好的效果。一般来说 , 度量学习的结果中 , 各维的方差 ( 或信息量 ) 通常各不相等[19,21] 。而现有的很多方法采用“度量学习 + 相同位数编码”的策略[15,20] , 导致的结果是随着哈希码长度的增大 , 精确度反而下降。一种更合理的量化策略是 ,采用更多的位数编码信息量更大的维。目前 , 有部分工作在这方面进行了尝试 , 取得了不错的结果[47] 。
离散哈希学习
基于松弛的两步学习策略将哈希码的学习过程从离散空间松弛到实值空间中 , 得到一个度量学习模型，然后再将度量学习得到的实值向量量化到离散空间中。 这个过程与原始的哈希学习目标存在一定的偏离 , 因此，学习到的哈希码效果往往不是很理想。一种更好的策略是采用离散优化来直接学习离散的哈希码，这类方法叫做离散哈希学习方法。
现有的离散哈希学习方法可以分为两大类，即半离散方法和完全离散方法。半离散方法[48-50]通常在原始目标中不采用将目标离散变量松弛到实值空间的策略 , 而引入新的实值变量将部分复杂约束 ( 例如正交约束 ) 松弛到实值空间 , 然后采用交替优化的策略 , 使得优化过程中新引入的实值变量和目标离散变量之间相互作用（尽可能接近）让目标离散变量尽可能地满足约束。完全离散方法[51]不引入新的实值变量，而是直接对目标离散变量进行离散优化得到哈希码。研究表明 , 离散哈希学习能显著提高哈希查询的召回率[48] , 从而有效地避免使用哈希查询时的空桶现象。 目前的离散哈希学习方法已经在无监督哈希[48] 、监督哈希 [49,51]中取得了一定的进展 , 并应用到协同过滤[50]等场景中。
深度哈希学习
传统的哈希学习一般基于手工特征 ( 如 SIFT、GIST 等 ), 而深度学习提供了一种更好的特征提取框架 , 并使得在哈希学习中采用端到端的学习方式成为可能。 因此 , 近期出现的深度哈希学习将深度学习和哈希学习结合起来，成为一个新的研究热点。
虽然有些深度哈希学习方法[52]也直接利用手工特征作为输入，但大部分深度哈希学习方法利用了深度学习的自动特征学习能力 , 下面对这些具有自动特征学习能力的方法进行介绍。
早期的深度哈希学习方法[53]将基于深度学习的特征学习过程和哈希码学习过程分割成两个互不影响的两个阶段，即先基于监督信息学习得到哈希码，然后用哈希码来指导特征学习过程，这两个阶段之间没有相互反馈。因此，这类方法学习得到的特征和哈希码并不一定能取得满意的结果。近期出现的深度哈希学习方法[54-59]利用端到端的方式 , 将特征学习过程和哈希码学习过程整合到一个统一的框架中，使得特征学习过程和哈希码学习过程可以相互提供反馈。实验结果表明，这类方法取得了比基于手工特征的方法更好的精确度，而且优于将特征学习过程和哈希码学习过程分割成两个阶段的深度哈希学习方法[53] 。