機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

共役勾配法

直線探索を用いる反復法において、探索方向を{\bf d}=-\nabla fとするのではなく、もっと良い探索方向を見つけようというのが本記事の趣旨です。
共役勾配法ニュートン法のように計算量の多い{\bf H}^{-1}を計算する必要はありません。

共役勾配法

現在の近似解が{\bf x}^{(K)}であるとき、関数f({\bf x})の2次近似は次のように書けます。

\begin{eqnarray}
f_{\rm II}({\bf x})=f^{(K)}+{\nabla f^{(K)}}^\top({\bf x}-{\bf x}^{(K)})+\frac{1}{2}({\bf x}-{\bf x}^{(K)})^\top{\bf H}^{(K)}({\bf x}-{\bf x}^{(K)})\tag{1}
\end{eqnarray}

(1)極値を求めるため、{\bf x}微分して、={\bf 0}とします。

\begin{eqnarray}
&&\nabla f_{\rm II}={\bf 0}\\
&&\Leftrightarrow\frac{\partial}{\partial{\bf x}}f_{\rm II}={\bf 0}\\
&&\Leftrightarrow \frac{\partial}{\partial{\bf x}}f^{(K)}+\frac{\partial}{\partial{\bf x}}{\nabla f^{(K)}}^\top({\bf x}-{\bf x}^{(K)})+\frac{1}{2}\frac{\partial}{\partial{\bf x}}({\bf x}-{\bf x}^{(K)})^\top{\bf H}^{(K)}({\bf x}-{\bf x}^{(K)})={\bf 0}\\
&&\Leftrightarrow\nabla f^{(K)}+{\bf H}^{(K)}({\bf x}-{\bf x}^{(K)})={\bf 0}\tag{2}
\end{eqnarray}

現在の位置{\bf x}^{(K)}から解{\bf x}に進むには、{\bf m}^{(K)}\propto{\bf x}-{\bf x}^{(K)}であるような{\bf m}^{(K)}の方向に移動すればよいことが分かります。

\begin{eqnarray}
{\bf H}^{(K)}{\bf m}^{(K)}\propto\nabla f^{(K)}\tag{3}
\end{eqnarray}

{\bf m}^{(K)}を共役勾配と呼びます。

{\bf x}^{(K)}での等高線の接線ベクトルを{\bf t}^{(K)}とすると、勾配\nabla f^{(K)}{\bf t}^{(K)}は直交するので、以下の式が成り立ちます。

\begin{eqnarray}
&&{{\bf t}^{(K)}}^\top\nabla f=0\\
&&\Leftrightarrow{{\bf t}^{(K)}}^\top{\bf H}^{(K)}{\bf m}^{(K)}=0\tag{4}
\end{eqnarray}

{\bf m}^{(K)}\nabla f^{(K)}からある程度{\bf t}^{(K)}方向にずれています。
ある定数\alpha^{(K)}を用いると、次の式が成り立ちます。

\begin{eqnarray}
{\bf m}^{(K)}=\nabla f^{(K)}+\alpha^{(K)}{\bf t}^{(K)}\tag{5}
\end{eqnarray}

イメージは下図です。
f:id:olj611:20210616092202p:plain:w400

(5)(4)に代入して、\alpha^{(K)}について解きます。

\begin{eqnarray}
&&{{\bf t}^{(K)}}^\top{\bf H}^{(K)}(\nabla f^{(K)}+\alpha^{(K)}{\bf t}^{(K)})=0\\
&&\Leftrightarrow{{\bf t}^{(K)}}^\top{\bf H}^{(K)}\nabla f^{(K)}+\alpha^{(K)}{{\bf t}^{(K)}}^\top{\bf H}^{(K)}{\bf t}^{(K)}=0\\
&&\Leftrightarrow\alpha^{(K)}=-\frac{{{\bf t}^{(K)}}^\top{\bf H}^{(K)}\nabla f^{(K)}}{{{\bf t}^{(K)}}^\top{\bf H}^{(K)}{\bf t}^{(K)}}\tag{6}
\end{eqnarray}

(6)\alpha^{(K)}を用いて、{\bf m}^{(K)}方向に直線探索をおこなえば、f極値に達することができます。
※この直線探索は勾配法などを用いて割と正確に求める必要があります。

直線探索の結果{\bf x}^{(K)}極値に到達したとします。
その点で探索直線は関数fの等高線に接しています。
よって、探索直線の方向が{\bf x}^{(K)}での接線方向{\bf t}^{(K)}になっており、{\bf t}^{K+1}={\bf m}^{(K)}です。
イメージを下図に記しました。

f:id:olj611:20210615214430p:plain:w400

以上より、次の共役勾配法の反復公式を得ます。

\begin{eqnarray}
&&{\bf m}^{(K)}=\nabla f^{(K)}+\alpha^{(K)}{\bf m}^{(K-1)},\\
&&\alpha^{(K)}=-\frac{{{\bf m}^{(K-1)}}^\top{\bf H}^{(K)}\nabla f^{(K)}}{{{\bf m}^{(K-1)}}^\top{\bf H}^{(K)}{\bf m}^{(K-1)}}\tag{7}\\
&&{\bf x}^{(K+1)}={\bf x}^{(K)}+t^{(K)}{\bf m}^{K}\tag{8}
\end{eqnarray}

(8)t^{(K)}は直線探索におけるステップ幅です。

偉人の名言

f:id:olj611:20210615215149p:plain:w300
決して諦めないヤツを打ち負かすことだけはできない。
ベーブ・ルース

参考文献

これなら分かる最適化数学

動画

なし

目次へ戻る