勾配法
提供: Internet Web School
(間の1版分が非表示) | |||
1 行: | 1 行: | ||
- | |||
==一次アルゴリズム== | ==一次アルゴリズム== | ||
<math> | <math> | ||
120 行: | 119 行: | ||
- | 関数<math>l({\bf x})</math>が解析的な関数なら, | + | これを一般化する.関数<math>l({\bf x})</math>が解析的な関数なら, |
<math> | <math> | ||
230 行: | 229 行: | ||
<math> | <math> | ||
l({\bf x}_n+\epsilon_n {\bf \eta }_n) | l({\bf x}_n+\epsilon_n {\bf \eta }_n) | ||
- | =\min_{ | + | =\min_{\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\ |
{\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ | {\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ | ||
{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル | {\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル |
2020年11月25日 (水) 14:35 時点における最新版
一次アルゴリズム
\( l(x,y)=x+y+x^2+y^2 \) を例にとる.\(l(x,y)\)を列ベクトルと行列
\( {\bf p} =\left ( \begin{array}{c} 1\\ 1\\ \end{array} \right ), {\bf x} =\left ( \begin{array}{c} x\\ y\\ \end{array} \right ), {\bf Q}= \left ( \begin{array}{cc} 1&0\\ 0&1\\ \end{array} \right ) \)
を使って表現すると
\( l(x,y) =(1,1) \left ( \begin{array}{c} x\\ y\\ \end{array} \right ) + (x,y) \left ( \begin{array}{cc} 1&0\\ 0&1\\ \end{array} \right ) \left ( \begin{array}{c} x\\ y\\ \end{array} \right ) \)
から \( l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x} \) と書ける.
ここで,\(l(x,y)\)の\(x,y\)についての偏微分係数はそれぞれ,
\( \frac{\partial l}{\partial x}(x,y)=1+x \\ \frac{\partial l}{\partial y}(x,y)=1+y \)
である。これらを要素にもつ列ベクトルは, \(l({\bf x})=l(x,y)\)の\({\bf x}\)について の微分であり,
\( \frac{d l}{d {\bf x}}({\bf x}) =\left ( \begin{array}{c} \frac{\partial l}{\partial x}(x,y)\\ \frac{\partial l}{\partial y}(x,y)\\ \end{array} \right ) ={\bf p}+ 2 {\bf Q} {\bf x} \)
である。
また,\(l({\bf x})\)の2階微分は
\( \frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q} \) である。
\( \Delta {\bf x}= \left ( \begin{array}{c} \Delta x\\ \Delta y\\ \end{array} \right ) \) とすると
\( l({\bf x} +\Delta {\bf x}) \\ ={\bf p}^T ( {\bf x} +\Delta {\bf x}) + ({\bf x}+\Delta {\bf x})^T {\bf Q}({\bf x}+\Delta {\bf x}) \\ ={\bf p}^T {\bf x} +{\bf x}^T {\bf Q} {\bf x} +{\bf p}^T \Delta {\bf x}) +2{\bf x}^T {\bf Q} \Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T {\bf Q} \Delta {\bf x} \\ =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} \)
である.
これを一般化する.関数\(l({\bf x})\)が解析的な関数なら,
\( l({\bf x} +\Delta {\bf x}) =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} +{\bf o}(\Delta {\bf x}) \)
となる.\({\bf o}(\Delta {\bf x})\)は3次以上の高位の項である。
勾配を使う計算法
\(l({\bf x})=l(x,y)\)を最小化するため先ず,
初期点 \( {\bf x}_0= \left ( \begin{array}{c} x_0\\ y_0\\ \end{array} \right ) \) を与えて,\(l({\bf x}_0)\)を求め,次に,
\({\bf x}={\bf x}_0\)での\(l({\bf x})\)の微分,
\( \frac{d l}{d {\bf x}}({\bf x}_0) = {\bf p}+ {\bf Q}{\bf x}_0 \)
を求め,これと微小な正数\(\epsilon >0\)を使って,
\( \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) \)
として,\(l({\bf x}_0 +\Delta {\bf x})\)を計算すると,
\( l({\bf x}_0 +\Delta {\bf x}) \\ =l({\bf x}_0)+\frac{d l}{d {\bf x}}({\bf x}_0)^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}_0) \Delta {\bf x} \\ =l({\bf x}_0) -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) +\epsilon^2 \frac{d l}{d {\bf x}}({\bf x}_0)^T \frac{d^2 l}{d^2 {\bf x}}({\bf x}_0) \frac{d l}{d {\bf x}}({\bf x}_0)\\ \)
ここで,任意のベクトル \( {\bf z} =\left ( \begin{array}{c} p\\ q\\ \end{array} \right ) \) について
\( {\bf z}^T{\bf z}=p^2+q^2 \) であるから\({\bf z}^T{\bf z} \ge 0 \)である。
同様に,
\( \frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 \)
\( \frac{d l}{d {\bf x}}({\bf x}_0)^T {\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 \)
である。
\(0 \lt \epsilon\)が十分小さければ, \( \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) \) として, \(l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)\) となる.
\( {\bf x}_1 ={\bf x}_0 +\Delta {\bf x} \) を新たな初期点としてこれを繰り返すことができる.このような方法を勾配法と呼ばれる.
特に,毎回の繰り返しで,
\( l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n)) =\min_{\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n)) \)
となるように,\(\epsilon_n\)を選ぶ繰り返し計算法を最急降下法と呼ぶ.
\( l({\bf x}_n+\epsilon_n {\bf \eta }_n) =\min_{\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\ {\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ {\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル \)
を繰り返しながら
\( \{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \} \)
を生成し, \( \lim_{n \to \infty }l({\bf x}_n)= \min_{\bf x} l({\bf x}) \)
とする計算法は,一次アルゴリズムと呼ばれている.
2次アルゴリズム
\( l({\bf x} +\Delta {\bf x}) =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} \)
を使って,高速なアルゴリズムを造る.
\( \Delta {\bf x}={\bf y}-{\bf x} \)
とおき,上の式の右辺を書き換える.
\( l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T({\bf y}-{\bf x}) +\frac{1}{2} ({\bf y}-{\bf x})^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) ({\bf y}-{\bf x}) \)
これは\({\bf y}\)についての2次式である。この式が\({\bf y}\)について,極小になるための 条件は,極値条件(\({\bf y}\)についての微分が\({\bf 0}\)ベクトル)
\( \frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x}) {\bf y}={\bf 0} \)
である。これから,行列 \( \frac{d^2 l}{d {\bf x}^2}({\bf x}) \) が正則(逆行列をもつ)とすれば,
\( {\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x}) \)
が得られる.
\( {\bf x}_{k+1}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}_k))^{-1} \frac{d l}{d {\bf x}}({\bf x}_k) \) を繰り返すアルゴリズムはニュートン法と呼ばれる.