エントロピー

シャノンの情報量：エントロピー

シャノンは情報理論の測定単位としてビットを考えた。

ある事象が起こる確率をｐとするとき，それが起こったという情報が持つ情報量Ｓは，
　　　Ｓ＝－logｐ ［ビット］
である。

• 情報の最小単位は，０／１，真／偽，ｙｅｓ／ｎｏのように「２つの状態のうちどちらか」のことだといえます。その情報量を１（ビット）とします。
• カード当てのゲームで，「カードの１枚が赤札だ（確率＝１／２）」という情報量も１です。では，「ハート，ダイヤ，スペード，クラブのうち，ハートである」という情報量は，「赤／黒の２つの状態のうち赤である」（情報量＝１）ことを知り，「ハートとダイヤのうちハートだ」（情報量＝１）を知ったと考えれば，２ビットであることは常識と合致します。それで，「４（＝２２）通りの状態のうち，どれであるか（ハート）を知ることの情報量は２である」としてもよいですね。

• 「万一の場合といいますが。この情報量は何ビットですか」log2(10)=3.32とする。

• 性質
  • 加法性：AとBが独立な事象のとき、「AもBも起こる」という事象の情報量は、Aの情報量とBの情報量の和である。
  • 起こりにくい事象（＝生起確率が低い事象）の情報量ほど、値が大きい。

符号化に関するシャノンの補助定理

• 符号化

