H = - i = 1 \sum n p_{i} lo g_{2} p_{i}

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

Shannon entropy

「エントロピーと呼べば議論で負けない」と勧められたという。

起こりうる結果の確率から、知らせ 1 つが平均で運ぶ情報の量を測る。圧縮できる限界を決め、通信・暗号・機械学習の土台になった。

年代: 1948年
人物: クロード・シャノン、ジョン・フォン・ノイマン、ラルフ・ハートレー、ジョン・テューキー

数学情報科学物理学生物学言語学

逸話

名前の由来

1948 年、ベル研究所のクロード・シャノンは、知らせが運ぶ「情報の量」を 1 つの式で測る方法を発表した。式はできた。残ったのは、この量を何と呼ぶかだった。

よく知られた話がある。シャノンは初め「情報」と呼ぶことを考えたが、使われすぎた言葉だと思ってやめた。次に「不確かさ」を考えた。そこへ数学者ジョン・フォン・ノイマンが、もっと良い名前を勧めた。「エントロピーと呼びなさい。理由は 2 つある。まず、あなたの不確かさの関数は、統計力学ですでにその名前で使われている。もう 1 つのほうが大事だ。エントロピーが本当は何なのか、誰もよく分かっていない。だから議論になれば、いつもあなたが有利になる」。

この話を広めたのは、熱力学の研究者マイロン・トライバスである。トライバスは 1961 年にシャノン本人から聞いたとして、1971 年に『サイエンティフィック・アメリカン』の記事「エネルギーと情報」(マキャーヴィンとの共著)で紹介した。シャノン自身の論文や本には、この会話は出てこない。

シャノン本人は、のちにこの話を打ち消している。1984 年に載ったロバート・プライスとの対談で、フォン・ノイマンから名前をもらったのかと問われ、「そうは思わない。フォン・ノイマンと私の間でそういうことは無かったと、かなり確信している」と答えた。プライスはその席で、シャノンが 1945 年の暗号の報告書ですでに「エントロピー」という言葉を使い、統計力学になぞらえていたことも指摘している。トライバスの記憶とシャノンの記憶のどちらが正しいのかは、分かっていない。

一方で、1948 年の論文には、シャノン自身の言葉でこう書いてある。この $H$ の形は、統計力学のある定式化で使われるエントロピーと同じ形であり、たとえばボルツマンの有名な $H$ 定理の $H$ である。つまりシャノンは、名前をもらう前から、物理学のエントロピーとの似かたに気づいていた。

同じ論文には、もう 1 つの名づけが記録されている。2 を底とする対数で測った単位を、シャノンは「2 進数字(binary digits)、短くしてビット(bits)」と呼び、この言葉は統計学者ジョン・テューキーの提案だと書き添えた。いまコンピュータの記憶の大きさを数えるビットという言葉が論文に載ったのは、これが最初とされる。

起源

情報を数で測ろうとした人は、シャノンの前にもいた。ベル研究所のハリー・ナイキストは 1924 年に、電信で送れる速さが、使える信号の種類の数の対数で決まることを示した。同じくベル研究所のラルフ・ハートレーは 1928 年の論文「情報の伝送」で、 $s$ 種類の記号を $n$ 個並べた知らせの情報の量を $n lo g s$ とした。ハートレーの量は、どの記号も同じように出てくるときにしか使えなかった。

シャノンは戦争中、ベル研究所で暗号と通信の研究をしていた。1945 年には、秘密の報告書「暗号の数学的理論」をまとめている(公開版は 1949 年の「秘密通信系の通信理論」)。暗号を破ることも、雑音の中から信号を取り出すことも、「相手にとって何が予想できないか」を測る問題だった。

1948 年 7 月と 10 月、シャノンは『ベル・システム技術雑誌』に 2 回に分けて「通信の数学的理論」を発表した。記号 $i$ が確率 $p_{i}$ で出てくる情報源について、記号 1 つあたりの平均の情報量を $H = - \sum p_{i} lo g p_{i}$ と定めた。確率がそろっていればハートレーの量に戻り、かたよっていれば小さくなる。

