## 定義 **最小記述長原理**（Minimum Description Length; MDL）は、データ中の規則性を圧縮可能性として捉え、候補モデルのうちデータを最も短く記述するものを選ぶ帰納推論の原理である。粗い二部符号では、仮説 \(H\) とデータ \(D\) について \[ L(H)+L(D\mid H) \] を最小化する。確率モデルでは \(L(D\mid H)=-\log P(D\mid H)\) とし、仮説の短さとデータへの適合度をビット単位で比較する。(Source: [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) 現代的なrefined MDLは、任意の仮説符号を足し合わせるだけではない。モデル \(\mathcal M\) に相対的な普遍符号を設計し、事後的な最尤分布に対する最悪ケースregretを最小化する。正規化最尤（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) \] となり、最尤適合とparametric complexityの和を最小化する。複雑なモデルは多様なデータ列へ高い最尤確率を与えられるため、より大きい複雑度を負担する。(Source: [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) MDLのOccam選好は「真の世界は単純である」という主張ではない。小標本では柔軟すぎるモデルの最尤推定が偶然変動を再現しやすいため、単純なモデルを選ぶという推論戦略である。標本が増えれば選ばれるモデルの複雑度も増えうる。(Source: [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) ## 横断的知見 - [[@2026__30papers__Kolmogorov Complexity]]が扱う最短プログラムは、あらゆる計算可能な規則性を記述できる理想的な基準だが計算不能である。[[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]の実用MDLは、記述言語を問題固有のモデルへ制限し、普遍符号とminimax regretを使うことで、理想的な最短記述を計算可能なモデル選択へ縮約する。したがってMDLの「最短」は絶対的なコルモゴロフ複雑性ではなく、選んだモデル集合に相対的である。(Source: [[@2026__30papers__Kolmogorov Complexity]], [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) - [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]]はgzip圧縮サイズを複雑性の計算可能な上界として使うが、これは任意の実用圧縮器による記述長であり、refined MDLのNMLとは異なる。前者は特定圧縮器が発見できた規則性を測り、後者は明示した確率モデル内で事後最適符号に対するregretを制御する。どちらもモデル／符号選択に相対的だが、保証する対象が異なる。(Source: [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]], [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) - [[@2026__30papers__Variational Lossy Autoencoder]]では、VAEの負の変分下限がbits-back期待符号長に一致し、近似事後分布と真の事後分布の差が追加符号長になる。[[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]の普遍符号と比べると、変分推論は計算可能な符号をニューラル生成モデル上で最適化する一方、その符号長には近似推論の非効率が含まれる。またVLAEの潜在情報量だけでは局所詳細のデコーダー符号長を数えていないため、潜在ボトルネックの短さとデータ全体のMDLは別の量である。(Source: [[@2026__30papers__Variational Lossy Autoencoder]], [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) - [[@2026__30papers__Keeping Neural Networks Simple by Minimizing the Description Length of the Weights]]は、重み事後分布と符号化事前分布のKLを重みのbits-back符号長として使う。これは[[変分ベイズニューラルネットワーク]]の目的関数をMDLとして読む初期例であり、固定精度・固定ガウスの特殊例からweight decayも導く。一方、データから学習した混合事前分布のパラメータ符号長を無視し、最小総記述長が相対誤差約1.0の退化解を選んだ。refined MDLから見ると、符号化対象をすべて数え、符号選択の主観性を制御しない「粗いMDL」が予測性能と乖離しうる具体例である。(Source: [[@2026__30papers__Keeping Neural Networks Simple by Minimizing the Description Length of the Weights]], [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]) ## 未解決の問い - NMLの正規化項が無限大になるモデルで、meta-two-part code、renormalized NML、条件付きNMLのどれを選ぶべきか。 - 高次元・小標本でparametric complexityの漸近式が不正確なとき、計算可能性とminimax regret保証を両立する近似は何か。 - 候補モデルがデータ生成過程を十分に近似しないmisspecification下で、MDLが不合理なモデルを選ぶ条件をどう検出し、非ad hocに補正できるか。 - モデル集合の切り分け自体が複数ありうるとき、異なる切り分け間の主観性をどこまで不変化できるか。 - ニューラルネットワークのように最尤解や正規化項を計算できない大規模モデルで、重みの記述長、予測符号長、実際の汎化性能をどう整合させるか。 - 変分推論の近似誤差による追加符号長と、NMLのminimax regretを同じモデル上で比較できる条件は何か。 ## 関連 - [[コルモゴロフ複雑性]] — 理想化MDLが用いる計算不能な最短プログラム長 - [[Peter Grünwald]] — refined MDLを体系化したチュートリアルの著者 - [[変分損失性オートエンコーダ]] — bits-back符号長を使い、潜在表現とデコーダーへ情報を分担させる生成モデル - [[変分ベイズニューラルネットワーク]] — 重み分布のKLをモデル符号長として最適化する - [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] — 汎用圧縮器を複雑性代理へ用いた例 ## 出典 - [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]] - [[@2026__30papers__Kolmogorov Complexity]] - [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] - [[@2026__30papers__Variational Lossy Autoencoder]] - [[@2026__30papers__Keeping Neural Networks Simple by Minimizing the Description Length of the Weights]]