📂最適化理論

割線法: ニュートン法

定義^{1 2}

目的関数 $J : \mathbb{R}^{n} \to \mathbb{R}$を最適化する問題で、次の繰り返しアルゴリズムをニュートン法^{Newton’s method}という。

$$\begin{equation} \mathbf{x}_{n+1} = \mathbf{x}_{n} - H^{-1}(\mathbf{x}_{n}) \nabla J(\mathbf{x}_{n}) \end{equation}$$

$\nabla J$は勾配で、$H$は$J$のヘッセ行列だ。

導出

$J$を2次導関数の項までテイラー展開で近似すると、次の通り。

$$J(\mathbf{x}) \approx J(\mathbf{x}_{0}) + (\mathbf{x} - \mathbf{x}_{0})^{T} \nabla J (\mathbf{x}_{0}) + \dfrac{1}{2!}(\mathbf{x} - \mathbf{x}_{0})^{T} (H(\mathbf{x}_{0})) (\mathbf{x} - \mathbf{x}_{0})$$

$J$を最小にする$\mathbf{x}$を見つけるために$\mathbf{x}$で微分すると（勾配とヘッセ行列の変数は省略する。）

$$\dfrac{\partial J(\mathbf{x})}{\partial \mathbf{x}} = \nabla J + (\mathbf{x} - \mathbf{x}_{0}) H = \mathbf{0}$$ $$\begin{equation} \implies \mathbf{x}^{\ast} = \mathbf{x}_{0} -H^{-1}\nabla J \end{equation}$$

説明

標準的な勾配降下法が目的関数の最適化のために1次導関数を使用するなら、ニュートン法は2次導関数まで使用する。式を比較すると、学習率$\alpha$がヘッセ行列の逆行列に置き換わっている形で、適応学習率と見ることができる。

$$\begin{align*} \text{Gradient Descent: } \mathbf{x}_{n+1} &= \mathbf{x}_{n} - \alpha \nabla J \\ \text{Newton’s Method: } \mathbf{x}_{n+1} &= \mathbf{x}_{n} - H^{-1} \nabla J \end{align*}$$

導出時にテイラー展開の2次項まで使用されたことに注目しよう。もし$J$が（局所的に）2次関数なら、$(2)$は（局所的に）最適解$\mathbf{x}^{\ast}$を一度で見つける式だ。もちろん、一般にそう良い状況に遭遇するのは難しいので、$(1)$を繰り返して$\mathbf{x}^{\ast}$を見つけなければならない。

逆行列の計算が含まれることを考えると、実際に使用するには便利なアルゴリズムではないかもしれないと推測できる。ヘッセ行列を保存するだけでも多くのメモリを消費し、$n \times n$行列の逆行列を計算するコストは$\mathcal{O}(n^{3})$で、$n$が大きい場合には、逆行列を計算する時間で普通に勾配降下法を何度か行った方が効率的かもしれない。特にディープラーニングでは、人工ニューラルネットワークが高性能を発揮するためには多くのパラメータが必要で、ChatGPT-3.5が1750億個のパラメータを持っていることを考えると、ニュートン法で学習させることを期待するのは難しい。ヘッセ行列の高い計算コストを克服するための様々な改良アルゴリズムが考案されている。

下に、一変数の時の式を見ると根を見つける際のニュートン法と同じ形になっているのがよくわかるだろう。

$$x_{n+1} = x_{n} - \dfrac{f^{\prime}(x_{n})}{f^{\prime \prime}(x_{n})}$$