ホーム » その他 » ニュートン法って何？

ニュートン法って何？

投稿者: junko.hosoda in その他投稿日: 2018-10-17

こんにちは。

初の記事はニュートン法についてです。（理論編）と（実装編）の２回に分けて進めていきます。今回はまずニュートン法を定義から確認し、そのイメージを掴みましょう。ではスタート。

簡単のため先ずは一次元の場合を考える。ある種の関数は方程式の解の形で現れる。

例えば $\sqrt{a}$ という関数は $\mathbb{R}_+$ に方程式 $x^2-a=0$ の正の解を対応させる関数です。このような関数の値を求めることは方程式を解くこと、すなはち $f(x)=0$ を満たすxを求めることと同値です。その方程式が線形つまり $ax+b=0$ のような形をしているときはその解は容易に求まります（多次元になると連立方程式を扱うことになるのでそういった意味では難しい）。そこで問題になるのが方程式が非線形の場合です。

ニュートン法はそんな非線形な方程式を解くための数値解法の一つです。先ずはその定義を見ましょう。 $f:\mathbb{R}\rightarrow\mathbb{R}$ が

区間 $[a,b]$ で二回微分可能
$f'(x)>0, \forall x\in [a,b]$ (単調増加性)
$f''(x)>0, \forall x\in [a,b]$ (下に凸)
$f(x)=0$ が解を持つ

を満たし、さらにfおよびf’が計算可能であるとき
”前の数xから $x-\frac{f(x)}{f'(x)}$ を計算し、それを次のxとする”を繰り返すことにより $f(x)=0$ の $[a,b]$ の解（単調性の仮定より唯一）が求まる。

なんでこれで解が求まるんだ！と思いますよね、実数の連続性とか中間値の定理とかを使うと証明できるんですけどここではもっと直感的に理解しましょう。

先ず一つ $x_0$ を取ります。関数 $f(x_0)$ を通る直線は

$y = f(x_0) + f'(x_0)(x-x_0)$

と書けます。ではこの直線とx軸との交点、つまり

$0 = f(x_0) + f'(x_0)(x-x_0)$

を見てみます。式を変形すると

$x = x_0 - \frac{f(x_0)}{f'(x_0)}$

となります。 $f'(x_0)>0$ を仮定すると $f(x_0)>0$ の時、右辺第２項は正なので

$x < x_0$

が成り立ちます。（逆も同様）さらに単調増加性より

$f(x) < f(x_0)$

です。式から分かることは関数の値を減少するように座標の移動しているんですね。これを図で見てみると

となり、確かに求める解（赤色）に近づくように移動していることがわかります。これがニュートン法です。

ニュートン法についての説明を終えて余談に入ります。

機械学習では目的関数の最適化が目標になります。目的関数とはこの場合で言えば $x^2-a$ です。そしてこの場合の最適化とは最小化を意味します。（最大化よりも最小化を最適化という方が個人的に多いと思います）そこでどうやって最適化しようか、とみんな悩みます。その手法の一つが今回のニュートン法です。他にも最急降下法、新しいものではAdamなどがあります。どれが一番良い、ということはないので状況に応じて良いものを選びましょう。

また、上の方で直線の式を使いましたが一般的にはテイラー展開を使って話を進めることが多いです。テイラー展開は関数の多項式近似です。条件はありますが、ほとんどの関数はテイラー展開により多項式に変換できます。なので今回の場合だと $\sqrt{a}$ をニュートン法で求めましたがテイラー展開によりもっと簡単に求めることができます。

$f(2) = \sqrt{2} = f(1) + \frac{1}{2}(2-1)^1 - \frac{1}{8}(2-1)^1 + \frac{1}{16}(2-1)^1 - \cdots$

これは $x=1$ 周りのテイラー展開です。機械学習に限らず問題を考えるときに局所的、小さい範囲で考えることは多いと思います。テイラー展開は局所的に関数を見ることができるのでそういう時に便利だと思います。

余談はこれくらいにして次回はニュートン法の簡単な実装とテイラー展開について見てみたいと思います。

指摘＆アドバイスお願いします。

引用画像：　http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod.aspx

タグ: テイラー展開, ニュートン法, 最適化

ニュートン法って何？

コメントする コメントをキャンセル

コメントするコメントをキャンセル