問題タブ [information-theory]

整数のユニバーサル コード、特にフィボナッチ コード ( http://en.wikipedia.org/wiki/Fibonacci_codeの意味で) に関する優れた本/紙/ウェブサイト/背景資料を提案できる人はいますか? ありがとう！

編集:これまでの回答と便利なリンクをありがとう! 完全に明確になっていない場合は申し訳ありません: フィボナッチ数を生成または計算するためのコード (プログラムの作成など) について質問しているのではなく、データを使用する特定のコード (データのエンコードまたは圧縮など) について質問しています。フィボナッチ数列。

最近、大学でデータ圧縮のコースを開始しました。しかし、コンピューターサイエンスに適用される「エントロピー」という用語の使用はかなり曖昧です。私が知る限り、それは大まかにシステムまたは構造の「ランダム性」に変換されます。

コンピュータサイエンスの「エントロピー」の正しい定義は何ですか?

シャノンの情報源コーディング定理から、圧縮された文字列のエントロピーは、次のように元の文字列のエントロピーによって制限されることがわかります。

ここで、H（X）はソース文字列のエントロピー、Nはソース文字列の長さ、Lは圧縮された文字列の予想される長さです。

これは必然的に、可逆圧縮に制限があることを意味します。

私が知りたいのは：

• エントロピーを予想される圧縮率に直接関連付けることはできますか？

• エントロピーを使用して、圧縮率の上限を見つけることができますか？

エントロピー式についての私の理解では、データを表すために必要な最小ビット数を計算するために使用されるということです。通常、定義するときは別の言い方をしますが、以前の理解は私が今まで頼っていたものです。

これが私の問題です。100 個の「1」の後に 100 個の「0」が続くシーケンスがあるとします = 200 ビット。アルファベットは {0,1}、エントロピーの底は 2 です。シンボル "0" の確率は 0.5、"1" は 0.5 です。したがって、エントロピーは 1 または 1 ビットで 1 ビットを表します。

ただし、100 / 1 / 100 / 0 のようなものでランレングス エンコードすることができます。出力するビット数の後にビットが続きます。データよりも小さい表現を持っているようです。特に、100 をはるかに大きな数に増やした場合。

私が使用している: http://en.wikipedia.org/wiki/Information_entropy現時点での参照として。どこで私は間違えましたか？シンボルに割り当てられた確率ですか？私はそれが間違っているとは思わない。それとも、圧縮とエントロピーの関係を間違えたのでしょうか? 他に何か？

ありがとう。

編集

いくつかの回答に続いて、私のフォローアップは次のとおりです。メッセージの特定のインスタンスにエントロピー式を適用して、その情報コンテンツを見つけようとしますか? メッセージ「aaab」を取り上げて、エントロピーが ~0.811 であると言うのは有効でしょうか? はいの場合、エントロピー式を使用して 1 と 0 が n 回繰り返される 1...10....0 のエントロピーは何ですか。答えは1ですか？

はい、入力シンボルのランダム変数を作成し、メッセージに基づいて確率質量関数を推測していることを理解しています。私が確認しようとしているのは、エントロピー式がメッセージ内のシンボルの位置を考慮していないということです。

PRNGではなく、ある種のセンサーまたはロギングデータなど、何らかのソースからのシーケンスpf番号N₁ , N₂ , N_{3が与えられた場合、このように処理すると仮定しても安全ですか?}...

Nn/ B = Q_n Rem Mn

シーケンスQよりエントロピーが少ないシーケンスになりますMか?

注:とのB両方が同じサイズの範囲であると仮定します。QM

これは、ほとんどの現実世界のデータ セットがソースに関係なく、対数分布を持っているという観測に関連しています。1 で始まる数字は、9 で始まる数字よりもはるかに一般的です。しかし、これは下位の部分についてはほとんど語っていません。

これをテストするための楽しい方法 (そしてシステム管理者のコンピューターを停止させて怒らせる方法) として、これを bash で実行します。

ファイルサイズの最初の桁のヒストグラムを取得します。

オークション Web サイトがユーザーにシリングを行っていないことを証明する (または少なくとも統計的証拠を示す) 方法について、情報理論に関する質問があります。

最近、入札ごとに支払うオークションのウェブサイトを立ち上げました。ユーザーが料金を支払って時限オークションに入札する新しいタイプのオークションです。入札ごとに価格が上がり、オークションの時間が長くなります。時間切れになった最後の入札者が商品を購入できます。

問題は、ユーザーが私たちがだましているのではないかと疑っていることです。ユーザーの信頼が私にとって最も重要であるなどの意図はありません。ただし、このモデルは他の悪意のあるサイトによって実装される可能性があり、入札者をだますのは簡単です. 私たちが正当であることをユーザーに示す手段を講じる必要があります。

誠実な運営を心掛けております。課題は、これをどのように世界に証明するかです。どのアプローチも、ユーザーのプライバシーを保護することとバランスを取る必要があります。

私が持っているいくつかのアイデアは次のとおりです。

• 各ユーザーのIPアドレスを表示

• 商品を受け取った勝者からの証言を求めます。商品と地元紙の最近の表紙コピーと一緒に写真を郵送してもらいます。

• 自宅の州や国など、各ユーザーに関する大まかな情報を表示する

私は何か提案を探しています。

アップデート

いくつかの素晴らしい提案。ここのところ：

• 各ユーザーに関する行動情報を提供します。

  • 加入時
  • どのオークションが参加したか
  • オークションの統計 - 入札数、費用

• 個人を特定できる情報を公開しないでください。勝てなかった人が勝者に報復する可能性があるため、IP アドレスはありません。

• ディスカッションとアドレスの質問のための公開フォーラム

• ユーザーからの証言を求めて、人々が実際に勝って製品を受け取ったことを示します。

  • それが私たちによって「発明された」ものではないことを証言でどのように示すことができますか? 最近の地元の新聞と一緒に写真を載せてくれるよう頼むことを考えています。これを大規模に偽造することは困難であり、時間と地域による勝者の分布.

ユーザーの居住国と州を表示しても問題ないと思いますか、それとも個人情報が多すぎると思いますか?

私はこの質問に出くわしました。

「ロスレス圧縮アルゴリズムは、一部のファイルを小さくし、ファイルを大きくしないことを保証すると主張しています。
これは;

a）不可能

b）可能ですが、不確定な時間実行される可能性があります。

c）圧縮率2以下で可能、

d）任意の圧縮率で可能ですか？」

私は（a）に傾倒していますが、その理由についてしっかりとした説明をすることができませんでした。（私は友人の考えをリストし、私は可能な答えとして思いついた）

dビットパケットを送信し、エラー訂正コード（d> r）用にさらにrビットを追加したい
場合、最大でいくつのエラーを見つけて訂正できますか？

シナリオ

JavaGUIアプリケーション内のデータセットに対して教師あり学習を実装しようとしています。ユーザーには、検査するアイテムまたは「レポート」のリストが提供され、使用可能なラベルのセットに基づいてそれらにラベルが付けられます。教師あり学習が完了すると、ラベル付けされたインスタンスが学習アルゴリズムに渡されます。これにより、ユーザーがそれらを表示する可能性がどの程度あるかについて、残りのアイテムを並べ替えようとします。

ユーザーの時間を最大限に活用するために、レポートのコレクション全体に関するほとんどの情報を提供するレポートを事前に選択し、ユーザーにラベルを付けてもらいたいと思います。私が理解しているように、これを計算するには、各レポートのすべての相互情報量の値の合計を見つけて、その値で並べ替える必要があります。次に、教師あり学習からのラベル付きレポートを使用してベイジアンネットワークを形成し、残りの各レポートのバイナリ値の確率を見つけます。

例

ここで、人為的な例が説明に役立つ可能性があり、間違いなく間違った用語を使用した場合の混乱を解消する可能性があります:-)アプリケーションがユーザーにニュース記事を表示する例を考えてみましょう。表示されるユーザーの好みに基づいて、最初に表示するニュース記事を選択します。相関関係のあるニュース記事の特徴は、、country of originまたはcategoryですdate。したがって、ユーザーがスコットランドからのニュース記事を興味深いものとしてラベル付けすると、スコットランドの他のニュース記事がユーザーにとって興味深いものになる可能性が高くなることを機械学習者に伝えます。スポーツなどのカテゴリ、または2004年12月12日などの日付についても同様です。

