最小説明長

最小記述長( MDL ) は、データの最も短い記述が最適なモデルであるというモデル選択の原則です。MDL 方式は、データ圧縮の観点から学習し、オッカムの剃刀の数学的応用として説明されることもあります。MDL 原則は、データの単一モデルを明示的に識別することなく、推定や順次予測など、他の形式の帰納的推論および学習に拡張できます。

MDL は主に情報理論に起源を持ち、統計学、理論計算機科学、機械学習、さらに狭義には計算学習理論の一般分野でさらに発展してきました。

歴史的には、定名詞句「最小記述長原則」には、記述の意味に応じて異なる、しかし相互に関連した用法があります。

• 情報理論の中心概念であるヨルマ・リッサネンの学習理論では、モデルは統計的仮説であり、記述は普遍的なコードとして定義されます。
• 1978年にリッサネンが行った^[1]短い説明を自動的に導き出す実用的な最初の試みは、ベイズ情報量基準(BIC)に関連しています。
• アルゴリズム情報理論では、データ シーケンスの記述長は、そのデータ セットを出力する最小のプログラムの長さです。この文脈では、これは「理想化された」MDL 原理とも呼ばれ、ソロモンオフの帰納的推論理論と密接に関連しています。ソロモンオフの帰納的推論理論では、データ セットの最適なモデルは、その最短の自己解凍アーカイブによって表されると考えられています。

利用可能なデータの最小長の記述を最良モデルとして選択することは、オッカムの剃刀として特定された原則に従います。コンピュータ プログラミングの出現以前は、そのような記述を生成することは科学理論家の知的労働でした。コンピュータ時代に比べてはるかに形式的ではありませんでした。2 人の科学者が理論上の意見の相違を抱えていた場合、彼らがオッカムの剃刀を正式に適用して理論を選択することはほとんどありませんでした。彼らは異なるデータ セットを持ち、おそらく異なる記述言語を持っていました。それでも、オッカムの剃刀はどのモデルが最良かを判断するための非公式なガイドであったため、科学は進歩しました。

形式言語とコンピュータ プログラミングの出現により、オッカムの剃刀は数学的に定義されました。データのビットとしてエンコードされた特定の観測セットのモデルは、そのデータを出力するコンピュータ プログラムの形式で作成できます。その後、オッカムの剃刀は、このアルゴリズム情報のビットで測定された最短のプログラムを最適なモデルとして正式に選択できます。

混乱を避けるために、MDL 原則には、モデルを具体化するプログラムを機械が作成したことを示唆するものは何もないことに注意してください。完全に人間の産物である可能性があります。MDL 原則は、コンピューターで実行される記述が人間の産物、機械の産物、またはその組み合わせの産物であるかどうかに関係なく適用されます。MDL 原則では、実行時に最も短い記述がエラーなしで元のデータ セットを生成すること のみが要求されます。

コンピュータ プログラムにおけるプログラムとリテラル データの区別は、すべての形式的な記述に適用され、記述の「 2 つの部分」と呼ばれることもあります。統計的な MDL 学習では、このような記述は2 部構成のコードと呼ばれることがよくあります。

MDL は、アルゴリズム (マシン) が説明を生成する機械学習に適用されます。学習は、アルゴリズムが同じデータ セットのより短い説明を生成するときに発生します。

ただし、データ セットの理論上の最小記述長 (コルモゴロフ複雑度と呼ばれる) は計算できません。つまり、アルゴリズムがランダムな偶然でデータ セットを出力するすべてのプログラムの中で最も短いプログラムを生成したとしても、自動定理証明器はそのような短いプログラムが存在しないことを証明できません。それでも、データ セットを出力する 2 つのプログラムがある場合、MDL 原則では、2 つのうち短い方を最良のモデルとして選択します。

近年、統計的データモデルではなくアルゴリズム的データモデルの機械学習MDL学習は、データ、計算リソース、理論の進歩の可用性が高まるにつれて、ますます注目を集めています。^{[2] [3]これらのアプローチは、急成長している}汎用人工知能の分野から情報を得ています。マービン・ミンスキーは死の直前に、この研究分野を強く支持し、次のように述べています。^[4]

