エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

最小二乗法の基礎をまとめる

本記事は以下の過去記事で得た結果を用います.

行列における単射,核(カーネル)が零ベクトルのみ,列フルランクは同値であることを証明する - エンジニアを目指す浪人のブログ

行列のランク落ち,列フルランク,行フルランク,フルランクそれぞれのときの4つの基本部分空間を図示する - エンジニアを目指す浪人のブログ

グラム行列についての定理を証明する - エンジニアを目指す浪人のブログ

ムーア・ペンローズ逆行列の定義,構成,一意性についてまとめる - エンジニアを目指す浪人のブログ

ムーア・ペンローズ逆行列と元の行列の4つの基本部分空間との関係について考える - エンジニアを目指す浪人のブログ


最小二乗法(least squares method ; LSM)について,それなりに利用頻度が高いものの,そのたびに勉強しなおしていて効率が悪かったので,その基礎をまとめておくことにしました.応用志向の線形代数の教科書ともいうべきBoyd and Vandenberghe(2018)の12章1,2節をベースにしています.

=================================================================================

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 最小二乗問題
{\displaystyle \; } 2. 解
{\displaystyle \;\;\; } 2.1. 正規方程式
{\displaystyle \;\;\; } 2.2. 最小二乗問題のただ一つの解


[ 0. 準備 ]

記号を準備します.

{\displaystyle \;\;\; \mathbf{R}^{n}  \;\;\;\;\;\;\;\;  } {\displaystyle \mathbf{R} } の要素を要素にもつ {\displaystyle n } 次元ベクトルの集合
{\displaystyle \;\;\; I \;\;\;\;\;\;\;\;\;\;  } {\displaystyle n \times n } 単位行列
{\displaystyle \;\;\; A \;\;\;\;\;\;\;\;\;\;  } {\displaystyle m \times n } 行列
{\displaystyle \;\;\; C(A) \;\;\;\;\; } {\displaystyle A } の列空間
{\displaystyle \;\;\; N(A^T) \;\;\; } {\displaystyle A } の左零空間

