最急降下法のソースを表示

{{about|最適化アルゴリズム|解析的（漸近）近似|{{仮リンク|最急降下法 (漸近解析)|en|Method of steepest descent}}あるいは{{仮リンク|鞍点法|en|Stationary phase approximation}}}}
{{redirect|勾配降下法|'''確率的'''勾配降下法|確率的勾配降下法}}
'''最急降下法'''（さいきゅうこうかほう、{{lang-en-short|gradient descent, steepest descent}}）<ref name="opt_math">{{cite book|和書
|first=俊秀|last=茨木
|authorlink=茨木俊秀
|title=最適化の数学
|series=共立講座 21世紀の数学 13
|publisher=共立出版
|date=2011-06-23
|isbn=978-4320015654
|ref=harv}}</ref>は、[[関数 (数学)|関数]]（ポテンシャル面）の[[傾き (数学)|傾き]]（一階[[微分]]）のみから、関数の[[最小値]]を探索する連続[[最適化問題]]の[[勾配法]]の[[アルゴリズム]]の一つ。勾配法としては最も単純であり、直接・間接にこのアルゴリズムを使用している場合は多い。最急降下法をオンライン学習に改良した物を[[確率的勾配降下法]]と呼ぶ。

尚、最急降下法の“最急”とは、最も急な方向に降下することを意味している。すなわち、[[収束]]の速さに関して言及しているわけではない（より速いアルゴリズムがあり得る）。

==手法==
{{mvar|n}} 次の[[数ベクトル空間|ベクトル]] {{math|'''''x''''' {{=}} (''x''<sub>1</sub>, ''x''<sub>2</sub>, ... , ''x''<sub>''n''</sub>)}} を[[独立変数|引数]]とする[[関数 (数学)|関数]]を {{math|''f''&thinsp;('''''x''''')}} としてこの関数の[[極小値]]を求めることを考える。

勾配法では[[反復法 (数値計算)|反復法]]を用いて {{mvar|'''x'''}} を解に近づけていく。{{mvar|k}} 回目の反復で解が {{math|'''''x'''''<sup>(''k'')</sup>}} の位置にあるとき、最急降下法では次のようにして値を更新する<ref name="opt_math"/>。

{{numBlk|:|
<math>\begin{align}
\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \alpha \operatorname{grad} f(\boldsymbol{x}^{(k)})
                       = \boldsymbol{x}^{(k)} 
                       - \alpha\begin{bmatrix}
                           \partial f(\boldsymbol{x}^{(k)}) / \partial x^{(k)}_1 \\
                           \partial f(\boldsymbol{x}^{(k)}) / \partial x^{(k)}_2 \\ 
                           \vdots \\ 
                           \partial f(\boldsymbol{x}^{(k)}) / \partial x^{(k)}_n
                         \end{bmatrix}
\end{align}</math>
|{{equationRef|SteepestDescent|最急降下法}}}}

ここで {{mvar|&alpha;}} は 1 回に更新する数値の[[重み]]を決めるパラメータであり、通常は小さな正の定数である。パラメータ {{mvar|&alpha;}} の適正な範囲は多くの場合、取り扱う問題の性質によって決まる。例えば力学問題を計算する際、計算結果が発散するような設定を与えることは、何らかの意味で非物理的な仮定をしている（あるいは元々のモデルの適用範囲を超えている）ことを示している。

例えば、{{math|''y'' {{=}} ''x''<sup>2</sup>}} の最小値の探索において、{{math|''&alpha;'' &gt; 1}} の場合、反復ごとに悪い解へと向かう。解の探索能力、収束速度は {{mvar|&alpha;}} に強く依存しており、{{mvar|&alpha;}} が大きすぎると発散の恐れがあり、小さすぎると収束が遅くなる（{{仮リンク|緩和法 (数学)|en|Relaxation (iterative method)|label=緩和法}}<!--あるいは[[過緩和]]、[[不足緩和]]-->も参照）。そのため、探索の初期では大きめにし、ある程度収束したら小さくする方法もとられる。小さくするやり方は反復回数の[[逆数]]や[[指数関数的減衰]]などがあり、[[焼きなまし法]]が参考になる。

[[勾配 (ベクトル解析)|勾配]]ベクトル {{math|grad ''f''&thinsp;('''''x''''')}} は関数 {{mvar|f}} の変化率が最も大きい方向を向く。したがって {{mvar|&alpha;}} が適切な値を持つなら、{{math|''f''&thinsp;('''''x'''''<sup>(''k'' + 1)</sup>)}} は必ず {{math|''f''&thinsp;('''''x'''''<sup>(''k'')</sup>)}} より小さくなる。

最急降下法のスキームは以下のようになる<ref name="opt_math"/>：
# {{mvar|'''x'''}} の[[初期値]] {{math|'''''x'''''<sup>(0)</sup>}} を決める（必要であれば、反復回数を記憶する変数を {{math|''k'' {{=}} 0}} と初期化しておく。実際には {{mvar|'''x'''}} を記憶する領域は 1 つで充分なので、単純に最急降下法のみを行う場合には必要ない）。
# {{math|{{sfrac|&part;''f''&thinsp;('''''x'''''<sup>(''k'')</sup>)|&part;''x''<sub>''i''</sub><sup>(''k'')</sup>}} {{=}} 0  (''i'' {{=}} 1, ... , ''n'')}} であるなら終了する（実際は正確に 0 になることはないので、十分小さな値になれば終了する）。
# 上記の記述に従って {{math|'''''x'''''<sup>(''k'')</sup>}} を更新する。
# 2 に戻る（必要なら {{mvar|''k''}} の値を 1 つ進める）。


== 特徴 ==
* 傾き（一階微分）のみしか見ないので手法として簡便で計算も速い。
* 勾配法のため、[[極値|局所的な最小値]]に捉まり易く、大域的な[[最小値]]を求めるのは困難であることが欠点である。それを回避するために、複数の初期値から探索を行うなどの対策が必要である。対策としては[[確率的勾配降下法]]も参照。
* 関数 {{mvar|f}} の偏微分が計算できなくてはならない。

==出典==
{{reflist}}

== 関連項目 ==
*[[最適化問題]]
*[[確率的勾配降下法]]
*[[共役勾配法]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:さいきゆうこうかほう}}
[[Category:勾配法]]
[[Category:数学に関する記事]]