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

1変数の場合

2階導関数 $f''(x)$ も計算できるなら、効率的な方法があります。

$x$ 軸上の点 $\bar{x}$ の近くの点 $\bar{x}+\Delta x$ での関数 $f(x)$ の値はテイラー展開して、

$\begin{eqnarray} f(\bar{x}+\Delta x)=f(\bar{x})+f'(\bar{x})\Delta x+\frac{1}{2}f''(\bar{x})\Delta x^2+\cdots\tag{1} \end{eqnarray}$

と書けます。
ここで、 $\cdots$ は $\Delta x$ の $3$ 次以上の項で、 $\Delta x$ が小さいと急速に小さくなります。
これを無視して、 $\Delta x$ の2次式を最大化(最小化)するために、 $\Delta x$ で微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\rm d}{\rm{d}{\Delta x}}f(\bar{x}+\Delta x)=0\\ &&\Leftrightarrow \frac{\rm d}{\rm{d}{\Delta x}}f(\bar{x})+\frac{\rm d}{\rm{d}{\Delta x}}f'(\bar{x})\Delta x+\frac{\rm d}{\rm{d}{\Delta x}}\frac{1}{2}f''(\bar{x})\Delta x^2 = 0\\ &&\Leftrightarrow f'(\bar{x})+f''(\bar{x})\Delta x = 0\\ &&\Leftrightarrow \Delta x=-\frac{f'(\bar{x})}{f''(\bar{x})}\tag{2} \end{eqnarray}$

$(2)$ より $x$ の近似値は

$\begin{eqnarray} x=\bar{x}-\frac{f'(\bar{x})}{f''(\bar{x})}\tag{3} \end{eqnarray}$

となります。

これを反復する方法をニュートン法と呼びます。
この方法を提案したのはニュートンですが、ラフソンも類似の方法を提案しているので、「ニュートン・ラフソン法」とも呼ばれます。

$(1)$ の高次の項を無視することは、関数 $f(x)$ を2次近似し、その極値を求めることに相当します。

$\begin{eqnarray} f_{\rm II}(x)=f(\bar{x})+f'(\bar{x})\Delta x+\frac{1}{2}f''(\bar{x})\Delta x^2\tag{4} \end{eqnarray}$

イメージを下図に記しました。

1変数の場合のニュートン法 アルゴリズム

1. $x$ の初期値を与える。
2. $\bar{x}\leftarrow x$ とおき、次のように $x$ を更新する。

$\begin{eqnarray} x\leftarrow\bar{x}-\frac{f'(\bar{x})}{f''(\bar{x})}\tag{5} \end{eqnarray}$

3. $|x-\bar{x}| < \delta$ なら終了する。そうでなければステップ2に戻る。

ただし、 $\delta$ は収束判定の定数です。

多変数の場合

点 $(\bar{x}_1,\ldots,\bar{x}_n)$ の近くの点 $(\bar{x}_1+\Delta x_1,\ldots,\bar{x}_n+\Delta x_n)$ での関数 $f(x_1,\ldots,x_n)$ の値はテイラー展開して、

$\begin{eqnarray} f(\bar{x}_1+\Delta x_1,\ldots,\bar{x}_n+\Delta x_n)=\bar{f}+\sum_{i=1}^n\frac{\partial\bar{f}}{\partial x_i}\Delta x_i+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2\bar{f}}{\partial x_i\partial x_j}\Delta x_i\Delta x_j+\cdots\tag{6} \end{eqnarray}$

と書けます。
ここで、バーは点 $(\bar{x}_1,\ldots,\bar{x}_n)$ での値を表します。
$(6)$ の $\cdots$ を無視して、 $\Delta x_i$ で偏微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial \Delta x_i}f(\bar{x}_1+\Delta x_1,\ldots,\bar{x}_n+\Delta x_n)=0\\ &&\Leftrightarrow\frac{\partial}{\partial\Delta x_i}\bar{f}+\frac{\partial}{\partial\Delta x_i}\sum_{i=1}^n\frac{\partial\bar{f}}{\partial x_i}\Delta x_i+\frac{\partial}{\partial\Delta x_i}\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2\bar{f}}{\partial x_i\partial x_j}\Delta x_i\Delta x_j=0\\ &&\Leftrightarrow\frac{\partial\bar{f}}{\partial x_i}+\sum_{j=1}^n\frac{\partial^2\bar{f}}{\partial x_i\partial x_j}\Delta x_j=0\\ &&\Leftrightarrow\sum_{j=1}^n\frac{\partial^2\bar{f}}{\partial x_i\partial x_j}\Delta x_j=-\frac{\partial\bar{f}}{\partial x_i}\tag{7} \end{eqnarray}$

