@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle

# A Tutorial Introduction to the Minimum Description Length Principle > [!abstract] 概要 > 30papers が、「データをどれだけ圧縮できるか」でモデルを選び、学習を最短記述の発見として捉える入門として選んだ [[Peter Grünwald]] のチュートリアルである。原典は、[[コルモゴロフ複雑性]]に基づく理想化MDLから、二部符号、普遍符号、正規化最尤、逐次予測までを接続し、[[最小記述長原理]]を概念面と数理面の両方から整理する。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]; [30papers](https://30papers.com/papers/mdl-principle-tutorial/); [arXiv](https://arxiv.org/abs/math/0406077)) ## ソース情報 - **30papers 掲載名**: A Tutorial Introduction to the Minimum Description Length Principle - **30papers 上の著者表記**: Peter Grunwald - **30papers 上の年**: 2004 - **30papers の位置づけ**: 圧縮性能でモデルを選び、学習を最短記述の発見として扱う読みやすい入門 - **原典**: [arXiv:math/0406077](https://arxiv.org/abs/math/0406077) - **著者**: [[Peter Grünwald]] - **提出日**: 2004-06-04 - **分量**: 80頁、2章、5図 - **分野**: 統計理論、情報理論、機械学習 arXiv HTMLと30papersは著者名をASCIIの「Peter Grunwald」と表示するが、論文PDFは「Peter Grünwald」と表記する。本文は、2005年刊行予定だった『Advances in Minimum Description Length: Theory and Applications』の冒頭2章を拡張したものである。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## 学習と圧縮データ中の規則性は、そのデータを逐語的に記録するより短い記述へ変換できる。周期列、偏った二値列、物理法則に従う測定値、文法に従う自然言語は、それぞれ異なる種類の規則性を圧縮へ利用できる。MDLは「学習」を「規則性の発見」と捉え、最もよくデータを圧縮する仮説または仮説集合を選ぶ。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) 理想化MDLは、データを出力して停止する最短プログラム、すなわち[[コルモゴロフ複雑性]]に基づく。しかし最短プログラムは計算不能であり、小標本では記述言語に由来する加法定数も支配的になる。実用MDLは、問題領域に応じて表現力を制限した計算可能な記述方法へ縮約するため、選んだモデルでは発見できない規則性が残る。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## モデル選択と二部符号粗い二部符号MDLは、仮説 \(H\) とデータ \(D\) に対して \[ L(H)+L(D\mid H) \] を最小化する。確率仮説では \(L(D\mid H)=-\log P(D\mid H)\) とし、仮説の短さとデータへの適合度を同じビット単位で比較する。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ![[_attachments/30papers-mdl-principle-tutorial/fig01-model-selection-tradeoff.png]] Figure 1.1。左は単純すぎる一次多項式、中央は観測点へ過剰適合する高次多項式、右は小さい非ゼロ誤差と低い複雑度を釣り合わせる三次多項式である。MDLのOccam選好は「世界は単純である」という主張ではなく、限られた標本では小さいモデルの方が未知データへの予測を信頼しやすいという推論戦略である。(Source: [原典 Figure 1.1](https://arxiv.org/pdf/math/0406077)) 粗い二部符号では、データ符号は確率から原理的に決められる一方、仮説符号の設計指針が不足する。固定した任意の符号でも広い条件下で漸近的一致性は得られるが、小標本では符号選択が結果を大きく左右しうる。この問題が、二部符号を普遍符号の一例へ位置づけ直すrefined MDLの動機になる。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) > [!caution] 「最短記述」の意味 > 30papersの紹介文は学習を「最短記述の発見」と要約するが、実用MDLは万能言語での文字どおりの最短プログラムを計算する方法ではない。また、任意の \(L(H)+L(D\mid H)\) を最小化すればよいわけでもない。原典のrefined MDLは、制限したモデルに相対的な普遍符号を設計し、符号の恣意性をminimax regretで抑える。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## 普遍符号と正規化最尤モデル \(\mathcal M\) のどの分布がデータを最も短く符号化するかは、データを見るまで分からない。普遍符号は、事後的に最適だった分布の符号長へ小さい追加長で近づく。二部符号、ベイズ混合、正規化最尤（Normalized Maximum Likelihood; NML）、逐次予測符号は、いずれもモデルに相対的な普遍符号である。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) 普遍分布 \(\bar P\) のregretは、データを見た後で選べた最尤分布に比べて余分に必要なビット数である。最悪ケースregretを一意に最小化するNML分布は、 \[ \bar P_{\mathrm{nml}}(x^n)= \frac{P(x^n\mid\hat\theta(x^n))} {\sum_{y^n}P(y^n\mid\hat\theta(y^n))} \] である。分母の対数 \[ \mathrm{COMP}_n(\mathcal M)= \log\sum_{y^n}P(y^n\mid\hat\theta(y^n)) \] はparametric complexityであり、多様なデータ列へよく適合できるモデルほど大きくなる。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) したがってNML符号長は、 \[ -\log \bar P_{\mathrm{nml}}(x^n\mid\mathcal M) =-\log P(x^n\mid\hat\theta(x^n))+\mathrm{COMP}_n(\mathcal M) \] となる。最尤適合の良さとモデルの柔軟性が、同じビット単位の二項として現れる。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## refined MDL 有限個のモデルでは、NMLによるデータ符号長が最短のモデルを選ぶ。無限個のモデルではモデル索引の符号長も加える。モデル内では可能ならNMLを使い、NMLが未定義または計算困難なら、minimax regretに近い別の普遍モデルを使う。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ![[_attachments/30papers-mdl-principle-tutorial/fig02-refined-mdl-principle.png]] Figure 2.4。refined MDLは、比較するモデルを明示的に符号化し、各モデル内の分布をNMLまたはそれに近い一部符号で暗黙的に符号化する。モデル間とモデル内の分布を、可能な限り同等に扱うことが設計原理である。(Source: [原典 Figure 2.4](https://arxiv.org/pdf/math/0406077)) refined MDLは、圧縮、モデルが適合できるデータ列の数え上げ、ベイズ混合との漸近関係、逐次予測における累積log lossという少なくとも四つの解釈を持つ。逐次解釈では過去だけから次の観測を予測するため、学習に使った同じデータ上で最尤値を評価する過学習を避ける。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## 他手法との関係正則な指数型分布族では、Jeffreys事前分布によるベイズ周辺尤度とNMLは漸近的に近づく。しかしMDLはベイズ混合だけでなくNMLや逐次予測を許し、事前分布を主観的信念ではなく短い符号を作る道具として扱える。そのため「MDLはBayesの特殊例」ではない。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) \[ -\log P(x^n\mid\hat\theta(x^n))+\frac{k}{2}\log n \] は正則条件、固定パラメータ数、大標本で得られる近似であり、BICとして知られる。パラメータ数が標本数とともに増える場合や小標本ではNML・Bayesと異なるモデルを選びうるため、本文は「MDL = BIC」という同一視を否定する。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) 逐次MDLは交差検証と似るが、未来を過去の予測へ使わず、各観測を一度だけ予測する。MMLは常に二部符号を使い、主観的事前分布の下で期待絶対符号長を最小化するのに対し、MDLのNMLは最悪ケース相対符号長を最小化する。(Source: [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]]) ## 評価 ### 強み - 適合度とモデルの柔軟性をビットという同じ単位で比較する。 - 「真の分布が候補モデル内にある」と仮定せず、観測データとモデルだけで解釈できる。 - NMLのminimax regretにより、粗い二部符号の恣意性を大きく減らす。 - 圧縮、数え上げ、ベイズ、逐次予測という複数の独立した解釈を持つ。 - モデルの構造とパラメータを同時に選び、過学習を原理内で扱う。 ### 限界 - NMLの正規化項は、ガウス位置モデルなどで無限大になりうる。 - parametric complexityの漸近近似は小標本や高次元で不正確になりうる。 - NMLが計算困難な場合、逐次法や精密な二部符号による近似が必要になる。 - 候補モデルがデータ生成過程を十分に近似しないmisspecification下で、MDLとBayesが不合理に振る舞う場合がある。 - 無限個のモデルやモデル族の分割では、穏やかながら主観性が残る。 ## 関連 - 中心概念: [[最小記述長原理]] - 理想化された最短記述: [[コルモゴロフ複雑性]] - 著者: [[Peter Grünwald]] - 実用圧縮器を複雑性代理に使う例: [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] ## 出典 - [[.raw/articles/30papers-mdl-principle-tutorial-2026-07-28]] - [30papers: A Tutorial Introduction to the Minimum Description Length Principle](https://30papers.com/papers/mdl-principle-tutorial/) - [arXiv abstract](https://arxiv.org/abs/math/0406077) - [arXiv PDF](https://arxiv.org/pdf/math/0406077)