最近、大学でデータ圧縮のコースを開始しました。しかし、コンピューターサイエンスに適用される「エントロピー」という用語の使用はかなり曖昧です。私が知る限り、それは大まかにシステムまたは構造の「ランダム性」に変換されます。
コンピュータサイエンスの「エントロピー」の正しい定義は何ですか?
58850 次
15 に答える
63
エントロピーはさまざまなことを意味します。
コンピューティングでは、エントロピーは、オペレーティング システムまたはアプリケーションによって収集されたランダム性であり、暗号化またはランダム データを必要とするその他の用途に使用されます。このランダム性は、多くの場合、ハードウェア ソース (マウスの動きなどの既存のもの、または特別に提供されたランダム性ジェネレーター) から収集されます。
情報理論では、エントロピーは確率変数に関連する不確実性の尺度です。この文脈での用語は通常、シャノン エントロピーを指します。シャノン エントロピーは、期待値という意味で、メッセージに含まれる情報を、通常はビットなどの単位で定量化します。同様に、シャノン エントロピーは、確率変数の値がわからない場合に欠落している平均情報量の尺度です。
データ圧縮におけるエントロピー
データ圧縮のエントロピーは、圧縮アルゴリズムに入力するデータのランダム性を表す場合があります。エントロピーが大きいほど、圧縮率は低くなります。つまり、テキストがランダムであるほど、圧縮できる量が少なくなります。
シャノンのエントロピーは、任意の通信の可能な限り最高のロスレス圧縮の絶対的な制限を表します。エンコードされるメッセージを、独立した同一分布の確率変数のシーケンスとして扱うと、シャノンのソース コーディング定理は、制限内で最短の平均長特定のアルファベットでメッセージをエンコードするための可能な表現は、エントロピーをターゲットアルファベットのシンボル数の対数で割ったものです。
于 2009-02-04T07:41:53.983 に答える
20
より実用的な焦点を当てた私のお気に入りの定義は、 Andrew Hunt と David Thomas による優れた書籍The Pragmatic Programmer: From Journeyman to Master の第 1 章にあります。
ソフトウェアエントロピー
ソフトウェア開発はほとんどすべての物理法則の影響を受けませんが、エントロピーは私たちに大きな打撃を与えます。エントロピーは、システム内の「無秩序」の量を指す物理学の用語です。残念ながら、熱力学の法則は、宇宙のエントロピーが最大になる傾向があることを保証しています。ソフトウェアに乱れが増えると、プログラマーはそれを「ソフトウェアの腐敗」と呼びます。
ソフトウェアの腐敗に寄与する要因は数多くあります。最も重要なのは、プロジェクトに取り組む際の心理学または文化のようです。1 人のチームであっても、プロジェクトの心理は非常にデリケートなものになる可能性があります。最善の計画と最高の人材にもかかわらず、プロジェクトはその存続期間中に破滅と衰退を経験する可能性があります。しかし、途方もない困難と絶え間ない挫折にもかかわらず、自然の無秩序への傾向とうまく闘い、かなりうまくいくプロジェクトが他にもあります。
...
...
壊れた窓。
1 つの壊れた窓は、かなり長い間修理されずに放置されており、建物の住民に放棄された感覚を植え付けています。そのため、別のウィンドウが壊れます。人々はポイ捨てを始めます。グラフィティが登場。深刻な構造的損傷が始まります。比較的短期間のうちに、建物は所有者の修理意欲を超えて損傷し、放棄感が現実のものとなります。
「割れ窓理論」は、ニューヨークやその他の主要都市の警察署に、大きなものを締め出すために小さなものを取り締まるよう促しました. それは機能します。壊れた窓、落書き、その他の小さな違反に注意を払うことで、重大な犯罪のレベルが低下しました。
ヒント4
壊れた窓と一緒に暮らすな
「壊れたウィンドウ」 (悪い設計、間違った決定、または貧弱なコード) を修復せずに放置しないでください。見つかったらすぐにそれぞれを修正します。適切に修正するのに十分な時間がない場合は、搭乗してください。おそらく、問題のあるコードをコメントアウトするか、「実装されていません」というメッセージを表示するか、代わりにダミーデータを代用することができます。これ以上の被害を防ぎ、状況を把握していることを示すために何らかの行動を起こしましょう。
引用元: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy
于 2009-02-04T07:55:13.630 に答える
11
私は常に、シャノン エントロピーの意味でエントロピーに遭遇しました。
http://en.wikipedia.org/wiki/Information_entropyから:
情報理論では、エントロピーは確率変数に関連する不確実性の尺度です。この文脈での用語は通常、シャノン エントロピーを指します。シャノン エントロピーは、期待値という意味で、メッセージに含まれる情報を、通常はビットなどの単位で定量化します。同様に、シャノン エントロピーは、確率変数の値がわからない場合に欠落している平均情報量の尺度です。
于 2009-02-04T07:41:16.780 に答える
9
(ソース: mit.edu )
メキシコ大学出身
エントロピーの情報理論的概念は、物理的概念の一般化です。エントロピーを説明する方法はたくさんあります。これは、確率変数のランダム性の尺度です。また、確率変数または確率過程に含まれる情報量の尺度でもあります。また、メッセージを圧縮できる量の下限でもあります。そして最後に、その値を決定するためにランダムなエンティティについて尋ねる必要があるのは、yes/no の質問の平均数です。
確率計算のサンプル アプリケーションでのエントロピーの式:
これは、その値の確率の rv のすべての値の合計に、その確率の対数を掛けたものです (つまり、p(x)logp(x))。この方程式は、情報の性質の第一原理から導き出すことができます。
于 2009-02-04T07:42:54.327 に答える
7
これは、情報理論におけるエントロピーの優れた代替説明です。
エントロピーは、予測を行う際の不確実性の尺度です。
エントロピーは、最初の予測を行った後に結果が得られた場合にどれほど驚くかということでも説明できます。
曲がったコインが 99% の確率で表になり、1% の確率で裏になるとします。尻尾がつく確率は 1% しかないので、実際に尻尾がつくと非常に驚くでしょう。一方で、我々はすでに 99% の確率で頭角を現しているので、頭角を現したとしてもそれほど驚くことではありません。
Surprise(x)それぞれの結果に驚きの量を与える関数が呼び出されたと仮定しましょう。次に、確率分布で驚きの量を平均化できます。この平均的な驚きの量は、私たちがどれほど不確実であるかの尺度としても使用できます. この不確実性はエントロピーと呼ばれます。
アップデート：
動物画像分類器モデル (機械学習) におけるエントロピーと予測されるクラスの信頼度との関係を説明するために、この視覚化を作成しました。ここで、エントロピーは、分類器モデルがその予測にどの程度自信を持っているかの尺度として使用されます。
これらの図は、2 つの分類子モデルからの予測のエントロピー値の比較を示しています。右側の図は、比較的高い信頼度 (エントロピーが低い) で馬の画像を予測していますが、左側の分類子は、馬、牛、キリンのいずれであるかを実際には区別できません (エントロピーが高い)。
于 2016-01-17T18:07:26.467 に答える
6
圧縮と情報理論の観点から言えば、ソースのエントロピーは、ソースからのシンボルが伝達できる情報の平均量 (ビット単位) です。非公式に言えば、シンボルの可能性が低いほど、その外観がもたらす驚きは大きくなります。
ソースに と などの 2 つのシンボルがAありB、それらの可能性が等しい場合、各シンボルは同じ量の情報 (1 ビット) を伝達します。可能性が等しい 4 つのシンボルを持つソースは、シンボルあたり 2 ビットを伝達します。
より興味深い例として、ソースにA、B、およびの 3 つのシンボルCがあり、最初の 2 つは 3 番目の 2 倍の可能性がある場合、3 番目はより驚くべきものですが、可能性も低くなります。以下で計算されるように、このソースの正味エントロピーは 1.52 です。
エントロピーを「平均驚き」として計算します。ここで、各シンボルの「驚き」は、その確率に確率の負のバイナリログを掛けたものです。
binary
symbol weight probability log surprise
A 2 0.4 -1.32 0.53
B 2 0.4 -1.32 0.53
C 1 0.2 -2.32 0.46
total 5 1.0 1.52
0 と 1 (排他的) の間の値の対数は負であるため、バイナリ対数の負が使用されます (もちろん)。
于 2009-02-07T17:42:11.103 に答える
2
簡単に言えば、エントロピーはランダム性を定義します。それは、何かがどれほど予測不可能であるかに似ています。より専門的な言い方をすれば、「コンピューティングでは、エントロピーとは、オペレーティング システムまたはアプリケーションが、暗号化またはランダム データを必要とするその他の用途で使用するために収集したランダム性です。このランダム性は、多くの場合、マウスの動きなどの既存のものまたは特別に提供されたランダム性ジェネレーターのいずれかのハードウェア ソースから収集されます。」ウィキペディアで定義されているとおりです。
ファイルに関するエントロピーの意味は、ファイル内のバイトがどれだけ乱雑であるかの測定値として簡単に結論付けることができます。nat、shannon、hartley など、エントロピーの定義に使用されるさまざまな単位があります。まあ、使用される最も一般的な単位はシャノンです。シャノンのアルゴリズムによると、ファイルのエントロピーが入らなければならない値の範囲は 0 から 8 です。したがって、エントロピー値がゼロの場合、結果は確実であると言えます。逆に、エントロピー値が 8 の場合、結果は最も予測不可能になります。イベントの結果のランダム性を測定するためにシャノンによって与えられた式は次のとおりです。
Entropy = ∑ pi log(1/pi)
ここで、iは確率piのイベントです。
この方程式は、常に 0 から 8 の間になります。
詳細については、次のリンクを参照してください: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
于 2016-02-05T15:03:07.780 に答える
0
コンピュータサイエンスのエントロピーは、一般的にビットの文字列がどれほどランダムであるかを指します。次の質問は、それを正確にすることについてです。
于 2010-06-05T04:40:42.390 に答える
0
エントロピーから大したことをするのは簡単です。私の考えでは、これは非常にシンプルで便利な概念です。
基本的に、コイントス、分岐命令の実行、配列のインデックス作成など、イベントから平均して何を学ぶかを定量化します。
同様に、検索アルゴリズムの途中での比較操作では、ある確率 P で 1 つの分岐が取られ、1-P で別の分岐が取られます。
二分探索の場合と同様に、P が 1/2 であるとします。次に、そのブランチを選択すると、基数 2 の log(2/1) が 1 であるため、以前よりも 1 ビット多くのことを知っています。一方、他のブランチを選択すると、1 ビットも学習します。
学習する情報の平均量を得るには、最初のブランチで学んだことにそのブランチを取る確率を掛け、さらに 2 番目のブランチで学んだことにそのブランチを取る確率を掛けます。
1/2 倍の 1 ビット、プラス 1/2 倍の 1 ビットは、1/2 ビットと 1/2 ビット、または合計 1 ビットのエントロピーです。それが、その決定から平均して学べることです。
一方、1024 エントリのテーブルで線形検索を行っているとします。
最初の == テストでは、YES の確率は 1/1024 なので、その決定での YES のエントロピーは
1/1024 times log(1024/1)
または 1/1024 * 10 = 約 1/100 ビット。
したがって、答えが「はい」の場合、10 ビットを学習しますが、その可能性は約 1000 分の 1 です。
一方、NO の可能性ははるかに高いです。そのエントロピーは
1023/1024 * log(1024/1023)
またはおおよそ 1 倍おおむねゼロ = 約ゼロ。
この 2 つを足し合わせると、その決定について平均して約 1/100 のことを学ぶことができます。
それが線形探索が遅い理由です。テーブル内のエントリを見つけるために 10 ビットを学習する必要があるため、各決定でのエントロピー (学習できる量) が小さすぎます。
于 2009-03-21T01:09:28.460 に答える
0
エントロピーは、ウイルス研究者にとってのハッシュ コードのようなものでもあります。取得するエントロピーが少ないということは、ウイルスである可能性がある暗号化または圧縮されたコードである可能性が高いことを意味します。
標準バイナリは、圧縮または暗号化されたバイナリよりもエントロピーが高くなります。
于 2009-02-04T11:18:22.067 に答える
0
簡単に言えば、その言語の記号の確率がわかれば、その言語の記号の平均情報量を計算できます。
または
言語のエントロピーは、言語の平均的な記号の情報量の尺度です
公正なコインを考えてみましょう。
2 つのシンボルがあり、それぞれ確率 1/2 であるため、エントロピーは次のように計算されます。
h =-(1/2*log1/2 +1/2*log1/2)=1
于 2017-03-21T16:03:54.910 に答える
-1
人々がエントロピー wrt CS の熱力学的定義を誤用していると聞いたことがあります。
たとえば、このシステムではエントロピーが確実に増加しています。
彼らが意味するのは、このコードがどんどん悪化しているということです!
于 2009-02-04T07:50:08.010 に答える