📂最適化理論

数学における勾配降下法

定義 ¹

スカラー関数 $\varphi : \mathbb{R}^{n} \to \mathbb{R}$ をコスト関数と言う。コスト関数 $\varphi ( \mathbf{x} )$ の極小値を求めるために、$\mathbf{x} = \mathbf{x}_{n}$で$\varphi ( \mathbf{x}_{n+1} ) < \varphi ( \mathbf{x}_{n} )$を満たす$\mathbf{x}_{n+1}$を見つけるアルゴリズムを降下法と言う。

説明

例えば、家を一軒建てることをコスト関数 $\varphi$ の例として考える。家を建てるために必要な資源は木、石、鉄、ガラス、労働費、不動産などがあり、これらは結局「いくらお金がかかるか」という問題に帰結する。この場合、$\varphi$は各資源のベクトルをコストというスカラーにマッピングする関数になる。誰もが気になる質問は「その最小コストはいくらか」ということだろう。一方、機械学習などではコスト関数を損失関数とも呼び、この場合は「実際の値と予測値の差が最小になるのはいつか」となる。

どのような問題であれ、これを数学的に抽象化すれば「スカラー関数の最小値を求める問題」と要約できる。降下法はこの問題を解くために$n$次元マニフォールド上でスカラーが極小値を見つけるメソッドだ。注意すべきは、最小値ではなく極小値であることだ。$\varphi$が凸関数なら話は別だが、一般的な場合では降下法はローカルミニマムを見つけ出せるだけで、それがグローバルミニマムであるという保証はできない。

勾配降下法

降下法の中でも勾配降下法は、コスト関数の勾配を利用して極小値を見つける、最も人気のある方法の一つだ。この方法の実地例を知りたければ、機械学習での勾配降下法を見るといい。

適切な$\alpha>0$に対して、$\mathbf{x}_{n+1} := \mathbf{x}_{n} - \alpha \nabla \varphi ( \mathbf{x}_{n} )$を勾配降下法と言う。

$- \nabla \varphi ( \mathbf{x}_{n} )$はマニフォールドが最も急激に減少する方向を示すので、$\alpha$が適切ならば、$\left\{ \mathbf{x}_{n} \right\}$は極小点へと収束するだろう。

しかし、この方法は簡単で扱いやすい一方で、収束速度に関して他の方法より速いと言い難く、貪欲アルゴリズムである。つまり、各ステップで最善を尽くして局所的には最も大きく減少するが、グローバルに見た場合にはそれほど良い方法ではないかもしれないということだ。

コード

以下はRコードで勾配降下法を実装したもので、勾配を計算するためにnumDerivパッケージを使った。

library(numDeriv)
 
optimizer<-function(f,x0,alpha=0.01){
  while(abs(f(x0))>10^(-8)){
    x0<-x0-alpha*grad(f,x0)
  }
  return(x0)
}
 
z<-function(v){
  return((v[1]-2)^2+(v[2]-3)^2)
}
 
optimizer(z,c(0,0))
z(c(1.999945,2.999918))

上のコードを実行した結果は次の通りである。

この結果は非常に簡単な例で、$z(x,y) = (x-2)^2 + (y-3)^2$の最小値となる点が見つかったことを示している。次の曲面で、$z$が最小になる点は$(2,3)$である。

一緒に見る

• 機械学習での勾配降下法