こんにちは。
初の記事はニュートン法についてです。(理論編)と(実装編)の2回に分けて進めていきます。今回はまずニュートン法を定義から確認し、そのイメージを掴みましょう。ではスタート。
簡単のため先ずは一次元の場合を考える。ある種の関数は方程式の解の形で現れる。
例えば
![Rendered by QuickLaTeX.com \sqrt{a}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-fc3feabd59870f8b605474392224184c_l3.png)
という関数は
![Rendered by QuickLaTeX.com \mathbb{R}_+](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-262ebd02d62c9c1b9703729251c17062_l3.png)
に方程式
![Rendered by QuickLaTeX.com x^2-a=0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-fb05ac60947a0c83aac271b577d990db_l3.png)
の正の解を対応させる関数です。このような関数の値を求めることは方程式を解くこと、すなはち
![Rendered by QuickLaTeX.com f(x)=0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-0bce6c022ed0fc63f4659af75888f96c_l3.png)
を満たすxを求めることと同値です。その方程式が線形つまり
![Rendered by QuickLaTeX.com ax+b=0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-b2c5a97201db17cfbef7b7550aa81e23_l3.png)
のような形をしているときはその解は容易に求まります(多次元になると連立方程式を扱うことになるのでそういった意味では難しい)。そこで問題になるのが方程式が非線形の場合です。
ニュートン法はそんな非線形な方程式を解くための数値解法の一つです。先ずはその定義を見ましょう。
![Rendered by QuickLaTeX.com f:\mathbb{R}\rightarrow\mathbb{R}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-8632e776521892b856a06775145c2ca5_l3.png)
が
- 区間
で二回微分可能
(単調増加性)
(下に凸)
が解を持つ
を満たし、さらにfおよびf’が計算可能であるとき
”前の数xから
![Rendered by QuickLaTeX.com x-\frac{f(x)}{f'(x)}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-ec742eb9e82a37d6dc9edf95241b9854_l3.png)
を計算し、それを次のxとする”を繰り返すことにより
![Rendered by QuickLaTeX.com f(x)=0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-0bce6c022ed0fc63f4659af75888f96c_l3.png)
の
![Rendered by QuickLaTeX.com [a,b]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-fcda5ef4ae327e1afef79dc73df91703_l3.png)
の解(単調性の仮定より唯一)が求まる。
なんでこれで解が求まるんだ!と思いますよね、実数の連続性とか中間値の定理とかを使うと証明できるんですけどここではもっと直感的に理解しましょう。
先ず一つ
![Rendered by QuickLaTeX.com x_0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-87f2a80bc63f8d7bc3df68c45a787402_l3.png)
を取ります。関数
![Rendered by QuickLaTeX.com f(x_0)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3b8c69aa19a8159a38ec6e918f5a89da_l3.png)
を通る直線は
![Rendered by QuickLaTeX.com \[y = f(x_0) + f'(x_0)(x-x_0)\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-c8652f45b05a8efac166f3811a144d2d_l3.png)
と書けます。ではこの直線とx軸との交点、つまり
![Rendered by QuickLaTeX.com \[0 = f(x_0) + f'(x_0)(x-x_0) \]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-eba4b6c66618f974339d265a14ad7c65_l3.png)
を見てみます。式を変形すると
![Rendered by QuickLaTeX.com \[x = x_0 - \frac{f(x_0)}{f'(x_0)}\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-cb5bdb818fe49b2c11b08ab7bc9bbb41_l3.png)
となります。
![Rendered by QuickLaTeX.com f'(x_0)>0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-37b6f2da2364acd77eec16657a289275_l3.png)
を仮定すると
![Rendered by QuickLaTeX.com f(x_0)>0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-bf012ff3454bae2fe05f3a0868548245_l3.png)
の時、右辺第2項は正なので
![Rendered by QuickLaTeX.com \[x < x_0\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d481fcd281c4ea0a0650b7da551f10b5_l3.png)
が成り立ちます。(逆も同様)さらに単調増加性より
![Rendered by QuickLaTeX.com \[f(x) < f(x_0)\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-158d2d37499cc45cf76db7f4a58f2c11_l3.png)
です。式から分かることは関数の値を減少するように座標の移動しているんですね。これを図で見てみると
![](http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod_Files/image001.png)
となり、確かに求める解(赤色)に近づくように移動していることがわかります。これがニュートン法です。
ニュートン法についての説明を終えて余談に入ります。
機械学習では目的関数の最適化が目標になります。目的関数とはこの場合で言えば
![Rendered by QuickLaTeX.com x^2-a](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-8dcd2ed1d64390583afb36b2936d804b_l3.png)
です。そしてこの場合の最適化とは最小化を意味します。(最大化よりも最小化を最適化という方が個人的に多いと思います)そこでどうやって最適化しようか、とみんな悩みます。その手法の一つが今回のニュートン法です。他にも最急降下法、新しいものではAdamなどがあります。どれが一番良い、ということはないので状況に応じて良いものを選びましょう。
また、上の方で直線の式を使いましたが一般的にはテイラー展開を使って話を進めることが多いです。テイラー展開は関数の多項式近似です。条件はありますが、ほとんどの関数はテイラー展開により多項式に変換できます。なので今回の場合だと
![Rendered by QuickLaTeX.com \sqrt{a}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-fc3feabd59870f8b605474392224184c_l3.png)
をニュートン法で求めましたがテイラー展開によりもっと簡単に求めることができます。
![Rendered by QuickLaTeX.com \[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\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a7ddb2d58c64686dc6ad45c216fd9582_l3.png)
これは
![Rendered by QuickLaTeX.com x=1](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3330a01aa4d7d81947b71297d8623d3b_l3.png)
周りのテイラー展開です。機械学習に限らず問題を考えるときに局所的、小さい範囲で考えることは多いと思います。テイラー展開は局所的に関数を見ることができるのでそういう時に便利だと思います。
余談はこれくらいにして次回はニュートン法の簡単な実装とテイラー展開について見てみたいと思います。
指摘&アドバイスお願いします。
引用画像: http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod.aspx