{\displaystyle \;\;\; x = [ x_1 \ \cdots \ x_n ]^T \;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル
{\displaystyle \;\;\; b = [ b_1 \ \cdots \ b_m ]^T \;\;\;\;\;\;\; } {\displaystyle m } 次元ベクトル
{\displaystyle \;\;\; r = [ r_1 \ \cdots \ r_m ]^T \;\;\;\;\;\;\; } {\displaystyle m } 次元ベクトル

 {\displaystyle  \langle \cdot , \cdot \rangle \;\;\; } 通常の内積  {\displaystyle \langle x,y \rangle = y^T x \;\;\; } (性質は文献[2]にあります)
{\displaystyle \left\| \cdot \right\| \;\;\; } (ユークリッド)ノルム {\displaystyle \left\| x \right\| = \sqrt{ x^T x } = \sqrt{ x_1^2 + \cdots + x_n^2 } \;\;\; } (性質は文献[3]にあります)


本記事では以下を仮定します.

仮定.
(0.1) {\displaystyle \; A } は縦長の行列( {\displaystyle \Leftrightarrow [ m \gt n ] } )
(0.2) {\displaystyle \; \mathrm{rank}\ A = n \; } ( {\displaystyle  \Leftrightarrow  A } の列 {\displaystyle a_1,\ldots,a_n } は線形独立)

これは列フルランクであることと同値です.冒頭の過去記事(行列における単射)も参考になります.


[ 1. 最小二乗問題 ]

連立一次方程式 {\displaystyle Ax=b } は変数の数 {\displaystyle n } よりも方程式の数 {\displaystyle m } の方が多い方程式系です.仮定.より {\displaystyle b }{\displaystyle A } の列の線形結合である場合に限りただ一つの解をもちます.冒頭の過去記事(行列のランク落ち)にあります.

それ以外のほとんどの {\displaystyle b } については {\displaystyle Ax = b } となる {\displaystyle x } は存在しません.妥協として,残差(residual)(ベクトル) {\displaystyle r=Ax-b } を可能な限り小さくする {\displaystyle x } を探索することを考えます.このことを,残差のノルム {\displaystyle \left\| Ax - b \right\| } を最小化する {\displaystyle x } を選択すること,で実現することにします.そのような {\displaystyle x }{\displaystyle Ax \approx b } をみたすものと考えることができます.

ノルムを最小化することはノルムの二乗を最小化することと同値なので,以下を最小化することを考えます.

{\displaystyle \;\;\; \left\| Ax - b \right\|^2  = \left\| r  \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;   = r_1^2 + \cdots + r_m^2 }

これを最小化する {\displaystyle n } 次元ベクトル {\displaystyle x = \hat{x} } を探索することを最小二乗問題(least squares problem)といい,以下のように定式化します.

(1.1){\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| Ax - b \right\|^2 }

行列 {\displaystyle A } とベクトル {\displaystyle b } は問題(1.1)のデータ(data),{\displaystyle \left\| Ax - b \right\|^2 } は目的関数(objective function)といいます.

問題(1.1)は {\displaystyle r }{\displaystyle x } のアフィン関数(文献[4]にあります)であることを強調して線形最小二乗問題(linear least squares problem)ということもあります.

すべての {\displaystyle x } について {\displaystyle \left\| A \hat{x} -b \right\|^2 \le \left\| A x -b \right\|^2 } をみたす任意の {\displaystyle \hat{x} } は,最小二乗問題(1.1)の解(solution)あるいは {\displaystyle Ax -b } の最小二乗近似解(least squares approximate solution)といいます.この解 {\displaystyle \hat{x} } は残差のノルムを最小化することで得たのであって方程式 {\displaystyle A\hat{x}=b } をみたす必要はなく,{\displaystyle Ax=b } の解でなくてもよいことに注意します.

最適残差ノルム(optimal residual norm) {\displaystyle \left\| A\hat{x}-b \right\| } が小さいとき,{\displaystyle \hat{x} }{\displaystyle Ax=b } を近似的に解く,といいます.一方,{\displaystyle Ax=b } をみたす {\displaystyle x} が存在するとき,残差のノルムが {\displaystyle 0 } なのでそれは最小二乗問題の解になっています.

最小二乗問題(1.1)のもう一つの名称は回帰(regression)です.{\displaystyle \hat{x} } はベクトル {\displaystyle b} から行列 {\displaystyle A } の列(空間)の上への回帰の結果です.


列に着目する解釈.
{\displaystyle A } の列をベクトル {\displaystyle a_1,\ldots,a_n } とすると,(1.1)の目的関数は以下のように変形でき,{\displaystyle b } に最も近い線形結合を探索する問題として解釈できます.

{\displaystyle \;\;\; \left\| A x -b \right\|^2 = \left\| ( x_1 a_1 + \cdots + x_n a_n ) - b \right\|^2 }

以下のベクトルは {\displaystyle a_1,\ldots,a_n } のすべての線形結合のなかで(ユークリッドノルムの意味で)最も {\displaystyle b } に近いベクトルです.

{\displaystyle \;\;\; A \hat{x} = \hat{x_1} a_1 + \cdots + \hat{x_n} a_n }


行に着目する解釈.
{\displaystyle A } の行をベクトル {\displaystyle \tilde{a}_1^T ,\ldots,\tilde{a}_n^T } とすると,{\displaystyle m } 次元ベクトルである残差 {\displaystyle r } の要素は以下となります.

{\displaystyle \;\;\; r_i = \tilde{a}_i^T x -b_i, \;\; i=1,\ldots,m }

よって(1.1)の目的関数は以下のように {\displaystyle m} 個の二乗項の和となります.

{\displaystyle \;\;\; \left\| A x -b \right\|^2 = (\tilde{a}_1^T x -b_1)^2 + \cdots + (\tilde{a}_m^T x -b_m)^2 }



[ 2. 解 ]
[ 2.1. 正規方程式 ]

以下の方程式系を正規方程式(normal equations)といいます.この方程式をみたす解を {\displaystyle x = \hat{x} } とします.

(2.1.1){\displaystyle \;\;\;  A^T A x = A^T b  }

{\displaystyle A^T A  } について以下が成り立ちます.{\displaystyle a_1,\ldots,a_n }{\displaystyle A } の列です.

{\displaystyle \;\;\; A^T A = \begin{bmatrix} a_1^T \\ a_2^T \\ \vdots \\ a_n^T  \end{bmatrix} \begin{bmatrix} a_1 & a_2 & \cdots & a_n  \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} a_{1}^T a_1 & a_{1}^T a_2 & \cdots & a_{1}^T a_n \\ a_{2}^T a_1 & a_{2}^T a_2 & \cdots & a_{2}^T a_n \\ \vdots  & \vdots & \vdots  \\ a_{n}^T a_1 & a_{n}^T a_2  & \cdots & a_{n}^T a_n \end{bmatrix}  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} a_{1}^T a_1 & a_{2}^T a_1 & \cdots & a_{n}^T a_1 \\ a_{1}^T a_2 & a_{2}^T a_2 & \cdots & a_{n}^T a_2 \\ \vdots  & \vdots & \vdots  \\ a_{1}^T a_n & a_{2}^T a_n  & \cdots & a_{n}^T a_n \end{bmatrix}  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} \langle a_1,a_1 \rangle & \langle a_2,a_1 \rangle & \cdots & \langle a_n,a_1 \rangle \\ \langle a_1,a_2 \rangle & \langle a_2,a_2 \rangle & \cdots & \langle a_n,a_2 \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle a_1,a_n \rangle & \langle a_2,a_n \rangle & \cdots & \langle a_n,a_n \rangle \end{bmatrix}  }


