Latent Factor Hashing

本文就论文 Supervised Hashing with Latent Factor Models 和论文 Discrete Latent Factor Model for Cross-Modal Hashing 对 Latent Factor Hashing (LFH) 做简单总结。

泰勒公式

泰勒公式是将一个在 出具有 阶导数的函数 利用关于 次多项式来逼近函数的方法。

若函数 在包含 的某个闭区间 上具有 $n$ 阶导数,且在开区间 上具有 阶导数,则对闭区间 上任意一点 $x$,成立下式:

其中, 表示 的 $n$ 阶导数,等号后的多项式称为函数 处的泰勒展开式,剩余的 是泰勒公式的余项,是 的高阶无穷小。

LFH

方法

论文 Supervised Hashing with Latent Factor Models 中提出了 LFH 方法,LFH 方法通过优化最大后验概率完成相似关系的提取。令 表示两个二进制码 点积的一半,即:

因为汉明距离与向量內积之间存在以下的关系:

其中 为二值码长度。

则给定 ,相似矩阵 的似然表示为:

并且

其中 是 logistic 函数,

一些方法直接通过优化最大似然来保留提取相似度,LFH则定义了 的先验概率 ,则 的后验概率为:

使用最大后验概率进行相似度的保留,为了进行后续的优化,首先将二值矩阵 的约束放宽成实值矩阵 重定义为:

相似的, 被替换为 。文中使用正态分布模拟 的先验分布,即:

则目标函数如下:

优化

直接优化整个矩阵 ,时间消耗太大,可以固定其他行,每次优化 的一行 ,我们可以找到 的一个下界,然后最大化那个下界。这里就需要用到泰勒展开式,计算 的一阶梯度向量,以及Hessian矩阵如下:

至于这里为什么要区分,是为了之后使用不同的学习策略时的统一表达,具体可以参见原论文。

定义

可以证明(三角不等式):

其中 表示 是半正定矩阵。

然后我们就可以使用 的二阶泰勒展开作为 的下界 ,即:

表示某个时间步 的值,为了使 最大,只需要令 的梯度为0,即可得到:

具体计算过程可参见附录,由此即可更新所有的行。

在本文中,作者提出了两种不同的优化策略(LFH-Full 和 LFH-Stochastic),两种方式分别使用全部的相似矩阵 和部分的相似矩阵(稀疏的相似矩阵 和对齐的相似矩阵 ),如下图所示:

三种方式更新的复杂度依次降低,在使用第三种对齐的部分相似矩阵时,由于保证了 的对称性, 可以简化为:

此时更新的复杂度为 ,因为 的值相对较小,所以在大规模数据集上,LFH的扩展性很强。

当得到最优的 时,通过符号函数得到二值矩阵

Out-of-Sample

定义矩阵 ,将查询 映射到实值向量 ,即

然后使用符号函数得到二值向量

使用线性回归来学习矩阵 的值, 损失定义为:

最优的 可由下式计算得到:

DLFH

论文 Discrete Latent Factor Model for Cross-Modal Hashing 提出了 DLFH 方法,与 LFH 相比主要有三点不同:

  1. DLFH 进行的是跨模态哈希,而 LFH 则是单模态哈希
  2. DLFH 是一种离散优化方法,直接学到二进制哈希码,而 LFH 则将二值放松到了实值
  3. 第三点是更新方式的不同,LFH 一次更新一个数据点的哈希码,而 DLFH 一次更新所有数据点的某一位哈希码,具体的更新方式在下文中介绍

方法

对于两个模态 ,以及他们之间的相似矩阵 ,我们的目标是学到两个模态的二值哈希码 ,其中 是哈希码长度。定义 ,其中 是超参。

需要注意的是,DLFH中的 和 LFH 中的 定义不同

定义 ,基于 ,我们定义相似度矩阵 的似然函数如下:

其中 定义为:

则对数似然为:

DLFH 的目标就是最大化对数似然,即优化下面的目标函数:

虽然其他一些方法也通过优化最大似然来提取跨模态相似度,但是这些方法都进行了放松处理,而 DLFH 则是直接进行的离散优化。

优化

因为有两个需要优化的矩阵,DLFH 采用交替优化的方式,每次固定一个矩阵,更新另一个矩阵。

固定 , 优化

DLFH 每次优化 的一列,即 ,为了达到这个目的,需要建立 的一个下界,然后最大化这个下界。首先计算目标函数 对于 的梯度以及 Hessian 矩阵如下:

其中 表示对角矩阵。

表示第 个迭代时 的值, 表示 的梯度,,定义 如下:

由于 ,所以有 ,故 的下界,然后,通过最大化 来学习 ,即:

要使上式最大,只需要 每个元素同号即可,即 ,使用这个结果可以得到:

固定 ,优化

同理可得:

其中,

本文也提出了随机优化的策略(DLFH-Stochastic)用来降低更新复杂度,每个迭代通过随机选择相似矩阵的 行(列)来计算 ,则更新 如下:

其中, 分别是采样的 列和行。更新的复杂度会降低为 ,其中

Out-of-Sample

文中使用线性和非线性两种分类器进行样本外扩展,对于线性分类器,最小化下面的平方损失:

其中 正则项的超参,可以得到:,哈希函数为:

对于非线性分类器,使用 kernel logistic regression (KLR) 进行分类,学习 个分类器,每个分类器对应一个bit,用来预测 的二值码,对于第 个bit,最小化下面的 KLR 损失:

其中 是正则项的超参, 的 RBF 核特征表示,哈希函数为:

参考文献

Zhang, Peichao, et al. “Supervised hashing with latent factor models.” Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. ACM, 2014.

Jiang, Qing-Yuan, and Wu-Jun Li. “Discrete Latent Factor Model for Cross-Modal Hashing.” IEEE Transactions on Image Processing (2019).

https://en.wikipedia.org/wiki/Matrix_calculus

https://en.wikipedia.org/wiki/Hessian_matrix

附录

梯度的计算。对式:

的梯度为0,即

因为 是对称矩阵,所以上式可以写为:

则有:

此时不赞何时赞!