Minkowski距离、Mahalanobis距离、Wasserstein距离

本文总结Minkowski距离、Mahalanobis距离、Wasserstein距离。

相关关系、距离度量的定义

这里需要明确相关关系和函数关系的区别：前者是多个变量间不能确定函数关系，但在趋势上存在明显的相关性，而函数关系有明确的表达式建立自变量和因变量的关系。

对于点$a,b,z$，距离度量$D$定义：

1. $D(a,b) \ge 0$ 当$a=b$取等式（非负性和正定性）
2. $D(a,b) = D(b,a)$（对称a性）
3. $D(a,b) \le D(a,z) + D(b,z)$​ （三角不等式）
4. $D(a, a) = 0$（同一性）

像KL散度（又称为相对熵）不满足第二点对称性，

$$\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{-\infty }^{\infty }p(x)\log \left({\frac {p(x)}{q(x)}}\right)\,dx \\ D_{\text{KL}}(P\parallel Q) \ne D_{\text{KL}}(Q\parallel P)$$

因此它不是严格的距离度量。

假设有向量分别为A、B，那么有cos相似，

$$\cos(\theta ) =\frac{\mathbf {A} \cdot \mathbf {B}}{ \|\mathbf {A} \|\|\mathbf {B} \|} =\frac {\sum \limits _{i=1}^{n}A_{i}B_{i}}{\sqrt {\sum \limits _{i=1}^{n}A_{i}^{2}}{\sqrt {\sum \limits _{i=1}^{n}B_{i}^{2}}}}$$

取值区间为$[-1, 1]$。

Minkowski（闵可夫斯基）距离

假设两个随机向量分别为$X=(x_{1},x_{2},\ldots ,x_{n})\in {\mathbb {R}}^{n}$和$Y=(y_{1},y_{2},\ldots ,y_{n})\in {\mathbb {R}}^{n}$，那么他们之间的闵可夫斯基距离为，

$$d\left(X,Y\right)=\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{\frac {1}{p}}$$

其中$p \ge 1$。

当$p=1$时，$d\left(X,Y\right)$为Manhattan距离。

当$p=2$时，$d\left(X,Y\right)$为Euclidean距离。

当$p=\infty$​时，$d\left(X,Y\right) = \max_i |x_i - y_i|$​为Chebyshev距离。

当$p=0$时，$d\left(X,Y\right)$为Hamming距离，即$ |x_i - y_i|$的非零个数。

对于第三点，这里给出一个证明。为简化符号，令$x_i = |x_i - y_i|$​，假设$x_j$最大，于是

$$\begin{align} \lim_{p \to + \infty} \left(\sum _{i=1}^{n}|x_{i}|^{p}\right)^{\frac {1}{p}} &= x_j \lim_{p \to + \infty} \left(\sum _{i=1}^{n}|\frac{x_{i}}{x_{j}}|^{p}\right)^{\frac {1}{p}} \newline &= x_j \newline &= L_{\infty}(x_1, x_2, \dots, x_n) \end{align}$$

以下是Tensorflow实现的Minkowski，

import tensorflow as tf

def manhattan(x, y):
    # L1
    return tf.reduce_sum(tf.abs(x - y))

def euclidean(x, y):
    # L2
    return tf.sqrt(tf.reduce_sum((x - y) ** 2))

def minkowski(x, y, p):
    # Lp
    return tf.reduce_sum(tf.abs(x - y) ** p) ** (1 / p)

def chebyshev(x, y):
    # L-infinity
    return tf.reduce_max(tf.abs(x - y))

def hamming(x, y):
    # 0
    return tf.reduce_sum(~tf.equal(x, y)) / len(x)

度量两个向量的距离或相似度、向量到一个数据集的距离我们会使用欧几里得距离。对于第一种情况，直接使用欧几里得定义即可；对于第二种情况，需要计算数据集的“中心”，这个中心可能值均值中心，也可能是中位数中心，取决于场景。然而，这种直接基于欧几里得的方法存在问题，每个维度有着不同的语义，或者说不同的尺度，在计算距离时显然尺度大的对距离的“贡献”更大。然而，并没有告诉我们，尺度大的维度应该有更大的贡献。于是，一个自然的想法是消除各个维度的尺度大小，让每个维度”平等起来“，这就是Mahalanobis（马哈拉诺比斯）距离的基本思想。

