最小二乗法さいしょうにじょうほうleast squares methodの基本きほん

1導入どうにゅう

この講義こうぎで重要じゅうようなのは、最小二乗法さいしょうにじょうほうleast squares methodは「解かいが存在そんざいしない方程式ほうていしきを無理むりに解とく」方法ほうほうではなく、右辺うへんright-hand sideを列空間れつくうかんcolumn spaceへ射影しゃえいprojectionする方法ほうほうだということである。

$$Ax=b$$Ax=b が解かいを持もつのは、$$b$$b が $$A$$A の列空間れつくうかんcolumn spaceに属ぞくする場合ばあいである。測定値そくていちを含ふくむ問題もんだいでは、$$b$$b が列空間れつくうかんcolumn spaceから少すこし外はずれることが多おおい。そのときは、$$Ax$$Ax を $$b$$b に最もっとも近ちかい列空間れつくうかんcolumn spaceの点てんに設定せっていする。

2用語ようごと定義ていぎ

最小二乗法さいしょうにじょうほうLeast squares とは、行列ぎょうれつmatrix $$A$$A とベクトル $$b$$b に対たいして

を最小化さいしょうかする $$x$$x を求もとめる方法ほうほうである。

残差ざんさResidual とは、

で定義ていぎされる誤差ごさベクトルである。

正規方程式せいきほうていしきNormal equations とは、実数じっすうreal number行列ぎょうれつmatrixで

と表あらわされる方程式ほうていしきである。

複素ふくそcomplexの場合ばあいは、$$A^T$$A^T を共役転置きょうやくてんちconjugate transpose $$A^{*}$$A^* に置おき換かえ、

を用もちいる。

3方針ほうしん

$$Ax$$Ax は $$A$$A の列空間れつくうかんcolumn spaceに属ぞくする。したがって $$\parallel Ax-b\parallel$$\|Ax-b\| を最小化さいしょうかするには、$$b$$b を列空間れつくうかんcolumn spaceへ直交射影ちょっこうしゃえいorthogonal projectionすればよい。最良近似さいりょうきんじ $$Ax$$Ax と誤差ごさ $$b-Ax$$b-Ax は直交ちょっこうorthogonalするため、そこから正規方程式せいきほうていしきが導みちびかれる。

4直感的ちょっかんてきな説明せつめい

列空間れつくうかんcolumn spaceを 1 つの平面へいめんとみなす。$$b$$b がその平面へいめんの外そとにあるなら、$$Ax=b$$Ax=b は成立せいりつしない。しかし平面へいめんの中なかで $$b$$b に最もっとも近ちかい点てんは存在そんざいする。その点てんが $$Ax$$Ax であり、垂直成分すいちょくせいぶんとして分離ぶんりされる誤差ごさが残差ざんさである。

この垂直すいちょくという条件じょうけんが計算けいさんへ変換へんかんされると、$$A^T(b-Ax)=0$$A^T(b-Ax)=0 となる。

なぜ列空間れつくうかんcolumn spaceへ射影しゃえいprojectionするのかは、$$Ax$$Ax の形かたちから決定けっていされる。$$x$$x をどのように選択せんたくしても、候補こうほとなる左辺さへんleft-hand side $$Ax$$Ax は $$A$$A の列れつcolumnの線型結合せんけいけつごうlinear combinationである。したがって到達可能とうたつかのうな右辺うへんright-hand sideの集合しゅうごうsetは $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) に限定げんていされる。$$b$$b がそこに属ぞくしない場合ばあい、問題もんだいは「$$b$$b に最もっとも近ちかい $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) の点てんを選択せんたくする」ことへ変換へんかんされる。

最近点さいきんてん $$\hat{b}$$\hat b では、残差ざんさ $$r=b-\hat{b}$$r=b-\hat b が列空間れつくうかんcolumn spaceのどの方向ほうこうにも成分せいぶんcomponentを持もたない。もし列空間れつくうかんcolumn spaceの方向ほうこうに残差ざんさの成分せいぶんcomponentが残存ざんそんしていれば、その方向ほうこうへ $$\hat{b}$$\hat b を微小びしょうに移動いどうして距離きょりを短縮たんしゅくできるためである。したがって