これはグラム行列であり,仮定.(0.2)と冒頭の過去記事(グラム行列)定理 7.2.10.(b)から {\displaystyle A^T A } は正定値したがって正則です.(2.1.1)は以下で表されるただ一つの解をもちます.

(2.1.2){\displaystyle \;\;\; \hat{x} =  (A^T A)^{-1} A^T b  }

仮定.と冒頭の過去記事(ムーア・ペンローズ逆行列の定義)より行列 {\displaystyle (A^T A)^{-1} A^T } は行列 {\displaystyle A } のムーア・ペンローズ逆行列(擬似逆行列)です.

(2.1.3){\displaystyle \;\;\; A^+ =  (A^T A)^{-1} A^T  }

(2.1.4){\displaystyle \;\;\; \hat{x} =  A^+ b }

{\displaystyle A^+ }{\displaystyle A } の左逆行列なので,{\displaystyle Ax = b } が解をもつときその解は(2.1.4)であり,最小二乗問題(1.1)の解でもあります.

(2.1.4)は {\displaystyle A } が正方行列で正則である場合の方程式 {\displaystyle Ax = b } の解 {\displaystyle x = A^{-1} b } によく似ているように見えます.この2つの違いについて理解することは重要です.だいたいの場合(2.1.4)は {\displaystyle A \hat{x} = b } をみたしません.

次節の事実.にあるように(2.1.4)は最小二乗問題(1.1)のただ一つの解であり,この解は {\displaystyle b } についての線形関数であることを示しています.このことは {\displaystyle A } が正方行列で正則である場合の解が {\displaystyle b } についての線形関数であることの一般化になっています.


[ 2.2. 最小二乗問題のただ一つの解 ]

事実.

正規方程式(2.1.1)の解(2.1.2)(2.1.4)は最小二乗問題(1.1)のただ一つの解である.

証明.

すべての {\displaystyle  x \neq \hat{x}  } について {\displaystyle  \left\| Ax - b \right\|^2 \gt \left\| A \hat{x} - b \right\|^2 } が成り立つことを示せばよい.
はじめに {\displaystyle  \left\| Ax - b \right\|^2 \ge \left\| A \hat{x} - b \right\|^2 } を示す.

