VMLS 12.2 最小二乗法 その二

線形代数

前回→VMLS 12.1
テキスト→Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

12.2 Solution

　この章では、データ行列 {\displaystyle A} についての

{\displaystyle A } の各行は線形独立である。{\displaystyle \quad(12.2)}
という前提のもとで、最小二乗法 (12.1) の解のいくつかの表現を導く。

計算による解法

　このセクションでは基本的な計算による最小二乗法の解法を学ぶ (証明には計算を用いない他の手法もある。そちらは次のセクションに記す)。関数 {\displaystyle f(x)=||Ax-b||^2} を最小化する {\displaystyle \hat{x}} は

{\displaystyle \frac{\partial f}{\partial x_i}(\hat{x})=0,\quad i=1,...,n,}
を満たす必要があり、これはベクトル表記で
{\displaystyle \nabla f(\hat{x})=0}
と表される。{\displaystyle \nabla f(\hat{x})=0} は {\displaystyle \hat{x}} における {\displaystyle f } の勾配である。勾配は行列表示で次のように表すことができる。
{\displaystyle \nabla f(\hat{x})=2A^T(Ax-b).\quad (12.3)}
この公式は184ページ*1のチェインルールから導くことができ、二次関数の和の勾配は {\displaystyle {\S}C.1}*2 で与えられる。念のため、公式 (12.3) の導出方法を示す。最小二乗法の目的関数を和の形で書くと、
{\displaystyle f(x)=||Ax-b||^2=\sum_{i=1}^{m}(\sum_{j=1}^{n}A_{ij}x_j -b_i)^2 }
となる。
{\displaystyle \nabla f(x)_k } を求めるために {\displaystyle x_k } に対して偏微分する。和を項別微分すると、
{\displaystyle \begin{eqnarray} \nabla f(x)_k &=& \frac{\partial f}{\partial x_i}(x)\\ &=& \sum_{i=1}^{m} 2 (\sum_{j=1}^{n} A_{ij}x_j -b_i)(A_{ik})\\ &=& \sum_{i=1}^{m} 2(A^T)_{ki} (Ax-b)_i\\ &=& (2A^T (Ax-b))_k. \end{eqnarray} }
これは公式 (12.3) を要素の項別に書き出したものである。
　最小二乗法の解法の導出を続ける。{\displaystyle ||Ax-b||^2 } を最小化するどのような {\displaystyle \hat{x} } も次式を満足する。
{\displaystyle \nabla f(\hat{x}) =2A^T(A\hat{x}-b) =0. }
これは次のように表すこともできる。
{ \displaystyle A^T A\hat{x}=A^T b.\quad(12.4) }
これらの方程式は正規方程式 (normal equations) と呼ばれる。係数行列 {\displaystyle A^TA } は {\displaystyle A } に関するグラム行列 (要素が各行の内積である行列) である。
　 {\displaystyle A } の各列が線形独立であるという我々の仮定 (12.2) は、グラム行列 {\displaystyle A^TA } が正則であることを示唆している (214ページ、{\displaystyle {\S}11.5}*3 )。これは
{\displaystyle \hat{x}=(A^T A)^{-1}A^T b\quad (12.5)}
が正規方程式 (12.4) の唯一の解法であることを意味する。すなわち、これは最小二乗法 (12.1) の唯一の解法である。
　我々は (12.5) で現れる行列 {\displaystyle (A^TA)^{-1}A^T } をすでに学習している。(11.5) で与えられる行列 {\displaystyle A } の疑似逆行列である。したがって我々は最小二乗法の解法をシンプルな形で
{\displaystyle \hat{x}=A^{\dagger}b \quad (12.6)}
と書ける。
　{\displaystyle {\S}11.5} で見たように、{\displaystyle A^{\dagger} } は {\displaystyle A } の左側逆行列であり、この over-determined な連立方程式 {\displaystyle Ax=b } が解を持つとき、{\displaystyle \hat{x}=A^{\dagger}b } はこれを解くことができる。しかしいま、我々は最小二乗解、つまり {\displaystyle f(x)=||Ax-b||^2} を最小化する {\displaystyle \hat{x}=A^{\dagger}b } に着目している (そしてもし {\displaystyle Ax=b } に解が存在するとき、{\displaystyle \hat{x}=A^{\dagger}b } こそが解である)。
　方程式 (12.6) は {\displaystyle A } が正則行列であるとき、連立一次方程式 {\displaystyle Ax=b } の公式、すなわち、{\displaystyle x=A^{-1}b } に酷似している。最小二乗解である公式 (12.6) と、解が一意に定まる連立一次方程式の公式 {\displaystyle x=A^{-1}b } との違いを理解することは非常に重要である。連立一次方程式と逆行列の場合は、{\displaystyle x=A^{-1}b } は厳密に {\displaystyle Ax=b } を満足する。最小二乗解の場合は、{\displaystyle \hat{x}=A^{\dagger}b } は一般的に {\displaystyle A\hat{x}=b } を満足しない。
　公式 (12.6) は最小二乗解 {\displaystyle \hat{x} } は {\displaystyle b } の一次関数であることを示している。これより、一般に、一意な解を持つ連立一次方程式はその右辺の一次関数である。

最小二乗解の直接的な証明