この論文は、 $H$ に 2 つの意味を与えた。1 つは、知らせを 0 と 1 の列に書き直すとき、1 記号あたり平均で $H$ ビットより短くはできず、 $H$ ビットにはいくらでも近づけられること(情報源符号化定理)。もう 1 つは、雑音のある通信路にも越えられない速さの上限(通信路容量)があり、それより遅ければ誤りをいくらでも小さくできること(通信路符号化定理)である。

翌 1949 年、論文はウォーレン・ウィーバーの解説を加えて本になった。題は『通信の数学的理論』で、論文の題の「ある(A)」が「その(The)」に変わっていた。

証明

シャノンは論文の付録で、 $H$ の形が 3 つの条件だけから決まることを示した。条件は次のとおり。(1) $H$ は確率 $p_{i}$ について連続である。(2) $n$ 個の結果が同じ確率 $1/ n$ のとき、その値 $A (n)$ は $n$ が増えるほど大きい。(3) 1 回の選択を 2 段階に分けてもよい。そのとき元の $H$ は、各段階の $H$ に、その段階に進む確率をかけて足したものに等しい。

同じ確率の $s^{m}$ 通りからの選択は、 $s$ 通りからの選択を $m$ 回くり返すことに分けられる。条件 (3) から
$A (s^{m}) = m A (s)$
同じく、どんな $t$ と $n$ についても $A (t^{n}) = n A (t)$ である。 $n$ を大きく取り、 $s^{m} \leq t^{n} < s^{m + 1}$ となる $m$ を選ぶ。対数を取って $n lo g s$ で割ると
$\frac{m}{n} \leq \frac{lo g t}{lo g s} < \frac{m}{n} + \frac{1}{n}$
条件 (2) から $A (s^{m}) \leq A (t^{n}) \leq A (s^{m + 1})$ 。手順 1 の形に直して $n A (s)$ で割ると
$\frac{m}{n} \leq \frac{A ( t )}{A ( s )} \leq \frac{m}{n} + \frac{1}{n}$
手順 2 と 3 の 2 つの量は、幅 $1/ n$ の同じ区間に入る。 $n$ はいくらでも大きくできるので、2 つは等しい。 $K = A (s) / lo g s > 0$ と置けば
$A (t) = K lo g t$
次に、確率が有理数 $p_{i} = n_{i} / N$ の場合を考える。同じ確率の $N$ 通りからの選択を、「まず $i$ 番目の組を確率 $p_{i}$ で選び、次に組の中の $n_{i}$ 通りから選ぶ」と 2 段階に分ける。条件 (3) から
$K lo g N = H (p_{1}, \dots, p_{k}) + K i \sum p_{i} lo g n_{i}$
$\sum_{i} p_{i} = 1$ を使って $K lo g N = K \sum_{i} p_{i} lo g N$ と書き直し、移項する。
$H = - K i \sum p_{i} lo g \frac{n _{i}}{N} = - K i \sum p_{i} lo g p_{i}$
確率が無理数の場合は、条件 (1) の連続性で有理数の場合から近づければよい。 $K = 1$ 、対数の底を 2 に取ったときの単位がビットである。
$H = - i \sum p_{i} lo g_{2} p_{i}$

$H$ がいちばん大きくなるのは、すべての $p_{i}$ が $1/ n$ のときで、その値は $lo g_{2} n$ である。確率がかたよるほど、次に何が来るか当てやすくなり、 $H$ は小さくなる。

応用

硬貨とさいころ。 表と裏が半々の硬貨を 1 回投げた結果は、ちょうど 1 ビットの情報を運ぶ。6 つの目が同じ確率のさいころは $lo g_{2} 6 \approx 2.585$ ビットである。「20 の質問」の遊びで、はい・いいえで答える質問を 20 回すれば、 $2^{20} = 1, 048, 576$ 通りの中から 1 つを言い当てられる。

天気予報。 雨の確率が 10% の日の「降った・降らない」は、 $H = - 0.1 lo g_{2} 0.1 - 0.9 lo g_{2} 0.9 \approx 0.469$ ビットしか情報を運ばない。ほとんど降らないと分かっている日に「今日も降らなかった」と聞いても、驚きは小さい。驚きの量は、その結果の確率を $p$ として $- lo g_{2} p$ で測られ、その平均が $H$ である。