ゲーデル以来最も重要な発見は、チャイティン、ソロモノフ、コルモゴロフによるアルゴリズム的確率という概念の発見だと私は思います。これは、一連の経験に基づいて予測を行う方法に関する新しい基本的な理論であり、素晴らしい理論で、誰もが学ぶべきものですが、1 つ問題があります。それは、この理論が予測するものを実際に計算できないことです。難しすぎて、無限の作業量を必要とするからです。しかし、チャイティン、コルモゴロフ、ソロモノフの理論に実用的な近似値を作成することは可能であり、現在のどの理論よりも優れた予測を行うことができます。誰もがそのすべてを学び、残りの人生をかけて取り組むべきです。

— 理解の限界に関するパネルディスカッション、ワールドサイエンスフェスティバル、ニューヨーク、2014年12月14日

任意のデータ セットは、有限の (たとえば、バイナリの)アルファベットの記号の文字列で表すことができます。

[MDL原則]は、次のような洞察に基づいています。与えられたデータセット内の規則性は、データを圧縮するために使用できます。つまり、データを文字通り記述するために必要な記号よりも少ない記号を使用してデータを記述できます。(Grünwald、2004) ^[5]

これを基に、1978 年に Jorma Rissanen は、アルゴリズム情報ではなく統計的情報の概念を使用する MDL 学習アルゴリズムを発表しました。過去 40 年間で、これは、ベイズモデルの選択と平均化、Lasso や Ridge などのペナルティ法などとの関連を持つ、統計および機械学習手順の豊富な理論に発展しました。Grünwald と Roos (2020) ^{[6] は}、すべての最新の開発を含む概要を示しています。Rissanen は、すべての統計学習はデータの規則性を見つけることであり、データの規則性を説明する最良の仮説は、データを統計的に最も圧縮できる仮説でもあるという考えから始めました。他の統計手法と同様に、データを使用してモデルのパラメーターを学習するために使用できます。ただし、通常、標準的な統計手法では、モデルの一般形式は固定されていると想定しています。MDL の主な強みは、モデルの一般形式とそのパラメーターの選択にも使用できることです。関心のある量 (モデルのみの場合もあれば、パラメータのみの場合もあり、その両方を同時に含む場合もあります) は仮説と呼ばれます。基本的な考え方は、最初に検討対象の仮説セット内の仮説をエンコードし 、次に「 の助けを借りて」エンコードすることで、長さのあるデータをエンコードする(ロスレスの) 2 段階コードを検討することです。最も単純な文脈では、これは単に「 によって行われた予測からのデータの偏差をエンコードする」ことを意味します。 ${\displaystyle D}$${\displaystyle {L(D)}}$${\displaystyle H}$${\displaystyle {\cal{H}}}$${\displaystyle D}$${\displaystyle H}$${\displaystyle H}$

$${\displaystyle {L(D)}=\min _{H\in {\cal {H}}}\ (\ L(H)+L(D|H)\ )\ }$$

そして、この最小値を達成することが、データ を最もよく説明するものと見なされます。簡単な例として、回帰問題を考えてみましょう。データは点のシーケンスで構成され、集合はからまでのすべての多項式の集合である可能性があります。次数 (たとえば) の多項式を記述するには、まずパラメータをある精度で離散化する必要があります。次に、この精度 (自然数) を記述する必要があります。次に、次数(別の自然数) を記述し、最後のステップでパラメータを記述する必要があります。合計の長さは になります。次に、x 値に固定コードを使用して の点を記述し、次に偏差のコードを使用します。 ${\displaystyle H}$${\displaystyle D}$${\displaystyle D}$${\displaystyle D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$${\displaystyle {\cal{H}}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle H}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle L(H)}$${\displaystyle D}$${\displaystyle n}$${\displaystyle y_{i}-H(x_{i})}$

