要素ごとに計算して理解する正規方程式。

はじめに

機械学習の方面では超おなじみの線形回帰分析ですが、線形回帰分析といえば最小二乗法がほぼ定番で、最小二乗法といえば正規方程式がほぼ必ず登場します。

よって正規方程式も超おなじみなわけで、正規方程式の導出の方法についてGoogle先生に尋ねてみると、行列やベクトルを駆使しまくる方法やプログラムを教えてくれます。

しかし、この情報だけだと行列やベクトルの計算から一度離れて一周回って戻ってきた時に「なんでそうなるんだっけ?」ということになりかねません。

そこで、この記事では最後の変形までは表記を簡略化する以外の目的では行列やベクトルの計算を使わずに要素ごとに計算して導出してみることにします。

線形回帰分析の概要

線形回帰分析とは、ある$n$個からなるデータの組$\{x_1, \cdots, x_n\}$(これらの数を説明変数といいます。)があったときに求められる値$y$(目的変数といいます。)が

\begin{align}
y &= \sum_{i=1}^{n}a_ix_i \label{eq:aixi}
\end{align}

という関係式で表すことができるものと仮定し、どのような説明変数を与えてもある程度正確そうな目的変数を与えてくれそうな$\{a_1, \cdots, a_n\}$のうち最良のものを求めることをいいます。

最小二乗法からの正規方程式

最小二乗法の概要

このある程度正確そうな状態を定量的に表すために、説明変数及び目的変数の組を用意します。この記事では仮に$m$組の説明変数及び$m$個の目的変数が用意できたとして、そのうちの$j$番目$(1 \le j \le m)$の説明変数を$\boldsymbol{x}_j = (x_{j,1}, \cdots, x_{j,n})$とおくことにし、対応する目的変数を$y_j$とおくことにします。

このとき、$\boldsymbol{x}_j$および$y_j$の間には

\begin{align}
y_j &= \sum_{i=1}^{n}a_ix_{j,i} \label{eq:aixireal}
\end{align}

の関係が成り立って欲しいところですが、そもそも$\{a_1, \cdots, a_n\}$はまだ求まっていないのですから、(\ref{eq:aixireal})式が成り立つ保証はありません。

そこで、(\ref{eq:aixireal})式の左辺及び右辺の値が一致しないことを前提に、左辺と右辺の差を二乗し、さらにそれを$1 \le j \le m$の範囲で足し合わせて$m$で割ったものを$J(a_1, \cdots, a_n) = J(\boldsymbol{a})$とおきます。

すると、$J(\boldsymbol{a})$は…

\begin{align}
J(\boldsymbol{a}) &= \sum_{j=1}^m\left( y_j\, – \sum_{i=1}^{n}a_ix_{j,i} \right)^2 \label{eq:rss}
\end{align}

と書けます。(\ref{eq:rss})式は残差平方和(RSS: residual sum of squares)と呼ばれる式です。

また、この記事では直接は使用しませんが、(\ref{eq:rss})式の両辺を$m$で割ると…

\begin{align}
\frac{J(\boldsymbol{a})}{m} &= \frac{1}{m}\sum_{j=1}^m\left( y_j\, – \sum_{i=1}^{n}a_ix_{j,i} \right)^2 \label{eq:mse}
\end{align}

と書けます。

(\ref{eq:mse})式は平均二乗誤差(MSE: Mean Squared Error)になります。

$J$を$\boldsymbol{a}$の関数と考えて、$J$が最小になるような$\boldsymbol{a}$を求めることを考えるのが最小二乗法のキモになります。

要素ごとに偏微分。

ここからは説明変数及び目的変数として与えられた$\boldsymbol{x}_j$および$y_j$は既知の定数であると考えることに留意しつつ以降の計算を進めていきます。

(\ref{eq:rss})式左辺は$\{a_1, \cdots, a_n\}$の2次の項の係数$\{x_1^2, \cdots, x_n^2\}$は負でない値になりますので$J$は$\{a_1, \cdots, a_n\}$のそれぞれについて高々2次の関数になります。

したがって、$J(\boldsymbol{a})$を$\{a_1, \cdots, a_n\}$のそれぞれについて偏微分した結果得られる式が0になるとき、すなわち$1 \le k \le n$を満たす整数$k$について、

\begin{align}
\frac{\partial J(\boldsymbol{a})}{\partial a_k} &= -2\sum_{j=1}^mx_{j,k}\left( y_j\, – \sum_{i=1}^{n}a_ix_{j,i} \right) \label{eq:partialderivative}
\end{align}

がすべて0になるときに$J(\boldsymbol{a})$が最小値をとります。なお、(\ref{eq:partialderivative})式は

\begin{align}
\frac{\partial}{\partial a_k} \left( y_j\, – \sum_{i=1}^{n}a_ix_{j,i} \right) &= x_{j,k} \label{eq:partialderivativek}
\end{align}

となることを利用しています。

正規方程式の導出

(\ref{eq:partialderivative})式の右辺が0となるときには、

\begin{align}
\sum_{j=1}^mx_{j,k}y_j &= \sum_{j=1}^mx_{j,k}\sum_{i=1}^{n}a_ix_{j,i} \label{eq:nefirst}
\end{align}

になりますので、これを行列かベクトルの形式でまとめて書けないか考えてみます。

まず左辺。

まず、(\ref{eq:nefirst})式の左辺について考えます。これは、

\begin{align}
\sum_{j=1}^mx_{j,k}y_j &=
\begin{pmatrix}
x_{1,k} & \cdots & x_{m,k}
\end{pmatrix}
\begin{pmatrix}
y_1 \cr
\vdots \cr
y_m
\end{pmatrix}\label{eq:nesecond}
\end{align}

