深度度量学习(二)协方差、Mahalanobis距离与Euclidean距离

Jun 24, 2019


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

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

参考:

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

这一篇主要说明两种距离,马氏距离(Mahalanobis Distance)和欧几里得距离(Euclidean Distance)。

以及度量学习相关的符号表示。

其中马氏距离基于协方差矩阵,所以对协方差和协方差矩阵的理解和相关计算的掌握是非常必要的。

并且本博文增加相关参考和原创的代码来进一步描述。

因为编译问题,中间欧氏距离推导马氏距离的公式显示不出来了,感兴趣同学可以手推一下。

协方差 和 协方差矩阵

回顾基础的数学课是因为除了运算和会去分析,还需要理解其几何含义和代数含义,这样才能更方便在深层特征空间中去理解特征代数。

先从大家都耳熟能详会算能算的公式出发,设X和Y为两个随机变量,则其的协方差为:

$ Cov(X, Y) = E[(X-{\mu}_x) (Y-{\mu}_y)] $

$ Cov(X, Y) = \frac{1}{n-1} \sum_{i=1}^{n}{(x_i - \bar{x})(y_i - \bar{y})} $

直接理解来看,是两个随机变量与其均值差的积的均值。

当X与Y相同的时候,那么就会变成方差,方差的小学也学过,其含义就是和样本均值的一个波动性,也就是样本中偏离均值的一个度量程度。

对一系列n个随机变量来说,其中任意两个随机变量的协方差,形成的矩阵即为协方差矩阵。

很简单的定义,计算也很简单,大二的时候便会学,那么接下来要理解的是其在度量学习中的意义。

我们从概率统计回到线性空间,在之前定义过内积的线性空间中,我们考虑过引入内积后可以定义正交,即向量垂直的概念,同时,定义内积计算也可以定义出角度。考虑在线性空间中对内积进行角度的计算:

$ \vec{a} \cdot \vec{b} = |\vec{a}| |\vec{b}| \cos{\theta} $

推算出两个向量余弦角度为:

$ \cos{\theta} = \frac{A \cdot B}{|A||B|} = \frac{\sum_{i=1}^{n}{A_i*B_i}}{ \sqrt{ \sum_{i=1}^{n}{(A_i)^2} } * \sqrt{ \sum_{i=1}^{n}{(B_i)^2} }}$

可以看到分子上是向量内积,再结合协方差的公式,将随机变量X和Y表示为向量,然后【进行零均值化后】,则可以发现:

$ Cov(X, Y) = \frac{1}{n-1} \sum_{i=1}^{n}{(x_i - \bar{x})(y_i - \bar{y})} = \frac{\vec{x} \cdot \vec{y}}{n-1}$

其中对均是进行0均值化的向量,对原始的随机变量,哪怕它们正交,但并不意味着协方差为0,所以对向量要根据自己的均值需要一个相对的变换,得到的向量均值要为0,这种情况下协方差才可以作为一种内积的表现。为了消去向量数值的影响,所以一般从内积除去向量长度即为余弦距离,而对于随机变量得到的向量,其角度便是耳熟能详的相关系数。

$ r = \frac{Cov(X, Y)}{\sqrt{Var(X)} * \sqrt{Var(Y)}} = \frac{\sum_{i=1}^{n}{(X_i - \bar{X})(Y_i - \bar{Y})}}{\sqrt{\sum_{i=1}^{n}{(X_i - \bar{X})^2}} * \sqrt{\sum_{i=1}^{n}{(Y_i - \bar{Y})^2}}} $

有一些很有用的性质,很多人拿去水数模比赛。

  • ,正相关
  • ,负相关
  • ,不相关,但不代表独立

说这么多其实就是把协方差矩阵和度量空间联系一下,对各种随机独立变量来说,一组和一组之间如何消除量纲去比较其中的相关性,就是余弦距离和相关系数的作用,而协方差矩阵则更具体的表明了向量两两之间的相关性。

这个并不是说要会用这些工具去水比赛或者水一些东西,这个在之后距离运算以及和概率的理解中是会遇到很多的,很有用,理解其几何意义和代数意义是必要的。

Mahalanobis距离

直接上公式,对向量,其Mahalanobis距离为:

$ d_{mahalanobis}(x_i, x_j) = \sqrt{(x_i - x_j)^T {\sum}^{-1} (x_i - x_j)} $

其中指的是协方差矩阵,作为二次型矩阵。

很明显公式里表示的是关于两个向量的一个二次型的根号,二次型的矩阵为数据的协方差矩阵的逆,那么为什么要这样?

再回顾一下二次型,二次型矩阵来说,其整体的二次型计算是线性计算,二次型矩阵表示向量运动也即没改变线性空间的结构,为旋转、拉伸和投影。那么也就是协方差矩阵作为其拉伸的依据,为什么?

很简单,为了消除量纲。

考虑一个例子,UCL machine learning repository下关于酒(Wine)的数据,数据包含13个属性,假如我们直接通过这些属性来计算两两酒之间的欧几里得距离,作为向量的相似度的度量,其实得到的效果是非常差的。

九个属性的均值在[0, 10]之间,三个属性均值在[10, 100]之间,一个属性的均值为747,所以计算其距离几乎全部都是被均值较大的属性所决定。对于一些需要距离计算的机器学习算法,如K-Means,效果会极差。

为了消除这种情况,我们需要考虑各个属性之间的一个相对关系。有同学会采用标准化对每列数据,或者whiten数据,实际上whitening后的数据来算欧几里得距离已经很接近Mahalanobis距离。

