オセロ3

そろそろまともな評価関数を作成しようと考えてリバーシの評価関数の最適化を読んで最急降下法の実装をしたけど,どこか実装がバグってるのか解が発散して困っていた.
最急降下法の練習にともうちょっと簡単な問題を設定してそれを解いてみようと考えて解いてみた.

問題

区間 [0, 2 \pi]を等分するM個の点 x_1, x_2, ..., x_M を取り,関数 \displaystyle f(\vec{w}) = \sum_{i=0}^{M} {(\sin(x_i) - \sum_{j=1}^{N} w_j {x_i}^j)}^2を最小化するベクトル \vec{w}を求める.
つまり,sinと多項式の和との差の二乗を最小にする係数を求めることになる.

最急降下法

pdfの式変形に従うと, \displaystyle  r_i = \sin(x_i) -\sum_{j=1}^{N} w_j {x_i}^jとすると  \displaystyle  \frac{\partial f}{\partial w_j} = -2 \sum_{i=1}^{M} r_i {x_i}^jになって,更新の式は \displaystyle w_j^{(k+1)} = w_j^{(k)} + 2 \alpha \sum_{i=1}^{M} r_i {x_i}^jになる.
実際に実装して,取る点の数と多項式の次数を調整してどの程度近似出来るかデータを取ってみた. f:id:odan3240:20160421115240p:plain
縦軸が誤差の値,横軸が次数,各グラフは点を何個取ったか.表示されていないのは結果がNaNになった部分.
次数が8辺りで誤差が改善されなくなっているのと,点の数(学習に使うデータの数)が増えるとNaNに発散しているのがわかる.
オセロの評価関数のために書いた最急降下法の解が発散したのは学習データを用意しすぎたのが原因なのかな.

実装したコード
github.com

追記

学習率 \alphaをデータの個数で割って正規化してやらないとダメで,その処理が抜けてました. f:id:odan3240:20160422094440p:plain