勾配法

提供: Internet Web School

(版間での差分)
 
(間の6版分が非表示)
1 行: 1 行:
-
 
+
==一次アルゴリズム==
-
== 1次アルゴリズム ==
+
-
 
+
-
関数の勾配
+
<math>
<math>
l(x,y)=x+y+x^2+y^2
l(x,y)=x+y+x^2+y^2
122 行: 119 行:
-
関数<math>l({\bf x})</math>が解析的な関数なら,
+
これを一般化する.関数<math>l({\bf x})</math>が解析的な関数なら,
<math>
<math>
131 行: 128 行:
</math>
</math>
-
となる.<math>{\bf o}(\Delta {\bf x})<math>は3次以上の高位の項である。
+
となる.<math>{\bf o}(\Delta {\bf x})</math>は3次以上の高位の項である。
-
== 勾配を使う計算法 ==
+
==勾配を使う計算法==
<math>l({\bf x})=l(x,y)</math>を最小化するため先ず,
<math>l({\bf x})=l(x,y)</math>を最小化するため先ず,
191 行: 188 行:
{\bf z}^T{\bf z}=p^2+q^2
{\bf z}^T{\bf z}=p^2+q^2
</math>
</math>
-
である,<math>{\bf z}^T{\bf z} \ge 0
+
であるから<math>{\bf z}^T{\bf z} \ge 0
</math>である。
</math>である。
208 行: 205 行:
<math>0 \lt \epsilon</math>が十分小さければ,
<math>0 \lt \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>
となる.
となる.
228 行: 222 行:
<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>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n))
</math>
</math>
235 行: 229 行:
<math>
<math>
l({\bf x}_n+\epsilon_n {\bf \eta }_n)
l({\bf x}_n+\epsilon_n {\bf \eta }_n)
-
=\min_{\epsilon,\epsilon>0} l({\bf x}_n+\epsilon {\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 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}によって決まる何らかの方向ベクトル
248 行: 242 行:
を生成し,
を生成し,
<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>
とする計算法は,一次アルゴリズムと呼ばれている.
とする計算法は,一次アルゴリズムと呼ばれている.
-
==2次アルゴリズム==
+
==2次アルゴリズム==
278 行: 272 行:
これは<math>{\bf y}</math>についての2次式である。この式が<math>{\bf y}</math>について,極小になるための
これは<math>{\bf y}</math>についての2次式である。この式が<math>{\bf y}</math>について,極小になるための
-
条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル)  
+
条件は,極値条件(<math>{\bf y}</math>についての微分が<math>{\bf 0}</math>ベクトル)  
<math>
<math>
286 行: 280 行:
である。これから,行列
である。これから,行列
-
 
<math>
<math>
\frac{d^2 l}{d {\bf x}^2}({\bf x})
\frac{d^2 l}{d {\bf x}^2}({\bf x})
</math>
</math>
-
 
が正則(逆行列をもつ)とすれば,
が正則(逆行列をもつ)とすれば,

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) \) を繰り返すアルゴリズムはニュートン法と呼ばれる.

個人用ツール