Mahalanobis（马哈拉诺比斯）距离

Mahalanobis（马哈拉诺比斯）距离，简称为马氏距离，它考虑各个特征之间的相关性，并通过数学处理使其和特征的尺度无关，计算方法如下，

$$D_{M}(\boldsymbol{x})=\sqrt{(\boldsymbol{x}-\boldsymbol{\mu})^{T} S^{-1}(\boldsymbol{x}-\boldsymbol{\mu})}$$

其中$S$为样本的协方差矩阵，考虑特例情况，当各个特征互相独立且方差为1时，矩阵$S$为单位矩阵。协方差矩阵的逆不一定存在，但在计算上无法避免，此时，使用矩阵的伪逆（pseudo-inverse）。

考虑随机向量

$${\displaystyle \mathbf {X} ={\begin{bmatrix}X_{1}\\X_{2}\\\vdots \\X_{n}\end{bmatrix}}}$$

其协方差矩阵

$$\Sigma = \begin{bmatrix} \mathrm{E}[(X_1 - \mu_1)(X_1 - \mu_1)] & \mathrm{E}[(X_1 - \mu_1)(X_2 - \mu_2)] & \cdots & \mathrm{E}[(X_1 - \mu_1)(X_n - \mu_n)] \\ \\ \mathrm{E}[(X_2 - \mu_2)(X_1 - \mu_1)] & \mathrm{E}[(X_2 - \mu_2)(X_2 - \mu_2)] & \cdots & \mathrm{E}[(X_2 - \mu_2)(X_n - \mu_n)] \\ \\ \vdots & \vdots & \ddots & \vdots \\ \\ \mathrm{E}[(X_n - \mu_n)(X_1 - \mu_1)] & \mathrm{E}[(X_n - \mu_n)(X_2 - \mu_2)] & \cdots & \mathrm{E}[(X_n - \mu_n)(X_n - \mu_n)] \end{bmatrix}$$

首先注意到，矩阵的 SVD 分解是一定存在

$$\mathbf{C}=\mathbf{U D V}^{T}$$

在完成分解后，奇异矩阵一定可逆，那么，我们只需要计算奇异矩阵的逆即可，进而构成 pseudo-inverse 矩阵，该矩阵作为矩阵逆的替代。奇异矩阵为，

$$\mathbf{D}=\left[\begin{array}{cc}{\mathbf{D}_{r}} & {0} \\ {0} & {0}\end{array}\right]$$

可以构造这样的逆，

$$\mathbf{D}^{\dagger}=\left[\begin{array}{cc}{\mathbf{D}_{r}^{-1}} & {0} \\ {0} & {0}\end{array}\right]$$

由于$\boldsymbol{U}, \boldsymbol{V}$是正交矩阵，于是求得矩阵$\boldsymbol{C}$的逆，称为伪逆，

$$\mathbf{C}^{\dagger}=\mathbf{V} \mathbf{D}^{\dagger} \mathbf{U}^{T}$$

用以上方法可以求得协方差矩阵$\Sigma$的伪逆，当它的逆不存在时，然后就可以代入到Mahalanobis距离度量中。这样计算得到的马氏距离也可以作为相似性度量，马氏距离越大相似性越小，反之则相似性越大。在机器学习中，马氏距离可以结合 KNN 使用，提升分类性能。

Python实现如下，

import numpy as np
import scipy.spatial as spatial

def mahalanobis_distance(obs, X, center="zero"):
    # mahalanobis distance of obs to X
    # wiki:
    # https://en.wikipedia.org/wiki/Mahalanobis_distance

    # 计算协方差矩阵
    cov = np.cov(X.T)

    # 计算数据集的中心
    if center == "zero":
        center = np.zeros(cov.shape[1])
    else:
        center = np.mean(X, axis=0)

    # 矩阵的逆不一定存在，这里使用矩阵的伪逆
    icov = np.linalg.pinv(cov)
    # 计算 obs 到 center 的 Mahalanobis distance
    d = spatial.distance.mahalanobis(obs, center, icov)
    return d

Wasserstein距离

两个概率密度之间的距离称为测度（metric），Wasserstein距离是常用的测度。

Wasserstein距离有一个有趣且形象的名称，推土机距离（Earth Mover’s Distance），是用来度量两个分布之间的距离指标。维基百科中的讲述比较苦涩，这里使用更直观的方式。

