深度度量学习(三)正则变换学习、相关例子介绍、爱因斯坦求和约定

Jul 2, 2019


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

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

参考:

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

这一篇主要说明一种带正则项的度量学习做法,主要包含正则项是什么,一般意义的度量学习的定义以及优化目标。

介绍完相关的基本概念后,以几个例子来理解一下。

最后对于带优化的矩阵相关运算的函数einsum,进行一个详细的学习。

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

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

正则变换学习,Regularized Transformation Learning

在之前的学习中,介绍了一些距离相关的说明,接下来我便可以通过欧几里得距离,来构成我们全局线性度量学习的一般模式。

我们根据这些距离的意义,以及算法,提出来一个通用的带正则的模型,回顾一下我们之前对度量学习(Metric Learning)的意义。

我们想通过一种带监督的方法,来学习一种新的距离去度量相似度。

原文即:

We aim to learn a new distance using supervision that is a function of the learned distance/similarity.

很简单的意思,用公式来回顾即:

$d_A(\vec{x}, \vec{y}) = (\vec{x} - \vec{y})^T A (\vec{x} - \vec{y})$

其中左边为原始向量,对两个原始向量的距离并不是直接求欧几里得或者其他的距离,而是引入参数矩阵A作为二次型矩阵,这个A是一个学习的参数,学习的基础是监督,原始的向量需要给出监督才能训练,之后我们对A进行内积映射得到:\(X^T G^T GX = X^T A X\),根据这个变换方便理解监督,对上述的新距离公式进行变换:

$d_A(\vec{x}, \vec{y}) = (\vec{x} - \vec{y})^T A (\vec{x} - \vec{y}) = (e_i - e_j)^T X^T A X (e_i - e_j)$

为了方便通过监督来学习,我们需要设置优化的目标,假设我们有一系列m个loss函数,记作:\(c_1, ..., c_m\),这些loss函数仅仅依赖于上述的内积矩阵\(X^T A X\),这些loss函数可以是很多形式,比如MSE等等。

除了loss函数部分,我们还需要一个正则项,记作\(r(A)\),这个正则项只和参数矩阵A相关,将两者结合到一起,即为总损失函数,也即我们的优化目标:

$L(A) = r(A) + \lambda \sum_{i=1}^{m}{c_i(X^T A X)} $

很明显这也就是一般的机器学习、深度学习的优化目标,损失函数+正则,那么度量学习有什么不同呢,其实没有什么不同,深度学习本来就是弄到最后度量层面上进行优化,包含了度量学习的部分。而度量学习本身都是侧重于对输入的大量的向量间的关系构建的问题,大量的向量有应该度量出相似的,有应该度量出不相似的,深度学习最后也是提取出向量然后进行非线性映射后优化,都是同理的。

而AlexNet也在12年提出,那时候深度学习还刚刚开始,我们理解这方面,很大程度也在理解深度学习,除了提取深度特征外,后面那部分究竟在干什么。

同理,本系列标题为深度度量学习,自然不会拘泥于表层的特征以及简单的度量学习。

说回来,我们的优化目标便是在参数矩阵A的定义域中,找到一个比较好的值让L(A)的值最小。这个A矩阵的定义域,一般是半正定矩阵的域,否则度量出负的东西没意义了。但很多情况下我们对A的定义域还有更严格的限制,比如非负对角矩阵的空间。所以在对A进行约束后,我们最终得到的优化目标的形式很像SVM、Lasso、Logistic回归的那种形式。

有的情况带约束的度量学习的优化目标可以定义如下,注意都是loss小于等于0的时候,才对正则项进行优化:

$\min_{A \in dom(A)} r(A)$

对\(c_i(X^T A X) \leq 0, 1 \leq i \leq m\)

有时候,我们还是把A拆成G,变成\(c_i(X^T G^T G X)\),然后通过对G优化来达到最终的优化结果。比如之后会说的NCA即为这种做法。

更多时候,对A优化一般会产生凸优化模型,而对G优化一般不会,凸优化的形式即为:

$min f_0(y)$ 对\(f_i(y) \leq 0, i=1,...,m\)且\(a_i^Ty=b_i, i=1,...,p\)

其中f均为凸函数,不等式可以进行推广。

相关例子介绍,Examples of Regularizers and Constraints

之前说了很多关于监督的,那么监督有什么形式?这里介绍一种比较常用的。

对于相似度判断的,我们定义一对向量\((i, j) \in S\),S集合表示里面所有的元素对里两个应该相似,同理定义D集合表示应该不相似的,定义\((i, j) \in D\),那么,我们往往可以这样来做:

$d_A(x_i, x_j) \leq u, (i, j) \in S$

$d_A(x_i, x_j) \leq l, (i, j) \in D$

然后我们选择的损失函数可以采用hinge loss:

$c(X^T A Y) = max(0, d_A(x_i, x_j) - u)^2, (i, j) \in S$

$c(X^T A Y) = max(0, l-d_A(x_i, x_j))^2, (i, j) \in D$

