読者です 読者をやめる 読者になる 読者になる

廿TT

譬如水怙牛過窓櫺 頭角四蹄都過了 因甚麼尾巴過不得

R による最急降下法の練習

モチベーション

最尤法とか最小二乗法とかのとき、いまぼくは R の optim 関数をブラックボックス的に使っていて変なとこに収束しちゃうことがよくある。

なので最適化について基本的なことを勉強しなおしたい。

追記

「例題」のところにあやまった記述があったので本文を一部削除、修正しました。
コメント欄参照。

例題

 \displaystyle f(x) = \frac{1}{2}x^2 + \exp(x)

この関数(目的関数)を最小化する x を求めたい。

高校で習った数学による知識だと微分して導関数 0 になるところが極値だった。

 \displaystyle f'(x) = x + \exp(x)

f'(x)=0 と置いて解こうと思ったけど解けない。

しかたないので数値解法(numerical method)を使う。

数値解法の中でもっとも単純(と思われる)のが、最急降下法(gradient descent method)というやつだ。

最急降下法 - Wikipedia

\displaystyle x^{\rm new} = x^{\rm old} - e f'(x^{\rm old})

なる更新式が使われる。ここで e学習率(learnig rate)などと呼ばれる定数だ。
(この定数がどのように効いてくるかは不勉強なので知らない。)

第二項目が降下方向。

最急降下法を使って解を求めてみる。

objfun <- function(x){
  (x^2)/2+exp(x)
}

dfn <- function(x){
  x+exp(x)
}

x_old =1 #初期値
e=1 #学習率
for(i in 1:100){
  x_new <- x_old - e*dfn(x_old)
  if(abs(x_old -x_new) < 1e-6)break;
  x_old <- x_new
}

結果、28回のイテレーションで収束し、x=-0.5671437 が解らしい。

> i
[1] 28
> x_old
[1] -0.5671437

プロットしてみる。

curve(objfun(x), xlim=c(-1,1),lwd=2)
points(x_old,objfun(x_old),pch=4,cex=2,lwd=2,col="blue2")


f:id:abrahamcow:20150325152104p:plain

> objfun(x_old)
[1] 0.727969

この例題では目的関数が1変数なので、uniroot 関数を使えば最急降下法と同じ結果が得られる。

> uniroot(dfn,c(-1,1))
$root
[1] -0.5671256

$f.root
[1] 2.764964e-05

$iter
[1] 4

$init.it
[1] NA

$estim.prec
[1] 6.103516e-05

ノート

  • なぜ最急降下法がうまくいったのか?
    • 目的関数が凸だから。
  • optimize って関数使ったらだめなの?
    • そんなことないです。コメント欄参照。誤った記述をして申し訳ありません。ご指摘ありがとうございます。

参考にした本

言語処理のための機械学習入門 (自然言語処理シリーズ)

言語処理のための機械学習入門 (自然言語処理シリーズ)

関連エントリ

abrahamcow.hatenablog.com