ごるごの勉強記録

電気タイプの大学生

VMLS 12.3 最小二乗法 その三

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

12.3 Solving least squares problems

 最小二乗法はQR分解を用いて解くことができる。{\displaystyle A}QR分解における {\displaystyle A=QR} とする (これは12.3の仮定にもとづく)。疑似逆行列 {\displaystyle A^{\dagger} }{\displaystyle A^{\dagger}=R^{-1}Q^T } と表されるため、次式を得る。

{\displaystyle \hat{x}=R^{-1}Q^T b. \quad(12.10) }
{\displaystyle \hat{x} } を計算するために、まず {\displaystyle Q^T }{\displaystyle b } を掛ける。それから back substitution*1 を用いて {\displaystyle R^{-1}Q^T b } を計算する。{\displaystyle A }{\displaystyle b } が与えられたときに最小二乗解 {\displaystyle \hat{x} } を求めるアルゴリズムを以下にまとめる。


アルゴリズム 12.1 QR分解を用いた最小二乗法の解法
各行が線形独立な {\displaystyle m\times n } 型行列 {\displaystyle A }{\displaystyle m } 次元ベクトル {\displaystyle b } が与えられたとき、

  1. {\displaystyle A }QR分解 {\displaystyle A=QR } を計算する。
  2. {\displaystyle Q^T b } を計算する。
  3. Back substitution により上三角行列の方程式 {\displaystyle R\hat{x}=Q^T b } を解く。



係数行列が正方行列の場合との比較

 係数行列 {\displaystyle A } が正方行列である連立一次方程式 {\displaystyle A } の解は {\displaystyle x=A^{-1}b } であった。{\displaystyle x }{\displaystyle A }QR分解を用いて {\displaystyle x=R^{-1}Q^T b } と表される ((11.4) 参照)。この方程式は (12.10) と同一である。(12.10) における唯一の相違点は、{\displaystyle A }{\displaystyle Q } が正方行列である必要がなく、{\displaystyle R^{-1}Q^T b } が最小二乗解、すなわち、{\displaystyle Ax=b } を一般に満たさないということである。
 実際に、アルゴリズム 12.1 は連立方程式QR分解で解くアルゴリズム 11.2 と同一である (11.2 の唯一の相違点は {\displaystyle A }{\displaystyle Q } が縦長でもよいことである) 。
 {\displaystyle A } が正方行列であるとき、方程式 {\displaystyle Ax=b } を解くことと最小二乗法 {\displaystyle minimize\quad ||Ax-b||^2 } は同値であり、アルゴリズム 11.2 とアルゴリズム 12.1 も同値となる。したがってアルゴリズム 12.1 は {\displaystyle A } が正方行列であるとき方程式 {\displaystyle Ax=b } を解くアルゴリズム 11.2 の一般化であると考えることができ、{\displaystyle A } が縦長であるときの最小二乗解を計算できる。

バックスラッシュ記法

 行列を扱ういくつかのソフトウェアパッケージには優決定系の方程式の最小二乗法を計算するためのバックスラッシュ演算が提供されている (209ページ参照)。これらのパッケージでは {\displaystyle A\backslash b }{\displaystyle A } が正則であるときの {\displaystyle Ax=b } の解 {\displaystyle x=A^{-1}b }、または {\displaystyle A } が縦長で線形独立な列をもつときの最小二乗解 {\displaystyle x=A^{\dagger}b } を意味する (ただしバックスラッシュ記法は数学的に正式な記法ではない)。

複雑性

 アルゴリズム 12.1 の最初のステップの複雑性は {\displaystyle 2mn^2 } フロップである。次のステップでは行列とベクトルの積を含むため、複雑性は {\displaystyle 2mn } である。三番目のステップでは {\displaystyle n^2 } フロップを要する。合計フロップ数は

{\displaystyle 2mn^2+2mn+n^2\approx 2mn^2 }
となる。第二項と第三項を無視すればそれは最初の {\displaystyle n }{\displaystyle 2m } の要素よりも小さくなる。アルゴリズムのオーダーは {\displaystyle mn^2 } である。複雑性は {\displaystyle A } の行の次元に比例し変数の数の二乗に比例する。

