抑えておきたいニュートン法と勾配法(Gradient Descent)の解釈の違いに関して

最適化問題を解くにあたって、勾配法(Gradient Descent)と同様によく用いられるのがニュートン法である。一方で、元々の数式がシンプルな勾配法とは異なり、ニュートン法は式が難しく表記されることが多いような印象を受ける。
ニュートン法の解説に関しては「ゼロから作るDeep Learning③」の解説が非常にわかりやすいと思われたので、当記事では「ゼロから作るDeep Learning③」の記載を元にニュートン法と勾配法の違いについて更新式の違いに着目することで確認を行う。

勾配法(Gradient Descent)

勾配法の手法の確認

勾配法(Gradient Descent)は最適化問題を繰り返し演算を用いて解く手法である。以下、下に凸の関数$f(x)$に関して$f(x)$が最小になる$x$を求めることを考える。

$f(x)$に対して勾配法を用いるにあたっては、下記の漸化式を用いた更新式を用いる。
$$
\large
\begin{align}
x_{n+1} = x_{n} – \alpha f'(x_{n}) \quad (1)
\end{align}
$$

上記の解釈にあたっては、「点$x_n$における傾きのマイナスの向きに$x_n$を動かす＝傾きが正なら数直線の左、傾きが負なら数直線の右に動かす」と考えれば良い。これにより、少なくとも点$x_n$よりも小さい点がある向きに動かして$x_{n+1}$を得ると考えることができる。

また、$\alpha$は学習率であり、$x_n$をどのくらい動かして$x_{n+1}$を得るかということを制御すると考えれば良い。

具体例を元に確認

下に凸の関数$f(x)=x^2$に対して、前項で確認した勾配法を元に値の更新を確認する。計算の簡易化にあたって、$x_0=8, \alpha=0.25$と定義する。このとき$x_1, x_2, x_3$は下記のように計算することができる。
$$
\large
\begin{align}
x_1 &= x_{0} – \alpha f'(x_{0}) \\
&= x_{0} – 0.25 \times 2x_0 \\
&= 0.5x_{0} = 4 \\
x_2 &= x_{1} – \alpha f'(x_{1}) \\
&= x_{1} – 0.25 \times 2x_1 \\
&= 0.5x_{1} = 2 \\
x_3 &= x_{2} – \alpha f'(x_{2}) \\
&= x_{2} – 0.25 \times 2x_2 \\
&= 0.5x_{2} = 1
\end{align}
$$

上記を確認すると、$x_0=8, x_1=4, x_2=2, x_3=1$のように、徐々に値が半分に変化することが確認できる。

ここまでの内容を元に一般項の$x_n$について考える。前項で表した$(1)$式は$x_0=8, \alpha=0.25$のとき下記のように変形を行うことができる。
$$
\large
\begin{align}
x_{n+1} &= x_{n} – \alpha f'(x_{n}) \\
&= x_{n} – 0.25 \times 2 x_n \\
&= 0.5x_{n}
\end{align}
$$
上記は数列$\{x_n\}$が公比$0.5$の等比数列であることを表している。

ニュートン法

$2$次のテイラー展開による関数の近似と最小値

ニュートン法は$x=a$の周辺における$2$次のテイラー展開による関数近似を元に理解するとわかりやすい。
$$
\large
\begin{align}
f(x) &\simeq \frac{f(a)}{0!}(x-a)^0 + \frac{f'(a)}{1!}(x-a)^1 + \frac{f^{”}(a)}{2!}(x-a)^2 \\
&= f(a) + f'(a)(x-a) + \frac{f^{”}(a)}{2}(x-a)^2 = g(x)
\end{align}
$$

上記のように近似を行なった関数$g(x)$が最小値を持つ$x$の値を考えるにあたって、$g'(x)$の計算を行う。
$$
\large
\begin{align}
g'(x) &= \frac{d}{dx} \left( f(a) + f'(a)(x-a) + \frac{f^{”}(a)}{2}(x-a)^2 \right) \\
&= f'(a) + \frac{f^{”}(a)}{2} \cdot 2(x-a) \\
&= f'(a) + f^{”}(a)(x-a)
\end{align}
$$

