🥇リチャード・ハミング: 第 13 章。情報理論

やった！

「このコースの目的は、技術的な将来に備えて準備することです。」

こんにちは、ハブル。素晴らしい記事を思い出してください「あなたとあなたの仕事」 (+219、2588 ブックマーク、429k 読み取り)?

それで、ハミング（はい、はい、自己監視と自己修正ハミングコード）全体があります книга、彼の講義に基づいて書かれています。この人は自分の考えを語っているので、私たちはそれを翻訳します。

これは単なるITに関する本ではなく、信じられないほどクールな人々の思考スタイルについての本です。 「それは単にポジティブ思考を高めるだけではありません。それは、素晴らしい仕事をする可能性を高める条件を説明しています。」

翻訳してくれた Andrey Pakhomov に感謝します。

情報理論は、1940 年代後半に C. E. シャノンによって開発されました。ベル研究所の経営陣は、それを「コミュニケーション理論」と呼ぶと主張しました。これはより正確な名前です。明白な理由から、「情報理論」という名前は一般大衆にはるかに大きな影響を与えており、それがシャノンがそれを選んだ理由であり、それは今日まで私たちが知っている名前です。名前自体は、この理論が情報を扱うことを示唆しており、情報化時代がさらに深く進むにつれ、この理論が重要になります。この章では、この理論から得られるいくつかの主な結論について触れます。「情報理論」が実際に何なのか、どこに適用できるのかを理解できるように、この理論のいくつかの個別の規定について厳密ではなく直感的な証拠を示します。そしてそうでないところ。

そもそも「情報」とは何でしょうか？シャノンは情報を不確実性と同一視します。彼は、確率 p のイベントが発生したときに受け取る情報の定量的尺度として、イベントの確率の負の対数を選択しました。たとえば、ロサンゼルスの天気は霧であると伝えると、p は 1 に近くなりますが、実際にはあまり情報が得られません。しかし、1 月のモントレーでは雨が降ると言った場合、メッセージには不確実性があり、より多くの情報が含まれることになります。ログ 0 = XNUMX であるため、信頼できるイベントには情報が含まれません。

これをさらに詳しく見てみましょう。シャノンは、情報の定量的尺度はイベントの確率 p の連続関数であるべきであり、独立したイベントの場合は加算的であるべきである、つまり 1 つの独立したイベントの発生の結果として得られる情報の量は、共同イベントの発生の結果として得られる情報の量。たとえば、サイコロの出目とコインの出目は通常、独立したイベントとして扱われます。上記を数学の言語に翻訳してみましょう。 I (p) が確率 p のイベントに含まれる情報量である場合、確率 p2 の XNUMX つの独立したイベント x と確率 pXNUMX の y からなる共同イベントについて、次の結果が得られます。

(x と y は独立したイベントです)

これは関数コーシー方程式であり、すべての p1 と p2 に当てはまります。この関数方程式を解くには、次のように仮定します。

p1 = p2 = p、

これは与える

p1 = p2 かつ p2 = p の場合、

等指数関数の標準的な方法を使用してこのプロセスを拡張すると、すべての有理数 m/n に対して次のことが当てはまります。

情報尺度の想定される連続性から、対数関数がコーシー関数方程式の唯一の連続解であることがわかります。

情報理論では、対数の底を 2 とするのが一般的であるため、1 値選択にはちょうど XNUMX ビットの情報が含まれます。したがって、情報は次の式で測定されます。

立ち止まって、上で何が起こったのかを理解しましょう。まず、「情報」という概念を定義したのではなく、その定量的な尺度を表す式を定義しただけです。

第 XNUMX に、この指標には不確実性があり、電話システム、ラジオ、テレビ、コンピュータなどの機械には合理的に適していますが、情報に対する人間の通常の態度は反映されていません。

第三に、これは相対的な尺度であり、現在の知識の状態によって異なります。乱数発生器からの「乱数」の流れを見ると、次の各数値は不確実であると想定しますが、「乱数」の計算式を知っていれば、次の数値は既知であるため、次の数値は不確実になります。情報が含まれています。

