資料壓縮/零頻率問題

推斷模型的最大問題之一是零頻率問題。（零頻率問題和逃逸碼，作者 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 是獨立的，機率論也幫不了我們。”