ニュートン法の収束 - 機械学習基礎理論独習

ニュートン法は真の解に近い近似値から出発すると、収束が極めて速いことが知られています。
$K$ 回目の反復の近似値と真値との値の差を $\epsilon^{(K)}$ とすると、 $K+1$ 回目の反復の近似値と真値との値の差を $\epsilon^{(K+1)}$ は
ほぼ $\epsilon^{(K)2}$ の定数倍であり、これを2次収束といいます。

2次収束 - 1変数の場合

真の解を $a$ とし、 $K$ 回目の反復の解を $x^{(K)}=a+\epsilon^{(K)}$ とおきます。
$f'(x^{(K)}),f''(x^{(K)})$ をテイラー展開します。

$\begin{eqnarray} f'(x^{(K)})&=&f'(a+\epsilon^{(K)})\\ &=&f'(a)+f''(a)\epsilon^{(K)}+\frac{1}{2}f'''(a)\epsilon^{(K)2}+O(\epsilon^{(K)})^3\\ &=&f''(a)\epsilon^{(K)}+\frac{1}{2}f'''(a)\epsilon^{(K)2}+O(\epsilon^{(K)})^3\tag{1} \end{eqnarray}$

$(1)$ の3行目は、 $f'(a)=0$ であることを利用しました。

$\begin{eqnarray} f''(x^{(K)})&=&f''(a+\epsilon^{(K)})\\ &=&f''(a)+f'''(a)\epsilon^{(K)}+O(\epsilon^{(K)})^2\tag{2} \end{eqnarray}$

ただし、 $O(\epsilon^{(K)})^p$ は $\epsilon^{(K)}$ の $p$ 乗あるいはそれ以上のべき乗に比例する微小な項です。

$(2)$ より、 $f''(x^{(K)})$ の逆数は次のように書けます。(※後でこの式変形について説明します。)

