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

觉得不错不妨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相同的时候，那么就会变成方差$Cov(X, X) = E[(X - {\mu}_x)^2] = \frac{1}{n-1} \sum_{i=1}^{n}{(x_i - \bar{x})^2}$，方差的小学也学过，其含义就是和样本均值的一个波动性，也就是样本中偏离均值的一个度量程度。

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

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

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

$ \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}$

其中对$\vec{x}, \vec{y}$均是进行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}}} $

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

$0<r<=1, or Cov(X,Y) > 0$，正相关
$-1<=r<0, or Cov(X,Y) < 0$，负相关
$r=0, or Cov(X,Y)=0$，不相关，但不代表独立

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

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

Mahalanobis距离

直接上公式，对向量$x_i, x_j$，其Mahalanobis距离为：

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

其中${\sum}^{-1}$指的是协方差矩阵，作为二次型矩阵。

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

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

很简单，为了消除量纲。

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

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

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

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

回到Mahalanobis距离，它很像whitening数据，whitening一个向量w，其均值和方差为$\mu, {\sum}$，我们得到的白化后的向量为$\tilde{w} = {\sum}^{1/2}(w-\mu)$

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

那么对两个白化后的向量$\tilde{w_i}, \tilde{w_j}$，计算欧几里得距离：

$ 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吧！

协方差 和 协方差矩阵

Mahalanobis距离

Euclidean距离

协方差和协方差矩阵