VMLS 14.1 分類

関連記事→線形代数 カテゴリーの記事一覧 - ごるごの勉強記録
テキスト→Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

Chapter 14 Least squares classification

 この章では、あるモデルを (13章で扱った数値とは対照的に) 結果が真または偽のような値をとるデータにフィッティングする問題を考える。最小二乗法はこのような問題にも用いることができる。

14.1 Classification

 13章のデータフィッティング問題の目的は、{ \displaystyle n } 次元ベクトル { \displaystyle x } をもとに (スカラーの) 数値 { \displaystyle y } を再現することであった。分類問題 (classification problem) では、結果や従属変数 { \displaystyle y } は変数のうち限定された値のみをとり、この理由から { \displaystyle y } はラベル、または統計学では categorical と呼ばれる。最も単純な場合、{ \displaystyle y } は真か偽か、もしくはスパムかスパムでないかというような二値のみをとる。これは二項分類 (two-way classification) 問題や二値分類 (binary classification) 問題、ブーリアン分類 (boolean classification) 問題と呼ばれる。我々はまず二項分類から始めることにする。
 { \displaystyle y } は、真を { \displaystyle y = +1 }、偽を { \displaystyle y=-1 } のような実数に符号化することができる ({ \displaystyle y=+1 }{ \displaystyle y=0 } や、任意の異なる二値のペアを用いて { \displaystyle y } を符号化できる)。実数値データフィッティングでは、おおよその関係 { \displaystyle y\approx f(x),\quad f:\mathbf{R}^n\rightarrow (-1,+1) } が成り立つと仮定する(この表記は { \displaystyle f } が変数として { \displaystyle n } 次元ベクトルをとり、出力として { \displaystyle  +1}{ \displaystyle -1 } を返すことを示す)。我々のモデルは { \displaystyle \hat{y}=\hat{f}(x) } の形をもち、{ \displaystyle \hat{f}:\mathbf{R}^n\rightarrow (-1,+1) } である。モデル { \displaystyle \hat{f} }{ \displaystyle n } 次元ベクトルを { \displaystyle \hat{f}(x)=+1 }{ \displaystyle \hat{f}(x)=-1 } に分類するため分類器と呼ばれる。実数値データフィッティングでは、いくつかの観測値を用いて分類器 { \displaystyle \hat{f} } を構成できる。

Examples.

 二項分類は幅広く応用されている。

  • 電子メールのスパム検出

 ベクトル { \displaystyle x } は電子メールのメッセージの特徴を格納している。電子メールの文面の単語数や感嘆符の数、大文字の単語や送信者に関連した特徴などである。メッセージがスパムである場合、出力は { \displaystyle +1 }、そうでなければ { \displaystyle -1 } となる。分類器を作るために用いられるデータはいくつかのメッセージをはっきりとゴミ箱に移動したユーザーからもたらされる。

  • 詐欺の検出

 ベクトル { \displaystyle x } はクレジットカードの利用者の特徴、例えば月平均の利用額や一週間の支払額の中央値、商品の種類別の利用回数、平均の預金残高等を与える。同様に、特定の取引に関する特徴も与える。出力 { \displaystyle y } は取引が詐欺の場合は { \displaystyle +1 }、そうでなければ { \displaystyle -1 } となる。分類器を作るために用いられるデータは後に詐欺だと判明した取引と公正な取引の過去のデータである。

  • ブール型文書分類

 ベクトル { \displaystyle x } は文書の単語カウント (またはヒストグラム) ベクトルであり、出力 { \displaystyle y } は文書がいくつかの特定の話題を含む場合 (政治等) に { \displaystyle +1 } となり、そうでなければ { \displaystyle -1 } となる。分類器を作るために用いられるデータは話題のラベルがついた文書のコーパスが用いられる。

  • 疾病検出

 例は患者に対応しており、{ \displaystyle y=+1 } は患者に特定の疾病があることを意味し、{ \displaystyle y=-1 } はそうではないことを意味する。ベクトル { \displaystyle x } は患者と関連する医学的特徴、年齢や性別、検査結果、症状等を格納する。分類器を作るために用いられるデータは病院の記録や医学的研究によりもたらされる。つまり、出力は医師によって診断された結果 (疾病の有無) に関連している。

  • ディジタル受信機

 現代の電子通信システムでは、{ \displaystyle y } は送信機から受信機へ送信される (伝統的に0と1で表される) 1ビットを表す。ベクトル { \displaystyle x } は受信信号の { \displaystyle n } 個の観測結果を表す。予測器 { \displaystyle \hat{y}=\hat{f}(x) } は復調ビットと呼ばれる。通信工学では、分類器 { \displaystyle \hat{f} } は復号器または検出器と呼ばれる。復号器を作るために用いられるデータは受信機側で既知の送信されたビット列である訓練信号からもたらされる。