したがって、シャノンによる情報の定義は多くの場合、機械にとっては適切ですが、その言葉に対する人間の理解には適合していないようです。「情報理論」が「コミュニケーション理論」と呼ばれるべきだったのはこのためです。しかし、定義を変えるには遅すぎます（定義がこの理論に当初の人気を与え、今でもこの理論が「情報」を扱っていると人々に思わせています）。シャノンの情報の定義が、一般的に使用されている意味からどれだけ離れているかを明確に理解します。シャノンの情報はまったく異なるもの、つまり不確実性を扱っています。

用語を提案するときに考慮すべき点は次のとおりです。シャノンの情報の定義など、提案された定義はあなたの元のアイデアとどのように一致しますか?また、それはどのように異なりますか? 概念についてのこれまでのビジョンを正確に反映する用語はほとんどありませんが、最終的には使用される用語が概念の意味を反映するため、明確な定義を通じて何かを形式化すると、常にノイズが生じます。

アルファベットが確率 pi の記号 q で構成されるシステムを考えてみましょう。この場合 平均的な情報量 システム内の (期待値) は次と等しくなります。

これを確率分布 {pi} を持つ系のエントロピーと呼びます。私たちが「エントロピー」という用語を使用するのは、同じ数学的形式が熱力学と統計力学に現れるためです。これが、「エントロピー」という用語がそれ自体の周囲に重要なオーラを生み出す理由ですが、それは最終的には正当化されません。同じ数学的表記形式は、記号の同じ解釈を意味するものではありません。

確率分布のエントロピーは、符号化理論において重要な役割を果たします。 XNUMX つの異なる確率分布 pi と qi のギブス不等式は、この理論の重要な結果の XNUMX つです。したがって、それを証明しなければなりません

証明は明らかなグラフに基づいています。 13.I、これは次のことを示しています

そして等価性は x = 1 の場合にのみ達成されます。左辺から合計の各項に不等式を適用してみましょう。

通信システムのアルファベットが q 個のシンボルで構成されている場合、各シンボルの送信確率 qi = 1/q をとり、q を代入すると、ギブスの不等式から次のようになります。

図 13.I

これは、すべての q 個のシンボルを送信する確率が同じで - 1 / q に等しい場合、最大エントロピーは ln q に等しく、そうでない場合は不等式が成り立つことを意味します。

一意に解読可能なコードの場合、クラフトの不等式が成立します。

ここで擬似確率を定義すると

もちろんどこで = 1、ギブスの不等式から導かれる、

そして、少し代数を適用します (K ≤ 1 であることを思い出してください。そのため、対数項を削除し、後で不等式を強化することができます)、次のようになります。

ここで、L は平均コード長です。

したがって、エントロピーは、平均コードワード長 L の文字ごとのコードの最小限界です。これは、干渉のないチャネルに関するシャノンの定理です。

ここで、情報が独立したビットのストリームとして送信され、ノイズが存在する通信システムの制限に関する主定理を考えてみましょう。 1 ビットが正しく送信される確率は P > 2/1 であり、送信中にビット値が反転する (エラーが発生する) 確率は Q = XNUMX - P に等しいことがわかります。エラーは独立しており、送信された各ビットのエラーの確率は同じであると仮定します。つまり、通信チャネルには「ホワイトノイズ」が存在します。

n ビットの長いストリームを XNUMX つのメッセージにエンコードする方法は、XNUMX ビットコードを n 次元に拡張することです。 n の値は後で決定します。 n ビットで構成されるメッセージを n 次元空間内の点として考えてみましょう。 n 次元空間があるため、簡単にするために各メッセージの発生確率は同じであると仮定します。考えられるメッセージは M 個あり (M も後で定義します)、したがって、送信されるメッセージの確率は次のようになります。

(差出人)
スケジュール 13.II

次に、チャネル容量の考え方を考えてみましょう。詳細には立ち入りませんが、チャネル容量は、最も効率的なコーディングの使用を考慮して、通信チャネル上で確実に送信できる情報の最大量として定義されます。通信チャネルを通じて、その容量を超える情報を送信できることに異論の余地はありません。これは、バイナリ対称チャネル (このケースで使用) について証明できます。ビット送信時のチャネル容量は次のように指定されます。