文字をビット列に置き換えること。`a'という文字を`00'、`b'という文字を`01'と置き換える。
置き換えられたビット列を符号語という。元に戻すのは復号化。

瞬時復号可能な符号化Kがあったとして,それぞれの符号語の出現確率をp1,p2,p3,・・・とすると、符号語が出現するという事象の持つ情報量Ikはlog2(pk)であり、 平均情報量であるところのエントロピーEは、

E=-Σpilogpi

とあらわせる このとき、平均符号長LとエントロピーEの間には、

E＜または=L

という関係が成立する。これがシャノンの補助定理。 一意に復号可能な符号化はその平均符号語長をエントロピーより小さくできない。

エントロピー

ある事象Ａが起こる確率をｐとすれば，起こらない確率はｑ＝１－ｐです。このとき，Ａが起こったとすれば，その情報量は－logｐ，起こらなかったとすれば，その情報量は－logｑです。それで，全体の情報量の期待値は， 　　　Ｈ＝－ｐlogｐ－ｑlogｑ となります。このようなＨのことをエントロピーといいます。

• 確率分布の情報量をエントロピーとよぶ。

  確率分布（ｐ１，ｐ２，・・・，ｐｎ）が与えられたとき，この系のエントロピーＨは，
  　　　Ｈ＝－ｐ１logｐ１－ｐ２logｐ２・・・－ｐｎlogｐｎ
  である。

Claude Shannon in 1948

In information theory, entropy is the measure of the amount of information that is missing before reception and is sometimes referred to as Shannon entropy. Shannon entropy is a broad and general concept which finds applications in information theory as well as thermodynamics. It was originally devised by Claude Shannon in 1948 to study the amount of information in a transmitted message. The definition of the information entropy is, however, quite general, and is expressed in terms of a discrete set of probabilities

　　　Ｈ(x)＝－ｐ１logｐ１－ｐ２logｐ２・・・－ｐｎlogｐｎ,

The entropy, H, of a discrete random variable X is a measure of the amount of uncertainty associated with the value of X.

In the case of transmitted messages, these probabilities were the probabilities that a particular message was actually transmitted, and the entropy of the message system was a measure of how much information was in the message. For the case of equal probabilities (i.e. each message is equally probable), the Shannon entropy (in bits) is just the number of yes/no questions needed to determine the content of the message.

エントロピー最大とは

例題を考えます。消費者が、AとBの商品を、何の情報もなく選択する確率は、半々でしょう。 2個から1個を選ぶ確率分布のエントロピーは， 　　　Ｈ＝－ｐlogｐ－（１－ｐ）log（１－ｐ） となりますが，ｐ＝０.５（ｑ＝０.５）のときに最大になります。

• これをベルヌーイ試行のエントロピーと呼ぶ。
  

このように、エントロピー最大となる確率は、情報量によって異なりますが、自然の状態はエントロピー最大の分布が現れると考えます。

• 分散一定で、エントロピーが最大となる分布は？
  • 答え：正規分布です。証明してください。

１因子情報路による選択の問題

''制約条件下でエントロピーを最大化する問題をエントロピー・モデルとよぶ。 特に価格などひとつの因子を与えて構成比を求める場合は、⼀因⼦情報路モデル呼ぶ。'' 問題です。

消費者が全然知識のない商品ＡとＢがあり，Ａの価格は２００円，Ｂの価格は１００円とします。
商品ＡとＢの販売比率ｐ，ｑ（＝１－ｐ）を求めなさい。

この場合、

消費者は消費金額をできるだけ少なくし、エントロピーが最大になるような、購入分布になる

と考えるのが、自然でしょう。何せ、自然な状態は、エントロピー最大ですから・・・。

そこで

エントロピー/費用＝L＝H/C　--->最大化
Ｈ＝－Plogp　+　(1-p)log(1-p)　
費用の期待値：Ｃ＝２００ｐ＋１００(1-p)

を行いましょう。

この問題は

L=(plogp+qlogq)/(2p+q)--->MAX
subject to p+q=1

ラグランジェの未定定数法で、未定乗数をλとして

∂ {H/c+λ(p+q-1)} / ∂p=0,
∂ {H/C+λ(p+q-1)} / ∂q=0,

を解けばよい。

(∂H/ ∂p・c- ∂ c/∂p ・H)/c^2+λ ={-(log p+loge)l-2H}/C^2+λ=0,

となり、これを解いて、 log p=-log e-2H/c+λc, log q=-log e-H/c+λc となるので、

p log p+q log q=-log e-H+λc。

これより、λ=loge/lとなり、これを代入すると、 p=2^(-2H/c), q=2^(-H/c) となる。ここで、2^(-H/c)=Xとおけば、 　p=ｘ＾2, q=ｘ^1 となる。 いま、p+q=1であるから、

ｘ^2 +ｘ^1=1

となる。

X^2 +X=1 を解いてｘを求め、p=ｘ＾2, q=ｘ^1　を求められる。

• 例題の場合：Ｘ＝０.６１８となるので、ｑが62%、pが38%購入されることになる。

１因子情報路での多数選択の手順

ｎ個の銘柄があり，その特性（価格）がｃ１，ｃ２，・・・，ｃｎであるとき，
　　Ｘ^ｃ１＋Ｘ^ｃ２＋・・・＋Ｘ^ｃｎ＝１
の根をＸ（０＜Ｘ＜１）とすれば，
ｎ個の銘柄の分散確率（販売比率），ｐ１，ｐ２，・・・，ｐｎは，
　　ｐ１＝Ｘ^ｃ１，　ｐ２＝Ｘ^ｃ２，　・・・，　ｐｎ＝Ｘ^ｃｎ
で求められる。

逆一因子情報路の問題

これは、確率を与えて、因子の値をどうすればよいかを求める問題である。

• 例題：仕事の参加者は、仕事の効用（主として「給与＋つらさ」としましょう）で、どの仕事に就きたがるかが決まるとしましょう。現在、２つの仕事の給与が同じなのに、選択比率で1:4で得られている時、これを半々の人気にするには、いくら給与を上げなければいけないでしょうかという問題。

天秤問題：情報量の問題

ここにありました。解法が見つかれば、答えをお知らせしましょう。

［第一問］ここに８個の金貨があり、そのうち一つだけがとてもよく出来た偽造品で、他の金貨よりわずかに軽いことだけが分かっています。天秤を使ってどの偽造品を見つけ出したいのですが、天秤を一回使用するたびにお金がかかるので、出来るだけ最小の手数で偽造品を見つける必要があります。どうしたら良いでしょう。

［第二問］上の問題と同じ（他の金貨よりわずかに軽い偽造品が一つだけ混ざっている）条件で４回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るでしょう。

［第三問］今度は少し条件を変えて、偽造品は「本物と少し重さが違う」ことは分かっているのですが、重いのか軽いのかは不明だとします。この場合、３回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るか予想してみてください。

［第四問］第三問で予想した数の金貨の中から、天秤を３回だけ使って「本物と少し重さが違う」偽造品を見つける手順を示してください。

［第五問］（心理学の問題）第一問で、私が金貨の数を９個ではなく８個としたのはどうしてでしょう。

［第六問］（情報科の学生のみ）天秤を一度使うごとに、ある一定の「情報」が得られるのですが、その情報量は何ビットでしょうか。

• 参考：天秤は、「右が重い」「左が重い」「同じ重さ」の3種類の情報を出しますから、一回の計量で天秤の出す情報量は　log2(3)です。
• 例題：12枚の金貨があり、このうち1枚が重さが異なる偽金貨です。これを見つけ出し重いか軽いか確認するのに最低何回天秤に乗せる必要があるか。[Log2(12)+1]/log2(3)=4.585/1.485＝2.9　なので、答えは3回です。軽いか思いかが判っていれば簡単で、27個のボールまでみつけることができる。金貨が重い（または軽い）と判っているとき、これを突き止めるに必要な情報量は log2(27)/log2(3) = 3 シャノンだから、 3回の秤量で27個の金貨を区別できる可能性があり、実際に解が存在する。与えられた金貨を三つのグループに等分すれば，一回の操作で偽物が含まれるグループが一つに特定されることからわかります．(三分法)

• 参考：天秤と金貨