スパース最小二乗法

 疎行列 {\displaystyle A } に対する最小二乗法はさまざまな場面に応用され、たとえば、12.1 の一般的なアルゴリズムで疎行列用に工夫したQR分解 (190ページ参照) を用いることでより効率的に解が求まる。
 {\displaystyle A } が疎行列であることを活用するもう一つの簡単な手法は正規方程式 {\displaystyle A^T Ax=A^T b } を巨大な疎行列を用いて解くことである。

{ \displaystyle \begin{bmatrix} 0&A^T\\ A&I \end{bmatrix} \begin{bmatrix} \hat{x}\\ \hat{y} \end{bmatrix} = \begin{bmatrix} 0\\b \end{bmatrix}. \quad (12.11)  }
これは {\displaystyle m\times n } 型の方程式を組み合わせ、係数行列を正方行列にしたものである。{\displaystyle A } が疎行列ならばその係数行列も疎行列である。{\displaystyle (\hat{x},\hat{y}) } がこれらの方程式を満たすとき、(12.11) を満たす {\displaystyle \hat{x} } を求めることは容易であり、逆に {\displaystyle \hat{x} } が正規方程式を満たすとき、{\displaystyle (\hat{x},\hat{y}) }{\displaystyle \hat{y}=b-A\hat{x} } とすると (12.11) を満たす。係数行列が疎行列である方程式を解くどのような手法でも (12.11) を解くことができる。

行列の最小二乗法

 最小二乗法のシンプルな拡張は方程式 {\displaystyle ||AX-B||^2 } を最小化する {\displaystyle n\times k } 型行列 {\displaystyle X } を求めることである。ここで {\displaystyle A }{\displaystyle m\times n } 型行列、{\displaystyle B }{\displaystyle m\times k } 型行列、ノルムは行列ノルムである。これは行列の最小二乗法 (matrix least squares problem) と呼ばれる。{\displaystyle k=1 } のとき {\displaystyle x }{\displaystyle b } はベクトルであり、行列の最小二乗法はもとの最小二乗法となる。
 行列の最小二乗法は、実は {\displaystyle k } 個の最小二乗法の組に過ぎない。これを確かめるために、

{\displaystyle ||AX-B||^2=||Ax_1-b_1||^2+\cdots+||Ax_k-b_k||^2 }
と表す。{\displaystyle x_j }{\displaystyle X }{\displaystyle j } 番目の列、{\displaystyle b_j }{\displaystyle B }{\displaystyle j } 番目の列である (ここで、我々は行列のノルムの二乗は列のノルムの二乗和に等しいという性質を用いた)。よって、目的関数はそれぞれが {\displaystyle X } の列のみに依存する {\displaystyle k } 個の項の和である。したがって、我々は独立に列 {\displaystyle x_j } を選ぶことができ、それらはそれぞれに対応する項 {\displaystyle ||Ax_j-b_j||^2 } を最小化する。{\displaystyle A } が線形独立な列をもつとすると、解は {\displaystyle \hat{x}_j=A^{\dagger}b_j } である。したがって、行列の最小二乗法の解法は
{\displaystyle \begin{eqnarray} \hat{X} &=& \begin{bmatrix} \hat{x}_1 \cdots \hat{x}_k \end{bmatrix} \\ &=& \begin{bmatrix} A^{\dagger}b_1 \cdots A^{\dagger}b_k \end{bmatrix} \\ &=& A^{\dagger} \begin{bmatrix} b_1 \cdots b_k \end{bmatrix} \\ &=& A^{\dagger}B \quad\quad\quad\quad\quad\quad (12.12) \end{eqnarray} }
行列の最小二乗法の非常にシンプルな解 {\displaystyle \hat{X}=A^{\dagger}B } は、{\displaystyle k=1 } であるのもとの最小二乗法の場合にも成り立つ。多くの線形代数のソフトウェアパッケージはバックスラッシュ演算子 {\displaystyle A\backslash B }{\displaystyle A^{\dagger}B } を表すために使っているが、これは数学的に正式な記法ではない。
 行列の最小二乗法はアルゴリズム 12.1 が factor-solve アルゴリズムのもう一つの例であるという事実を用いることで効率的に解くことができる。{\displaystyle \hat{X}=A^{\dagger}B } を解くために我々は {\displaystyle A }QR分解を行い、アルゴリズム 12.1 のステップ2とステップ3を {\displaystyle k } 個の {\displaystyle B } の各列について実行する。合計の計算コストは {\displaystyle 2mn^2+k(2mn+n^2) } フロップである。 {\displaystyle k }{\displaystyle n } と比較して小さいときは、およそ {\displaystyle 2mn^2} フロップであり、一つの最小二乗法 (すなわち、右側にベクトルがある場合) の計算コストと等しくなる。

