勾配法
提供: Internet Web School
(ページの作成: １次アルゴリズム 関数の勾配 <math> l(x,y)=x+y+x^2+y^2 </math> を例にとって説明します。<math>l(x,y)</math>を 列ベクトルと行列 <math> {\bf p} =\…) |
|||
| 8 行: | 8 行: | ||
を例にとって説明します。<math>l(x,y)</math>を | を例にとって説明します。<math>l(x,y)</math>を | ||
列ベクトルと行列 | 列ベクトルと行列 | ||
| + | |||
<math> | <math> | ||
{\bf p} | {\bf p} | ||
| 31 行: | 32 行: | ||
\right ) | \right ) | ||
</math> | </math> | ||
| + | |||
を使って表現すると | を使って表現すると | ||
| 58 行: | 60 行: | ||
から | から | ||
| + | |||
<math> | <math> | ||
l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x} | l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x} | ||
</math> | </math> | ||
| + | |||
と書ける． | と書ける． | ||
ここで,<math>l(x,y)</math>の<math>x,y</math>についての偏微分係数はそれぞれ, | ここで,<math>l(x,y)</math>の<math>x,y</math>についての偏微分係数はそれぞれ, | ||
| + | |||
<math> | <math> | ||
\frac{\partial l}{\partial x}(x,y)=1+x \\ | \frac{\partial l}{\partial x}(x,y)=1+x \\ | ||
\frac{\partial l}{\partial y}(x,y)=1+y | \frac{\partial l}{\partial y}(x,y)=1+y | ||
</math> | </math> | ||
| + | |||
である。これらを要素にもつ列ベクトルは, | である。これらを要素にもつ列ベクトルは, | ||
<math>l({\bf x})=l(x,y)</math>の<math>{\bf x}</math>について | <math>l({\bf x})=l(x,y)</math>の<math>{\bf x}</math>について | ||
の微分であり, | の微分であり, | ||
| + | |||
<math> | <math> | ||
\frac{d l}{d {\bf x}}({\bf x}) | \frac{d l}{d {\bf x}}({\bf x}) | ||
| 82 行: | 89 行: | ||
={\bf p}+ 2 {\bf Q} {\bf x} | ={\bf p}+ 2 {\bf Q} {\bf x} | ||
</math> | </math> | ||
| + | |||
| + | |||
である。 | である。 | ||
また,<math>l({\bf x})</math>の２階微分は | また,<math>l({\bf x})</math>の２階微分は | ||
| + | |||
<math> | <math> | ||
\frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q} | \frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q} | ||
</math> | </math> | ||
| - | + | ||
| + | である。 | ||
| + | |||
<math> | <math> | ||
\Delta {\bf x}= | \Delta {\bf x}= | ||
| 97 行: | 109 行: | ||
\right ) | \right ) | ||
</math> | </math> | ||
| + | |||
として, | として, | ||
| + | |||
<math> | <math> | ||
l({\bf x} +\Delta {\bf x}) \\ | l({\bf x} +\Delta {\bf x}) \\ | ||
| 131 行: | 145 行: | ||
勾配を使う計算法 | 勾配を使う計算法 | ||
| - | + | ||
| + | <math>l({\bf x})=l(x,y)</math>を最小化するため,先ず, | ||
| + | |||
初期点 | 初期点 | ||
<math> | <math> | ||
| 142 行: | 158 行: | ||
\right ) | \right ) | ||
</math> | </math> | ||
| + | |||
を与えて,<math>l({\bf x}_0)</math>を求め,次に, | を与えて,<math>l({\bf x}_0)</math>を求め,次に, | ||
<math>{\bf x}={\bf x}_0</math>での<math>l({\bf x})</math>の微分, | <math>{\bf x}={\bf x}_0</math>での<math>l({\bf x})</math>の微分, | ||
| + | |||
<math> | <math> | ||
\frac{d l}{d {\bf x}}({\bf x}_0) | \frac{d l}{d {\bf x}}({\bf x}_0) | ||
= {\bf p}+ {\bf Q}{\bf x}_0 | = {\bf p}+ {\bf Q}{\bf x}_0 | ||
</math> | </math> | ||
| + | |||
を求め,これと微小な正数<math>\epsilon >0</math>を使って, | を求め,これと微小な正数<math>\epsilon >0</math>を使って, | ||
| 154 行: | 173 行: | ||
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) | \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) | ||
</math> | </math> | ||
| + | |||
として,<math>l({\bf x}_0 +\Delta {\bf x})</math>を計算すると, | として,<math>l({\bf x}_0 +\Delta {\bf x})</math>を計算すると, | ||
| 167 行: | 187 行: | ||
\frac{d l}{d {\bf x}}({\bf x}_0)\\ | \frac{d l}{d {\bf x}}({\bf x}_0)\\ | ||
</math> | </math> | ||
| - | |||
ここで,任意のベクトル | ここで,任意のベクトル | ||
| + | |||
<math> | <math> | ||
{\bf z} | {\bf z} | ||
| 179 行: | 199 行: | ||
\right ) | \right ) | ||
</math> | </math> | ||
| + | |||
について | について | ||
| + | |||
<math> | <math> | ||
{\bf z}^T{\bf z}=p^2+q^2 | {\bf z}^T{\bf z}=p^2+q^2 | ||
| 187 行: | 209 行: | ||
\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 \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 | ||
</math> | </math> | ||
| + | |||
| + | |||
<math> | <math> | ||
\frac{d l}{d {\bf x}}({\bf x}_0)^T | \frac{d l}{d {\bf x}}({\bf x}_0)^T | ||
{\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 | {\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 | ||
</math> | </math> | ||
| - | である。<math>\epsilon</math>が十分小さければ, | + | |
| + | である。 | ||
| + | |||
| + | <math>\epsilon</math>が十分小さければ, | ||
| + | |||
<math> | <math> | ||
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) | \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) | ||
</math> | </math> | ||
| + | |||
として, | として, | ||
<math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math> | <math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math> | ||
となる． | となる． | ||
| + | |||
<math> | <math> | ||
{\bf x}_1 ={\bf x}_0 +\Delta {\bf x} | {\bf x}_1 ={\bf x}_0 +\Delta {\bf x} | ||
</math> | </math> | ||
を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に,毎回の繰り返しで, | を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に,毎回の繰り返しで, | ||
| + | |||
<math> | <math> | ||
l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n)) | l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n)) | ||
=\min_{\epsilon,\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n)) | =\min_{\epsilon,\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n)) | ||
</math> | </math> | ||
| + | |||
となるように,<math>\epsilon_n</math>を選ぶ繰り返し計算法を最急降下法と呼ぶ． | となるように,<math>\epsilon_n</math>を選ぶ繰り返し計算法を最急降下法と呼ぶ． | ||
| 215 行: | 247 行: | ||
{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル | {\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル | ||
</math> | </math> | ||
| + | |||
を繰り返しながら | を繰り返しながら | ||
| + | |||
<math> | <math> | ||
\{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \} | \{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \} | ||
</math> | </math> | ||
| + | |||
を生成し, | を生成し, | ||
<math> | <math> | ||
\lim_{n \to \infty } l({\bf x}_n)=min_{{\bf x}}l({\bf x}) | \lim_{n \to \infty } l({\bf x}_n)=min_{{\bf x}}l({\bf x}) | ||
</math> | </math> | ||
| + | |||
とする計算法は,一次アルゴリズムと呼ばれている． | とする計算法は,一次アルゴリズムと呼ばれている． | ||
２次アルゴリズム | ２次アルゴリズム | ||
| + | |||
<math> | <math> | ||
l({\bf x} +\Delta {\bf x}) | l({\bf x} +\Delta {\bf x}) | ||
| 231 行: | 268 行: | ||
\Delta {\bf x} | \Delta {\bf x} | ||
</math> | </math> | ||
| + | |||
を使って,高速なアルゴリズムを造る． | を使って,高速なアルゴリズムを造る． | ||
| + | |||
<math> | <math> | ||
\Delta {\bf x}={\bf y}-{\bf x} | \Delta {\bf x}={\bf y}-{\bf x} | ||
</math> | </math> | ||
| + | |||
とおき,上の式の右辺を書き換える． | とおき,上の式の右辺を書き換える． | ||
| + | |||
<math> | <math> | ||
l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T({\bf y}-{\bf x}) | l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T({\bf y}-{\bf x}) | ||
| 241 行: | 282 行: | ||
({\bf y}-{\bf x}) | ({\bf y}-{\bf x}) | ||
</math> | </math> | ||
| + | |||
これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための | これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための | ||
条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル) | 条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル) | ||
| + | |||
<math> | <math> | ||
\frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x}) | \frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x}) | ||
{\bf y}={\bf 0} | {\bf y}={\bf 0} | ||
</math> | </math> | ||
| + | |||
である。これから,行列 | である。これから,行列 | ||
| + | |||
<math> | <math> | ||
\frac{d^2 l}{d {\bf x}^2}({\bf x}) | \frac{d^2 l}{d {\bf x}^2}({\bf x}) | ||
</math> | </math> | ||
| + | |||
が正則(逆行列をもつ)とすれば, | が正則(逆行列をもつ)とすれば, | ||
| + | |||
<math> | <math> | ||
| - | {\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x})</math> | + | {\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x}) |
| + | </math> | ||
| + | |||
が得られる． | が得られる． | ||
2020年11月25日 (水) 08:26時点における版
１次アルゴリズム
関数の勾配 \( 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})\)の２階微分は
\( \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} +\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})<math>,解析的な関数なら, <math> 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})<math>は３次以上の高位の項である。 勾配を使う計算法 <math>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
\)
である。
\(\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,\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,\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_[[:Template:\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} \)
を使って,高速なアルゴリズムを造る．
\( \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}\)についての２次式である。この式が\({\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) \) を繰り返すアルゴリズムはニュートン法と呼ばれる．
