エントロピーのコンピュータサイエンスの定義
1.はじめに
このチュートリアルでは、エントロピーの概念と、コンピューターサイエンスのさまざまな分野でのその応用について見ていきます。
エントロピーは、コミュニケーションに関連する問題の中で生じたシャノンによって開発された情報理論に関連しています。
2.通信
コミュニケーションは、あるメカニズムが別のメカニズムと積極的に関係を結ぶすべてのプロセスとして定義できます。
通信システムには、ソース、通信チャネル、および受信機の3つの基本要素が含まれています。
情報理論とは、情報の測定とその伝達に関する質問に、ノイズの有無にかかわらず答えることです。
3.組み合わせエントロピー
情報エントロピーの式を導出することで、その意味を理解することができます。
A、B、およびCの3つの異なるシンボルの可能な固定長シーケンスを検討してください。 シンボルAのインスタンスが2つ、シンボルBのインスタンスが5つ、シンボルCのインスタンスが3つあるとします。 2つの可能なシーケンスは次のとおりです。
BCBBCCABAB
BACBACBBCB
これらの組み合わせのそれぞれは順列と呼ばれます。 同じタイプのシンボルが区別できないことを考慮すると、順列の数は多項係数によって与えられます。 この例では、順列の数は次のとおりです。
一般に、多重度の異なる記号によって形成される長さのシーケンスの場合、次のようになります。
バイナリ文字列を使用して、可能な順列のそれぞれを一意にエンコードするとします。 長さビットの文字列は、さまざまな可能性をエンコードできます。
順列をエンコードするには、が必要です。 基数2の対数をとると、2進文字列の長さは次のようになります。
シーケンスを構成するシンボルのバイナリ文字列の平均の長さは次のとおりです。
4。情報理論におけるエントロピー
情報理論におけるエントロピーは、情報エントロピーまたはシャノンエントロピーとも呼ばれ、コンビナトリアルエントロピーで表され、それらから導出できます。
次の式で対数を操作すると、次のように記述できます。
十分に大きいスターリングの公式を使用して、階乗の対数を近似できます。
それを考慮すると、次のようになります。
比率が長さのシーケンスの-番目のシンボルの出現の確率にすぎないことを考慮に入れて、エントロピーの最終的な一般式を取得します。
私たちが導入した近似を考えると、情報エントロピーは組み合わせエントロピーの上限です。
自然対数の関数としてよく使用されます。
この場合、単位はnats/symbolです。 ビットとnatはどちらも無次元単位です。
5。連続の場合のエントロピー
離散ケースから連続ケースへの移行において、シャノンは単純に総和を積分に置き換えました。
この量は、一般に記号で表され、微分エントロピーと呼ばれます。積分は、確率分布の代わりに確率密度関数を使用することを意味します。
ここに問題があります。 これは、平均と分散の正規確率密度によって与えられると考えてください。
次に、積分を計算すると、微分エントロピーは次のようになります。
上記の式は、のゼロ未満であることに注意してください。
したがって、微分エントロピーの適用には注意が必要です。 離散エントロピーの単純な一般化としてのその重要でない使用は、予期しない結果を引き起こす可能性があります。
Jaynesは、これらの問題を解決するために、相対エントロピーとして知られる微分エントロピーの修正バージョンを提案しました：
上記の式は、同じ間隔で測定する限り、スケール不変です。 多くの場合、一様確率密度の形で、先験的な確率と見なすことができます。
微分エントロピーの問題は、連続体のエントロピーの絶対的な尺度が数学的に正当化されないという事実から生じます。 相対エントロピーは、で与えられる任意のレベルに関する微分エントロピーを測定します。
6.エントロピーと情報
シャノンの研究は、フォンノイマン（シャノンに名前を提案した）が指摘したように、統計物理学におけるボルツマンの観察から、エントロピーは物理の可能な代替案の数に関連していることを考慮して、「情報が不足している」ことに由来しています。システム。
情報理論の情報は意味とは関係ありません。 シャノンは書いた：
「コミュニケーションのセマンティックな側面は、技術的な側面とは無関係です。」
2つのメッセージから選択できる場合は、情報量の単位（またはビット、John Wによって提案された用語）として2つのメッセージのうちの1つを選択することを任意に示すことができます。 テューキー）。 これまで見てきたように、メッセージがバイナリ文字列としてエンコードされるときにビットが発生します。
6.1. エルゴードプロセス
メッセージのシンボルシーケンスには、一般に、さまざまな確率があります。 アルファベットの可能な記号の中から選択してメッセージを作成します。 実際のプロセスでは、シンボルを選択する確率は以前の選択とは無関係ではありません。
通常のアルファベットの記号で単語を構成する英語で書かれたメッセージを考えてみてください。 たとえば、母音が後にある確率は、母音が存在する確率よりもはるかに高くなります。
一連の確率によってシンボルを選択するプロセスがある場合、確率過程を扱います。 確率過程のシンボルの選択が以前に選択されたシンボルまたはイベントに依存する場合、マルコフ過程があります。 イベントの数が多いときにマルコフ過程がサンプルに依存しない統計につながる場合、エルゴード過程があります。
したがって、エントロピーは、エルゴードプロセスを検討する際の不確実性、驚き、または特定の数の可能性の間の選択に関連する情報の尺度です。
7.最大エントロピー
関係する可能性が同じようにありそうな場合は最大です。 2つのオプションについて、次のようになります。
これにより、次のグラフィック表現が得られ、次の最大値が示されます。
この結果を、3つ以上の確率が関係するケースに一般化することができます。 この最大値が一意であることを示すことができます。
確率密度の具体的な関数形式を使用する場合、次のようになります。
- 以前に見た正規密度のエントロピーは、同じ分散を持つすべての密度の中で最大です。 言い換えると、平均と分散の制約下での最大エントロピー分布はガウス分布です。
- 均一密度のエントロピーは、考えられるすべての確率密度の中で最大です。 漸近線ではないため、均一密度のエントロピーは、すべての点で一定の値であるため（積分は存在しません）、ドメイン全体で計算することはできませんが、有限の範囲で計算できます。 この場合、連続の場合の確率はであり、微分エントロピーは次のようになります。
これは、選択した範囲の範囲によって異なります。 離散的な場合、natsで表されるイベントとエントロピーの最大エントロピーは次のとおりです。
8.避けられない物理的アナロジー
前のセクションで、情報理論の開発の初期段階における熱力学の影響を強調しました。 ただし、情報エントロピーは、物理学の他の分野でも非常に重要です。
8.1。熱力学的エントロピー
理想気体の熱力学的エントロピーは、ボルツマン-プランク方程式で与えられます。
ここで、はボルツマン定数であり、はガスのマクロ状態に対応する実際のミクロ状態の数です。 ボルツマン方程式は、エントロピーと熱力学系の原子または分子を配置できる方法の数との関係を示しています。
ボルツマン方程式の意味と、順列の概念から始まる組み合わせエントロピーに与えたものの類似性に注意してください。
8.2. 順序、確率、およびエントロピー
孤立したシステムでは、無秩序またはエントロピーは、最大に達するまで、物理的な不可逆プロセスごとに増加することがわかっています。 この結果は、外部との熱伝達がない断熱システムの不可逆過程にも当てはまります。 この事実は、重要な巨視的な結果をもたらします。
空気が充満した容器にガスを注入し、十分な時間を待つと、すべての点で同じ濃度に達するまで、ガスが自然に空気中に拡散することがわかります。
別の例は、異なる温度での2つの物体間の接触です。 この場合、2つの物体の間に熱の流れがあり、それらの温度と等しくなります。これは、エネルギーの濃度または密度の尺度と見なすことができます。 2つの物体の質量が異なる場合、プロセスの終了時にエネルギー量は異なりますが、単位体積あたりのエネルギーは同じになります。
2番目の原則は、多くの場合、システム内のいくつかのプロパティを等しくしようとする物理プロセスの確立によって明らかになります。 その結果、物理的に観測可能なものの勾配がゼロになります。 孤立したシステムでは、エントロピーの増加につながるプロセスは自発的です。 最大エントロピーは熱力学的平衡に対応します。
宇宙は断熱的で孤立したシステムです。 最大エントロピーに達すると、自発的なプロセスを可能にするエネルギーの勾配はなくなります。 この予想は、宇宙の熱的死またはエントロピー死として知られています。
システムのすべてのポイントでの最大熱力学的エントロピーと物理的特性の同等性、および確率の同等性から派生する最大情報エントロピーの類似性に注意してください。
8.3。不確実性と量子力学
不確定性原理は基本的な自然の限界です。 これは、任意の精度または確実性の物理的観測量（共役変数）のペアで測定する可能性に関するものです。
エントロピーは不確定性の尺度であるため、情報エントロピー（エントロピー定式化）の観点から不確定性原理を定式化できるのは偶然ではありません。
Bourret 、 Everett 、 Hirschman 、および Leipnik によって個別に提案された不等式から始まり、各関数とそのフーリエ変換によって満たされます。それぞれ座標空間と運動量空間を接続します。
Beckner 、およびBialinicki-BirulaとMicielskiは次のことを示しました。
ここで、はプランク定数に関連しています。
上で見たように、正規確率密度の微分エントロピーは、同じ分散を持つすべての分布の中で最大であるため、一般的な確率密度に対して、不等式を書くことができます。
最後の方程式を前の方程式に代入すると、次のようになります。
それが不確定性原理の定式化です。
9.エントロピープロパティ
エントロピーのいくつかの基本的な特性は次のとおりです。
- 連続性：確率の値を最小限に変更すると、エントロピーがわずかに変更されるだけです。
- 対称性：結果の並べ替えでは、メジャーは不変です。
- 加法性：エントロピーの量は、プロセスをどのように考えるか、およびプロセスをどのように部分に分割するかとは無関係である必要があります。
10.他の形式のエントロピー
2つの確率変数が与えられると、それらの周辺確率、同時確率、および条件付き確率を、関係によってリンクされて定義できます。
エントロピーは分布または確率密度の関数であるため、類似のバリアントを定義できます。
結合エントロピーは、一連の変数に関連する不確実性の尺度です。 離散的および連続的なケースの場合、次の形式を取ります。
どこ：
等式は、とが統計的に独立している場合にのみ有効です。
条件付きエントロピーまたは同義語は、別の確率変数の値が与えられた場合に、確率変数の結果を記述するために必要な情報の量を定量化します：
いくつかの重要なプロパティは次のとおりです。
ディスクリートの場合と同等のプロパティを持ちます。
情報理論で非常に重要な量は相互情報量（MI）であり、別の確率変数を観察することによって1つの確率変数について取得された情報の量を定量化します。 これは、2つの変数間の相互依存性の尺度です：
MIは正で対称であり、次の関係を通じてさまざまな形式のエントロピーにリンクされています。
11.情報の伝達と伝達
容量ビット/秒の通信チャネルとエントロピービット/シンボルのソースの場合、妨害されていないチャネルの平均伝送速度は、ビット/シンボルで制限されます。 この制限に近づくほど、エンコードプロセスは長くなります。
逆説的な事実は、通信チャネルにノイズが存在する場合、受信したメッセージのエントロピーは、送信元によって送信されたエントロピーよりも大きいということです。 したがって、受信されたメッセージには、送信されたメッセージよりも多くの情報が含まれます。これは、外乱によって、純粋なソースのエントロピーに追加されたエントロピーが導入されるためです。 追加情報は不要です（ノイズ）が、形式的な観点からは、受信したメッセージの全体的なエントロピーに寄与します。
12.データ圧縮
データ圧縮は、エントロピーと情報理論の概念の適用の注目すべき例です。
送信元から受信者にメッセージを送信するには、通信チャネルを使用します。 送信には、メッセージをコーディングする前のプロセスが含まれます。 アルゴリズムを使用して、元のサイズ（圧縮）を縮小することができます。
圧縮は、非可逆または可逆になる可能性があります。 例としてオーディオファイル圧縮を使用すると、mp3は不可逆圧縮であり、FLACは可逆圧縮です。
具体的なアルゴリズムについては検討しませんが、データ圧縮メカニズムを規定する一般的な法則を確認します。
12.1。エントロピーとコーディング
コーディングでは、メッセージの各シンボルは、固定長または可変長のコードまたはコードワードによって識別されます。 たとえば、アルファベットの最初の4文字を。でエンコードできます。
各シンボルが確率とコードワード長で識別される場合、平均コードワード長は次のようになります。
ソースコーディング定理またはシャノンの最初の定理は、情報ソースの出力を、平均長がソースエントロピーよりも短いソースコードで表すことができないことを確立しています：
コードワードの平均の長さは、ソースのエントロピーによって制限されます。 低いほど、理論的に到達できる値は低くなります。 したがって、エントロピーが低いメッセージはより圧縮可能です。
12.2。データ圧縮
コーディング効率は次のとおりです。
の値は、圧縮アルゴリズムを開発するときに目指す限界です。
直感的な結果として、エンコードされた文字列に、それを生成する可能性のあるソース文字列が1つしかない場合、一意のデコード可能性があります。 このタイプのエンコーディングの例は、プレフィックスコードです。
プレフィックスコードは、他のコードワードのプレフィックスであるコードワードがないコードです。 たとえば、可変長コーディングを使用する場合、のコードワードは（サブストリング11）のコードワードのプレフィックスコードであるため、プレフィックスコードはありません。
この文脈では、重要な結果はクラフト-マクミランの不等式です。
コードワードの長さがKraft-McMillanの不等式を満たす場合、これらのコードワードの長さを使用してプレフィックスコードを作成できます。 これにより、デコードの一意性が保証されます。
シンボルごとに、が検証された場合、それを証明できます。 この状態が発生しない場合は、バイナリのシャノンファノコードを使用してソースを拡張することで効率を上げることができます。
シンボルのブロックのシャノンファノコードは、エントロピーの定義に由来する後者の等式である、より短いコードワード長を期待します。 元のソースシンボルの予想されるコードワードの長さは、次の長さより短くなります。
十分に大きくすることを選択することにより、これをエントロピーにできるだけ近づけることができ、を取得できます。 支払う代償は、デコードプロセスの複雑さの増加です。
12.3。圧縮方式
このセクションの結論として、古典的な圧縮スキームを報告します。
それぞれが確率を持つシンボルのベクトルを想定し、バイナリアルファベットを使用したエンコードの問題を検討します。 整数と実数、およびの場合、コーディングスキーム、、およびデコードは、次のように形式化できます。
このスキーマは、次の条件が満たされた場合の圧縮スキーマを形成します。
実際には、最後の条件から、確率に従ってシンボルをコーディングすることで、元の確率を目的の精度で近似するデコードプロセスが可能になる必要があります。
13.エントロピーと機械学習
13.1。クロスエントロピー誤差関数
ニューラルネットワークなどの分類器では、2乗誤差の代替誤差関数を使用できます。
入力が与えられた場合のターゲットの独立した条件付き確率から始めて、尤度関数の負の対数から構築された誤差関数を最小化するのが通常です。
ここで、はデータセットのレコードのベクトルであり、はクラス（ネットワーク出力ユニット）の数です。
ターゲットが2つの相互に排他的なクラスと。にのみ属していると考える場合、条件付き確率は次のようになります。
はクロスエントロピー誤差関数であり、エントロピーの最大値に関する説明ですでに見た形式を持っています。
連続の場合を分析することにより、この誤差関数の最小値が2乗誤差の最小値と同じであることを示すことができます。
13.2。最大エントロピーの原理
Jaynesによって提案された最大エントロピーまたはMaxEntの原理は、問題内の知識を最もよく表す確率分布が最大エントロピーを持つものであることを確立します。 ニューラルネットワークの出力は、特定の条件下では、入力が与えられた場合のターゲットの条件付き確率の近似値であるため、MaxEnt原理は潜在的に最適化基準を構成します。
MaxEntの原理には批判がないわけではありません。 これにより、2つの同様の原則が提案されました。
- 最大相互情報量（MaxMI）の原理。最適な確率密度は、ネットワーク出力とターゲット間のMIが最大の確率密度です。
- 最小相互情報量（MinMI）の原理。最適な確率密度は、ネットワーク出力と入力の間のMIが最小の確率密度です。
後者の場合、入力とターゲットの周辺確率（合理的な条件）がわかっている場合、MinMIはMaxEntの原理と同等です。
13.3。推定器のエラー
たとえば、入力に依存するニューラルネットワークの出力によって与えられるターゲットと推定量を考慮すると、条件付き微分エントロピーに依存する、予想される2次誤差の下限を取得することができます。
この表現は量子力学において重要であり、これもまた物理学と情報理論の間の関係の重要性を強調しています。
14.結論
このチュートリアルでは、エントロピーの概念と、コンピューターサイエンスのさまざまな分野でのエントロピーの使用の意味について概説しました。 情報理論の歴史的発展を考えると、エントロピーの分析は熱力学的エントロピーの意味を無視することはできません。
このトピックは広範であり、もちろん、単一の記事で網羅的に扱うことはできません。 それにもかかわらず、テキストで扱われているテーマは、さらなる洞察のためのアイデアを与えることができます。
