一文讲通机器学习的距离、相似度和分布散度

在机器学习中，我们经常需要回答一个基础问题：

两个对象到底有多相似，或者多不同？

这里的对象可以是两个特征向量，也可以是两张图片的embedding、两个句子的语义表示，甚至是两个概率分布

例如，在图像检索中，我们希望判断两张图片在特征空间是否接近；在聚类中，我们需要判断不同样本是否应当划分到同一个簇；在分类任务中，我们可能需要衡量模型预测分布和真实标签分布之间的差异。

为了描述这些关系，机器学习经常会用距离来度量。严格来说，距离、相似度、相异度和散度并不是完全相同的概念

距离

距离用于衡量两个对象的差异程度，值越小差异越小。具有

非负性、
同一性（两个对象完全相同，或具有可比性）、
对称性（x到y的距离的与y到x的距离）、
三角不等式（x到y的距离不超过x到y+y到z的距离）

满足者四个条件的距离，称为度量。

距离往往同时关注方向和长度，而相似度往往只关注方向

相似度

相似度通常值越大，对象差异越小。它衡量的是两个向量方向上的接近程度：方向一致是1，垂直是0，相反是-1

相异度

实际应用中通常将相似度转换为一个”越小越相似“的量，比如说 1-cos(x,y)。这个量通常不满足三角不等式，但经常用于损失函数的设计中，用于惩罚两个向量之间的偏差

散度

前面的距离和相似度通常用于比较两个向量，但我们经常需要比较两个概率分布。最经典的是KL散度，我们会在下面讲到，KL散度不满足对称性

基于绝对位移的向量距离

范数距离

这个再深度学习中比较常见。L1距离一般称为曼哈顿距离，L2距离就是下面的欧式距离。两者都属于Minkowski距离的特殊情况

一般形式为：

$d_p(x,y) = \left( \sum_{i=1}^{D} |x_i-y_i|^p \right)^{\frac{1}{p}}$

欧式距离

$d_{\text{Euc}}(x,y) = \sqrt{ (x_1-y_1)^2+ (x_2-y_2)^2 }$

假设

每一个维度的量纲相近
每一个维度的重要性完全相同
特征维度之间不存在相关性

解决方法

量纲问题

这个问题从直觉上来看就是说，如果有维度A、B，维度A波动本来就大，那么在A、B同样大小的偏差下，A不应该被过度惩罚。

量纲问题很好解决：标准化（不是平时的minmax归一化）。最常用的方法是除以每个维度的标准差$\sigma_i$，则标准化距离为：

$d(x,y) = \sqrt{ \sum_{i=1}^{D} \frac{(x_i-y_i)^2}{\sigma_i^2} }$

标准化欧式距离可以写成矩阵形式

$d^2(x,y) = (x-y)^\top W (x-y)$

其中：

$W= \begin{bmatrix} \frac{1}{\sigma_1^2} & 0 & \cdots & 0\\ 0 & \frac{1}{\sigma_2^2} & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \frac{1}{\sigma_D^2} \end{bmatrix}$

这也是加权欧式距离的表示，权重是方差的倒数

马氏距离

上述欧式距离只能解决量纲问题，但无法解决维度相关性问题。

什么是特征间的相关性？

比如说有两个特征：花瓣长度、花瓣宽度

现实中花瓣越长，通常也会越宽，存在正相关。如果我们统计下来，也许会获得这样一张图

xychart-beta
    title "花瓣长度与花瓣宽度分析"
    x-axis ["0.5", "1.0", "1.5", "2.0", "2.5", "3.0"]
    y-axis "花瓣长度 (cm)" 0 --> 8
    line [1.4, 3.0, 4.5, 5.5, 6.1, 7.3]

假设我们这里拟合 y = 2x+1 ，那么沿着这条直线，也就是主要趋势偏移是数据中最常见的变化。而垂直于这条直线偏移就显得十分异常

也就是说这里有两种移动方向，一个是平行于直线，一个是垂直于直线。这两种方向在移动长度相同的情况下，距离本应该是区分很大的，但是如果用欧式距离来算是相同的

协方差矩阵

上述问题说明，数据分布允许我们沿某些方向自由变化，但不允许我们沿另一些方向自由变化。协方差矩阵就用于描述数据沿哪些方向变化。

我们设随机向量为：

