机器算法验证 - 校正数据集大小的 Kullback-Leibler 散度 - 吾爱随笔录

校正数据集大小的 Kullback-Leibler 散度

机器算法验证距离信息论 kullback-leibler 互信息噪音

2022-04-13 01:18:47

我们有以下 KLD 的实现：

import numpy as np
import pandas as pd
from scipy.stats import entropy


def KL_divergence(a, b):
    hist_a = np.histogram(a, bins=100, range=(0,1.0))[0]
    hist_b = np.histogram(b, bins=100, range=(0,1.0))[0]
    hist_b = np.where(hist_b == 0.0, 1e-6, hist_b)
    return entropy(hist_a, hist_b)

它采用两个数据集（范围为 0-1），将它们离散化为 100 个相等的 bin，并在结果数据集上计算 KLD。

在实践中，这根本行不通，因为这个距离随着数据集的大小（较小的数据集 = 较大的距离）而极大地缩放。在这里，我编写了一个简单的脚本，模拟不同大小数据（大小为 100、1000、10000）的许多分布，评估 KLD，并绘制每个直方图。“潜在概率”是这些数据集可能遵循的示例分布。

import numpy as np
import pandas as pd
from scipy.stats import entropy
import matplotlib.pyplot as plt
%matplotlib inline


def KL_divergence(hist_a, hist_b):
    return entropy(hist_a, hist_b)

actual_bin_counts = np.array([7805,   436,   396,   456,   559,   809,  1139,  1928,  4618, 60948])
underlying_probability = actual_bin_counts / actual_bin_counts.sum()

def generate_histogram(n_samples, true_probs = underlying_probability):
    uniform_random = np.random.uniform(0,1, size=n_samples)
    bins_counts = np.digitize(uniform_random, underlying_probability.cumsum())
    return np.unique(bins_counts, return_counts=True)[1]

distances_1000 = []
for repeat in range(10_000):
    try:
        sampled_a = generate_histogram(1000)
        sampled_b = generate_histogram(1000)
        distances_1000.append(KL_divergence(sampled_a, sampled_b))
    except:
        # we had a category with 9 bins. I don't care enough to fix it.
        pass

distances_10_000 = []
for repeat in range(10_000):
    try:
        sampled_a = generate_histogram(10_000)
        sampled_b = generate_histogram(10_000)
        distances_10_000.append(KL_divergence(sampled_a, sampled_b))
    except:
        # we had a category with 9 bins. I don't care enough to fix it.
        pass

distances_100_000 = []
for repeat in range(10_000):
    try:
        sampled_a = generate_histogram(100_000)
        sampled_b = generate_histogram(100_000)
        distances_100_000.append(KL_divergence(sampled_a, sampled_b))
    except:
        # we had a category with 9 bins. I don't care enough to fix it.
        pass

plt.xscale('log')
plt.hist(distances_1000, bins=100);
plt.hist(distances_10_000, bins=100);
plt.hist(distances_100_000, bins=100);

如您所见，虽然基础分布相同，但距离是无法比拟的。如何纠正数据集的大小？

2个回答

基本问题是真实基础分布之间的 KL 散度为零，因为它们在您的代码中是相同的（，）但采样变化（几乎）确保在有限样本中两者之间的 KL 散度经验分布将是正数，因为经验分布不会完全相等。由于随着样本量趋于无穷大，经验分布（均匀地）收敛到真实分布，因此样本 KL 散度几乎肯定会随着样本量达到其真实值，这会导致您的直方图越来越接近随着样本量的增加为零。 $U(0,1)$ $\rightarrow \infty$

如果您查看直方图在 x 轴上（大致）居中的位置，您会看到的直方图位于的直方图所在位置的大约处（与。）样本大小的比率并非巧合的是。与其他两个相比，直方图也可以看到相同的效果。 $n=100,000$ $1/100^{th}$ $n=1000$ $3\times 10^{-4}$ $3\times 10^{-2}$ $100-1$ $n=10,000$

