これだけは知っておきたい最適化アルゴリズムの基礎

本記事では、最適化アルゴリズムの基礎を最急降下法(steepest descent)を用いて紹介します。

機械学習をメインにされている人も、確率的降下勾配法(Stochastic Gradient Descent; SGD)の基礎になるテーマなので知っておいて損はありません。

 

今回は、以下の無制約最小化問題を考えます。

{min:f(x)}

まず、この問題に対する解の定義を与えます。

  • 大域的最適解(global minimizer)

{x^*\in R^n}が任意の{x\in R^n}に対して、{f(x^*)\leq f(x)}が成り立つとき、{x^*}を大域的最適解という。

  • 局所的最適解(local minimizer)

{x^*\in R^n}の適当な近傍を{N(x^*)}とする。このとき、任意の点{x \in N(x^*)}に対して、{f(x^*)\leq f(x)}が成り立つとき、{x^*}を局所的最適解という。

簡単に言えば、大域的最適解は一番小さい点、局所的最適解はまわりと比較して一番小さい点となります。

 

準備が出来たので、ここから反復法の説明を行います。

反復法では、適当な初期点{x^0 \in R^n}からスタートして点を以下のように更新します。
{x^{k+1} = x^{k} + \alpha^k d^k}

ここで{d^k \in R^n}は、探索方向と呼ばれ、この方向に進むことで{k}回目の反復点より、{k+1}回目の反復点の方が解に近づくようになります。{\alpha^k}スカラーで探索方向にどれぐらい進むかを制御します。

この更新を繰り返すことで、{x^k}が最適解{x^*}に十分近づいたとき、アルゴリズムを終了します。(イメージとしては、十分小さい{\epsilon}に対して{| x^k - x^* | \leq \epsilon}を満たしたとき。真の解がわからないから反復法を使っているのにどうやって判定するんだ、という鋭いツッコミは別記事で...)

これが反復法の基礎となります。連続最適化における様々なアルゴリズムは、この探索方向{d^k}の求め方が異なります。

 

さて、探索方向{d^k}の決定方法ですが、これは関数が減少する方向となることが期待されます。すなわち、

{f(x^{k+1}) - f(x^{k}) =f(x^{k} +\alpha ^k d^k) - f(x^{k})}

が負となるような{d^k}を求めたい、ということに他なりません。

ここで関数{f}微分可能なとき、

{lim_{t\rightarrow +0} \displaystyle \frac{f(x^{k} +t d^k) - f(x^{k})}{t} = \nabla f(x^k)^T d^k}

より、この右辺が負となれば良いことがわかります。(イメージしづらい方は、{f(x^{k} +\alpha ^k d^k))}テイラー展開して、一次の項までで打ち切ってみてください)
この右辺を、方向微係数と呼び、反復法ではこれが負となるような{d^k}を選びます。

 

さて、ここから最急降下法の紹介に入ります。

上述より、方向微係数は次のようにあらわされます。

{\nabla f(x^k)^T d^k = \|\nabla f(x^k) \| \| d^k \| cos \gamma}

ただし、 {\gamma}{f(x^k)}{d^k}のなす角です。この式より、方向微係数を最小にするのは {\gamma = \pi}のときであり、探索方向は

{d^k = -\nabla f(x^k)}

として、求められます。

以上より、アルゴリズムは現在の反復点{x^k}が、解に十分近づくまで以下の更新を行います。

{x^{k+1} = x^k + \alpha^k (-\nabla f(x^k)) =x^k - \alpha^k \nabla f(x^k)}

このように、方向微係数を最小とする方向を用いて、解を探索するために最急降下法と呼ばれます。

 

では、探索方向を常に方向微係数を最小にする {d^k = -\nabla f(x^k)}とすれば良いのでしょうか。実際には、これでは上手くいかない場合(振動など)があります。また、式を見てわかる通り、今回は一回微分までの情報しか使っていませんが、二回微分の情報を用いるアルゴリズム(ニュートン法)もあります。

 

さらに、ステップ幅{\alpha^k}も適当に取れば良いということではなく、解にたどり着くための条件が存在します。収束性(アルゴリズムが解に本当に収束するのか)や収束率 (どれぐらいの速さで解に収束するのか)などを解析するときに、重要となってきます。

 

今回は、最適化アルゴリズムの基礎を最急降下法を用いて紹介してきました。

これらは、機械学習でよく用いられる最適化手法の理解の助けになると思います。解を求めるときに、このようなアルゴリズムが基礎になっていることを想像していただければ幸いです。

 

不定期更新ですがよろしくお願いします。
何かあればコメントやツイッター(@hiyoko9t)でお気軽にお声がけください。