ここで、前と同様に、P は送信されたビットにエラーがない確率です。 n 個の独立したビットを送信する場合、チャネル容量は次の式で与えられます。

チャネル容量に近い場合、各シンボル ai、i = 1、...、M に対してほぼこの量の情報を送信する必要があります。各シンボル ai の発生確率が 1 / M であると考えると、我々が得る

M 個の同じ確率のメッセージ ai のいずれかを送信すると、次のようになります。

n ビットが送信されると、nQ エラーが発生することが予想されます。実際には、n ビットで構成されるメッセージの場合、受信メッセージに約 nQ 個のエラーが発生します。 n が大きい場合、相対変動 (変動 = 分布幅、 )
n が増加するにつれて、エラー数の分布はますます狭くなります。

したがって、送信機側から、送信するメッセージ ai を受け取り、その周囲に半径のある球を描きます。

これは、予想されるエラー数 Q よりも e2 に等しい量だけわずかに大きくなります (図 13.II)。 n が十分に大きい場合、この球を超えてメッセージポイント bj が受信側に現れる確率は任意に小さくなります。送信側の観点から見た状況をスケッチしてみましょう。送信メッセージ ai から受信メッセージ bj までの任意の半径があり、誤差の確率は正規分布に等しく (またはほぼ等しく)、最大値に達します。 NQの。任意の e2 に対して、n が非常に大きいため、結果として得られる点 bj が私の球の外側にある確率は、好きなだけ小さくなります。

次に、同じ状況をあなたの側から見てみましょう (図 13.III)。受信側には、n 次元空間で受信した点 bj の周りに同じ半径 r の球 S(r) があり、受信したメッセージ bj が私の球の中にある場合、私が送信したメッセージ ai はあなたの球の中にあります。球。

どのようにしてエラーが発生するのでしょうか? 以下の表に示す場合にエラーが発生する可能性があります。

図 13.III

ここでは、受信したポイントの周囲に構築された球内に、送信された可能性のあるエンコードされていないメッセージに対応するポイントが少なくとも XNUMX つある場合、これらのメッセージのどれが送信されたかを判断できないため、送信中にエラーが発生したことがわかります。送信されたメッセージにエラーがないのは、それに対応する点が球内にあり、指定されたコード内に同じ球内に存在する可能性のある他の点がない場合のみです。

メッセージ ai が送信された場合のエラーの確率 Pe を表す数式があります。

第 1 項の最初の要素を XNUMX として破棄できます。こうして不等式が得られます。

明らかに、

したがって、

右側の最後の用語に再適用する

n を十分に大きくすると、最初の項を必要なだけ小さく、たとえばある数値 d より小さくすることができます。したがって、私たちは

次に、n ビットで構成される M 個のメッセージをエンコードするための単純な置換コードを構築する方法を見てみましょう。コードを正確に構築する方法がまったく分からなかった (誤り訂正コードがまだ発明されていなかった) シャノンは、ランダムコーディングを選択しました。メッセージ内の n ビットごとにコインを投げ、M 個のメッセージに対してこのプロセスを繰り返します。合計で nM 回のコイントスを行う必要があるため、

同じ確率 XNUMX/XNUMXnM を持つコード辞書。もちろん、コードブックの作成プロセスがランダムであるということは、コードポイントが重複する可能性があり、コードポイントが互いに近くにあるため、エラーの原因となる可能性があることを意味します。これが、選択した小さな誤差レベルよりも高い確率で発生しない場合、指定された n は十分に大きいことを証明する必要があります。
重要な点は、シャノンが考えられるすべてのコードブックを平均して平均誤差を見つけたことです。記号 Av[.] を使用して、考えられるすべてのランダムコードブックのセットの平均値を示します。もちろん、定数 d を平均すると定数が得られます。平均する場合、各項は合計の他のすべての項と同じになるからです。

