ソースを表示

１次アルゴリズム

関数の勾配
<math>
l(x,y)=x+y+x^2+y^2
</math>
を例にとって説明します。<math>l(x,y)</math>を
列ベクトルと行列
<math>
{\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 )
</math>
を使って表現すると

<math>
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 ) 
</math>

から
<math>
l({\bf x}) ={\bf p}^T {\bf x} +  {\bf x}^T {\bf Q}{\bf x} 
</math>
と書ける．


ここで,<math>l(x,y)</math>の<math>x,y</math>についての偏微分係数はそれぞれ,
<math>
\frac{\partial l}{\partial x}(x,y)=1+x \\
\frac{\partial l}{\partial y}(x,y)=1+y 
</math>
である。これらを要素にもつ列ベクトルは, 
<math>l({\bf x})=l(x,y)</math>の<math>{\bf x}</math>について
の微分であり,
<math>
\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}
</math>
である。
また,<math>l({\bf x})</math>の２階微分は
<math>
\frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q}
</math>
である。さて,
<math>
\Delta {\bf x}=
\left (
\begin{array}{c}
\Delta x\\
\Delta y\\
\end{array}
\right ) 
</math>
として,
<math>
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} 
</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} 
</math>

となる．

無論,一般の関数<math>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})
</math>
となる．<math>{\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。

勾配を使う計算法
さて,<math>l({\bf x})=l(x,y)</math>を最小化するため,先ず,
初期点
<math>
{\bf x}_0=
\left (
\begin{array}{c}
x_0\\
y_0\\
\end{array}
\right ) 
</math>
を与えて,<math>l({\bf x}_0)</math>を求め,次に,

<math>{\bf x}={\bf x}_0</math>での<math>l({\bf x})</math>の微分,
<math>
\frac{d l}{d {\bf x}}({\bf x}_0)
=  {\bf p}+ {\bf Q}{\bf x}_0 
</math>
を求め,これと微小な正数<math>\epsilon >0</math>を使って,

<math>
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)
</math>
として,<math>l({\bf x}_0 +\Delta {\bf x})</math>を計算すると,

<math>
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)\\
</math>


ここで,任意のベクトル
<math>
{\bf z}
=\left (
\begin{array}{c}
p\\
q\\
\end{array}
\right ) 
</math>
について
<math>
{\bf z}^T{\bf z}=p^2+q^2
</math>
である,<math>{\bf z}^T{\bf z} \ge 0</math>である。同様に,
<math>
\frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0
</math>
<math>
\frac{d l}{d {\bf x}}({\bf x}_0)^T 
{\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0
</math>
である。<math>\epsilon</math>が十分小さければ,
<math>
\Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0)
</math>
として,

<math>l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)</math>
となる．
<math>
{\bf x}_1 ={\bf x}_0 +\Delta {\bf x}
</math>
を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に,毎回の繰り返しで,
<math>
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))
</math>
となるように,<math>\epsilon_n</math>を選ぶ繰り返し計算法を最急降下法と呼ぶ．

<math>
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}によって決まる何らかの方向ベクトル
</math>
を繰り返しながら
<math>
\{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \}
</math>
を生成し,
<math>
\lim_{n \to \infty } l({\bf x}_n)=min_{{\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} 
</math>
を使って,高速なアルゴリズムを造る．
<math>
\Delta {\bf x}={\bf y}-{\bf x}
</math>
とおき,上の式の右辺を書き換える．
<math>
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}) 
</math>
これは<math>{\bf y}</math>についての２次式である。この式が<math>{\bf y}</math>について,極小になるための
条件は,極値条件(<math>{\bf y}</math>についての微分が{\bf 0}ベクトル) 
<math>
\frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x})
 {\bf y}={\bf 0} 
</math>
である。これから,行列
<math>
\frac{d^2 l}{d {\bf x}^2}({\bf x})
</math>
が正則(逆行列をもつ)とすれば,
<math>
{\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x})</math>
が得られる．

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