*1:上三角行列を係数行列にもつ連立一次方程式を一番下の行から順に求める手法。

VMLS 11.5 疑似逆行列

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

11.5 Pseudo-inverse

列の線形独立性とグラム行列の正則性

 はじめに、{\displaystyle m\times n } 型行列 {\displaystyle A } はグラム行列 {\displaystyle A^T A } が正則である場合のみ線形独立な列をもつことを証明する。
 まず、{\displaystyle A } の各列が線形独立であるとする。{\displaystyle x }{\displaystyle (A^T A)x=0 } を満足するある {\displaystyle n } 次元ベクトルとする。左側から {\displaystyle x^T } を掛けると

{\displaystyle 0=x^T=x^T(A^T Ax)=x^T A^T Ax=||Ax||^2, }
すなわち {\displaystyle Ax=0 } を得る。{\displaystyle A } の各列は線形独立であるから、{\displaystyle x=0 } を得る。{\displaystyle (A^T A)x=0 } の唯一の解は {\displaystyle x=0 } であるため、{\displaystyle A^T A } は正則である。
 つぎに逆を証明する。{\displaystyle A } の各列が線形従属である、すなわち、{\displaystyle Ax=0 } を満たす {\displaystyle n } 次元の非零ベクトル {\displaystyle x } が存在するとする。左側から {\displaystyle A^T } を掛けると {\displaystyle (A^T A)x=0 } を得る。これはグラム行列 {\displaystyle A^T A } が正則ではないことを意味する。

正方行列または縦長の行列の疑似逆行列

 {\displaystyle A } が線形独立な列をもつ (すなわち、{\displaystyle A } が正方行列か縦長の行列である) とき、{\displaystyle A } が左逆行列をもつことを示す (我々はすでにこの逆、すなわち左逆行列をもつ行列が線形独立な列をもつことを知っている)。{\displaystyle A } が線形独立な列をもつとすると、{\displaystyle A^T A } は正則である。ここで、

{\displaystyle ((A^T A)^{-1}A^T)A=(A^T A)^{-1}(A^T A)=I }
より、{\displaystyle (A^T A)^{-1}A^T }{\displaystyle A } の左逆行列である。
 この特定の {\displaystyle A } の左逆行列{\displaystyle A } の疑似逆行列 (pseudo-inverse of {\displaystyle A }) とよばれ、{\displaystyle A^{\dagger} } と表記される。
{\displaystyle A^{\dagger}=(A^T A)^{-1}A^T.\quad (11.5) }
疑似逆行列は二人の数学者に因んでムーア・ペンローズ逆行列 (Moore-Penrose inverse) とも呼ばれる。
 {\displaystyle A } が正方行列であるとき、疑似逆行列 {\displaystyle A^{\dagger} } は元の逆行列となる。
{\displaystyle A^{\dagger}=(A^T A)^{-1}A^T=A^{-1}A^{-T}A^T=A^{-1}I=A^{-1}. }
ただし、{\displaystyle A } が正方行列でないとき、この方程式は成立しない。

他の場合での疑似逆行列

 疑似逆行列 {\displaystyle A^{\dagger} } は、縦長であるがその列が線形従属な行列や横長でありその行が線形従属な行列、正方行列であるが正則ではない行列を含むどのような行列に対しても定義できる。しかし、これらの場合には疑似逆行列は左逆行列ではなく、それぞれ右逆行列または逆行列となる。(これらの場合に {\displaystyle A^{\dagger} } が何を意味するのかについては例題 15.11 で紹介する。)

QR分解による疑似逆行列

 QR分解は疑似逆行列についての簡単な公式を与える。{\displaystyle A } が左逆行列をもつとき、その列は線形独立であり、QR分解 {\displaystyle A=QR } が存在する。ここで、