假设有两个离散概率分布，分别为，

$$p = \left(\begin{array}{l} x_{1}, x_{2}, \cdots, x_{n} \\ p_{1}, p_{2}, \cdots, p_{n} \end{array}\right),\; q = \left(\begin{array}{l} y_{1}, y_{2}, \cdots, y_{m} \\ q_{1}, q_{2}, \cdots, q_{m} \end{array}\right)$$

注意到到它们是满足归一性的，即

$$\sum_{i=1}^{n}p_i = 1,\quad \sum_{i=1}^{m}q_i = 1$$

Wasserstein距离度量通过把分布$p$​变换为$q$​花费最小的成本。为把$p$​变换为$q$​，需要考虑把$p_{i}$​分配给$q_{j}$​，数量为$c_{i,j} \ge 0$​并花费成本$d_{i,j}$​。这里所谓的把$p_{i}$​分配给$q_{j}$​，可以直观地理解，第$i$​处有数量$p_i$​的东西（如泥沙、土壤，即上述离散分布中的$x_i$），把它移动到第$j$处，使得其数量为$p_j$，这个搬移的量就是$c_{i,j} \ge 0$，其对应的成本为$d_{i,j}$​。

注意到，从$i$​处移动到$j=1,\dots,n$​处的总量为$p_{i}$​，因此有，

$$\begin{equation} \sum_j c_{i,j}=p_i \end{equation}$$

同理，

$$\sum_i c_{i,j}=q_j$$

这里花费成本$d_{i,j}$构成一个矩阵，需要额外定义。

因此有最优化问题，

$$\begin{align} \min_{c_{ij}} \sum_{i,j} c_{i,j}d_{i,j} \\ \text{s.t.} \; \sum_j c_{i,j}=p_i \\ \sum_i c_{i,j}=q_j \\ c_{i,j} \ge 0 \end{align}$$

其实就是一个经典的线性规划问题。

该问题可以Python实现求解，具体如下，

import numpy as np
from scipy import optimize

def wasserstein_distance(p, q, C):
    """Wasserstein距离计算方法，
    p.shape=(m,)
    q.shape=(n,)
    C.shape=(m,n), d_{ij}
    p q满足归一性概率化
    """
    p = np.array(p)
    q = np.array(q)
    A_eq = []
    for i in range(len(p)):
        A = np.zeros_like(C)
        A[i,:] = 1.0
        A_eq.append(A.reshape((-1,)))
    for i in range(len(q)):
        A = np.zeros_like(C)
        A[:,i] = 1.0
        A_eq.append(A.reshape((-1,)))
    A_eq = np.array(A_eq)
    b_eq = np.concatenate([p, q], axis=0)
    C = np.array(C).reshape((-1,))
    return optimize.linprog(
        c=C,
        A_eq=A_eq[:-1],
        b_eq=b_eq[:-1],
        method="interior-point",
        options={"cholesky":False, "sym_pos":True}
    ).fun

这个实现只依赖numpy和scipy。在运用到句子上时，可以取$p_i = \frac{1}{n}$​​​以及$q_i = \frac{1}{m}$​​​​，即认为词的均匀分布在各个位置上。

而$x_i$对应位置$i$的词向量，$d_{ij}$使用两个词向量的差异来计算，即

$$d_{ij} = \|\boldsymbol{u}_i - \boldsymbol{v}_j \|$$

实现的Python代码如下，

def word_mover_similar(x, y):
    """Word Mover's Distance计算方法, 
    x.shape=(m,d)
    y.shape=(n,d)
    """
    x = np.array(x)
    y = np.array(y)
    p = np.ones(x.shape[0]) / x.shape[0]
    q = np.ones(y.shape[0]) / y.shape[0]
    C = np.sqrt(np.mean(np.square(x[:,None] - y[None,:]), axis=2))
    return wasserstein_distance(p, q, C)

总结

本文简单讲述距离度量的定义、Minkowski距离、Mahalanobis距离、Wasserstein距离这三种距离。

参考

[1] https://en.wikipedia.org/wiki/Wasserstein_metric

[2] https://en.wikipedia.org/wiki/Mahalanobis_distance

转载请包括本文地址：https://allenwind.github.io/blog/6561
更多文章请参考：https://allenwind.github.io/blog/archives/