コルモゴロフ構造関数

1973 年、アンドレイ・コルモゴロフは、統計とモデル選択に対する非確率的アプローチを提案しました。各データを有限のバイナリ文字列とし、モデルをバイナリ文字列の有限集合とします。与えられた最大コルモゴロフ複雑度のモデルで構成されるモデル クラスを考えます。個々のデータ文字列のコルモゴロフ構造関数は、モデル クラスの複雑度レベルの制約と、データを含むクラス内のモデルの最小対数カーディナリティとの関係を表します。構造関数は、個々のデータ文字列のすべての確率的特性を決定します。つまり、制約されたモデル クラスごとに、真のモデルが検討中のモデル クラス内に存在するかどうかに関係なく、クラス内で最も適合する個々のモデルを決定します。従来のケースでは、確率分布を持つデータ セットについて説明し、特性は期待値のものです。対照的に、ここでは個々のデータ文字列と、焦点を当てた個々の文字列の特性を扱います。この設定では、特性は、従来のケースのように高い確率ではなく、確実に保持されます。コルモゴロフ構造関数は、個々のデータに対する個々のモデルの適合度を正確に定量化します。

コルモゴロフ構造関数は、アルゴリズム情報理論（コルモゴロフ複雑性理論とも呼ばれる）で使用され、複雑性が増すモデルを使用して文字列の構造を記述します。

構造関数はもともと1973年にタリンで開催されたソ連の情報理論シンポジウムでコルモゴロフによって提案されたが、その結果は公表されなかった^{[1] p. 182。しかし、その結果は1974年に[2]}で発表され、コルモゴロフ自身による唯一の記録となった。彼の最後の科学的発言の1つは（LAレビンによるロシア語からの翻訳）次の通りである。

各構成オブジェクトには、自然数 k の関数、つまり最大 k の複雑性の定義を可能にする x を含むセットの最小濃度の対数が対応しています。要素 x 自体が単純な定義を可能にする場合、関数は小さな k でも 0 になります。このような定義がない場合、要素は否定的な意味で「ランダム」です。ただし、関数が比較的小さな で値をとった場合、 が としてほぼ変化する場合にのみ、要素は肯定的に「確率的にランダム」になります。${\displaystyle \Phi_{x}(k)}$${\displaystyle \Phi}$${\displaystyle \Phi}$${\displaystyle \Phi_{0}}$${\displaystyle k=k_{0}}$${\displaystyle \Phi (k)=\Phi _{0}-(k-k_{0})}$

— コルモゴロフ、上記発表より

^{CoverとThomas [1]}で議論されている。VereshchaginとVitányi ^[3]でも広く研究されており、主要な特性も解明されている。コルモゴロフ構造関数は次のように表される。

${\displaystyle h_{x}(\alpha )=\min _{S}\{\log |S|:x\in S,K(S)\leq \alpha \}}$

ここで、は長さ のバイナリ文字列で、は の 想定モデル (長さ n の文字列のセット) であり、はのコルモゴロフ複雑度であり、 は想定の の複雑度を境界付ける非負の整数値です。明らかに、この関数は非増加であり、に達します。ここで、はに変更するために必要なビット数であり、は のコルモゴロフ複雑度です。 ${\displaystyle x}$${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle S}$${\displaystyle x}$${\displaystyle K(S)}$${\displaystyle S}$${\displaystyle \alpha}$${\displaystyle S}$${\displaystyle \log |\{x\}|=0}$${\displaystyle \alpha =K(x)+c}$${\displaystyle c}$${\displaystyle x}$${\displaystyle \{x\}}$${\displaystyle K(x)}$${\displaystyle x}$

を 含む集合を定義する。${\displaystyle S}$${\displaystyle x}$

${\displaystyle K(S)+K(x|S)=K(x)+O(1)}$。

この関数は、対角線Lと呼ばれる次式で定義される充足線の下では、一定の独立定数以上に減少することはありません。 ${\displaystyle h_{x}(\alpha )}$

${\displaystyle L(\alpha )+\alpha =K(x)}$。

特定の引数（たとえば、 の場合）に対して、のグラフによって に一定距離以内に近づきます。 これらの に対して、 が成り立ち、関連するモデル（ の証拠）は の最適セットと呼ばれ、ビットの記述はアルゴリズム的十分統計量です。慣例により、「コルモゴロフ複雑性」を「アルゴリズム的」と書きます。 アルゴリズム的十分統計量の主な特性は次のとおりです。が のアルゴリズム的十分統計量である場合、 ${\displaystyle h_{x}}$${\displaystyle \alpha =K(x)+c}$${\displaystyle \alpha }$${\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}$${\displaystyle S}$${\displaystyle h_{x}(\alpha )}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle x}$