という直交分解ちょっこうぶんかいが最小二乗法さいしょうにじょうほうleast squares methodの幾何学的内容きかがくてきないようである。

5厳密げんみつな説明せつめい

5.11. 列空間れつくうかんcolumn spaceへの射影しゃえいprojection

$$A$$A の列空間れつくうかんcolumn spaceを $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) とする。$$Ax$$Ax は常つねに $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) に属ぞくする。最小二乗解さいしょうにじょうかいでは、$$Ax$$Ax が $$b$$b の $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) への直交射影ちょっこうしゃえいorthogonal projectionになる。

したがって残差ざんさ

は列空間れつくうかんcolumn spaceに直交ちょっこうorthogonalする。

5.22. 直交条件ちょっこうじょうけんから正規方程式せいきほうていしきへ

$$A$$A の列れつcolumnを $$a_1,\text{[PARSE ERROR: Undefined("Command("dots")")]},a_n$$a_1,\dots,a_n とする。$$r$$r が列空間れつくうかんcolumn spaceに直交ちょっこうorthogonalするとは、

である。これは行列ぎょうれつmatrixで

と表現ひょうげんできる。$$r=b-Ax$$r=b-Ax を代入だいにゅうすると、

すなわち

を得える。これが正規方程式せいきほうていしきである。

複素ふくそcomplexの場合ばあいは、列れつcolumnとの直交条件ちょっこうじょうけんは同おなじく $$⟨r,a_j⟩=0$$\langle r,a_j\rangle=0 であるが、行列ぎょうれつmatrixでは $$A^{*}r=0$$A^*r=0 と書かく。したがって

すなわち

を得える。ここで $$A^{*}$$A^* は共役転置きょうやくてんちconjugate transposeであり、複素内積ふくそないせきcomplex inner productに対たいする随伴ずいはんadjointとして現あらわれる。

5.33. 一意性いちいせい

$$A$$A の列れつcolumnが一次独立いちじどくりつlinear independenceなら、$$A^{T}A$$A^T A は可逆かぎゃくinvertibleである。この場合ばあい、最小二乗解さいしょうにじょうかいは

で一意いちいに決定けっていされる。列れつcolumnが一次従属いちじじゅうぞくlinear dependenceなら、射影しゃえい $$\hat{b}$$\hat b は一意いちいであるが、係数ベクトルcoefficient vector $$x$$x は一意いちいとは限かぎらない。つまり、複数ふくすうの $$x$$x が同おなじ $$Ax=\hat{b}$$Ax=\hat b を与あたえうる。その場合ばあい、最小さいしょうノルム解かいを選択せんたくする道具どうぐが擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixである。

5.44. 射影行列しゃえいぎょうれつ

$$A$$A が列満階数れつまんかいすうなら、列空間れつくうかんcolumn spaceへの直交射影ちょっこうしゃえいorthogonal projectionは

で表現ひょうげんされる。このとき

であり、$$\hat{b}$$\hat b が $$b$$b の列空間れつくうかんcolumn spaceへの射影しゃえいprojection、$$r$$r が直交残差ちょっこうざんさである。さらに

が成立せいりつするため、$$P$$P は「一度いちど射影しゃえいprojectionすれば再度さいど射影しゃえいprojectionしても変化へんかしない」対称たいしょうな射影行列しゃえいぎょうれつである。複素ふくそcomplexの場合ばあいは $$A^T$$A^T を $$A^{*}$$A^* に置換ちかんし、

を用もちいる。

6具体例ぐたいれい

とする。$$Ax$$Ax は全成分ぜんせいぶんが $$x$$x のベクトルであり、$$b$$b を定数ていすうで近似きんじする問題もんだいである。正規方程式せいきほうていしきは

すなわち

である。したがって $$x=\frac{7}{3}$$x=\frac73 となる。これは $$1,2,4$$1,2,4 の平均へいきんであり、定数ていすうで最良さいりょうに近似きんじする値あたいになる。

点てん $$(0,1),(1,2),(2,2)$$(0,1),(1,2),(2,2) を $$y=\alpha +\beta t$$y=\alpha+\beta t で近似きんじする直線当ちょくせんあてはめでは、

と書かく。このとき

であり、解とくと