この設定は、すべてのニュース記事の任意の順序（たとえば、カテゴリ別、日付別）を選択するか、ランダムに並べ替えてから、ユーザーが進むにつれて優先度を計算することで計算できます。私がやりたいのは、ユーザーに少数の特定のニュース記事を見て、それらに興味があるかどうかを言わせることによって、その注文の一種の「有利なスタート」を取得することです（教師あり学習の部分）。ユーザーに表示するストーリーを選択するには、ストーリーのコレクション全体を考慮する必要があります。ここで相互情報量が出てきます。各ストーリーについて、ユーザーが分類したときに、他のすべてのストーリーについてどれだけ教えてくれるか知りたいです。たとえば、スコットランドを起源とするストーリーが多数ある場合は、ユーザーにそのうちの1つを（少なくとも）分類してもらいたいと思います。カテゴリや日付などの他の相関機能についても同様です。目標は、分類されたときに他のレポートに関するほとんどの情報を提供するレポートの例を見つけることです。

問題

私の数学は少し錆びていて、機械学習に慣れていないので、相互情報量の定義をJavaの実装に変換するのに問題があります。ウィキペディアでは、相互情報量の方程式を次のように説明しています。

しかし、何も分類されておらず、学習アルゴリズムがまだ何も計算していないときに、これが実際に使用できるかどうかはわかりません。

私の例のように、このクラスの新しいラベルのないインスタンスが多数あったとします。

私の特定のシナリオでは、フィールド/機能間の相関は完全一致に基づいているため、たとえば、1日と10年の日付の違いはそれらの不平等において同等です。

相関の要因（たとえば、日付はカテゴリよりも相関が高いですか？）は必ずしも等しいとは限りませんが、事前定義して一定にすることができます。これは、関数の結果が事前定義された値であることを意味しますかp(x,y) 、それとも用語を混同していますか？

質問 （ついに）

この（偽の）ニュース記事の例を前提として、相互情報量の計算を実装するにはどうすればよいですか？ライブラリ、javadoc、コード例などはすべて歓迎すべき情報です。また、このアプローチに根本的な欠陥がある場合は、その理由を説明することも同様に価値のある答えになります。

PS。私はWekaやApacheMahoutなどのライブラリを知っているので、それらについて言及するだけではあまり役に立ちません。私はまだ相互情報量に関するものを具体的に探しているこれら両方のライブラリのドキュメントと例を探しています。私が本当に役立つのは、これらのライブラリが相互情報量に役立つリソース（コード例、javadoc）を指すことです。

私はこの宿題を持っています：与えられたアルファベットの記号のコードワードを見つけること。3つのシンボルのグループにバイナリハフマンを使用する必要があると書かれています。それは正確にはどういう意味ですか？[アルファベット]^3で通常のハフマンを使用しますか？もしそうなら、どうすればグループ内の3つのシンボルの違いを知ることができますか？