シャノンのエントロピー公式。私の混乱を助けます

Question

エントロピーの式の私の理解は、それがいくつかのデータを表現するために必要なビットの最小数を計算するために使用されるということです。定義されている場合、通常は別の言い方をしますが、以前の理解は今まで頼っていたものです。

これが私の問題です。 100 '1'の後に100 '0' = 200ビットが続くシーケンスがあるとします。アルファベットは{0,1}、エントロピーのベースは2です。シンボル<！> quot; 0 <！> quotの確率。 0.5および<！> quot; 1 <！> quot; 0.5です。したがって、エントロピーは1または1ビットであり、1ビットを表します。

ただし、100/1/100/0のようにランレングスエンコードできます。この場合、出力するビット数の後にビットが続きます。データよりも小さい表現を持っているようです。特に、100をはるかに大きくする場合。

使用しているもの： http://en.wikipedia.org/wiki/Information_entropy現時点での参照として。 どこで私は間違えましたか？シンボルに割り当てられた確率ですか？私はそれが間違っているとは思わない。または、圧縮とエントロピーの関係が間違っているのでしょうか？他に何か？

ありがとう。

編集

フォローアップの回答のいくつかを以下に示します。メッセージの特定のインスタンスにエントロピー公式を適用して、その情報内容を見つけようとしますか？メッセージ<！> quot; aaab <！> quot;を取得することは有効ですか？エントロピーは〜0.811であると言います。 「はい」の場合、1 ... 10 .... 0のエントロピーはどうなりますか。1と0はエントロピーの公式を使用してn回繰り返されます。答えは1ですか？

はい、入力シンボルのランダム変数を作成し、メッセージに基づいて確率質量関数を推測していることを理解しています。私が確認しようとしているのは、エントロピーの式がメッセージ内のシンボルの位置を考慮していないことです。

Answer 1

  

または、圧縮とエントロピーの関係が間違っていましたか？

かなり近いですが、この最後の質問は間違いがどこにあったかです。元の表現よりも小さい形式に何かを圧縮できる場合、元の表現に少なくとも冗長性があることを意味します。 メッセージの各ビットは実際には1ビットの情報を伝えていませんでした。

冗長データはメッセージの情報内容に寄与しないため、エントロピーも増加しません。たとえば、<！> quot; random bit generator <！> quot;を想像してください。値<！> quot; 0 <！> quot;のみを返します。これはまったく情報を伝えません！ （実際には、1種類のシンボルのみで構成されるバイナリメッセージはエントロピー式でゼロによる除算を必要とするため、未定義の情報量を伝えます。）

対照的に、ランダムなコインフリップを多数シミュレートした場合、このメッセージのサイズを大幅に減らすことは非常に困難です。各ビットは1ビット近くのエントロピーに寄与します。

データを圧縮すると、その冗長性が抽出されます。その代わりに、このデータを圧縮および圧縮解除する方法を知っているスキームを考案する必要があるため、1回限りのエントロピー価格を支払います。それ自体が情報を受け取ります。

  

ただし、100/1/100/0のようにランレングスエンコードできます。この場合、出力するビット数の後にビットが続きます。データよりも小さい表現を持っているようです。特に、100をはるかに大きくする場合。

要約すると、元のデータよりもデータのエンコードを小さくするスキームを考案できるという事実から、何か重要なことがわかります。つまり、元のデータにはほとんど情報が含まれていませんと書かれています。

---

さらに読む

いくつかの例を使用して、任意の数字列のエントロピーを正確に計算する方法など、これをより徹底的に扱うには、この短いホワイトペーパー。

Answer 2

コルモゴロフの複雑さ

をご覧ください

  

情報を失わずに文字列を圧縮できる最小ビット数。これは、普遍的なチューリングマシンによって与えられる、固定されているが普遍的な圧縮解除スキームに関して定義されます。

また、特定のケースでは、アルファベット{0,1}に制限しないでください。あなたの例では、{0 ... 0、1 ... 1}（0の100と1の100）を使用します

Answer 3

この例ではエンコードは機能しますが、同等の有効なケースを考えることができます：010101010101 ...これは1/0/1/1 / ...としてエンコードされます

エントロピーは、病理学的例だけでなく、指定されたアルファベットで作成できるすべての可能なメッセージにわたって測定されます！

Answer 4

John Feminellaは正しかったが、言いたいことがもっとあると思う。

シャノンエントロピーは確率に基づいており、確率は常に見る人の目にあります。

あなたは、1と0が等しくありそうだと言いました（0.5）。その場合、100 1の後に100 0が続く文字列の確率は0.5 ^ 200で、その中の-log（base 2）は200ビットです。ただし、その文字列のエントロピー（シャノン用語で）は、その情報内容にその確率を掛けたもの、つまり200 * 0.5 ^ 200であり、依然として非常に小さい数字です。

これは重要です。文字列を圧縮するためにランレングスコーディングを行うと、この文字列の場合、文字列の長さは短くなりますが、2 ^ 200文字列全体で平均するとうまくいきません。運が良ければ、平均で約200になりますが、それ以下ではありません。

一方、元の文字列を見て、それが生成された人は誰でも同じように生成する可能性が高いと言う場合、その確率は0.5 ^ 200よりも大きいと本当に言っているので、ストリングのジェネレーターの元の確率構造、つまり200ビットよりもエントロピーが低いという異なる仮定を立てます。

個人的には、特にコルモゴロフ（アルゴリズム）の情報を見ると、このテーマが本当に面白いと思います。その場合、文字列の情報内容を、それを生成できる最小のプログラムの長さとして定義します。これは、ソフトウェアエンジニアリングと言語設計に関するあらゆる種類の洞察につながります。

お役に立てば幸いです。ご質問ありがとうございます。