最小メッセージ長

最小メッセージ長( MML ) は、統計モデルの比較と選択のためのベイズ情報理論的手法です。^{[1]これは、}オッカムの剃刀の正式な情報理論の言い換えです。つまり、モデルが観測データに対する適合精度の尺度で同等であっても、データの最も簡潔な説明を生成するモデルが正しい可能性が高くなります (説明はモデルの記述と、記述されたモデルを使用したデータのロスレス エンコードで構成されます)。MML はChris Wallaceによって発明され、最初に「分類のための情報尺度」という重要な論文で紹介されました。^[2] MML は、理論的な構成概念としてだけでなく、実際に展開できる手法として意図されています。^{[3]これは、データをモデル化するために}チューリング完全な言語を使用する必要がない点で、関連するコルモゴロフ複雑性の概念とは異なります。^[4]

シャノンの「通信の数学的理論」 （1948 年）では、最適コードでは、確率 を持つイベントのメッセージ長（2 進数）は で与えられると述べられています。 ${\displaystyle E}$${\displaystyle \operatorname {長さ} (E)}$${\displaystyle E}$${\displaystyle P(E)}$${\displaystyle \operatorname {長さ} (E)=-\log _{2}(P(E))}$

ベイズの定理によれば、一定の証拠がある場合の（可変）仮説の確率は に比例し、条件付き確率の定義によりに等しくなります。このような事後確率が最も高いモデル（仮説）を求めます。モデルとデータの両方を一緒に表す（記述する）メッセージをエンコードするとします。 であるため、最も可能性の高いモデルは、このようなメッセージが最も短くなります。メッセージは の 2 つの部分に分かれます。最初の部分はモデル自体をエンコードします。2 番目の部分には、モデルによって処理されると観測データを出力する情報（たとえば、パラメータの値や初期条件など）が含まれます。 ${\displaystyle H}$${\displaystyle E}$${\displaystyle P(E|H)P(H)}$${\displaystyle P(H\land E)}$${\displaystyle \operatorname {長さ} (H\land E)=-\log _{2}(P(H\land E))}$${\displaystyle -\log _{2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E|H))}$

MML は、モデルの複雑さと適合度を自然かつ正確にトレードオフします。モデルが複雑になると、記述に時間がかかります (最初の部分が長くなります) が、データへの適合度は高くなります (2 番目の部分が短くなります)。したがって、MML メトリックでは、そのモデルが費用対効果を生まない限り、複雑なモデルは選択されません。

モデルが長くなる理由の 1 つは、さまざまなパラメータがより正確に記述されるため、より多くの桁数の伝送が必要になるという単純な理由です。MML の威力の多くは、モデル内のパラメータをどの程度正確に記述するかの処理と、これを実際に実現可能にするさまざまな近似値から生まれます。これにより、たとえば、多くのパラメータが不正確に記述されているモデルと、より少ないパラメータがより正確に記述されているモデルを、有効に比較することが可能になります。

• MML は、異なる構造のモデルを比較するために使用できます。たとえば、最も初期のアプリケーションは、最適なクラスの数を持つ混合モデルを見つけることでした。混合モデルにクラスを追加すると、常にデータの適合精度が向上しますが、MML では、クラスを定義するパラメーターをエンコードするために必要な追加ビットと比較してこれを考慮する必要があります。
• MML はベイズモデル比較の手法です。すべてのモデルにスコアが与えられます。
• MML はスケール不変であり、統計的に不変です。多くのベイズ選択法とは異なり、MML では長さの測定から体積への変更や、直交座標から極座標への変更は考慮されません。
• MML は統計的に一貫しています。パラメータあたりのデータ量が上限を超えている Neyman-Scott (1948) 問題や因子分析などの問題の場合、MML は統計的に一貫してすべてのパラメータを推定できます。
• MML は測定の精度を考慮します。MML はフィッシャー情報(Wallace-Freeman 1987 近似、または他の近似のその他のハイパーボリューム) を使用して、連続パラメータを最適に離散化します。したがって、事後分布は常に確率であり、確率密度ではありません。
• MML は 1968 年から使用されています。MML コーディング スキームは、教師なし分類、決定木とグラフ、DNA 配列、ベイジアン ネットワーク、ニューラル ネットワーク (現時点では 1 層のみ)、画像圧縮、画像と機能のセグメンテーションなど、さまざまな分布や多くの種類の機械学習向けに開発されてきました。