当然这种无监督的缩放,它的效用程度有时候是不够的,有的时候一列属性相比其他列是更重要的。在带监督的训练里,一列属性的权重会随着学习而变化,那么这种情况更需要一种能够适配带监督学习的数据无量钢化。度量学习的一个目标是根据监督的信息,来学习数据的变换,从而得到一个想要的距离关系,而对于线性的变换,我们采用上述的二次型的方式来对数据进行放缩旋转等操作,而Mahalanobis采用协方差矩阵的逆作为二次型矩阵,是其中一种比较广泛使用的方式。

回到Mahalanobis距离,它很像whitening数据,whitening一个向量w,其均值和方差为,我们得到的白化后的向量为

其解释为在原本向量减去其均值后,做一个标准差的逆的线性变换。

那么对两个白化后的向量,计算欧几里得距离:

$ d_{euclidean}(\tilde{w_i}, \tilde{w_j})$

$ = \sqrt{(\tilde{w_i} - \tilde{w_j})^T(\tilde{w_i} - \tilde{w_j})} $

继续推导即为:

$ d_{euclidean}(\tilde{w_i}, \tilde{w_j}) = \sqrt{(w_i - w_j)^T(w_i - w_j)} $

$ d_{euclidean}(\tilde{w_i}, \tilde{w_j}) = d_{mahalanobis}(w_i, w_j) $

这个结果挺神奇的,对白化后向量求欧几里得距离直接便是对原本向量求马氏距离,使用马氏距离对上述的酒数据集处理,可以比较有效的去掉因为数值导致找不到向量间相关度的问题。

在度量学习中,我们一般对马氏距离进行更多的推广,依然采用马氏距离的那种形式:

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

推广后也即将协方差矩阵的逆作为一种一般的矩阵形式,还是要注意,二次型矩阵的作用是旋转、伸缩和投影,这里依然是线性变换,没有破坏空间结构也没有映射到其他的空间,我们期望能够学习到一个更好的矩阵A,让我们得到的向量间的距离更符合我们的期望。

当A为半正定矩阵的时候,可以进一步进行:

$ A = G^T G$

$ d_A(\vec{x}, \vec{y}) = {|G\vec{x} - G\vec{y}|_2}^2$

这种也可以称为广义的马氏距离,它是作为线性度量学习的一个非常重要的基石。

Euclidean距离

欧几里得距离的表现形式很简单,当然这里也不做更加数学化和复杂的解释,主要结合Scikit-Learn的代码进行一个实现。

很多时候我们都需要计算pairwise-distance,在我的课题里,这方面相关的代码已经写了很多了,很多小伙伴觉得欧式距离很简单呀,平方差的和不就搞定了,而在TensorFlow等符号化表示里,他不会直接的让你进行平方差的和的表示,而是一定要采用它的底层数学工具来进行公式的计算,所以这部分代码实现的基本功是很重要的。

而对很多情况我们求的pairwise-distances输入并不是两个向量,而是两个包含很多向量的矩阵,最终输出的距离也不是一个数字,而是一个两两的距离矩阵,其i行j列表示X的第i列向量和Y的第j列向量的欧几里得距离。

对【矩阵】x和y,公式表达:

$ dist(x, y) = sqrt(x \cdot x - 2 * x \cdot y + y \cdot y) $

注意,上述二元运算不是矩阵乘法,且x和y必定其元素内部的长度一致,否则不在同一欧几里得空间,无法计算距离。而为了定义其中二元运算,所以需要对矩阵乘法扩展。

扩展运算对于包含n个d维向量的矩阵x,求:

$ x \cdot x = vector_n(i) = \sum_{j=1}^{d}{x[i][j] * x[i][j]}$

采用numpy进行运算:

>>> x = [  [1,2,3], [4,5,6], [7,8,9] ]
>>> xx = np.einsum('ij,ij->i', x, x)
>>> xx
array([ 14,  77, 194])

定义传入参数:

def euclidean_distances(
    X,                     # 矩阵X
    Y=None,                # 矩阵Y, None时为X
    Y_norm_squared=None,   # 是否有提前计算好的Y的
    squared=False,         # 取得的距离是否平方
    X_norm_squared=None    # 是否有提前计算好的X的内积
)

除去其他参数的相关设置和配置,直接看核心操作:

XX = row_norms(X, squared=True)[:, np.newaxis]
YY = row_norms(Y, squared=True)[np.newaxis, :]

distances = -2 * safe_sparse_dot(X, Y.T, dense_output=True)
distances += XX
distances += YY

np.maximum(distances, 0, out=distances)

其中row_norms为上述的拓展操作,后续的np.newaxis为升维,方便后续的矩阵运算,safe_sparse_dot为sklearn定义的安全矩阵乘法,这个在普通情况下使用普通矩阵乘法也可以。

范例:

>>> x = np.array([  [1,2,3], [4,5,6], [7,8,9] ])
>>> y = np.array([  [3,4,5], [7,7,7], [9,9,9] ])
>>> xx = np.einsum('ij,ij->i', x, x)
>>> xx
array([ 14,  77, 194])
>>> yy = np.einsum('ij,ij->i', y, y)
>>> yy
array([ 50, 147, 243])
>>> 
>>> xy = np.dot(x, y.T)
>>> xy
array([[ 26,  42,  54],
       [ 62, 105, 135],
       [ 98, 168, 216]])

>>> xx + yy - 2*xy
>>> xx + yy - 2*xy
array([[  12,  140,  329],
       [ -60,   14,  167],
       [-132, -112,    5]])

在上述的案例中,xx + yy - 2*xy这里,其中xx为3*1的矩阵,yy为1*3的矩阵,xy为3*3的矩阵,这里python会根据需要自动的进行增添,所以相当于一个很简略的计算。

到此基本就是Euclidean距离符号化计算的一个流程。

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