を得える。したがって最良近似直線さいりょうきんじちょくせんは

であり、残差ざんさは $$A$$A の 2 本ほんの列れつcolumnに直交ちょっこうorthogonalする。

7別べつの観点かんてん

幾何的きかてきには、最小二乗法さいしょうにじょうほうleast squares methodは点てんを部分空間ぶぶんくうかんsubspaceへ射影しゃえいprojectionする方法ほうほうである。統計的とうけいてきには、観測値かんそくちと予測値よそくちの差さの 2 乗和じょうわを最小化さいしょうかする方法ほうほうである。

8定理ていり：存在そんざいと射影しゃえいによる特徴とくちょうづけ

$$A\in R^{m\times n}$$A\in\mathbb R^{m\times n} と $$b\in R^m$$b\in\mathbb R^m に対たいして、$$\parallel Ax-b\parallel$$\|Ax-b\| を最小さいしょうにする $$x$$x は存在そんざいする。$$x$$x は一意いちいとは限かぎらないが、最良近似さいりょうきんじ $$\hat{b}=Ax$$\hat b=Ax は一意いちいで、$$b$$b の $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) への直交射影ちょっこうしゃえいorthogonal projectionである。

$$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) が有限次元ゆうげんじげんの部分空間ぶぶんくうかんsubspaceなので、

と直交分解ちょっこうぶんかいできる。$$Ax=\hat{b}$$Ax=\hat b とすれば、任意にんいの $$y$$y について

である。

9階数かいすうrankが落おちる場合ばあいと最小さいしょうノルム解かい

$$A$$A の列れつcolumnが一次従属いちじじゅうぞくlinear dependenceなら、$$A^{T}A$$A^TA は可逆かぎゃくinvertibleでない。このとき正規方程式せいきほうていしきは複数ふくすうの解かいを持もつことがあるが、どの解かいも同おなじ射影しゃえい $$\hat{b}$$\hat b を与あたえる。一意いちいな代表元だいひょうげんとして、$$\ker A$$\ker A 方向ほうこうの成分せいぶんを持もたない最小さいしょうノルム解かいを選えらぶ。この選択せんたくを擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixが与あたえる。

10数値計算上すうちけいさんじょうの注意ちゅうい

理論上りろんじょうは正規方程式せいきほうていしきや射影行列しゃえいぎょうれつで最小二乗解さいしょうにじょうかいを記述きじゅつできる。一方いっぽうで数値計算すうちけいさんでは、$$A^{T}A$$A^TA を直接ちょくせつ構成こうせいすると条件数じょうけんすうが悪化あっかする場合ばあいがある。そのため、実装じっそうでは QR 分解ぶんかいや特異値分解とくいちぶんかいsingular value decompositionSVDを用もちいることが標準的ひょうじゅんてきである。

11判定基準はんていきじゅん

• $$Ax=b$$Ax=b が過剰かじょうな条件じょうけんを持もち、厳密解げんみつかいが存在そんざいしない場合ばあいは最小二乗法さいしょうにじょうほうleast squares methodを検討けんとうする。
• 列空間れつくうかんcolumn spaceへの最近点さいきんてんを求もとめる問題もんだいでは、残差ざんさの直交条件ちょっこうじょうけんを立式りっしきする。
• 列れつcolumnが一次独立いちじどくりつlinear independenceなら $$A^{T}A$$A^TA の可逆性かぎゃくせいを利用りようする。
• 列れつcolumnが一次従属いちじじゅうぞくlinear dependenceなら、一意いちいな射影しゃえいと非一意ひいちいになりうる係数ベクトルcoefficient vectorを区別くべつする。

12どこまで成立せいりつするか

実数じっすうreal numberの標準内積ひょうじゅんないせきでは $$A^T$$A^T を用もちいる。複素ふくそcomplexの場合ばあいは共役転置きょうやくてんち $$A^{*}$$A^* を用もちい、正規方程式せいきほうていしきは $$A^{*}Ax=A^{*}b$$A^*Ax=A^*b となる。列れつcolumnが一次従属いちじじゅうぞくlinear dependenceの場合ばあい、射影しゃえいprojection $$\hat{b}$$\hat b は一意いちいであるが、係数けいすうcoefficient $$x$$x は一意いちいとは限かぎらない。

