原创：岐山凤鸣，转载请注明本站域名

觉得不错不妨star/follow一下我的Github

参考：

Kulis, Brian. (2012). Metric Learning: A Survey. Foundations and Trends in Machine Learning. 5. 10.1561/2200000019. 

这一篇终于会介绍正式的metric learning的算法了，不过在此之前得对上一篇收个尾，即正则有哪些，为什么要提出这些。

之后介绍基于这些原理的算法，在十几年前都是顶会算法，所以参考意义很强。MMC和LMNN在现在的一些顶会算法里也有应用。

注1：这篇综述是2012年的，视野当然会受到限制，但根据基础的理论介绍的算法模型均在当年有着很深远的影响，在追逐前沿的同时，旧模型的思路和原理依然值得探寻。

注2：这系列博文并不是翻译这篇综述，有很多我个人的私货…并不代表正确，但具有参考价值。

Frobenius范数正则，Frobenius Norm Regularization

公式如下：

$ r(A) = |A|_{F}^2$

这是最常用的一种正则项，对一个矩阵A来说，其Frobenius范数为：

$ r(A) = \sqrt{\sum_{i=1}^{m}{\sum_{j=1}^{n}^2}}} $

很简单，Frobenius范数可以理解成L2范数的矩阵版本（L2范数是向量版本），当然我们这里的r(A)是取平方后的，可以理解成squared l2-norm，这个常常在SVM和岭回归里用到，我还记得在吴恩达的SVM课里SVM的公式后面赫然的带了一个所有参数的平方和。Frobenius当然也继承了很多squared l2-norm的性质。

下面介绍几个采用这个范数的例子。

Schultz和Joachims方法

Schultz和Joachims在2004年提出过一种相对距离约束，结合Frobenius平方正则的方法。

首先，既然是采用距离约束，就免不了前几篇提过的 $X^TAX$结构，而这两个人对A进行了如下的定义：

$A = \tilde{A}D\tilde{A}^T$

其中$\tilde{A}$是一个已经给定的矩阵，而D是一个对角矩阵(也即是主要的优化目标)，总体优化目标为：

$\min_D |A|^2F + \lambda {\sum{i=1}^{m}{c_i(X^T A X)}}$

其中$c_i(X^T A X) = [1 + d_A(x_{i_1}, x_{i_2}) - d_A(x_{i_1}, x_{i_3})]_{+}, (i_1, i_2, i_3) \in R, A = \tilde{A}D\tilde{A}^T, D diagonal$

其中假如$\tilde{A} = I$，优化问题便成为了【对角矩阵型马氏距离约束的带Frobenius平方正则的度量学习问题】，看上去拗口，但其实也就是对之前二次型矩阵变成半正定的对角矩阵，并且带上Frobenius平方正则，在现代眼光来看就是L2正则，这样的话就变成了一个很类似于回归的问题。

Kwok and Tsang方法

Kwok和Tsang的思路与上述非常的不同，正则方法一样，但是使用的约束是相似与不相似约束，并且对矩阵A并没有采用对角的形式。

那么什么叫相似约束(similarity constraint)和不相似约束(dissimilarity constraint)？

假设我们考虑一个相似约束$d_A(x, y) \leq u$，说明这俩相似，注意这个距离是带A的情况，那么原始情况下(即二次型矩阵为I)应该是比这个距离大的，所以他们考虑$d_A(x, y) \leq d_I(x, y)$，这个就非常巧妙了。

那么同理对不相似约束$d_I(x, y) + \gamma \leq d_A(x, y)$，当然这里为了更好约束距离，让他们至少间隔一些距离，所以还是引入参数$\gamma$

整体优化目标为：

$min_{A \geq 0, \gamma \geq 0} |A|^2F + \sum{i}{c_i(X^TAX) - \lambda_g \gamma}$

那么其中的$c_i$即为：

$ c_i (X^T A X) = \lambda_s [d_A(x_i, y_i) - d_I(x_i, y_i)]_{+}, (x_i, y_i)\in S$

$ c_i (X^T A X) = \lambda_d [d_I(x_i, y_i) + \gamma - d_A(x_i, y_i)]_{+}, (x_i, y_i) \in D$