{\displaystyle A^T A=(QR)^T(QR)=R^T Q^T QR=R^T R }
より、
{\displaystyle A^{\dagger}=(A^T A)^{-1} A^T=(R^T R)^{-1}(QR)^T=R^{-1}R^{-T}R^T Q^T=R^{-1}Q^T }
を得る。
 QR分解を用いて、{\displaystyle Q^T } の列について back substitution を適用して疑似逆行列を計算できる (これは11.3の {\displaystyle A }正則行列であるときのアルゴリズムと全く同一である)。この手法の複雑性はQR分解に要する {\displaystyle 2n^2 m } フロップと back substitusion に要する {\displaystyle mn^2 } フロップである。したがって合計は {\displaystyle 3mn^2 } フロップとなる。
 同様に、{\displaystyle A } が右逆行列であるとき、その転置行列のQR分解 {\displaystyle A^T=QR } が存在する。{\displaystyle AA^T=(QR)^T(QR)=R^T Q^T QR=R^T R } であり、
{\displaystyle A^{\dagger}=A^T(A^T A)^{-1}=(QR)(R^T R)^{-1}=QRR^{-1}R^{-T}=QR^{-T} }
を得る。上記の手法を用いて計算すると、次の公式を得る。
{\displaystyle (A^T)^{\dagger}=(A^{\dagger})^T. }

優決定・劣決定な連立一次方程式の解法

 この疑似逆行列は、係数行列の各列が線形独立な優決定系、または各行が線形独立な劣決定系の解法を与える。{\displaystyle A } の各列が線形独立であるとき、優決定の方程式 {\displaystyle Ax=b } は解 {\displaystyle x=A^{\dagger}b } をもつ。{\displaystyle A } の各行が線形独立であるとき、劣決定の方程式 {\displaystyle Ax=b } は任意の {\displaystyle b } に対して解をもち、{\displaystyle x=A^{\dagger}b } が解である。

Numerical Example

 これらのアイデアを、199ページと201ページの例題で用いられた {\displaystyle 3\times 2 } 型行列

{ \displaystyle A=\begin{bmatrix} -3&-4\\ 4& 6\\ 1& 1 \end{bmatrix}. }
を用いた簡単な計算例で説明する。この行列は線形独立な列をもち、QR分解は
{ \displaystyle Q=\begin{bmatrix} -0.5883&0.4576\\ 0.7845&0.5230\\ 0.1961&-0.7191 \end{bmatrix},\quad R=\begin{bmatrix} 5.0990&7.2563\\ 0&0.5883 \end{bmatrix} }
となる。{\displaystyle A } は疑似逆行列をもち、
{ \displaystyle A^{\dagger}=R^{-1}Q^T=\begin{bmatrix} -1.2222&-1.1111&1.7778\\ 0.7778&0.8889&-1.2222 \end{bmatrix}. }
となる。我々は疑似逆行列を用いて {\displaystyle b=(1,-2,0) } のとき優決定な方程式 {\displaystyle Ax=b } が解をもつかを調べることができ、もしも解をもつならばその解を求めることができる。{\displaystyle x=A^{\dagger}(1,-2,0)=(1,1) } を計算し {\displaystyle Ax=b } が成り立つかどうかを調べればよい。いま、{\displaystyle Ax=b } が成立するので、{\displaystyle x }{\displaystyle Ax=b } の唯一の解である。

VMLS 10.4 QR分解

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

10.4 QR分解

正規直交列を持つ行列

グラム行列の応用として、我々は {\displaystyle n } 次元ベクトル {\displaystyle a_1,...,a_k } が正規直交であることを、行列表示を用いて次のように簡潔に示すことができる。

{\displaystyle A^T A=I }

ここで、{\displaystyle A } は列ベクトル {\displaystyle a_1,...,a_k } を持つ {\displaystyle n\times k } 型行列である。正規直交列を持つ行列に正式な名称はないが、{\displaystyle A^T A=I } を満足する正方行列は直交行列と呼ばれ、その列は正規直交基底をなす。直交行列は様々な場面に応用される。
 我々はすでに単位行列、二次元の反転・回転行列 (129ページ)、置換行列 (132ページ) といった直交行列に出会っている。

ノルム、内積、角度に関する性質

