如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
哈希函数学习的两个步骤：
根据哈希函数性质，可做如下分类：
问题定义：
选取矩阵
X
X
⊤
\mathbf{X X}^\top
XX⊤ 最大的
m
m
m 个特征向量，组成投影矩阵
W
∈
R
d
×
m
\mathbf{W}\in \mathbb{R}^{d\times m}
W∈Rd×m，并定义哈希函数为：
h
(
x
)
=
sgn
(
W
⊤
x
)
.
h(\mathbf{x})=\operatorname{sgn}\left(\mathbf{W}^\top \mathbf{x}\right).
h(x)=sgn(W⊤x).
min { y i } ∑ i j W i j ∥ y i − y j ∥ 2 s.t. y i ∈ { − 1 , 1 } k ∑ i y i = 0 1 n ∑ i y i y i ⊤ = I \begin{aligned} \mathop{\min}\limits_{\left\{\mathbf{y}_i\right\}} \ \ \ & \sum_{i j} W_{i j}\left\|\mathbf{y}_i-\mathbf{y}_j\right\|^2 \\ \text { s.t.} \ \ \ & \mathbf{y}_i \in\{-1,1\}^k \\ &\sum_i \mathbf{y}_i=0 \\ &\frac{1}{n} \sum_i \mathbf{y}_i \mathbf{y}_i^\top=\mathbf{I} \end{aligned} {yi}min s.t. ij∑Wij∥yi−yj∥2yi∈{−1,1}ki∑yi=0n1i∑yiyi⊤=I
其中 W i j W_{ij} Wij 为 x i \mathbf{x}_i xi 和 x j \mathbf{x}_j xj 的相似度，第二个约束意味着所有数据映射后，每一位上 1 1 1 和 − 1 -1 −1 的数量相同，第三个约束意味着不同位之间没有关联。上述优化问题为整数规划，难以求解，可将 y i ∈ { − 1 , 1 } k \mathbf{y}_i \in\{-1,1\}^k yi∈{−1,1}k 约束取消，对问题进行放松，并将求得的 { y i } \{\mathbf{y}_i\} {yi} 每一位通过 sgn \operatorname{sgn} sgn 函数映射，得到最终的二进制编码。
对
X
\mathbf{X}
X 使用 k-means 聚类，得到
{
u
j
∈
R
d
}
j
=
1
m
\{\mathbf{u}_j\in \mathbb{R}^d\}_{j=1}^m
{uj∈Rd}j=1m，重新定义矩阵
Z
∈
R
n
×
m
\mathbf{Z}\in \mathbb{R}^{n\times m}
Z∈Rn×m：
Z
i
j
=
{
exp
(
−
D
2
(
x
i
,
u
j
)
/
t
)
∑
j
′
∈
J
i
exp
(
−
D
2
(
x
i
,
u
j
′
)
/
t
)
,
∀
j
∈
J
i
0
,
otherwise
Z_{i j}=\left\{\begin{array}{l} \frac{\exp \left(-\mathcal{D}^2\left(\mathbf{x}_i, \mathbf{u}_j\right) / t\right)}{\sum_{j^{\prime} \in\mathcal{J}_i } \exp \left(-\mathcal{D}^2\left(\mathbf{x}_i, \mathbf{u}_{j^{\prime}}\right) / t\right)}, \forall j \in \mathcal{J}_i \\ 0, \text { otherwise } \end{array}\right.
Zij=⎩
⎨
⎧∑j′∈Jiexp(−D2(xi,uj′)/t)exp(−D2(xi,uj)/t),∀j∈Ji0, otherwise
其中
J
i
\mathcal{J}_i
Ji 为一个下标集合，对应
{
u
j
∈
R
d
}
j
=
1
m
\{\mathbf{u}_j\in \mathbb{R}^d\}_{j=1}^m
{uj∈Rd}j=1m 中
s
s
s 个离
x
i
\mathbf{x}_i
xi 最近的点的下标。定义哈希函数为：
h
(
x
)
=
sign
(
W
⊤
z
(
x
)
)
,
h(\mathbf{x})=\operatorname{sign}\left(W^\top z(\mathbf{x})\right),
h(x)=sign(W⊤z(x)),
其中 W = n Λ − 1 / 2 V Σ − 1 / 2 W=\sqrt{n} \Lambda^{-1 / 2} V \Sigma^{-1 / 2} W=n Λ−1/2VΣ−1/2， Λ = diag ( Z ⊤ 1 ) \Lambda=\operatorname{diag}\left(Z^\top\mathbf{1}\right) Λ=diag(Z⊤1)， V V V 和 Σ \Sigma Σ 由矩阵 Λ − 1 / 2 Z ⊤ Λ − 1 / 2 \Lambda^{-1 / 2} Z^\top \Lambda^{-1 / 2} Λ−1/2Z⊤Λ−1/2 的特征向量和特征值组成。该方法整体目标与 Spectral Hashing 一致，但通过引入 Anchor，使问题求解得到了加速，时间复杂度从 O ( n 3 ) O(n^3) O(n3) 降至为 O ( n m 2 ) O(nm^2) O(nm2)。具体细节可参照原论文。
问题定义：
常见算法如下所示，具体信息见参考资料，此处不再展开。
该部分属于有监督哈希一类，不过监督信息从标记变为了排序信息，例如三元组 ( x , x + , x − ) \left(x, x^{+}, x^{-}\right) (x,x+,x−)。该部分涉及的常见算法如下：
