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

情報論的学習理論3

勾配降下法

データ$D^n=D_1,\ldots,D_n$,損失函数$\mathcal{L}(D;\theta)$に対して

\[\mathcal{L}(\theta):=\frac1n\sum_{t=1}^n\mathcal{L}(D_t;\theta)\]

とする.特に$\mathcal{L}(\theta)$を$\theta$について最小化したいが,解析的に行えないときに効果を発揮するのが勾配降下法である.

1次の勾配降下法

  • $\theta^{(0)}$を適当な初期値とする.
  • $\theta^{(t)}$を逐次的に$\theta^{(t+1)}=\theta^{(t)}-\alpha\nabla\mathcal{L}(\theta)|_{\theta=\theta^{(t)}}$と更新する.ここで$\alpha$は学習率と呼ばれる値である.

2次の勾配降下法

  • $\theta^{(t+1)}=\theta^{(t)}-H^{-1}\nabla\mathcal{L}(\theta)|_{\theta=\theta^{(t)}}$によって更新を行う.

確率的勾配降下法

$\mathcal{L}(\theta)=\frac1n\sum_{t=1}^n\mathcal{L}(D_t;\theta)$について$n$が充分に大きいとすると計算のコストがかかる.そこで$D^n$から一部を乱択した$\tilde{D}^{\tilde{n}}$を用いて

\[\tilde{\mathcal{L}}(\theta):=\frac{1}{\tilde{n}}\sum_{t=1}^{\tilde{n}}\mathcal{L}(\tilde{D}_t;\theta)\]

で近似する.

モデル選択

いま簡単のためモデルの複雑さがモデルのパラメータ数のみで決定されるとして,$k$次元のパラメータ集合$\Theta_k$に対して$k$次元のパラメータモデルを

\[\mathscr{P}_k:=\{p(x;\theta,k):\theta\in\Theta_k\}\]

と定める.また

\[\mathscr{P}:=\bigcup_k\mathscr{P}_k\]

このとき$\mathscr{P}_1\subset\mathscr{P}_2\cdots\subset\cdots$という入れ子構造を持つ.モデル選択とはデータ$x^n=x_1,\ldots,x_n$が与えられたときに「最良の」$k$を決定する問題である.例えばクラスタリングであればクラスタの数がこの$k$に相当するし,多項式近似であれば多項式の最大次数が$k$である.

この「最良」を決定する手法は幾つか存在するが,さらにその手法を選択する目的に応じたメタな規準が必要となる.

情報量規準

情報量規準は函数$f(k|x^n)$で,$f$を最小とする$k$が最良となるようなもののことである.AIC,BIC,MDL,交差検証法などが有名である.

AIC(赤池情報量規準)

\[f(k|x^n)=-\ln p(x^n;\hat{\theta}(x^n),k)+k\]

ただし$\hat{\theta}$は最尤推定量である.この第1項はデータに対する適合性,第2項はモデルの複雑さにそれぞれ対応し,互いにトレードオフの関係にある.つまり一般に複雑なモデルはよい適合性を持つ.

AICは期待平均対数尤度の不偏推定量となる.ここで期待平均対数尤度は$n\mathbb{E}_{X^n}\mathbb{E}_Z[-\ln p(Z;\hat{\theta}(X^n))]$で$X^n,Z$は同一の分布から独立に生成され,それぞれ訓練データとテストデータである.

補題1

中心極限定理を仮定する.つまり

\[\sqrt{n}(\hat{\theta}(x^n)-\theta)\rightsquigarrow\mathcal{N}(0,I^{-1}(\theta))\]

である.ただし,$\theta$は真の分布のパラメータで$\rightsquigarrow$は法則収束を指すのであった.このとき

\[n\mathbb{E}_{X^n}\mathbb{E}_Z[-\ln p(Z;\hat{\theta}(X^n))]=n\mathbb{E}_Z[-\ln p(Z;\theta)]+\frac{k}{2}+o(1)\]

が成立する.

証明(補題1)

$\hat{\theta}$の$\theta$周りでのTaylor展開を考える.

\[\begin{aligned} n\mathbb{E}_{X^n}\mathbb{E}_Z[-\ln p(Z;\hat{\theta}(X^n))] &= n\mathbb{E}_Z[-\ln p(z;\hat{\theta})] - n\mathbb{E}_{X^n}\mathbb{E}_Z[\nabla\ln p(z;\theta)(\hat{\theta}-\theta)] \cr & + \mathbb{E}_{X^n}[\frac12\sqrt{n}(\hat{\theta}-\theta)^{\top}\mathbb{E}_Z[-\nabla^2\ln p(z;\theta)]\sqrt{n}(\hat{\theta}-\theta)]+R \end{aligned}\]

ここで右辺第2項について

\[\begin{aligned} \mathbb{E}_{Z}[-\nabla\ln p(x;\theta)] &= \sum_z p(z;\theta)\frac{1}{p(z;\theta)}\nabla p(x;\theta) \cr &= \sum \nabla p(z;\theta)=\nabla\sum p(z;\theta)=0 \end{aligned}\]

