计算描述长度

Question

我有两个整数数组，x 和 y:

x = np.array([[1, 2, 0, 12,  4],
              [5, 2, 1, 10, 12]]
            )

y = np.array([[1, 2, 0, 11,  4],
              [5, 3, 0, 10, 15]]
            )

并且我想使用 x 到 compress/compute y 的描述长度（以“位”为单位），然后比较“保存的位数”为压缩的结果。鉴于我们的数据很小，我们将简单地使用 n_bits = 8 （8 位）来存储每个整数。在未压缩的情况下，总共需要 2 x 5 x 8 = 80 位来存储 y（即 DL(y) = 80）。同样，DL(x) = 80。现在，假设 x 是压缩 y 的最佳“模型”/“假设”，然后根据 MDL 框架：

DL(y, x) = DL(y|x) + DL(x)

其中DL(x)是存储x所需的位数，DL(y|x)是给定x的y的剩余位数：

residual = x - y

array([[ 0,  0,  0, -1,  0],
       [ 0,  1, -1,  0,  3]])

那么，这个残差数组的DL(y|x)是什么？根据我遇到的一些例子（我不完全理解），DL(y|x) 可以通过首先识别残差

中唯一值的数量来计算

n_bits = 8
n_unique = len(np.unique(residual))  # 4
DL_residual = 2 * 5 * np.log2(n_unique) + n_unique * n_bits  # 52 bits

如果我没理解错的话，因为n_unique = 4（即残差的基数是4），那么看起来2 * 5 * np.log2(n_unique)是在计算存储残差的位数。但是，我不知道为什么需要 n_unique * n_bits （也许不需要？？）。天真地，我会假设 2 * 5 * np.log2(n_unique) 就足够了。

我什至不知道这是否是计算残差描述长度的正确方法，最终，我需要弄清楚残差的描述长度是多少。

Answer 1

TLDR；您需要 2 * 5 * np.log2(n_unique) 位来存储将哪个唯一值放在何处，但是您还需要 n_unique * n_bits 位来存储唯一值本身。

您为使用 x 压缩 y 而应用的转换如下所示：

使用 x 作为 y 的最佳模型并计算 residual。如果 x 是完美的，您希望在 residual 中看到全零。但是，由于它不是完美的，因此还剩下一些其他值。您已经获得了以下残差：

array([[ 0,  0,  0, -1,  0],
       [ 0,  1, -1,  0,  3]])

许多值是 0，还有一些是相同的。因此，为了压缩 residual，我们确定了唯一的整数值，并用存储唯一值的数据结构中的值索引替换每个值。我将在这里使用一个列表，特别是以下内容：

[0, -1, 1, 3]

当我用这个列表中的索引替换值时，残差变为：

array([[ 0,  0,  0,  1,  0],
       [ 0,  2,  1,  0,  2]])

由于索引比值更小，我们需要更少的位来存储它们。我们只需要 2 * 5 * log2(len(unique)) 位来存储这个转换后的数组。但是，如果我们只存储这个，我们就缺少需要插入以重建 y 的实际值！ 3. 因此，我们还需要存储包含唯一值的列表。这里的元素是具有通常位数 n_bits 的整数。我们有 n_unique=4 个，因此要存储 unique 除了仅存储索引外，我们还需要 n_unique * n_bits 位。

如果 x 可以完美地预测 y，那么 residual 将全为零。在这种情况下，只有一个唯一值 (0)。有了这个，您只需要存储数组的大小，或者如果您不想存储此信息，则将 0 的字符串编码为一个位。当然，您还必须存储 0。

事实上，即使 residual 仅包含一些其他值，您也会获得相同的压缩大小。

计算描述长度

Computing Description Length

python

numpy

information-theory