${\displaystyle K(S)+\log |S|=K(x)+O(1)}$。

つまり、モデルを使用し、ビットの列挙体のインデックスをデータからモデルへのコードとして使用する 2 部構成の説明は、ビットの の最も短い 1 部構成のコードと同じくらい簡潔です。これは次のように簡単にわかります。 ${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle \log |S|}$${\displaystyle x}$${\displaystyle K(x)}$

${\displaystyle K(x)\leq K(x,S)+O(1)\leq K(S)+K(x|S)+O(1)\leq K(S)+\log |S|+O(1)\leq K(x)+O(1)}$、

簡単な不等式と十分性プロパティを使用すると、 であることがわかります。(たとえば、 が与えられた場合、 ビットで自己限定的に(その終わりを決定できる)記述できます。) したがって、におけるのランダム性不足は定数であり、これは が S の一般的な(ランダムな)要素であることを意味します。ただし、を含むモデルが十分統計ではない場合があります。 のアルゴリズム的十分統計量には、最適モデルであることの他に、 という追加のプロパティがあります。したがって、情報のコルモゴロフ複雑性対称性(におけるに関する情報は、x におけるに関する情報とほぼ同じです)により、 が成り立ちます。アルゴリズム的十分統計量は、によってほぼ完全に決定される最適モデルです。(は の最短プログラムです。) このような最小の に関連付けられたアルゴリズム的十分統計量は、アルゴリズム的最小十分統計量と呼ばれます。 ${\displaystyle K(x|S)=\log |S|+O(1)}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle \log |S|+O(1)}$ ${\displaystyle \log |S|-K(x|S)}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle K(x,S)=K(x)+O(1)}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$${\displaystyle K(S|x^{*})=O(1)}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x^{*}}$${\displaystyle x}$${\displaystyle \alpha }$

図に関して：MDL構造関数は以下で説明されます。適合度構造関数は、となるモデルのランダム性不足（上記参照）が最も少ないものです。この構造関数は、文字列xに対するモデル（xを含む）の適合度を与えます。適合度が低い場合、モデルはよく適合し、適合度が高い場合、モデルはよく適合しません。ある に対して となる典型的なモデルがあり、 はSに対して典型的（ランダム）です。つまり、はxに最もよく適合するモデルです。詳細については、^[1]、特に^[3]と^{[4]を参照してください。}${\displaystyle \lambda _{x}(\alpha )}$${\displaystyle \beta _{x}(\alpha )}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle \beta _{x}(\alpha )=0}$${\displaystyle \alpha }$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle x}$${\displaystyle S}$

グラフが少なくとも 45 度の角度で下降し、n で始まり、およそ で終わるという制約の下では、すべてのグラフ (引数と値の加法項まで) は、何らかのデータ x の構造関数によって実現され、その逆も同様です。グラフが最初に対角線に当たる場合、引数 (複雑さ) は最小の十分な統計量の引数です。この場所を決定することは計算不可能です。^{[3]を参照してください。}${\displaystyle K(x)}$${\displaystyle O(\log n)}$

構造関数は、複雑さの各レベルにおいて、ストリップ内の個々の文字列xに最適なモデルを、高い確率ではないが確実に選択することを可能にすることが証明されています。 ^[3]${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle O(\log n)}$

最小記述長(MDL) 関数: 与えられた最大コルモゴロフ複雑度 の集合のモデルクラスにおいて、モデルコスト K(S) と S 内の x のインデックスの長さからなる x の最小の 2 部構成コードの長さ ( S の複雑度の上限は) は、MDL 関数または制約付き MDL 推定量によって与えられます。 ${\displaystyle \alpha }$${\displaystyle \alpha }$

${\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}$

ここで、モデル S を使用した x の 2 部構成のコード全体の長さは次のようになります。 ${\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}$

構造関数によって、複雑さの各レベルにおいて、ストリップ内の個々の文字列xに対して最適なモデルSを高い確率ではない確実性で選択できることが証明されています。 ^[3]${\displaystyle \alpha }$${\displaystyle O(\log n)}$

上記で開発された数学は、 MDLの発明者であるヨルマ・リッサネンによってMDLの基礎として採用されました。^[5]

計算可能な確率分布のすべてについて、次のことが証明できる^[6]。 ${\displaystyle P}$