$\begin{eqnarray} \frac{1}{f''(x^{(K)})}=\frac{1}{f''(a)}\left(1-\frac{f'''(a)}{f''(a)}\epsilon^{(K)}+O(\epsilon^{(K)})^2\right)\tag{3} \end{eqnarray}$

1変数の場合のニュートン法の更新式は以下の式でした。

$\begin{eqnarray} x^{(K+1)}&=&x^{(K)}-\frac{f'(x^{(K)})}{f''(x^{(K)})}\\ &=&a+\epsilon^{(K)}-\frac{f'(x^{(K)})}{f''(x^{(K)})}\tag{4} \end{eqnarray}$

$(4)$ の $\frac{f'(x^{(K)})}{f''(x^{(K)})}$ を計算します。

$\begin{eqnarray} \frac{f'(x^{(K)})}{f''(x^{(K)})}&=&\left(f''(a)\epsilon^{(K)}+\frac{1}{2}f'''(a)\epsilon^{(K)2}+O(\epsilon^{(K)})^3\right)\frac{1}{f''(a)}\left(1-\frac{f'''(a)}{f''(a)}\epsilon^{(K)}+O(\epsilon^{(K)})^2\right)\\ &=&\left(\epsilon^{(K)}+\frac{f'''(a)}{2f''(a)}\epsilon^{(K)2}+O(\epsilon^{(K)})^3\right)\left(1-\frac{f'''(a)}{f''(a)}\epsilon^{(K)}+O(\epsilon^{(K)})^2\right)\\ &=&\epsilon^{(K)}-\frac{f'''(a)}{2f''(a)}\epsilon^{(K)2}+O(\epsilon^{(K)})^3\tag{5} \end{eqnarray}$

$(5)$ の3行目の式変形で $\epsilon^{(K)}$ の $3$ 乗以上の項は $O(\epsilon^{(K)})^3$ にまとめています。
$(5)$ を $(4)$ に代入します。

$\begin{eqnarray} &&x^{(k+1)}=a+\epsilon^{(K)}-\epsilon^{(K)}+\frac{f'''(a)}{2f''(a)}\epsilon^{(K)2}+O(\epsilon^{(K)})^3\\ &&\Leftrightarrow a+\epsilon^{(K)}=a+\frac{f'''(a)}{2f''(a)}\epsilon^{(K)2}+O(\epsilon^{(K)})^3\\ &&\Leftrightarrow \epsilon^{(K)}=\frac{f'''(a)}{2f''(a)}\epsilon^{(K)2}+O(\epsilon^{(K)})^3\tag{6} \end{eqnarray}$

$(6)$ の式変形で $O(\epsilon^{(K)})^3$ は(どうせ)無視するので、符号は $+$ にしています。

$(6)$ より、高次の微小量 $O(\epsilon^{(K)})^3$ を無視すると、前ステップの2乗に比例するので、2次収束することが分かりました。

まだ説明していない $(3)$ の式変形について説明します。

一般に、微小量 $\epsilon$ の級数 $a_0+a_1\epsilon+a_2\epsilon^2+\cdots$ の逆数が次のように展開されるとします。

$\begin{eqnarray} \frac{1}{a_0+a_1\epsilon+a_2\epsilon^2+\cdots}=b_0+b_1\epsilon+b_2\epsilon^2+\cdots\tag{7} \end{eqnarray}$

$(7)$ の分母を払います。

$\begin{eqnarray} 1=(a_0+a_1\epsilon+a_2\epsilon^2+\cdots)(b_0+b_1\epsilon+b_2\epsilon^2+\cdots)\tag{8} \end{eqnarray}$

$(8)$ の右辺を展開します。

$\begin{eqnarray} (a_0+a_1\epsilon+a_2\epsilon^2+\cdots)(b_0+b_1\epsilon+b_2\epsilon^2+\cdots)=a_0b_0+(a_0b_1+a_1b_0)\epsilon+(a_0b_2+a_1b_1+a_2b_0)\epsilon^2+\cdots\tag{9} \end{eqnarray}$

$(8)$ の両辺の係数比較します。

$\begin{eqnarray} \left\{ \begin{array}{l} a_0b_0=1\\ a_0b_1+a_1b_0=0\\ a_0b_2+a_1b_1+a_2b_0=0\\ \end{array}\tag{10} \right. \end{eqnarray}$

$(10)$ の連立方程式を解くと、次のようになります。

$\begin{eqnarray} &&b_0=\frac{1}{a_0},\\ &&b_1=-\frac{a_1b_0}{a_0}=-\frac{a_1}{a_0^2},\\ &&b_2=-\frac{a_1b_1+a_2b_0}{a_0}=\frac{a_1^2-a_0a_2}{a_0^3}\tag{11} \end{eqnarray}$

ゆえに、次のように展開されます。

$\begin{eqnarray} \frac{1}{a_0+a_1\epsilon+a_2\epsilon^2+\cdots}=\frac{1}{a_0}\left(1-\frac{a_1}{a_0}\epsilon+\frac{a_1^2-a_0a_2}{a_0^2}\epsilon^2+\cdots\right)\tag{12} \end{eqnarray}$

2次収束 - 多変数の場合

真の解を $\bf a$ とし、 $K$ 回目の反復の解を ${\bf x}^{(K)}={\bf a}+{\boldsymbol\epsilon}^{(K)}$ とおきます。
$\frac{\partial f({\bf x}^{(K)})}{\partial x_i},\frac{\partial^2 f({\bf x}^{(K)})}{\partial x_i\partial x_j}$ をテイラー展開します。

$\begin{eqnarray} \frac{\partial f({\bf x}^{(K)})}{\partial x_i}&=&\frac{\partial f({\bf a}+{\boldsymbol\epsilon}^{(K)})}{\partial x_i}\\ &=&\frac{\partial f({\bf a})}{\partial x_i}+\sum_{k=1}^n\frac{\partial^2 f({\bf a})}{\partial x_i\partial x_k}\epsilon^{(K)}+\frac{1}{2}\sum_{k=1}^n\sum_{l=1}^n\frac{\partial^3f({\bf a})}{\partial x_i\partial x_k\partial x_l}\epsilon_k^{(K)}\epsilon_l^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\\ &=&\sum_{k=1}^n\frac{\partial^2 f({\bf a})}{\partial x_i\partial x_k}\epsilon^{(K)}+\frac{1}{2}\sum_{k=1}^n\sum_{l=1}^n\frac{\partial^3f({\bf a})}{\partial x_i\partial x_k\partial x_l}\epsilon_k^{(K)}\epsilon_l^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\tag{13} \end{eqnarray}$

$(13)$ の3行目は、 $\frac{\partial f({\bf a})}{\partial x_i}=0$ であることを利用しました。

$\begin{eqnarray} \frac{\partial^2 f({\bf x}^{(K)})}{\partial x_i\partial x_j}&=&\frac{\partial^2 f({\bf a}+{\boldsymbol\epsilon}^{(K)})}{\partial x_i\partial x_j}\\ &=&\frac{\partial^2 f({\bf a})}{\partial x_i\partial x_j}+\sum_{k=1}^n\frac{\partial^3f({\bf a})}{\partial x_i\partial x_j\partial x_k}\epsilon_k^{(K)}+O({\boldsymbol\epsilon}^{(K)})^2\tag{14} \end{eqnarray}$

ただし、 $O({\boldsymbol\epsilon}^{(K)})^p$ は ${\boldsymbol\epsilon}^{(K)}$ の $p$ 乗あるいはそれ以上のべき乗に比例する微小な項です。

$(13),(14)$ を勾配 $\nabla f$ とヘッセ行列 ${\bf H}$ を用いて書きなおします。

$\begin{eqnarray} &&\nabla f({\bf x}^{(K)})={\bf H}({\bf a}){\boldsymbol\epsilon}^{(K)}+\frac{1}{2}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\tag{15}\\ &&{\bf H}({\bf x}^{(K)})={\bf H}({\bf a})+{\bf K}+O({\boldsymbol\epsilon}^{(K)})^2\tag{16} \end{eqnarray}$

ここで、 $\sum_{k=1}^n\frac{\partial^3f({\bf a})}{\partial x_i\partial x_j\partial x_k}\epsilon_k^{(K)}$ を $(i,j)$ 成分とする行列を $\bf K$ とおきました。

$(16)$ より、 ${\bf H}({\bf x}^{(K)})$ の逆行列は次のように書けます。(※後でこの式変形について説明します。)

$\begin{eqnarray} {\bf H}({\bf x}^{(K)})^{-1}={\bf H}({\bf a})^{-1}\left({\bf I}-{\bf K}{\bf H}({\bf a})^{-1}+O({\boldsymbol\epsilon}^{(K)})^2\right)\tag{17} \end{eqnarray}$

多変数の場合のニュートン法の更新式は以下の式でした。

$\begin{eqnarray} {\bf x}^{(K+1)}&=&{\bf x}^{(K)}-{\bf H}({\bf x}^{(K)})^{-1}\nabla f({\bf x}^{(K)})\\ &=&{\bf a}+{\boldsymbol\epsilon}^{(K)}-{\bf H}({\bf x}^{(K)})^{-1}\nabla f({\bf x}^{(K)})\tag{18} \end{eqnarray}$

$(18)$ の ${\bf H}({\bf x}^{(K)})^{-1}\nabla f({\bf x}^{(K)})$ を計算します。

$\begin{eqnarray} {\bf H}({\bf x}^{(K)})^{-1}\nabla f({\bf x}^{(K)})&=&{\bf H}({\bf a})^{-1}\left({\bf I}-{\bf K}{\bf H}({\bf a})^{-1}+O({\boldsymbol\epsilon}^{(K)})^2\right) \left({\bf H}({\bf a}){\boldsymbol\epsilon}^{(K)}+\frac{1}{2}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\right)\\ &=&\left({\bf H}({\bf a})^{-1}-{\bf H}({\bf a})^{-1}{\bf K}{\bf H}({\bf a})^{-1}+O({\boldsymbol\epsilon}^{(K)})^2\right) \left({\bf H}({\bf a}){\boldsymbol\epsilon}^{(K)}+\frac{1}{2}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\right)\\ &=&{\boldsymbol\epsilon}^{(K)}-\frac{1}{2}{\bf H}({\bf a})^{-1}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\tag{19} \end{eqnarray}$

$(19)$ を $(18)$ に代入します。

$\begin{eqnarray} &&{\bf x}^{(K+1)}={\bf a}+{\boldsymbol\epsilon}^{(K)}-{\boldsymbol\epsilon}^{(K)}+\frac{1}{2}{\bf H}({\bf a})^{-1}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\\ &&\Leftrightarrow{\bf a}+{\boldsymbol\epsilon}^{(K+1)}={\bf a}+\frac{1}{2}{\bf H}({\bf a})^{-1}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\\ &&\Leftrightarrow{\boldsymbol\epsilon}^{(K+1)}=\frac{1}{2}{\bf H}({\bf a})^{-1}{\bf K}{\boldsymbol\epsilon}^{(K)}+O({\boldsymbol\epsilon}^{(K)})^3\tag{20} \end{eqnarray}$

$(6)$ より、高次の微小量 $O(\epsilon^{(K)})^3$ を無視したときに、 $\epsilon_i^{(K+1)}$ は以下のようになります。

$\begin{eqnarray} \epsilon_i^{(K+1)}=\frac{1}{2}\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^nH_{ij}^{-1}({\bf a})\frac{\partial^3f({a})}{\partial x_j\partial x_k\partial x_l}\epsilon_k^{(K)}\epsilon_l^{(K)}\tag{21} \end{eqnarray}$

$(21)$ より、誤差はほぼ前ステップの誤差の2乗に比例することが分かります。

まだ説明していない $(17)$ の式変形について説明します。

一般に行列 $\bf X$ が微小量 $\epsilon$ に関して ${\bf X}={\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots$ と展開できるとします。
ただし、 ${\bf A}_k=O(\epsilon^k)$ です。
この逆行列が以下のように展開されるとします。

$\begin{eqnarray} ({\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots)^{-1}={\bf B}_0+{\bf B}_1+{\bf B}_2+\cdots\tag{22} \end{eqnarray}$

ただし、 ${\bf B}_k=O(\epsilon^k)$ です。
$(22)$ の両辺に ${\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots$ を左から掛けます。

$\begin{eqnarray} {\bf I}=({\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots)({\bf B}_0+{\bf B}_1+{\bf B}_2+\cdots)\tag{23} \end{eqnarray}$

$(23)$ の右辺を展開します。

$\begin{eqnarray} ({\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots)({\bf B}_0+{\bf B}_1+{\bf B}_2+\cdots)={\bf A}_0{\bf B}_0+({\bf A}_0{\bf B}_1+{\bf A}_1{\bf B}_0)+({\bf A}_0{\bf B}_2+{\bf A}_1{\bf B}_1+{\bf A}_2{\bf B}_0)+\cdots\tag{24} \end{eqnarray}$

$(23)$ の両辺の $\epsilon$ の同じ次数の係数比較します。

$\begin{eqnarray} \left\{ \begin{array}{l} {\bf A}_0{\bf B}_0={\bf I}\\ {\bf A}_0{\bf B}_1+{\bf A}_1{\bf B}_0={\bf O}\\ ({\bf A}_0{\bf B}_2+{\bf A}_1{\bf B}_1+{\bf A}_2{\bf B}_0={\bf O} \end{array}\tag{25} \right. \end{eqnarray}$

$(25)$ の連立方程式を解くと、以下のようになります。

$\begin{eqnarray} &&{\bf B}_0={\bf A}_0^{-1},\\ &&{\bf B}_1=-{\bf A}_0^{-1}{\bf A}_1{\bf B}_0=-{\bf A}_0^{-1}{\bf A}_1{\bf A}_0^{-1},\\ &&{\bf B}_2=-{\bf A}_0^{-1}({\bf A}_1{\bf B}_1+{\bf A}_2{\bf B}_0)=-{\bf A}_0^{-1}(-{\bf A}_1{\bf A}_0^{-1}{\bf A}_1{\bf A}_0^{-1}+{\bf A}_2{\bf A}_0^{-1})\tag{26} \end{eqnarray}$

ゆえに次のように展開されます。

$\begin{eqnarray} ({\bf A}_0+{\bf A}_1+{\bf A}_2+\cdots)^{-1}={\bf A}_0^{-1}({\bf I}-{\bf A}_1{\bf A}_0^{-1}+(-{\bf A}_1{\bf A}_0^{-1}{\bf A}_1{\bf A}_0^{-1}+{\bf A}_2{\bf A}_0^{-1}))\tag{27} \end{eqnarray}$

偉人の名言

f:id:olj611:20210619051641p:plain:w300
知識への投資には常に最高の利息がついてくる
ベンジャミン・グラハム

参考文献

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

動画

なし