{\displaystyle m\times n } 型行列 {\displaystyle A } の各行が正規直交であるとし、{\displaystyle x }{\displaystyle y } を任意の {\displaystyle n } 次元ベクトルとする。いま、{\displaystyle z }{\displaystyle Az } に移す関数 {\displaystyle f: R^n\rightarrow R^m } を定義すると、次の性質を得る。

  • {\displaystyle ||Ax||=||x||.\quad } よって、{\displaystyle f } はノルムを保存する。
  • {\displaystyle (Ax)^T(Ay)=x^T y.\quad } {\displaystyle f } は2ベクトルの内積を保存する。
  • {\displaystyle \angle (Ax,Ay)=\angle (x,y).\quad } {\displaystyle f } はベクトル間の角度を保存する。

上記の三つの方程式において、左右のベクトルの次元が異なっていることに注意されたい。左側は {\displaystyle m } 次元、右側は {\displaystyle n } 次元である。
 これらの性質は簡単な行列の性質を用いて証明できる。まず、二つ目の性質「{\displaystyle A } の乗算は内積を保存する」から始める。

{\displaystyle \begin{eqnarray} (Ax)^T(Ay) &=& (A^T x^T)(Ay)\\ &=& x^T (A^T A)y\\ &=& x^T Iy\\ &=& x^T y. \end{eqnarray} }
一行目で、我々は転置行列の積の性質を用いた。二行目では、四つの行列を再び結合した (行ベクトル {\displaystyle x^T } と列ベクトル {\displaystyle y } を行列とみなしている)。三行目では、{\displaystyle A^T A=I } を用いた。最後に、{\displaystyle Iy=y } を用いた。
 二つ目の性質から、我々は一つ目の性質を導くことができる。{\displaystyle y=x } とおくと {\displaystyle (Ax)^T(Ax)=x^T x } となり、両辺の平方根をとると {\displaystyle ||Ax||=||x|| } が得られる。三つ目の角度の保存は、一つ目と二つ目の性質から得られる。
{\displaystyle \angle(Ax,Ay)=arccos(\frac{(Ax)^T(Ay)}{||Ax|| ||Ay||})=arccos(\frac{x^T y}{||x|| ||y||})=\angle(x,y). }

QR分解

我々は {\displaystyle {\S}5.4 } で示したグラム-シュミットの正規直交化法*1 を行列を用いて簡潔に表現することができる。{\displaystyle n\times k } 型行列 {\displaystyle A } の各列 {\displaystyle a_1,...,a_k } は互いに線形独立であるとする。独立な次元の非対称性により、{\displaystyle A } は縦長の行列となる。つぎに、{\displaystyle n } 次元ベクトル {\displaystyle a_1,...,a_k } にグラム-シュミットの正規直交化法を適用したベクトル {\displaystyle q_1,...,q_k } を列ベクトルにもつ {\displaystyle n\times k } 型行列 {\displaystyle Q } を定義する。{\displaystyle q_1,...,q_k } の正規直交性は行列表示で {\displaystyle Q^T Q=I } と表現できる。我々は {\displaystyle a_i }{\displaystyle q_i } の関係を次のような方程式

{\displaystyle a_i=(q_1^T a_i)q_1+\cdots+(q_{i-1}^T a_i)q_{i-1}+||\tilde{q}_i||q_i }
で表すことができる。{\displaystyle \tilde{q}_i } はグラム-シュミットの正規直交化法のはじめの操作で
{\displaystyle a_i=(R_{1i}q_1+\cdots+R_{ii}a_i)q_i }
として得られるベクトルである。ここで、{\displaystyle i < j } において {\displaystyle R_{ij}=q_i^T a_j }{\displaystyle R_{ii}=||\tilde{q}_i|| } である。{\displaystyle i > j } において {\displaystyle R_{ij}=0 } と定義することで、我々は上記の方程式を簡潔な行列表示で次のように表すことができる。
{\displaystyle A=QR }
これは行列 {\displaystyle A } を二つの行列 {\displaystyle Q }{\displaystyle R } の積で表すため、QR分解 (QR factorization) と呼ばれる。
 {\displaystyle n\times k } 型行列 {\displaystyle Q } は正規直交な列をもち、{\displaystyle k\times k } 型行列 {\displaystyle R } は正の対角成分をもつ上三角行列である。{\displaystyle A } が線形独立な列をもつ正方行列であるとき、{\displaystyle Q } は直交行列であり、QR分解は {\displaystyle A } を二つの正方行列の積で表現する。
 QR分解における行列 {\displaystyle Q }{\displaystyle R } の性質はグラム-シュミットの正規直交化法から直接導かれる。{\displaystyle Q^T Q=I } はベクトル {\displaystyle q_1,...,q_i } の正規直交性から得られる。また、{\displaystyle A } の各列ベクトル {\displaystyle a_i }{\displaystyle q_1,...,q_i } の線形結合であるため、行列 {\displaystyle R } は上三角行列となる。
 グラム-シュミットの正規直交化法はQR分解の唯一のアルゴリズムではない。他にもいくつかのQR分解のアルゴリズムが存在し、それらは丸め誤差が存在する場合はより信頼性が高い (これらのQR分解の手法では {\displaystyle A } の列を処理する順番が変わることがある)。

