アルゴリズム情報理論における「情報」と「有用な情報」の違い

Question

によると ウィキペディア:

非公式には、アルゴリズム情報理論の観点から、文字列の情報コンテンツは、その文字列の可能な限り短い自己完結型表現の長さと同等です。

「有用な情報」の類似の非公式の厳密な定義は何ですか？なぜ「有用な情報」がより自然またはより基本的な概念とみなされないのか。素朴に純粋にランダムな文字列には、定義によりゼロ情報が含まれている必要があるように思われるため、標準の定義により最大の情報があると考えられているという事実に頭を巻き込もうとしています。

Answer 1

ここの中心的な概念はです コルモゴロフの複雑さ, 、そしてより具体的に 圧縮率. 。圧縮性の直感的な感覚を取得するには、2つの文字列$ a in mathbb {b}^*$および$ b in mathbb {b}^*$、ここで$ mathbb {b} = {0,1 } $。させて

$ a = 1010 $ $ 1010 $ 1010 $ 1010 $、および

$ b = 1011 $ $ 0110 $ $ 0111 $ 1001 $。

$ | a |に注意してください= | b | = 16 $。 $ a $または$ b $の情報をどのように定量化できますか？一般に、古典的な情報理論について考えると、長さの文字列を送信すると、平均して$ n $ビットが必要です。ただし、送信するために必要なビットの数を言うことはできません 明確 長さの文字列$ n $。

ランダムな文字列の情報コンテンツがゼロではないのはなぜですか？

よく見ると、実際には$ a = 10^8 $であることがわかります。ただし、$ B $がその構造に明らかなパターンがある場合、少なくともそれを言うのははるかに難しいです 思われる と 感じます $ a $よりもランダム。 $ a $でパターンを見つけることができるため、$ a $を簡単に圧縮し、16ドル未満のビットで表すことができます。同様に、$ b $のパターンを検出するのは簡単ではないため、それをそれほど圧縮することはできません。したがって、$ B $には$ A $よりも多くの情報があると言えます。さらに、ランダムな文字列の長さ$ n $には最大の情報があり、それを圧縮する方法がないため、$ n $ビット未満で表すことができます。

では、有用な情報は何ですか？

にとって 有用な情報, 、はい、チューリングマシン$ t $を使用した定義があります。 $ x in mathbb {b}^*$の有用な情報

$$ min_t space { space l（t） + c（x | t）：t in {t_0、t_1、... } }、$$

ここで、$ l（t）$は、チューリングマシン$ t $の自己制限エンコードの長さを示します。表記は、通常、$ c（x）$が$ x $ x $ x $ c（x | y）$のコルモゴロフの複雑さを示し、$ y $を与えられた$ x $の条件付きコルモゴロフの複雑さを示します。

ここで、$ t $は$ x $に含まれる有用な情報の量を具体化します。私たちが尋ねることができるのは、要件を満たすものの中から選択する$ t $です。問題は、最短のプログラム$ x^* $をパーツに分離することです$ x^* = pq $ $ p $は適切な$ t $を表します。これは実際に生まれたまさにそのアイデアです 最小説明長（MDL）.

Answer 2

「便利」を定義するのが難しいためかもしれません。メッセージが豊富なメッセージが豊富なメッセージ$ x $があるとします。これは、$ alpha $の$ alpha $の$ y $で最大で圧縮できるとします。直感的には、$ x $と$ y $には、同じ量の有用な情報が含まれています。実際、通常の定義に従って同じ量の情報が含まれています。ここで、$ y $と同じ長さの$ x $のプレフィックス$ z $を想像してください。 $ x $以外の有用な情報を含める必要があります。したがって、$ y $以下です。ただし、$ z $は圧縮し、$ y $ができないため、$ y $は$ z $よりも「ランダム」です。したがって、「有用な」情報を圧縮性に関連付けようとすると、次のパラドックスに遭遇する可能性があります。メッセージのプレフィックスは、メッセージ全体よりも高い「有用な」情報を持つ可能性があります。

Answer 3

それほど正式ではない観点から、「ランダム」という言葉から自分自身を切り離すと、本当にランダムなビットのセットが実際の意味で情報を保存しないことが正しいので、それは助けになると思います。 （名前のセットを暗号化して暗号化された値をお客様に送信した場合、コルモゴロフの複雑さは非常に高いかもしれませんが、名前を把握するのに役立ちません）。

しかし、このように考えてください。あなたが外国語でウェブサイトを見た場合（あなたがそれを話さないと仮定して、スウェーデン語など）、それは多かれ少なかれランダムに見えるでしょう。言葉にはいくつかの順序がありますが、それほどではありません。ただし、このようなテキストのWebページを見ると、123456123456123456123456などがある場合、より迅速に理解できるようになります。スウェーデン語を話さないと、スウェーデンのウェブページが「最初の6つの数字が連続して繰り返される」と同等のことを言ったとしても、おそらくもっと多くのことを得ることができるでしょう。ウェブサイトには同じ情報が含まれていますが、あなたにはランダムに見えます。また、スペースの量については、同じ情報を保存していても、スウェーデンのWebページよりも効率が低くなります。この情報はスウェーデン語にあるため、「便利」だとは思わないかもしれませんが、情報はまだそこにあります。

「情報」の概念は普遍的であることを意図しているため、ランダムに見えるもの、したがって役に立たないもののように見えるものは、他の誰かに多くの情報を保存することができます。情報の尺度は、文字列の本質的なプロパティであることを目的としており、あなたに意味があり、何が意味をなさないか、そしてあなたが解釈できないことに依存することはできません。

助けるかもしれないもう1つの（より技術的な）ポイントは、私がここで少し不誠実であるということです。 Juhoが指摘しているように、情報 は 誰がそれを解釈しているかを比較して定義されています。スウェーデンのウェブページは情報の手段としてまったく役に立たないかもしれませんが、スウェーデン語を話す人はそれが多くの情報を持っていると感じるかもしれません。定義はこれを反映しています。ただし、数学から、このウェブサイトをお客様に伝えるために最短（スペースで最も有益な）のウェブページの違いと、スウェーデン語を話す人に伝えることができる最短のウェブページの違いは、追加定数によってのみ異なる場合があることを知ることができます。なんで？あなたにとって、スウェーデン以外のスピーカーとして、あなたが理解できるページを保存する最短の方法は、「最初の6つの整数が連続して繰り返される」ことだからです。これはスウェーデン人よりもかなり長いかもしれません。 （ここで私と一緒にいて、スウェーデン語は非常に短く効率的であるのに対し、英語は非常に長く無駄であると仮定します）。

しかし、たとえあなたがスウェーデン語を話すことができたとしても、あなたは長さから添加物の定数を削減することしかできないでしょう！なんで？あなたはいつでもスウェーデン語と英語の辞書を買いに行くことができるからです。それから、スーパーショートスウェーデンのウェブページはあなたにとって理にかなっています。確かに、辞書がある場合にのみ理にかなっていますが、辞書には一定の長さがあります。したがって、$$（ mbox {英語での情報の最も効率的な表現}） leq（ mbox {スウェーデン語の最も効率的な表現}） +（ mbox {スウェーデン語 - 英語辞書の長さ}）$$。これはあなたの元の質問から少しトピックになっていますが、私がやろうとしているポイントは、誰が情報を読んでいるのかはそれほど重要ではないということです。ランダムに見えるスウェーデンのウェブページはあなたにとって「有用」ではありませんでしたが、他の人にとっては「有用」であり、あなたはそれを自分で利用することができないことから一定の量の情報に過ぎません。