と書けます。$k$は$1 \le k \le n$を満たす整数であったことを思い出すと、(\ref{eq:nesecond})式は縦方向に並べることができて…

\begin{align}
\begin{pmatrix}
\displaystyle\sum_{j=1}^mx_{j,1}y_j \cr
\vdots \cr
\displaystyle\sum_{j=1}^mx_{j,n}y_j
\end{pmatrix} &=
\begin{pmatrix}
x_{1,1} & \cdots & x_{m,1} \cr
\vdots & \ddots & \vdots \cr
x_{1,n} & \cdots & x_{m,n} \cr
\end{pmatrix}
\begin{pmatrix}
y_1 \cr
\vdots \cr
y_m
\end{pmatrix}
\label{eq:nethird}
\end{align}

と書けます。

ここで、$X = \begin{pmatrix}
x_{1,1} & \cdots & x_{1,n} \cr
\vdots & \ddots & \vdots \cr
x_{m,1} & \cdots & x_{m,n} \cr
\end{pmatrix} $, $\boldsymbol{y} = (y_1, \cdots y_n)^T$(右肩の$T$は行列またはベクトルの転置を表します。以下同じ。)とおくと、(\ref{eq:nethird})式の右辺は

\begin{align}
\begin{pmatrix}
x_{1,1} & \cdots & x_{m,1} \cr
\vdots & \ddots & \vdots \cr
x_{1,n} & \cdots & x_{m,n} \cr
\end{pmatrix}
\begin{pmatrix}
y_1 \cr
\vdots \cr
y_m
\end{pmatrix} &= X^T\boldsymbol{y} \label{eq:nefourth}
\end{align}

と書くことができます。

次に右辺。

次に、(\ref{eq:nefirst})式の左辺について考えます。

左辺は総和を2回とる形になっていて一見ややこしいので、とりあえず、

\begin{align}
\sum_{i=1}^{n}a_ix_{j,i} &= \sum_{i=1}^{n}a_ix_{j,i} \nonumber \cr
&= b_j \label{eq:bj}
\end{align}

とおいてみます。すると…

\begin{align}
\sum_{j=1}^mx_{j,k}\sum_{i=1}^{n}a_ix_{j,i} &= \sum_{j=1}^mx_{j,k}b_j \nonumber \cr
&= \begin{pmatrix}
x_{1,k} & \cdots & x_{m,k}
\end{pmatrix}
\begin{pmatrix}
b_1 \cr
\vdots \cr
b_m
\end{pmatrix} \label{eq:nefifth}
\end{align}

ここで再度$k$が$1 \le k \le n$を満たす整数であったことを思い出すと、(\ref{eq:nefifth})式は縦方向に並べることができて…

\begin{align}
\begin{pmatrix}
\displaystyle\sum_{j=1}^mx_{j,1}b_j \cr
\vdots \cr
\displaystyle\sum_{j=1}^mx_{j,n}b_j
\end{pmatrix} &=
\begin{pmatrix}
x_{1,1} & \cdots & x_{m,1} \cr
\vdots & \ddots & \vdots \cr
x_{1,n} & \cdots & x_{m,n} \cr
\end{pmatrix}
\begin{pmatrix}
b_1 \cr
\vdots \cr
b_m
\end{pmatrix} \nonumber \cr
&= X^T\boldsymbol{b}\label{eq:nesixth}
\end{align}

と書けます。なお、$\boldsymbol{b} = (b_1, \cdots b_m)^T$とおいています。

(\ref{eq:bj})式を用いると$\boldsymbol{b}$は、

\begin{align}
\begin{pmatrix}
b_1\cr
\vdots\cr
b_j\cr
\vdots\cr
b_n\cr
\end{pmatrix} &= \begin{pmatrix}
\displaystyle\sum_{i=1}^{n}x_{1,i}a_i \cr
\vdots \cr
\displaystyle\sum_{i=1}^{n}x_{j,i}a_i \cr
\vdots \cr
\displaystyle\sum_{i=1}^{n}x_{m,i}a_i
\end{pmatrix} \nonumber \cr
&= \begin{pmatrix}
x_{1,1} & \cdots & x_{1,n} \cr
\vdots & \ddots & \vdots \cr
x_{j,1} & \cdots & x_{j,n} \cr
\vdots & \ddots & \vdots \cr
x_{m,1} & \cdots & x_{m,n} \cr
\end{pmatrix}
\begin{pmatrix}
a_1 \cr
\vdots \cr
a_n
\end{pmatrix} \nonumber \cr
&= X\boldsymbol{a} \label{eq:bjsecond}
\end{align}

になります。

ここまで(\ref{eq:nefirst})式の左辺及び右辺に対して等式を縦に並べるという操作を1回ずつ行っているために、(\ref{eq:nefourth})式及び(\ref{eq:nesixth})式が等しいとおくことができて、さらに(\ref{eq:bjsecond})式の結果と合わせると…

\begin{align}
X^T\boldsymbol{y} &= X^TX\boldsymbol{a} \label{eq:normalequation}
\end{align}

が成り立つことがわかります。

なんとか正規方程式にたどり着くことができました。

特に$X^TX$が正則行列である場合には$(X^TX)^{-1}$が計算できますので、

\begin{align}
\boldsymbol{a} &= (X^TX)^{-1}X^T\boldsymbol{y} \label{eq:normalequationsolution}
\end{align}

と計算することにより、$\boldsymbol{a}$を求めることができます。$\blacksquare$

まとめ

ここまでの計算で行列の要素ごとに計算を行うことで、正規方程式を導出することができました。

行列やベクトルの計算時に使える関係式を忘れても計算できる方法ですので、ご参考にしていただけると幸いです。

この記事は以上です。