これは増やすことができます (M–1 が M になります)

特定のメッセージについて、すべてのコードブックを平均する場合、エンコードはすべての可能な値にわたって実行されるため、点が球内に存在する平均確率は、空間の総体積に対する球の体積の比率になります。球の体積は、

ここで、s=Q+e2 <1/2、ns は整数でなければなりません。

右側の最後の項がこの和の中で最大になります。まず、階乗のスターリング公式を使用してその値を推定しましょう。次に、その前の項の係数が減少していることに注目します。この係数は左に移動するにつれて増加することに注意してください。したがって、次のことが可能になります。 (1) 合計の値を次の等比数列の合計に制限します。この初期係数を使用し、(2) 等比数列を ns 項から無限数の項に拡張し、(3) 無限等比数列の和を計算し (標準的な代数、重要なことは何もありません)、最後に限界値を取得します (十分に大きい場合)。 n):

エントロピー H(s) が二項恒等式にどのように現れるかに注目してください。テイラー級数展開 H(s)=H(Q+e2) は、一次導関数のみを考慮して他をすべて無視して得られる推定値を与えることに注意してください。それでは、最終的な式をまとめてみましょう。

どこ

私たちがしなければならないのは、e2 < e3 となるように e1 を選択することだけです。そうすれば、n が十分に大きい限り、最後の項は任意に小さくなります。その結果、C に任意に近いチャネル容量で、平均 PE 誤差を必要なだけ小さくすることができます。
すべてのコードの平均の誤差が十分に小さい場合は、少なくとも XNUMX つのコードが適切である必要があるため、少なくとも XNUMX つの適切なコーディングシステムが存在します。これはシャノンによって得られた重要な結果、つまり「ノイズの多いチャネルに関するシャノンの定理」ですが、彼はこれを、私が使用した単純な二値対称チャネルよりもはるかに一般的なケースに対して証明したことに注意する必要があります。一般的なケースでは、数学的な計算ははるかに複雑になりますが、考え方はそれほど変わらないため、特定のケースの例を使用すると、定理の本当の意味を明らかにできることがよくあります。

結果を批判しましょう。私たちは「十分に大きな n に対して」と繰り返してきました。しかし、n はどのくらいの大きさでしょうか? チャネル容量に近づけると同時に正しいデータ転送を確実に行いたい場合は、非常に大規模です。実際、非常に大きいため、後でエンコードするのに十分なビット数のメッセージを蓄積するには、非常に長い時間待機する必要があります。この場合、ランダムコード辞書のサイズは単純に巨大になります (結局のところ、n と M が非常に大きいという事実にもかかわらず、そのような辞書はすべての Mn ビットの完全なリストよりも短い形式で表すことはできません)。

エラー訂正コードは、コードブック自体を回避し、代わりに通常の計算を使用するため、非常に長いメッセージを待機したり、非常に大きなコードブックを介してメッセージをエンコードおよびデコードしたりすることを回避します。単純な理論では、このようなコードはチャネル容量に近づく能力を失いながらも低いエラー率を維持する傾向がありますが、コードが多数のエラーを訂正すると、パフォーマンスは良好になります。言い換えれば、一部のチャネル容量を誤り訂正に割り当てる場合、ほとんどの場合、誤り訂正機能を使用する必要があります。つまり、送信される各メッセージで多数の誤りを訂正する必要があり、そうでないとこの容量が無駄になります。

同時に、上で証明された定理はまだ無意味ではありません。これは、効率的な伝送システムでは、非常に長いビット列に対して賢明な符号化スキームを使用する必要があることを示しています。例としては、外惑星を越えて飛行した衛星が挙げられます。地球や太陽から遠ざかるにつれて、データブロック内のますます多くのエラーを修正する必要が生じます。一部の衛星は約 5 W を供給するソーラーパネルを使用し、他の衛星はほぼ同じ電力を供給する原子力発電を使用します。電源の低電力、地球上での送信ディッシュのサイズと受信ディッシュのサイズの制限、信号が到達しなければならない膨大な距離 - これらすべてを構築するには、高レベルの誤り訂正を備えたコードの使用が必要です。効果的なコミュニケーションシステム。

