機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

ニュートン法(多変数の場合)

概要

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

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


  4. \nabla \bar{f}\nabla {f}\mathbf{x}_{old}を代入したものを表す。
    \bar{\mathbf{H}}^{-1}\mathbf{H}^{-1}\mathbf{x}_{old}を代入したものを表す。

実験

別の記事にしました。

www.iwanttobeacat.com