nAG最適化コーナー: DFO（Derivative Free Optimization）

この記事はnAG最適化コーナー シリーズの一部です。

前回の記事では、導関数を提供する方法を検討し、有限差分（FD）近似に焦点を当てました。 今回は、微分を必要とせず、また有限差分を使って内部で近似する必要もないアルゴリズムについても詳しく説明します。このクラスの最適化アルゴリズムは、通常、DFO（Derivative-Free-Optimization）と呼ばれます。

以下を前提とします。
$$\begin{equation*} \min_{x\in R^n}{f(x)} \end{equation*}$$
ここで $f$ は非線形で滑らかな目的関数であり、以下であっても良いものとします。

• 導関数が未知でブラックボックス
• 導関数の評価に時間がかかる
• 潜在的にノイズが含まれている

このような問題には、DFO（Derivative Free Optimization）ソルバーを用いるのが最善です。 （ここで強調しておく点として、導関数が利用可能で且つ計算が容易の場合は常に導関数に基づく方法を優先的に用いるべきです。）

DFO（Derivative Free Optimization）アプローチの比較

DFO（Derivative Free Optimization）アルゴリズムには主に3つのファミリがあります。

• 確率的（グローバル）な方法（遺伝的アルゴリズム、ベイジアン最適化、...）
• 直接検索を行う方法（Nelder-Mead、Pattern-Search、...）
• モデルを基にする方法

確率的方法は、目的関数のいかなる性質（連続性さえも）を仮定せず、ランダムな関数評価によって可変空間を探索します。関数評価は、これまでのベストな点（局所の可能性あり）に重み付けしたヒューリスティックスによりグローバルな探索を行います。それにより局所解にトラップされないので、大域的解の近似を行います。しかしながらこれを行うためには、通常、多くの目的関数評価を行う必要があるため、負荷の高い関数には適していません。

直接検索を行う方法（非常に普及しているNelder-Meadシンプレックスアルゴリズムを含む）は、与えられた出発点からのヒューリスティックに基づいて空間を系統的に探索します。実装が容易であるため人気がありますが、一般的に局所解に向かってゆっくりと収束します。多くの場合において、直接探索を行う方法よりもモデルを基にする方法が大幅に優れています。

これを示すため Rosenbrockのバナナ関数 の最適化を行う例を取り上げます。 $$\begin{equation*} f(x,y) = (1-x)^2 + 100(y-x^2)^2 \end{equation*}$$

今回利用するのはnAG数値計算ライブラリをMATLAB®から使うためのツールボックス「nAG Toolbox for MATLAB®」で提供される以下の４種のDFO関数です:

• 有限差分を用いる準ニュートンアルゴリズム (e04jy)
• 粒子群最適化（PSO）アルゴリズム (e05sa) - 確率的方法の例として
• Nelder-Meadシンプレックス・アルゴリズム (e04cb)
• モデルを基にするアルゴリズム(e04jc)

先に述べたように、DFOソルバーは（一般的に収束の確認や解の比較に用いる）導関数を近似しません。 DFOソルバの進捗状況を定量化するための一つの方法として、関数値が$\varepsilon$の範囲内の点に到達するのに必要な関数評価回数を観測することがあります。 今回のケースでは最適な目的値は $0.0$ $$x=y=1.0$ の点$ です。

以下の表は、各ソルバーとそれぞれのしきい値$\varepsilon$について必要とされた関数評価の回数をまとめたものです。

PSOを除くすべてのソルバーの出発点は $[-2,2]$ としました。PSOはその代わりに範囲境界 $-2\leq x,y \leq 2$ を与えました。（またPSOについてはそれぞれ５回実行し、その平均を結果としています。）

$\varepsilon$	$10^{-3}$	$10^{-5}$	$10^{-7}$	$10^{-9}$	$10^{-11}$
PSO, e05sa	947	3316	$\infty$	$\infty$	$\infty$
Quasi-Newton, e04jy	154	152	156	159	172
Nelder-Mead, e04cb	203	221	233	245	263
Model-based, e04jc	135	148	156	160	163

PSOでは多くの関数評価が必要で、このような確率論的手法が高精度解を得るためには良い選択ではない事が観察できます。 また、一般的に導関数を基にするソルバーは解に向かって急速な収束を示す傾向がありますが、ここでも有限差分近似を有する準ニュートン法はこのような挙動を示し、数回の追加評価でより高い精度に容易に達している事が観察できます。更に、モデルを基にするアルゴリズムはNelder-Meadシンプレックス法より優れており、また準ニュートンよりも関数評価の回数もわずかに勝っています。