{\displaystyle \;\;\; \left\| Ax - b \right\|^2 = \left\| (Ax - A \hat{x}  ) + ( A \hat{x} - b) \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  =   \left[ (Ax - A \hat{x}  ) + ( A \hat{x} - b) \right]^T \left[ (Ax - A \hat{x}  ) + ( A \hat{x} - b) \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (Ax - A \hat{x})^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (A (x -  \hat{x}) )^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (x -  \hat{x})^T A^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (x -  \hat{x})^T ( A^T A \hat{x} - A^T b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (x -  \hat{x})^T 0 \;\;\; \because } (2.1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 \;\;\;\;\;\; } (※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  \ge \left\| A \hat{x} - b \right\|^2  \;\;\; \because \forall x \in \mathbf{R}^n , \ \left\| Ax - A \hat{x} \right\|^2 \ge 0 }

つぎに {\displaystyle  x = \hat{x}  } がただ一つの解であることを示す.

{\displaystyle \;\;\; \left\| Ax - b \right\|^2 = \left\| A \hat{x} - b \right\|^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Rightarrow \ \left\| Ax - A \hat{x} \right\|^2 = 0 \;\;\; \because } (※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Leftrightarrow \ \left\| A (x -  \hat{x}) \right\|^2 = 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Leftrightarrow \ A (x -  \hat{x}) = 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Rightarrow \  x -  \hat{x} = 0 \;\;\; \because } 仮定.(0.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Leftrightarrow \  x = \hat{x}  }

したがって {\displaystyle x = \hat{x} }{\displaystyle \left\| Ax - b \right\|^2 = \left\| A \hat{x} - b \right\|^2 } となるただ一つの {\displaystyle x } であり,すべての {\displaystyle  x \neq \hat{x}  } について {\displaystyle  \left\| Ax - b \right\|^2 \gt \left\| A \hat{x} - b \right\|^2 } が成り立つ.(証明終わり)


幾何的な解釈.

{\displaystyle A \hat{x} }{\displaystyle b } に最も近い {\displaystyle A } の列の線形結合です.最適な残差は {\displaystyle \hat{r} = A \hat{x} - b  } であり,以下が成り立ちます.

{\displaystyle \;\;\; \left\| \hat{r} \right\| = \left\| A \hat{x} - b \right\| }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \left\| AA^+b - b \right\| \;\;\; \because } (2.1.4)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \left\| (I - AA^+ )b \right\| }

冒頭の過去記事(ムーア・ペンローズ逆行列と元の行列)事実.(2.1)(2.3)より以下が成り立ちます.

(2.2.1){\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; AA^+ b \; }{\displaystyle b }{\displaystyle N(A^T) } に沿った {\displaystyle C(A) } への直交射影

(2.2.2){\displaystyle \;\;\; - \hat{r} = (I - AA^+) b \; }{\displaystyle b }{\displaystyle C(A) } に沿った {\displaystyle N(A^T) } への直交射影


{\displaystyle m=3,\ n=2 } の場合のイメージを図示します.最小二乗問題(1.1)を解くことはすべての {\displaystyle Ax } から {\displaystyle b } との距離が最も近いものを探索する問題であり,{\displaystyle Ax \perp \hat{r} } であることがわかります.

f:id:seetheworld1992:20190315122007j:plain

実際に任意の {\displaystyle x } について以下を確認することができます.正規方程式(2.1.1)はこの結果をみたすための方程式と解釈することもできます.

{\displaystyle \;\;\; (Ax)^T \ \hat{r} = (Ax)^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = x^T A^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = x^T (A^T A \hat{x} - A^T b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 0 \;\;\; \because } (2.1.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;  \Rightarrow \ Ax \perp \hat{r} }


{\displaystyle b }{\displaystyle A } の列の線形結合( {\displaystyle  \Leftrightarrow  b \in C(A) })のとき,{\displaystyle Ax=b } はただ一つの解をもちます.{\displaystyle b }{\displaystyle N(A^T) } 方向(上図の赤いベクトル方向)の要素は持ちません.(2.2.2)より {\displaystyle - \hat{r} = 0 } です.

=================================================================================

以上,最小二乗法の基礎をまとめました.最小二乗法には初等的なイメージがありますが,実際には線形代数の様々な概念が用いられていてとても教育的であると感じます.



参考文献
[1] Boyd, S., and Vandenberghe, L. (2018), Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares, Cambridge University Press.
[2] Wolfram MathWorld Inner Product のページ http://mathworld.wolfram.com/InnerProduct.html
[3] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm
[4] Wolfram MathWorld Afine Function のページ http://mathworld.wolfram.com/AffineFunction.html

おまけ
[1] へのリンク http://vmls-book.stanford.edu/vmls.pdf