ヘッセ行列

$\begin{eqnarray} {\bf H}=\begin{pmatrix} \frac{\partial^2f}{\partial x_1^2} & \cdots & \frac{\partial^2f}{\partial x_1\partial x_n}\\ \vdots & \ddots & \vdots\\ \frac{\partial^2f}{\partial x_n\partial x_i} & \cdots & \frac{\partial^2f}{\partial x_n^2}\\ \end{pmatrix}\tag{8} \end{eqnarray}$

の点 $(\bar{x}_1,\ldots,\bar{x}_n)$ における値を $\bar{\bf H}$ とおきます。
$(8)$ の成分表記をベクトルと行列でまとめて書くと、以下のようになります。

$\begin{eqnarray} &&\bar{\bf H}\Delta{\bf x}=-\nabla\bar{f}\\ &&\Leftrightarrow\Delta{\bf x}=-\bar{\bf H}^{-1}\nabla\bar{f}\tag{9} \end{eqnarray}$

$(9)$ より ${\bf x}$ の近似値は

$\begin{eqnarray} {\bf x}=\bar{\bf x}-\bar{\bf H}^{-1}\nabla\bar{f}\tag{10} \end{eqnarray}$

となります。

$(6)$ の高次の項を無視することは、関数 $f(x)$ を2次近似し、その極値を求めることに相当します。

$\begin{eqnarray} f_{\rm II}(x_1,\ldots,x_n)=\bar{f}+\sum_{i=1}^n\frac{\partial\bar{f}}{\partial x_i}(x_i-\bar{x}_i)+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2\bar{f}}{\partial x_i\partial x_j}(x_i-\bar{x}_i)(x_j-\bar{x}_j)\tag{11} \end{eqnarray}$

多変数の場合 - ベクトルで計算

上記では、 $\Delta x_i$ で微分しましたが、 $\Delta{\bf x}$ で微分することにより、式 $(9)$ を導いていきます。

点 $\bar{\bf x}$ の近くの点 $\bar{\bf x}+\Delta {\bf x}$ での関数 $f({\bf x})$ の値はテイラー展開して、

$\begin{eqnarray} f(\bar{\bf x}+\Delta {\bf x})\simeq f(\bar{\bf x})+\langle\nabla f(\bar{\bf x}),\Delta {\bf x}\rangle + \frac{1}{2}\langle\nabla^2 f(\bar{\bf x})\Delta {\bf x},\Delta {\bf x}\rangle+\cdots\tag{12} \end{eqnarray}$

と書けます。
$(12)$ の $\cdots$ を無視して、 $\Delta {\bf x}$ で偏微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial f(\bar{\bf x}+\Delta {\bf x})}{\partial\Delta {\bf x}}={\bf 0}\\ &&\Leftrightarrow \frac{\partial f(\bar{\bf x})}{\partial\Delta {\bf x}}+\frac{\partial\langle\nabla f(\bar{\bf x}),\Delta {\bf x}\rangle}{\partial\Delta {\bf x}} + \frac{1}{2}\frac{\partial\langle\nabla^2 f(\bar{\bf x})\Delta {\bf x},\Delta {\bf x}\rangle}{\partial\Delta {\bf x}}={\bf 0}\\ &&\Leftrightarrow \nabla f(\bar{\bf x})+\nabla^2 f(\bar{\bf x})\Delta {\bf x}={\bf 0}\\ &&\Leftrightarrow\Delta {\bf x}= -\nabla^2 f(\bar{\bf x})^{-1}\nabla f(\bar{\bf x})\tag{13} \end{eqnarray}$