• アルゴリズム的確率
• アルゴリズム情報理論
• 文法誘導
• 帰納的推論
• 帰納的確率
• コルモゴロフ複雑度- 絶対複雑度（定数内、ユニバーサルチューリングマシンの特定の選択に依存する）; MMLは通常、計算可能な近似値である（^[4]を参照）
• 最小記述長– MML の 10 年後に開発された、おそらく異なる (非ベイジアン) 動機による代替手段。
• オッカムの剃刀

原著論文:

• Wallace、Boulton (1968年8 月)。「分類のための情報測定」。コンピュータ ジャーナル。11 (2): 185–194。doi : 10.1093 /comjnl/11.2.185。

書籍:

• Wallace, CS (2005 年 5 月)。最小メッセージ長による統計的および帰納的推論。情報科学と統計。Springer-Verlag。doi : 10.1007/0-387-27656-4。ISBN 978-0-387-23795-4。
• アリソン、L. (2018).オッカムの剃刀のコーディング. シュプリンガー. doi :10.1007/978-3-319-76433-7. ISBN 978-3319764320. S2CID  19136282。、MML の実装、およびソースコードについて説明します。

関連リンク:

• Chris Wallace の既知の出版物すべてへのリンク。
• Chris Wallace の出版物を検索できるデータベース。
• Wallace, CS; Dowe, DL (1999). 「最小メッセージ長とコルモゴロフ複雑度」. Computer Journal . 42 (4): 270–283. CiteSeerX  10.1.1.17.321 . doi :10.1093/comjnl/42.4.270.
• 「コルモゴロフ複雑性に関する特集号」。コンピュータジャーナル。42 （4）。1999年。^{[リンク切れ‍ ]}
• Dowe, DL; Wallace, CS (1997)。「最小メッセージ長による Neyman-Scott 問題の解決」。第 28 回インターフェイスシンポジウム、オーストラリア、シドニー。「コンピューティング サイエンスと統計」第 28 巻。614 ～ 618 ページ。
• MMLの歴史、CSWの最後の講演。
• Needham, S.; Dowe, D. (2001). 決定木誘導における効果的なオッカムの剃刀としてのメッセージ長(PDF)。第 8 回 AI と統計に関する国際ワークショップの議事録。pp. 253–260。(オッカムの剃刀がMML として解釈された場合にどのように機能するかを示します。)
• Allison, L. (2005 年 1 月). 「関数型プログラミングにおける機械学習とデータマイニングのモデル」. J​​ournal of Functional Programming . 15 (1): 15–32. doi : 10.1017/S0956796804005301 . S2CID  5218889.(MML、FP、Haskell コード)。
• Comley, JW; Dowe, DL (2005 年 4 月)。「第 11 章: 最小メッセージ長、MDL、非対称言語による一般化ベイジアン ネットワーク」。Grunwald, P.、Pitt, MA、Myung, IJ (編)。最小記述長の進歩: 理論とアプリケーション。MIT プレス。265 ～ 294 ページ。ISBN 978-0-262-07262-5。
• Comley, Joshua W.; Dowe, DL (2003 年 6 月 5 ～ 8 日)。「一般的なベイジアン ネットワークと非対称言語」。統計および関連分野に関する第 2 回ハワイ国際会議議事録。Comley & Dowe (2003、2005) は、離散値パラメータと連続値パラメータの両方を使用した MML ベイジアン ネットに関する最初の 2 つの論文です。

• Dowe, David L. (2010). 「MML、ハイブリッド ベイジアン ネットワーク グラフィカル モデル、統計的一貫性、不変性、一意性」(PDF)。科学哲学ハンドブック (第 7 巻: 統計哲学ハンドブック)。Elsevier。pp. 901–982。ISBN 978-0-444-51862-0。
• 最小メッセージ長 (MML)、LA の MML 紹介 (MML alt.)。
• 最小メッセージ長 (MML)、研究者、およびリンク。
• 「もう一つのMML研究ウェブサイト」。2017年4月12日時点のオリジナルよりアーカイブ。
• MML混合モデリングの Snob ページ。
• MITECS: Chris Wallace が MITECS の MML にエントリを書きました。(アカウントが必要です)
• mikko.ps: ヘルシンキのミッコ・コイヴィストによる短い紹介スライド
• 赤池情報量基準( AIC )モデル選択法、および MML との比較: Dowe, DL; Gardner, S.; Oppy, G. (2007 年 12 月)。「ベイズは破綻しない! ベイズ主義者にとって単純さが問題にならない理由」。Br . J. Philos. Sci . 58 (4): 709–754. doi :10.1093/bjps/axm033。