哈希学习

哈希是信息检索中常用的技术，我们首先使用下图说明哈希在信息检索中的使用：

（a）多表查找：检索与每个表中的查询的哈希码对应的列表。 （b）单表查找：检索与查询的哈希码对应和接近的列表。 （c）哈希码排名：将查询与编码空间中的每个参考项进行比较。 （d）非穷举搜索：哈希表查找（或其他反向索引结构）检索候选者，然后对候选者进行哈希码排名

 早期的有关哈希的研究工作如Locality-sensitive hashing（LSH），需要很长比特的哈希码或者非常多的哈希表才能达到预期的性能。因此，最近的学术界更多的研究集中于基于学习的哈希，期望通过此方法学习到更有效紧致的哈希码。所谓哈希学习问题只指，对于数据x，我们期望学到它的紧致表达哈希码B（r比特），B是r×n的，同时期望学习到一个预测函数（哈希函数）。

因此我们可以定义Learning to hash为学习（复合）哈希函数的任务，即y = h（x），将输入项x映射到一段简洁的代码y上，目的是使查询q的最近邻搜索结果尽可能接近 真正最近的搜索结果，并在与此同时保证在编码空间搜索的高效性。 Learning to hash需要考虑五个问题：1）采用什么哈希函数h（x），2）在编码空间使用什么样的相似性（矩阵），3）在输入空间中提供什么样相似性（矩阵），4）为优化目标选择什么样的损失函数 ，以及5）采用什么优化技术。

[图片及描述来源：Wang, J.; Zhang, T.; Song, J.; Sebe, N.; Shen, H. T. (2016). A Survey on Learning to Hash. arXiv:1606.00185.]

发展历史

对于数据x，其对应的哈希码是离散的，因此在学习中不能用传统的梯度下降方法去解，这一问题是典型的混合整数问题，通常为NP hard（non-deterministic polynomial，缩写NP，非确定性多项式）问题。

在2015年之前，求解该问题基本分两步。第一步是将离散限制去掉，这就变成了连续优化的问题，可以用传统的梯度下降方法去求解，它的缺点是很难得到比较好的局部最优解；第一步去掉离散限制之后得到了连续的结果，第二步通过设定阈值进行二值化操作，比如将大于阈值的转为1，小于阈值的转为0，由此就得到了哈希码。为了减少量化损失，2011年 Yunchao Gong and Svetlana Lazebnik提出了迭代量化（ITQ）的方法，与多类谱聚类和正交Procrustes问题有关，它可以用于无监督数据嵌入（如PCA）和监督嵌入（如典型相关分析（CCA））。这种方法的缺点是对于长哈希码（比如超过100比特），量化偏差会很大，使得学出来的哈希码不是很有效。

2015年后，求解该问题开始转向离散优化，试图在不去掉binary constraint的条件下去解哈希问题。Fumin Shen和Heng Tao Shen等人提出了SDH，这是一个有监督的离散哈希工作。其假设有一个数据X，我们希望学习到它的二进制代码B，同时使其很容易被分类到Y（groundtruth）这个标签矩阵上，希望通过W这个矩阵将B很容易分到正确的类别上。由于SDH方法的损失函数不是通用的，他们于2016年发表文章试图找到一种方法满足loss是任意的，只要是平滑的就可以求解。该方法被证明一定是可以收敛的，并且比SDH更快，可以把该方法应用到有监督和无监督哈希中。

2017年，中国科学院提出了一种深度离散哈希算法（discrete hashing algorithm），该算法认为学习到的二值编码应该也可以用于分类。成对标签信息和分类信息在统一框架下用于学习哈希编码。他们将最后一层的输出直接限制为二进制编码，而这种做法在基于深度学习哈希算法中很少被研究。由于哈希编码的离散性质，他们使用交替优化方法来求解目标函数。实验结果表明，该方法在基准数据集上的表现要好过当时最好的哈希方法。

主要事件

发展分析

瓶颈

前文已经提到，哈希码是离散的，因此在学习中不能用传统的梯度下降方法去解，这一问题是典型的混合整数问题，通常为NP hard，而是NP 问题是计算机科学中最大的开放性问题之一。

未来发展方向

机器学习技术和「二次幂」这样的旧理论的工作结合起来可以计算机效率和能力的界限。哈希，甚至于数据索引的基本原理不会一夜之间就被机器学习策略替代，但是在算法中引入自主性的想法是强大而令人兴奋的概念。随着我们越来越善用机器学习，以及在提升计算机处理机器学习工作负载的效率上做出的不断的努力，利用这些优势的新想法肯定会找到其主流用途。

Contributor: Yuanyuan Li