$X= \begin{bmatrix} X_1\\ X_2\\ \vdots\\ X_D \end{bmatrix}$

均值为：

$\mu = \mathbb E[X]$

协方差矩阵为：

$\Sigma = \mathbb E \left[ (X-\mu)(X-\mu)^\top \right]$

在二维情况下为：

$\Sigma = \begin{bmatrix} \operatorname{Var}(X_1) & \operatorname{Cov}(X_1,X_2) \\ \operatorname{Cov}(X_2,X_1) & \operatorname{Var}(X_2) \end{bmatrix}$

其中对角线元素表示自身波动程度，也就是该维度的方差。非对角线元素表示两个特征是否同步变化。当如果该元素大于0，也就是正相关；反之为负相关。元素的绝对值大小统一量纲后表示相关性程度，如果接近0说明它们在线性意义下缺少明显相关性。

马氏距离

$d_M(x,\mu) = \sqrt{ (x-\mu)^\top \Sigma^{-1} (x-\mu) }$

所以针对相关性问题，这里的加权矩阵式上述协方差矩阵的逆。这里和加权欧式距离有些相似，对角元素是意义的，关键在于非对角元素让他可以处理特征相关性。

为什么求逆，其实蛮好理解。对于对角元素来说，方差大的移动距离大惩罚应该小，所以应该求倒数。对于非对角元素，可以应用特征分解$\Sigma
=
Q\Lambda Q^\top$，这里不多做解释，整体来说可以说明马氏距离做了两件事

旋转坐标系：消除不同维度之间的相关性
按方差缩放：消除不同方向上的量纲

所以有一个很直观的看待方式：马氏距离是白化后的欧式距离。原始空间中数据可能是一个倾斜椭圆，白化以后变成近似圆形。然后在圆形中计算欧式距离

从距离到概率模型

高斯分布

马氏距离和高斯分布的关系

多元高斯分布的概率密度为

$p(x) = \frac{ 1 }{ (2\pi)^{D/2} |\Sigma|^{1/2} } e^ \left[ -\frac12 (x-\mu)^\top \Sigma^{-1} (x-\mu) \right]$

可见指数部分就是上述马氏距离的平方。也就是说，对于高斯分布，距离均值的马氏距离越小，概率密度越高。

所以马氏距离的等距离线和高斯分布的等密度线都是椭圆。

负对数似然

对高斯密度取负对数

$-\log p(x) = \frac12 d_M^2(x,\mu) + \frac12 \log |\Sigma| + \frac{D}{2}\log(2\pi)$

得到三项。其中第一项即马氏距离，衡量样本距离中心有多远，第二项用于描述高斯的分布，第三项是个常数

第二项很重要，因为假设两个高斯分布A和B，A非常集中（高瘦）而B矮胖，同一个样本到两者中心的马氏距离可能相似，但如果高斯B的覆盖范围极大，它在任何一个局部位置上的概率密度反而更低。

所以：当不同类别的协方差不同，只比较马氏距离还不够，严格来说应该比较完整的高斯似然

那么从欧氏距离到现在，我们可以建立三种模型

模型	协方差假设	几何形状	决策边界
最近质心	$\sigma^2I$	球形	线性
LDA	所有类别共享 $\Sigma$	相同形状椭球	线性
QDA	每类独立 $\Sigma_k$	不同形状椭球	二次

GMM

单个高斯只能描述一个大致单峰的簇，而局部特征可能存在多种模式，这些特征未必形成一个椭圆形簇，而可能形成多个子簇。但单个高斯很难拟合这种多峰结构。所以我们引入了GMM

高斯混合模型

GMM假设数据并非来自一个高斯分布，而是来自多个高斯分布的混合

$p(x) = \sum_{k=1}^{K} \pi_k \mathcal N (x\mid\mu_k,\Sigma_k)$

其中

K是高斯成分数量
$\pi_k$是第 k 个成分的权重，大于零且sum为1
$\mu_k$是第 k 个高斯中心
$\sum_k$是第 k 个高斯协方差矩阵

GMM的生成过程在直觉上可以理解成：先随机选择一个高斯成分，再从该高斯成分中采样一个数据点。这个高斯成分可以认为是一个隐变量

说到隐变量，自然想到变分推断，以及ELBO等等。这里先点到为止，以后再说。

与马氏距离的关系

