確率的コンプレクシティ (stochastic complexity)

いわゆる普通のエントロピーであるShannonエントロピーは,データの生成分布が機知のときの最短符号長. それに対し,ある確率モデルのクラスのいずれかからデータが生成されている場合,そのデータの最短符号長.

確率モデルのクラスからのモデル選択の一つである,データの最小符号長を実現するモデルを採用するMDL原理では,当所は二段階符号化に基づいていた.これを,以下のようなその他の符号化方法にも一般化するために,この確率的コンプレクシティの概念が導入された.

最尤符号化

\(k\)個の実数値パラメータ\(\Theta_k\)で記述される確率モデルを考え,このモデルを\(k=1,\ldots,M\)と変化させたときの確率モデルの族\(\mathcal{M}\)を考える.

この族から生成された\(N\)個のデータからなるデータ集合\(X^N\)が与えられたとする. このデータの\(\mathcal{M}\)で,データの生成確率が最大になるように\(\hat{k}\)と\(\hat{\Theta}_k\)を選んだときの,\(X^N\)の尤度を \(\Pr[X^N;\hat{k},\hat{\Theta}_k]\) と書く.

同じ大きさの全てのデータ集合についてのこの尤度の総和が\(1\)となるように正規化したときの\(X^n\)の符号長は次式になり,こうした符号化手法を最尤符号化 (maximum likelihood coding) と呼ぶ \[-\log\biggl(\frac{\Pr[X^N;\hat{k},\hat{\Theta}_k]}{\sum_{Y^N}\Pr[Y^N;\hat{k},\hat{\Theta}_k]}\biggr)\]

実際にはこの式の分母の計算は,一般には無理だが,漸近的に次式に等しくなることを利用して計算できる. \[-\log\Pr[X^N;\hat{k},\hat{\Theta}_k]+\frac{k}{2}\log\frac{N}{2\pi}+\log\int\sqrt{|I(\Theta)|}d\Theta+o(1)\] ただし,\(I(\Theta)\)はFisher情報行列

前半の\(-\log\text{尤度}+\frac{k}{2}\log N\)の項は二段階符号化を使ったときの符号長と一致する.

その他,BICとも同様の考えのベイズ符号化や,データを一個ずつ符号化する予測的符号化でも同様の式が得られることが知られる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-10-25 (月) 20:43:43