曲線フィッティング - 最小二乗法 - 機械学習基礎理論独習

要件

$N$ 個のデータ $(x_1,t_1),\cdots,(x_N,t_N)$ に当てはまる曲線を求めたい。

モデルの定義

予測曲線(モデル)を $y=w_0+w_1x+w_2x^2+\cdots+w_Dx^D$ とします。

目的関数の定義

あるデータ $(x_n,t_n)$ に着目する。
$x_n$ の予測値は $w_0+w_1x_n+w_2x_n^2+\cdots+w_Dx_n^D$ です。
$t_n$ との差の2乗は $(w_0+w_1x_n+w_2x_n^2+\cdots+w_Dx_n^D-t_n)^2$ です。
これを全データについて足し合わせたものを目的関数とします。

$\begin{eqnarray} E(w_0,\cdots,w_{D-1})=\frac{1}{2}\sum_{n=1}^N(w_0+w_1x_n+w_2x_n^2+\cdots+w_Dx_n^D-t_n)^2\tag{1} \end{eqnarray}$

$\frac{1}{2}$ は $w_0,\cdots,w_D$ で偏微分した式を奇麗に見せるためのものです。

モデルと目的関数を簡潔に表す

$\begin{eqnarray} &&{\bf w}=(w_0, w_1, w_2, \cdots, w_D)^\top\tag{2}\\ &&\phi_i(x)=x^i\tag{3}\\ &&\phi_0(x)=1\tag{4}\\ &&{\boldsymbol\phi}(x)=(\phi_0(x), \phi_1(x), \phi_2(x), \cdots, \phi_D(x))^\top\tag{5}\\ \end{eqnarray}$

とおくと、モデルは $y={\bf w}^\top\boldsymbol\phi(x)$ と表せます。

また、目的関数は $E({\bf w})=\frac{1}{2}\sum_{n=1}^N({\bf w}^\top\boldsymbol\phi(x_n)-t_n)^2$ と書けます。

さらに、

$\begin{eqnarray} {\boldsymbol\Phi}=\begin{pmatrix} \boldsymbol\phi(x_1)^\top \\\ \vdots \\\ \boldsymbol\phi(x_N)^\top\ \end{pmatrix},{\bf t}=(t_1,\cdots,t_N)^\top\tag{6} \end{eqnarray}$

とおくと
目的関数は $E({\bf w})=\frac{1}{2}||\boldsymbol\Phi{\bf w}-{\bf t}||^2$ と書けます。

目的関数の最小化

目的関数を最小化するために ${\bf w}$ で偏微分し、 $={\bf 0}$ とし、
これについて解くと ${\bf w}$ が定まり、予測曲線が決定します。
誤差の二乗和からなる目的関数を最小化するので、これを最小二乗法と言います。

以下、導出です。

$\begin{eqnarray} &&\nabla E({\bf w})={\bf 0}\\ &&\frac{\partial}{\partial {\bf w}}E({\bf w})={\bf 0}\\ &&\Leftrightarrow\frac{\partial}{\partial {\bf w}}\frac{1}{2}||\boldsymbol\Phi{\bf w}-{\bf t}||^2={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}\frac{\partial}{\partial {\bf w}}(\boldsymbol\Phi{\bf w}-{\bf t})^\top(\boldsymbol\Phi{\bf w}-{\bf t})={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}\frac{\partial}{\partial {\bf w}}({\bf w}^\top\boldsymbol\Phi^\top-{\bf t}^\top)(\boldsymbol\Phi{\bf w}-{\bf t})={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}\frac{\partial}{\partial {\bf w}}({\bf w}^\top\boldsymbol\Phi^\top\boldsymbol\Phi{\bf w}-{\bf w}^\top\boldsymbol\Phi^\top{\bf t}-{\bf t}^\top\boldsymbol\Phi{\bf w}+{\bf t}^\top{\bf t})={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}\frac{\partial}{\partial {\bf w}}({\bf w}^\top\boldsymbol\Phi^\top\boldsymbol\Phi{\bf w}-2{\bf w}^\top\boldsymbol\Phi^\top{\bf t}+||{\bf t}||^2)={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}(2\boldsymbol\Phi^\top\boldsymbol\Phi{\bf w}-2\boldsymbol\Phi^\top{\bf t})={\bf 0}\\ &&\Leftrightarrow \boldsymbol\Phi^\top\boldsymbol\Phi{\bf w}=\boldsymbol\Phi^\top{\bf t}\\ &&\Leftrightarrow {\bf w}=(\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}\boldsymbol\Phi^\top{\bf t}\tag{7}\\ \end{eqnarray}$

$\boldsymbol\Phi^\top\boldsymbol\Phi$ は正則であるとします。

目的関数は凸関数である

目的関数が凸関数であること示すには、目的関数のヘッセ行列が半正定値行列であることを示せばよいです。
以下、証明です。

まず、目的関数のヘッセ行列を求めます。

$\begin{eqnarray} \nabla\nabla E({\bf w})&=&\frac{\partial}{\partial {\bf w}}\left(\frac{\partial}{\partial {\bf w}^\top}E({\bf w})\right)\\ &=&\frac{\partial}{\partial {\bf w}}\left(\frac{\partial}{\partial {\bf w}}E({\bf w})\right)^\top\\ &=&\frac{\partial}{\partial {\bf w}}\left(\boldsymbol\Phi^\top\boldsymbol\Phi{\bf w}-\boldsymbol\Phi^\top{\bf t}\right)^\top\\ &=&\frac{\partial}{\partial {\bf w}}({\bf w}^\top\boldsymbol\Phi^\top\boldsymbol\Phi-{\bf t}^\top\boldsymbol\Phi)\\ &=&(\boldsymbol\Phi^\top\boldsymbol\Phi)^\top\\ &=&\boldsymbol\Phi^\top\boldsymbol\Phi\tag{8}\\ \end{eqnarray}$

次に、ヘッセ行列が半正定値行列であることを示します。
${\bf x}\in\mathbb{R}^D$ とします。

$\begin{eqnarray} {\bf x}^\top\boldsymbol\Phi^\top\boldsymbol\Phi{\bf x}&=&(\boldsymbol\Phi{\bf x})^\top(\boldsymbol\Phi{\bf x})\\ &=&||\boldsymbol\Phi{\bf x}||^2\geq0\tag{9}\\ \end{eqnarray}$

目的関数のヘッセ行列は半正定値行列であることが示せました。
よって、目的関数は凸関数です。

偉人の名言

待っているだけの人達にも何かが起こるかもしれないが、それは努力した人達の残り物だけである。
エイブラハム・リンカーン

参考文献

パターン認識と機械学習上巻

機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

曲線フィッティング - 最小二乗法

要件