最急降下法
![]() | この項目では、最適化アルゴリズムについて説明しています。解析的(漸近)近似については「最急降下法 (漸近解析)(英語版)あるいは鞍点法(英語版)」をご覧ください。 |
![]() | 「勾配降下法」はこの項目へ転送されています。確率的勾配降下法については「確率的勾配降下法」をご覧ください。 |
最急降下法(さいきゅうこうかほう、英: gradient descent, steepest descent)[1]は、関数(ポテンシャル面)の傾き(一階微分)のみから、関数の最小値を探索する連続最適化問題の勾配法のアルゴリズムの一つ。勾配法としては最も単純であり、直接・間接にこのアルゴリズムを使用している場合は多い。最急降下法をオンライン学習に改良した物を確率的勾配降下法と呼ぶ。
尚、最急降下法の“最急”とは、最も急な方向に降下することを意味している。すなわち、収束の速さに関して言及しているわけではない(より速いアルゴリズムがあり得る)。
手法
n 次のベクトル x = (x1, x2, ... , xn) を引数とする関数を f (x) としてこの関数の極小値を求めることを考える。
勾配法では反復法を用いて x を解に近づけていく。k 回目の反復で解が x(k) の位置にあるとき、最急降下法では次のようにして値を更新する[1]。
ここで α は 1 回に更新する数値の重みを決めるパラメータであり、通常は小さな正の定数である。パラメータ α の適正な範囲は多くの場合、取り扱う問題の性質によって決まる。例えば力学問題を計算する際、計算結果が発散するような設定を与えることは、何らかの意味で非物理的な仮定をしている(あるいは元々のモデルの適用範囲を超えている)ことを示している。
例えば、y = x2 の最小値の探索において、α > 1 の場合、反復ごとに悪い解へと向かう。解の探索能力、収束速度は α に強く依存しており、α が大きすぎると発散の恐れがあり、小さすぎると収束が遅くなる(緩和法(英語版)も参照)。そのため、探索の初期では大きめにし、ある程度収束したら小さくする方法もとられる。小さくするやり方は反復回数の逆数や指数関数的減衰などがあり、焼きなまし法が参考になる。
勾配ベクトル grad f (x) は関数 f の変化率が最も大きい方向を向く。したがって α が適切な値を持つなら、f (x(k + 1)) は必ず f (x(k)) より小さくなる。
最急降下法のスキームは以下のようになる[1]:
- x の初期値 x(0) を決める(必要であれば、反復回数を記憶する変数を k = 0 と初期化しておく。実際には x を記憶する領域は 1 つで充分なので、単純に最急降下法のみを行う場合には必要ない)。
- ∂f (x(k))/∂xi(k) = 0 (i = 1, ... , n) であるなら終了する(実際は正確に 0 になることはないので、十分小さな値になれば終了する)。
- 上記の記述に従って x(k) を更新する。
- 2 に戻る(必要なら k の値を 1 つ進める)。
特徴
- 傾き(一階微分)のみしか見ないので手法として簡便で計算も速い。
- 勾配法のため、局所的な最小値に捉まり易く、大域的な最小値を求めるのは困難であることが欠点である。それを回避するために、複数の初期値から探索を行うなどの対策が必要である。対策としては確率的勾配降下法も参照。
- 関数 f の偏微分が計算できなくてはならない。
出典
関連項目
| ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
非線形(無制約) |
| ![]() | ||||||||||||
非線形(制約付き) |
| |||||||||||||
凸最適化 |
| |||||||||||||
組合せ最適化 |
| |||||||||||||
メタヒューリスティクス | ||||||||||||||
|