線形モデル
データ$(y_1,x_{11},\cdots,x_{1m}),\cdots(y_n,x_{n1},\cdots,x_{nm})$ を線形モデル $$ y=\theta_0+\theta_1x_1+\cdots+\theta_mx_m=\theta_0+\sum_{j=1}^m \theta_jx_j $$ で説明したい. 最小二乗法の考え方に基づき,
$\displaystyle\sum_{i=1}^n\left[y_i-\left(\theta_0+\sum_{j=1}^m \theta_jx_{ij}\right)\right]^2$ を最小化することを目標とする. ここで, $$ X= \renewcommand{\arraystretch}{1.5} \left[ \begin{array}{ccccc} 1 &
x_{11}& x_{12} &\cdots &x_{1m} \\ 1& x_{21}&x_{22}&\cdots &x_{2m}\\ \vdots & \vdots& \vdots& & \vdots \\1 &x_{n1} & x_{n2} &\cdots & x_{nm}
\end{array} \right] ,\ \ \ \boldsymbol{\theta}= \left[ \begin{array}{c} \theta_0\\ \theta_1\\ \vdots \\ \theta_m \end{array} \right] ,\ \ \ \boldsymbol{y}= \left[ \begin{array}{c} y_1\\ y_2\\ \vdots
\\ y_n \end{array} \right] $$ とすると, $$\displaystyle \sum_{i=1}^n\left[y_i-\left(\theta_0+\sum_{j=1}^m
\theta_jx_{ij}\right)\right]^2={\|\boldsymbol{y}-X\boldsymbol{\theta}\|}^2={\|X\boldsymbol{\theta}-\boldsymbol{y}\|}^2$$ より, $\|X\boldsymbol{\theta}-\boldsymbol{y}\|$の最小値問題となる. これを解くには, 次の正規方程式を用いる.
正規方程式
$A$を行列, $\boldsymbol{x}, \boldsymbol{b}$を縦ベクトルとし, $\|\cdot\|$をノルムとする. また$A^{\top}$を$A$の転置行列とする(ただし${}^t\!A, A^{\mathrm{T}}$という表記法もある). $A^{\top}A$が正則なとき,
$\|A\boldsymbol{x}-\boldsymbol{b}\|$を最小にする$\boldsymbol{x}$はただ一つであり, それは, 正規方程式： $$A^{\top}A\boldsymbol{x}=A^{\top}\boldsymbol{b}$$ を解くことで得られる.
$\|A\boldsymbol{x}-\boldsymbol{b}\|=0$, すなわち$A\boldsymbol{x}=\boldsymbol{b}$となる解が見つかればよい(→補足1)が, 見つからないときでもこの定理により, $\|A\boldsymbol{x}-\boldsymbol{b}\|$を最小にするような$\boldsymbol{x}$を見つけられる. 正規方程式は$A\boldsymbol{x}=\boldsymbol{b}$の両辺に左から$A^{\top}$を掛けたものである.
[証明] 目的関数の二乗 $\|A\boldsymbol{x}-\boldsymbol{b}\|^2$ は \begin{align*} \|A\boldsymbol{x}-\boldsymbol{b}\|^2&=(A\boldsymbol{x}-\boldsymbol{b})^{\top}(A\boldsymbol{x}-\boldsymbol{b})\ \ \ (\because 補足2)\\ &=(\boldsymbol{x}^{\top}A^{\top}-\boldsymbol{b}^{\top})(A\boldsymbol{x}-\boldsymbol{b})\\ &=\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}-\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}-\boldsymbol{b}^{\top}A\boldsymbol{x}+\boldsymbol{b}^{\top}\boldsymbol{b}\\ &=\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}-2\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}+\boldsymbol{b}^{\top}\boldsymbol{b}\ \ \ (\because 補足3) \end{align*} これを $\boldsymbol{x}$で微分する（各要素$x_j$で偏微分する, つまり勾配ベクトルを求める→補足4）と, $$\frac{\partial \|A\boldsymbol{x}-\boldsymbol{b}\|^2}{\partial \boldsymbol{x}}=2A^{\top}A\boldsymbol{x}-2A^{\top}\boldsymbol{b}$$ となる. よって, $\|A\boldsymbol{x}-\boldsymbol{b}\|$ が最小となる必要条件として, $$\frac{\partial \|A\boldsymbol{x}-\boldsymbol{b}\|^2}{\partial \boldsymbol{x}}=0\ \Leftrightarrow\ A^{\top}A\boldsymbol{x}=A^{\top}\boldsymbol{b}$$ が得られる. 特に, $A^{\top}A$ が正則なときは, $$\boldsymbol{x}=(A^{\top}A)^{-1}A^{\top}\boldsymbol{b}$$ が唯一の解であり, この $\boldsymbol{x}$ が最小値を与える.
補足1: $n$変数の連立1次方程式$A\boldsymbol{x}=\boldsymbol{b}$に解がただ一つ存在する必要十分条件は $${\rm rank}(A)=n$$ 補足2: $\mathbb{R}^n$のベクトル $\boldsymbol{a}= \renewcommand{\arraystretch}{1} \left[ \begin{array}{c} a_1 \\ \vdots \\ a_n \end{array} \right], \ \boldsymbol{b}= \left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right] $に対して $$(\boldsymbol{a}, \boldsymbol{b})=\boldsymbol{a}^{\top}\boldsymbol{b}=a_1b_1+\cdots+a_nb_n$$ を$\mathbb{R}^n$の標準内積とし, ベクトル$\boldsymbol{a}$のノルムを $$\|\boldsymbol{a}\|=\sqrt{(\boldsymbol{a},\boldsymbol{a})} $$ とする.
補足3: $\boldsymbol{b}^{\top}A\boldsymbol{x}=(\boldsymbol{b}, A\boldsymbol{x})$はスカラーなので, 転置を取っても同じである. よって, $$\boldsymbol{b}^{\top}A\boldsymbol{x}=\left(\boldsymbol{b}^{\top}A\boldsymbol{x}\right)^{\top}=\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b} $$ 補足4：多変数関数$f(x_1,x_2,\cdots,x_n)$に対して, 各変数による偏微分を並べたベクトルを勾配ベクトルという. 例えば, $f(x_1,x_2,x_3)=x_1+x_2^2+x_3^3$のとき, 勾配ベクトルは$(1,2x_2,3x_3^2)$となる. この勾配ベクトルは, $$\frac{df}{d\boldsymbol{x}}={\rm grad}f=\nabla f=\left(\frac{\partial f}{\partial x_1}, \cdots, \frac{\partial f}{\partial x_n}\right)$$などと表記される. ただし縦ベクトルか横ベクトルかは$\boldsymbol{x}$による. 対称行列$A'(=A^{\top}A)$(→補足5)に関する二次形式 $$\boldsymbol{x}^{\top}A'\boldsymbol{x}=\sum_{i=1}^n\sum_{j=1}^na'_{ij}x_ix_j\ \ \ \left(A':=\left[a'_{ij}\right]_{n\times n}\right)$$ を$x_k$で偏微分すると, \begin{align*} \frac{\partial \boldsymbol{x}^{\top}A'\boldsymbol{x}}{\partial x_k}&=\frac{\partial}{\partial x_k}\sum_{i=1}^n\sum_{j=1}^na'_{ij}x_ix_j\\ &=\frac{\partial}{\partial x_k}\left(\sum_{j (\neq k)}a'_{kj}x_kx_j+\sum_{i (\neq k)}a'_{ik}x_ix_k+a'_{kk}x_k^2\right)\\ &=\sum_{j (\neq k)}a'_{kj}x_j+\sum_{i (\neq k)}a'_{ik}x_i+2a'_{kk}x_k\\ &=2\sum_{i=1}^na'_{ki}x_k\ \ \ (\because A'は対称行列なので, a'_{ik}=a'_{ki}) \end{align*} となるので, 勾配ベクトルは $$\frac{\partial \left(\boldsymbol{x}^{\top}A'\boldsymbol{x}\right)}{\partial \boldsymbol{x}}=\left[ \begin{array}{c} 2\sum_{i=1}^na'_{1i}x_1 \\ \vdots \\ 2\sum_{i=1}^na'_{ni}x_n \end{array} \right]=2\left[ \begin{array}{ccc} a'_{11} &\cdots&a'_{1n}\\ \vdots&\ddots&\vdots \\ a'_{n1} &\cdots&a'_{nn} \end{array} \right]\left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right]=2A'\boldsymbol{x}$$ となる. ゆえに $$\frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}\right)}{\partial \boldsymbol{x}}=2A^{\top}A\boldsymbol{x}$$ が成り立つ. また, 線形関数 \begin{align*} \boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}=(A\boldsymbol{x}, \boldsymbol{b})&=\left(\sum_{j=1}^m a_{1j}x_j\right)b_1+\cdots+\left(\sum_{j=1}^m a_{nj}x_j\right)b_n=\sum_{i=1}^n\sum_{j=1}^m a_{ij}x_jb_i \end{align*} を$x_k$で偏微分すると, \begin{align*} \frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}\right)}{\partial x_k}&=\frac{\partial}{\partial x_k}\sum_{i=1}^n\sum_{j=1}^m a_{ij}x_jb_i\\ &=\frac{\partial}{\partial x_k}\sum_{j=1}^m\left(\sum_{i=1}^na_{ij}b_i\right)x_j\\ &=\sum_{i=1}^na_{ik}b_i \end{align*} となるので, 勾配ベクトルは $$\frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}\right)}{\partial \boldsymbol{x}}=\left[ \begin{array}{c} \sum_{i=1}^na_{i1}b_i \\ \vdots \\ \sum_{i=1}^na_{im}b_i \end{array} \right]=\left[ \begin{array}{ccc} a_{11} &\cdots&a_{n1}\\ \vdots&\ddots&\vdots \\ a_{1m} &\cdots&a_{nm} \end{array} \right]\left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right]=A^{\top}\boldsymbol{b}$$ となる.
補足5: $A^{\top}A$は対称行列となる.
[証明] 行列$B$が対称行列ならば, $B^{\top}=B$である. $$\left(A^{\top}A\right)^{\top}=A^{\top}\left(A^{\top}\right)^{\top}=A^{\top}A$$ が成り立つので, $A^{\top}A$は対称行列である.
$\|A\boldsymbol{x}-\boldsymbol{b}\|=0$, すなわち$A\boldsymbol{x}=\boldsymbol{b}$となる解が見つかればよい(→補足1)が, 見つからないときでもこの定理により, $\|A\boldsymbol{x}-\boldsymbol{b}\|$を最小にするような$\boldsymbol{x}$を見つけられる. 正規方程式は$A\boldsymbol{x}=\boldsymbol{b}$の両辺に左から$A^{\top}$を掛けたものである.
[証明] 目的関数の二乗 $\|A\boldsymbol{x}-\boldsymbol{b}\|^2$ は \begin{align*} \|A\boldsymbol{x}-\boldsymbol{b}\|^2&=(A\boldsymbol{x}-\boldsymbol{b})^{\top}(A\boldsymbol{x}-\boldsymbol{b})\ \ \ (\because 補足2)\\ &=(\boldsymbol{x}^{\top}A^{\top}-\boldsymbol{b}^{\top})(A\boldsymbol{x}-\boldsymbol{b})\\ &=\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}-\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}-\boldsymbol{b}^{\top}A\boldsymbol{x}+\boldsymbol{b}^{\top}\boldsymbol{b}\\ &=\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}-2\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}+\boldsymbol{b}^{\top}\boldsymbol{b}\ \ \ (\because 補足3) \end{align*} これを $\boldsymbol{x}$で微分する（各要素$x_j$で偏微分する, つまり勾配ベクトルを求める→補足4）と, $$\frac{\partial \|A\boldsymbol{x}-\boldsymbol{b}\|^2}{\partial \boldsymbol{x}}=2A^{\top}A\boldsymbol{x}-2A^{\top}\boldsymbol{b}$$ となる. よって, $\|A\boldsymbol{x}-\boldsymbol{b}\|$ が最小となる必要条件として, $$\frac{\partial \|A\boldsymbol{x}-\boldsymbol{b}\|^2}{\partial \boldsymbol{x}}=0\ \Leftrightarrow\ A^{\top}A\boldsymbol{x}=A^{\top}\boldsymbol{b}$$ が得られる. 特に, $A^{\top}A$ が正則なときは, $$\boldsymbol{x}=(A^{\top}A)^{-1}A^{\top}\boldsymbol{b}$$ が唯一の解であり, この $\boldsymbol{x}$ が最小値を与える.
補足1: $n$変数の連立1次方程式$A\boldsymbol{x}=\boldsymbol{b}$に解がただ一つ存在する必要十分条件は $${\rm rank}(A)=n$$ 補足2: $\mathbb{R}^n$のベクトル $\boldsymbol{a}= \renewcommand{\arraystretch}{1} \left[ \begin{array}{c} a_1 \\ \vdots \\ a_n \end{array} \right], \ \boldsymbol{b}= \left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right] $に対して $$(\boldsymbol{a}, \boldsymbol{b})=\boldsymbol{a}^{\top}\boldsymbol{b}=a_1b_1+\cdots+a_nb_n$$ を$\mathbb{R}^n$の標準内積とし, ベクトル$\boldsymbol{a}$のノルムを $$\|\boldsymbol{a}\|=\sqrt{(\boldsymbol{a},\boldsymbol{a})} $$ とする.
補足3: $\boldsymbol{b}^{\top}A\boldsymbol{x}=(\boldsymbol{b}, A\boldsymbol{x})$はスカラーなので, 転置を取っても同じである. よって, $$\boldsymbol{b}^{\top}A\boldsymbol{x}=\left(\boldsymbol{b}^{\top}A\boldsymbol{x}\right)^{\top}=\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b} $$ 補足4：多変数関数$f(x_1,x_2,\cdots,x_n)$に対して, 各変数による偏微分を並べたベクトルを勾配ベクトルという. 例えば, $f(x_1,x_2,x_3)=x_1+x_2^2+x_3^3$のとき, 勾配ベクトルは$(1,2x_2,3x_3^2)$となる. この勾配ベクトルは, $$\frac{df}{d\boldsymbol{x}}={\rm grad}f=\nabla f=\left(\frac{\partial f}{\partial x_1}, \cdots, \frac{\partial f}{\partial x_n}\right)$$などと表記される. ただし縦ベクトルか横ベクトルかは$\boldsymbol{x}$による. 対称行列$A'(=A^{\top}A)$(→補足5)に関する二次形式 $$\boldsymbol{x}^{\top}A'\boldsymbol{x}=\sum_{i=1}^n\sum_{j=1}^na'_{ij}x_ix_j\ \ \ \left(A':=\left[a'_{ij}\right]_{n\times n}\right)$$ を$x_k$で偏微分すると, \begin{align*} \frac{\partial \boldsymbol{x}^{\top}A'\boldsymbol{x}}{\partial x_k}&=\frac{\partial}{\partial x_k}\sum_{i=1}^n\sum_{j=1}^na'_{ij}x_ix_j\\ &=\frac{\partial}{\partial x_k}\left(\sum_{j (\neq k)}a'_{kj}x_kx_j+\sum_{i (\neq k)}a'_{ik}x_ix_k+a'_{kk}x_k^2\right)\\ &=\sum_{j (\neq k)}a'_{kj}x_j+\sum_{i (\neq k)}a'_{ik}x_i+2a'_{kk}x_k\\ &=2\sum_{i=1}^na'_{ki}x_k\ \ \ (\because A'は対称行列なので, a'_{ik}=a'_{ki}) \end{align*} となるので, 勾配ベクトルは $$\frac{\partial \left(\boldsymbol{x}^{\top}A'\boldsymbol{x}\right)}{\partial \boldsymbol{x}}=\left[ \begin{array}{c} 2\sum_{i=1}^na'_{1i}x_1 \\ \vdots \\ 2\sum_{i=1}^na'_{ni}x_n \end{array} \right]=2\left[ \begin{array}{ccc} a'_{11} &\cdots&a'_{1n}\\ \vdots&\ddots&\vdots \\ a'_{n1} &\cdots&a'_{nn} \end{array} \right]\left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right]=2A'\boldsymbol{x}$$ となる. ゆえに $$\frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}\right)}{\partial \boldsymbol{x}}=2A^{\top}A\boldsymbol{x}$$ が成り立つ. また, 線形関数 \begin{align*} \boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}=(A\boldsymbol{x}, \boldsymbol{b})&=\left(\sum_{j=1}^m a_{1j}x_j\right)b_1+\cdots+\left(\sum_{j=1}^m a_{nj}x_j\right)b_n=\sum_{i=1}^n\sum_{j=1}^m a_{ij}x_jb_i \end{align*} を$x_k$で偏微分すると, \begin{align*} \frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}\right)}{\partial x_k}&=\frac{\partial}{\partial x_k}\sum_{i=1}^n\sum_{j=1}^m a_{ij}x_jb_i\\ &=\frac{\partial}{\partial x_k}\sum_{j=1}^m\left(\sum_{i=1}^na_{ij}b_i\right)x_j\\ &=\sum_{i=1}^na_{ik}b_i \end{align*} となるので, 勾配ベクトルは $$\frac{\partial \left(\boldsymbol{x}^{\top}A^{\top}\boldsymbol{b}\right)}{\partial \boldsymbol{x}}=\left[ \begin{array}{c} \sum_{i=1}^na_{i1}b_i \\ \vdots \\ \sum_{i=1}^na_{im}b_i \end{array} \right]=\left[ \begin{array}{ccc} a_{11} &\cdots&a_{n1}\\ \vdots&\ddots&\vdots \\ a_{1m} &\cdots&a_{nm} \end{array} \right]\left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right]=A^{\top}\boldsymbol{b}$$ となる.
補足5: $A^{\top}A$は対称行列となる.
[証明] 行列$B$が対称行列ならば, $B^{\top}=B$である. $$\left(A^{\top}A\right)^{\top}=A^{\top}\left(A^{\top}\right)^{\top}=A^{\top}A$$ が成り立つので, $A^{\top}A$は対称行列である.
コメントをお書きください