2015/05/27

正規方程式の導出と計算例

分野: 線形代数  レベル: 大学数学

$A^{\top}A$ が正則なとき,$\|Ax-b\|$ を最小にする $x$ はただ一つであり,それは正規方程式:$A^{\top}Ax=A^{\top}b$ を解くことで得られる。

前半は正規方程式を用いた最小二乗法の計算の具体例。後半は正規方程式の導出。

最小二乗法と正規方程式

  • $x,b$ は縦ベクトル,$A$ は行列です。 $\|x\|$ はベクトル $x$ の長さを表します。
  • $A$ と $b$ が与えられたとき,$\|Ax-b\|$ を最小にするような $x$ を求める問題は非常に重要です。→最小二乗法の行列表現(単回帰,多変数,多項式)
  • 連立方程式 $Ax=b$ が解を持つときは嬉しいけども,解を持たない時にも諦めるのではなく,$Ax$ が $b$ に近くなるような $x$ を探したいというモチベーションです。
  • 正規方程式は,$Ax=b$ の両辺に左から $A^{\top}$ をかけただけなので覚えやすいです。

正規方程式を用いた計算例

最小二乗法(直線)の簡単な説明で扱った問題です。

例題

$(2,3),\:(4,7),\:(9,11)$ というデータの組に対して最小二乗法を適用してもっともらしい直線を引け。

解答

求める直線の傾きを $p$,切片を $q$ とおくと,以下のように行列表現できる:
目標:$\|Ax-b\|$ を最小にする $x=\begin{pmatrix}p\\q\end{pmatrix}$ を求める。
ただし,$A=\begin{pmatrix}2&1\\4&1\\9&1\end{pmatrix}$,$b=\begin{pmatrix}3\\7\\11\end{pmatrix}$

よって,答えは正規方程式を解くことにより,
$x=(A^{\top}A)^{-1}A^{\top}b=\begin{pmatrix}\frac{14}{13}\\\frac{21}{13}\end{pmatrix}$
求める直線の方程式は $y=\dfrac{14}{13}x+\dfrac{21}{13}$

正規方程式の導出

考え方は非常に単純です。凸な二次関数なので微分して$=0$ とするだけです。ただし,計算は慣れていないとやや大変です(行列の基本的な演算や微分公式を用いる)。

(正規方程式の導出)
まず,目的関数の二乗 $\|Ax-b\|^2$ を整理する:
$\|Ax-b\|^2=(Ax-b)^{\top}(Ax-b)\\
=(x^{\top}A^{\top}-b^{\top})(Ax-b)\\
=x^{\top}A^{\top}Ax-2x^{\top}A^{\top}b+b^{\top}b$
ただし,最後の変形で補足1を用いた。

これを $x$ で微分する(各要素で偏微分する,つまり勾配ベクトルを求める→補足2)と,$2A^{\top}Ax-2A^{\top}b$ となる。よって,$\|Ax-b\|$ が最小となる必要条件として,$A^{\top}Ax=A^{\top}b$ が得られる。

特に,$A^{\top}A$ が正則なときは,$x=(A^{\top}A)^{-1}A^{\top}b$ が唯一の解であり,この $x$ が最小値を与える。

補足1:$b^{\top}Ax$ はスカラーなので,転置を取っても同じ。つまり,$b^{\top}Ax=x^{\top}A^{\top}b$

補足2:対称行列 $A$ に関する二次形式 $x^{\top}Ax$ の微分(勾配ベクトル)は $2Ax$,
線形関数 $x^{\top}A^{\top}b$ の微分は $A^{\top}b$
(単純計算で簡単に証明できる)

正規方程式。きれいですよねえ。
分野: 線形代数  レベル: 大学数学