trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

PRML 5.2.1~5.2.4

5.2.1 パラメータ最適化

課題

誤差関数E(w)を最小にする重みベクトルwを見つける。

結論

方程式\nabla Eの解を見つければよい。 しかし、解析的な解を見つけるのはほぼ無理なため数値的な反復手段により解を見つける。

理由

誤差関数の勾配\nabla Eが0になる点が最小値になる(勾配が0でないなら-\nabla Eの方向に少し動かすと更に誤差関数を小さくできる)。 勾配が0なら最小値というわけではないことに注意。

補足

極小点種類
大域的最小点:誤差関数の最小値に相当する極小点
局所的極小点:大域的最小値以外の極小点 一般的に大域的最小点を見つけたかどうか知ることはできない。

5.2.2 局所二次近似

目的

最適化問題とそれを解くテクニックへの理解を得るため、誤差関数の局所二次近似を考える。

結論

w^{\ast}で評価されたヘッセ行列が正定値ならw^{\ast}は極小点である。

理由

E(w)をある点\hat{w}の周りでテイラー展開すると(5.28)。
3次以上の項は省略、b,Hはそれぞれ(5.29),(5.30)。

極小点w^{\ast}の周りで局所二次近似を考えると(5.32)。
※極小点で勾配0なのでb=\nabla E(w^{\ast})=0

(5.32)をHの固有ベクトルで表現すると $$ E(w)=E(w^{\ast})+\frac{1}{2}(\sum\alpha_{i}u_{i})^{T}H(\sum\alpha_{i}u_{i})\\ =E(w^{\ast})+\frac{1}{2}(\sum\alpha_{i}u_{i})^{T}(\sum\lambda_{i}\alpha_{i}u_{i})\\ =E(w^{\ast})+\frac{1}{2}\sum\lambda_{i}\alpha_{i}^{2} $$ Hが正定値(\sum\lambda_{i}\alpha_{i}^{2}>0)なら、w\ne w^{\ast}のときE(w^{\ast})<E(w)となるためw^{\ast}は極小点となる。

5.2.3 勾配情報の利用

勾配情報の利用により、誤差巻子の極小点を見つけるのに必要な計算量はO(W^{3})からO(W^{2})に向上する。

勾配情報を利用しない場合

O(W^{2})個の点で関数を評価、それぞれの評価にO(W)ステップが必要なため、O(W^{3})ステップとなる。

勾配情報を利用する場合

O(W)回の評価、それぞれの評価にO(W)ステップが必要なため、O(W^{2})ステップとなる。

5.2.4 勾配降下最適化

勾配情報を用いたアプローチの紹介。

勾配降下法あるいは最急降下法

(5.41)。直感的には合理的だが、実際には性能が悪い。

共役勾配法準ニュートン法

単純な勾配降下法よりも頑強でかつ早い。また、極小点に到達しない限り、反復ごとに常に誤差関数が減少する。

オンライン勾配降下法あるいは逐次的勾配降下法、確率的勾配降下法

誤差関数は各データ点を表す項の和からなる(5.42)。
重みベクトルの更新を1回ごとに1つのデータ点に基づいて作成する(5.43)。

オンライン手法の利点

データの冗長度を効率的扱うことができる。
局所的極小値を回避できる可能性がある。