エントロピーの解説
1948年、ベル研究所の技術者クロード・シャノンは、それまで誰も厳密に定式化していなかった問いを立てました。メッセージにはどれだけの情報が含まれているのか、という問いです。彼の答えはビットで測られる1つの数で、それはメッセージが何を意味するかではなく、どれだけ意外かによって決まります。エントロピーと呼ばれるこの数は、あらゆる圧縮プログラム、あらゆるネットワーク回線、あらゆる記憶装置の限界を定めています。そして、あるテキストは元の大きさのほんの一部まで縮むのに、別のテキストはまったく縮められない理由も説明してくれます。
情報とは驚きである
シャノンの洞察は、情報をメッセージの意味ではなく、それがどれだけ予想外かで測ることでした。答えをすでに知っているなら、それを聞いても何もわかりません。千通りのうちのどれでもありえたなら、多くのことがわかります。同じくらいありそうな2つの可能性から1つを特定するメッセージは1ビットを持ちます。4つから1つなら2ビット、8つから1つなら3ビットで、一般に、同じくらいありそうな N 通りの可能性から1つを特定するには log₂ N ビットが必要です。したがって、確率 p で現れる記号は −log₂ p ビットを持ちます。まれであるほど、多くを伝えるのです。
シャノンの公式
エントロピーは1記号あたりの平均情報量で、H = −Σ p log₂ p と表されます。和は、確率 p を持つすべての記号についてとります。公平なコインなら H は1ビットです。90%の確率で表が出るコインでは0.47ビットにすぎません。結果がたいてい意外ではないからです。エントロピーはすべての記号が同じくらいありそうなときに最大となり、n 個の記号なら log₂ n ビット、1つの記号が確実に現れるならゼロです。シャノンはジョン・フォン・ノイマンの助言に従ってこの名前を選びました。同じ公式が物理学にも現れ、そこではエントロピーが乱雑さを測るからです。
圧縮の限界
シャノンの情報源符号化定理によれば、どんな可逆符号も、1記号あたり平均で情報源のエントロピーより少ないビット数を使うことはできず、一方でいくらでもエントロピーに近づく符号は作れます。デイビッド・ハフマンが1952年、学生のときに考案したハフマン符号は、よく現れる記号に短い符号を、まれな記号に長い符号を割り当て、エントロピーとの差を1記号あたり1ビット以内に収めます。算術符号はさらに近づきます。つまりエントロピーは単なる記述ではなく、越えられない限界なのです。1バイトあたり8ビットのエントロピーを持つランダムなバイトのファイルは、まったく圧縮できません。
文脈と冗長性
テキストの文字は互いに独立ではありません。英語では、Q の次には U が来て、ピリオドの次は大文字で、INFORMA で始まる単語はほぼ確実に TION と続きます。直前の記号を考慮に入れると条件付きエントロピーが得られ、これは記号を1つずつ数えたときのエントロピーより低くなります。その差が冗長性、つまりメッセージのうち予測できたはずの部分です。deflate 方式を使う ZIP のような圧縮プログラムは、繰り返し現れる文字列を見つけて短い参照に置き換えます。現代の圧縮プログラムは、各記号をその文脈から予測します。
英語にはどれだけの情報があるのか
英語の文字頻度で1文字ずつ数えると、1文字は約4.1ビットを持ちます。ランダムに選んだ文字なら4.7ビットです。1951年、シャノンはさらに踏み込みました。人にテキストの冒頭を見せて次の文字を当ててもらい、何回で当たるかを数えたのです。その結果から、英語は1文字あたり約0.6〜1.3ビットしか持たないと見積もりました。言い換えれば、書かれた英語のおよそ4分の3は冗長性であり、だからこそ文字が抜けた英文でもたいてい読めるのです。
ランダム性とパスワード
エントロピーは予測できなさの尺度でもあり、セキュリティはまさにそれに依存しています。N 通りの可能性から一様に選ばれた鍵やパスワードは log₂ N ビットのエントロピーを持ち、攻撃者は平均してその約半分を試さなければなりません。26種類の小文字から作ったランダムな12文字のパスワードは約56ビットです。よくある単語は、どれほど長くてもそれよりはるかに少なくなります。乱数生成器は、その出力がランダムな情報源の完全なエントロピーを持つかどうかで検査され、オペレーティングシステムはタイミングのゆらぎからエントロピーを集めて乱数生成器のシードにしています。
エントロピーが現れるところ
エントロピーは、通話や写真や動画ストリームに何ビット必要か、そしてモデムや Wi-Fi の回線が通信路容量にどこまで近づけるかを決めます。生物学者は、4種類の塩基がそれぞれ最大2ビットを持てる DNA の情報量や、生態系の多様性を測るのに使います。機械学習では、決定木がエントロピーを最も減らす質問を選び、交差エントロピー損失がほとんどのニューラルネットワークを訓練しています。言語学者は、1文字あたりや1単語あたりのエントロピーで言語を比べます。
試してみよう
エントロピー計算機を開いて、どんなテキストでも文字、単語、バイトごとに測ってみましょう。段落をランダムな文字、ビット、数字、DNA と比べ、すべての記号の自己情報量、保存サイズに対するテキストの情報量、そして既知の文脈が増えるにつれて1記号あたりのビット数がどう下がるかを、ZIP の実際の結果と並べて見ることができます。
よくある質問
なぜエントロピーはビットで測るのですか?
シャノンが2を底とする対数を使い、同等な選択肢の間の「はい」か「いいえ」の選択1回が1単位になるようにしたからです。自然対数を使うと単位はナットで約1.44ビット、10を底とするとハートレーで約3.32ビットです。物理学者や一部の統計学者はこれらを使います。
テキストのエントロピーが文字の種類数の log₂ を超えることはありますか?
ありません。異なる記号が n 個なら、エントロピーは最大でも1記号あたり log₂ n ビットで、それに届くのはすべての記号が同じ頻度のときだけです。偏りがあれば、また文脈から予測できる部分があれば、エントロピーは下がります。
情報理論のエントロピーは物理学のエントロピーと同じものですか?
公式の形は同じです。ボルツマンとギブズは、物理的なエントロピーを系の微視的状態の確率についての和として書きました。意味も関連しており、どちらも自分がどれだけ知らないかを測っています。物理学者はその後、1ビットの情報を消去するとわずかな熱が必ず放出されることを示しました。
圧縮したファイルをさらに圧縮しても効果がないのはなぜですか?
良い圧縮プログラムは冗長性のほとんどを取り除くので、出力はランダムに近く、1バイトあたり8ビット近いエントロピーを持ちます。取り除くものはもう残っておらず、もう一度圧縮すると、圧縮プログラム自身のオーバーヘッドのためにふつうは少し大きくなります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エントロピー計算機を開く