問題タブ [information-theory]

編集：うわー、多くの素晴らしい応答。はい、私はこれを遺伝的アルゴリズムによって実行される種類の品質を判断するための適応度関数として使用しています。したがって、評価のコストは重要です（つまり、高速である必要があります。できればO(n)）。

私がいじっているAIアプリケーションの一部として、整数の候補配列をその単調性、別名「ソート性」に基づいて評価できるようにしたいと思います。現在、ソートされた最長の実行を計算し、それを配列の長さで割るヒューリスティックを使用しています。

これは良いスタートですが、ソートされたサブシーケンスの「塊」が存在する可能性を考慮に入れていません。例えば：

この配列は、3つのソートされたサブシーケンスに分割されます。私のアルゴリズムでは、40％しかソートされていないと評価されますが、直感的には、それよりも高いスコアが得られるはずです。この種のもののための標準的なアルゴリズムはありますか？

これは、単純なプログラミングの問題というよりは、コンピュータ サイエンス/情報理論の問題です。この問題を投稿するのに適したサイトを誰か知っている場合は、お知らせください。

M メッセージで冗長に送信される N ビットのデータがあり、少なくとも M-1 のメッセージが正常に受信されるとします。メッセージあたりのビット数を減らして N ビットのデータをエンコードするさまざまな方法に興味があります。(これはRAIDに似ていますが、はるかに小さいレベルであり、N = 8 または 16 または 32 です)

例: N = 16 で M = 4 と仮定すると、次のアルゴリズムを使用できます。

4 つのメッセージのうち 3 つのメッセージが通過することを保証できれば、各グループから少なくとも 1 つのメッセージが通過します。したがって、9 ビット以下でこれを機能させることができます。おそらく総ビット数を少なくしてこれを行う方法がありますが、その方法はわかりません。

この種のことを行うための単純なエンコード/デコードアルゴリズムはありますか? この問題に名前はありますか？（名前がわかれば、ググってみます！）

注：私の特定のケースでは、メッセージが正しく到着するか、まったく到着しません（メッセージがエラーで到着しません）。

（編集：2番目の部分を別の質問に移動しました）

情報理論は、エンコードとデコードが存在する場所で機能します。例：圧縮（マルチメディア）、暗号化。

情報理論では、「エントロピー」、「自己情報」、「相互情報量」などの用語に遭遇し、主題全体がこれらの用語に基づいています。これは抽象的なものに過ぎません。率直に言って、それらは実際には意味がありません。

これらのことを実際的な方法で説明している本/資料/説明（できれば）はありますか？

編集：

情報理論の紹介：ジョン・ロビンソン・ピアスによるシンボル、信号、ノイズは、私が望む方法で（実際に）それを説明する本です。その良すぎる。私はそれを読み始めました。

ウィキペディアとマッケイの情報理論、推論、学習アルゴリズムについて知っています（教科書として適切ですか？）。シャノンのエントロピーから始まり、条件付きエントロピーと相互情報量を経た教科書が求められています...何かアイデアはありますか？大学でそのようなコースを受講している場合、どの教科書が使用されますか？

ありがとう。

情報理論の分野で「条件付きエントロピー」が関係していると思う質問があります。私は頭を包み込もうとしていますが、助けを借りることができます。4つの家がある例を考えてみましょう。最初の家には8人、2番目の家には4人、3番目の家には2人、4番目の家には2人が住んでいます。だから、4つの家と16人。これらの人の1人をランダムに選択した場合、その選択は16人の中からの選択であり、その選択に対して4ビットの情報エントロピーが得られます。

しかし、ここで2段階の選択を考えてみましょう。最初に、ランダムに1つの家を選択し、次に、選択した家の1人を選択します。したがって、最初のステップである、利用可能な4つの家から1つの家を選択するステップでは、2ビットの情報エントロピーが生成されます。しかし今、私が最初の家を選ぶ時間の25％で、2番目のステップは最初の家の8人の中から1人を選ぶ際にさらに3ビットを追加します。別の25％のケースでは、2番目の家に住む4人の中から1人を選択するのに、あと2ビットしか必要ありません。そして最後に、完全に半分のケースでは、3番目または4番目の家のいずれかに住んでいるペアから1人を選ぶのに1ビットだけ必要です。

どういうわけか、2ステップアプローチのビットカウントの加重平均は、シングルステップメソッドが必要とするのと同じ4ビットの合計を生成するはずだと私には思えます。しかし、私は数字を合計することができないので、明らかに私が考えている以上の数学があります。私はあなたが次のように確率を単純に合計できるはずだと期待していました：

しかし、これは3.75ビットの結果を生成し、私が期待している4ビットではありません。これは私がこれを評価するために使用したPythonのビットです。

だから、私の数字から何かが欠けています。誰かが私を正しい方向に向けることができますか？

バイアスされたランダムな 0 と 1 の無限ストリーム (たとえば、1 は既知の要因により 0 よりも一般的です) が理想的な乱数ジェネレーターである場合、それを (より短い) 無限ストリームに変換したいと思います。理想的ですが偏りもありません。

エントロピーの定義を調べると、理論上、入力の各ビットから取得できる出力のビット数を示すこのグラフが見つかります。

質問:ほぼ理想的に効率的なコンバーターを実際に実装する実用的な方法はありますか?

これがmathoverflowに属する数学の質問なのか、それともここに属するコンピュータサイエンスの質問なの かわからないので、お詫び申し上げます。

そうは言っても、私はデータ、情報、知識の根本的な違いを理解していると思います。私の理解では、情報にはデータと意味の両方が含まれています。私がはっきりしていないことの1つは、情報がデータであるかどうかです。情報は特別な種類のデータと見なされますか、それともまったく異なるものですか？

適切に使用されたワンタイム パッド暗号の暗号文は、暗号化されたメッセージに関するデータをまったく明らかにしないことを理解しています。

これは、ワンタイムパッドで暗号化されたメッセージと完全にランダムなノイズを区別する方法がないということですか? それとも、メッセージについて何も学べなくても、メッセージがあると判断する理論的な方法はありますか?

誰かがこのエントロピーの問題について私にいくつかの指針を与えることができることを願っています。

Xは、均一な整数分布0〜32（両端を含む）からランダムに選択されます。

各Xiの発生確率は等しいため、エントロピーH（X）=32ビットを計算します。

ここで、次の擬似コードが実行されるとします。

int r = rand（0,1）; //ランダムな整数0または1

r = r * 33 + X;

2つの変数rとXの間の相互情報量をどのように計算しますか？

相互情報量はI（X; Y）= H（X）-H（X | Y）として定義されますが、条件付きエントロピーH（X | Y）をこの問題に適用する方法がよくわかりません。

ありがとう

私は情報理論を勉強していますが、うまくいかないことが1つあります。

線形コードCと生成行列が与えられた場合、MIはCのすべての可能なコードワードを計算できることを私は知っています。

しかし、私は理解していません：

• パリティチェックマトリックスとはhttp://en.wikipedia.org/wiki/Parity-check_matrix
• 生成行列からパリティチェック行列を作成する方法

ポインタをいただければ幸いです。

ありがとう！