理論関連事項

統計学の基本事項,確率分布の詳細,各種データ解析法の理論的背景について.

最急降下法

最急降下法は最もナイーブな勾配降下法.ランダムに与えられた初期値を少しずつ更新することで最終的な解を求める.計算は以下のステップで進む.ここで,$t$ はステップ.また,$\boldsymbol{\theta}_t$,$\alpha$ および $\boldsymbol{g}_t$ はそれぞれ解の候補,学習率および,ステップ $t$ における勾配ベクトル.

  1. 初期値 $\boldsymbol{\theta}_0$ を決める.$t=0$.
  2. $\boldsymbol{\theta}_t$ が最適解に近いとき,計算終了.
  3. $\boldsymbol{\theta}_{t+1}\gets\boldsymbol{\theta}_{t}-\alpha\boldsymbol{g}_t$ および $t\gets t+1$ でパラメーターを更新.
  4. ステップ 2 および 3 を繰り返す.

ニュートン法

ニュートン法はヘシアンを用いた関数最適化法.勾配の変化,すなわちヘシアンが小さいときは大きく変化させ,逆にヘシアンが大きいときは,大きく進みすぎる可能性を避けるために小さく変化させる.計算は以下のステップで進む.ここで,$t$ はステップ.また,$\boldsymbol{\theta}_t$,$\alpha$, $\boldsymbol{g}_t$ および $\boldsymbol{H}_t$ はそれぞれ解の候補,学習率,ステップ $t$ における勾配ベクトルおよびヘシアン.

  1. 初期値 $\boldsymbol{\theta}_0$ を決める.$t=0$.
  2. $\boldsymbol{\theta}_t$ が最適解に近いとき,計算終了.
  3. $\boldsymbol{\theta}_{t+1}\gets\boldsymbol{\theta}_{t}-\boldsymbol{H}_t^{-1}\boldsymbol{g}_t$ および $t\gets t+1$ でパラメーターを更新.
  4. ステップ 2 および 3 を繰り返す.

ニュートン法では $-\boldsymbol{H}_t^{-1}\boldsymbol{g}_t$ の方向にパラメーターを更新するが,これをニュートン方向という.ニュートン方向を導出するために,ある目的関数 $f(\boldsymbol{x})$ を考える.また,現在の $\boldsymbol{x}$ からの微小変化量を $\boldsymbol{d}$ とする.これに対して,$\boldsymbol{x}$ まわりでテイラー展開した以下の式を考える.このとき,三次以上の項は無視して二次近似を行う.

\begin{eqnarray*}f(\boldsymbol{d}+\boldsymbol{x})&=&f(\boldsymbol{x})+{}^t\!\boldsymbol{g}\boldsymbol{d}+\frac{1}{2}{}^t\!\boldsymbol{d}\boldsymbol{H}\boldsymbol{d}\tag{1}\end{eqnarray*}

この式は以下のようにも書ける.

\begin{eqnarray*}f(\boldsymbol{d}+\boldsymbol{x})=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}+\sum_{i=1}^{n}g_id_i+f(\boldsymbol{x})\tag{2}\end{eqnarray*}

よって,この式に対して $\boldsymbol{d}$ について勾配をとると以下のようになる.

\begin{eqnarray*}f(\boldsymbol{d}+\boldsymbol{x})&=&\dfrac{1}{2}\dfrac{\partial}{\partial\boldsymbol{d}}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}+\dfrac{\partial}{\partial\boldsymbol{d}}\sum_{i=1}^{n}g_id_i\\&=&\dfrac{1}{2}\dfrac{\partial}{\partial\boldsymbol{d}}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}+\left(\dfrac{\partial}{\partial d_1}\sum_{i=1}^{n}g_id_i,\dfrac{\partial}{\partial d_2}\sum_{i=1}^{n}g_id_i,\dots,\dfrac{\partial}{\partial d_n}\sum_{i=1}^{n}g_id_i\right)\\&=&\dfrac{1}{2}\dfrac{\partial}{\partial\boldsymbol{d}}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}+(g_1,g_2,\dots,g_n)\\&=&\dfrac{1}{2}\dfrac{\partial}{\partial\boldsymbol{d}}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}+\boldsymbol{g}\\&=&\dfrac{1}{2}\left(\dfrac{\partial}{\partial d_1}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j},\dfrac{\partial}{\partial d_2}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j},\dots,\dfrac{\partial}{\partial d_n}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}\right)+\boldsymbol{g}\\&=&\dfrac{1}{2}\left(\dfrac{\partial}{\partial d_1}(H_{11}d_1^2+H_{22}d_2^2+\dots+2H_{(n-1)n}d_{n-1}d_n),\dfrac{\partial}{\partial d_2}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j},\dots,\dfrac{\partial}{\partial d_n}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}\right)+\boldsymbol{g}\\&=&\dfrac{1}{2}\left(\dfrac{\partial}{\partial d_1}(2H_{11}d_1+2H_{12}d_2+\dots+2H_{1n}d_n),\dfrac{\partial}{\partial d_2}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j},\dots,\dfrac{\partial}{\partial d_n}\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}d_{i}d_{j}\right)+\boldsymbol{g}\\&=&\dfrac{1}{2}\left(2\sum_{j=1}^{n}H_{1j}d_{j},2\sum_{j=1}^{n}H_{2j}d_{j},\dots,2\sum_{j=1}^{n}H_{nj}d_{j}\right)+\boldsymbol{g}\\&=&\boldsymbol{H}\boldsymbol{d}+\boldsymbol{g}\tag{3}\end{eqnarray*}

