最適化におけるニュートン法

提供: testwiki
ナビゲーションに移動 検索に移動
（小さなステップサイズでの）関数の最小化に対するニュートン法（赤）と最急降下法（赤）との比較。ニュートン法では（二次の導関数による）曲率の情報を用いるため、反復点はより直接的な経路を描く。

最適化におけるニュートン法（さいてきかにおけるニュートンほう、テンプレート:Lang-en-short）を説明する。微分積分学におけるニュートン法（ニュートン・ラフソン法）では、微分可能関数 f が f(x)=0 の解、つまり根を求めるための反復的手法である。一方で二階微分可能な関数 f を最適化する場合は、その導関数 f′ の根を求めることと等しい。したがって導関数 f′ に対してニュートン法を適用し、f の停留点である方程式 f′(x)=0 の解を求める。これらの解は最小値、最大値、鞍点のいずれか可能性である（詳細は臨界点 (数学) の多変数節および本記事の幾何学的解釈節を参照）。ニュートン法は最適化において関数 f の（大域的）最小値を求める際に重要な手法である。

ニュートン法

最適化での重要な課題である関数の最小化について考える。まず始めに単一実数変数関数のような単変数関数について説明し、次により一般的で実用的である多変数関数について説明を行う。

2回微分可能な関数 f:ℝ→ℝ が与えられたとして、以下の最適化問題を解くことを目指す。

minx∈ℝf(x).

ニュートン法は初期の最適推定値（出発点）x0∈ℝ から出発し、反復ごとに f の2次のテイラー近似を利用して最小化点 x* に収束するような数列 {xk} を生成することで最適化問題を解く。関数 テンプレート:Mathの点 xk 周りにおける2次のテイラー展開は以下のように表される。

f(xk+t)≈f(xk)+f′(xk)t+12f″(xk)t2.

次の反復点 xk+1​ は xk+1=xk+t とすると、2次近似の式を t に関して最小化するような点となる。2次導関数が正であれば2次近似の式は t に関して凸関数であり、最小値は導関数を 0 とすることで求められる。導関数は以下の通りである:

0=ddt(f(xk)+f′(xk)t+12f″(xk)t2)=f′(xk)+f″(xk)t,

したがって最小化は以下の式で達成される。

t=−f′(xk)f″(xk).

以上のことから、ニュートン法は以下の反復を行う:

xk+1=xk+t=xk−f′(xk)f″(xk).

幾何学的解釈

ニュートン法の幾何学的な解釈は各反復点 xk​ において関数 f(x) のグラフに接するような放物線を当てはめ、その点での傾きと曲率が元のグラフと同じになるようにし、その放物線の最大値・最小値（高次元では鞍点も起こりうる）に進むと考えられる（詳細は以下）。もし f が2次関数である場合はニュートン法は1回の反復で極値を厳密に求めることができる。

高次元

単変数関数に対するニュートン法は d>1 のような多次元の一般の問題に対しても適用することができる。一階の導関数を勾配（f′(x)=∇f(x)=gf(x)∈ℝd）、二階導関数をヘッセ行列（f″(x)=∇2f(x)=Hf(x)∈ℝd×d）とすることで、反復の式は以下の通りに書き換えられる： xk+1=xk−[f″(xk)]−1f′(xk),k≥0.

ニュートン法では一般的にステップサイズを γ=1 とすることが多いが、収束性を高めるためにステップサイズ 0<γ≤1 と小さくとることがある：

xk+1=xk−γ[f″(xk)]−1f′(xk).

これは各反復でウルフ条件やより単純かつ効率的なアルミホ条件を満たすことで安定した収束性を保証するために用いられる。ステップサイズが 1 以外の場合、この手法は緩和ニュートン法（テンプレート:Lang-en-short）あるいは減衰ニュートン法 （テンプレート:Lang-en-short）と呼ばれる。

収束性

