谈谈Metric Learning (IV): ITML进阶

Author: Huan Li Date : Jun 10, 2015 Updated On : May 31, 2018
1,944 words in total, 8 minutes required.

1. Kernel Learning问题

对于Kernel Learning这个问题,我们可以这样认为:

给定一个kernel $ K$, 我们在一些点集上同样有constraints,这个时候,为了使得这些点之间的pairwise distance服从constraints的情况,我们需要优化这个kernel,这就是kernel learning问题的基本定义。

相信你可以看到,这个定义已经和我们讨论的ITML有一定的相似性,我们先从Kulis2006的这篇 low-rank kernel learning的文章来讲起:

对于low-rank kernel learning的输入,是一个specified kernel $ K_0$, 我们的目标是使得我们需要的kernel $ K$ 无限接近 $ K_0$ ,而这种“接近”自然是由我们的LogDet divergence来衡量的,好了,那么对于这个问题。

首先,我们知道给定的$ A_0$是如下形式的, $ K_0 = X^{T}A_0X$,它是一个$ n \times n$的方阵,优化问题如下:

Equation.1

$\min\limits_K D_{ld}(K, K_0)$
$\text{s.t.}$
$K_{ii} + K_{jj} - 2K_{ij} \leq v, (i,j) \in S$
$K_{ii} + K_{jj} - 2K_{ij} \geq l, (i,j) \in D$
$K \succeq 0$

2. Kernel Learning和ITML的联系

现在已经看出一点端倪了,实际上这两个问题的关联在于如何证明$ K$和$ A$存在着“强关联”。回想下我们在上一篇中介绍的关于$A$和$A_0$的LogDet优化:

Equation.2

$\min\limits_{A \succeq 0} D_{ld}(A, A_0)$
$\text{s.t.}$
$tr(A(x_i - x_j)(x_i - x_j)^{T}) \leq v, (i,j) \in S$
$tr(A(x_i - x_j)(x_i - x_j)^{T}) \geq l, (i,j) \in D$

为了证明它们之间的关联,我们给出一个引理及其证明,如下:

Lemma.1

给定$K = X^{T}AX$,当且仅当$K$是Equation.1的可行解的情况下,$A$是Equation.2的可行解。

证明: $K_{ii} + K_{jj} - 2K_{ij}$可写成$(e_i - e_j)^{T}K(e_i - e_j) = (x_i - x_j)^{T}A(x_i - x_j)$。因此,对于similar constraint,$K_{ii} + K_{jj} - 2K_{ij} \leq v$等价于$tr(A(x_i - x_j)(x_i-x_j)^{T}) \leq v$。同理,适用于dissimilar constraint。得证。

由上,我们可以给出一个定理及其证明:

Theorem.1

给定Equation.1的最优解$K^{\star}$及Equation.2的最优解$A^{\star}$,必有$K^{\star} = X^{T}A^{\star}X$。

证明: 对于Equation.1的Bregman projection update可写为:

$A_{t+1} = A_{t} + \beta A_{t}(x_i - x_j)(x_i - x_j)^{T}A_{t}$

对于Equation.2的Bregman projection update 则可写为:

$K_{t+1} = K_{t} + \beta K_{t}(e_i - e_j)(e_i - e_j)^{T}K_{t}$

优化的算法可以得出,两者当中使用的$\beta$是一致的,接下来可以归纳证明,在每一次迭代的过程中,都满足关系$K_t = X^{T}A_{t}X$(给定初始条件:$K_0 = X^{T}A_{0}X$)

假设$ K_t = X^{T}A_{t}X$则:

$K_{t+1}$
$= K_{t} + \beta K_{t}(e_i - e_j)(e_i - e_j)^{T}K_{t}$
$= X^{T}A_{t}X + \beta X^{T}A_{t}X(e_i - e_j)(e_i - e_j)^{T}X^{T}A_{t}X$
$= X^{T}A_{t}X + \beta X^{T}A_{t}(x_i - x_j)(x_i - x_j)^{T}A_{t}X$
$= X^{T}(A_{t} + A_{t}(x_i - x_j)(x_i - x_j)^{T}A_{t})X$
$= X^{T}A_{t+1}X$

如果$K$能收敛到$K^{\star}$,那么$A$也能收敛到$A^{\star}$。则两个问题等价,定理得证。

那么,通过这么多的推论和证明,我们终于可以认为ITML算法实际上与low-rank kernel learning的问题是一致的,因此,我们可以将ITML算法的输入由一个初始矩阵$A_0$置换成$K_0$,将限制条件更改为$K_{ii} + K_{jj} - 2K_{ij}$,而相应的输出也变成了一个$K^{\star}$。

3. ITML算法的核化

我们在上一篇提及ITML的思想是希望优化的$A$在满足constraints的情况下尽可能地逼近$A_0$,而$A_0$的选择就体现出了你想要求解一个怎样的问题。

