Post Tuned Hashing,PTH

[ACM 2018] Post Tuned Hashing_A New Approach to Indexing High-dimensional Data [paper] [code]

Zhendong Mao, Quan Wang, Yongdong Zhang, Bin Wang.

Overcome

  • 大多数哈希方法都有二值化过程,二值化加速了检索过程,但同时难以避免得也破环了原始数据的相邻结构。

Contribute

  • 提出了新的哈希方法——PTH,包含三个阶段:projection,binarization和post-tuning。其中post-tuning阶段可以在利用任意哈希方法得到哈希二值编码之后,再独立得进行post-tune处理以重建被二值阶段破坏的数据相邻结构,以改善算法表现。
  • 为post-tuning算法提出了一个out-of-sample扩展,使得PTH算法可以处理训练数据集之外的数据,如测试集。
  • PTH在五个数据集的测试表现超过的所有的state-of-the-art算法。

Algorithm

POST TUNED HASHING

之前的哈希方法大都有projection和binarization两个阶段,这些two-stage的方法大都会造成neighborhood error。我们可以定义neighborhood error如下:
$$
L = ||S-V||_{F}^{2}
$$
其中, S, V分别是原始数据X和二值编码B的相似矩阵,其中$ij-th$个元素表明对应第i个数据和第j个数据是否相似。

Post Tuned Hashing(PTH)的post-tuning过程:$R:{-1,1}^m \to {-1, 1}^m$,可以改善二值编码,使得neighborhood error最小化:
$$
PTH(X) = R(H(X))
$$
在post-tuning过程中,H(X)可以利用任何哈希方法产生。因此,PTH可以非常简单得应用于广泛的哈希方法中以改进其二值编码表现。

Overall Framework

矩阵S表示原始数据X间的相似信息,其具体定义如下:

V表示原始数据X对应的二值编码B间的相似信息,其具体定义如下:
$$
V_{ij} = (b_i · b_j )/ m
$$
此时,将neighbood error改写为:
$$
L = ||S-\frac{1}{m} B^TB||_{F}^2
$$

定义Upost-tuning matrix,且Z=H(X),此时,目标函数为:

矩阵U中的每一个元素代表Z中对应位置的元素是否需要更新以得到更小的neighborhood error。PTH方法最终得到的改善后的哈希编码为:B=U ○ Z。

Optimization Algorithm

Observation:目标函数中的所有二次项都是常数(取值只为1/-1),因此最小化目标函数等同于最小化所有线性项。

令$\gamma=1/m$,则目标函数变为:

上述目标函数关于矩阵第p行的表示为:

令z_p为矩阵Z第p行的行向量,Q = Z*Z^T。则上述目标函数变为:

令矩阵$C=Q○(S - \gamma O)$,则目标函数的线性项关于矩阵U第p行第q列的元素$u_{ij}$的结果为:

因此,对于元素$u_{ij}$,最小化Q(U)即最小化上式,且其可以被认为是元素$u_{ij}$的权重。当这个权重小于0时,我们将$u_{ij}$设为1,大于0时则设为-1。

Updating strategy:在每次更新时,当且仅当$u_{ij}$的权重绝对值大于一个阈值$\eta$时对其进行更新,在实验中,阈值$\eta$被设置为所有权重的均值。mean absolute value of projecttion results。为了增加计算效率,可以使用同一个矩阵C对U的每一行进行更新,所得到的表现和elementi-by-element的结果类似。

Pruning strategy:在算法中仅对projection results(未二值化处理)中值接近0或则小于一个阈值$\delta$的元素进行更新,因为只有这些元素才有较大的概率而二值化到错误的编码。阈值$\delta$被设置为mean absolute value of projection results

在论文的代码中,并没有利用到$\eta$。只要$(\sum_ku_p^kC_q^k)u_{ij}<0$,就对$u_{ij}$取反。符合最小化目标函数的思想。

Out-of-Sample Post-Tuning

PTH在post-tuning阶段可以改善数据X的二值编码,使其更好得保留原有数据的相邻结构。但是我们还需要对不在数据集X中的数据( 查询图片)进行测试。我们称X为skeleton points。完整的post-tuning阶段包含两个步骤:

  1. 对skeleton points进行post-tune处理;
  2. 对out-of-samples进行post-tune进行处理使得其二值编码能够和X保持一致。

假设q为out-of-sample,$z^q$为q的原始二值编码,则q的post-tuning过程为:

其中$S^q$为q和X的相邻信息矩阵,B为X的post-tuned编码。post-tuning过程和哈希函数的学习过程时独立的,因此skeleton points X可以和哈希函数所用的训练集不同,且后续实验表明,一小部分的数据集X就可以使得post-tuning过程达到很好的效果。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×