ニュートン法（多変数の場合） - 機械学習に詳しくなりたいブログ

概要

ニュートン法は、f(x)=0の解αを求める数値計算法で、最急降下法に比べて収束が早い特徴があります。ニュートン・ラフソン法とも呼びます。この記事では多変数の場合におけるアルゴリズムについて記載しています。多変数の場合、 $f(\mathbf x)=0$ の解を求めるには $\mathbf x$ の次元数分の連立方程式が必要です。この解を求めることから議論が出発し、最終的に、ある多変数関数 $f(\mathbf x)$ の $f^{\prime}(\mathbf x)=0$ の解を求めるニュートン法の更新式を求めます。機械学習においては連立方程式の解を求める更新式よりも、勾配が０となる解を求める更新式のほうが重要度が高いのではと思います。

1変数の場合は以下の記事に記載しました。

www.iwanttobeacat.com

アルゴリズム

の続きです。今回は多変数のニュートン法です。 $f_1(x_1, \cdots ,x_n)=0, \cdots, f_n(x_1, \cdots ,x_n)=0$ のような $n$ 個の連立方程式

${\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} f_1(x_1, \cdots ,x_n)=0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ f_n(x_1, \cdots ,x_n)=0 \tag{1} \end{array} \right. \end{eqnarray} }$

の解を、1変数のニュートン法と同様に各関数 $f$ を1次近似し、近似解を求めることを考えます。点 $(x^{\prime}_1, \cdots, x^{\prime}_n)$ における1次近似は、接線、接平面の公式により

$g_{i}(x_1, \cdots ,x_n) = \bar{f}_{i x_{1}}(x_1-x^{\prime}_1) + \cdots +\bar{f}_{i x_{n}}(x_n-x^{\prime}_n) + f_i(x^{\prime}_1, \cdots ,x^{\prime}_n)\tag{2}$

です。なおここで $\bar{f}_{i x_{1}}$ は、 $f_i$ を $x_1$ で偏微分し、 $(x^{\prime}_1, \cdots, x^{\prime}_n)$ を代入したものを表します。各関数で $g_i$ を求め、 $g_i=0$ を行列式でまとめて書けば、

$\left( \begin{array}{ccc} \bar{f}_{1 x_1} & \ldots & \bar{f}_{1 x_n} \\ \vdots & \ddots & \vdots \\ \bar{f}_{n x_1} & \ldots &\bar{f}_{n x_n} \end{array} \right) \left( \begin{array}{c} x_1 - x^{\prime}_1 \\ \vdots \\ x_n - x^{\prime}_n \end{array} \right) + \left( \begin{array}{c} \bar{f}_1 \\ \vdots \\ \bar{f}_n \end{array} \right) =0 \tag{3}$

となります。ここで $\bar{f}_1$ は、 $f_1$ に $(x^{\prime}_1, \cdots, x^{\prime}_n)$ を代入したものを表します。式(3)を整理すれば、

$\left( \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right) = \left( \begin{array}{c} x^{\prime}_1 \\ \vdots \\ x^{\prime}_n \end{array} \right) - \left( \begin{array}{ccc} \bar{f}_{1 x_1} & \ldots & \bar{f}_{1 x_n} \\ \vdots & \ddots & \vdots \\ \bar{f}_{n x_1} & \ldots &\bar{f}_{n x_n} \end{array} \right)^{-1} \left( \begin{array}{c} \bar{f}_1 \\ \vdots \\ \bar{f}_n \end{array} \right) \tag{4}$

となり、1次近似による近似解が求められました。1変数のときと同様に、これを繰り返せば真の解に近づいていきます。

さて、式(4)で求められるものは $f_1=0,\cdots,f_n=0$ となる $(x_1,\cdots,x_n)$ です。ある１つの関数における $\displaystyle \frac{\partial f_1}{\partial x_1}=0,\cdots,\frac{\partial f_1}{\partial x_n}=0$ となる点が求めたければ、式(4)において $\displaystyle f_1 \to \frac{\partial f_1}{\partial x_1},\cdots,f_n \to \frac{\partial f_1}{\partial x_n}$ と置き換えれば、

$\left( \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right) = \left( \begin{array}{c} x^{\prime}_1 \\ \vdots \\ x^{\prime}_n \end{array} \right) - \left( \begin{array}{ccc} \bar{f}_{1 x_1 x_1} & \ldots & \bar{f}_{1 x_n x_1} \\ \vdots & \ddots & \vdots \\ \bar{f}_{1 x_1 x_n} & \ldots &\bar{f}_{1 x_n x_n} \end{array} \right)^{-1} \left( \begin{array}{c} \bar{f}_{1 x_1} \\ \vdots \\ \bar{f}_{1 x_n} \end{array} \right) =0 \tag{5}$

となります。ここで右辺の行列は点 $(x^{\prime}_1, \cdots, x^{\prime}_n)$ におけるヘッセ行列になっています。*1　 $\mathbf{x}=(x_1,\cdots,x_n)$ 、 $\mathbf{x}^{\prime}=(x^{\prime}_1, \cdots, x^{\prime}_n)$ とし、ヘッセ行列 $\mathbf H$ と勾配の記号を用いれば、

$\mathbf{x} = \mathbf{x}^{\prime} - \bar{\mathbf{H}}^{-1} \nabla \bar{f} \tag{6}$

となります。ニュートン法（1変数の場合）の式(4)を多変数に拡張した形になっています。

以上をまとめると、

$f^{\prime}(\mathbf x)=0$ の解を求めるニュートン法のアルゴリズム

$\mathbf x$ の初期値を設定する。
$\mathbf{x}_{new} = \mathbf{x}_{old} - \bar{\mathbf{H}}^{-1} \nabla \bar{f}$ 　によって $\mathbf x$ を更新する
停止条件（更新量が一定値以下になるなど）が満たされるまで手順２を繰り返す