深度度量学习(四)正则学习、MMC算法

Jul 9, 2019


原创:岐山凤鸣,转载请注明本站域名

觉得不错不妨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平方正则的方法。

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

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

其中是一个已经给定的矩阵,而D是一个对角矩阵(也即是主要的优化目标),总体优化目标为:

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

其中

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

Kwok and Tsang方法

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

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

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

那么同理对不相似约束,当然这里为了更好约束距离,让他们至少间隔一些距离,所以还是引入参数

整体优化目标为:

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

那么其中的即为:

$ 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平方正则,这里要看到里面有参数,那么在考虑正则的时候,也要考虑这个,怎么解决,我们可以对A写成如下形式(博客貌似显示不出来矩阵,这是一个2*2矩阵,后面两项放到下面就好了):

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

这个形式的,可以称为【加强马氏矩阵】(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结合一起搞正则,当然这里也可以,不过这个的作者没这么肝,直接用的Frobenius平方正则。

MMC算法,Mahalanobis Metric Learning for Clustering

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

首先前提条件就是假设我们已知一系列集合使得为相似对集合,为不相似对集合,优化目标为:

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

就这个作者,他没用通用的平方,反而加了个根号,为啥? 主要是因为带平方的解在这个问题里是不重要的rank-one solution。他们同时讨论了当A是对角矩阵或者为任意半正定矩阵的情况。在任意情况下,他们弄了个梯度下降去解决,找那个矩阵的曲面的极值点,那么这个优化的正则采用的是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框架,即,假如A为I,则即为原始空间度量下的欧几里得距离,而采用A则是施加线性变换后的度量距离,我们希望能够学到一个更好的A,让映射后的距离比较满足我们的想法。

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

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

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