情報理論

提供: miniwiki
移動先:案内、検索

情報理論（じょうほうりろん、英: Information theory）は、情報・通信を数学的に論じる学問である。応用数学の中でもデータの定量化に関する分野であり、可能な限り多くのデータを媒体に格納したり通信路で送ったりすることを目的としている。情報エントロピーとして知られるデータの尺度は、データの格納や通信に必要とされる平均ビット数で表現される。例えば、日々の天気が3ビットのエントロピーで表されるなら、十分な日数の観測を経て、日々の天気を表現するには「平均で」約3ビット/日（各ビットの値は 0 か 1）と言うことができる。

情報理論の基本的な応用としては、ZIP形式（可逆圧縮）、MP3（非可逆圧縮）、DSL（伝送路符号化）などがある。この分野は、数学、統計学、計算機科学、物理学、神経科学、電子工学などの交差する学際領域でもある。その影響は、ボイジャー計画の深宇宙探査の成功、CDの発明、携帯電話の実現、インターネットの開発、言語学や人間の知覚の研究、ブラックホールの理解など様々な事象に及んでいる。

概要

情報理論の基本となる概念は人間のコミュニケーション手段として最も広く使われている「言語」である。言語に関する重要な2つの観点がある。第1に、最もよく使われる単語（例えば、「日」、「私」、「それ」）はそれほど使われない単語（例えば、「唯々諾々」、「開口一番」、「対馬海流」）よりも短く、結果として文はそれほど長くならない。このような単語長のトレードオフはデータ圧縮に通じるものがあり、情報源符号化の基盤となっている。第2に、自動車が通りかかったなどのノイズのために文の最初の方を聞き逃しても、聞いていた人はメッセージの言わんとするところを理解できる（場合もある）。そのような言語の堅牢性は電気通信システムの基本であり、通信におけるその種の堅牢性を構築するのが通信路符号化である。情報源符号化と通信路符号化は情報理論の基礎となる概念である。

情報源符号化と通信路符号化では、メッセージの内容の重要性を全く考慮していない。例えば、「またおいでください」という決まり文句と、緊急時の叫び「救急車を呼んでくれ!!」は長さは似たようなものだが、その内容の重要性はかなり異なる。情報理論では、メッセージの重要性や意味には立ち入らない。すなわち、データの質は扱わず、確率論的に扱えるデータの量だけを扱う。

情報理論は、1948年、クロード・シャノンが Bell System Technical Journal に投稿した論文 "A Mathematical Theory of Communication"（通信の数学的理論）を始まりとする。古典的情報理論の中心パラダイムは、ノイズの多い通信路上で情報を転送する際の技術的問題であった。最も基本的な成果はシャノンの情報源符号化定理であり、ある事象を表現するために必要となる平均「ビット」数はその情報エントロピーであるとされた。また、シャノンの通信路符号化定理では、ノイズの多い通信路で信頼できる通信を行えることが示され、その際の転送レートの上限を通信路容量と称した。実際の通信速度を通信路容量に近づけるには、適切な符号化が必要となる。

情報理論は、過去半世紀の間に工学の手法として定着するまでになった様々な分野と密接に関連している。それは、人工知能、複雑系、サイバネティックス、情報学、機械学習、システム工学などである。情報理論は数学理論としても深遠であり、その応用も幅広い。その中でも特に符号理論は広く応用されている。

符号理論は、具体的な「符号」の方式を確立する分野であり、効率を上げ、エラー発生率をシャノンが定式化した通信路容量のレベルに近づけることを研究する分野である。符号は、データ圧縮（情報源符号化）と誤り検出訂正（通信路符号化）が主要な技法である。後者については、シャノンの研究のとおりの方式が可能であると証明するまで長い年月を要した。情報理論の符号に関する第3の技法は暗号化アルゴリズムである。符号理論や情報理論の成果は暗号理論や暗号解読に広く応用されている。

情報理論は、情報検索、諜報活動、賭博、統計学、さらには作曲にまで使われている。

歴史的背景

