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

情報論的学習理論4

情報・符号・確率

ここでは一見異なる概念である情報・符号・確率が(情報論的学習理論では)ほぼ同一視できることを見ていく.

$\mathscr{X}$を有限集合,$\mathscr{X}^n$を長さ$n$のデータ列の集合とする.また$\{0,1\}^{\star}$を任意の長さの二元列の集合とする.このとき符号化とは

\[\pi:\mathcal{X}^n\to \{0,1\}^{\star}\]

のことを指す.また語頭符号化を以下のように定める.

  • $\mathcal{X}^n$に属する任意の元$x_1, x_2 ~(x_1\ne x_2)$について$\pi(x_1)$と$\pi(x_2)$の一方が他方の先頭部分の語頭に一致しないような$\pi$.これは符号後を連ねた際に,区切り記号を用いることなく原文を一意的に記述可能のことを意味する.たとえば$\mathcal{X}^2=\{0,1\}^2$として符号化$\pi$を

\[\begin{cases} \pi(00) = 000 \cr \pi(01) = 001 \cr \pi(10) = 01 \cr \pi(11) = 1 \end{cases}\]

とすれば,$1$か$000$を区切りとみることで区切り記号を用いずに一意的な表記をすることができる(逆に$\pi(000)=010$などとしてしまうと区切り記号が必要となる).つまりこの$\pi$は語頭符号化である.

以下簡単のため符号長(函数)を$l(x^n)=|\pi(x^n)|$と定める.語頭符号化について以下が成り立つ.

定理(語頭符号化の必要十分条件,Kraftの不等式)

$\pi$が語頭符号化可能であることは$\sum_{x^n}2^{-l(x^n)}\le 1$と必要十分である(一般に$m$元符号化をすれば$2\to m$)

定義(劣確率分布)

$p(X^n)$が$\mathscr{X}^n$の劣確率分布であるとは

  • 任意の$X^n$について$p(X^n)\ge 0$
  • $\displaystyle \sum_{X^n\in\mathscr{X}^n}p(X^n)\le 1$(等号の時一般の確率分布)

いま$p(X^n)$が劣確率分布であるとすると$l(x)=\lceil-\log_2 P(X^n)\rceil$とすることで符号長函数$l(X^n)$の語頭符号化が存在する.ここでは構成が可能であることを示しているだけで,具体的な手法についてはarithmetic coding, haffmann codingなどを参照.

逆に$l(x^n)$が語頭符号化の符号長函数であるならばKraftの不等式を満たすので$p(x^n)=2^{-l(x^n)}$として得られる劣確率分布が存在する.

以上から劣確率分布$p(X^n)$と符号長函数$l(x^n)$とが表裏一体の関係にあることが分かる.ところがここで劣確率分布$p(X^n)$に$p(\bar{X})=1-\sum p(X^n)$を加えた$p(\tilde{X}^n)$は$p(\tilde{X}^n)\ge 0$と$\sum p(\tilde{X}^n)=1$をみたす確率分布である.

つまり劣確率分布は即座に確率分布に変換することができるので,確率分布と符号化とが表裏一体である,ということができる.

定理(平均符号長の下限,シャノンの符号化定理)

いま真の分布$P$が既知であるとし,$L$を任意の語頭符号化符号長函数であるとする.このとき

\[\mathbb{E}_P[L(X^n)]\ge H_n(P)\]

で,この下限は$L(X^n)=-\ln P(X^n)$をとれば達成可能である.ただし$H_n(P)$は$P$のエントロピー函数で$-\sum P(X^n)\ln P(X^n)$.

これは適当な確率分布$q$によって$L(X^n)=-\ln q(X^n)$として$\mathbb{E}_P[L(X^n)]=-\sum p(X^n)\ln q(X^n)$を考えれば導かれる.

確率的複雑さとMDL規準

k次元のパラメーター集合$\Theta_k$に対してk次元のモデル集合を

\[\mathscr{P}_k=\{p(X^n;\theta,k);\theta\in\Theta_k\}\]

とする.

\[p_{\mathrm{NLM}}(x^n)=\frac{p(x^n;\hat{\theta}(x^n))}{\sum p(x^n; \hat{\theta}(x^n))}\]

ただし$\hat{\theta}$は最尤推定量とする.この$p_{\mathrm{NML}}$確率分布をなすので正規化最尤符号長を

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

と定める.このとき$l$は$x^n$の$\mathscr{P}_k$に対する確率的複雑さであり,最終辺第二項は$\mathscr{P}_k$の情報論的複雑さを表しパラメーターコンプレキシティと呼ばれる.シャノンの符号化定理では真の分布$P$は既知であったが,今は未知である.

\[\begin{aligned} \text{シャノンの情報量}~ ~ &= -\ln P(X^n) &P:\text{known} \cr &\Updownarrow& \cr \text{確率的複雑さ}~ ~ &= -\ln p_{\mathrm{NML}}(X^n) &P:\text{unknown}(\mathscr{P}_k:\text{known}) \end{aligned}\]

定理(パラメーターコンプレキシティの漸近近似式)

いま中心極限定理の成立を仮定する.つまり$\sqrt{n}(\hat{\theta}_{\mathrm{MLE}}-\theta)\rightsquigarrow\mathcal{N}(0,I^{-1}(\theta))$,$I(\theta)$が$\theta$について連続で$\int\sqrt{|I(\theta)|}d\theta<\infty$のもとで

\[\ln\sum_{x^n}p(x^n;\hat{\theta}(x^n))=\frac{k}{2}\ln\frac{n}{2\pi}+\ln\int\sqrt{|I(\theta)|}d\theta+o(1)\]

この定理に従えば,正規化最尤符号長$-\ln p_{\mathrm{NML}}(x^n)$は

\[-\ln p(x^n;\hat{\theta}(x^n))+\frac{k}{2}\ln\frac{n}{2\pi}+\ln\int\sqrt{|I(\theta)|}d\theta=:\mathrm{MDL}_k(x^n)\]

となる.MDL規準とは$x^n$が与えられたときに$\min_k \mathrm{MDL}_k(x^n)$である.

comments powered by Disqus