假设,我希望这个度量是满足欧氏距离特性的,那么就应该选择单位矩阵$I$来作为初始化的$A_0$。由此,假设$A_0 = I$,则$K_0 = X^{T}A_0X = X^{T}X$,实际上就是一个Gram矩阵

这里我们定义一个kernel function来替代上述这种直观的表达,即

$k(x,y) = \phi(x)^{T}\phi(y)$

其中$\phi()$理解为对于变量的非线性转换函数。转换到核空间后,我们是否还能通过估量来学习到一个合适的metric呢?

实际上,我们的metric定义变成了:

$d_A(\phi(x), \phi(y)) = (\phi(x) - \phi(y))^{T}A(\phi(x) - \phi(y))$
$=\phi(x)^{T}A\phi(x) - 2\phi(x)^{T}A\phi(y) + \phi(y)^{T}A\phi(y)$

随后,我们定义一个新的核公式:

$\widetilde{k}(x,y) = \phi(x)^{T}A\phi(y)$

虽然我们没有办法直接去计算$A$(可以理解为hilbert space下的一个operator),但是我们依然可以计算$\widetilde{k}(x,y)$,由于$A_0 = I$,我们可以考虑递归地展开学习到的matrix $A$:

$A = I + \sum\limits_{i,j}\sigma_{ij}\phi(x_i)\phi(x_j)^{T}$

这是核化之后的$A$,它依然希望能够尽量逼近$I$,这里我们引入了一些系数coefficient $\sigma_{ij}$。这样,就可以写出新的核公式的表达形式:

$\widetilde{k}(x,y) = \phi(x)^{T}A\phi(y) = \phi(x)^{T}(I + \sum\limits_{i,j}\sigma_{ij}\phi(x_i)\phi(x_j)^{T})\phi(y)$
$= \phi(x)^{T}\phi(y) + \sum\limits_{i,j}\sigma_{ij}\phi(x)^{T}\phi(x_i)\phi(x_j)^{T}\phi(y)$
$= k(x,y) + \sum\limits_{i,j}\sigma_{ij}k(x,x_i)k(x_i,y)$

到这里,我们看到,新的核公式是老的核公式和一系列系数的组合,通过优化Equation.2当中的问题,我们可以得到一系列系数$\sigma_{ij} $来估量新的核函数$\widetilde{k}()$。

4. 在线算法

在一般的metric learning甚至于优化问题当中,通常程序是接收一堆数据并进行最小化的工作。我们接下介绍一个online算法,能够在线增量地对metric进行优化和学习。

在online算法里,假设算法接收一个实例$(x_t, y_t, d_t)$,其中$t$是一个time step,并且使用当前的model $A_t$预测一个distance $\widetilde{d_{A_t}} = d_{A_t}(x_t,y_t)$。

那么这个prediction的loss可以表达为$l_t(A_t) = (d_t - \widetilde{d_t})^2$。其中,$d_t$我们称之为$x_t$和$y_t$之间的”true/target” distance。

那么通过一次prediction,算法将$A_t$修改为$A_{t+1}$,并且用新的model进行接下来的预测,我们于是得到predicitons的total loss 为$\sum_{tl_t}(A_t)$。

对于这样一个total loss,由于输入数据和他们的target distance是没有关联的,我们找不到它的bound,一个可行的方案就是将其和离线阶段中的最佳可能(best possible)方案进行对比。

对于最佳可能方案,可以这样得到,假设给出一个T-trail sequence $S = \{(x_1,y_1,d_1),\ldots,(x_T,y_T,d_T)\}$, best possible方案满足:

$A^{\star} = \arg\min\limits_{A \succeq 0} \sum\limits_{t = 1}^{T}l_t(A)$

理解起来非常简单易懂,就是对于离线给定的测试序列,total loss最小化的。

这样,对于online算法而言,就是将得到的total loss和最佳可能方案进行对比。

一个解决在线学习的通用方法是在每一个time step解决下列正规化优化问题:

$\min\limits_{A \succeq 0} f(A) = \overbrace{D(A,A_t)}^{Regularization~Term} + \eta_t \cdot \overbrace{l_t(A)}^{Loss~Term}$

这个公式中:

  • $\eta_t$是$t$时刻的learning rate,$ D$是用来测量新计算的matrix $A$和当前的$A_t$的散度。
  • Regulartization Term: 最小化两者散度是为了使得两者尽量靠近而保证最小化趋于平稳。
  • Loss Term: 是为了使得计算的model $A$和特定时刻的$A_t$保持一致。使得学习到的distance尽量与target distance保持一致。
  • 而learning rate则跟具体问题相关,需要进行调节。

这个问题中,我们同样用LogDet来表示散度$D$,于是可以得到:

$A_{t+1} = \arg\min\limits_{A} D_{ld}(A,A_t) + \eta_t (d_t - \widetilde{d_{t}})^2$