実際には、確率モデルがよく使用されます (ただし常に使用されるわけではありません) 。たとえば、各多項式を対応する条件付き分布に関連付けて、が平均と、固定または自由パラメータとして追加できる分散で正規分布していることを表します。次に、仮説のセットは、多項式を持つ線形^{[説明が必要]}モデルという仮定に簡略化されます。 ${\displaystyle H}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle H(X)}$${\displaystyle \sigma ^{2}}$${\displaystyle {\cal {H}}}$${\displaystyle Y=H(X)+\epsilon }$${\displaystyle H}$

さらに、多くの場合、特定のパラメータ値に直接関心があるわけではなく、たとえば多項式の次数だけに興味があります。その場合、を に設定します。ここで、各 は、データが j 次多項式として最もよく記述されるという仮説を表します。次に、仮説が与えられたデータを、仮説がデータによく適合する場合は常にコード長が短くなるように設計された1 部構成のコードを使用してコード化します。このようなコードの設計は、ユニバーサル コーディングと呼ばれます。使用できるユニバーサル コードにはさまざまな種類があり、長いデータ シーケンスでは同様の長さになることが多いですが、短いデータ シーケンスでは長さが異なります。「最良」 (ミニマックス最適性プロパティがあるという意味で) は、正規化最大尤度(NML) コードまたはShtarkovコードです。非常に便利なコードのクラスは、ベイズ周辺尤度コードです。分布の指数族の場合、Jeffreys 事前分布が使用され、パラメータ空間が適切に制限されている場合、これらは NML コードと漸近的に一致します。これにより、MDL理論は客観的ベイズモデル選択と密接に関係するようになり、ベイズモデル選択においても、異なる理由からではあるが、ジェフリーズの事前分布が採用されることがある。モデル選択に対するMDLアプローチは、多数のサンプルに対して 「 BICアプローチと形式的に同一の選択基準を与える」^{[7] 。}${\displaystyle {\cal {H}}}$${\displaystyle {\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}}$${\displaystyle {\cal {H}}_{j}}$${\displaystyle D}$${\displaystyle {\cal {H}}_{j}}$${\displaystyle H\in {\cal {H}}_{j}}$${\displaystyle L(D|H)}$

コインを 1000 回投げ、表と裏の回数を記録します。次の 2 つのモデル クラスを考えます。

• 1 つ目は、表の場合は 0、裏の場合は 1 で結果を表すコードです。このコードは、コインが公平であるという仮説を表します。このコードによるコードの長さは常に 1000 ビットです。
• 2 番目は、特定のバイアスを持つコインに効率的なすべてのコードで構成され、コインが公平ではないという仮説を表します。表が 510 回、裏が 490 回観測されたとします。この場合、2 番目のモデル クラスの最適なコードによるコード長は 1000 ビット未満になります。

このため、単純な統計手法では、データのより適切な説明として 2 番目のモデルを選択する可能性があります。ただし、MDL アプローチでは、最良のコードを使用するのではなく、仮説に基づいて単一のコードを作成します。このコードは、正規化された最大尤度コードまたはベイジアン コードです。このようなコードを使用すると、2 番目のモデル クラスに基づく合計コード長は 1000 ビットより大きくなります。したがって、MDL アプローチに従うと、2 番目のモデル クラスの最良の要素がデータにより適合しているにもかかわらず、偏ったコインの仮説を裏付ける十分な証拠がないという結論に必然的に至ります。

MDL 理論の中心となるのは、コード長関数と確率分布の間の1 対 1 の対応です(これは、クラフト・マクミラン不等式に従います)。任意の確率分布 について、の長さ (ビット単位)が に等しくなるようなコードを構築できます。このコードは、予想されるコード長を最小化します。逆に、コード が与えられた場合、同じことが成り立つような確率分布を構築できます(ここでは丸めの問題は無視します)。言い換えると、効率的なコードを探すことは、適切な確率分布を探すことと同じです。 ${\displaystyle P}$${\displaystyle C}$${\displaystyle C(x)}$${\displaystyle -\log _{2}P(x)}$${\displaystyle C}$${\displaystyle P}$