スパースQR分解

 行列 {\displaystyle A } が疎行列 (sparse matrix)*2 であるとき、これを効率的に扱ういくつかのQR分解のアルゴリズムがある。このとき、行列 {\displaystyle Q } は一般の {\displaystyle nk } 個の要素を持つ {\displaystyle n\times k } 型行列とよりも要求メモリ量が少ない特別なフォーマットで記憶される。これらのスパースQR分解の flop count*3 もまた {\displaystyle 2nk^2 } より少ない。

*1:グラム-シュミットの正規直交化法の説明はこのブログが最高にわかりやすい。

*2:成分の殆どが零である行列。

*3:この flop は flip-flop のことでしょうか。わかりませんでした。

レアジョブ 実用英会話 6-1-2 値引き交渉

www.rarejob.com

vocabulary

rip someone off: ぼったくる

If someone rips you off, they cheat you by charging too much money for something or by selling you something that is broken or damaged.
Rip off definition and meaning | Collins English Dictionary

The car dealer ripped me off.

the best someone can do: 買い手が支払える最高金額、または売り手が提示できる最低金額。
Is 25,000 yen the best you can do?

his/her last offer: 交渉における売り手、買い手のどうしても譲れない金額。
Is 22,000 yen your last order?

Pronunciation

語尾の t と語頭の y の連結