${\displaystyle -\log P(x)=\log |S|+O(\log n)}$。

例えば、長さ の文字列の集合上の計算可能な分布が である場合、それぞれの確率は です。コルモゴロフの構造関数は次のようになります。 ${\displaystyle P}$${\displaystyle S}$${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}$

${\displaystyle h'_{x}(\alpha )=\min _{P}\{-\log P(x):P(x)>0,K(P)\leq \alpha \}}$

ここで、x は長さ n のバイナリ文字列で、は に対する 想定モデル (長さの文字列の計算可能な確率) 、はのコルモゴロフ複雑度、 は 想定の の複雑度を境界付ける整数値です。明らかに、この関数は非増加でに達します。ここで、c はに変更するために必要なビット数、は のコルモゴロフ複雑度です。次に です。すべての複雑度レベルについて、関数は最大尤度(ML) のコルモゴロフ複雑度バージョンです。 ${\displaystyle -\log P(x)>0}$${\displaystyle P}$${\displaystyle n}$${\displaystyle x}$${\displaystyle K(P)}$${\displaystyle P}$${\displaystyle \alpha }$${\displaystyle P}$${\displaystyle \log |\{x\}|=0}$${\displaystyle \alpha =K(x)+c}$${\displaystyle x}$${\displaystyle \{x\}}$${\displaystyle K(x)}$${\displaystyle x}$${\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}$${\displaystyle \alpha }$${\displaystyle h'_{x}(\alpha )}$

構造関数によって、複雑さのレベルごとに、ストリップ内の個々の文字列に最適なモデルを、高い確率ではないが確実に選択できることが証明されています。 ^[3]${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle x}$${\displaystyle O(\log n)}$

MDL 関数: モデル コスト K(P) と の長さで構成される x の最小の 2 部構成コードの長さは、与えられた最大コルモゴロフ複雑度 の計算可能な確率質量関数のモデル クラスで、P の複雑度の上限は で、MDL 関数または制約付き MDL 推定量によって与えられます。 ${\displaystyle -\log P(x)}$${\displaystyle \alpha }$${\displaystyle \alpha }$

${\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}$

ここで、モデル P を使用した x の 2 部構成のコード全体の長さです。 ${\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}$

それぞれの複雑さのレベルにおいて、MDL関数は、大きな確率ではないが確実に、ストリップ内の個々の文字列xに対して最適なモデルPを選択できることが証明されています。 ^[3]${\displaystyle \alpha }$${\displaystyle O(\log n)}$

このアプローチは、コルモゴロフ複雑度を使用して、個々の有限シーケンスのレート歪みと個々の有限シーケンスのノイズ除去の理論に拡張できることが判明しました^[7]。実際の圧縮プログラムを使用した実験は成功しています。^[8]ここでの仮定は、自然データの場合、コルモゴロフ複雑度は、優れた圧縮プログラムを使用した圧縮バージョンの長さとそれほど変わらないというものです。

• Cover, TM; P. Gacs; RM Gray (1989). 「コルモゴロフの情報理論とアルゴリズムの複雑性への貢献」Annals of Probability . 17 (3): 840–865. doi : 10.1214/aop/1176991250 . JSTOR  2244387.
• Kolmogorov, AN; Uspenskii, VA (1987 年 1 月 1 日). 「アルゴリズムとランダム性」.確率理論とその応用. 32 (3): 389–412. doi :10.1137/1132060.
• Li, M., Vitányi, PMB (2008).コルモゴロフ複雑性とその応用への入門(第 3 版). ニューヨーク: Springer. ISBN 978-0387339986。{{cite book}}: CS1 maint: multiple names: authors list (link)特に、コルモゴロフ構造関数に関する401～431ページと、個々のシーケンスのレート歪みとノイズ除去に関する613～629ページ。
• Shen, A. (1999 年 4 月 1 日). 「コルモゴロフ複雑性と統計分析に関する議論」.コンピュータジャーナル. 42 (4): 340–342. doi :10.1093/comjnl/42.4.340.
• V'yugin, VV (1987). 「与えられた複雑性境界を持つ尺度に対する有限オブジェクトのランダム性欠陥について」.確率理論とその応用. 32 (3): 508–512. doi :10.1137/1132071.
• V'yugin, VV (1999 年 4 月 1日)。「有限バイナリ シーケンスのアルゴリズムの複雑さと確率的特性」。コンピュータ ジャーナル。42 (4): 294–317。doi :10.1093/ comjnl /42.4.294。