SciTech-BigDataAIML-Measurement: Euclidian Distance + Manhattan Distance + Area面积 + Density密度 + KLD(KL散度):测度比较"两Distribution(概率分布)"的Similarity(接近度)

abaelhe / 2024-12-29 / 原文

Measurement

测度

Euclidian Distance(欧几理得距离)

$\large \begin{array}{rl} \\ EuDistance(Point_1, Point_2) &= \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \\ where: & \\ Point_1 &= (x_1, y_1), \\ Point_2 &= (x_2, y_2), \\ \end{array}$

Manhattan Distance(🚕出租车站点距离)

$\large \begin{array}{rl} \\ MhtDistance(Point_1, Point_2) &= |x_1 - x_2| + |y_1 - y_2| \\ where: & \\ Point_1 &= (x_1, y_1), \\ Point_2 &= (x_2, y_2), \\ \end{array}$

KLD(Kullback-Leibler Divergence，KL散度):

测度比较两Distribution的Similarity

AI领域最重要的 Measure Method of Distributions(分布度量方法)
简写和全称: KLD(Kullback-Leibler Divergence, KL散度)
用途: 测度比较两Distribution的Similarity(
- 统计应用上, 我们经常需要用一个常用、组件模块化、简单近似的 $\large Distribution$ $\large f^* $，
  去描述另一个复杂的， $\large Distribution$ $\large f $ 或 $\large Observations(观察数据)$ $\large D$；
- 这时,我们需要一个度量来衡量选择的 $\large \bm{ Approximated\ Distribution}$ $\large f^* $
  对比原 $\large Distribution$ $\large f$ 总共 $\large Loss$ 多少$\large \bm{ Information(信息量)}$。
  这就是KLD(散度)起作用的地方。

$\large Information\ Entropy$(信息熵)

KL(Kullback-Leibler Divergence, 散度)起源于 IT(Information Theory, 信息理论)。
I.T.的主要目标是量化数据的信息量。
I.T. 最重要的度量标准称为 $\large Entropy$(熵), 常用 $\large H$ 表示。
$large \text{for a Distribution} \large p(X)$, $\large \text{ the } Definition \text{ of } Entropy$ 的定义是:
$\large \begin{array}{rl} \\ H &= \overset{N}{\underset{i=1}{\sum}}{p(x_{i}) \cdot log_{k}{p(x_{i})}} \\ if\ k = 2, then: \\ \end{array}$

如果计算时使用$\large log_{2}$, 我们可以将Entropy(熵)解释为
"Encoding(编码)我们的Information(信息)所需的$ Minimum\ Number \text{ of } bits$(最小比特数)。

举几个例子，有一门语言是由 ABCD 四个字母组成的，整个语料库为 8192个字母。

Example 1, A、B、C、D 四个字母分别占 1/2(4096个), 1/4(2048个), 1/8(1024个), 1/8(1024个)。
那么最有效的一种编码方式为 A(0), B(10), C(110), D(111)。
整个语料库的长度 4096 x 1 + 2048 x 2 + 1024 x 3 x 2=14336，平均长度为 14336/8192=1.75。
和下面代码的【结果1】一致。
Example 2, ABCD 等概率, 最有效的一种编码方式为 A(00), B(01), C(10), D(11), 计算平均长度为2，
和代码中的【结果2】一致。
Example 3: ABCD 四个字母占比变成1/8(1024个), 1/8(1024个), 1/2(4096个), 1/4(2048个),
最有效的一种编码方式为 A(110), B(111), C(0), D(10), 计算平均长度为1.75，
和代码中的【结果3】一致。

我们用$\large Entropy$(熵)的方式计算：

代码示例1：

import math

def cal_entropy_log2(prob_distribution):
    return -sum(p * math.log2(p) for p in prob_distribution)

p = [0.5, 0.25, 0.125, 0.125]
entropy = cal_entropy_log2(p)
print(f"熵: {entropy}")
#【结果1】输出为：熵: 1.75

q = [0.25, 0.25, 0.25, 0.25]
entropy = cal_entropy_log2(q)
print(f"熵: {entropy}")
#【结果2】输出为：熵: 2.0

q2 = [0.125, 0.125, 0.5, 0.25]
entropy = cal_entropy_log2(q2)
print(f"熵: {entropy}")
#【结果3】输出为：熵: 1.75

import numpy as np
def kl_divergence_log2(a, b):
    return sum(a[i] * np.log2(a[i]/b[i]) for i in range(len(a)))

print('KL-divergence_log2(例1 || 例2): %.6f ' % kl_divergence_log2(p, q))
# 输出：KL-divergence_log2(例1 || 例2): 0.250000 

print('KL-divergence_log2(例1 || 例3): %.6f ' % kl_divergence_log2(p, q2))
# 输出：KL-divergence_log2(例1 || 例3):

$\large KL$(Kullback-Leibler) 散度的计算公式

$\large KL\text{ is a kind of }Method \text{ for } measuring \text{ the } difference \text{ between } two\ Distributions$
散度, 是一种衡量两个概率分布之间差异性的度量方法。

$\large KL$是对熵公式的轻微修改。
$\large \begin{array}{ll} \\ Hypothesis, \\ \text{ there is a }Distribution\ p(X), \text{ usually means } Observations,\ Samples,\\ \text{ and } Approximated\ Distribution\ q, \text{ usually means the }output \text{ of } Predicative\ Model,\\ then, \text{ the } difference \text{ between these } two\ Distribution \text{ is as follow }：\\ \end{array}$

离散性的公式如下：
$\large \begin{array}{rl} \\ D_{KL}(p || q) &= \overset{N}{\underset{i=1}{\sum}}{[ p(x_{i}) \cdot ( log_{k}{p(x_{i})} - log_{k}{q(x_{i})} ) ]} \\ & = \overset{N}{\underset{i=1}{\sum}}{( p(x_{i}) \cdot log_{k}{ \dfrac{p(x_{i})}{q(x_{i})} } )} \\ \end{array}$

连续性的公式如下：
$\large \begin{array}{rl} \\ D_{KL}(p || q) &= \int_{-\infty}^{\infty} { p(x) \cdot [ log_{k}{p(x)} - log_{k}{q(x)} ] } \text{ d}x \\ &= \int_{-\infty}^{\infty} { p(x) \cdot log_{k}{ \dfrac{p(x)}{q(x)} } \text{ d}x } \\ \end{array}$

二进制编码角度的解释

假如用二进制编码长度来解释 $\large KL$ , 其衡量的是当使用基于$\large q(x)$ 的编码而非基于$\large p(x)$ 的编码对来自$\large p(x)$的$\large Samples$进行编码时, 所需的额外比特数的$\large Expectation$, 结果大于等于 0(两个$\large Distribution$完全一样时为 0)。

还以【例1】计算 $\large KL$ 散度（注意：对数的底还是取 2，而不是概率学用到的自然底数 e）。
当我们使用【例2】的 ABCD 编码方式对【例1】的数据编码时，
平均长度显然就是 2，
所以 $\large KL(例1||例2) =2-1.75=0.25$。

当我们使用【例3】的 ABCD 编码方式对【例1】的数据编码时，
长度变成 (4096 * 3 + 2048 * 3 + 1024 * 1 + 1024 * 2 )/8192 = 2.625，
所以 $\large KL(例1||例3) = 2.625-1.75 =0.875$，

和代码一致, 即相对于自身分布的最优编码，用另一个分布的最优编码来编码时，平均额外需要0.875个比特。

KL 散度的分步计算

KL 散度的中间步骤的计算结果, 可能为正, 也可能为负数。

以下为 p 和 q1 的 $\large KL$ 散度的分步计算结果，可对照上面的数据示例和程序输出看。

p[i]	q[i]	p[i]/q[i]	log(p[i]/q[i])	p[i]*log(p[i]/q[i])
0.15	0.14	1.071429	0.068993	0.010349
0.13	0.14	0.928571	-0.074108	-0.009634
0.23	0.25	0.920000	-0.083382	-0.019178
0.09	0.08	1.125000	0.117783	0.010600
0.2	0.21	0.952381	-0.048790	-0.009758
0.05	0.06	0.833333	-0.182322	-0.009116
0.15	0.12	1.250000	0.223144	0.033472
			求和：	0.006735

分步计算的结果和后面代码的一致。

如下面代码所示。

import numpy as np
from kl_div_data import box_p, box_q1, box_q2

def kl_divergence_step(a, b):
    return np.array([a[i] * np.log(a[i]/b[i]) for i in range(len(a))])

np.set_printoptions(precision=6)

print(kl_divergence_step(box_p, box_q1))
# 输出：
# [ 0.010349 -0.009634 -0.019178  0.0106   -0.009758 -0.009116  0.033472]

print(kl_divergence_step(box_p, box_q2))
# 输出：
# [ 0.046523  0.021717  0.010224 -0.051783  0.057536 -0.058158  0.076624]

$\large KL$ 散度的特点及代码示例

$\large KL$散度具有以下显著特点：

非对称性： $\large KL$散度是非对称的，
即从 P分布到 Q分布的 $\large KL$散度, 与从 Q分布到 P分布的 $\large KL$散度可能不同。
如代码中示例， $\large KL(p || q1)$ 和 $\large KL(q1 || p) $ 不同。
非负性： $\large KL$散度的值始终为非负数。
当且仅当两个概率分布完全一致时， $\large KL$散度的值才为零。
$\large KL$散度值越大，表示两个概率分布越不相似。
如代码示例，相对 p, q2 的 $\large KL$ 散度比 q1大, 这和图上的直观显示一致。
非度量性： $\large KL$散度并不满足度量空间的性质，特别是三角不等式。
由于非对称性和非度量性， $\large KL$ 散度不能用于计算两个分布之间的“距离”或“相似度”。
直观性： $\large KL$散度的值越大, 表示用一个分布近似另一个分布时引入的信息损失或误差越大。
这使得KL散度在度量模型的误差或信息损失方面非常直观。

以下代码列出 $\large KL$ 散度的三种实现方式：

简单函数
使用 Scipy rel_entr 函数
使用 Pytorch KLDivLoss

简单函数

import numpy as np
from scipy.special import rel_entr
from kl_div_data import box_p, box_q1, box_q2

def kl_divergence(a, b):
    return sum(a[i] * np.log(a[i]/b[i]) for i in range(len(a)))

print('KL-divergence(p || q1): %.6f ' % kl_divergence(box_p, box_q1))

# KL 散度没有对称性
print('KL-divergence(q1 || p): %.6f ' % kl_divergence(box_q1, box_p))
# 从计算结果可以看出，概率分布 q2 和 p 的差异明显更大
print('KL-divergence(p || q2): %.6f ' % kl_divergence(box_p, box_q2))

使用 Scipy rel_entr 函数

# 使用 Scipy rel_entr 函数
p = np.array(box_p)
q1 = np.array(box_q1)
q2 = np.array(box_q2)

# 和上面函数的计算结果一致
print('rel_entr KL-divergence(p || q1): %.6f ' % sum(rel_entr(p, q1)))
print('rel_entr KL-divergence(p || q2): %.6f ' % sum(rel_entr(p, q2)))
print('rel_entr KL-divergence(q1 || p): %.6f ' % sum(rel_entr(q1, p)))
# 自身的 KL 散度是0
print('rel_entr KL-divergence(p || p): %.6f ' % sum(rel_entr(p, p)))

# -------  输出如下 -------
# KL-divergence(p || q1): 0.006735 
# KL-divergence(q1 || p): 0.006547 
# KL-divergence(p || q2): 0.102684 
# rel_entr KL-divergence(p || q1): 0.006735 
# rel_entr KL-divergence(p || q2): 0.102684 
# rel_entr KL-divergence(q1 || p): 0.006547 
# rel_entr KL-divergence(p || p): 0.000000

使用 Pytorch KLDivLoss

# torch 的写法，参考：https://pytorch.org/docs/stable/generated/torch.nn.KLDivLoss.html
import torch
kl_loss = torch.nn.KLDivLoss(reduction="sum",log_target=False)

# 第 1 个参数为模型的输出，上面直接指定了概率，故增加一次 log
# 第 2 个参数为真实概率
output = kl_loss(torch.log(torch.tensor(q1)), torch.tensor(p))
print(output)
# 输出：
# tensor(0.0067, dtype=torch.float64)