the best you can do -> the / bes-chu / can do

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:テキストを(略

VMLS 12.1 最小二乗法 その一

こんにちは。ごるごです。

研究室の宿題で線形代数を勉強しなければならないので、ついでにこのブログで勉強の記録も付けていきたいと思います。テキストはこちらになります。

web.stanford.edu

基本的にはテキストをざっくりと翻訳していく形になるかと思います。ところどころ日本語があやしい箇所がありますがご容赦ください(できればコメントで添削してほしい)。また、諸事情によりChapter 12のLeast Squaresから始めます。

それでは、スタート!

Chapter 12 Least squares

 この章では、連立一次方程式の誤差の二乗和を最小化することで、over-determined*1連立方程式の近似解を求める強力な手法を学ぶ。その手法と、後の章で記載されるいくつかの拡張は幅広い分野に応用されている。最小二乗法は19世紀にガウスルジャンドル二人の数学者によって独立に発見された。

12.1 Least squares problem

 {\displaystyle m\times n} 型の係数行列 {\displaystyle A} が縦長であるとき、連立方程式{ \displaystyle Ax=b } と表され、{\displaystyle b} が {\displaystyle m} 次元ベクトルであるので、この連立方程式は over-determined となる。すなわち、方程式の数 {\displaystyle m} が選択できる変数の数 {\displaystyle n} よりも多い。これらの方程式は、{\displaystyle b}{\displaystyle A} の各列の線形結合であるときのみ解をもつ。
 しかし、ほとんどの {\displaystyle b} において、{ \displaystyle Ax=b } を満たす {\displaystyle n} 次元ベクトル {\displaystyle x} は存在しない。妥協案として、我々は残差 { \displaystyle r=Ax-b } を最小化する {\displaystyle x} を探すことにする。つまり、残差のノルム { \displaystyle ||Ax-b|| } を最小化するということである。もし残差ベクトルが小さくなるなら、{ \displaystyle Ax\approx b } であると言える(いくつかの本では残差は { \displaystyle b-Ax } と定義されるが、{ \displaystyle ||Ax-b||=||b-Ax|| } であるため差し支えない)。
 残差のノルムを最小化することと残差の二乗を最小化することは同義であるため、

{ \displaystyle \begin{equation}||Ax-b||^2=||r||^2=r_1^2+\cdots+r_m^2\end{equation} }
により残差の二乗和を最小化できる。すべての可能な {\displaystyle x} から { \displaystyle ||Ax-b||^2 } を最小化する {\displaystyle n} 次元ベクトル { \displaystyle \hat{x} } を求める問題を、最小二乗法(least squares problem)という。最小二乗法は次のような表記
{ \displaystyle minimize\quad ||Ax-b||^2\qquad (12.1) }
により表され、(12.1)はこれを満たす {\displaystyle x} を求めることを意味する。行列 {\displaystyle A} とベクトル {\displaystyle b} を(12.1)のデータと呼ぶ。最小化される量 { \displaystyle ||Ax-b||^2 } を、最小二乗法(12.1)の目的関数(objective function)という。(12.1)は線形最小二乗法(linear least squares)と呼ばれることがある。残差 {\displaystyle r}{\displaystyle x} のアフィン変換であることを強調したい場合や、残差 {\displaystyle r}{\displaystyle x} の任意の関数である非線形最小二乗法と区別したい場合に用いられる。
 すべての {\displaystyle x}{ \displaystyle ||A\hat{x}-b||^2\leq||Ax-b||^2 } を満たすどのようなベクトル {\displaystyle \hat{x}} も最小二乗法(12.1)の解である。そのようなベクトルを { \displaystyle ||Ax-b||^2 } の最小二乗解(least squares approximate solution)と呼ぶ。ここで、{ \displaystyle Ax=b } の近似解 {\displaystyle \hat{x}} が { \displaystyle A\hat{x}=b } を満たさないことに注意する。{\displaystyle \hat{x}} は単に残差のノルムを最小化したものにすぎない。「{\displaystyle \hat{x}}{ \displaystyle Ax=b } の最小二乗法的に解く」などという紛らわしい説明を使う本もあるが、一般的に、最小二乗解 {\displaystyle \hat{x}} は等式 { \displaystyle Ax=b } を解けないことを強調しておく。
 (我々が元々の残差のノルムと呼ぶところの) { \displaystyle ||Ax-b||^2 } が小さいとき、{\displaystyle \hat{x}}{ \displaystyle Ax=b } を近似的に解けると言える。つまり、もしもある  { \displaystyle n } 次元ベクトル  { \displaystyle x } が  { \displaystyle Ax=b } を満足するならば、残差のノルムはゼロであり、最小二乗解となる。
 データフィッティングへの応用(次章のトピックである)で典型的に用いられる最小二乗法(12.1)の他の名称は回帰(regression)である。最小二乗解 {\displaystyle \hat{x}} はベクトル {\displaystyle b} を {\displaystyle A} の各列に回帰させた結果である。

列の解釈

{\displaystyle A} の各列が {\displaystyle m} 次のベクトルであるとき、最小二乗法(12.1)は {\displaystyle m} 次ベクトル {\displaystyle b} に最も近い各列の線形結合を求める問題となる。つまり、ベクトル {\displaystyle x} は係数を与える。

{ \displaystyle ||Ax-b||^2=||(x_1 a_1 +\cdots+x_n a_n)-b||^2. }
{\displaystyle \hat{x}} が最小二乗解であるとき、ベクトル
{ \displaystyle A\hat{x}=\hat{x}_1 a_1+\cdots+\hat{x}_n a_n}
は、すべてのベクトル { \displaystyle a_1,...,a_n } の線形結合の中で、最もベクトル { \displaystyle b } に近づく。

行の解釈

{ \displaystyle A} の各行が { \displaystyle n} 次の行ベクトル { \displaystyle \tilde{a}^T_1,...,\tilde{a}^T_n } であるとすると、残差の成分は次のように与えられる。

{ \displaystyle r_i=\tilde{a}^T_i x-b_i,\quad i=1,...,m. }
最小二乗法の目的関数は
{ \displaystyle ||Ax-b||^2=(\tilde{a}^T_1 x-b_1)^2+\cdots+(\tilde{a}^T_m x-b_m)^2, }

つまり、{ \displaystyle m} 本のスカラーの連立一次方程式における残差の二乗和である。我々の目的がすべての残差を小さくする { \displaystyle x} を選ぶことであるならば、この残差の二乗和を最小化することは道理にかなった解釈である。

Example

次のようなデータをもつ最小二乗法を考える。

{ \displaystyle \begin{bmatrix} 2&0\\-1&1\\0&2 \end{bmatrix} ,\quad \begin{bmatrix} 1\\0\\-1\end{bmatrix}. }
{ \displaystyle Ax=b} の二変数に対して over-determined な三本の方程式の組
{ \displaystyle 2x_1=1,\quad -x_1+x_2=0,\quad 2x_2=-1}
は解を持たない(一つ目の方程式からは { \displaystyle x_1=1/2}、三つ目の方程式からは { \displaystyle x_2=-1/2} が得られるが、二つ目の方程式を満たさない)。相当する最小二乗法は
{ \displaystyle minimize\quad (2x_1-1)^2+(-x_1+x_2)^2+(2x_2+1)^2 }
である。この最小二乗法は次章で紹介する手法を用いることで解ける(または、単純に計算する)。その唯一の解は {\displaystyle \hat{x}=(1/3,-1/3) } である。最小二乗法解 {\displaystyle \hat{x} } は等式 {\displaystyle Ax=b } を満たさない。その残差は
{\displaystyle \hat{r}=A\hat{x}-b=(-1/3,-2/3,1/3) }
であり、二乗和は {\displaystyle ||A\hat{x}-b||^2=2/3 } である。この近似解と、先ほどの {\displaystyle Ax=b } の一つ目と二つ目の方程式の(厳密な)解である {\displaystyle \hat{x}=(1/2,-1/2) } とを比較してみる。残差は
{\displaystyle \hat{r}=A\hat{x}-b=(0,-1,0) }
であり、二乗和は {\displaystyle ||A\hat{x}-b||^2=1 } である。
 行の解釈は我々に
{ \displaystyle (1/3)\begin{bmatrix} 2\\-1\\0 \end{bmatrix} +(-1/3) \begin{bmatrix} 0\\1\\2 \end{bmatrix}=\begin{bmatrix} 2/3\\-2/3\\-2/3 \end{bmatrix} }
{\displaystyle b } に最も近い {\displaystyle A } の各行の線形結合であることを教えてくれる。
 図 12.1 は {\displaystyle x=(x_1,x_2) } に対する目的関数 {\displaystyle ||A\hat{x}-b||^2 } の値を示している。また、{\displaystyle ||A\hat{x}-b||^2=2/3 } のときの最小二乗解 {\displaystyle \hat{x} } 黒点で示している。曲線は目的関数の値が {\displaystyle ||A\hat{x}-b||^2+1, ||A\hat{x}-b||^2+2, \cdots } の場合の点 {\displaystyle x } を表している。
f:id:gorgonzolax:20210423112741p:plain
Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

次回→VMLS 12.2

*1:Over-determinedとは、連立一次方程式において方程式の数が未知数の数より多い状態のこと。これは、連立方程式{ \displaystyle Ax=b } のような行列表示で表したとき、係数行列 {\displaystyle A} が縦長の行列であることを意味する。Over-determined な連立方程式は解が係数行列の線形結合で表される場合を除き解くことができない。

再稼働

どうも。ごるごです。

 

この度、数年間放置していたこのブログを再稼働させることにしました。

理由は

 

noteでTeX記法が使えない!

 

私は2020年に無事高専を卒業して僻地大学へ編入しました。そして、

「今度こそ大学生活や勉強したことをブログに書いていこう!そしていま流行りのnoteを使おう!」

と思ったのですが、なんとnoteではTeXが使えないのです。これでは数式を美しく表示できない......

 

このような経緯ではてブを使うためだけにアカウントを作ったはてなに戻ってきたという次第です。

 

というわけで、次回は早速TeX記法を使って線形代数の記事を執筆したいと思います。

改めてよろしくお願いします。