このセクションでは、{\displaystyle \hat{x}=(A^T A)^{-1}A^T b } が最小二乗法 (12.1) の解であることを、計算を用いずに直接証明する。任意の {\displaystyle x \neq \hat{x} } に対して、{\displaystyle \hat{x} } が {\displaystyle ||Ax-b||^2 } を最小化するとき

{\displaystyle ||A\hat{x}-b||^2<||Ax-b||^2 }
が成り立つことを示す。
　まず
{\displaystyle \begin{eqnarray} ||Ax-b||^2 &=& ||(Ax-A\hat{x})+(A\hat{x}-b)||^2\\ &=& ||Ax-A\hat{x}||^2+||A\hat{x}-b||^2+2(Ax-A\hat{x})^T(A\hat{x}-b) \quad (12.7) \end{eqnarray} }
から始める。ここで、つぎの恒等式を利用した。
{\displaystyle ||u+v||^2=(u+v)^T(u+v)=||u||^2+||v||^2+2u^T v. }
(12.7) の第三項はゼロである。
{\displaystyle \begin{eqnarray} (Ax-A\hat{x})^T(A\hat{x}-b) &=& (x-\hat{x})^T A^T(A\hat{x}-b)\\ &=& (x-\hat{x})^T (A^TA\hat{x}-A^T b)\\ &=& (x-\hat{x})^T 0\\ &=& 0 \end{eqnarray} }
三行目で我々は正規方程式 {\displaystyle (A^T A)\hat{x}=A^T b } を用いた。これにより、(12.7) は次のように簡単化される。
{\displaystyle ||Ax-b||^2=||A(x-\hat{x})||^2+||A\hat{x}-b||^2. }
右辺第一項は非負であるため
{\displaystyle ||Ax-b||^2 \geq ||A\hat{x}-b||^2. }
これは {\displaystyle \hat{x} } が {\displaystyle ||Ax-b||^2 } を最小化することを表している。上の等式が成立するとすると、{\displaystyle ||Ax-b||^2 = ||A\hat{x}-b||^2 } であるので、{\displaystyle ||A(x-\hat{x})||^2=0 }、すなわち {\displaystyle A(x-\hat{x})=0 } を得る。{\displaystyle A } は線形独立な列を持つので、我々は {\displaystyle x-\hat{x}=0,\quad i.e.,\quad x=\hat{x} } を得る。したがって、{\displaystyle ||Ax-b||^2=||A\hat{x}-b||^2 } を満たす {\displaystyle x } は {\displaystyle x=\hat{x} } のみであり、すべての {\displaystyle x\neq \hat{x} } に対して {\displaystyle ||Ax-b||^2>||A\hat{x}-b||^2 } が成り立つ。

行形式

最小二乗解の公式は行列 {\displaystyle A } の行 {\displaystyle x=\tilde{a}_i^T } に関する便利な表記がある。

{\displaystyle \hat{x}=(A^T A)^{-1}A^T b=(\sum_{i=1}^m \tilde{a}_i\tilde{a}_i^T )^{-1}(\sum_{i=1}^m b_i \tilde{a}_i).\quad(12.8) }
この公式で、我々は {\displaystyle n\times n } 型グラム行列 {\displaystyle A^T A } を外積の和として、{\displaystyle n } 次ベクトル {\displaystyle A^T b } を {\displaystyle m } 個の {\displaystyle n } 次ベクトルとして表している。
f:id:gorgonzolax:20210424222744p:plain
Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

直交性原理

点 {\displaystyle A\hat{x} } は {\displaystyle b } に最も近い {\displaystyle A } の各列の線形結合である。最適化された残差は {\displaystyle \hat{r}=A\hat{x}-b } である。最適化された残差は直交性原理と呼ばれる性質を満足する。それらは {\displaystyle A } の各列に直交し、また、{\displaystyle A } の各列の任意の線形結合に直交する。すなわち、任意の {\displaystyle n } 次ベクトル {\displaystyle z } に対して、

{\displaystyle (Az)\perp \hat{r} }
を得る。我々は直交性原理を {\displaystyle A^T (A\hat{x}-b) =0 } で表される正規方程式から導くことができる。任意の{\displaystyle n } 次ベクトル {\displaystyle z } に対して、
{\displaystyle (Az)^T \hat{r}=(Az)^T (A\hat{x}-b)=z^T A^T (A\hat{x}-b)=0 }
が得られる。
　{\displaystyle m=3 }、{\displaystyle n=2 } の最小二乗法について、直交性原理は図12.2のように示される。影のついた平面は {\displaystyle A } の二つの列 {\displaystyle a_1 } と {\displaystyle a_2 } のすべての線形結合の組 {\displaystyle z_1 a_1+z_2 a_2 } を表す。点 {\displaystyle A\hat{x} } は平面上で最も {\displaystyle b } に近い点である。最適化された残差は点 {\displaystyle \hat{r} } は {\displaystyle b } から {\displaystyle A\hat{x} } へのベクトルとして表される。このベクトルは平面上のどの点とも直交している。

次回→VMLS 12.3

*1:すみません。まだ勉強できていないのでテキストをご参照ください。

*2:こちらもテキストをご参照ください。

*3:テキストを(略