nano_exit

基礎的なことこそ、簡単な例が必要だと思うのです。

任意の基底関数における正規方程式

多項式による正規方程式の導出を、こちらにサイトでお世話になった。
線形回帰の Normal Equation(正規方程式)について
しかし、別に多項式じゃなくても何でも良いと思ったので、導出してみた。

何かしらの入力 xに対する出力 y N個の組 (x_1, y_1), \cdots, (x_N, y_N) で得られているとする。
この結果から、 (x,y)の関係を基底関数 \phi^{(0)}(x), \cdots, \phi^{(N_P)}(x)の組み合わせ(線形結合)で表現したい。
言い換えれば、各基底関数に掛ける係数 c^{(0)}, \cdots, c^{(N_p)}をどのように取れば最も誤差が小さくなるか、を求めたい。
ここで、関数 \phi xに依存するが、係数 c xに依存しないことに注意。全ての xで上手いこと行くような cが欲しいのである。

ある点 (x_i, y_i)における誤差 \Delta_iは、差分の二乗を取って大小の比較が出来るように定義する。(要素数で割って分散で表しても良い)


\displaystyle
\Delta_i = \left( c^{(0)} \phi^{(0)}(x_i) + \cdots + c^{(N_p)} \phi^{(N_p)}(x_i) - y_i \right)^2 \\
\displaystyle
\qquad = \left( \left( \sum^{N_p}_{j=0} c^{(j)} \phi^{(j)}(x_i) \right) - y_i  \right)^2 \\
\displaystyle
\qquad = \left( \left( X \vec{c} \right)_i  - y_i \right)^2 =  \left( X \vec{c} \right)^2_i - 2 \left( X \vec{c} \right)_i y_i  + y^2_i \\
\displaystyle
\qquad \equiv \delta^2_i

ここで、行列 Xとベクトル \vec{c}, \vec{y}, \vec{\delta}を以下の様に定義した。


\displaystyle
\begin{align}
X &= \left( \begin{array}{cccc} \phi^{(0)}(x_1) & \phi^{(1)}(x_1) & \cdots & \phi^{(N_p)}(x_1) \\ \phi^{(0)}(x_2) & \phi^{(1)}(x_2) & \cdots & \phi^{(N_p)}(x_2) \\ \vdots & \vdots & \vdots & \vdots \\ \phi^{(0)}( x_N ) & \phi^{(1)}( x_N ) & \cdots & \phi^{(N_p)}( x_N ) \end{array} \right) \\
\vec{c} &= \left( \begin{array}{c} c^{(0)} \\ c^{(1)} \\ \vdots \\ c^{(N_p)} \end{array} \right)
\end{align}

\displaystyle
\begin{align}
\vec{ y } = \left( \begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_N \end{array} \right)
\quad
\vec{ \delta } = \left( \begin{array}{c} \delta_1 \\ \delta_2 \\ \vdots \\ \delta_N \end{array} \right)
\end{align}

 \vec{c}はベクトルのなので、 X \vec{c}もベクトルであることに注意。
また、行列やベクトルのサイズが N_p+1なのか Nなのかにも注意。

行列を使って表現することを意識して、全誤差 \Deltaを次の様に表す。

 
\displaystyle
\Delta = \sum^N_{i=1} \Delta_i = \sum^N_{i=1} \delta_i \delta_i = {}^t \! \vec{\delta} \, \vec{\delta}
 = {}^t \!\! \left(  X \vec{c} -\vec{ y } \right) \left( X \vec{c} - \vec{ y } \right)

ここで、 \Delta c^{(k)}微分したものを \Delta^{(k)}と定義すると、


\displaystyle
\frac{d}{d c^{(k)}} \left( X \vec{c}\right)_i = \frac{d}{d c^{(k)}} \sum^{N_p}_{j} c^{(j)} \phi^{(j)}(x_i) \\
\displaystyle
\quad = \phi^{(k)}( x_i )
\\
\displaystyle
\frac{d}{d c^{(k)}} \left( X \vec{c}\right)^2_i = \frac{d}{d c^{(k)}} \sum^{N_p}_{j} \sum^{N_p}_{j'} c^{(j)} c^{(j')} \phi^{(j)}(x_i) \phi^{(j')}(x_i) \\
\displaystyle
\quad = \phi^{(k)}( x_i ) \sum^{N_p}_{j'} c^{(j')} \phi^{(j')}(x_i) + \phi^{(k)}( x_i ) \sum^{N_p}_{j} c^{(j)} \phi^{(j)}(x_i) \\
\displaystyle
\quad = 2 \phi^{(k)}( x_i ) \sum^{N_p}_{j} c^{(j)} \phi^{(j)}(x_i) = 2 \phi^{(k)}( x_i ) \left( X \vec{c}\right)_i
\\
\displaystyle
\therefore \Delta^{(k)}_i = 2 \phi^{(k)}( x_i ) \left( \left( X \vec{c}\right)_i - y_i \right) = 2 \phi^{(k)}( x_i ) \delta_i
\\
\displaystyle
\therefore \Delta^{(k)} =  2 \sum^N_i \phi^{(k)}( x_i ) \delta_i = 2 \left( {}^t \! X \vec{\delta} \right)_k

ただし、 \vec{ \Delta }の要素数は係数 cと同じであることに注意。

今考えているのは、全誤差 \Deltaが最小になる様な \vec{c}を求めることなので、 \Delta極値を取る条件、すなわち全ての \Delta^{(k)}がゼロになる条件から、係数 cが満たすべき方程式が得られる。


\displaystyle
\vec{ \Delta } =  2 {}^t \! X \vec{\delta} = 2 {}^t \! X \left( X \vec{c} - \vec{ y } \right) = \vec{0} \\
\displaystyle
\therefore \vec{ c } = \left( {}^t \! X X \right)^{-1} \, {}^t \! X \, \vec{ y }

これが、正規方程式と呼ばれる関係式であり、結果だけ見ると、


\displaystyle
\vec{y} = X \vec{c}

を満たす \vec{c}を求める問題にあたかもすり替わったかの様に見える。
実際には、極値問題をちゃんと解いているわけで、「えいやっ!と置いてしまえ!」ということではなく、安心して使える。

導出的には最小値ではなく極値を求めているため、式だけでは停留点や最大値が求まってしまう可能性を除けないが、実際には誤差は無限に大きくなれるため、少なくとも最大値は除かれている。

この導出では、基底関数の形を特に指定していないため、(個人的には)見通しが良くなっている(と思う)。
例えば、二つの基底関数 \phi^{(0)}( x ) = 1,  \phi^{(1)}( x ) = x を使えば線形フィッティングだし、様々な周期の三角関数(もしくは平面波)を使えばフーリエ変換になる。

また、面白いのが、基底関数行列 Xは上で示したように N \times (N_p + 1 )行列なので、一般に正方行列ではなく、正則でもない。
そのため、 \vec{y} = X \vec{c} \vec{c}について解くためには、まずは {}^t \! Xを掛けて \vec{c}の係数行列を正方にするという着眼点が、個人的には新鮮だった。