哈达玛矩阵指导下的在线哈希学习新方法

作者 | 蒋宝尚

编辑 | 丛 末

越来越多的数据流，让视觉相似度检索在应用场景中越来越难，例如微信每天都会产生十几亿甚至上百亿的流数据网络图片，给相似图片搜索带来了挑战。而视觉哈希编码技术逐渐成为实现相似性检索的有效途径。

近日，厦门大学纪荣嵘关于在线哈希学习新方法的论文被发表在 IJCV 上，在论文中纪教授引入哈达玛矩阵指导哈希函数的学习，即吸取了传统在线哈希方法的优点，也最大程度上降低了精度损失。另外，对比当前最先进的七种技术，引入哈达玛矩阵的在线哈希学习都有一定程度的性能提高。

论文地址：https://arxiv.org/pdf/1905.04454.pdf

最近邻搜索在搜索领域一夫当关，作为一种找寻最优点的思路，在很多领域中都有很广泛应用，如：计算机视觉、信息检索、数据挖掘、机器学习，大规模学习等。

但最近邻搜索有两个关键问题：1、特征维度较高；2、数据量较大。例如，简单的穷尽搜索，需要将原始数据从存储中加载到内存，这将面临非常高的时间复杂度，成为现实应用中所必须解决需要解决的一个瓶颈问题。

为解决这个问题，近年来，在实际应用中出现了一些时间复杂度为次线性的、快速有效的最近邻搜索方法，例如KD树、Ball树、Metric树。但基于树的方法需要的存储空间往往很大，在某些时候存储这些索引树的空间甚至超过存储数据本身所需的存储空间。

不同于基于树的索引将数据空间进行递归的划分，哈希类算法重复的对整个数据空间进行二类划分，同时对于每一个划分进行一次二值编码。

即哈希算法将输入数据映射到一个离散的汉明空间，每一个数据点用一串二值码表示。汉明距离可以通过异或操作进行快速计算，因此使用哈希码对数据库进行穷尽检索，时间复杂度也能满足应用要求。

所以，哈希算法成为解决最近邻搜索的希望之一。而最近邻搜索思路在视觉相似度领域的应用也推动着哈希算法解决视觉相似性难题。

更进一步，网络数据流源源不断地产生使得数据库急剧增长，在线哈希学习成为减少视觉哈希编码复杂度不可或缺的技术途径。

吸取了传统在线哈希方法的优点，厦门大学的纪荣嵘，林明宝两位老师，引入哈达玛矩阵在线学习哈希函数，通过用Sylvester方法构造的正交二进制矩阵，其在一定程度上克服了强约束、需要大量的训练批次的困境。

此项工作日前已经发表在International Journal of Computer Vision（ 国际计算机视觉杂志）期刊上。作为人工智能领域最重要的顶级学术期刊之一，IJCV 每年出版的文章数量极小，但却拥有较高的影响因子（5年影响因子为12.389）。

1

方法介绍

根据纪教授在论文中介绍，这项方法被称为：哈达玛矩阵指导下的线哈希学习。旨在解决解决大规模流数据问题。方法的创新点在于引入哈达玛矩阵，矩阵中的每一列都作为目标代码来指导哈希函数的学习。

注：哈达玛矩阵，英文为Hadamard Matrix，定义是由+1和-1元素构成的且满足Hn*Hn’=nI（这里Hn’为Hn的转置，I为单位方阵）n阶方阵。

不同于传统的方法，该方案进行哈希编码的时候仅仅只需要利用当前阶段的流数据，因此学习效率在每一阶段都是恒等的。为此，作者把具有正交性质的哈达玛矩阵作为同一类流数据的目标编码，目标编码进一步作为感知机的虚拟类别来学习分类器。

另外，需要的训练设备要求较低，对于内存的需求仅需要满足一对数据的大小尽可，基于数据对的训练方式又极大压缩了训练时间的消耗。