1948年6月と10月、クロード・シャノンは Bell System Technical Journal 誌で古典的論文 "A Mathematical Theory of Communication" を発表し、情報理論を学問分野として確立し、世界的な注目を浴びた。

この論文以前、ベル研究所で考えられていた情報の理論は限定的であり、あらゆる事象が同じ確率で発生することを暗黙の前提としていた。1924年、ハリー・ナイキストの論文 Certain Factors Affecting Telegraph Speed（テレグラフの速度を制限する要因）では、通信システムにおける「情報; intelligence」と「回線速度」の定量化に関する理論が述べられている。それによると、情報の転送速度 W は [math]W = K \log m[/math] で表され、m は選択可能な電圧レベル数、K はある定数である。1928年、ラルフ・ハートレーの論文 Transmission of Information（情報の伝送）では、測定可能な量として「情報; information」という用語が使われている。その中で情報の定量化は [math]H = \log S^n = n \log S[/math] で表され、S は文字の種類数、n は伝送された文字数であるとした。後に十進の情報量を表す単位をハートレー（Hartまたはhartley）と呼ぶようになった。1940年、アラン・チューリングは、第二次世界大戦時のドイツ軍の暗号統計解析の一部として同様の考え方を使った。

確率の異なる事象群を扱う情報理論の基礎となる数学は、ルートヴィッヒ・ボルツマンとウィラード・ギブスによる統計力学からもたらされた。情報理論におけるエントロピーと熱力学におけるエントロピーは単なる用語の類似以上の関連がある（ランダウアーの原理参照）。

シャノンの革新的論文については、ベル研究所での研究で1944年末ごろには実際の研究はほとんど済んでいた。シャノンの理論は情報理論の基礎となる静的プロセスとしての通信のモデルを提案し、論文冒頭で次のように表明している。

「通信の基本的課題は、ある地点で選択されたメッセージを正確または近似的に別の地点で再生することである」

それと共に次のような概念が提唱された。

情報に関する数学的理論

"「情報量」"

情報の数学的理論は確率論と統計学に基づいている。最も重要な情報の定量的尺度はエントロピーと伝達情報量である。エントロピーは確率変数の情報の尺度であり、メッセージの圧縮しやすさの度合いである。伝達情報量は2つの確率変数間に共通する情報の尺度であり、通信路における通信速度を決定するのに使われる。

以下の式に出てくる対数の底は、情報エントロピーの単位を決定するのに使われる。現在最も一般に使われている情報の単位はビットであり、2を底とする対数に基づいている。そのため通常、底は 2 とみなされる。さらに、通常定義されない [math]0 \log 0 \,[/math] を 0 とする。

エントロピー

ファイル:Binary entropy plot.png
ベルヌーイ試行のエントロピーを成功確率の関数 [math]H_\mbox{b}(p)[/math] として表したもの。2値エントロピー関数と呼ばれる。エントロピーは1ビットの成功確率が1/2であるときに最大となる。例えば細工のないコイントスなど。

離散確率変数 [math]M[/math] のエントロピー [math]H[/math] とは、[math]M[/math] の値の不確かさの尺度である。ここでの「ビット」の定義は重要である。例えば、通常の感覚（0 と 1）で 1000 ビットを転送するとしよう。事前にそのビット群の内容（0 と 1 の送信順序）がわかっている場合、論理的には通信によって得られる情報はゼロである。逆に個々のビットが 0 なのか 1 なのか五分五分の確率であった場合（かつビット間に相互の関連が存在しない場合）、1000 ビットで得られる情報は最大となる。これらの中間で、情報の定量化は次のように表される。[math]\mathbb{M}\,[/math] を確率変数 [math]M[/math] の発するメッセージ [math]m[/math] の集合とし、[math]p(m)=Pr(M=m)[/math] としたとき、[math]M[/math] のエントロピーは次のようになる（単位はビット）。

[math] H(M) = \mathbb{E}_{M} [-\log p(m)] = -\sum_{m \in \mathbb{M}} p(m) \log p(m)[/math]