很奇妙对吧，我也感觉很奇妙，对比这两个人的方法和上面两个人的方法，会发现，上面两个人采用的主要是相对距离的约束，也就是我们俩的距离要比你们俩的距离大，而这两个人主要采用的是经过映射后的距离和之前的距离对比，我们相似的话，我们映射后自然距离更近，同理相离也一样。

那么正则方法依然是Frobenius平方正则，这里要看到里面有参数$\gamma$，那么在考虑正则的时候，也要考虑这个$\gamma$，怎么解决，我们可以对A写成如下形式（博客貌似显示不出来矩阵，这是一个2*2矩阵，后面两项放到下面就好了）：

$\bar{A} = \begin{bmatrix}A & 0\ 0^T & -\gamma \end{bmatrix}$

这个形式的$\bar{A}$，可以称为【加强马氏矩阵】(augmented Mahalanobis matrix)，这种情况下重新定义正则项即为：

$r(\bar{A}) = |A|_F^2 - \lambda_g \gamma$

具体的推导过程我这里就不用写了，其实这个结果很直观的。

POLA, Pseudo-Metric Online Learning Algorithm

这个其实就是一个loss函数，类似SVM的思想，引入 $y_i$，如果为1，那么说明一对向量应该相似，如果为-1，那么说明一对向量应该不相似，公式如下：

$c_i (X^T A X) = [1 + y_i (d_A(x_i, y_i) - \gamma)]_{+}$

在上面的Kwok and Tsang操作里将A结合$\gamma$一起搞正则，当然这里也可以，不过这个的作者没这么肝，直接用的Frobenius平方正则。

MMC算法，Mahalanobis Metric Learning for Clustering

之前的各种操作可以各位同学感觉没见过，非常的陌生，而到这里之后，介绍的算法一般都是实用性很强（在当时），且引领过一段潮流的算法，首先介绍的就是这个MMC，一个用上述我们讲过的基于Mahalanobis度量机制的搞聚类的算法。

首先前提条件就是假设我们已知一系列集合使得$(x_i, x_j) \in S$为相似对集合，$(x_i, x_j) \in D$为不相似对集合，优化目标为：

$\min_{A \geq 0} \sum_{(x_i, x_j) \in S}{d_A(x_i, x_j)}$

且 $\sum_{(x_i, x_j) \in D}{\sqrt{d_A(x_i, x_j) \geq 1}}$

就这个作者，他没用通用的平方，反而加了个根号，为啥？主要是因为带平方的解在这个问题里是不重要的rank-one solution。他们同时讨论了当A是对角矩阵或者为任意半正定矩阵的情况。在任意情况下，他们弄了个梯度下降去解决，找那个矩阵的曲面的极值点，那么这个优化的正则采用的是AC矩阵乘法结果的迹，即$tr(AC)$，其中C:

$C = \sum_{(x_i, x_j)\in S} {(x_i - x_j)(x_i - x_j)^T}$

这个方法类似于对K-means的加强，引入了距离度量的约束去做一个聚类，也算是别出心裁。

这个和我们之前讨论的正则框架不同，一个相近的是Bilenko提出的一个方法，也是采用Mahalanobis metric learning的框架去做的聚类，也是对K-means进行了约束与加强。

总结

在讨论度量学习的时候，对其框架是一定要掌握的，也就是Mahalanobis metric learning框架，即$d_A(X^T A X)$，假如A为I，则即为原始空间度量下的欧几里得距离，而采用A则是施加线性变换后的度量距离，我们希望能够学到一个更好的A，让映射后的距离比较满足我们的想法。

对于损失函数来说，我们考虑两种损失，一种是相对损失，对一个三元组，让其中相似的距离靠近，不相似的距离远离。另外一种便是对相似对来说，映射后的距离应该低于原始距离，非相似对来说，映射后的距离应该往往高于原始距离$\gamma$

对于正则来说，有很多的选择，有对迹进行正则，当然更多情况下采用Frobenius平方正则，这个也就是L2正则在矩阵上的扩展，有时候在具体的方法里需要改进，比如引进新的参数的时候。

所以虽然上面的公式多，但是其实还是很好理解的，下一篇主要讲LMNN，这个算法是现在也依然用的比较多的。