数据压缩/零频率问题

推断模型的最大问题之一是零频率问题。（零频率问题和逃逸码，作者 Arturo San Emeterio Campos。1999年）

在解压缩文件时，自适应霍夫曼解码器会根据明文中迄今为止看到的字母来不断改变其对哪些字母可能出现以及哪些字母不可能出现的估计。它根据每个字母出现的频率来预测未来字母的概率。然后，解码器将使用其当前的码字表来解码下一个字母，该表将短码字分配给它预测很可能出现的每个字母，并将长码字分配给它预测可能出现但不太可能的每个字母。

例如，假设一个文本文件以“Gadsby”（1939）的扩展引文开头。最简单的方法——到目前为止“e”的频率为零，因此我将假设它将继续为零——将无法正常工作。

如果霍夫曼解码器认为某个字节的频率为零，那么就无法说服该解码器发出该字节——现在不能，将来也不能。该字节不再是其字典的一部分。因此，解码器将无法正确地发出最终确实使用字母“e”的明文。

因此，为了能够正确解码以“Gadsby”的引文开头，然后包含字母“e”的明文，我们必须让霍夫曼解码器对“e”的未来频率进行非零估计。即使是不准确的估计——只要它不完全为零——也能让解码器正确地发出明文，而不会出错。准确的估计将产生比不准确的估计更小的压缩文件。不幸的是，很难准确地估计从未出现过的东西的频率。

上下文混合自适应解压缩器也有类似的问题。为了获得良好的压缩率，解压缩器需要准确地预测下一个比特是 1 的概率，P(x)。在解压缩足够多的文本后，解压缩器可以观察到事件 A 发生了 Ax 次，并且在 A1 次中下一个比特是 1。因此，在没有其他信息的情况下，当 A 再次发生时，它估计下一个比特是 1 的概率为 P(x|A) = A1/Ax。如果 A 和 B 以前同时发生过很多次 ABx（并且在这些情况下，下一个比特是 1 的次数为 AB1），那么当 A 和 B 再次同时发生时，我们对 P(x|A,B) 的最佳估计——我们对下一个比特是 1 的估计——是 AB1/ABx，完全忽略 A1 和 Ax 以及 B1 和 Bx。

但是，当 A 和 B 第一次同时发生时，我们无法这样做——我们无法计算 0/0。我们所能做的就是猜测 P(x|A,B) 与 P(x|A) 相同，或者与 P(x|B) 相同，或者以某种方式结合这些预测，可能使用像林肯指数这样的启发式方法，该方法考虑了每个事件发生的次数。给定事件计数 A1 和 Ax 以及 B1 和 Bx，如何对 P(x|A,B) 进行良好的估计？不幸的是，

“即使假设 A 和 B 是独立的，概率论也帮不了我们。”