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

情報論的学習理論2

線型回帰モデル

線型回帰モデルは教師あり学習の枠組みで,

\[ p(y|x;\theta)=\frac{1}{\sqrt{s\pi\sigma^2}}\exp(-\frac{(y-\theta^\top x)^2}{2\sigma^2}) \]

つまり

\[ y=\theta^\top x-\epsilon ~~\epsilon\sim\mathscr{N}(0, \sigma^2) \]

ここで観測されるデータ列を$(x_1,y_1),\ldots,(x_n,y_n)$として,$X=[x_1,\ldots,x_n],Y=(y_1,\ldots,y_n)^\top$とすると線型モデルの負の対数尤度は

\[ \frac{1}{\sigma^2}\sum_t(y_t-\theta^\top x_t)^2+n\ln\sqrt{2\pi\sigma^2} \]

の第一項の和は

\[ (Y-X\theta)^\top(Y-X\theta) \]

と書ける.$\frac{\partial \mathcal{L}(\theta)}{\partial \theta}|_{\theta=\hat{\theta}_{\mathrm{NLE}}}=0$より

\[X^\top Y-X^\top X\hat{\theta}=0\]

これは$X^\top X$が正則の時に

\[\hat{\theta}=(X^\top X)^{-1}X^\top Y\]

と求まるが$x$が$n$次の時に$(X^\top X)^{-1}$は$O(d^3)$のオーダーなのであまり計算をしたくない.

スパース正則

対数尤度に正則化項を加えた

\[-\sum_t\ln p(y_t|x_t;\theta)+\lambda R(\theta)\]

を考える.特に$R(\theta)=\sum|\theta|^p$を考える.上の式の最小化は,ある$B>0$が存在して

\[\sum\ln(y_t|x_t;\theta)=\sum(y_t-\theta^\top x_t)\]

を$R(\theta)\le B$と等価である.

損失函数

損失函数はデータ$\mathscr{D}=(\mathscr{X}, \mathscr{Y})$,(確率)モデル空間$\mathscr{P}$に対して

\[\mathcal{L}:\mathscr{D}\times\mathscr{P}\to\mathbb{R}\]

で定義される.

  • 対数損失は$P_\theta=p(y|x;\theta)$として$\mathcal{L}(\mathscr{D};P_\theta)=-\ln p(y|x;\theta)$

  • 2乗損失は確率ではなく適当の函数$f_\theta$によって$\mathcal{L}(\mathcal{D};f_\theta)=(y-f_\theta(x))^2$

  • 0-1損失は$\mathcal{L}(\mathcal{D};f_\theta)=1-\mathbf{1}[y+f_\theta(x)]$

  • ロジステック損失は$y\in\{-1,1\}$で$\mathcal{L}(\mathcal{D};f_\theta)=-\ln\frac{1}{1+\exp{(-yf_\theta(x))}}$

結局,最尤推定とMAP推定は経験的損失$\sum_t\mathcal{L}(\mathscr{D}_t;P_\theta)$と正則化項$\lambda R(\theta)$を$\theta$について最小化することなのであった.

$L_1$正則化 a.k.a LASSO

LASSOはLeast Absolute Shrinkage and Selection Operatorの略らしく,スパースな解が得やすいことが知られている.

\[f_\theta=\sum_t(y_t-\theta^\top x_t)^2+\lambda\sum_i|\theta_i|\]

これは正則化項の絶対値により解析的に解くことは出来ない.$\theta$の第$j$成分$\theta_j$に注目する.

\[ \begin{aligned} f_\theta &= \sum_t(y_t-\theta_j x_{t,j}-\sum_{i\ne j}\theta_i x_{t,i})^2 + \lambda(|\theta_j|+\sum_{i\ne j}|\theta_i|) \cr\cr & = (\sum_t x_{t,j})^2\theta_j^2-2\theta_j(\sum_t x_{t,j}y_t)+2\theta_j\sum_t\sum_{i\ne j}\theta_i x_{t,j}x_{t,i}+\lambda|\theta_j|+C \end{aligned} \]

ここで$C$は$\theta_j$を含まない項.$A_j=\frac{\sum_t x_{t,j}(y_t-\sum_{i\ne j}x_{t,i}\theta_i)}{\sum_t x_{t,j}^2}, \rho=\frac{\lambda}{2\sum_t x_{t,j}^2}$とおくと,

\[f_\theta=(\sum_t x_{t,j})^2(\theta_j^2-2A_j\theta_j+2\rho|\theta_j|)\]

以下では$g(\theta)=\theta^2-2A\theta+\rho|\theta|$の最小化を考える(添え字$j$は省略する).

\[\mathrm{sign}(\theta)=\begin{cases} & 1 ~~ \text{if } \theta > 0 \cr & -1 ~~ \text{if } \theta < 0 \cr & \forall\hat{x}\in(-1,1) ~~ \text{otherwise} \end{cases}\]

を用いて

\[\frac{\partial g(\theta)}{\partial \theta}=2(\theta-A+\rho\mathrm{sign}(\theta))=0\]

を考えると

  • $A>\rho(>0)$のとき$\theta=A-\rho>0$
  • $A<-\rho(<0)$のとき$\theta=A+\rho<0$
  • $\rho\le A\le\rho$のとき$\theta=0$

つまり各$j$につきこの操作を繰り返して$g(\theta_j)$を最小とする$\theta_j$を更新することで,$f_\theta$を最小とするような,スパースな$\theta$を求めることが出来る.

comments powered by Disqus