エントロピーの重要な特徴として、メッセージ空間内の全メッセージが全て同じ確率でありうる場合に（つまり最も予測が難しい場合）、エントロピー値が最大の [math]H(M) = \log |\mathbb{M}|[/math] となる。

関数 H を確率分布で表すと次のようになる:

[math]H(p) = -\sum_{i=1}^k p(i) \log p(i),[/math]　　ここで [math] \sum_{i=1}^k p(i) = 1 [/math]

これの重要かつ特殊な場合を2値エントロピー関数と呼び、次のようになる:

[math]H_\mbox{b}(p) = H(p, 1-p) = - p \log p - (1-p)\log (1-p)\,[/math]

2つの離散確率変数 [math]X[/math] と [math]Y[/math] の結合エントロピーとは、単にその組 [math](X, Y)[/math] のエントロピーである。例えば、[math](X,Y)[/math] がチェスの駒の位置を表すとする。[math]X[/math] が行、[math]Y[/math] が列を表すとすると、その結合エントロピーとは、駒の位置のエントロピーを表す。数学的には次のようになる。

[math]H(X, Y) = \mathbb{E}_{X,Y} [-\log p(x,y)] = - \sum_{x, y} p(x, y) \log p(x, y) \,[/math]

[math]X[/math] と [math]Y[/math] が独立なら、結合エントロピーは単純に個々のエントロピーの総和となる。類似の概念として交差エントロピーがあるが、違うものである。

[math]Y=y[/math] のときの [math]X[/math] の条件付きエントロピーとは、[math]Y=y[/math] が既知であるときの [math]X[/math] のエントロピーである。前述の例で言えば、列が決まっているときの駒の行位置のエントロピーとなる。[math]Y=y[/math] のときの [math]X[/math] の条件付きエントロピーは次のようになる:

[math] H(X|y) = \mathbb{E}_{{X|Y}} [-\log p(x|y)] = -\sum_{x \in X} p(x|y) \log p(x|y)[/math]

ここで [math]p(x|y)[/math] は、ある [math]y[/math] に関する [math]x[/math] の条件付き確率である。

確率変数 [math]Y[/math] における [math]X[/math] の条件付きエントロピーとは、[math]Y[/math] についての平均条件付きエントロピーであり、次のようになる:

[math] H(X|Y) = \mathbb E_Y \{H(X|y)\} = -\sum_{y \in Y} p(y) \sum_{x \in X} p(x|y) \log p(x|y)[/math]
[math] = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(y)}[/math]

これを [math]Y[/math] に関する [math]X[/math] のあいまい度とも呼ぶ。このように条件付きエントロピーには、確率変数についての定義と、それが特定の値の場合の定義があるので、混同しないこと。これらのエントロピーには次の関係が成り立つ。

[math] H(X|Y) = H(X,Y) - H(Y) \,[/math]

伝達情報量などの情報定量化

もう1つの重要な情報の尺度として伝達情報量（相互情報量とも呼ぶ）がある。これは、ある確率変数を観測することによって別の確率変数について得られる情報量の尺度である。これは通信において重要な概念であり、妥当な通信量を決定するのに使われる。[math]Y[/math] との関連での [math]X[/math] の伝達情報量（概念的には [math]Y[/math] を観測することで得られる [math]X[/math] に関する情報量を意味する）は次のように表される:

[math]I(X;Y) = \sum_{y\in Y} p(y)\sum_{x\in X} p(x|y) \log \frac{p(x|y)}{p(x)} = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)\, p(y)}[/math]

伝達情報量の基本特性は次の式で表される:

[math]I(X;Y) = H(X) - H(X|Y)\,[/math]

この意味は、Y を知っていれば、知らない場合よりも X の符号化で平均して [math]I(X; Y)[/math] ビット節約できることを意味する。伝達情報量は対称的であるため、次のようにも表せる:

[math]I(X;Y) = I(Y;X) = H(X) + H(Y) - H(X,Y)\,[/math]

関連する尺度として、自己情報量、自己相互情報量(PMI)、カルバック・ライブラー情報量、差分エントロピーなども情報理論では重要である。

