Supervised Discrete Hashing

Supervised Discrete Hashing(SDH)论文阅读笔记。

1536309561149

CVPR 2015

本文提出了一个有监督的哈希学习框架,旨在快速且高效地对二进制哈希码直接进行优化。为了利用监督标签信息,本文设计了一个分类框架进行哈希学习,即希望学到的哈希码能够获得更高的分类精度。哈希码相当于数据的特征,将源数据通过非线性转化到二值空间,然后在此空间下进行分类。

为了实现上述的框架,本文将二值特征学习和线性分类器联合起来进行优化。为了能更好的获得数据的非线性结构特征,哈希函数的学习在核空间下进行。整个的优化过程以迭代的方式进行,分为三个相互关联的子问题

为了解决最复杂的子问题,即二值优化问题,本文提出了 discrete cyclic coordinate descent(DCC) 算法来一位一位(bit by bit)的生成哈希码。通过选择合适的分类损失函数,DCC 算法可以返回最优哈希码的闭合解,使得优化过程变得更加高效。

SDH的关键技术在于直接解决没有经过任何松弛操作离散优化问题。首先引入了一个辅助变量,将目标函数转化成可以以正则化项的形式解决的问题;然后使用DCC算法解决二值优化问题。

SDH

  • $n$ 个样本

  • 学习二值表示

学到的二值表示能够保留数据的语义关联,其中第 $i$ 列 $\mathbf{b}_i$ 是数据 $\mathbf{x}_i$ 的二值表示,长度为 $L$。

为了利用标签信息,将二进制码的学习问题转化成线性分类问题,希望学到的二值表示使得分类结果达到最优。

定义如下的多分类公式:

其中 $\mathbf{w}_k \in \mathbb{R}^{L\times 1},k=1,\cdots,C$ 是类别 $k$ 的分类向量,$\mathbf{y}\in \mathbb{R}^{C \times 1}$ 是标签向量。

目标函数如下:

  • $\mathcal{L}(\cdot)$ 损失函数
  • $\lambda$ 正则项系数
  • 实际标签矩阵

在上式中,可以将 $\mathbf{b}_i$ 替换来消除约束,但是这样做使得优化问题变得更加复杂。一些方法通过先学习 $F(\mathbf{x})$ 的方法,来学习 $\mathbf{b}_i$ 的实值表达,然后通过阈值函数转换为二值表达,这样做可以使得原问题更容易得到解决,但是最后的结果并不是最优解。

为了得到更高质量的二进制表达,将上述问题转化如下:

上式中最后一项用来建模二进制码 $\mathbf{b}_i$ 与其实值表达 $F(\mathbf{x}_i)$ 之间的误差,$\nu$ 是惩罚因子。理论上,当 $\nu$ 足够大时,上式即接近原优化问题。

容易看出,上式是非凸的并且难以求解,但是当制定合适的损失函数时,上式是可以迭代的求解的。

$\mathbf{b}_i$ 的非线性映射

本文使用一个简单但是有效的非线性变换,如下所示:

其中 $\phi(\mathbf{x})$ 是一个 $m$ 维的列向量,由 RBF 核函数映射得到:

其中 是从训练样本中随机挑选的 $m$ 个样本,$\sigma$ 是核的宽度, 映射到低维空间,

F-Step

将(3) 中 $\mathbf{B}$ 固定,$\mathbf{P}$ 可以由下式计算:

这一步与损失函数无关。

使用 $l_2$ 损失

(3) 是写为:

G-Step

对于上式,当$\mathbf{B}$ 固定时,能够很容易求得 $\mathbf{W}$ 的闭合解:

B-Step

当除 $\mathbf{B}$ 以外的其他参数都固定时,由于 $\mathbf{B}$ 的离散性,求得 $\mathbf{B}$ 的值很难。将原问题写为:

上式的求解问题是 NP 难度的,但是当 $\mathbf{B}$ 中的其他列固定时,$\mathbf{B}$ 中的每一列都有一个封闭解。将上式重写为:

等价于:

其中 $\mathbf{Q} = \mathbf{WY} + \nu F(\mathbf{X})$。

本文使用 DCC 方法学习 $\mathbf{B}$,即一位一位地学习 $\mathbf{B}$ 。令 $\mathbf{z}^T$ 表示 $\mathbf{B}$ 的第 $l$ ($l=1,\cdots,L$)列,$\mathbf{B}’$ 表示矩阵 $\mathbf{B}$ 除去 $\mathbf{z}$ 的子矩阵,其他符号($\mathbf{q},\mathbf{Q}’$ 和 $\mathbf{v}, \mathbf{W}’$)的定义与之类似,则有:

其中

同样的,有

将上面的式子结合起来,得到

这个问题有最优解:

使用hinge损失

损失函数为:

其中 $c_i$ 是 $\mathbf{x}_i$ 的标签。

G-Step

当 $\mathbf{B}$ 固定时,$\mathbf{W}$ 可由多分类 SVM 解决方法求得。

B-Step

当除 $\mathbf{B}$ 以外的其他参数固定时,原问题写为:

上式中的约束可以写为:

带入原问题中,得:

这里 $\delta = 1/\nu$。

上式可以转化为:

该问题的最优解为:

SDH 算法如下所示:

1536473767360

实验

详见论文。

此时不赞何时赞!