問題タブ [information-theory]

これを行うための標準的な方法はありますか？

グーグル（「近似エントロピー」ビット）は複数の学術論文を明らかにしますが、任意の長さの特定のビット文字列の近似エントロピーを定義する擬似コードのチャンクを見つけたいと思います。

（これは言うのが簡単で、アプリケーションによって異なる場合、私のアプリケーションには16,320ビットの暗号化データ（暗号文）が含まれます。しかし、パズルとして暗号化されており、解読することは不可能ではありません。最初に確認したいと思います。エントロピーですが、そのような適切な定義を簡単に見つけることができませんでした。したがって、StackOverflowにあるべき質問のようでした！16kのランダムに見えるビットの暗号化を解除することから始めるアイデアも歓迎します...）

この関連する質問も参照してください：
エントロピーのコンピュータサイエンスの定義は何ですか？

私のアルゴリズムの教科書から：

毎年開催される郡競馬には、互いに競ったことのない 3 頭のサラブレッドが参加します。興奮して、あなたは彼らの過去 200 レースを研究し、これらを 4 つの結果 (1 位 (「1 位」)、2 位、3 位、その他) の確率分布として要約します。

一番予想しやすい馬は？この問題に対する定量的なアプローチの 1 つは、圧縮率を調べることです。各馬の履歴を 200 個の値 (1 位、2 位、3 位、その他) の文字列として書き留めます。これらの実績文字列をエンコードするために必要なビットの総数は、ハフマンのアルゴリズムを使用して計算できます。これは、Aurora では 290 ビット、Whirlwind では 380 ビット、Phantasm では 420 ビットになります (チェックしてください!)。Aurora はエンコードが最も短いため、強い意味で最も予測可能です。

彼らはどのようにしてファンタズムの 420 を得たのですか? 私は400バイトを取得し続けます:

最初に結合、その他 = 0.4、2 番目、3 番目に結合 = 0.6。各位置をエンコードする 2 ビットで終了します。

ハフマン符号化アルゴリズムについて誤解しているものはありますか?

教科書はこちらから入手できます: http://www.cs.berkeley.edu/~vazirani/algorithms.html (156 ページ)。

情報利得の値がマイナスになる可能性はありますか?

今後 10 年間、世界中のすべてのスーパーコンピューターを自由に使用できると想像してください。あなたの仕事は、10 本の長編映画を可能な限り無損失で圧縮することでした。もう 1 つの基準は、通常のコンピューターがオンザフライで圧縮解除できる必要があり、圧縮解除ソフトウェアをインストールするために HD の多くを費やす必要がないことです。

私の質問は、今日の最良の代替品よりもどれだけ多くの圧縮を達成できるかということです. 1%、5%、50%? より具体的には、辞書のサイズが固定されている場合、圧縮に理論的な制限はありますか（ビデオ圧縮でもそう呼ばれる場合）？

指数分布データの圧縮に役立つ機械学習アルゴリズムや予測モデルはありますか? ゴロム コードを使用してファイルを既にエンコードしました。これにより、大量のスペースが確実に節約されますが、これでは十分ではありません。圧縮が必要です。PAQ8L は十分に圧縮しません。

必要に応じてファイルを請求してください。

指数分布 --

{a,b,b,a,a,b,c,c,a,a,b,a,a,b,a,c,b,a,b,d}

M が、それぞれ属性 X と Y を持つオブジェクト m の集合であると仮定します。ここで、X と Y が指定された m に対して 1 つの値しか持てない場合 (つまり、X,Y が P(X=x_i|M=m_i) の確率変数である場合、P( Y=y_i|M=m_i))、X と Y の相互情報量を計算することは可能です。しかし、X が一度に複数の結果を持つことができるとしたらどうでしょうか? つまり、m_3 の場合 X={x1,x2} - 一般に、X の結果はすべての可能な結果のサブセットです。そのような場合、相互情報量やその他の依存度を測定できますか?

X をバイナリ確率変数 X_1、X_2 などに分割することは可能ですか? X_1=1 の場合、X に x1 が含まれている場合は X_1=0 であり、それ以外の場合はすべての組み合わせ i,j について I(X_i,Y_j) を計算し、情報を順番に合計します。 I(X,Y) を取得するには?

ありがとう。

例：

英語で書かれたテキストがあり、そのエントロピーを計算しました。しかし、LZ 法に基づく圧縮アルゴリズムは、エントロピーによって与えられる限界をはるかに下回ることに気付きました。

それは、英語のテキストをモデルとする情報源が記憶を持っているという事実によるものです。したがって、圧縮の境界は、そのソースのエントロピーではなく、エントロピー レートによって決まります。

メモリ付きソースのエントロピー率の定義を見ましたが、英語で書かれたテキストのアルゴリズムまたは擬似コードでエントロピー率を計算する方法を知りたいと思っていました。

何か案は？

手伝ってくれてありがとう。

Jeff Atwood は最近、「文字列のエントロピーの計算」コード スニペットをコミュニティが改善できるかどうかを知りたがっていた CodeReview 投稿へのリンクをツイートしました。彼は説明しました。

彼の方法の要点は、文字列内の一意の文字の数を数えると、それがエントロピーを意味するように思われました (コードはPieterG の回答から取得されました):

一意の文字数が文字列のエントロピーを意味する方法と、文字列のエントロピーが低品質を意味する方法がわかりません。アトウッド氏が何を達成しようとしているのか、この分野の知識が豊富な人に説明してもらえないだろうかと思っていました。

ありがとう！

簡単な質問です。

次のような一連のデータがある場合:

では、属性 1 に対する属性 2 の情報利得は何ですか?

データセット全体のエントロピーを計算しました: -(3/6)log2(3/6)-(3/6)log2(3/6)=1

それから私は立ち往生しています！attribute-1 と attribute-2 のエントロピーも計算する必要があると思いますか? では、これらの 3 つの計算を情報利得の計算に使用しますか?

どんな助けでも素晴らしいでしょう、

ありがとうございました ：）。

通話記録の長いリストにuser_idsをエンコードしようとしています。これらのレコードの中で最もスペースを占める部分は、発信者と受信者のシンボルです。最もアクティブな発信者に短い記号を割り当てるマップを作成します---これにより、ファイルの全体的なサイズ（したがってI / O時間）を抑えることができます。

各シンボルが何回使用されるかを事前に知っています---言い換えれば、相対的な確率分布を知っています。さらに、生成されるコードがハフマンコードのように「プレフィックスフリー」であることが重要ではありません。では、最高のエンコーディングスキーム、つまり、最も圧縮率が高く、迅速な実装が存在するものは何でしょうか。

答えは、圧縮スキームを指すだけでなく、そのエンコーディングスキームの実装も指す必要があります。