$g(x)$は下に凸の関数なので、$g'(x)=0$の際に$g(x)$は最小値を持つ。
$$
\large
\begin{align}
g'(x) &= 0 \\
f'(a) + f^{”}(a)(x-a) &= 0 \\
\frac{f'(a)}{f^{”}(a)} + x – a &= 0 \\
x &= a – \frac{f'(a)}{f^{”}(a)}
\end{align}
$$

ここまでの議論により、$g(x)$は$\displaystyle x = a – \frac{f'(a)}{f^{”}(a)}$の時に最小値を持つ。

ニュートン法の手法の確認

ニュートン法は前節の$\displaystyle x = a – \frac{f'(a)}{f^{”}(a)}$の式に対して、$x_{n}=a, x_{n+1}=x$のように置き換えることで更新式を作成することができる。
$$
\large
\begin{align}
x_{n+1} = x_{n} – \frac{f'(x_n)}{f^{”}(x_n)}
\end{align}
$$

具体例を元に確認

ニュートン法は前節の$\displaystyle x = a – \frac{f'(a)}{f^{”}(a)}$の式に対して、$x_{n}=a, x_{n+1}=x$のように置き換えることで更新式を作成することができる。
$$
\large
\begin{align}
x_{n+1} = x_{n} – \frac{f'(x_n)}{f^{”}(x_n)}
\end{align}
$$

具体例を元に確認

勾配法における具体例と同様に$f(x) = x^2, x_0 = 8$に対してニュートン法を考える。このとき$f^{”}(x)=2$より、$x_1$は下記のように計算することができる。
$$
\large
\begin{align}
x_1 &= x_{0} – \frac{f'(x_0)}{f^{”}(x_0)} \\
&= x_{0} – \frac{2 x_0}{2} \\
&= 0
\end{align}
$$
上記では繰り返し計算を行うことなく結果が導出できたが、これはニュートン法が$2$次のテイラー展開による関数近似に基づくことに起因すると考えるとわかりやすい。

上記の例ではニュートン法がそのまま答えを出すことより、比較になりにくいので、$f(x)=x^4$に関しても以下考える。$f'(x)=4x^3$より、勾配法の更新式は下記のように表される。
$$
\large
\begin{align}
x_{n+1} &= x_{n} – \alpha f'(x_{n}) \\
&= x_{n} – \alpha \times 4x_n^3 \\
&= x_{n} – 4 \alpha x_n^3
\end{align}
$$
上記の式は$\alpha=0.0025$の周辺に$\alpha$を設定すれば、徐々に最小値に近づくのが確認できるが、$\alpha$の選択が難しく、値が発散することも多く収束させるのも難しい。$x_{0} – 4 \alpha x_0^3 = 0$を$\alpha$に関して解くことで$\displaystyle \alpha = \frac{1}{4x_0^2}$を導出し、これを用いることで計算を$1$度で行えるが、実際の最適化にあたってはこのように関数形がわかっていないので$\alpha$の設定は難しい。

一方でニュートン法では$f'(x)=4x^3, f^{”}(x)=12x^2$より、更新式は下記のように表される。
$$
\large
\begin{align}
x_{n+1} &= x_{n} – \frac{f'(x_n)}{f^{”}(x_n)} \\
&= x_{n} – \frac{4x_{n}^3}{12x_{n}^2} \\
&= 0.75 x_n
\end{align}
$$
上記は数列${ x_n }$が公比$0.75$の等比数列であることを表しており、勾配法より少ない繰り返し数で結果が得られることが多いことが読み取れる。

勾配法・ニュートン法の解釈

ここまでで勾配法とニュートン法に関して確認を行なったが、以下ではそれぞれの更新式について確認を行うことで手法の解釈を確認する。
・勾配法
$$
\large
\begin{align}
x_{n+1} = x_{n} – \alpha f'(x_{n})
\end{align}
$$
・ニュートン法
$$
\large
\begin{align}
x_{n+1} = x_{n} – \frac{f'(x_n)}{f^{”}(x_n)}
\end{align}
$$

$2$つの手法の更新式を比較すると、勾配法の学習率$\alpha$を$2$階微分を用いた$\displaystyle \frac{1}{f^{”}(x_n)}$で置き換えたのがニュートン法であることがわかる。

よって、$\alpha$の調整が必要な勾配法に対して、ニュートン法は調整を行う必要がなく、実用上ニュートン法の方が収束させやすいように思われる。古典的な最適化では勾配法よりもニュートン法がベースに用いられることが多い。

一方で、ニュートン法は$2$階微分を計算する必要があり、Deep Learningのような複雑な計算に対しては$1$階微分に基づく勾配法の方がよく用いられている。