论文阅读：Post Tuned Hashing: A New Approach to Indexing High-dimensional Data

1. 方法介绍

Learning to hash是进行高维数据索引的有效方法，它的目标是：学习一个low-dimensional的、similarity-preserving的二进制编码表示，使该其可以代表原高维空间的数据。本文基于Unsupervised hashing method思想，通过探索数据内在特征与属性，来学习二进制码表示。

传统的无监督hashing基本都通过2阶段的范式来实现：

mapping：将高维原始数据投影到低维空间；
binarization：将投影向量二值化，变成一个“二进制”编码。

并且为了保证原有的neighborhood relationships，他们大都选择在投影阶段或者二值化阶段做出优化。

但是，论文指出，尽管他们努力地在某个阶段保证了邻域关系(例如在降维时保证了邻域关系)，但是二值化过程不可避免地造成了neighborhood error：即原数据中相邻的数据可能会产生不相似的二进制编码，而不相邻数据可能会产生相似编码。于是论文提出了一个全新的步骤，post-tuning stage，意图使用该方法在二值化后重建邻域关系，减小邻域损失。图1展示了加入新的步骤前后，邻域损失情况。

图1. Toy illustration of the superiority of post-tuning.

值得注意的是，该步骤独立于前两个步骤，因此可以广泛适配传统的2阶段方法。

2. 方法框架分析与推导

下面我们对该方法的理论做一定的阐述与推导：

首先，我们设数据集 $X \in R^{d \times n}$ 包含n个数据，每个数据的维度为d。为了完成无监督hashing的两个阶段，我们可以通过一个线性或非线性的函数 $P : R^{d} \to R^{m}$ 完成高维到低维的投影，再通过一个二值化函数 $s g n (\cdot)$ 将低维向量二值化：

\begin{matrix} (1) & Z = H (X) = s g n (P (X)) \end{matrix}

其中 $s g n : R^{m} \to {- 1, 1}^{m}$ ，其根据每个元素是否大于0进行二值划分。

由于论文指出上述2阶段方法会造成严重的neighborhood error，因此他们定义了该损失函数的表达式：

\begin{matrix} (2) & L = ‖ S - V ‖_{F}^{2} \end{matrix}

其中 $S \in R^{n \times n}$ 是原始数据的邻域关系矩阵，定义为