通信路容量

ファイル:Channel Concept Diagram.png
通信路の概念図
"「シャノンの通信路符号化定理」"

イーサネットなどの通信路上の通信が情報理論構築の主な動機である。電話を使ったことのある人なら誰でも経験することだが、そのような通信路では正確な信号の再現に失敗することもよくあり、ノイズや一時的な信号の途絶などにより信号が識別不能となることがある。そのようなノイズの多い通信路でどれだけの情報を伝えることが期待できるだろうか？

離散的な通信路による通信を考える。X を転送されるメッセージの集合とし、Y をある一定時間内にその通信路経由で受信したメッセージの集合とする。ここで、[math]p(y|x)[/math] を x が送信されたときに y が受信される条件付き確率の分布関数とする。ここで、[math]p(y|x)[/math] がその通信路に固有の属性であるとする（この通信路のノイズの性質を表している）。この通信路での X と Y の同時分布は、我々がこの通信路に送り出すメッセージの周辺分布 [math]f(x)[/math] から求められる。この条件で通信できる情報量を最大化したい。この尺度となるのが伝達情報量であり、伝達情報量の最大値を通信路容量と呼んで次の式で表す:

[math] C = \max_{f} I(X;Y).\! [/math]

通信路容量は情報レート R（ここで R は記号ごとのビット数）による通信と次のような関係がある。R < C であるような情報レートで符号誤り率 ε > 0 である場合、十分大きな数 N について、コードの長さが N で情報レートが R 以上かつ誤り率が ε 以下となるような符号化アルゴリズムが存在し、非常に低い誤り率で通信を行える可能性がある。さらに R > Cであるような情報レートでは、低い誤り率で通信を行うことは不可能である。

特定通信路モデルでの通信路容量

ファイル:BinarySynmetricChannel.png
2元対称通信路
ファイル:BinaryErasureChannel.png
2元消失通信路
  • 連続的なアナログ通信路のノイズは主にガウス雑音である。シャノン・ハートレイの定理。
  • 2元対称通信路 (Binary Symmetric Channel, BSC)でバイナリ値の取り違えが発生する確率を p とする。BSCの通信路容量は [math]1 - H_\mbox{b}(p)[/math] ビットであり、ここで [math]H_\mbox{b}[/math] は2値エントロピー関数である。
  • 2元消失通信路 (Binary Erasure Channel, BEC) で消失が発生する確率を p とする。消失とは入力側が入力したバイナリ値が出力側に届かない状態であり、結果として出力側は 0 と 1 以外に e (erasure)という第3の状態をとる。BECの通信路容量は 1 - pビットである。

情報源理論

逐次的にメッセージを生成するプロセスは情報源と見なすことができる。メモリを持たない情報源の発するメッセージは互いに独立で同一の分布に従う確率変数であり、エルゴード性と定常性が特徴である。そのような情報源は常に確率的である。これらの用語は情報理論以外でよく研究されている。

レート

情報レート (rate) とは、記号ごとの平均エントロピーである。メモリを持たない情報源では、これは単に各記号のエントロピーを表すが、一般に次のような式で表される:

[math]r=\mathbb E H(M_t|M_{t-1},M_{t-2},M_{t-3}, \ldots).[/math]

正確に言えば、これは単位時間当たりの期待される条件付きエントロピーであり、それまでに生成されたメッセージ群から得られる。情報理論では、言語の「レート」や言語の「エントロピー」を扱うのも特別なことではない。例えば、ソースが英語の散文であった場合などにそのような言い方が出てくる。メモリのない情報源の情報レートは単に [math]H(M)[/math] となる。これは、メモリのない情報源では、それまでのメッセージ群と次のメッセージとの間に理論上何も関係がないためである。情報源の情報レートは、冗長性と圧縮の程度に関係する。

応用

符号理論

"「符号理論」"