上の証明で使用した n 次元空間に戻りましょう。これについて議論する中で、球のほぼ全体の体積が外表面近くに集中していることを示しました。したがって、送信信号が受信信号の周囲に構築された球の表面近くに位置することはほぼ確実です。このような球の小さな半径。したがって、任意の多数のエラー nQ を訂正した後、受信信号がエラーのない信号に任意に近づくことが判明することは驚くべきことではありません。前に説明したリンク容量が、この現象を理解する鍵となります。誤り訂正ハミング符号用に構築された同様の球は互いに重なり合わないことに注意してください。 n 次元空間にほぼ直交する次元が多数存在することは、M 個の球をほとんど重なり合わずに空間に適合させることができる理由を示しています。デコード中に少数のエラーしか引き起こさない、任意の小さなオーバーラップを許容する場合、空間内に球を密に配置することができます。ハミングは、シャノンによる一定レベルのエラー訂正、つまりエラーの確率が低いことを保証しましたが、同時に実際のスループットを任意に通信チャネルの容量に近い値に維持しましたが、これはハミングコードでは不可能でした。

情報理論は効率的なシステムを設計する方法を教えてくれませんが、効率的な通信システムへの道を示します。これはマシン間の通信システムを構築するための貴重なツールですが、前述したように、人間が相互に通信する方法とはほとんど関連性がありません。生物学的遺伝が技術的な通信システムにどの程度似ているかはまったく不明であるため、情報理論が遺伝子にどのように適用されるかは現時点では明らかではありません。私たちには挑戦する以外に選択肢はありません。成功によってこの現象の機械的な性質が示された場合、失敗によって情報の性質の別の重要な側面が示されることになります。

あまり脱線しないようにしましょう。すべての元の定義は、多かれ少なかれ、私たちの元の信念の本質を表現している必要があるが、それらはある程度の歪みを特徴としており、したがって適用できないことを私たちは見てきました。最終的には、私たちが使用する定義が実際に本質を定義すると伝統的に受け入れられています。しかし、これは物事を処理する方法を示すだけであり、私たちに意味を伝えるものではありません。仮定に基づくアプローチは、数学界で非常に支持されていますが、実際にはまだ多くのことが望まれています。

ここで、定義が思い通りに循環的であり、その結果誤解を招く IQ テストの例を見てみましょう。知能を測定することを想定したテストが作成されます。その後、可能な限り一貫性を保つように改訂されてから出版され、測定された「知能」が正規分布するように（もちろん検量線上で）簡単な方法で校正されます。すべての定義は、最初に提案されたときだけでなく、ずっと後、導き出される結論に使用されるときにも再確認する必要があります。定義上の境界は、解決される問題に対してどの程度まで適切ですか? ある設定で与えられた定義が、まったく異なる設定に適用されることがどのくらいありますか? これはかなり頻繁に起こります! 人生で必ず遭遇する人文科学では、このようなことがよく起こります。

したがって、情報理論のこのプレゼンテーションの目的の XNUMX つは、その有用性を示すことに加えて、この危険性について警告すること、または望ましい結果を得るために情報理論を使用する方法を正確に示すことでした。最初の定義が、最終的に何が見つかるかを、見た目よりもはるかに大きく決定することは、長い間指摘されてきました。新しい状況だけでなく、長年取り組んでいる分野でも、最初の定義には細心の注意が必要です。これにより、得られた結果がどの程度トートロジーであり、役に立たないものであるかを理解できるようになります。

エディントンの有名な物語は、海で網を使って漁をした人々の話です。釣った魚の大きさを調べた結果、海で見られる魚の最小サイズが決まりました。彼らの結論は、現実ではなく、使用された手段によって決定されました。

継続するには...

本の翻訳、レイアウト、出版を手伝いたい人は、個人メッセージまたは電子メールに書いてください。 [メール保護]

ところで、私たちは別の素晴らしい本の翻訳も開始しました - 「ドリームマシン：コンピュータ革命の物語」)