S_{i j} = {\begin{cases} \begin{aligned} 1 & if d (x_{i}, x_{j}) < ϵ \\ - 1 & otherwise \end{aligned} \end{cases}

$d (\cdot)$ 衡量了原始数据空间的欧氏距离。而 $V$ 是二值化空间的邻域关系矩阵，定义为

\begin{matrix} (3) & V_{i j} = (b_{i} \cdot b_{j}) / m \end{matrix}

其中，b_i 是数据 x_i 的二值化向量。可以看到V_ij 是值域为-1到1的离散变量。那么通过式(3)，损失函数可以改写为：

\begin{matrix} (4) & L = ‖ S - \frac{1}{m} B^{T} B ‖_{F}^{2} \end{matrix}

其中 $B \in {- 1, 1}^{m \times n}$ 是n个数据的二值化向量矩阵。

结合公式(1)和公式(4)，很容易得到在传统方法中， $B = H (x)$ 。现在，作者希望通过加入第3个步骤，即Post Tuned Hashing (PTH)，来实现二值化向量的重建。具体而言，论文将定义一个新的变换 $R : {- 1, 1}^{m} \to {- 1, 1}^{m}$ ，使得重建后的二值向量能够最小化损失：

\begin{matrix} (5) & P T H (X) = R (H (X)) \end{matrix}

对于这个新的变换，论文设计了一个二值(-1,1)的矩阵post-tuning matrix，表示为 $U \in R^{m \times n}$ ，通过学习这个矩阵来使损失最小化。这样，公式(4)可以进一步写为

\begin{matrix} (6) & min Q (U) = ‖ S - γ (U \circ Z)^{T} (U \circ Z) ‖_{F}^{2} \end{matrix}

为了清楚地推导论文的优化算法，这里对于步骤做了细化的分析：

\begin{matrix} (7) & \begin{aligned} U \circ Z & = [\begin{array}{c} u_{11} & u_{12} & \dots & u_{1 n} \\ u_{21} & u_{22} & \dots & u_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ u_{m 1} & u_{m 2} & \dots & u_{m n} \end{array}] \circ [\begin{array}{c} z_{11} & z_{12} & \dots & z_{1 n} \\ z_{21} & z_{22} & \dots & z_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ z_{m 1} & z_{m 2} & \dots & z_{m n} \end{array}] \\ = [\begin{array}{c} u_{11} z_{11} & u_{12} z_{12} & \dots & u_{1 n} z_{1 n} \\ u_{21} z_{21} & u_{22} z_{22} & \dots & u_{2 n} z_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ u_{m 1} z_{m 1} & u_{m 2} z_{m 2} & \dots & u_{m n} z_{m n} \end{array}] \end{aligned} \end{matrix}

\begin{matrix} (8) & \begin{aligned} S - γ (U \circ Z)^{T} (U \circ Z) \\ = S - γ [\begin{array}{c} u_{11} z_{11} & u_{21} z_{21} & \dots & u_{m 1} z_{m 1} \\ u_{12} z_{12} & u_{22} z_{22} & \dots & u_{m 2} z_{m 2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ u_{1 n} z_{1 n} & u_{2 n} z_{2 n} & \dots & u_{m n} z_{m n} \end{array}] [\begin{array}{c} u_{11} z_{11} & u_{12} z_{12} & \dots & u_{1 n} z_{1 n} \\ u_{21} z_{21} & u_{22} z_{22} & \dots & u_{2 n} z_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ u_{m 1} z_{m 1} & u_{m 2} z_{m 2} & \dots & u_{m n} z_{m n} \end{array}] \\ = S - γ [\begin{array}{c} \sum_{k = 1}^{m} u_{k 1} z_{k 1} u_{k 1} z_{k 1} & \sum_{k = 1}^{m} u_{k 1} z_{k 1} u_{k 2} z_{k 2} & \dots & \sum_{k = 1}^{m} u_{k 1} z_{k 1} u_{k n} z_{k n} \\ \sum_{k = 1}^{m} u_{k 2} z_{k 2} u_{k 1} z_{k 1} & \sum_{k = 1}^{m} u_{k 2} z_{k 2} u_{k 2} z_{k 2} & \dots & \sum_{k = 1}^{m} u_{k 2} z_{k 2} u_{k n} z_{k n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \sum_{k = 1}^{m} u_{k n} z_{k n} u_{k 1} z_{k 1} & \sum_{k = 1}^{m} u_{k n} z_{k n} u_{k 2} z_{k 2} & \dots & \sum_{k = 1}^{m} u_{k n} z_{k n} u_{k n} z_{k n} \end{array}] \end{aligned} \end{matrix}

\begin{matrix} (9) & \Rightarrow {[(U \circ Z)^{T} (U \circ Z)]}_{i j} = \sum_{k = 1}^{m} u_{k i} z_{k i} u_{k j} z_{k j} \end{matrix}

根据上面的详细推导，我们的目标函数可以写为

\begin{matrix} (10) & \begin{aligned} min Q (U) = ‖ S - γ (U \circ Z)^{T} (U \circ Z) ‖_{F}^{2} \\ \Leftrightarrow & min_{U} \sum_{i j} {[S_{i j} - γ \sum_{k = 1}^{m} u_{k i} z_{k i} u_{k j} z_{k j}]}^{2} \end{aligned} \end{matrix}

我们也可以统计U的第p行的部分：

\begin{matrix} (11) & \begin{aligned} \sum_{i j} {[S_{i j} - γ \sum_{k = 1}^{m} u_{k i} z_{k i} u_{k j} z_{k j}]}^{2} \\ = & \sum_{i j} {[S_{i j} - γ (u_{p i} z_{p i} u_{p j} z_{p j} + \sum_{k = 1, k \neq p}^{m} u_{k i} z_{k i} u_{k j} z_{k j})]}^{2} \\ =_{x = u_{p i} z_{p i} u_{p j} z_{p j}}^{set A = \sum_{k = 1, k \neq p}^{m} u_{k i} z_{k i} u_{k j} z_{k j}} & \sum_{i j} {[S_{i j} - γ (x + A)]}^{2} \\ = & \sum_{i j} S_{i j}^{2} - 2 γ S_{i j} (x + A) + γ^{2} (x + A)^{2} \\ \overset{delete without x}{=} & \sum_{i j} - 2 γ S_{i j} x + γ^{2} x^{2} + 2 γ^{2} A \cdot x \end{aligned} \end{matrix}

所以一次项，即文章中的linear terms，可以表示为

\begin{matrix} (12) & \begin{aligned} \sum_{i j} - 2 γ S_{i j} x + 2 γ^{2} A \cdot x \\ = & - 2 \sum_{i j} u_{p i} z_{p i} u_{p j} z_{p j} [γ S_{i j} - γ^{2} (\sum_{k = 1, k \neq p}^{m} u_{k i} z_{k i} u_{k j} z_{k j})] \end{aligned} \end{matrix}

论文设 $Z$ 的第p行的数据为 $z$ _p，其转置(即column向量)为 $\overset{―}{z}$ _p，设 $Q = {\overset{―}{z}}_{p} {\overset{―}{z}}_{p}^{T}$ ，设 $(U \circ Z)_{∖ p}$ 是将公式(1)的第p行删除的新矩阵，设 $O = {[(U \circ Z)_{∖ p}]}^{T} [(U \circ Z)_{∖ p}]$ ，我们可以轻易地将公式(5)改写为

\begin{matrix} (13) & - 2 γ \sum_{i j} u_{p i} Q_{i j} (S_{i j} - γ O_{i j}) u_{p j} \end{matrix}

值得指出， $Q_{i j} = z_{p i} z_{p j} = Q_{j i}, O_{i j} = \sum_{k = 1, k \neq p}^{m} u_{k i} z_{k i} u_{k j} z_{k j} = O_{j i}, S_{i j} = S_{j i}$ (详见论文公式(4))，那么如果我们设 $C = Q \circ (S - γ O)$ ，那么 $C$ 就是对称矩阵。因此公式6可以进一步化简：

\begin{matrix} (14) & - 2 γ \sum_{i j} u_{p i} c_{i j} u_{p j} \end{matrix}

其中，每一个涉及 $u_{p q}$ 的量均可以表示为：

\begin{matrix} (15) & \begin{aligned} - 2 γ \sum_{i = q, j} u_{p q} c_{q j} u_{p j} - 2 γ \sum_{i, j = q} u_{p i} c_{i q} u_{p q} & = - 4 γ \sum_{k} u_{p k} c_{q k} u_{p q} \\ = - 4 γ \sum_{k = 1, k \neq q}^{n} u_{p k} c_{q k} u_{p q} + 二 次 项 \end{aligned} \end{matrix}

对于每一个元素 $u_{p q}$ ，最小化损失函数公式(6)即最小化公式(15)。我们可以将 $u_{p q}$ 前面的系数当成是权重，那么为了最小化损失，当权重为负时，我们希望 $u_{p q} = 1$ ，权重为正时反之。

更新与优化策略

论文提供了一种更新策略：

update the current entry if its coefficient is larger than a fixed threshold $η$ .

这个策略可以按照矩阵 $U$ 内的元素顺序进行依次更新，减小了算法复杂度。并且，在一行元素更新时，矩阵 $C$ 并不需要更新，这是因为 $C$ 受到 $U$ 所有元素的影响，对一行数据的改变不敏感。

论文提供了一种剪枝策略：

Only tune the elements whose projection results (value before binarization) are close to 0, or smaller than a threshold $δ$ .

即，我们只调整那些投影后值与0接近的元素(因为0是二值化的一个阈值)，因为这些元素更有可能被二值化为不正确的值。这有效减少了post-tuning的复杂度，并且缓解了过拟合。

结合这两种策略，最终的优化算法如下图所示：

图2. Post-tuning Algorithm

Out-of-Sample Post-Tuning

由于是无监督学习方法，故方法必须兼容新的数据 $q \notin X$ 。与K近邻的思想类似，新来的数据 $q$ 理应与原来的数据 $X$ 产生联系。因此，我们称原来的数据为skeleton points。这样，完整的post-tuning应该包含以下2个任务：

post-tuning skeleton points $X$ ；
post-tuning out-of-sample $q$ .

与公式(6)类似的，我们建立如下损失：

\begin{matrix} (16) & \begin{aligned} min R (u^{q}) & = ‖ S^{q} - \frac{1}{m} (u^{q} \circ z^{q})^{T} B ‖_{F}^{2} \\ s.t. & u^{q} \in {- 1, 1}^{m} \end{aligned} \end{matrix}

其中:

$S^{q} \in R^{1 \times n}$ ： $q$ 和 $X$ 的邻域关系矩阵；
$u^{q} \in R^{1 \times m}$ ：即 $q$ 的post-tuning matrix；
$z^{q} \in R^{1 \times m}$ ：即 $q$ 经过二值化后的向量；
$B = (U \circ Z) \in R^{m \times n}$ ： $X$ 经过post-tuning的新二值化向量。

总之上式衡量了hashing前后 $q$ 和 $X$ 的邻域关系。论文也提到，由于post-tuning完全独立于前面2个步骤，因此这里的skeleton points( $X$ )在实践中并不是全部训练集，而是选择少部分数据点以提高效率。数据点数量的选择和最终方法效果的关系可从下图得出