1.9k 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$ ← Previous Post Next Post→ Table of Contents 1. Kernel Learning问题2. Kernel Learning和ITML的联系3. ITML算法的核化4. 在线算法