以下のテストでは、DFO法は（非常に低レベルのノイズであっても）ノイズを含む問題に対して、有限差分に依存する方法より、はるかに堅牢であることが示されます。

モデルを基にするDFOアルゴリズム

nAG数値計算ライブラリにはモデルを基にする2つのDFOソルバーがあります：

• e04jc: 一般的な制約付き非線形問題
• e04ff: 最小二乗較正問題に特化

これらのソルバーは、一連の補間点に一致する目的関数 $f$ の値を用いる事と、モデルが正確であるとみなされる信頼領域の監視を行う事で、収束が保証されるようにします。 このようなアルゴリズムは以下のようにまとめることができます。

1. 初期化
   • 最初の反復とその周囲の最初の信ｊ頼領域を選択する
   • 信頼領域内の一連の補間点を選択する
   • 信頼領域内に2次補間モデルを構築する
2. 収束するまで繰り返す
   • 信頼領域内でモデルを最小化する
   • 新たな点において目的関数を評価する
   • モデルが目的関数値の減少を正しく予測した場合:
     • 離れた補間点を新しい点で置き換える
     • 新たな点の周りの信頼領域を移動する
   • そうでない場合:
     • ジオメトリが良好でない場合は補間点をいくつか置き換える
     • もしくは信頼領域を縮小する

以下のアニメーションは２回の反復を示します。

この種の方法は導関数の有限差分を利用する方法と比較し主に2つの利点があります。 第1にこの種の方法では関数の評価が現在の反復から遠く離れている場合にのみ破棄され、それ以外の場合は引き続き何度も利用されます。しかしながら有限差分フレームワークでは勾配の推定値は利用されるとすぐに破棄されます。 第2にこの種の方法は信頼領域内に良く散在した点を持つので、関数評価にエラーが発生した場合の問題を緩和てきます。

ノイズの多い関数の実験

現実の問題では、関数の評価が不正確な場合がしばしばあります。 例えば、完全精度で計算されない負荷の高いシミュレーションや、確率モデルに基づく問題には小さな誤差が生じます。 このような関数はノイズが多い関数と言われます。

前回の記事では、$f$ の評価の誤差が大きくなるにつれて、有限差分近似の精度が非常に急速に失われることが示されました。（通常、$f$ の精度はマシン精度 $\varepsilon$ までと仮定しています） ノイズが多い関数に適用される有限差分近似は通常全く機能しません。

対照的にモデルを基にするDFOはより柔軟で、関数評価の範囲に広がりがあるため、各点での小さな不完全性は、それぞれの距離によって良好に緩和されます。

この振る舞いをCUTEst test setにある以下の4つの関数を用いて示します。

• Rosenbrock
• Genhumps
• Arwhead
• Dqdrtic

ここではこれらの関数について以下の問題を解きます。
$$\begin{equation*} \min_{x\in R^n}{\tilde f(x)} \end{equation*}$$ ここで $\tilde f(x) = f(x) + \epsilon$ であり $\epsilon$ は正規分布 $N(0,\sigma^2)$ に基づくノイズを表します。

テスト問題は（ここでも）e04jy - 有限差分を用いる準ニュートン法、及び e04jc - モデルを基にする DFO ソルバーを利用します。 次の表では、ソルバーが実際のソリューションの $10^3 \cdot \sigma$ の範囲内に到達するために必要な関数評価の回数をさまざまなレベルのノイズ $\sigma$ に対して示しています（5回の実行後の平均）。$\infty$は、ソルバーが希望の精度に到達できなかったことを示します。

Noise level		$\sigma=10^{-10}$	$\sigma=10^{-9}$	$\sigma=10^{-8}$	$\sigma=10^{-7}$	$\sigma=10^{-6}$
Rosenbrock	e04jc	373	382	402	345	321
	e04jy	388	$\infty$	$\infty$	$\infty$	$\infty$
Genhumps	e04jc	310	302	286	242	282
	e04jy	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
Arwhead	e04jc	80	83	72	63	64
	e04jy	221	1088	$\infty$	$\infty$	$\infty$
Dqdrtic	e04jc	17	17	17	17	17
	e04jy	26	54	1153	$\infty$	$\infty$

覚えておくと役立つ事

導関数が容易に利用できない問題については、DFO（Derivative Free Optimization）が有限差分近似の代替案となる可能性があります。 特に、e04jc のようなモデルベースのDFOアルゴリズムは、この分野の最先端技術を表しています。 また、有限差分を用いる方法はノイズに非常に敏感であり、非常に少量のノイズでも簡単に機能しなくなるため避けるべきです。従ってこのような問題については一般的にDFOソルバーの利用が望ましいと言えます。

 

---