私たちが特に求めているのは、 翻訳を手伝ってくれる方ビデオのみのボーナスチャプター。（10 分間転送します。最初の 20 分はすでに使用されています)

本の内容と翻訳された章序文

科学と工学を実践する技術の紹介: 学ぶことを学ぶ (28 年 1995 月 XNUMX 日) 翻訳: 第 1 章
「デジタル（ディスクリート）革命の基礎」（30年1995月XNUMX日）第2章デジタル（ディスクリート）革命の基礎
「コンピュータの歴史 - ハードウェア」 (31 年 1995 月 XNUMX 日) 第3章コンピュータの歴史 - ハードウェア
「コンピュータの歴史 - ソフトウェア」 (4 年 1995 月 XNUMX 日) 第4章コンピュータの歴史 - ソフトウェア
「コンピュータの歴史 - アプリケーション」 (6 年 1995 月 XNUMX 日) 第 5 章: コンピュータの歴史 - 実用化
「人工知能 - パート I」 (7 年 1995 月 XNUMX 日) 第6章人工知能 - 1
「人工知能 - パート II」 (11 年 1995 月 XNUMX 日) 第7章人工知能 - II
「人工知能III」（13年1995月XNUMX日）第8章人工知能-III
「n次元空間」（14年1995月XNUMX日）第9章 N次元空間
「コーディング理論 - 情報の表現、パート I」 (18 年 1995 月 XNUMX 日) 第10章コーディング理論 - I
「コーディング理論 - 情報の表現、パート II」 (20 年 1995 月 XNUMX 日) 第11章符号化理論 - II
「誤り訂正符号」 (21 年 1995 月 XNUMX 日) 第12章エラー訂正コード
「情報理論」（25年1995月XNUMX日）第13章情報理論
「デジタルフィルター、パート I」 (27 年 1995 月 XNUMX 日) 第14章デジタルフィルター - 1
「デジタルフィルター、パート II」 (28 年 1995 月 XNUMX 日) 第15章デジタルフィルター - 2
「デジタルフィルター、パート III」 (2 年 1995 月 XNUMX 日) 第16章デジタルフィルター - 3
「デジタルフィルター、パート IV」 (4 年 1995 月 XNUMX 日) 第 17 章デジタルフィルター - IV
「シミュレーション、パート I」（5 年 1995 月 XNUMX 日）第 18 章モデリング - I
「シミュレーション・パートⅡ」（9年1995月XNUMX日）第 19 章モデリング - II
「シミュレーション、パートIII」（11年1995月XNUMX日）第 20 章モデリング - III
「光ファイバー」（12年1995月XNUMX日）第21章光ファイバー
「コンピュータ支援指導」（16年1995月XNUMX日）第 22 章: コンピュータ支援指導 (CAI)
「数学」 (18 年 1995 月 XNUMX 日) 第23章数学
「量子力学」 (19 年 1995 月 XNUMX 日) 第24章量子力学
「創造性」（23年1995月XNUMX日）。翻訳：第25章創造性
「エキスパート」（25年1995月XNUMX日）第26章専門家
「信頼できないデータ」 (26 年 1995 月 XNUMX 日) 第27章信頼できないデータ
「システムエンジニアリング」（30年1995月XNUMX日）第28章システムエンジニアリング
「測定したものは得られる」 (1 年 1995 月 XNUMX 日) 第 29 章: 測定した結果が得られる
「私たちが知っていることをどうやって知るのか」（6月2、1995） 10分ごとに翻訳する
ハミング、「あなたとあなたの研究」（6 年 1995 月 XNUMX 日）。翻訳：あなたとあなたの作品

本の翻訳、レイアウト、出版を手伝いたい人は、個人メッセージまたは電子メールに書いてください。 [メール保護]

出所： habr.com

リチャード・ハミング: 第 13 章情報理論

コメントを追加します返信をキャンセル

リチャード・ハミング: 第 13 章 情報理論

コメントを追加します 返信をキャンセル

リチャード・ハミング: 第 13 章情報理論

コメントを追加します返信をキャンセル