第3項については$\mathbb{E}_Z[-\nabla^2\ln p(z;\theta)]$がフィッシャー情報量行列であることと,中心極限定理,χ2乗分布の期待値が$k$であることを用いて$\frac{k}{2}$で近似できる1.あるいは$n(\hat{\theta}-\theta)(\hat{\theta}-\theta)^{\top}$が共分散行列であることを思えばこれは$I(\theta)^{-1}$に収束して,

\[\frac12\mathrm{tr}(\mathbb{E}_{X^n}[I(\theta)n(\hat{\theta}-\theta)(\hat{\theta}-\theta)^{\top}])=\frac12\mathrm{tr}\mathbf{I}_k=\frac{k}{2}\]

補題2

\[E_{X^n}[-\ln p(X^n; \theta)] = E_{X^n}[-\ln p(X^n;\hat{\theta}(X^n))]+\frac{k}{2}+o(1)\]

証明(補題2)

同様のTaylor展開を考える.

\[\begin{aligned}-\ln p(X^n;\theta) & =-\ln p(X^n;\hat{\theta}) +\nabla(-\ln p(X^n;\theta))|_{\theta=\hat{\theta}}(\theta-\hat{\theta})\cr &+\frac12(\theta-\hat{\theta})^{\top}(-\nabla^2\ln p(X^n;\theta))(\theta-\hat{\theta})+o(1)\end{aligned}\]

ここで右辺第2項は最尤推定量は対数尤度の極値であるので0,また第3項については

\[\begin{aligned} n\cdot\frac1n\sum_t(-\nabla^2 \ln p(X_t;\theta))|_{\theta=\hat{\theta}} &\approx n\mathbb{E}_{\theta}[\nabla^2 \ln p(X;\theta)]|_{\theta=\hat{\theta}} \cr &= nI(\hat{\theta}) \end{aligned}\]

先ほどと同様の議論によって

\[\mathbb{E}_{X^n}[\frac12(\theta-\hat{\theta})^{\top}(-\nabla^2\ln p(X^n;\theta))(\theta-\hat{\theta})]=\frac{k}{2}\]

定理(期待平均対数尤度の不偏推定量がAICとなる)

データが独立に同一の分布から生起してかつ中心極限定理が成立することを仮定する.

\[\mathrm{AIC}_k(x^n):=-\ln p(x^n;\hat{\theta}(x^n))+k\]

とすると

\[E_{X^n}[\mathrm{AIC}_k(x^n)]=nE_{X^n}E_Z[-\ln p(Z;\hat{\theta}(X^n))]+o(1)\]

証明

補題1により

\[nE_{X^n}E_Z[-\ln p(Z;\hat{\theta}(X^n))]=n\mathbb{E}_Z[-\ln p(Z;\theta)+\frac{k}{2}+o(1)]\]

これはi.i.d.の仮定によって

\[E_X^n[-\ln p(X^n;\theta)]+\frac{k}{2}+o(1)\]

補題2によって

\[E_X^n[-\ln p(X^n;\hat{\theta}(X^n))]+\frac{k}{2}+\frac{k}{2}+o(1)=\mathbb{E}_{X^n}[\mathrm{AIC}_k(X^n)]+o(1)\]

ここでは定理の仮定にi.i.d.中心極限定理があることに注意を要する.特に中心極限定理は隠れ変数が存在する場合には成立しない.

BIC (ベイジアン情報規準)

シュヴァルツ規準とも言われ,以下によって定められる.

\[f(k|x^n):=-\ln p(x^n;\hat{\theta}(x^n))]+\frac{k}{2}\ln n\]

$M=-\int\pi(\theta)p(x^n;\theta)d\theta$を$k$について最小化することを考える.

\[\begin{aligned}\ln M &= -\ln\int\pi(\theta)\exp(\ln p(x^n;\theta))d\theta \cr & \approx -\ln\int\pi(\theta)\exp(\ln p(x^n;\hat{\theta})+ \frac{n}{2}(\theta-\hat{\theta})^{\top}\hat{I}(\hat{\theta})(\theta-\hat{\theta}))d\theta \cr &\approx -\ln p(x^n;\hat{\theta})+\ln\int\pi\exp(-\frac12(\theta-\hat{\theta})^{\top}n\hat{I}(\hat{\theta})(\theta-\hat{\theta}))d\theta \end{aligned}\]

ここで$\exp$内でTaylor展開をし,$\hat{I}(\theta):=\nabla^2 p(X^n;\theta)$とした.ガウス積分$\int\exp(-\frac{x^{\top}\Sigma^{-1}x}{2})dx=(2\pi|\Sigma|)^{d/2}$を用いて第2項にラプラス近似を用いると

\[\ln(\frac{2\pi}{n})^{k/2}|\hat{I}(\hat{\theta})|^{k/2}=\frac{k}{2}\ln n+o(1)\]


  1. todo [return]
comments powered by Disqus