标准hinge loss的写法为 \([z]_{+} = max(0, z)\)

上述采用的是绝对距离,同样我们可以采用相对距离的方法,取三元组\((i, j, k) \in R\),其中i和j要更相似,i和k来自不同类,要远离,即要满足:

$d_A(x_i, x_j) < d_A(x_i, x_k)$

这个约束还不够,我们有时候还要加个约束,去约定究竟相似的应该和不相似的距离多远,所以加个margin:

$d_A(x_i, x_j) < d_A(x_i, x_k) - m$

很多情况,m都取1,因为深度学习里提取的特征往往都进行了归一化,这种形式是目前最流行的。深度学习里的Triplet Loss便是基于此,这方面详细的代码设计年末我会公开。在这种度量的效果的训练下,越多的样本,效果会越好。

关于正则的选取,一般上述情况可以选取下面三种:

$r(A) = \frac{1}{2}{|A|}_F^2 $

$r(A) = tr(AC) $

$r(A) = tr(A) - \log{det(A)}$

其中tr是矩阵的迹,det是行列式,C为类别标签矩阵。比如对中间那种叫做trace-norm,可以让度量学习的模型有更好的低秩解,在降维等问题中有很大作用,第一种叫Frobenius Norm Regularization,下一篇会讲到其用法以及这些正则的具体用法。

爱因斯坦求和约定,einsum

爱因斯坦求和约定全称Einstein Summation Convention,简称einsum。

在上一篇博文中,采用的扩展矩阵内积的计算便是使用的np.einsum,这个非常的厉害,能计算内积、外积、矩阵乘法、矩阵迹等等各种运算,并且能够很简单的进行优化,比自己手写以及采用其他的函数方便了很多倍。

下面直入主题,如果我们想计算一个求和式,一般会怎么样,例如:

$c_j = \sum_{i=1}{a_{ij}}$

这个是对矩阵a进行列求和,最后是j列,采用einsum写法即为:

>>> a = [ [2,3,1], [4,5,1]]
>>> c = np.einsum('ij->j', a)
>>> c
array([6, 8, 2])

所以很简单理解的,下面依次来介绍几种写法:

  • 行求和

$c_i = \sum_{j=1}{a_{ij}}$

>>> a = [ [2,3,1], [4,5,1]]
>>> c = np.einsum('ij->i', a)
>>> c
array([ 6, 10])
  • 转置

$a_{ji} = a_{ij}$

>>> a = [ [2,3,1], [4,5,1]]
>>> c = np.einsum('ij->ji', a)
>>> c
array([[2, 4],
       [3, 5],
       [1, 1]])
  • 矩阵全部元素求和

$c = \sum_{i=1}{\sum_{j=1}{a_{ij}}}$

>>> a = [ [2,3,1], [4,5,1]]
>>> c = np.einsum('ij->', a)
>>> c
16
  • Ax,矩阵乘向量

$c_i = \sum_{j}{A_{ij}x_j}$

>>> a
[[2, 3, 1], [4, 5, 1]]
>>> x = [4,5,6]
>>> c = np.einsum('ij,j->i', a, x)
>>> c
array([29, 47])
  • AX,矩阵相乘

$c_ij = \sum_{k=1}{A_{ik}X_{kj}}$

>>> a
[[2, 3, 1], [4, 5, 1]]
>>> x = [ [2,3,3,3], [3,4,4,4], [5,6,6,6] ]
>>> c = np.einsum('ik,kj->ij', a, x)
>>> c
array([[18, 24, 24, 24],
       [28, 38, 38, 38]])
  • xy,向量内积

$c = \sum_{i=1}{a_i b_i}$

>>> a
[[2, 3, 1], [4, 5, 1]]
>>> a = [2, 3, 1]
>>> b = [4, 5, 1]
>>> c = np.einsum('i,i->', a, b)
>>> c
24
  • 向量外积

$c_{ij} = a_i b_j$

>>> a = [2, 3, 1]
>>> b = [4, 5, 1]
>>> c = np.einsum('i,j->ij', a, b)
>>> c
array([[ 8, 10,  2],
       [12, 15,  3],
       [ 4,  5,  1]])
  • tr(A),矩阵的迹

$tr(A) = \sum_{i=1}{a_{ii}}$

>>> a = [[2, 3, 1], [4, 5, 1], [3, 4, 5] ]
>>> tra = np.einsum('ii->', a)
>>> tra
12
  • Frobenius正则

$Frobenius(A) = \sum_{i}{\sum_{j}{a_{ij}^2}}$

>>> a = [[2, 3, 1], [4, 5, 1], [3, 4, 5] ]
>>> frobenius = np.einsum('ij,ij->', a, a)
>>> frobenius
106

对于einsum函数,有一个参数optimize,设置True后可优化。

关于优化的测试我之后一并放上来,目前是不采取CUDA架构下最快的。

觉得有用的话就follow/star一下我的Github吧!