圧縮。 4 つの記号が確率 $1/2, 1/4, 1/8, 1/8$ で出てくるとき、 $H = 1.75$ ビットである。符号を 0、10、110、111 と決めると、1 記号あたりの平均の長さもちょうど 1.75 ビットになる(図示)。よく出る記号ほど短い符号を割り当てるこの作り方は、1952 年にデイヴィッド・ハフマンが最良の方法を示し、いまも ZIP や JPEG の中で使われている。

合言葉の強さ。 英小文字 26 種類から 1 文字ずつ無作為に選んだ 8 文字の合言葉は、 $8 lo g_{2} 26 \approx 37.6$ ビットである。キーボードで打てる 94 種類の文字から 12 文字を無作為に選べば、 $12 lo g_{2} 94 \approx 78.7$ ビットになる。1 ビット増えるごとに、総当たりで試す数は 2 倍になる。人が覚えやすい言葉を選ぶと確率がかたよるので、実際の $H$ はこの値よりずっと小さい。

図示

2 通りの結果の一方が確率 p で起こるときのエントロピー。p = 0.5 で最大の 1 ビット、p が 0 か 1 に近づくと 0 になる。雨の確率 10% の日は 0.47 ビット。

確率 1/2・1/4・1/8・1/8 の 4 つの記号に、木の枝をたどって 0 と 1 の符号を付ける。平均の長さは 1.75 ビットで、エントロピーと一致する。

シミュレーション

棒の上の端をドラッグすると、その記号の確率が変わり、ほかの棒は合計が 1 になるように伸び縮みする。下の帯には、この確率で引いた記号が流れてくる。帯の高さは、その記号の驚き $- lo g_{2} p$ ビットである。驚きの平均(実線)は、引く回数が増えるほど $H$ (点線)に近づく。確率をそろえると $H$ は最大になり、1 つに集めると 0 に近づく。

広がる学問

情報科学 圧縮の限界を決めるほか、機械学習では予測の外れ具合を測る「交差エントロピー」が、分類や言語モデルの学習で最小化される量として使われる。決定木は、エントロピーが最も減る質問から順に枝を作る。
物理学 統計力学のエントロピー $S = - k \sum p_{i} ln p_{i}$ と同じ形である(ボルツマンのエントロピー)。ランダウアーは 1961 年、1 ビットの情報を消すには少なくとも $k T ln 2$ の熱が出ると論じた。室温で約 $2.9 \times 1 0^{- 21}$ J である。
生物学 生態学では、種ごとの個体の割合からシャノンの多様度指数を計算し、森や海の生き物の多様さを比べる。DNA の 1 文字は 4 種類なので、最大で 2 ビットの情報を持つ。
言語学 シャノンは 1951 年、人に英文の続きを 1 文字ずつ当てさせる実験で、英語の 1 文字あたりのエントロピーを 0.6〜1.3 ビットと見積もった。26 文字が同じ確率なら 4.7 ビットなので、英語は先を読みやすい言葉だと分かる。
数学確率論では、2 つの分布の違いを測るカルバック・ライブラー情報量など、 $H$ から派生した量が使われる。対数の性質 $lo g (ab) = lo g a + lo g b$ のおかげで、独立な 2 つの知らせの情報量は足し算になる(対数の法則)。

参考文献

C. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal 27 (1948), 379-423, 623-656.
C. E. Shannon, W. Weaver, The Mathematical Theory of Communication, University of Illinois Press, 1949.(植松友彦訳『通信の数学的理論』ちくま学芸文庫、2009)
R. V. L. Hartley, "Transmission of Information", Bell System Technical Journal 7 (1928), 535-563.
M. Tribus, E. C. McIrvine, "Energy and Information", Scientific American 225(3) (1971), 179-188.
R. Price, "A Conversation with Claude Shannon: One Man's Approach to Problem Solving", IEEE Communications Magazine 22(5) (1984), 123-126.
C. E. Shannon, "Prediction and Entropy of Printed English", Bell System Technical Journal 30 (1951), 50-64.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE 40 (1952), 1098-1101.

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

名前の由来

起源

証明

応用

図示

シミュレーション

広がる学問

参考文献

タグ

この公式のニュース

同じタグを持つ公式

姉妹サイト