数値計算すうちけいさんでは、$$A^{T}A$$A^TA を明示的めいじてきに作つくらない方法ほうほうを選えらぶことが多おおい。

13定理ていり：最小二乗解さいしょうにじょうかいの存在そんざいと直交射影ちょっこうしゃえい

$$A\in R^{m\times n}$$A\in\mathbb R^{m\times n} と $$b\in R^m$$b\in\mathbb R^m に対たいして、$$\parallel Ax-b\parallel$$\|Ax-b\| を最小さいしょうにする $$x$$x は常つねに存在そんざいする。ただし $$x$$x が一意いちいであるとは限かぎらない。一意いちいなのは、最良近似さいりょうきんじ $$\hat{b}=Ax$$\hat b=Ax、すなわち $$b$$b の $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) への直交射影ちょっこうしゃえいorthogonal projectionである。

理由りゆうは、$$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) が有限次元ゆうげんじげんの部分空間ぶぶんくうかんsubspaceなので、$$b$$b は

と直交分解ちょっこうぶんかいできるからである。$$Ax$$Ax が $$\hat{b}$$\hat b に等ひとしいような $$x$$x を選えらべば、任意にんいの $$y$$y について

である。ここで $$Ay-\hat{b}\in \mathrm{Col}\left(A\right)$$Ay-\hat b\in\operatorname{Col}(A) と $$r\perp \mathrm{Col}\left(A\right)$$r\perp\operatorname{Col}(A) を使つかった。この証明しょうめいは、最小二乗法さいしょうにじょうほうが微分計算びぶんけいさんではなく直交分解ちょっこうぶんかいorthogonal decompositionに基もとづくことを示しめしている。

14階数落かいすうおちの場合ばあいと最小さいしょうノルム解かい

$$A$$A の列れつcolumnが一次従属いちじじゅうぞくlinear dependenceなら、$$A^{T}A$$A^TA は可逆かぎゃくでない。このとき正規方程式せいきほうていしき

は解かいを複数ふくすう持もつことがある。複数ふくすうの解かいは同おなじ $$Ax=\hat{b}$$Ax=\hat b を与あたえ、差さは $$\ker A$$\ker A に属ぞくする。したがって、代表解だいひょうかいを一意いちいに選えらぶには $$\ker A$$\ker A 方向ほうこうの成分せいぶんを持もたない最小さいしょうノルム解かいを選えらぶ。この選択せんたくを擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixが実現じつげんする。

15計算例けいさんれい：2 変数へんすうの直線近似ちょくせんきんじ

点てん $$(0,1),(1,2),(2,2)$$(0,1),(1,2),(2,2) を $$y=\alpha +\beta t$$y=\alpha+\beta t で近似きんじする。行列ぎょうれつで書かくと

である。正規方程式せいきほうていしきは

より

これを解とくと

である。したがって最良近似直線さいりょうきんじちょくせんは

である。残差ざんさは $$b-Ax$$b-Ax であり、$$A$$A の 2 本ほんの列れつcolumnに直交ちょっこうorthogonalする。

16数値計算すうちけいさんでの実務的じつむてきな注意ちゅうい

$$A^{T}A$$A^TA を作つくると条件数じょうけんすうは概おおむね二乗にじょうされる。つまり、もとの $$A$$A が少すこし悪条件あくじょうけんなだけでも、$$A^{T}A$$A^TA は大おおきく不安定ふあんていになりうる。理論りろんの証明しょうめいでは正規方程式せいきほうていしきが本質ほんしつを示しめすが、数値計算すうちけいさんでは QR 分解ぶんかいや特異値分解とくいちぶんかいsingular value decompositionSVDを使つかうのが安全あんぜんである。

17最終形さいしゅうけい

18一言ひとことでいうと

• 最小二乗法さいしょうにじょうほうleast squares methodは、$$b$$b を列空間れつくうかんcolumn spaceへ直交射影ちょっこうしゃえいorthogonal projectionし、残差ざんさを列空間れつくうかんcolumn spaceに直交ちょっこうorthogonalさせる方法ほうほうである。

19演習えんしゅうリンク

20関連かんれんリンク