予測誤差

 与えられたデータ点 { \displaystyle x, y } と予測結果 { \displaystyle \hat{y}=\hat{f}(x) } に対し、以下に示す可能性のみが存在する。

  • 真かつ陽性{ \displaystyle y=+1 } かつ { \displaystyle \hat{y}=+1 }
  • 真かつ陰性{ \displaystyle y=-1 } かつ { \displaystyle \hat{y}=-1 }
  • 偽かつ陽性{ \displaystyle y=-1 } かつ { \displaystyle \hat{y}=+1 }
  • 偽かつ陰性{ \displaystyle y=+1 } かつ { \displaystyle \hat{y}=-1 }

はじめの二つの場合では予測したラベルはただしく、後の二つの場合では予測したラベルは誤りである。三番目の偽かつ陽性 またはタイプ I のエラー の場合と、四番目の偽かつ陰性 またはタイプ II のエラー の場合に注目する。これら二つのタイプのエラーを平等に扱うことができる応用範囲もあれば、どちらかのタイプのエラーを他方より重視する応用範囲もある。

誤り率と混同行列

 与えられたデータセット

{\displaystyle x^{(1)},...,x^{(N)},\quad y^{(1)},...,y^{(N)} }
とモデル { \displaystyle \hat{f} } に対して、データセットにおいて上記のそれぞれが起こる確率を計算でき、{ \displaystyle \hat{y}^{(i)} } に対応した列と { \displaystyle y^{(i)} } に対応した行をもつ { \displaystyle 2\times 2 } の分割表や混同行列 で表すことができる (これは機械学習における慣例であり、統計学では列と行が入れ替わることがある)。表14.1のように、要素は示したの4つのケースの総数を与える。対角成分は正しい推測に対応し、左上の数値は真かつ陽性の数、右下は真かつ陰性の数である。非対角成分はエラーに対応し、右上は偽かつ陰性、左下は偽かつ陽性である。4つの数の合計はデータセットのサンプル数 { \displaystyle N } である。表14.1のように行の合計と列の合計が示されることもある。

f:id:gorgonzolax:20210518215133j:plain

 様々なパフォーマンスの指標は混同行列の数値として表される。

  • 誤り率は (二種類の) エラーの合計をサンプル数で割ったもの、つまり { \displaystyle (N_{fp})+N_{fn})/N } である。
  • 真かつ陽性の確率 (感度 (sensitivity) または再現率 (recall rate) ) は { \displaystyle N_{tp}/N_p }。これは { \displaystyle \hat{y}=+1 } と正しく推定されたデータ点 { \displaystyle y=+1 } を与える。
  • 偽かつ陽性の確率 (偽陽性率 (false alarm rate) ) は { \displaystyle N_{fp}/N_p }偽陽性率は { \displaystyle \hat{y}=+1 } と間違って推定されたデータ点 { \displaystyle y=-1 } を与える。
  • 特異度 (specificity) または真かつ陰性の確率は1から偽陽性率を引いたものに等しい。つまり、 { \displaystyle N_{tn}/N_n } である。特異度は { \displaystyle \hat{y}=-1 } と正しく推定されたデータ点 { \displaystyle y=-1 } を与える。
  • 適合率 (precision) は { \displaystyle N_{tp}/(N_{tp}+N_{fp}) } であり、真と予測されたもののうち正しかったデータを指す。

良い分類器は小さな (ゼロに近い) 誤り率と偽陽性率をもち、高い (1に近い) 感度と特異度、適合率をもつ。これらの指標うちのいずれかは特定の応用先によってはより重要になる。
 サンプル数 { \displaystyle N=1266 } のうち、{ \displaystyle y=+1 } となるスパムが { \displaystyle 127 } 件含まれ、残りの { \displaystyle 1139 } 件がスパムではなく { \displaystyle y=-1 } となるEメールのデータセットに関するスパム検出器の混同行列の例を14.2に示す。このデータセットに対し、この分類器は真かつ陽性が { \displaystyle 95 } 件、真かつ陰性が { \displaystyle 1120 } 件、偽かつ陽性が { \displaystyle 19 } 件、偽かつ陰性が { \displaystyle 32 } 件である。誤り率は { \displaystyle (19+32)/1266=4.03\% } である。感度は { \displaystyle 95/127=74.8\% } (データ内のスパムのうちおよそ75%を検出することを意味する) であり、偽陽性率は { \displaystyle 19/1139=1.67\% } (スパムでないメールのうちおよそ1.7%が誤ってスパムとラベリングされることを意味する) である。

f:id:gorgonzolax:20210521000226j:plain

分類問題の検証

 分類問題において我々は誤り率、感度、偽陽性率に関心がある。そのため out-of-sample validation と cross-validation はパフォーマンスの指標や我々が知りたい指標、すなわち、誤り率や感度と偽陰性率の組などを提供する。このうちのいずれかの指標がその他の指標よりも重要視される場合もある。

次回→VMLS 14.2

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 0=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 } を表している。
Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

次回→VMLS 12.2

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