從樣本中估計熵是荒謬的嗎？
要知道源的確切熵，我需要做的就是使用香農公式 $ \sum -p(i) \lg p(i) $ ， 在哪裡 $ i $ 是個 $ i $ - 源發出的字母表中的第一個元素。因此，唯一讓我無法說出確切熵的是不知道 $ p $ . 因此，估計熵的問題歸結為估計問題 $ p $ .
我研究了里德對這個問題的回答。Reid 似乎說你得到樣本 1011 你可能有 0 到 4 位熵。為什麼從這個樣本中估計機率分佈是荒謬的？結果我們得到了三個一和一個零。猜測是不是很荒謬 $ p(1) = 3/4 $ 和 $ p(0) = 1/4 $ ，因此對源熵的估計是 $ 0.8111 = 1/4 \times (-\lg(1/4)) + (3/4 \times (-\lg(3/4))) $ ，樣本中的資訊量為 $ 3.244 $ 位。
從理論上講，您可以將估計給定樣本（假設是獨立且同分佈的）樣本集合的熵的問題分解為兩個步驟：
- 估計基礎隨機變數的分佈
- 計算隨機變數的熵
一般來說，你可以通過“計數”來做第一個。如果您看到 4 個樣本的集合 $ 0, 0, 0, 1 $ , 你可以設置 $ \Pr[X = 0] = 3/4 $ ， 和 $ \Pr[X = 1] = 1/4 $ （這通常稱為“經驗分佈”）。然後，您可以輕鬆計算熵。
請注意，問題的其餘部分有一個很大的警告，因為您需要一個獨立且分佈相同的樣本來源來應用它。如果你看到 $ 1011 $ ，這是單個樣本，還是四個獨立的、相同分佈的樣本？要回答這個問題，您需要仔細考慮如何生成樣本，但無論如何我都會繼續討論假設您可以生成 iid 樣本的事情。
因此，熵計算的準確性降低到經驗分佈與“真實”基礎分佈的接近程度。對於“足夠大”的樣本量，它將收斂到真實分佈，但量化收斂速度變得很重要。有多種方法可以做到這一點，經驗分佈函式維基百科頁面中總結了一些方法。量化這一點的一種特別有用的方法是通過DKW 不等式。
讓 $ \mathcal{X} $ 是潛在的（未知的）分佈，讓 $ X_1,\dots, X_n $ 是 $ n $ iid 樣本來自 $ \mathcal{X} $ . 讓 $ F(x) $ 是的累積分佈函式 $ \mathcal{X} $ . 我們定義樣本的經驗累積分佈函式 $ X_1,\dots, X_n $ 通過： $$ F_n(x) = \frac{1}{n}\sum_{i = 1}^n \mathbf{1}{X_i \leq x} $$ 這裡 $ \mathbf{1}{X_i \leq x} $ 是一個“指標函式”，如果是 1 $ X_i \leq x $ , 否則為 0。所以 $ F_n(x) $ 計算有多少 $ X_i $ 小於 $ x $ （然後將其規範化為 $ [0,1] $ 除以 $ n $ ).
然後 DKW 不等式表明，對於任何 $ \epsilon > \sqrt{\frac{\ln(2)}{2n}} $ : $$ \Pr[|\sup_{x\in \mathbb{R}} (F(x) - F_n(x))| > \epsilon] \leq 2\exp(-2n\epsilon^2) $$ 這給出了累積分佈函式與經驗累積分佈函式之間的距離的“類切爾諾夫”界限。
在估計經驗累積分佈函式後，您可以將其轉換為各種機率的估計值。這是因為 $ p_i = \Pr[X = i] = \Pr[X \leq i] - \Pr[X \leq i-1] = F(i) - F(i-1)\approx F_n(i) - F_n(i-1) \pm 2\epsilon = \tilde{p}_i \pm 2\epsilon $ . 更正式地說，通過應用 DKW 不等式，我們將得到 $ |p_i - \tilde{p}_i| \leq 2\epsilon $ 很有可能 $ 2\exp(2n\epsilon^2) $ .
然後我們可以計算它的熵： $$ \begin{align*} \mathbb{H}[\tilde{X}] &= \sum_{i\in\mathsf{supp}(\tilde{X})} \tilde{p}i(-\log_2(\tilde{p_i}))\ &= \sum{i\in\mathsf{supp}(\tilde{X})} (p_i\pm 2\epsilon)(-\log_2(p_i\pm 2\epsilon)) \end{align*} $$ 從這裡你可以嘗試限制它與真實熵的接近程度。不幸的是，我目前看到的唯一方法是手動操作—— $ -\log_2(x) $ 是凸的所以 $ -\log_2(2(x+y)/2) \leq -1 -\log_2(x)/2 - \log_2(y)/2 $ ， 但 $ \pm\epsilon $ 可能是負面的，所以你開始遇到這些問題。
無論如何，您可以按照您的說法繼續，但要準確估計熵：
- 您需要能夠將隨機源“分解”為獨立且分佈相同的樣本
- 您需要一個大樣本量（因此估計值落在 DKW 不等式之外的機率， $ 2\exp(-2n\epsilon^2) $ ， 是小”）。