サンプルからエントロピーを推定するのはばかげていますか？
ソースの正確なエントロピーを伝えるために私がする必要があるのは、シャノンの式を使用することだけです $\sum -p(i) \lg p(i)$、 どこ $i$ それは $i$-ソースによって発行されたアルファベットの-番目の要素。したがって、正確なエントロピーを教えてくれないのは、知らないことだけです。$p$。したがって、エントロピーを推定する問題は、推定の問題に還元されます。$p$。
私はこの質問に対するリードの答えを研究しました。Reidは、0〜4ビットのエントロピーを持つことができるサンプル1011を取得すると言っているようです。このサンプルから確率分布を推定するのはなぜばかげているのでしょうか。3つの1と1つの0が得られることがわかりました。それを推測するのはばかげていますか$p(1) = 3/4$ そして $p(0) = 1/4$したがって、ソースのエントロピーの推定値は次のようになります。 $0.8111 = 1/4 \times (-\lg(1/4)) + (3/4 \times (-\lg(3/4)))$、およびサンプルの情報量は $3.244$ ビット。
回答
理論的には、（独立していて同じように分布していると仮定した）サンプルの特定のコレクションのエントロピーを推定する問題を2つのステップに分解できます。
基礎となる確率変数の分布を推定する
その確率変数のエントロピーを計算する
一般的に、あなたは「数える」ことによって最初をすることができます。4つのサンプルのコレクションが表示された場合$0, 0, 0, 1$、設定できます $\Pr[X = 0] = 3/4$、および $\Pr[X = 1] = 1/4$（これは一般に「経験的分布」として知られています）。その後、エントロピーを簡単に計算できます。
質問の残りの部分には大きな注意点があることに注意してください。それを適用するには、独立した同じ分布のサンプルのソースが必要です。あなたが見たら$1011$、これは単一のサンプルですか、それとも4つの独立した同じ分布のサンプルですか？これに答えるには、サンプルがどのように生成されるかを慎重に考える必要がありますが、それでも、iidサンプルを生成できると仮定して説明を続けます。
したがって、エントロピー計算がどれだけ正確であるかは、経験分布が「真の」基礎となる分布にどれだけ近いかということになります。「十分に大きい」サンプルサイズの場合、実際の分布に収束しますが、収束率を定量化することが重要になります。これを行うにはさまざまな方法がありますが、いくつかは経験分布関数のウィキペディアのページにまとめられています。これを定量化するための特に有用な方法の1つは、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)$、 小さいです"）。
この答えは他の答えを補完するものです。
ここで入手できる論文「エントロピーの近似の複雑さ」で、Tugkan Batu et alは、この問題に対する複雑さの理論的アプローチを示しています。サポートされているディストリビューションに焦点を当てる$[n]=\{1,2,\ldots,n\}.$興味深いことに、それらの結果の一つは、エントロピため乗法推定値は、のために働くであろうということである任意の配布$n$ 存在しません。
特に、彼らは、劣線形時間（サポートサイズ）で高効率でエントロピーを推定することに関心があります。 $n$）。彼らは、ブラックボックスモデル[@Markによる回答で検討]と、実際に「give me$p_i$「 ffor some$i\in [n],$ そのように見積もりを作成します。
それらは、乗法因子による乗法因子推定を定義します $\gamma>1,$ その出力のアルゴリズムとして $\hat{H}$ 満たす $$ \frac{H}{\gamma} \leq \hat{H} \leq \gamma H. $$
次に、 $\gamma>1,$ そして $0<\epsilon_0<1/2,$ それらは、上の分布のエントロピーを近似できることを証明します。 $[n]$ 乗法係数内に $(1+2\epsilon_0)\gamma,$ 少なくとも確率で $3/4,$ に $$O((n^{1/\gamma^2}/\epsilon_0^2)\cdot \mathrm{poly}(\log n))$$ 分布のエントロピーが少なくともである限り、時間 $\frac{3\gamma}{2\epsilon_0(1-2\epsilon_0)}.$
存在しない結果については、 $\gamma>1,$ すべての分布のエントロピーを内に乗法的に近似するアルゴリズムはありません $\gamma.$ きちんとした証明は、最初にアルゴリズムにランタイムがあることを前提としています $\leq c n^{\alpha},$ いくつかのための $\alpha>0,$ いくつかの $c\in (0,1),$ 次に、そのようなアルゴリズムは2つの分布を区別する必要があることを指摘します $$ \mathbb{p}=(1-n^{-\alpha},n^{-\alpha-1},\ldots,n^{-\alpha-1}) $$ そして $$ \mathbb{q}=(1,0,\ldots,0) $$ 出力することにより $\hat{H}\geq \frac{1}{\gamma}n^{-\alpha} \log n>0,$ にとって $\mathbb{p}$ そして $\hat{H}=0$ にとって $q$ （以来 $\gamma 0=0/\gamma=0.$）しかし、のみを使用するアルゴリズム $c n^{\alpha}$ サンプルは確実に区別できません $\mathbb{p},$ そして $\mathbb{q}$ なので $n$ 増加します。
次に、確率変数を入力として受け取る関数の場合はエントロピー。この確率変数が4ビットの文字列である場合。その場合、4ビットはエントロピーに関する情報を提供しません。それが可能だから$\mathbb{P}(X=1011)=1$ または $\mathbb{P}(X=1011)=\frac{1}{2^4}$。あなたがあなたの文字列を次のように考えるなら$4$ 同じ変数のサンプル：少し異なります：エントロピーがそうではないことを知っています $zero$： $\mathbb{P}(X=0)\neq 0$ そして $\mathbb{P}(X=1)\neq 0$。しかし、あなたはそれ以上の情報を持っていません。多分：$\mathbb{P}(X=0)\neq 0.999999$ そして $\mathbb{P}(X=1)= 0.000001$ または $\mathbb{P}(X=0)=\mathbb{P}(X=1)=\frac{1}{2}$。
または、より一般的には、 $1>\epsilon > 0$： $\mathbb{P}(X=0)=\epsilon$ そして $\mathbb{P}(X=1)= 1 -\epsilon$ 可能です。
次にエントロピー $H$ 検証： $0<H\leq1$。
それはあなたを助けません...
この変数をベルヌーイ変数として記述したい場合、エントロピーは良いツールではありません。（統計で）Estimatorを使用することをお勧めします。しかし、理論的には、この見積もりを暗号化の目的として使用することはできません。