符号理論は、情報理論の中でも最も重要かつ直接的な応用分野である。その領域は、情報源符号化理論（データ圧縮）と通信路符号化理論（誤り検出訂正）に大別される。データの統計的記述を用いて、符号化に必要とされるビット数（情報源の情報エントロピー）を定量化する。

  • データ圧縮（情報源符号化）: 圧縮方式は次の2つに分類される:
    1. 可逆圧縮: データの復元が正確に行われる
    2. 非可逆圧縮: 歪関数によって指定された忠実度レベルでデータを再現するために必要なビット数を割り当てる。この情報理論のサブセットをレート歪理論と呼ぶ。
  • 誤り訂正符号（通信路符号化）: データ圧縮によって可能な限り冗長性を排除する一方、誤り訂正符号を付与することで正しい性質の冗長性を導入し、ノイズのある通信路でデータを効率的かつ忠実に転送可能にする。

圧縮と転送に関する符号理論は情報理論に裏打ちされている。ただし、それは1対1の通信に関してのみである。発信者が複数の場合（複数アクセス通信路）、受信者が複数の場合（同報通信路）、仲介者がいる場合（リレー通信路）、それらの複合であるコンピュータネットワークなどについて、転送後の圧縮は最適とは言えないかもしれない。このようなマルチエージェント通信モデルを扱うのはネットワーク情報理論 (Network Information Theory) である。

諜報活動と秘密保持

情報理論の概念は、暗号理論や暗号解読でも広く使われている。シャノン自身、現在では判別距離と呼ばれている暗号理論上重要な概念を定義した。平文の冗長性に基づき、暗号文の復号で平文が一意に定まるのに必要な暗号文の量の下限を定めるものである。

擬似乱数生成

情報理論の応用例として、GPSの符号化方式での信号隠蔽がある。このシステムでは擬似乱数を使って信号をノイズフロアのレベル以下に抑えている。そのため、一般の電波受信者は信号があることにさえ気づかないが、秘密の擬似乱数列を使ってある期間の信号を積分することで信号を検出できる。GPSシステムでは、C/A信号は一般に公開されているが、P(Y)信号に使われている擬似乱数列は秘密とされている。同様の手法は短距離の秘密通信にも使われており、低電力で敵に気づかれずに通信が可能である。これはステガノグラフィーの一種とも言える。また、スペクトラム拡散通信も参照されたい。

その他の応用

情報理論のその他の応用として、ギャンブルや投資への応用、ブラックホールと情報のパラドックス、バイオインフォマティクス、音楽などがある。

参考文献

古典的論文

その他の論文

情報理論の教科書的書籍

  • 甘利俊一: 情報理論 筑摩書房（ちくま学芸文庫）, 2011. ISBN 978-4-480-09358-5
  • 今井秀樹: 情報理論 昭晃堂, 1984.
  • Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1949. ISBN 0-252-72548-4
  • Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
  • Robert B. Ash. Information Theory. New York: Interscience, 1965. ISBN 0-470-03445-9. New York: Dover 1990. ISBN 0-486-66521-6
  • Thomas M. Cover, Joy A. Thomas. Elements of information theory
    • 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.
    • 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
  • Stanford Goldman. Information Theory. New York: Prentice Hall, 1953. New York: Dover 1968 ISBN 0-486-62209-6, 2005 ISBN 0-486-44271-3
  • Fazlollah M. Reza. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
  • Raymond W. Yeung. A First Course in Information Theory Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7
  • David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
  • Masud Mansuripur. Introduction to Information Theory. New York: Prentice Hall, 1987. ISBN 0-13-484668-0

その他の書籍

  • James Bamford, The Puzzle Palace, Penguin Books, 1983. ISBN 0-14-006748-5
  • Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
  • A. I. Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. ISBN 0-486-60434-9
  • H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, NJ (1990). ISBN 0-691-08727-X
  • Tom Siegfried, The Bit and the Pendulum, Wiley, 2000. ISBN 0-471-32174-5
  • Charles Seife, Decoding The Universe, Viking, 2006. ISBN 0-670-03441-X

関連項目

応用

理論

概念

外部リンク


テンプレート:データ圧縮



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=情報理論&oldid=116670」から取得