式 $(1)$ は $\boldsymbol{H}$ が正定置のとき,狭義凸関数なので,式 $(3)$ を $0$ として得られる以下の $\boldsymbol{d}$ は最適解である.

\begin{eqnarray*}\boldsymbol{d}=-\boldsymbol{H}^{-1}\boldsymbol{g}\tag{4}\end{eqnarray*}

以上より,$f(\boldsymbol{x})$ を二次近似した関数の極値を求めることができた.ここで,$\boldsymbol{x}$ から $\boldsymbol{d}$ だけ微小変化させた結果の値を $\boldsymbol{x}^+$,すなわち $\boldsymbol{x}^+=\boldsymbol{x}+\boldsymbol{d}$ とする.このとき,$\boldsymbol{d}=-\boldsymbol{H}^{-1}\boldsymbol{g}$ より $\boldsymbol{x}^+=\boldsymbol{x}-\boldsymbol{H}^{-1}\boldsymbol{g}$ であり,ニュートン法ではこれに従って値を更新する.この $-\boldsymbol{H}^{-1}\boldsymbol{g}$ がニュートン方向である.ニュートン法は非常に収束が速く,二次収束することが知られている.すなわち,$t$ における真の値と近似値との差を $\epsilon_{t}$ としたとき,$\epsilon_{t+1}$ は $\epsilon_{t}^2$ の定数倍となる.ニュートン法は目的関数によっては勾配降下法よりも速く解に辿り着ける方法であるが,大量の鞍点を含むような関数の最適化には不向きと考えられる.勾配の降下する方向へ値を更新する勾配降下法に対して,ニュートン法は勾配が $0$ となる点を探す手法であるので,その付近で勾配が $0$ となる鞍点に捕われてしまう可能性がある.

共役勾配法

共役勾配法は狭義凸関数の最適化を $n$ 回の反復で行なうことができる最適化法.以下のような狭義凸関数を考える.

\begin{eqnarray*}f(\boldsymbol{x})=\frac{1}{2}{}^t\!\boldsymbol{x}\boldsymbol{A}\boldsymbol{x}+{}^t\!\boldsymbol{b}\boldsymbol{x}\tag{5}\end{eqnarray*}

これに対して,共役勾配法は以下のようなステップで計算される.

  1. 初期値 $\boldsymbol{\theta}_0$ を決める.$t=0$.
  2. $\boldsymbol{\theta}_t$ が最適解に近いとき,計算終了.
  3. $\boldsymbol{\theta}_{t+1}\gets\boldsymbol{\theta}_{t}+\alpha_t\boldsymbol{d}_{t}$ および $t\gets t+1$ でパラメーターを更新.$\alpha_t$ および $\boldsymbol{d}_{t}$ は以下の式で計算される.
  4. ステップ 2 および 3 を繰り返す.
\begin{eqnarray*}\alpha_t=-\frac{{}^t\!\boldsymbol{g}_{t}\boldsymbol{d}_t}{{}^t\!\boldsymbol{d}_t\boldsymbol{A}\boldsymbol{d}_t}\tag{6}\end{eqnarray*}
\begin{eqnarray*}\boldsymbol{d}_t=-\boldsymbol{g}_t+\frac{{}^t\!\boldsymbol{g}_t\boldsymbol{g}_t}{{}^t\!\boldsymbol{g}_{t-1}\boldsymbol{g}_{t-1}}\boldsymbol{d}_{t-1}\tag{7}\end{eqnarray*}

この $\boldsymbol{d}_{t}$ の計算は Fletcher-Reeves 法と呼ばれる方法による.

Hatena Google+