数式が表示されるようになったと聞いて (http://qiita.com/iizukak/items/04d6e226982bc108bc16)

この前会社の人と多項式フィッティングを実装してみようってことで書いた数式を（紙はあげちゃったのでうろ覚えで）備忘録として再度。

正則化項つきエラー関数

\tilde{E}(\mathbf{w}) = 
\frac{1}{2}\sum_{n}
  \left\{
    y(\mathbf{x_n};\mathbf{w}) - t_n 
  \right\}
+ \frac{\lambda}{2} \left| \mathbf{w} \right|^2

を最小化する $\mathbf{w}$ を求めたい。ただし、

y(\mathbf{x};\mathbf{w}) = \sum_j w_j x^j

である。

まずエラー関数を $w_j$ で微分すると、

\begin{aligned}
\frac{\partial\tilde{E}}{\partial w_j}
& = 
\sum_{n}
  \left(
    \left\{ y(\mathbf{x_n};\mathbf{w}) - t_n \right\}
    \frac{\partial y(\mathbf{x_n};\mathbf{w})}{\partial w_j}
  \right)
+ \lambda w_j
\\
&=
\sum_{n}
  \left(
    \left\{ y(\mathbf{x_n};\mathbf{w}) - t_n \right\}
    x_n^j
  \right)
+ \lambda w_j
\end{aligned}

となる。

これを元にGradient Descentのループ

\begin{aligned}
w_j 
&:= 
w_j - \alpha \frac{\partial\tilde{E}}{\partial w_j}
\\
&=
w_j - \alpha \left[
\sum_{n}
  \left(
    \left\{ y(\mathbf{x_n};\mathbf{w}) - t_n \right\}
    x_n^j
  \right)
+ \lambda w_j
\right]
\\
&=
\left( 1 - \alpha \lambda \right) w_j - \alpha
\sum_{n}
  \left(
    \left\{ y(\mathbf{x_n};\mathbf{w}) - t_n \right\}
    x_n^j
  \right)
\end{aligned}

をまわす。

これをJavaScriptで実装したものが http://jsfiddle.net/s4rC2/10/ である。

会社でやっていた時にはきちんと動いていなかったのだが、帰ってきて試行錯誤していたら、アルゴリズム的には問題なくて、以下のポイントを抑えてあげればきちんと動いた。

まず先ほどの一番下の右辺を見ると、 $ ( 1 - \alpha \lambda ) w_j$ というのがあるが、これは $w_j$ をちょっとだけ小さくする働きをすることが期待される。$\lambda$ が正則化項由来であることを考えると、 $\mathbf{w}$ が大きくなり過ぎるのを抑制する働きということで納得がいく。

つまり、

\alpha \lambda \ll 1

が成り立つように $\alpha$ と $\lambda$ を選ぶ必要がある。

次に、その次の項に着目すると、 $y(\mathbf{x_n};\mathbf{w}) - t_n$ は（この差を縮めるのが今回の目的であることを考えると）それほど大きくならないはずだが、$x_n^j$ が厄介である。

もし観測点の$x$座標が1よりも大きい値（例えば10とか）であれば、$j$ が大きいほど（多項式フィッティングに使う多項式の次数が大きいほど）$x_n^j$が巨大になってしまうため、$w_j$ が発散してしまう。

そのため、

\alpha x_n^j \ll 1

となるように $\alpha$ を選ぶか、それだと収束が極端に遅くなってしまうので、現実的には観測点の $x$ 座標が1以下になるようにデータを正規化することが重要である。