ざっくりML

機械学習に興味ある大学院生によるブログです.

勾配法

「これなら分かる最適化数学」を読み始めたので、最適化についても紹介していこうと思います.

 

これなら分かる最適化数学―基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで

関数の最適化の代表の手法の「勾配法」を軽く説明する.

  1. 勾配法

1変数の場合と多変数の場合があるのでまずは1変数の場合を説明する. そもそも最適化とは、ある制約条件のもとで関数の値を最大(最小)にする変数の値を求めることを言う. 勾配法のアルゴリズムは単純であるが昔からよく使われる手法の一つである. まず初期値 x_0を与える. この初期値の与え方についても多くの研究がされているが今回は割愛. f^{\prime}(x_0) = 0ならそこで最大(最小)値をとる. ある点での勾配が正、つまりf^{\prime}(x_t ) > 0のとき(下図の青)はその点から負の方向に、勾配が負のとき、つまりf^{\prime}(x_0)  < 0のとき(下図の赤)はその点から正の方向に少し進むことで、目的地(最大、最小となる点)に近づいていく. 簡単にまとめたアルゴリズムを以下に示す. f:id:linearml:20170903230043p:plain

  1. xの初期値x^{0}を与える
  2. もしf^{\prime}(x^{0}) = 0のとき、そのときのx_tが最大(最小)値をとる地点である
  3.  x^{t} = x^{t-1} - \alpha f^{\prime}(x^{t-1})に更新する (ただし、\alphaは学習率と呼ばれ1ステップでどれだけ更新するかを表すハイパーパラメータである)
  4. 収束するまで2,3を繰り返す

計算機で実装する上でちょうどf^{\prime}(x)=0となるxを求めるのは現実的ではないので、ある小さい値\epsilonに対して、|f^{\prime}(x)|< \epsilonになる点に到達した時に収束したとみなすことにする. また導関数 \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}を用いて数値微分する. 以下にソースと結果を載せる.

勾配法

f:id:linearml:20170903232812p:plain 初期値はx=5で53回の繰り返しで収束している. またオレンジの線が移動した経緯を示している.

多変数の場合も基本的な流れは同じで各点での導関数を求め少しずつ動かしていけば良い.

勾配法は単純で有効な手法であるが問題点もいくつかある. 一つ目は初期値の与え方によって局所解に陥ってしまうことである. 二つ目は勾配を計算しなければならないが、微分できない関数であったり、できたとしても複雑すぎる場合がある. また変数が数百、数千のときも勾配を求めるのが大変なことである. なので色々な最適化の手法を知ることが必要であり、それぞれの関数に対して適切な手法を選ぶことが求められる.