ニュートン法と勾配降下法の違い

こちらもおすすめ
準備：非線形方程式の解法としてのニュートン法
最小化問題の解法としてのニュートン法
勾配降下法（最急降下法）
準ニュートン法
あわせて読みたい
こちらもおすすめ

【初心者から上級者まで】Pythonプログラミングを勉強するのにおすすめの本：６冊を難易度順に紹介【感想あり】 | Quant College

【初心者向け】LIBOR廃止とRFR移行の体系的まとめ | Quant College

準備：非線形方程式の解法としてのニュートン法

まず準備として、非線形方程式の解法としてのニュートン法を簡単にレビューしておく。非線形方程式の解法とは、一般の関数f(x)がゼロとなるxを求める方法である。

一次までのテーラー展開により、

f(x) ~ f(a) + f'(a)(x – a)

とf(x)をaの周りで一次近似する。右辺がゼロになるxを求めると、

x ~ a – f(a) / f'(a)

となり、このaをx(k), xをx(k+1)などと書き換えてイコールでむすんでしまえば、

x(k+1) = x(k) – f(x(k)) / f'(x(k))

となり、ニュートン法におけるx(k)の更新式を得る。

最小化問題の解法としてのニュートン法

次に、今度は非線形方程式の解法ではなく、最小化問題の解法を考える。

最小化の必要条件として一階微分がゼロ、

f'(x) = 0

を解くことを考えると、これはまさに、上の非線形方程式の解法において、f(x)をf'(x)に置き換えたものである。これにより最小化問題が非線形方程式に帰着する。

ニュートン法の更新式に当てはめると、

x(k+1) = x(k) – f'(x(k)) / f”(x(k))

を得る。これが最小化問題の解法で出てくるニュートン法である。

実際に応用するときは、xは１変数ではなく多変数であることから、xはベクトル、f'(x)はベクトル、f”(x)は行列である。

二階微分が並んだ行列f”(x)はヘッセ行列と呼ばれ、それが分母に来ているから、ヘッセ行列の逆行列を、勾配ベクトルf'(x)に左から乗じることになる。

しかし実際に応用するときは、ベクトルxのサイズが大きすぎて、ヘッセ行列のサイズも巨大になってしまうため、ヘッセ行列の逆行列を求めるのにかなり時間がかかる。そこで、この逆行列の計算を避けることにより、計算速度を上げる方法がいくつもある。

勾配降下法（最急降下法）

そのうち最もシンプルなのが、勾配降下法とか最急降下法と呼ばれるものである。この方法は、ヘッセ行列の逆行列を、単位行列のスカラー倍で置き換えてしまう。

x(k+1) = x(k) – ηI f'(x(k))

ここでIは単位行列で、ηは学習率と呼ばれる。本ではよく、１変数のケースとして単位行列Iを省略して書いてある。

二階微分の項をごっそり落としたことで、

二階微分の計算が不要
逆行列の計算が不要

となり、高速化できる。

準ニュートン法

しかし勾配降下法は単純化しすぎていて、解がジグザグに動いて収束がよろしくない。

同様にヘッセ行列の逆行列を計算しない方法として、準ニュートン法などがある。準ニュートン法は、二階微分の項をごっそり落とすのではなく、ヘッセ行列の逆行列を、よりシンプルな行列でうまく近似しよう、という方法である。