$-\log \left[ \pi_k \mathcal N (x\mid\mu_k,\Sigma_k) \right] = \frac12d_k^2(x) + \frac12\log|\Sigma_k| - \log\pi_k + C$

也就是说，判断某个点更像哪个成分时，需要综合到该成分中心的马氏距离；该成分的协方差大小；改成份本身出现的先验概率

这里不再讲述EM算法通过交替优化学习GMM

K-means

K均值可以看作GMM的一个简化极限情况，即假设所有高斯具有相同权重，相同球形协方差，并采用硬分配（GMM采用软分配，可以直觉上理解为label smoothing）

基于方向的相似度

距离往往受到方向和长度两个因素的影响。当我们不关心绝对长度，而关心方向是否接近。比如说句子语义是否相似；对比学习的正负样本是否容易区分等等

点积

点积往往也叫做内积。这里数学知识都清楚，我们从直觉来简单讲讲就好

就是说我们：

$x^\top y = \|x\|_2 \|y\|_2 \cos\theta$

方向越接近cos越小，值越大。但同时收到模长和方向两个因素影响.

为了消除模长的干扰，一种最简单的方法就是L2归一化，也就是将向量归一化为单位向量再计算点积。

余弦相似度

$\cos(x,y) = \frac{ x^\top y }{ \|x\|_2\|y\|_2 }$

这就像是对点积进行另一种归一化对吧。为了除零错误我们通常在分母添加一个小正数

常见的余弦距离定义为：

$d_{\cos}(x,y) = 1-\cos(x,y)$

这样值的范围为0到1

关注两个向量之间的夹角，而不是绝对长度。但经过L2归一化后，余弦距离和欧式距离排序是等价的

实际应用中我们往往会除以一个温度参数 $\tau$，尤其是在对比学习中：

$s(x,y) = \frac{ \operatorname{cos}(x,y) }{ \tau }$

例如，再一组候选样本中，可以根据相似度构造softmax概率

$p_i = \frac{ \exp \left( \operatorname{cos}(x,y_i)/\tau \right) }{ \sum_j \exp \left( \operatorname{cos}(x,y_j)/\tau \right) }$

温度参数决定了概率分布的尖锐程度。$\tau$ 越小，相似度差距越大，softmax分布越尖锐。直觉上这就好比对比学习中的拉近正样本

角距离

$x^\top y = \|x\|_2 \|y\|_2 \cos\theta$

不过多解释，相比余弦相似度满足三角不等式，且保留取值非负（0~pi），可以视为严格意义上的度量

概率分布之间的差异度量

这一块我觉得很信息论这门课有很大联系。OUC的大家可以试着选修信息论基础这门课，可以作为机器学习入门。不过z老师的话比较喜欢吹牛，不太会讲到重点上来（呵呵）

这是前言，现在回到正题

一个概率分布本身也可以写成向量。比如说离散分布。这样我们理论上可以计算两个概率向量之间的欧式距离，这在某些情况下没有问题，但概率分布具有额外的语义：

每个元素表示概率质量
所有元素之和必须为 1
某些为止概率为0时，含义特殊
又是还需要考虑概率质量从一个位置转移到另一个位置的代价

基础知识有：信息量（-logp）、熵（$-\sum_{i=1}^Dp_ilogp_i$）

KL散度

交叉熵

我们假设真实分布是P，但我们使用另一个分布Q来描述数据，那么交叉熵定义为

$H(P,Q) = -\sum_{i=1}^{D} p_i\log q_i$

用于衡量：当真实数据分布服从 P，但我们使用 Q 进行预测或编码时，平均需要付出多少代价。如果 Q 对真实高概率事件也给出较高概率，那么交叉熵偏小。如果 Q 对高概率事件给出很低概率，那么交叉熵会显著增大。

Pocon

距离度量

一文讲通机器学习的距离、相似度和分布散度

距离

相似度

相异度

散度

基于绝对位移的向量距离

范数距离

欧式距离

假设

解决方法

量纲问题

马氏距离

什么是特征间的相关性？

协方差矩阵

马氏距离

从距离到概率模型

高斯分布

马氏距离和高斯分布的关系

负对数似然

GMM

高斯混合模型

与马氏距离的关系

K-means

基于方向的相似度

点积

余弦相似度

角距离

概率分布之间的差异度量

KL散度

交叉熵

JS散度

Wasserstein距离

Hellinger距离与MMD

离散对象的距离

深度学习中的度量学习