请注意，在两个基础分布不相同的情况下，分箱到一个恒定数量的箱中通常不会允许 KL 散度接近真实值，相反，收敛将是离散之间的 KL 散度的真实值分布以明显的方式从底层连续分布和 bin 边界形成，因此在这种情况下收敛到真实值是您编写代码的方式带来的一个快乐的巧合。

KL 散度并不会真正产生较大数据集的较小距离，反之亦然。在您的示例中，由于代码中的采样步骤（在 generate_histogram 中），距离是无法比较的。

本质上，当您使用该函数生成具有 100 个数据点的概率质量函数时，有相当多的采样不确定性会被输入到 KL 散度中。例如，当我使用 100 个数据点运行该函数时，我得到了一些认识：

generate_histogram(100)/100.

# array([0.09, 0.02, 0.01, 0.03, 0.02, 0.03, 0.02, 0.01, 0.77])
# array([0.06, 0.02, 0.01, 0.04, 0.06, 0.81])
# array([0.09, 0.01, 0.01, 0.01, 0.01, 0.01, 0.04, 0.04, 0.78])
# array([0.09, 0.03, 0.01, 0.03, 0.03, 0.09, 0.72])
# array([0.08, 0.01, 0.01, 0.04, 0.86])
# array([0.09, 0.02, 0.01, 0.01, 0.01, 0.01, 0.02, 0.09, 0.74])

（顺便说一句，你应该在这里检查你的实现，因为数组的长度不相等 - 即一些 bin 概率为零并且这些被忽略，而且我不知道 scipy 对不相等的数组长度做了什么。这不是具有较高数据点的其他两个部分的问题，因为任何块的概率通常都不为零。我怀疑这就是为什么第一个直方图如此偏斜而其他直方图没有的原因。）

另一方面，当您使用 10k 个数据点调用 generate_histogram 时，概率中没有太多的采样不确定性，并且输入 KL 散度函数的每个概率向量看起来都相同：

np.round(generate_histogram(10000)/10000., 2)
# array([0.1 , 0.  , 0.  , 0.01, 0.01, 0.01, 0.01, 0.03, 0.06, 0.77])
# array([0.1 , 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.02, 0.06, 0.77])
# array([0.1 , 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.02, 0.06, 0.77])
# array([0.1 , 0.01, 0.  , 0.01, 0.01, 0.01, 0.01, 0.02, 0.06, 0.77])
# array([0.1 , 0.  , 0.01, 0.01, 0.01, 0.01, 0.02, 0.02, 0.06, 0.77])

由于每个实现都与 2 dp 相同，因此 KL 散度反映了这一点，并且大多数时候基本上在 0 左右。

我推测您的第一个函数 ( KL_divergence(a, b)) 不能很好地工作，因为对于较小的数据集，100 个 bin 是巨大的。使用具有可比大小的数据集的 100 个 bin 的问题是，大多数 bin 中都会有 1、2 和 0，并且会有很大的抽样不确定性，这可能会导致您认为 KL 散度受以下因素影响数据集的大小，而在现实中，只有 bin 的数量和影响它的概率的采样不确定性。

我对 KL 散度没有太多经验，但它毕竟只是随机变量的函数，您应该能够根据您的具体用例来解释其估计中的不确定性。

例如，如果您使用不同大小的数据集，您将能够引导，即：

和引导（带替换的样本）以获得引导数据集和。 $D_1$ $D_2$ $D_1^*$ $D_2^*$
.cumsum()正如您已经完成的那样，通过获得 ECDF 的估计值。
计算这组自举数据的 KL 散度。
重复。

这样，您可以通过获取 KL 散度周围的采样不确定性来解释数据集的差异。

如果您只是在寻找点估计，您可以简单地采用自举分布的模式。

如果出于某种原因，您想向 KL 散度函数提供相同数量的数据点（可能使用更多的 bin），您可以对两个数据集进行核密度估计，对大量值进行采样来自这些密度，并在得到的概率向量上使用 KL 散度。这并不能真正解释采样的不确定性，但它可以让您克服实施问题。

其它你可能感兴趣的问题

上一篇随机森林“现成的”RMSE 下一篇麦当劳欧米茄：假设、系数和解释