为了释放强约束的需要，作者将哈达玛矩阵的每一列作为每个类标签的目标码，它本质上满足哈希码的几个期望性质。由于目标编码是已知的，不需要去设计很复杂的约束性条件。相比于目前已有的最佳方法，所题方案以更少的训练时间，在不同的数据集（CIFAR-10， Places205， MNIST、NUS-WIDE四个经典数据集）下获得10%～30%的精度增长，该技术可应用于大规模城市视觉目标布控、特定网络产品查找等。

2

方法细节

在线哈希框架：数据到来→在汉明空间中学习目标码→学习独立的二进制分类器进行预测

哈希学习的目的是学习一系列哈希编码，使得期望的邻域结构被保留。通过用一组哈希函数对数据集进行投影来达到此目标。

注：B是学习目标，即哈希编码，H(x)是哈希函数，X是数据集，sign 是符号函数，W是投影矩阵。

定义完学习目标之后，作者使用核技巧来利用线性模型的优势，同时使它们能够捕获非线性数据模型。具体而言，通过基于锚点的核函数将原始空间中的数据映射到特征空间，然后数据Xi有了一种新的表示，如下：

注：下标m，代表有m个锚点。

为了获得这些锚，作者假设了在初始阶段有m个数据点可用。因为在收集到m个数据点之前，学习过程不会开始。所以这m个数据点被认为是内核技巧中使用的m个锚。另外，在核函数方面，作者使用了高斯径向基函数核。例如：

注：η2 被定义为在学习过程中需要调整的宽度。

整个算法的流程如上图所示。其中，W-ensemble为：

注：π^t是可调参数，作者设置 π^t=1/T

3

实验

在实验部分，作者使用了几种最先进的方法进行了大规模的图像检索实验，用到了四个广泛使用的数据集，即CIFAR-10、 Places205、MNIST、NUS-WIDE。

CIFAR-10：该数据集共有60000张彩色图像，这些图像是32*32，分为10个类，每类6000张图。作者将整个数据集分为59K图像检索集，以及1000图像的测试集。此外，作者从从检索集中随机抽取20000张图像组成训练集来学习哈希函数。

Places205：作为Places 数据集的一个子数据集，里面包含250万张图像，205个场景类别。作者首先从AlexNet的FC7层提取每个图像的特征，然后通过执行PCA将其表示为128维特征。为了拆分整个数据集，作者从每个类别中随机选择20个实例，其余的被视为检索集。最后，使用检索集中的100K图像的随机子集来更新哈希函数。

MNIST：数据集包含从0到9的70000手写数字图像。每个图像均由784像素的归一化原始像素表示。作者将数据集分为一个测试集，一个检索集。

NUS-WIDE：从Flickr收集，包含296648张图，共有81个标签，作者根据前10个频繁标签从整个数据集中保留了186577张标记图像，其中2000幅图像作为查询集，其余的作为检索集。并从检索集中随机抽取40000张图像作为训练集。

评价指标有两个，分别为：mAP（ mean Average Precision）、Precision@H2（Precision within a Hamming ball of radius 2）。比较的基准方法有七个，分别为：OKH、SketchHash、AdaptHash、OSH、MIHash、BSODH、HCOH。

在CIFAR-10中mAP、 Precision指标的性能表现如上。

在CIFAR-10数据集的mAP指标上，除了在48-bit的实验中，HCOH略胜HMOH一筹。其他实验都是HMOH更加优秀。而在Precision@H2指标下，HMOH超越了所有的SOTA方法。

在Places205中mAP、 Precision指标的性能表现如上。

在Places205数据集中，mAP指标下，HMOH胜过了所有的SOTA方法。在Precision@H2指标下，HMOH输给了MIHash。

在MNIST中mAP、 Precision指标的性能表现如上。

在MNIST数据集中，mAP指标下，HMOH胜过了所有的SOTA方法，在Precision@H2指标下，HMOH输给了MIHash。

在NUS-WIDE 中mAP、 Precision@H2指标的性能表现如上。

在NUS-WIDE数据集中，两个指标的表现中，HMOH胜过了所有的SOTA方法。