統計的 MDL の記述言語は計算上は普遍的ではありません。そのため、原理的にも再帰的な自然プロセスのモデルを学習することはできません。

統計的MDL学習は、前述のコードと確率分布の対応を通じて、確率論や統計と非常に密接に結びついています。このため、一部の研究者はMDLをベイズ推論と同等と見なしています。MDLにおけるモデルとデータのコード長は、ベイズフレームワークにおける事前確率と周辺尤度にそれぞれ対応しています。^[8]

ベイズ機構は効率的な MDL コードの構築に役立つことが多いが、MDL フレームワークはベイズ的でない他のコードにも対応している。一例としては、現在の MDL 理論で中心的な役割を果たしているがベイズ推論には同等のものがないShtarkov正規化最大尤度コードが挙げられる。さらに、Rissanen は真の データ生成プロセスについて仮定を立てるべきではないと強調している。実際には、モデルクラスは現実を単純化したものであり、客観的な意味で真実であるコードや確率分布は含まれていないのが一般的である。^{[9] [自費出版のソース? ] [10]}最後に言及した参考文献で、Rissanen は MDL の数学的基礎をコルモゴロフ構造関数に基づいている。

MDLの哲学によれば、ベイズ法は、悪い結果につながるような危険な事前確率に基づいている場合は却下されるべきである。MDLの観点から許容できる事前確率は、いわゆる客観的ベイズ分析でも好まれる傾向があるが、その動機は通常異なる。^[11]

リッサネンの学習への情報理論的アプローチは、最初のものではありませんでした。1968 年にはすでに、ウォレスとボールトンが最小メッセージ長(MML) と呼ばれる関連概念を開拓していました。MDL と MML の違いは、現在も混乱の原因となっています。表面的には、これらの方法はほとんど同じように見えますが、特に解釈において、いくつかの重要な違いがあります。

• MML は完全に主観的なベイジアン アプローチです。つまり、データ生成プロセスに関する自分の信念を事前分布の形で表現するという考えから始まります。MDL は、データ生成プロセスに関する仮定を回避します。
• どちらの方法も2 部構成のコードを使用します。最初の部分は、モデル クラスのインデックス (モデル選択) やパラメーター値 (パラメーター推定) など、学習しようとしている情報を常に表します。2 番目の部分は、最初の部分の情報が与えられたデータのエンコードです。これらの方法の違いは、MDL の文献では、不要なパラメーターをコードの 2 番目の部分に移動し、いわゆる 1 部構成のコードを使用してデータで表すことができるようにすることが提唱されていることです。1 部構成のコードの方が、2 部構成のコードよりも効率的であることがよくあります。MML の元の記述では、すべてのパラメーターが最初の部分にエンコードされているため、すべてのパラメーターが学習されます。
• MML フレームワークでは、各パラメータは、最適な全体メッセージ長になる精度で正確に記述されます。前述の例は、あるパラメータが当初はモデルに「おそらく役立つ」と考えられていたが、その後、データの説明に役立たないことが判明した場合に発生する可能性があります (このようなパラメータには、そのパラメータが役に立たないことが判明する (ベイジアン) 事前確率に対応するコード長が割り当てられます)。MDL フレームワークでは、モデルの比較よりもモデル クラスの比較に重点が置かれており、このようなパラメータを明示的に含むモデルのクラスと、パラメータを含まない他のクラスを比較することで、同じ問題に取り組む方が自然です。違いは、同じ結論に達するために適用される仕組みにあります。

• アルゴリズム的確率
• アルゴリズム情報理論
• 帰納的推論
• 帰納的確率
• レンペル・ジヴ複雑性

• ヘルシンキ大学による、Web 上の最小説明長。読み物、デモンストレーション、イベント、MDL 研究者へのリンクが掲載されています。
• Jorma Rissanen のホームページ。MDL に関する講義ノートやその他の最新資料が掲載されています。
• 最小記述長の進歩、MIT Press、ISBN 0-262-07262-9。