テンプレート:Math が強凸関数でリプシッツ連続なヘッセ行列をもち、x0 が最適点 x*=arg⁡min⁡f(x) に十分に近い場合、ニュートン法によって生成される点列 x0,x1,x2,… は f の最適点 x* に二次収束する[1]。すなわち、

‖xk+1−x*‖≤12‖xk−x*‖2,∀k≥0.

ニュートン方向の計算

高次元においてニュートン方向 h=−(f″(xk))−1f′(xk) を求めるために直接ヘッセ行列の逆行列を計算することは計算コストが高い。このような場合はヘッセ行列の逆行列を求める代わりに次の線形方程式を解いてベクトル h を計算することで反復の効率を高める：

[f″(xk)]h=−f′(xk)

この方程式はさまざまな行列の分解法や反復法を用いて高い精度で近似的に解くことができる。これらの手法の多くは特定の条件を満たす方程式にのみ適用が可能であり、コレスキー分解や共役勾配法では f″(xk) が正定値行列である場合に適用することができる。この制約は一見すると特殊な条件のように思われるが、実際にはこの条件があることで問題がうまく解けていないことを示す有用な指標ともなりうる。最小化問題において f″(xk) が正定値行列でない場合、ニュートン法では局所最小値ではなく鞍点に収束している可能性があることを考察することができる。

一方でラグランジュの未定乗数法などの鞍点を求めるようなテンプレート:仮リンクではヘッセ行列はが対称であるが正定値ではない行列となることが起こりうる。このとき xk+1 を求める場合は修正コレスキー分解や共役残差法などの手法を用いる必要がある。

準ニュートン法では勾配の変化量に基づいてヘッセ行列（あるいはその逆行列）を近似することで、逆行列を直接求めないで計算効率が向上する。

ヘッセ行列が非可逆に近い場合、その逆行列は数値的に不安定になり解が発散することが起こりうる。このとき、ヘッセ行列に f″(xk)+Bk が正定値となるような行列 Bk を加えることが回避策として挙げられる。具体的にはヘッセ行列を対角化し、固有値の負の要素を ϵ>0 に置き換えることで f″(xk)+Bk​ を正定値行列にすることできる。

レーベンバーグ・マーカート法では近似したヘッセ行列に単位行列をスケーリングした μI を加える。各反復ごとにスケールサイズ μ を調整することで数値的な安定性を担保する。具体的には μ が大きくヘッセ行列が小さい場合でもこの手法はステップサイズ 1/μ の最急降下法のように振る舞う。これによりヘッセ行列が有益な情報をもたない場合でも、収束は遅くなるもののより確実に収束性を保証することができる。

補足事項

最も簡易なニュートン法ではいくつか注意しなければならないことがある:

  1. ヘッセ行列が正則でない場合は適用できない。これはニュートン法の定義から明らかなようにヘッセ行列の逆行列を求める必要があるからである。
  2. 必ずしも収束するとは限らなく、複数の点において巡回することがある。
  3. 極小値でなく、鞍点に収束する場合がある。詳細は幾何学的解釈節を参照

準ニュートン法やレーベンバーグ・マーカート法のような改良型のニュートン法に関しても注意事項がいくつか挙げられる:

具体例として、コスト関数が（強）凸性をもち、ヘッセ行列が大域的有界あるいはリプシッツ連続であるような仮定が必要である（詳細は収束節）。レーベンバーグ・マーカート各々の論文ではレーベンバーグ・マーカート法に関する理論的な分析がレーベンバーグの論文ほとんどされておらず、マーカートの論文においても限定的な状況のみでしか分析をしていないため、大域的収束性は保証されていない。これに対してテンプレート:仮リンクを用いた最急降下法は一般的な仮定の下でも優れた理論的収束性が保証されており、（ディープニューラルネットワークのような）大規模な実用的な問題でも効果的に動作することから比較対象として挙げられる。

脚注

テンプレート:脚注ヘルプ テンプレート:Reflist

参考文献

関連項目

外部リンク

テンプレート:最適化アルゴリズム

  1. ↑ テンプレート:Cite book
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=最適化におけるニュートン法&oldid=13681」から取得