情報論的学習理論5 | moskomule log

情報論的学習理論5

MDL規準は

\[\begin{aligned} \mathrm{MDL}_k(x^n) &=-\ln p_{\mathrm{NML}}(x^n)\cr &=-\ln p(x^n;\theta)+\ln\sum_{x^n} p(x^n;\theta) \end{aligned}\]

であり,最右辺の第1項が情報量,第2項がparametric complexityという情報量と同じ尺度の量でこれを用いるのがMDLの肝要であった.ただしこの第2項の計算は困難であって漸近近似を使う方法と厳密計算を行う方法が知られている.

後者は,つまり厳密計算できる問題のクラスは限定されておりg函数を使った手法と漸化式を用いた方法がある.

g函数

確率密度函数を

\[p(x^n;\theta)=p(x^n|\hat{\theta}(x^n))g(\hat{\theta}(x^n);\theta)\]

と分解する.ただし$\displaystyle p(x^n|\hat{\theta})=\frac{p(x^n;\theta)}{g(\hat{\theta};\theta)}$で

\[g(\bar{\theta};\theta)=\sum_{x^n;\hat{\theta}(x^n)=\bar{\theta}}p(x^n;\theta)=\sum_{x^n} p(x^n;\theta)\delta(\hat{\theta}(x^n)-\theta)\]

である.この$\bar{\theta}$に関する確率密度函数をg函数と呼ぶ.実際,

\[\int g(\bar{\theta};\theta)d\theta=\int d\theta (\sum_{x^n;\hat{\theta}(x^n)=\bar{\theta}}p(x^n;\theta))=\sum_{x^n}p(x^n;\theta) = 1 \]

であるから確率密度函数である.

MDK規準の性質

情報の真の分布が既知であればシャノンの符号化定理を用いることができるのであった.未知の時には以下が成り立つ.

定理(Rissarrenの不等式)

中心極限定理を仮定する.任意の語頭符号長函数$\mathcal{L}$に対して$n\to\infty$でルベーグ測度が0に近づく$\theta\in\Theta$の集合を除いて次が成立する(つまりほとんどいたるところで以下が成立する).

任意の$\epsilon >0$に対して

\[\mathbb{E}[\mathcal{L}(x^n)]_{\theta}\geq H_n(P)+\frac{k-\epsilon}{2}\ln n\]

ただし左辺は真の分布に対する平均,右辺第1項はエントロピーである.これは真の分布が未知の場合の符号長の下限を与えている.

  • $\theta$が$\mathcal{L}(x^n)=-\ln p(x^n;\theta)$であるように(理想的に)とることができると$\mathcal{L}(x^n)$は下限を下回るが,このような$\theta$は確率0でしか存在しない.

  • $\mathrm{MDL}_k(x^n)$はRissarrenの不等式を漸近的に成立する.

comments powered by Disqus