線形代数とデータサイエンス

線形代数は、データをベクトルや行列として表現し、幾何と計算を両立して扱うための共通言語である。データサイエンスは、確率・統計と最適化、そして学習モデルを通じて、行列計算を知識抽出へ接続する学問である。

参考ドキュメント

1. ギルバート・ストラング（著），松崎公紀（訳），ストラング：線形代数とデータサイエンス，近代科学社．
2. 松浦真也，主成分分析と行列の特異値分解，講義資料（PDF）．
3. 桂田祐史，信号処理とフーリエ変換：離散フーリエ変換に関する講義資料（PDF）．

第1章：線形代数の要点

本章では、データサイエンスで繰り返し現れる行列計算を、列空間・直交性・分解という3つの視点で整理する。各節の式変形は、最小二乗・次元削減・学習の更新則へそのまま接続できる形で述べるのである。

1.1　行列Aの列ベクトルを用いた行列ベクトル積 Ax

$A\in {\mathbb{R}}^{m\times n}$ の列ベクトルを $a_1,\dots ,a_n$ とし、$x\in {\mathbb{R}}^n$ の成分を $x_1,\dots ,x_n$ とすると、行列ベクトル積は

$$Ax=\sum _{j=1}^n{x}_j{a}_j$$

と表される。すなわち $Ax$ は列空間 $\mathcal{C}(A)$ の要素であり、$x$ は $a_j$ の線形結合係数である。

同じ $Ax$ を与える $x$ が一意であるためには、列ベクトルが一次独立である必要がある。一次独立でない場合、$Ax$ は同じでも $x$ は複数存在し、これは零空間 $\mathcal{N}(A)$ の存在として記述される。

同じ積を行ベクトルの側から見ると、$A$ の行ベクトルを $r_1^T,\dots ,r_m^T$ として

$$Ax=\left[\begin{array}{c}{r}_1^{T}x\\ ⋮\\ r_m^{T}x\end{array}\right]$$

である。各成分は内積であり、特徴ベクトル $x$ を「重み $r_i$ で測る」操作として理解できる。

計算量の観点では、密行列では $Ax$ に $O(mn)$ の積和が必要である。疎行列では非零要素数を $\mathrm{nnz}(A)$ として $O(\mathrm{nnz}(A))$ まで下がり、反復法や大規模学習で支配的な演算となる。

データ行列 $X$ を「各行がサンプル、各列が特徴量」と置くと、線形モデルは $Xw$ の形で予測を作る。ここで $w$ は特徴量の寄与を決める係数であり、列ベクトルの線形結合という見方は、予測が特徴量の重ね合わせであることを明確にする。

1.2　行列－行列積 AB

$A\in {\mathbb{R}}^{m\times n}$ と $B\in {\mathbb{R}}^{n\times p}$ の積 $AB$ は、線形写像の合成に対応する。$B$ の列を $b_1,\dots ,b_p$ とすると

$$AB=[A{b}_1,\dots ,A{b}_p]$$

となり、$AB$ の各列は「まず $B$ がベクトルを作り、その後 $A$ が作用する」結果である。

一方で、$A$ の行を $r_i^T$、$B$ の列を $b_j$ とすると

$$(AB{)}_{ij}=r_i^T{b}_j$$

であり、成分は内積の総和として現れる。したがって $AB$ は「$A$ の行が $B$ の列を測る」行為の集積である。

行列積は一般に可換ではなく、$AB\ne BA$ である。この非可換性は、処理の順序が意味を持つことを表し、特徴変換や学習器の合成で順序を変えると別のモデルになる理由を与える。

結合則 $(AB)C=A(BC)$ は常に成り立つため、複数の積は計算順序を選べる。数値計算では、積の順序は計算量と丸め誤差の蓄積に影響するため、行列の形状や疎性に応じて順序を決める必要がある。

ブロック行列としての理解も重要である。例えば特徴を群に分けたとき、行列積はブロックごとの相互作用を持ち、同じ式でも構造が見えると解釈や近似が容易になる。

1.3　4つの基本部分空間

行列 $A\in {\mathbb{R}}^{m\times n}$ に対し、列空間 $\mathcal{C}(A)\subset {\mathbb{R}}^m$、行空間 $\mathcal{C}(A^T)\subset {\mathbb{R}}^n$、零空間 $\mathcal{N}(A)\subset {\mathbb{R}}^n$、左零空間 $\mathcal{N}(A^T)\subset {\mathbb{R}}^m$ の4つが基本部分空間である。これらは「何が作れるか」「何が潰れるか」「何が測れないか」を同時に言語化する。

階数を $r=\mathrm{rank}(A)$ とすると、次元は

$$\dim \mathcal{C}(A)=r,\dim \mathcal{C}(A^T)=r,\dim \mathcal{N}(A)=n-r,\dim \mathcal{N}(A^T)=m-r$$

である。特に $\dim \mathcal{N}(A)=n-r$ はランク・ヌルリティ定理であり、未知数の自由度がどれだけ残るかを与える。

直交分解として

$${\mathbb{R}}^n=\mathcal{C}(A^T)\oplus \mathcal{N}(A),{\mathbb{R}}^m=\mathcal{C}(A)\oplus \mathcal{N}(A^T)$$

が成り立つ。ここで $\oplus$ は直交直和であり、互いに直交して全空間を埋めることを意味する。

最小二乗 $\underset{x}{min}\parallel Ax-b{\parallel }_2$ では、$Ax$ が $\mathcal{C}(A)$ に属するため、$b$ のうち $\mathcal{C}(A)$ に含まれない成分は残差として必ず残る。最適解では残差 $r=b-A\hat{x}$ が列空間に直交し、

$$A^T(b-A\hat{x})=0$$

となるが、これは $r\in \mathcal{N}(A^T)$ を意味する。

この4空間は、データの冗長性や同定不能性を表す。例えば特徴量が線形従属であると $\mathcal{N}(A)$ が非自明となり、回帰係数が一意でなくなることが構造として現れる。

1.4　消去と A = LU

ガウス消去は、行基本変形により $A$ を上三角へ変換し、後退代入で解を得る方法である。消去の係数を下三角行列として蓄えると

$$A=LU$$

が得られ、$L$ は対角成分が1の下三角、$U$ は上三角となる。

実際には、ピボットが0または非常に小さいと不安定になるため、行の入れ替えを行うことが多い。このとき

$$PA=LU$$

という形で置換行列 $P$ が入る。$P$ は行の順序を入れ替える直交行列の一種であり、計算の安定性を確保するための要素である。

$LU$ は「同じ $A$ に対して多くの $b$ を解く」状況で効果が大きい。$Ax=b$ を $LUx=b$ として $Ly=b$ を前進代入で解き、その後 $Ux=y$ を後退代入で解けばよい。

行列式とも関係し、$A=LU$ が成り立つなら

$$det(A)=det(L)det(U)$$

である。$L$ の対角が1なら $det(L)=1$ であり、$det(A)$ は $U$ の対角積に等しい（置換が入れば符号が変わる）。

消去は線形代数の「計算の骨格」を与えるが、同時に数値誤差の入り口でもある。したがって、分解の存在だけでなく、ピボット選択と条件数の理解が不可欠である。

1.5　直交行列と部分空間

直交行列 $Q$ は $Q^{T}Q=I$ を満たし、長さと内積を保存する。したがって $\parallel Qx{\parallel }_2=\parallel x{\parallel }_2$、$(Qx{)}^T(Qy)=x^{T}y$ が成り立ち、幾何を壊さない座標変換である。

直交基底は射影を簡潔にする。$Q\in {\mathbb{R}}^{m\times k}$ が列直交（$Q^{T}Q=I_k$）なら、$\mathrm{span}(Q)$ への直交射影行列は

$$P=Q{Q}^T$$

である。任意の $b$ に対し、射影 $Pb$ は $\mathrm{span}(Q)$ 内で $b$ に最も近い点になる。

直交化の基本手続きとしてグラム・シュミット法がある。線形独立な $a_1,\dots ,a_k$ から直交ベクトル $q_1,\dots ,q_k$ を作り、列空間の直交基底を得る。数値計算では丸め誤差の影響を考え、修正グラム・シュミットやハウスホルダー変換が用いられる。

$QR$ 分解は $A=QR$（$Q$ 直交、$R$ 上三角）であり、最小二乗を安定に解く代表的手段である。$\underset{x}{min}\parallel Ax-b{\parallel }_2=\underset{x}{min}\parallel QRx-b{\parallel }_2=\underset{x}{min}\parallel Rx-Q^{T}b{\parallel }_2$ と変形でき、上三角系へ落ちる。

部分空間の言葉で見ると、$Q$ の列は列空間の直交基底であり、$Q^{T}b$ は $b$ のその基底での座標である。したがって直交分解は、座標系の選択と射影の計算を同時に実現している。

1.6　固有値と固有ベクトル

$A\in {\mathbb{R}}^{n\times n}$ に対し $Av=\lambda v$ を満たす非零ベクトル $v$ を固有ベクトル、スカラー $\lambda$ を固有値という。固有ベクトル方向では、$A$ の作用が単なる伸縮に簡約されるため、反復作用の理解が容易になる。

もし $A$ が対角化可能なら、固有ベクトルを並べた $V$ と固有値を並べた $\mathrm{\Lambda }$ により

$$A=V\mathrm{\Lambda }{V}^{-1}$$

と書ける。このとき

$$A^k=V{\mathrm{\Lambda }}^k{V}^{-1}$$

となり、長時間挙動は $|\lambda |$ が最大のモードに支配される。

固有値は安定性とも関係する。離散時間系 $x_{t+1}=A{x}_t$ では、スペクトル半径 $\rho (A)=\underset{i}{max}|{\lambda }_i|$ が1未満なら原点へ収束し、1を超えると発散が起こり得る。

対称行列では性質が大きく良くなる。$A=A^T$ なら固有値は実数で、固有ベクトルは直交基底を作り

$$A=Q\mathrm{\Lambda }{Q}^T$$

となる。この直交性により、固有分解は数値的にも幾何的にも扱いやすい。

データ解析では、共分散行列の固有値が分散の大きさを表し、グラフラプラシアンの小固有値が連結性やクラスタ構造を表す。固有問題は「データの長期的・大域的な形」を抽出する道具として働くのである。

1.7　正定値対称行列

対称行列 $A=A^T$ が正定値であるとは、任意の $x\ne 0$ に対して

$$x^{T}Ax>0$$

が成り立つことである。このとき固有値はすべて正であり、二次形式 $x^{T}Ax$ は厳密に凸である。

正定値性は内積を定める。$A$ が正定値なら

$$⟨x,y{⟩}_A=x^{T}Ay$$

は内積になり、$\parallel x{\parallel }_A=\sqrt{x^{T}Ax}$ はノルムになる。すなわち正定値行列は「計る物差し」を与える。

数値計算ではコレスキー分解

$$A=L{L}^T$$

が重要である。$L$ は下三角であり、$LU$ よりも高速かつ安定に解ける状況が多い。最小二乗の正規方程式で $A^{T}A$ が正定値なら、コレスキーで解く選択肢が生まれる。

反復法の立場では、共役勾配法は正定値対称系 $Ax=b$ に対して強い性質を持つ。収束は条件数 ${\kappa }_2(A)={\lambda }_{max}/{\lambda }_{min}$ に支配され、前処理は実質的に条件数を改善する操作である。

統計では共分散行列が半正定値である。データが十分に独立で分散が正なら正定値に近づき、逆行列（精度行列）が意味を持つ。逆行列は部分相関や線形予測に現れ、線形代数が確率の構造へ踏み込む入り口となる。

1.8　特異値分解による特異値と特異ベクトル

任意の $A\in {\mathbb{R}}^{m\times n}$ は特異値分解

$$A=U\mathrm{\Sigma }{V}^T$$

を持つ。$U$ と $V$ は直交行列、$\mathrm{\Sigma }$ は非負の特異値 ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$ を対角に持つ（長方形では対角以外0）行列である。

特異値分解は、対称固有分解と密接に関係する。実際に

$$A^{T}A=V{\mathrm{\Sigma }}^2{V}^T,A{A}^T=U{\mathrm{\Sigma }}^2{U}^T$$

となり、$V$ は $A^{T}A$ の固有ベクトル、$U$ は $A{A}^T$ の固有ベクトルである。したがって、特異値は $A^{T}A$ の固有値の平方根である。

幾何的には、$V^T$ が入力空間の回転、$\mathrm{\Sigma }$ が軸方向の伸縮、$U$ が出力空間の回転を表す。$A$ がどの方向を強く伸ばし、どの方向を強く潰すかが ${\sigma }_i$ により定量化される。

逆問題では擬似逆行列が重要になる。$A$ のランクを $r$ とすると

$$A^{+}=V\left[\begin{array}{cc}{\mathrm{\Sigma }}_r^{-1}& 0\\ 0& 0\end{array}\right]U^T$$

であり、最小二乗解の一つを与える。小さい特異値は ${\mathrm{\Sigma }}^{-1}$ で大きく増幅されるため、ノイズがある場合には切断や正則化が必要となる。

特異値分解は階数と4つの基本部分空間を同時に可視化する。右特異ベクトルのうち ${\sigma }_i=0$ に対応するものは $\mathcal{N}(A)$ の基底であり、左特異ベクトルのうち ${\sigma }_i=0$ に対応するものは $\mathcal{N}(A^T)$ の基底である。

1.9　主成分と最適な低ランク行列

データ行列を $X\in {\mathbb{R}}^{N\times d}$（行がサンプル、列が特徴）とし、各列を中心化して平均0にしたものを再び $X$ と書く。共分散行列は

$$C=\frac{1}{N}{X}^{T}X$$

であり、$C$ は対称半正定値である。固有分解 $C=V\mathrm{\Lambda }{V}^T$ の固有ベクトル $V$ が主成分方向を与え、固有値が分散の大きさを与える。

SVDで見ると $X=U\mathrm{\Sigma }{V}^T$ より $X^{T}X=V{\mathrm{\Sigma }}^2{V}^T$ であり、PCAはSVDの右特異ベクトル $V$ を得る問題と同一である。主成分得点は $XV=U\mathrm{\Sigma }$ となり、データを直交座標へ回転した上でスケールを付けたものとして理解できる。

低ランク近似は、データの自由度を減らしても情報を保つために用いられる。切断SVDにより

$$X_k=U_k{\mathrm{\Sigma }}_k{V}_k^T$$

とすると、Eckart–Youngの定理により $X_k$ はランク $k$ の行列の中で

$$\parallel X-X_k{\parallel }_F$$

を最小にする。これは「最も誤差が小さい圧縮」が数学的に一意に決まることを意味する。

PCAの目的は「分散を最大にする方向」を選ぶことであり、低ランク近似の目的は「再構成誤差を最小にする」ことであるが、中心化と二乗誤差の下では両者が一致する。したがって、分散の説明率と再構成誤差の両方が同じ固有値・特異値により測れる。

注意すべき点として、中心化を行わないと主成分が平均方向に引かれやすい。さらに特徴量の単位が大きく異なると、分散の大きい特徴が主成分を支配しやすく、標準化や相関ベースの扱いが必要になる場合がある。

1.10 レイリー商と一般化固有値

対称行列 $A$ に対するレイリー商は

$$R(x)=\frac{x^{T}Ax}{x^{T}x}$$

で定義され、$x$ の方向に沿う二次形式の平均的な大きさを表す。$x$ を単位ベクトルに制限すれば $R(x)=x^{T}Ax$ であり、これは二次形式の最大化・最小化問題になる。

極値は固有値に一致する。すなわち

$${\lambda }_{max}=\underset{x\ne 0}{max}R(x),{\lambda }_{min}=\underset{x\ne 0}{min}R(x)$$

であり、最大値・最小値を与える $x$ はそれぞれ最大固有値・最小固有値の固有ベクトルである。これは Courant–Fischer の最小最大原理として一般化できる。

一般化固有値問題は

$$Ax=\lambda Bx$$

であり、$B$ が対称正定値なら、$B$ による内積の下での固有問題として理解できる。レイリー商も

$$R_B(x)=\frac{x^{T}Ax}{x^{T}Bx}$$

に置き換わり、$x^{T}Bx=1$ の制約付きで $x^{T}Ax$ を極値化する問題になる。

この形式は、重み付き最小二乗や正則化の背後に現れる。例えば「あるエネルギーを小さくしつつ別の量を固定する」型の設計では、自然に $A$ と $B$ の比として固有問題が生じる。

1.11 ベクトル，関数，行列のノルム

ベクトルノルムには ${\ell }^1,{\ell }^2,{\ell }^{\mathrm{\infty }}$ があり、

$$\parallel x{\parallel }_1=\sum _i|x_i|,\parallel x{\parallel }_2=\sqrt{\sum _i{x}_i^2},\parallel x{\parallel }_{\mathrm{\infty }}=\underset{i}{max}|x_i|$$

である。これらは誤差の測り方を変える操作であり、損失関数や正則化項の形を決める。

関数ノルムは連続版として現れる。例えば区間上の関数 $f$ に対し

$$\parallel f{\parallel }_2={(\int |f(t){|}^{2}dt)}^{1/2}$$

はエネルギーを測る量であり、フーリエ解析や最小二乗近似の理論で重要である。

行列ノルムは作用素ノルム（誘導ノルム）として

$$\parallel A\parallel =\underset{x\ne 0}{max}\frac{\parallel Ax\parallel }{\parallel x\parallel }$$

で定義される。${\ell }^2$ に対応する行列ノルムは最大特異値に等しく

$$\parallel A{\parallel }_2={\sigma }_1$$

が成り立つ。

フロベニウスノルム

$$\parallel A{\parallel }_F=\sqrt{\sum _{i,j}{a}_{ij}^2}=\sqrt{\sum _k{\sigma }_k^2}$$

も頻繁に用いられる。$\parallel A{\parallel }_F$ は成分二乗和であり、SVDとの相性がよく、低ランク近似の誤差評価に自然に現れる。

ノルムには基本的不等式があり、例えば誘導ノルムでは劣乗法性

$$\parallel AB\parallel \le \parallel A\parallel \parallel B\parallel$$

が成り立つ。これにより、複数段の変換が誤差をどれだけ増幅し得るかを上から押さえることができる。

条件数はノルムで定義される。可逆行列 $A$ に対し

$${\kappa }_2(A)=\parallel A{\parallel }_2\parallel A^{-1}{\parallel }_2=\frac{{\sigma }_{max}}{{\sigma }_{min}}$$

であり、${\sigma }_{min}$ が小さいほど逆問題が不安定になりやすいことが定量化される。

1.12 行列とテンソルの分解：非負と疎

非負値行列分解（NMF）は、非負データ $X\in {\mathbb{R}}_{\ge 0}^{m\times n}$ に対し

$$X\approx WH,W\ge 0,H\ge 0$$

を求める。非負制約により、正負の相殺が起きにくく、加法的な部品表現として解釈しやすいことが多い。

NMFは一般に非凸であり、初期値や更新則に依存して異なる解へ到達し得る。したがって、解の一意性よりも、目的に合った表現（例えば局在性や滑らかさ）を得るための制約設計が重要である。

疎表現は、多くの成分が0に近い係数でデータを表すことを目指す。辞書 $D$ と係数 $z$ を用い、$x\approx Dz$ として

$$\underset{z}{min}\frac{1}{2}\parallel Dz-x{\parallel }_2^2+\lambda \parallel z{\parallel }_1$$

を解くと、${\ell }^1$ 項が疎性を促す。これはラプラス事前分布を仮定した最大事後推定としても理解でき、統計と最適化が同じ式に合流する。

行列分解ではランクが構造仮定であるのに対し、疎表現では「成分数の少なさ」が構造仮定である。両者は別の仮定であるが、同時に用いることで「低ランクかつ疎」といった複合的な表現も設計できる。

テンソル分解は多次元配列 $X\in {\mathbb{R}}^{I\times J\times K\cdots }$ を対象とする。CP分解は

$$X\approx \sum _{r=1}^R{a}_r\otimes b_r\otimes c_r$$

の形でランク1テンソルの和として表し、Tucker分解は

$$X\approx G{\times }_{1}A{\times }_{2}B{\times }_{3}C$$

の形でコアテンソル $G$ と因子行列の積として表す。

テンソルでは、行列とは異なる同定性の性質が現れる。条件が整うと、回転の自由度が少なく、因子が比較的決まりやすい場合がある一方、計算は非凸で大規模化しやすい。したがって、分解の目的（圧縮、解釈、予測）に応じてランクや制約を設計する必要がある。

本章の要点は、行列の作用を列空間として捉え、直交性で誤差を分解し、分解（LU・QR・固有分解・SVD）で構造を抽出することである。これらは次章以降の大規模計算や学習法の式変形で繰り返し用いられ、同じ概念が異なる形で再登場するのである。

第2章：大規模行列の計算

本章では、行列のサイズが大きくなったときに何が難しくなり、どの数学的工夫が計算を成立させるかを整理するのである。密行列の分解をそのまま適用できない状況を前提に、誤差の評価、最小二乗の解法の分岐、基底の取り方、乱択法による近似という流れで述べるのである。

2.1　数値線形代数

数値線形代数は、有限精度の浮動小数点計算で線形代数を実行するとき、結果がどの程度信頼できるかを定量化し、安定に計算する方法を与える分野である。理論上同じ式であっても、計算の順序や分解法の選択により、誤差の増幅が大きく異なるのである。

浮動小数点では、四則演算の結果は一般に丸めを受ける。典型的には

$$\mathrm{fl}(a\circ b)=(a\circ b)(1+\delta ),|\delta |\le u$$

のようにモデル化され、$u$ は単位丸め誤差である（$\circ$ は $+,-,\times ,/$ のいずれかである）。この丸めは各演算で蓄積し、特に引き算による桁落ちや、極端にスケールが異なる量の加算で顕在化しやすいのである。

誤差評価では、前進誤差と後退誤差を区別する。前進誤差は得られた解 $\hat{x}$ と真の解 $x$ の差 $\parallel \hat{x}-x\parallel$ を測る量である一方、後退誤差は「入力をどれだけわずかに変えれば $\hat{x}$ が厳密解になるか」を測る量である。後退誤差が小さいアルゴリズムは、入力データに対して理にかなった意味で安定であることが多いのである。

線形方程式 $Ax=b$ の難しさは条件数で支配される。可逆行列 $A$ について

$$\kappa (A)=\parallel A\parallel \parallel A^{-1}\parallel$$

と定めると、$b$ や $A$ の小さな摂動が解 $x$ にどれだけ増幅されるかの上界が得られる。特に2ノルムでは ${\kappa }_2(A)={\sigma }_{max}/{\sigma }_{min}$ であり、最小特異値が小さいことが不安定性の直接要因である。

大規模行列では、メモリと計算量の制約が最初に効いてくる。密な $n\times n$ 行列を保持するだけで $O(n^2)$ のメモリが必要であり、$LU$ や $QR$ などの分解は一般に $O(n^3)$ の演算量を要する。したがって行列が疎である、あるいは行列ベクトル積 $Ax$ を高速に計算できるという構造を利用し、反復法へ移行するのが自然である。

疎行列は非零要素数 $\mathrm{nnz}(A)$ に比例した計算で $Ax$ を評価できる。多くの反復法は本質的に行列ベクトル積の繰り返しであり、行列を明示的に分解しない。これは「行列の作用だけを使って解を近づける」という思想であり、巨大データの最小二乗や偏微分方程式離散化において中心となるのである。

代表的な反復法として、Krylov部分空間法がある。初期残差 $r_0=b-A{x}_0$ に対し

$${\mathcal{K}}_k(A,r_0)=\mathrm{span}\{r_0,A{r}_0,A^2{r}_0,\dots ,A^{k-1}{r}_0\}$$

を構成し、その部分空間上で最も良い近似解を求めるのが基本原理である。共役勾配法は対称正定値系に適合し、GMRESは一般の非対称系へ拡張される。

反復法の性能は前処理に大きく依存する。前処理は、元の問題 $Ax=b$ を $M^{-1}Ax=M^{-1}b$ のように変形して「解きやすい形へ」移す操作である。理想的には $M\approx A$ でありながら、$M^{-1}$ を適用する計算が軽い必要があるため、ここに設計上の緊張が生まれるのである。

停止条件も数値線形代数の中心である。反復を止める基準として $\parallel r_k\parallel /\parallel b\parallel$ を用いることが多いが、残差が小さいことと解誤差 $\parallel x-\hat{x}\parallel$ が小さいことは常に同値ではない。条件数が大きいと、残差が小さくても解が不確かであり得るため、条件数評価や正則化の視点と組み合わせて判断する必要があるのである。

2.2　最小二乗法の4つの方法

最小二乗問題は

$$\underset{x}{min}\parallel Ax-b{\parallel }_2$$

であり、データサイエンスでは回帰、同定、復元の最も基本的な形である。幾何学的には、$Ax$ が列空間 $\mathcal{C}(A)$ を動くので、$b$ を $\mathcal{C}(A)$ へ直交射影した点が最適近似になるのである。

最適性条件は残差 $r=b-A\hat{x}$ が列空間に直交することであり、

$$A^T(b-A\hat{x})=0$$

すなわち正規方程式

$$A^{T}A\hat{x}=A^{T}b$$

が得られる。この式は簡潔であるが、数値的には $A^{T}A$ の条件数が $\kappa (A{)}^2$ 程度まで悪化し得ることが重要である。したがって「解ける」ことと「信頼できる」ことは別であり、解法の選択理由がここから生じるのである。

最小二乗の主要な解法は、正規方程式、QR分解、SVD、反復法の4つとして整理できる。いずれも同じ幾何を異なる分解で実装しているが、計算量・安定性・拡張性が異なるのである。

方法	主要変形	数値安定性	計算量の目安（密行列）	備考
正規方程式	$A^{T}Ax=A^{T}b$	低い場合がある	$A^{T}A$ 形成が $O(m{n}^2)$、解法が $O(n^3)$	条件数が悪化しやすい
QR分解	$A=QR$	高い	$O(m{n}^2)$	直交性で誤差が抑えられる
SVD	$A=U\mathrm{\Sigma }{V}^T$	最も高い	$O(m{n}^2)$（定数が大きい）	ランク欠損・正則化と整合
反復法	行列ベクトル積	前処理次第	$O(k\mathrm{nnz}(A))$	巨大・疎で有効

正規方程式は、実装が簡単で計算資源が限られる場合に魅力があるが、$A^{T}A$ を作る段階で情報が二乗的に圧縮され、丸め誤差に弱くなり得る。特に $A$ の列がほぼ従属であるとき、${\sigma }_{min}$ が小さく、$A^{T}A$ はさらに悪条件となるため、解が不安定になりやすいのである。

QR分解は、直交行列 $Q$ によりノルムが保たれることを利用する。$A=QR$ とすると

$$\parallel Ax-b{\parallel }_2=\parallel QRx-b{\parallel }_2=\parallel Rx-Q^{T}b{\parallel }_2$$

であり、$R$ が上三角であるため後退代入へ落ちる。$Q^{T}b$ は $b$ の列空間方向と直交補空間方向を分離し、残差の大きさが幾何として読み取れる形になるのである。

SVDは最小二乗を最も透明にする。$A=U\mathrm{\Sigma }{V}^T$ とすると、擬似逆行列により最小ノルム解の一つが

$$\hat{x}=A^{+}b=V{\mathrm{\Sigma }}^{+}{U}^{T}b$$

で与えられる。小特異値がノイズを増幅する機構が式の形で現れるため、正則化を入れた議論と整合しやすいのである。

正則化付き最小二乗として、Tikhonov正則化（リッジ回帰）がある。これは

$$\underset{x}{min}\parallel Ax-b{\parallel }_2^2+\lambda \parallel x{\parallel }_2^2$$

であり、正規方程式は

$$(A^{T}A+\lambda I)x=A^{T}b$$

となる。$A^{T}A$ に $\lambda I$ を足すことは最小固有値を持ち上げ、条件数を改善し、過剰適合を抑える方向へ働くのである。

重み付き最小二乗も重要である。誤差の共分散が $\mathrm{\Sigma }$ のとき

$$\underset{x}{min}(Ax-b{)}^T{\mathrm{\Sigma }}^{-1}(Ax-b)$$

となり、$W={\mathrm{\Sigma }}^{-1/2}$ を用いて $\underset{x}{min}\parallel W(Ax-b){\parallel }_2$ に帰着する。これは「ノイズが小さい観測を強く信じる」ことを幾何として表したものであり、一般化固有値の構造へも接続するのである。

反復法は、$m,n$ が非常に大きいときの現実的選択となる。LSQRやCGNRなどは最小二乗をKrylov法で解く代表例であり、行列を明示的に分解せず $A$ と $A^T$ の作用だけで進む。停止を早めれば近似解となり、これは暗黙の正則化として働く場合があるため、計算と統計の両面で意味を持つのである。

最小二乗の幾何をもう一段掘り下げると、射影行列が現れる。列が一次独立であるとき、最小二乗解は

$$\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$$

であり、近似値は $\hat{b}=A\hat{x}$ である。このとき

$$\hat{b}=Pb,P=A(A^{T}A{)}^{-1}{A}^T$$

で $P$ は列空間への直交射影となる。したがって最小二乗は「データを部分空間へ落とす」操作であり、モデルが表現できる成分と表現できない成分が射影で分離されるのである。

2.3　列空間の3種類の基底

列空間 $\mathcal{C}(A)$ の基底は一つではなく、目的に応じて使い分ける必要がある。ここでは、元の列から選ぶ基底、直交基底、特異ベクトル基底の3種類を取り上げ、それぞれが何を見やすくし、何を犠牲にするかを述べるのである。

第1の基底は、元の列ベクトルの部分集合として選ぶ基底である。ガウス消去やピボット付きQRにより、独立性の高い列を選択し、それらで列空間を張る。元の特徴量の一部として基底が表現されるため、解釈が直感的であり、どの特徴が空間を支配しているかが見えやすいのである。

この考えは列サブセット選択（CUR分解など）へもつながる。$A\approx CUR$ の形で、$C$ を実データの列、$R$ を実データの行として選ぶと、近似がデータの成分から構成される。SVDのように回転した基底よりも、データの座標系に沿った説明が欲しい場合に意味を持つのである。

第2の基底は直交基底である。QR分解 $A=QR$ の $Q$ の列は $\mathcal{C}(A)$ の直交基底になり、任意の $b$ の射影 $Q{Q}^{T}b$ が最小二乗近似を与える。直交であることにより係数が安定に決まり、射影や距離の計算が単純になるのである。

直交基底の重要性は、誤差解析でも現れる。直交変換はノルムを保存するため、$\parallel Ax-b{\parallel }_2$ の評価が変換によって歪まない。したがって計算過程で「距離が保たれる」という性質が、誤差を増やさない仕組みとして働くのである。

第3の基底は特異ベクトル基底である。SVD $A=U\mathrm{\Sigma }{V}^T$ における $U$ の上位 $r$ 本（$r=\mathrm{rank}(A)$）は列空間の直交基底を与えるが、さらに「重要度の順序」を同時に与える点が本質である。${\sigma }_1\ge {\sigma }_2\ge \cdots$ の大小が、どの方向が強く表現され、どの方向が弱いかを定量化するのである。

特異ベクトル基底は低ランク近似へ直結する。上位 $k$ 個だけを残すと、列空間のうち「データを最もよく再現する部分空間」が得られ、誤差は ${\sigma }_{k+1}$ や $\sum _{i>k}{\sigma }_i^2$ で評価できる。これは、基底の選び方そのものが統計的な圧縮の設計になっていることを意味するのである。

3種類の基底は互いに排他的ではなく、目的によって併用される。解釈を保ちたいときは列選択基底が有利であり、安定な計算を優先するときは直交基底が有利であり、圧縮やノイズ除去を重視するときは特異ベクトル基底が有利である。したがって「どの基底が良いか」は、行列の性質だけでなく、取り出したい情報の種類に依存するのである。

2.4　乱択線形代数

乱択線形代数は、ランダム性を用いて行列の主要構造を高速に近似する方法を体系化した分野である。巨大データでは厳密分解にこだわるよりも、高い確率で十分良い近似を短時間で得ることに価値があり、乱択法はその要求に合致するのである。

基本となる発想はスケッチである。行列 $A\in {\mathbb{R}}^{m\times n}$ に対し、$s\ll m$ のランダム行列 $S\in {\mathbb{R}}^{s\times m}$ を用いて

$$\tilde{A}=SA,\tilde{b}=Sb$$

を作り、小さい問題で近似解を得る。$S$ が距離や内積をある程度保つなら、元の最小二乗 $\parallel Ax-b{\parallel }_2$ の性質が $\parallel \tilde{A}x-\tilde{b}{\parallel }_2$ に反映されるのである。

距離保存の背後にはランダム射影の理論がある。高次元点集合の距離をほぼ保ったまま低次元へ写せるという事実は、スケッチが幾何を壊しにくい理由を与える。したがって乱択法は、単なる経験的技巧ではなく、確率的な保証を伴う近似である点が重要である。

乱択SVD（乱択低ランク近似）の基本形は、行列の値域をランダムに探索することである。ランダム行列 $\mathrm{\Omega }\in {\mathbb{R}}^{n\times (k+p)}$ を用いて

$$Y=A\mathrm{\Omega }$$

を作ると、$Y$ の列空間は $A$ の主要な列空間成分を高確率で含む。ここで $p$ は余裕次数であり、わずかに大きく取ることで近似の頑健性が増すのである。

次に、$Y$ の直交基底 $Q$ を作り、$A$ を $Q$ で近似する：

$$A\approx Q{Q}^{T}A$$

である。これにより大行列 $A$ の情報は小行列 $B=Q^{T}A$ に圧縮され、あとは $B$ に対してSVDを実行すればよい。計算の多くが行列ベクトル積と小さな分解に置き換わり、大規模化に耐える構造になるのである。

特異値の減衰が遅い場合には、パワー反復を組み合わせる。例えば

$$Y=(A{A}^T{)}^{q}A\mathrm{\Omega }$$

とすると、支配的特異値の寄与が強調され、近似が改善される。これは「重要方向をより見つけやすくする」操作であるが、反復回数 $q$ を増やすと計算量も増えるため、精度と資源の折り合いが必要である。

スケッチ行列 $S$ の構成にも選択肢がある。ガウス乱数や符号乱数のような密なスケッチは理論が扱いやすいが、計算コストとメモリ負荷が増える。疎スケッチ（CountSketchなど）や、構造を持つ変換（ランダム化ハダマード変換など）は高速化に寄与し、巨大データで意味を持つのである。

乱択法は最小二乗にも直接適用できる。スケッチ後の問題

$$\underset{x}{min}\parallel SAx-Sb{\parallel }_2$$

を解くと、元の問題の近似解が得られ、特に $m$ が極めて大きいときに有効である。さらに $SA$ に対してQRを行い、それを前処理として反復法に渡すと、収束が改善される場合が多いのである。

列・行のサンプリングという考え方も重要である。行列の情報は均一に分布しているとは限らず、少数の行や列が大きな影響力を持つことがある。レバレッジスコアはその影響度を測る量であり、これに比例してサンプルすると近似が良くなるという思想が生まれるのである。

乱択線形代数の価値は、計算の高速化だけではない。大規模データでは、厳密解が必ずしも最良の推定を意味しないことが多く、近似が統計的安定性と親和的である場合もある。したがって、乱択法は「計算資源の制約下で、構造を保った近似を得る」ための数学として位置づけられるのである。

本章で述べた数値線形代数、最小二乗の複数解法、基底の取り方、乱択近似は、いずれも行列の分解と直交性という第1章の概念を計算へ翻訳したものである。次章以降では、低ランクや疎性といった構造仮定が、どのように推定可能性と計算可能性を同時に成立させるかを、さらに深い形で扱うのである。

第3章：低ランク行列と圧縮センシング

本章では、低ランク性と疎性という2つの構造が、少ない情報からの復元やノイズ分離を可能にする理由を、逆行列の更新・固有値の挙動・特異値の減衰という線形代数の言葉で説明するのである。さらに、${\ell }^2$ と ${\ell }^1$ を組み合わせた最適化が、低ランク成分と疎成分の分離、そして圧縮センシングや行列補完の基礎式として現れる流れを示すのである。

3.1　A の変化から生じる A^{-1} の変化

逆行列は、行列のわずかな変化に対して大きく変動し得る量であり、その感度は条件数と密接に関係する。大規模計算や逐次推定では、$A$ を丸ごと作り直して逆行列を再計算するのではなく、低ランクな更新として扱い、$A^{-1}$ を更新する発想が中心となるのである。

基本となる事実は、可逆行列 $A$ とベクトル $u,v$ に対して rank-1 更新

$$\tilde{A}=A+u{v}^T$$

を考えるとき、$\tilde{A}$ が可逆であれば Sherman–Morrison の公式

$$(A+u{v}^T{)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^T{A}^{-1}}{1+v^T{A}^{-1}u}$$

が成り立つことである。分母の $1+v^T{A}^{-1}u$ が 0 に近いとき、更新後の逆行列が急激に増幅され得るため、可逆性と数値安定性の両方を同時に監視する必要がある。

より一般に、低ランク更新

$$\tilde{A}=A+UC{V}^T(U\in {\mathbb{R}}^{n\times r},V\in {\mathbb{R}}^{n\times r},C\in {\mathbb{R}}^{r\times r})$$

に対しては Woodbury の公式

$$(A+UC{V}^T{)}^{-1}=A^{-1}-A^{-1}U{(C^{-1}+V^T{A}^{-1}U)}^{-1}{V}^T{A}^{-1}$$

が成り立つ。$r\ll n$ であれば、更新に必要な主要計算は $r\times r$ の逆行列であり、巨大な $n\times n$ 逆行列を再計算するより圧倒的に軽いのである。

これらの公式は、逆行列そのものを持たなくても意味を持つ。実際には $A^{-1}$ を明示せず、線形方程式 $Az=b$ を解く操作を $A^{-1}b$ とみなし、そこへ $U$ や $V$ を挿入する形で更新を実装することが多い。したがって低ランク更新は、反復法や前処理と結びついた形で現場の計算を支えるのである。

微分の観点からも、逆行列の感度は簡潔に表せる。$A$ の微小摂動 $\mathrm{\Delta }A$ に対して

$$(A+\mathrm{\Delta }A{)}^{-1}-A^{-1}=-A^{-1}(\mathrm{\Delta }A)A^{-1}+O(\parallel \mathrm{\Delta }A{\parallel }^2)$$

が成り立ち、一次の変化は $A^{-1}$ が左右から挟む形で現れる。ゆえに $\parallel A^{-1}\parallel$ が大きい、すなわち $A$ が悪条件であると、逆行列は摂動に対して脆弱になるのである。

低ランク更新は、正則化とも結びつく。例えばリッジ型の更新として $\tilde{A}=A+\lambda I$ を考えると、固有値は一様に $\lambda$ だけ持ち上がり、最小固有値が増えることで逆行列の暴れが抑えられる。低ランク更新と対角更新を組み合わせることで、計算量と安定性の折り合いを取る設計が可能になるのである。

3.2　インターレースする固有値と低ランクな信号

低ランクな変更は、固有値の分布を局所的に動かすが、その動きには厳密な制約がある。特に対称行列に対する固有値のインターレースは、低ランク信号がノイズの上に突き出す条件を、固有値列の順序として記述する道具となるのである。

まず、対称行列 $A\in {\mathbb{R}}^{n\times n}$ の固有値を

$${\lambda }_1(A)\ge {\lambda }_2(A)\ge \cdots \ge {\lambda }_n(A)$$

と並べる。$A$ の主小行列（ある行と列を同時に削除して得る $(n-1)\times (n-1)$ 行列）を $B$ とすると、Cauchy のインターレース定理により

$${\lambda }_1(A)\ge {\lambda }_1(B)\ge {\lambda }_2(A)\ge {\lambda }_2(B)\ge \cdots \ge {\lambda }_{n-1}(B)\ge {\lambda }_n(A)$$

が成り立つ。部分系の固有値が元の固有値の隙間に挟まるという事実は、データの一部欠落やサブサンプリングがスペクトルへ与える影響の限界を与えるのである。

rank-1 更新 $A+\rho u{u}^T$ に対しても、固有値の変化は秩序を保つ。一般の摂動評価として Weyl の不等式は

$$|{\lambda }_i(A+E)-{\lambda }_i(A)|\le \parallel E{\parallel }_2$$

を与え、低ランクであっても $\parallel E{\parallel }_2$ が大きければ固有値は大きく動き得ることを示す。一方で rank が小さいと、動く固有値の本数に強い制約がかかり、全体のスペクトルが一様に崩れるわけではないのである。

低ランク信号の基本モデルとして、スパイク型の共分散を考える。真の共分散を

$$\mathrm{\Sigma }={\sigma }^{2}I+\sum _{j=1}^r{\theta }_j{v}_j{v}_j^T({\theta }_j>0,v_j^T{v}_k={\delta }_{jk})$$

とすると、${\sigma }^{2}I$ が等方的ノイズ、後者が rank-$r$ の信号である。観測から得る標本共分散は有限サンプルのゆらぎを含み、ノイズのスペクトルにも広がりが生じるため、信号の固有値 ${\sigma }^2+{\theta }_j$ がノイズ帯域からどれだけ分離するかが、主成分として回収できるかを決めるのである。

この分離は、固有値の間隔と固有ベクトルの安定性にも直結する。Davis–Kahan 型の評価により、固有値ギャップが大きいほど固有ベクトルは摂動に強く、ギャップが小さいほど方向は回転しやすい。したがって、低ランク信号をスペクトルで検出する議論では、固有値そのものだけでなく、固有値の間隔を同時に扱う必要があるのである。

グラフラプラシアン $L$ の小固有値がクラスタ構造を表すのも、同様にインターレースと摂動の論理で理解できる。辺の追加や重みの変更は $L$ の低ランクないし局所的な更新として表され、固有値列の動きが連結性や分割の頑健性へ反映されるのである。

3.3　急速に減衰する特異値

多くの実データでは、行列の特異値が急速に減衰し、有効な自由度が小さいことが多い。これはデータが本当に低ランクである場合だけでなく、低ランク近似が少ない誤差で成り立つという意味で「低ランクに近い」状況が広く存在するためである。

$A\in {\mathbb{R}}^{m\times n}$ の特異値を ${\sigma }_1\ge {\sigma }_2\ge \cdots$ とする。rank-$k$ 近似 $A_k$ を切断SVDで作ると、Eckart–Young の定理により

$$\parallel A-A_k{\parallel }_2={\sigma }_{k+1},\parallel A-A_k{\parallel }_F^2=\sum _{j>k}{\sigma }_j^2$$

が成り立つ。ゆえに、特異値が速く落ちるほど、少数の成分で行列を高精度に表現できるのである。

特異値減衰の形は、近似の難易度を決める。指数的減衰 ${\sigma }_j\approx c{\alpha }^j$（$0<\alpha <1$）なら、少数の $k$ で誤差が急減する一方、べき減衰 ${\sigma }_j\approx c{j}^{-p}$ の場合は尾部が厚く、同じ誤差まで落とすにはより大きな $k$ が必要である。したがって、低ランク法を適用する前に、特異値の減衰形を観察し、期待できる圧縮率を把握することが重要である。

統計の観点では、特異値の小さい方向はノイズに埋もれやすい。$A$ に加法ノイズ $E$ が乗って $A+E$ を観測するとき、スペクトルノルムでの摂動は $\parallel E{\parallel }_2$ 程度で固有値・特異値へ反映される。したがって ${\sigma }_k$ が $\parallel E{\parallel }_2$ と同程度以下になると、その成分を推定することは本質的に不安定になりやすいのである。

この事情は、切断が推定の安定化として働く理由でもある。小特異値の逆数は擬似逆で増幅因子になるため、切断SVDは不安定な方向を捨てることで推定誤差を抑える。したがって低ランク近似は、圧縮だけでなく、逆問題の安定化としても理解されるのである。

特異値減衰は計算方法にも影響する。上位 $k$ 個の特異値・特異ベクトルだけが必要なら、反復法や乱択法が有効になり、全SVDを避けられる。第2章の乱択低ランク近似が機能する根拠も、上位特異値が支配的であるという減衰構造にあるのである。

3.4　${\ell }^2+{\ell }^1$ の分離アルゴリズム

${\ell }^2$ はエネルギーや二乗誤差を測る標準的な量であり、${\ell }^1$ は疎性を促す量として働く。両者を組み合わせると、ノイズに対して頑健で、かつ疎な表現を持つ推定が得られ、低ランク成分と疎成分の分離にも同型の構造が現れるのである。

基本形は LASSO に代表される

$$\underset{x}{min}\frac{1}{2}\parallel Ax-b{\parallel }_2^2+\lambda \parallel x{\parallel }_1$$

である。${\ell }^2$ 項がデータ適合、${\ell }^1$ 項が疎性を与え、$\lambda$ が両者の均衡を調整する。$\lambda$ を大きくすると係数はより0へ押し込まれ、小さくするとデータ適合が優先されるのである。

この問題は凸であり、近接勾配法で解ける。${\ell }^1$ の近接写像はソフトしきい値

$${\mathrm{soft}}_{\tau }(z)=\mathrm{sign}(z)max(|z|-\tau ,0)$$

であり、更新は

$$x^{k+1}={\mathrm{soft}}_{\lambda t}(x^k-t{A}^T(A{x}^k-b))$$

の形になる。ここで $t$ はステップ幅であり、$A^{T}A$ のスペクトル半径に応じて選ばれるのである。

収束を速める方法として加速近接勾配（FISTA）があり、同じ近接写像を用いながら、補助変数を導入して収束率を改善する。凸性の下で収束保証が明確である点は、大規模データで反復回数を見積もる上で意味が大きいのである。

${\ell }^2+{\ell }^1$ は疎性だけでなく、分離の問題にも現れる。観測 $M$ を

$$M=L+S$$

と分解し、$L$ を低ランク、$S$ を疎として回収する問題は、ロバストPCAとして

$$\underset{L,S}{min}\parallel L{\parallel }_{\ast }+\lambda \parallel S{\parallel }_1\text{s.t.}L+S=M$$

で定式化される。ここで $\parallel L{\parallel }_{\ast }$ は核ノルムであり、特異値の和 $\sum _i{\sigma }_i(L)$ である。

核ノルムの近接写像は特異値しきい値（SVT）である。$Y=U\mathrm{\Sigma }{V}^T$ のSVDに対し

$${\mathrm{SVT}}_{\tau }(Y)=U\mathrm{diag}(max({\sigma }_i-\tau ,0))V^T$$

となり、特異値をソフトに削る操作として低ランク化が実現される。疎成分の更新がソフトしきい値であるのと並行しており、低ランクと疎の分離が同じ数学構造の上で進むことが見えるのである。

実装上は ADMM による分割がよく用いられる。制約 $L+S=M$ をラグランジュ乗数で扱い、$L$ 更新はSVT、$S$ 更新はソフトしきい値、乗数更新は残差に比例する形になる。各更新が閉形式に近い形で書けるため、巨大でも反復が組み立てやすいのである。

${\ell }^2+{\ell }^1$ 系の方法は、目的に応じて多様に変形される。ノイズを明示するなら

$$\underset{L,S}{min}\parallel L{\parallel }_{\ast }+\lambda \parallel S{\parallel }_1\text{s.t.}\parallel M-(L+S){\parallel }_F\le \epsilon$$

のような緩和が自然であり、データの不確かさを許容した推定になる。制約型と罰則型は双対性を通じて関係するが、$\lambda$ や $\epsilon$ の選び方が推定の性質を決めるため、ノイズモデルと同時に考える必要があるのである。

次の表は、${\ell }^2+{\ell }^1$ と関連する基本問題をまとめたものである。

目的	代表的定式化	構造仮定	主要近接写像
疎回帰	$\underset{x}{min}\frac{1}{2}|Ax-b{|}_2^2+\lambda |x{|}_1$	$x$ が疎	ソフトしきい値
疎復元（制約型）	$\underset{x}{min}|x{|}_1\text{s.t.}|Ax-b{|}_2\le \epsilon$	$x$ が疎	射影としきい値
低ランク近似	$\underset{L}{min}\frac{1}{2}|L-M{|}_F^2+\lambda |L{|}_{\ast }$	$L$ が低ランク	SVT
低ランク＋疎分離	$\underset{L,S}{min}|L{|}_{\ast }+\lambda |S{|}_1\text{s.t.}L+S=M$	$L$ 低ランク、$S$ 疎	SVT とソフトしきい値

3.5　圧縮センシングと行列補完

圧縮センシングは、未知ベクトルが疎であるという仮定の下で、観測数が未知数より少ない状況から復元を可能にする理論である。行列補完は、未知行列が低ランクであるという仮定の下で、観測エントリが欠けた状況から全体を復元する理論であり、疎性と低ランク性が互いに鏡像のような位置にあることを示すのである。

圧縮センシングの基本式は

$$y=Ax(A\in {\mathbb{R}}^{m\times n},m<n)$$

であり、未知 $x$ は $k$-疎、すなわち非零要素数が $k$ 程度であると仮定する。$m<n$ では一般に無数の解があるが、疎という構造を追加すると解が一意に近づくのである。

理想的な定式化は $\parallel x{\parallel }_0$（非零数）最小化であるが、これは組合せ最適化となり難しい。そこで凸緩和として

$$\underset{x}{min}\parallel x{\parallel }_1\text{s.t.}Ax=y$$

（ノイズがある場合は $\parallel Ax-y{\parallel }_2\le \epsilon$ を課す）を解く。${\ell }^1$ が疎性を誘導する理由は、単位球が角を持ち、解が座標軸へ寄りやすい幾何にあるのである。

観測行列 $A$ がどの程度復元に適しているかは、RIP（Restricted Isometry Property）で表現されることが多い。すべての $k$-疎ベクトル $x$ に対して

$$(1-{\delta }_k)\parallel x{\parallel }_2^2\le \parallel Ax{\parallel }_2^2\le (1+{\delta }_k)\parallel x{\parallel }_2^2$$

が成り立つなら、$A$ は疎ベクトルの距離をほぼ保ち、異なる疎ベクトルが観測空間で混線しにくい。ランダム行列は高確率でこの性質を満たしやすく、必要観測数が $m\gtrsim k\log (n/k)$ 程度で足りるという形で理論が与えられるのである。

復元アルゴリズムには、基底追跡（${\ell }^1$ 最小化）だけでなく、反復しきい値法や貪欲法もある。例えば反復しきい値は、${\ell }^2+{\ell }^1$ で述べた更新をそのまま用い、安価な反復で疎解へ近づける。貪欲法は支持集合を段階的に増やしていくが、条件が整えば少ない反復で解に到達し得るため、計算資源との兼ね合いで選ばれるのである。

行列補完は、部分観測から低ランク行列 $X$ を復元する問題である。観測集合 $\mathrm{\Omega }$ に対し、射影作用素 $P_{\mathrm{\Omega }}$ を

$$(P_{\mathrm{\Omega }}(X){)}_{ij}=\{\begin{array}{ll}{X}_{ij}& (i,j)\in \mathrm{\Omega }\\ 0& \text{それ以外}\end{array}$$

と定めると、基本形は

$$P_{\mathrm{\Omega }}(X)=P_{\mathrm{\Omega }}(M)$$

を満たす低ランク $X$ を求める問題になる。rank 最小化は難しいため、凸緩和として

$$\underset{X}{min}\parallel X{\parallel }_{\ast }\text{s.t.}{P}_{\mathrm{\Omega }}(X)=P_{\mathrm{\Omega }}(M)$$

が中心となる。核ノルムがランクの凸包として働き、低ランク性を促すのである。

行列補完が可能であるためには、低ランクであるだけでは不十分であり、非ゼロ成分が特定の行や列に偏りすぎないことが必要である。これは非整合性（incoherence）として定式化され、特異ベクトルが標準基底へ極端に集中しないことを要求する。直感的には、情報が全体に分散しているほど、ランダムに欠けても埋め戻しが可能になりやすいのである。

ノイズがある場合には

$$\underset{X}{min}\frac{1}{2}\parallel P_{\mathrm{\Omega }}(X)-P_{\mathrm{\Omega }}(M){\parallel }_F^2+\lambda \parallel X{\parallel }_{\ast }$$

のような罰則型が自然である。近接勾配法では、観測誤差に対する勾配ステップと、SVTによる核ノルム近接が交互に現れ、低ランク性を維持しながら観測へ合わせていく形になるのである。

圧縮センシングと行列補完は、未知量の構造が異なるだけで、数学的骨格は共通である。疎性は座標基底での少数成分、低ランク性は特異ベクトル基底での少数成分という形で表現され、どちらも ${\ell }^1$ 型の凸緩和が中心に置かれる。したがって、どの基底で構造が現れるのかを見極めることが、復元可能性の議論と計算法の設計を同時に決めるのである。

本章では、低ランク更新が逆行列や固有値に与える制約、特異値減衰が近似と安定性を同時に支える理由、そして ${\ell }^2+{\ell }^1$ が疎性・低ランク性の推定へ直結することを示したのである。次章では、フーリエ・巡回・クロネッカー・ラプラシアンといった特別な行列が、これらの構造を自然に生み、計算をさらに加速する土台になることを扱うのである。

第4章：特別な行列

本章では、信号処理・画像処理・ネットワーク解析・クラスタリングなどで頻出する行列構造を取り上げ、その構造が計算と理論の双方を簡単にする理由を線形代数として述べるのである。これらの行列は、対角化や低ランク近似、反復法の高速化へ自然に接続し、データ解析の中核的な演算を支えるのである。

4.1　フーリエ変換：離散と連続

連続フーリエ変換は

$$\hat{f}(\omega )={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(t)e^{-i\omega t}dt$$

で定義され、時間（あるいは空間）領域の関数を周波数領域へ写す線形変換である。逆変換は規約に依存する定数を除いて

$$f(t)=\frac{1}{2\pi }{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}\hat{f}(\omega )e^{i\omega t}d\omega$$

の形で与えられ、フーリエ変換は情報を失わない可逆な表現変換である。

フーリエ変換が重要なのは、微分や畳み込みが周波数領域で単純化されるためである。例えば $f\ast g$ を畳み込みとして

$$(f\ast g)(t)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(\tau )g(t-\tau )d\tau$$

と定めると、畳み込み定理により

$$\widehat{f\ast g}(\omega )=\hat{f}(\omega )\hat{g}(\omega )$$

が成り立つ。これは線形時不変系（シフト不変な系）の解析が、周波数成分ごとのスカラー倍へ還元されることを意味するのである。

エネルギー保存を述べる Parseval の等式も基本である。規約に応じた係数は変わるが、一般に

$$\int |f(t){|}^{2}dt\propto \int |\hat{f}(\omega ){|}^{2}d\omega$$

が成り立ち、時間領域の二乗和と周波数領域の二乗和が同じ情報量を持つことを示す。したがってノイズの大きさやフィルタの影響が、ノルムとして一貫した形で評価できるのである。

離散フーリエ変換（DFT）は $N$ 点列 $x\in {\mathbb{C}}^N$ を $X\in {\mathbb{C}}^N$ に写し、

$$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-i2\pi kn/N}(k=0,\dots ,N-1)$$

で与えられる。逆DFTは

$$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{i2\pi kn/N}$$

であり、DFTは可逆な線形変換である。

DFTは行列 $F\in {\mathbb{C}}^{N\times N}$ を用いて $X=Fx$ と書ける。成分を

$$F_{kn}=e^{-i2\pi kn/N}$$

とすると、規格化した行列 $\frac{1}{\sqrt{N}}F$ はユニタリであり、内積とノルムを保存する。よってDFTは、周波数基底への直交（正確にはユニタリ）変換であると理解できるのである。

FFTはDFTを高速に計算するアルゴリズムであり、計算量を $O(N^2)$ から $O(N\log N)$ へ下げる。分割統治により指数関数の構造を再利用する点が要であり、行列を明示せずともフーリエ行列の作用 $Fx$ を高速に評価できるのである。巨大データでは $Fx$ や $F^{T}x$ の繰り返しが支配的になり、FFTの存在がモデル選択や反復法の実行可能性を左右する。

連続と離散の接続では、標本化と周期延長が本質である。DFTは有限長列を周期的に延長した信号の周波数成分を与え、畳み込みは巡回畳み込みとして現れる。したがって、有限長データの畳み込みやフィルタリングをDFTで扱うとき、線形畳み込みと巡回畳み込みの差を埋めるためにゼロ埋めが必要になるのである。

次の表は、変換の対象と計算構造の差を整理したものである。

対象	変換	演算としての姿	主な帰結
連続関数	積分	作用素	微分・畳み込みの単純化、スペクトル解析
離散列	行列（和）	ユニタリ変換	周期構造、巡回行列の対角化、FFTによる高速化

4.2　巡回置換行列と巡回行列

巡回置換行列 $P\in {\mathbb{R}}^{N\times N}$ は、成分を1つ循環シフトする作用を表す。例えば

$$P=\left[\begin{array}{ccccc}0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& & & \ddots & ⋮\\ 0& 0& 0& \cdots & 1\\ 1& 0& 0& \cdots & 0\end{array}\right]$$

とすると、$Px$ は $x$ を下方向へ1つ巡回シフトした列になる。$P$ は直交行列であり $P^{T}P=I$ を満たすため、シフト操作はノルムを保存するのである。

巡回行列 $C$ は、あるベクトル $c$ を第1列にもつ行列で、各列が巡回シフトになっている行列である。$P$ を用いると

$$C=c_{0}I+c_{1}P+c_2{P}^2+\cdots +c_{N-1}{P}^{N-1}$$

のように多項式で表せる。よって巡回行列の積は、巡回シフトの線形結合として理解できるのである。

巡回行列が特に扱いやすいのは、DFTで対角化できるためである。フーリエ行列 $F$ を用いると

$$C=F^{\ast }\mathrm{\Lambda }F$$

となり、$\mathrm{\Lambda }$ は対角行列で、その対角成分は $c$ のDFTで与えられる。したがって

$$Cx=F^{\ast }(\mathrm{\Lambda }(Fx))$$

となり、巡回行列の作用は周波数領域で成分ごとのスカラー倍に還元される。

この構造は、巡回畳み込みが周波数領域で積になる事実と同値である。信号 $x$ に対するシフト不変フィルタ $h$ の巡回畳み込みは $C(h)x$ と書け、DFTにより

$$F(C(h)x)=(Fh)\odot (Fx)$$

となる（$\odot$ は要素ごとの積である）。ゆえにFFTを用いれば、畳み込みを $O(N\log N)$ で実行できるのである。

巡回行列は数値線形代数にも現れる。例えばテプリッツ行列を巡回行列で近似すると、前処理や近似解法が高速化されることがある。巡回構造は境界条件が周期的である状況に自然であり、周期境界を仮定した差分法やスペクトル法とも整合するのである。

4.3　クロネッカー積 A×B

クロネッカー積は通常 $A\otimes B$ と書き、$A\in {\mathbb{R}}^{m\times n}$、$B\in {\mathbb{R}}^{p\times q}$ に対して

$$A\otimes B=\left[\begin{array}{ccc}{a}_{11}B& \cdots & a_{1n}B\\ ⋮& \ddots & ⋮\\ a_{m1}B& \cdots & a_{mn}B\end{array}\right]\in {\mathbb{R}}^{mp\times nq}$$

で定義される。テンソル積に対応し、多次元格子や多因子モデルの演算を、行列として一貫して表す道具である。

クロネッカー積の重要性は、次元分離（separable structure）を保ったまま多次元化できる点にある。例えば2次元画像に1次元作用素を縦方向・横方向へ別々に作用させる操作は、クロネッカー積で簡潔に書ける。これにより、巨大な $mp\times nq$ 行列を明示せず、低次元行列の積を繰り返す形へ変形できるのである。

基本恒等式として、行列のベクトル化 $\mathrm{vec}(\cdot )$ を用いると

$$\mathrm{vec}(AXB)=(B^T\otimes A)\mathrm{vec}(X)$$

が成り立つ。これは、多次元配列上の双線形作用が、クロネッカー積の一次作用へ落ちることを意味する。したがって回帰やテンソル推定の式変形で、設計行列がクロネッカー積として現れることが多いのである。

固有値・特異値にも保存則がある。$A$ の固有値を ${\lambda }_i$、$B$ の固有値を ${\mu }_j$ とすると、$A\otimes B$ の固有値は ${\lambda }_i{\mu }_j$ で与えられる（対角化可能性などの条件の下で明確になる）。特異値についても、$\sigma (A\otimes B)$ は $\sigma (A)$ と $\sigma (B)$ の積の全組合せとして現れるため、条件数の見積りが容易になるのである。

計算面では、$A\otimes B$ を作らずに $(A\otimes B)z$ を計算する形が鍵である。$z=\mathrm{vec}(X)$ と見なして上の恒等式を逆向きに使えば、$AX{B}^T$ の計算へ変換できる。よってメモリと計算量が、巨大行列のサイズではなく因子行列のサイズで決まるのである。

4.4　クロネッカー和による正弦変換と余弦変換

クロネッカー和は

$$A\oplus B=A\otimes I+I\otimes B$$

で定義される。特に2次元ラプラシアンの差分離散化は、1次元差分作用素のクロネッカー和で表され、分離可能な構造を保つ。よって多次元偏微分方程式の離散化が、1次元問題の積み重ねとして扱えるのである。

例えば1次元の2階差分作用素を

$$T=\frac{1}{h^2}\mathrm{tridiag}(-1,2,-1)$$

とすると、2次元格子上のラプラシアンに対応する行列は

$$L=T\oplus T=T\otimes I+I\otimes T$$

となる。これにより、2次元の巨大系の固有値・固有ベクトルが、1次元の固有対から構成できるという利点が生まれるのである。

固有分解の保存則として、$Au=\lambda u$、$Bv=\mu v$ が成り立つなら、

$$(A\oplus B)(u\otimes v)=(\lambda +\mu )(u\otimes v)$$

となる。つまりクロネッカー和の固有値は和になり、固有ベクトルはテンソル積になる。したがって多次元のスペクトルが直積構造として整理でき、分離可能な高速解法が組み立てられるのである。

境界条件を含めると、固有基底として離散正弦変換（DST）や離散余弦変換（DCT）が自然に現れる。ディリクレ境界（端で値が0）に整合する基底が正弦になり、ノイマン境界（端で微分が0）に整合する基底が余弦になる。よって、対応する変換を用いることで差分作用素が（同値な意味で）対角化され、線形方程式の解が周波数ごとの割り算へ還元されるのである。

次の表は、境界条件と基底の対応を整理したものである（実装の細部は規約で変化し得るが、対応の方向性は変わらない）。

境界条件（1次元）	固有基底の形	代表的変換
ディリクレ（端で0）	正弦	DST
ノイマン（端の勾配0）	余弦	DCT
周期	複素指数	DFT

画像圧縮でDCTが重要なのは、自然画像が低周波成分へエネルギーが集中しやすいことと、ブロック単位の境界条件が余弦基底と整合しやすいことに由来する。偏微分方程式のソルバでDST/DCTが重要なのは、境界条件を満たす固有基底に展開することで、作用素の逆を周波数領域で実行できるからである。

4.5　テプリッツ行列とシフト不変フィルタ

テプリッツ行列は、対角方向に一定な成分を持つ行列であり、

$$T=\left[\begin{array}{cccc}{t}_0& t_{-1}& \cdots & t_{-(n-1)}\\ t_1& t_0& \cdots & t_{-(n-2)}\\ ⋮& ⋮& \ddots & ⋮\\ t_{n-1}& t_{n-2}& \cdots & t_0\end{array}\right]$$

の形で表される。これは有限長の線形畳み込み（端では外側が0とみなされる状況）を行列積として表現したものであり、シフト不変フィルタが境界で破れることを行列構造として反映するのである。

長さ $n$ の信号 $x$ とフィルタ係数 $h$ に対し、線形畳み込みは $y=Tx$ と書ける。$T$ は $h$ から作られるテプリッツ行列であり、端の処理（ゼロ埋め、反射、外挿など）をどう定めるかで行列の形が変わる。したがってフィルタの数学的定義は、実際には境界条件を含む問題設定である。

巨大なテプリッツ系 $Tx=b$ を直接解くと重いため、構造を使った高速化が重要になる。代表的には、テプリッツ行列を巡回行列で近似し、FFTで前処理や反復法の1ステップを高速化する方法がある。巡回近似は周期境界を導入することで対角化可能にし、計算を周波数領域へ移すのである。

また、自己相関や共分散推定ではテプリッツ構造が自然に現れる。弱定常過程では自己共分散がラグ差にのみ依存するため、共分散行列がテプリッツになる。ゆえに時系列の推定や予測は、テプリッツ構造を保った最小二乗や正則化として組み立てられるのである。

テプリッツと巡回の差は、境界の扱いに集約される。信号が周期であると仮定すれば巡回行列が正確なモデルになり、そうでなければテプリッツが自然である。よって、問題の物理やデータ生成過程に即した境界条件を選ぶことが、行列構造の選択に相当するのである。

4.6　グラフとラプラシアンとキルヒホッフの法則

重み付き無向グラフ $G=(V,E)$ に対し、重み行列 $W$ と次数行列 $D$ を

$$W_{ij}=w_{ij},D_{ii}=\sum _j{w}_{ij}$$

で定めると、グラフラプラシアンは

$$L=D-W$$

である。$L$ は対称半正定値であり、固有値が非負であるという性質が、エネルギーや滑らかさの最小化へ直結する。

二次形式は

$$x^{T}Lx=\frac{1}{2}\sum _{i,j}{w}_{ij}(x_i-x_j{)}^2$$

となり、隣接ノード間の差の二乗和として解釈される。よって $L$ は、グラフ上で滑らかな信号（近いノードほど値が近い）を好む正則化として機能するのである。

正規化ラプラシアンも重要である。対称正規化は

$$L_{\mathrm{sym}}=I-D^{-1/2}W{D}^{-1/2}$$

であり、ランダムウォーク正規化は

$$L_{\mathrm{rw}}=I-D^{-1}W$$

である。次数のばらつきが大きいグラフでは、正規化によりクラスタリングや拡散の性質が安定しやすくなる。

ラプラシアンは incidence 行列（接続行列）で表現できる。向きを付けた辺集合に対し incidence 行列 $B$ を作ると、

$$L=B^T{W}_{e}B$$

（$W_e$ は辺重みの対角行列）となり、$L$ が勾配（差分）と発散の合成であることが明確になる。これは連続のラプラシアン $\mathrm{\nabla }\cdot \mathrm{\nabla }$ の離散版としての意味を与えるのである。

電気回路との対応では、ノード電位 $v$ と注入電流 $i$ が

$$Lv=i$$

で結ばれる。これはキルヒホッフの電流則（各ノードで流入出の和が0）とオーム則（電位差に比例して電流が流れる）をまとめた線形方程式であり、ネットワーク問題がラプラシアン系へ帰着することを示す。

ラプラシアンの零固有値は連結成分の数を与える。具体的には、無向グラフが $c$ 個の連結成分を持つとき、$L$ の零固有値の重複度は $c$ である。したがってスペクトルはグラフの大域的構造を直接に反映するのである。

行列木定理は、$L$ の任意の余因子（1行1列を削除した行列の行列式）が、重み付き全域木の総和に等しいことを述べる。これはスペクトル・行列式が組合せ構造を数えるという強い結び付きを与え、ネットワークの冗長性や信頼性を評価する数学的基盤となるのである。

4.7　スペクトラル法と k 平均法によるクラスタリング

スペクトラルクラスタリングは、データ点をノードとし、類似度から重み付きグラフを作り、ラプラシアンの固有ベクトルで埋め込みを作った上で $k$ 平均法を適用する方法である。幾何学的に非凸な形状でも、グラフ上の近接性が適切に表現されていれば、固有ベクトルが分離しやすい表現を与えるのである。

基本的な構成は次の通りである。まず類似度 $w_{ij}$ を設計し、例えばガウスカーネル

$$w_{ij}=\exp (-\frac{\parallel x_i-x_j{\parallel }_2^2}{2{\sigma }^2})$$

や $k$ 近傍での接続などで重み行列 $W$ を作る。次に $L$ または $L_{\mathrm{sym}}$ を構成し、その小さい固有値に対応する固有ベクトルを $k$ 本取り、行を正規化して $k$ 平均を行うのである。

理論的には、グラフカットの最適化が固有問題へ緩和される。例えば正規化カット（Normalized Cut）は、離散的な割当て変数の組合せ最適化であるが、連続緩和を行うとラプラシアンの固有ベクトルが最適解の候補になる。したがって固有ベクトルは、分割問題を凸に近い形へ移した結果として現れるのである。

$k$ 平均法自体は、与えられた表現空間でクラスタ中心との二乗距離和を最小化する。スペクトラル法が重要なのは、元空間で $k$ 平均がうまくいかない状況でも、固有ベクトル空間ではクラスタがほぼ線形分離される場合がある点にある。これは、グラフ上の拡散やランダムウォークの遅いモードが、クラスタ間のボトルネックを表すためである。

正規化の選択も数学的意味を持つ。$L$ は値の差分を直接測るのに対し、$L_{\mathrm{sym}}$ は次数によるスケーリングを取り入れ、密度の偏りに対して頑健になりやすい。ランダムウォーク $P=D^{-1}W$ を考えると、$L_{\mathrm{rw}}=I-P$ であり、小固有値は長時間の遷移で残るモードに対応するため、確率過程としての解釈が得られるのである。

大規模データでは固有ベクトル計算が支配的になるため、第2章の反復法や乱択法が重要になる。特に上位ではなく下位固有ベクトルが必要である点が特徴であり、シフト付き反復やLanczos法、前処理などが効果を持つ。類似度行列を疎に構成することも、計算量と記憶量を決める要因になるのである。

4.8　ランク1 行列の補完

ランク1行列は

$$X=u{v}^T(u\in {\mathbb{R}}^m,v\in {\mathbb{R}}^n)$$

の形で表され、最も単純な低ランク構造である。観測が欠けた状況で $u,v$ を推定する問題は、行列補完の最小例として、同定可能性とアルゴリズムの性質を理解する上で有用である。

観測集合 $\mathrm{\Omega }$ に対し、$X_{ij}$ が $(i,j)\in \mathrm{\Omega }$ のみ観測されるとすると、条件は

$$u_i{v}_j=M_{ij}((i,j)\in \mathrm{\Omega })$$

である。これは未知が $m+n$ 個で方程式が $|\mathrm{\Omega }|$ 本という構造だが、$u,v$ のスケール不定性（$u\leftarrow \alpha u,v\leftarrow {\alpha }^{-1}v$ で同じ $X$）があるため、自由度は実質 $m+n-1$ になるのである。

同定可能性は、$\mathrm{\Omega }$ のグラフ構造で理解できる。二部グラフとして、行ノードと列ノードを辺 $\mathrm{\Omega }$ で結ぶと、連結でない成分がある場合、成分ごとにスケールが独立に動きうるため一意性が失われる。したがって観測パターンの連結性が、低ランク補完における根本条件の一つになるのである。

推定は非凸になりやすい。最小二乗で

$$\underset{u,v}{min}\sum _{(i,j)\in \mathrm{\Omega }}(u_i{v}_j-M_{ij}{)}^2$$

と書くと、$u$ と $v$ の積が現れるため同時最適化は非凸である。ただし $u$ を固定すれば $v$ は線形最小二乗、$v$ を固定すれば $u$ は線形最小二乗となるため、交互最小二乗（ALS）が自然に導かれるのである。

ノイズを含む場合には正則化が有効である。例えば

$$\underset{u,v}{min}\sum _{(i,j)\in \mathrm{\Omega }}(u_i{v}_j-M_{ij}{)}^2+\lambda (\parallel u{\parallel }_2^2+\parallel v{\parallel }_2^2)$$

はスケールの暴れを抑え、推定の安定性を改善する。これは核ノルム正則化と深い関係を持ち、一般の低ランク補完にも同型の設計が拡張されるのである。

ランク1は単純であるが、欠損が偏ると推定が急に不安定になる。ある行や列がほとんど観測されない場合、その成分は他から拘束されず推定誤差が大きくなる。よって観測の配置が、ランクそのものと同程度に復元の難易度を支配するのである。

4.9　直交プロクラステス問題

直交プロクラステス問題は、行列 $A,B\in {\mathbb{R}}^{d\times n}$ に対して

$$\underset{R}{min}\parallel RA-B{\parallel }_F\text{s.t.}{R}^{T}R=I$$

を解く問題である。$R$ は回転（反射を含む直交変換）であり、点集合や特徴表現の向きを合わせる操作として現れるのである。

解はSVDで与えられる。$B{A}^T=U\mathrm{\Sigma }{V}^T$ とすると

$$R^{\star }=U{V}^T$$

が最適解である。これは $\parallel RA-B{\parallel }_F^2=\parallel A{\parallel }_F^2+\parallel B{\parallel }_F^2-2\mathrm{tr}(RB{A}^T)$ を用い、$\mathrm{tr}(RB{A}^T)$ を最大化する問題へ帰着することで示されるのである。

回転のみ（反射を除く）を要求する場合は $det(R)=1$ の制約を追加する。これにより $R=U{\tilde{V}}^T$ の形で、最後の特異ベクトルの符号を調整する操作が入る。剛体運動の推定や三次元復元では、この差が幾何的意味を持つのである。

平行移動も含める場合は、点の重心を引いてから直交プロクラステスを適用するのが基本である。すなわち列平均を引いた $\tilde{A},\tilde{B}$ に対して回転 $R$ を求め、最後に重心の差で平行移動を戻す。これにより、距離を保った整列（剛体整列）が線形代数として完結するのである。

データサイエンスでは、埋め込み表現の整列に現れる。例えば異なる学習で得た特徴空間が、同じ意味構造を持ちながら回転している場合、プロクラステスにより空間を合わせて比較できる。SVDが幾何的整合を直接与える点で、分解と解釈が結び付いた代表例である。

4.10　距離行列

距離行列は点集合 $\{x_i{\}}_{i=1}^n$ に対して

$$D_{ij}=\parallel x_i-x_j\parallel$$

または二乗距離

$${\mathrm{\Delta }}_{ij}=\parallel x_i-x_j{\parallel }^2$$

を並べた行列である。距離は幾何を直接に表し、クラスタリング、可視化、カーネル法など多くの手法の入力として用いられるのである。

二乗距離行列と内積行列（グラム行列）の相互変換が基本である。点を行列 $X=[x_1,\dots ,x_n]\in {\mathbb{R}}^{d\times n}$ に並べ、グラム行列を $G=X^{T}X$ とすると、

$${\mathrm{\Delta }}_{ij}=G_{ii}+G_{jj}-2G_{ij}$$

が成り立つ。よって距離が分かれば内積が復元でき、内積が分かれば距離が復元できるのである。

多次元尺度構成法（MDS）はこの関係を用いる。中心化行列

$$H=I-\frac{1}{n}\mathbf{1}{\mathbf{1}}^T$$

を用いると、二乗距離行列 $\mathrm{\Delta }$ から中心化されたグラム行列が

$$G_c=-\frac{1}{2}H\mathrm{\Delta }H$$

で得られる。$G_c$ を固有分解して正の固有値に対応する成分を取れば、ユークリッド空間への埋め込み座標が得られるのである。

距離行列がユークリッド距離として整合するためには条件がある。中心化後の $G_c$ が半正定値であることが必要であり、負の固有値が出る場合は、与えられた距離がユークリッド距離ではないか、ノイズや誤差が距離を歪めていることを示唆する。したがって距離から幾何を作る操作は、固有値の符号と大きさを通じて整合性を判定できるのである。

距離と内積の変換はカーネル法にも直結する。カーネル行列 $K$ は内積を一般化したものであり、$K$ が半正定値であれば特徴空間での内積として解釈できる。距離ベースのカーネル（例えばRBFカーネル）は距離から内積構造を作る操作であり、距離行列の性質が学習の安定性へ反映されるのである。

距離行列はグラフにも接続する。例えば最短路距離から距離行列を作ると、グラフ上の幾何を連続空間へ埋め込む議論が可能になる。さらに有効抵抗距離はラプラシアンの擬似逆 $L^{+}$ を用いて

$$R_{ij}=(e_i-e_j{)}^T{L}^{+}(e_i-e_j)$$

と書け、スペクトルと距離が同じ式で結ばれるのである。

本章では、フーリエ・巡回・クロネッカー・テプリッツ・ラプラシアン・距離行列など、構造が明確な行列が持つ対角化・分離・低ランク性の性質を、計算可能性と解釈可能性の双方から述べたのである。次章では、これらの行列が確率・統計の中でどのように現れ、平均・分散・共分散・多変量分布が線形代数として統一的に書けることを扱うのである。

第5章：確率と統計

本章では、確率変数と分布を言葉ではなく数式で扱うための基礎を、平均・分散から多変量分布とマルコフ連鎖まで一貫して述べるのである。線形代数で現れた内積・ノルム・固有値は、共分散行列や二次形式として確率論の中心に現れ、推定と学習の理屈を支えるのである。

5.1　平均と分散と確率

確率論の出発点は確率空間 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ である。$\mathrm{\Omega }$ は起こり得る事象の集合、$\mathcal{F}$ は事象の族（$\sigma$-代数）、$\mathbb{P}$ は事象へ確率を割り当てる測度であり、$\mathbb{P}(\mathrm{\Omega })=1$ と可算加法性を満たすのである。

確率変数 $X$ は $X:\mathrm{\Omega }\to \mathbb{R}$ の写像であり、平均（期待値）は

$$\mathbb{E}[X]={\int }_{\mathrm{\Omega }}X(\omega )d\mathbb{P}(\omega )$$

で定義される。離散の場合は $\mathbb{E}[X]=\sum _{x}x\mathbb{P}(X=x)$、連続の場合は密度 $p(x)$ を用いて $\mathbb{E}[X]=\int xp(x)dx$ と書けるのである。

分散は

$$\mathrm{Var}(X)=\mathbb{E}[(X-\mathbb{E}[X]{)}^2]$$

であり、不確かさの大きさを二乗平均として表す。計算上は

$$\mathrm{Var}(X)=\mathbb{E}[X^2]-\mathbb{E}[X{]}^2$$

が頻用され、平均と2次モーメントが分かれば分散が求まるのである。標準偏差 $\sigma =\sqrt{\mathrm{Var}(X)}$ は元の単位へ戻した尺度であり、誤差やノイズの大きさの比較に用いられる。

期待値の基本性質として線形性

$$\mathbb{E}[aX+bY]=a\mathbb{E}[X]+b\mathbb{E}[Y]$$

が成り立つ。分散は線形ではないが、独立であれば加法性

$$\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$$

が成り立つ。独立性がない場合は共分散が現れ、

$$\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)+2\mathrm{Cov}(X,Y)$$

となるのである。

確率の基本操作として、条件付き確率と全確率の公式がある。$\mathbb{P}(B)>0$ のとき

$$\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}$$

であり、分割 $\{B_i\}$ に対して

$$\mathbb{P}(A)=\sum _i\mathbb{P}(A\mid B_i)\mathbb{P}(B_i)$$

が成り立つ。これらは推定や分類で現れる事後確率の計算を支えるのである。

統計に入ると、母数と標本の区別が重要になる。独立同分布（i.i.d.）の標本 $X_1,\dots ,X_n$ に対し、標本平均

$$\overline{X}=\frac{1}{n}\sum _{i=1}^n{X}_i$$

は母平均 $\mu =\mathbb{E}[X]$ の推定量である。大数の法則により $\overline{X}\to \mu$（確率収束などの意味で）となり、平均は標本数を増やすことで安定化するのである。

分散の推定では自由度補正が現れる。母分散を ${\sigma }^2$ とすると、標本分散

$$s^2=\frac{1}{n-1}\sum _{i=1}^n(X_i-\overline{X}{)}^2$$

は $\mathbb{E}[s^2]={\sigma }^2$ を満たす不偏推定量である。一方で $\frac{1}{n}\sum (X_i-\overline{X}{)}^2$ は下方へ偏るため、推定量の目的（不偏性か、平均二乗誤差か）を意識して使い分ける必要があるのである。

平均のゆらぎは中心極限定理で与えられる。十分な条件の下で

$$\sqrt{n}\frac{\overline{X}-\mu }{\sigma }\Rightarrow \mathcal{N}(0,1)$$

が成り立ち、$\overline{X}$ の誤差はおおむね $O(n^{-1/2})$ の縮み方をする。したがって推定精度の改善には、データ数を4倍にして誤差を半分にするというスケールが現れるのである。

5.2　確率分布

分布は確率変数の生成法を数式で表したものであり、尤度や損失関数の形を通じて推定と学習の骨格を決める。離散分布は確率質量関数 $p(x)=\mathbb{P}(X=x)$、連続分布は確率密度関数 $p(x)$ を用いて表し、いずれも正規化条件

$$\sum _{x}p(x)=1,\int p(x)dx=1$$

を満たすのである。

基本となる離散分布としてベルヌーイ分布は

$$\mathbb{P}(X=1)=p,\mathbb{P}(X=0)=1-p$$

であり、二項分布は独立なベルヌーイ試行の和として

$$\mathbb{P}(S=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}$$

で与えられる。ポアソン分布は希な事象の回数として

$$\mathbb{P}(N=k)=e^{-\lambda }\frac{{\lambda }^k}{k!}$$

であり、二項分布の極限として現れるのである。

連続分布の中心は正規分布である。$X\sim \mathcal{N}(\mu ,{\sigma }^2)$ の密度は

$$p(x)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp (-\frac{(x-\mu {)}^2}{2{\sigma }^2})$$

であり、加法ノイズや誤差のモデルとして頻用される。指数分布は待ち時間として

$$p(x)=\lambda e^{-\lambda x}(x\ge 0)$$

を持ち、無記憶性 $\mathbb{P}(X>s+t\mid X>s)=\mathbb{P}(X>t)$ を満たす。ガンマ分布は指数の和として現れ、形状の柔軟性が高いのである。

分布は推定の式を通じて具体化される。観測データ $x_1,\dots ,x_n$ がパラメータ $\theta$ を持つ分布 $p(x\mid \theta )$ から独立に生成されたとすると、尤度は

$$L(\theta )=\prod _{i=1}^{n}p(x_i\mid \theta )$$

であり、最大化する $\theta$ が最尤推定である。計算では対数尤度

$$\ell (\theta )=\sum _{i=1}^n\log p(x_i\mid \theta )$$

を最大化する形に直すのが自然であり、積が和へ変換されることで最適化が容易になるのである。

分布選択は、負の対数尤度が誘導する損失関数を通じて直接に現れる。代表例を次の表にまとめるのである（定数項は省略する）。

観測モデル	条件付き分布	負の対数尤度（1点）	推定で現れる量
実数値＋ガウスノイズ	$\mathcal{N}(y;f,{\sigma }^2)$	$\frac{1}{2{\sigma }^2}(y-f{)}^2$	二乗誤差（${\ell }^2$）
実数値＋ラプラスノイズ	$\propto e^{-	y-f	/b}$
二値分類	$\mathrm{Bernoulli}(y;\pi )$	$-y\log \pi -(1-y)\log (1-\pi )$	交差エントロピー
カウント	$\mathrm{Poisson}(y;\lambda )$	$\lambda -y\log \lambda$	ログリンクと整合

この対応により、損失関数の形を恣意的に選ぶのではなく、ノイズや生成仮定として説明できるようになる。外れ値が多いと二乗誤差は大きく引きずられるが、ラプラス型は外れ値に対して感度が相対的に抑えられるため、分布仮定が推定の頑健性へそのまま反映されるのである。

さらに一般化すると、指数型分布族

$$p(x\mid \theta )=h(x)\exp (\eta (\theta {)}^{T}T(x)-A(\theta ))$$

が現れる。ベルヌーイ、ポアソン、正規（分散既知）などが含まれ、十分統計量 $T(x)$ が推定を要約する。統計量が低次元で閉じることは、計算と理論の両方を簡潔にするのである。

5.3　モーメントとキュムラントと統計の不等式

モーメントは分布の形を数で特徴づける。$k$ 次モーメントは $\mathbb{E}[X^k]$、中心モーメントは $\mathbb{E}[(X-\mu {)}^k]$ であり、$k=2$ は分散、$k=3$ は歪み、$k=4$ は尖りの尺度に関係するのである。

確率母関数としてモーメント母関数

$$M_X(t)=\mathbb{E}[e^{tX}]$$

がある。$M_X$ が $t=0$ の近傍で存在すれば、テイラー展開によりモーメントを生成する。さらにキュムラント母関数

$$K_X(t)=\log M_X(t)$$

を導入すると、その係数がキュムラントになる。キュムラントが重要なのは独立和に対して加法的である点であり、独立な $X,Y$ に対して

$$K_{X+Y}(t)=K_X(t)+K_Y(t)$$

が成り立つ。よって和の分布の近似や漸近評価が扱いやすくなるのである。

推定や学習では、確率的な偏差を制御する不等式が要になる。最も基本のマルコフ不等式は非負確率変数 $Z\ge 0$ に対して

$$\mathbb{P}(Z\ge a)\le \frac{\mathbb{E}[Z]}{a}(a>0)$$

である。これを $Z=(X-\mu {)}^2$ に適用するとチェビシェフ不等式

$$\mathbb{P}(|X-\mu |\ge t)\le \frac{\mathrm{Var}(X)}{t^2}$$

が得られ、分散のみから尾確率を上界できるのである。

独立な有界変数の平均の集中にはヘフディング不等式が現れる。$X_i\in [a_i,b_i]$ が独立なら

$$\mathbb{P}(\overline{X}-\mathbb{E}[\overline{X}]\ge t)\le \exp (-\frac{2n^2{t}^2}{\sum _{i=1}^n(b_i-a_i{)}^2})$$

となり、平均の偏差が指数的に小さくなることを示す。より精密には分散も使うベルンシュタイン型の不等式があり、尾の形状が改善されるのである。

確率論で頻出する単純な評価として和の評価（合併界）

$$\mathbb{P}\left(\bigcup _{j=1}^m{A}_j\right)\le \sum _{j=1}^m\mathbb{P}(A_j)$$

がある。多数の誤差事象を一括して抑えるときに用いられ、高次元統計で座標ごとの偏差を同時に抑える議論へ接続するのである。

これらの不等式は、乱択線形代数やランダム行列にも現れる。例えばランダムな射影でノルムが保たれるという主張は、確率的集中を用いて「ほとんど確実に」歪みが小さいことを示す形で支えられる。線形代数で扱ったノルムやスペクトル半径が、確率の上界にそのまま現れる点が重要である。

5.4　共分散行列と同時確率

多変量確率変数 $X\in {\mathbb{R}}^d$ の平均ベクトルを $\mu =\mathbb{E}[X]$ とすると、共分散行列は

$$\mathrm{\Sigma }=\mathbb{E}[(X-\mu )(X-\mu {)}^T]$$

で定義される。$\mathrm{\Sigma }$ は対称であり、任意のベクトル $a$ に対して

$$a^T\mathrm{\Sigma }a=\mathrm{Var}(a^{T}X)\ge 0$$

が成り立つため半正定値である。よって共分散行列は、線形結合の分散を与える行列として理解できるのである。

$\mathrm{\Sigma }$ の対角成分は各成分の分散、非対角成分は共分散

$$\mathrm{Cov}(X_i,X_j)=\mathbb{E}[(X_i-{\mu }_i)(X_j-{\mu }_j)]$$

であり、相関係数は

$${\rho }_{ij}=\frac{\mathrm{Cov}(X_i,X_j)}{\sqrt{\mathrm{Var}(X_i)\mathrm{Var}(X_j)}}$$

で規格化される。相関が0でも独立とは限らないが、正規分布では相関0が独立性と一致するという特別な性質があるのである。

標本からの推定では、データ行列 $X\in {\mathbb{R}}^{n\times d}$（行が標本、列が変数）を用い、中心化した行列を $\tilde{X}$ とすると標本共分散は

$$S=\frac{1}{n-1}{\tilde{X}}^T\tilde{X}$$

で与えられる。これはグラム行列の形であり、線形代数の視点では $S$ の固有分解がPCAに一致する。固有値は分散の大きさ、固有ベクトルは変動の主方向であるという解釈が自然に出るのである。

同時確率（結合分布）$p(x_1,\dots ,x_d)$ は依存構造を含む。条件付き分布は

$$p(x,y)=p(y\mid x)p(x)$$

と分解でき、ベイズ則

$$p(x\mid y)=\frac{p(y\mid x)p(x)}{p(y)}$$

が推論を与える。推定での事前分布 $p(x)$ は、未知量に対する制約を確率として表す方法であり、正則化と同値な形で現れることが多いのである。

依存構造を疎にする考え方として条件付き独立がある。例えば確率変数の集合で、ある変数を条件にすると他が独立になる構造は、グラフとして表現できる。ガウス型の場合、精度行列

$$\mathrm{\Theta }={\mathrm{\Sigma }}^{-1}$$

の非ゼロパターンが条件付き独立性に対応し、${\mathrm{\Theta }}_{ij}=0$ が「$i$ と $j$ は残りを条件に独立」を示す。ここでも行列の疎性が、推論の計算量と解釈可能性を同時に左右するのである。

共分散行列はスケーリングの影響を強く受けるため、標準化（白色化）が重要になることがある。白色化は $Z=W(X-\mu )$ により $\mathrm{Cov}(Z)=I$ を目指す操作であり、$W={\mathrm{\Sigma }}^{-1/2}$ が理想形である。これは第1章の直交化や第2章の数値計算と同様に、条件数を整える操作として理解できるのである。

5.5　多変量正規分布と重み付き最小二乗法

多変量正規分布 $X\sim \mathcal{N}(\mu ,\mathrm{\Sigma })$ は密度が

$$p(x)=\frac{1}{(2\pi {)}^{d/2}|\mathrm{\Sigma }{|}^{1/2}}\exp (-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu ))$$

で与えられる。指数部に現れる

$$(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu )$$

はマハラノビス距離の二乗であり、${\mathrm{\Sigma }}^{-1}$ が内積（計量）を定めると解釈できる。よって正規分布は「楕円形の等密度面」を持ち、その形が共分散行列により決まるのである。

多変量正規の重要な性質として、線形変換で閉じることがある。$Y=AX+b$ とすると

$$Y\sim \mathcal{N}(A\mu +b,A\mathrm{\Sigma }{A}^T)$$

である。したがって線形観測モデルの誤差伝播が明示的に追える。周辺分布（部分変数の分布）も正規であり、条件付き分布も正規になるため、推定が解析的に扱いやすいのである。

線形モデル $y=Ax+\epsilon$ を考え、$\epsilon \sim \mathcal{N}(0,\mathrm{\Sigma })$ とする。尤度最大化は

$$\underset{x}{min}(y-Ax{)}^T{\mathrm{\Sigma }}^{-1}(y-Ax)$$

に一致し、これは重み付き最小二乗（一般化最小二乗）である。$\mathrm{\Sigma }$ が ${\sigma }^{2}I$ なら通常の最小二乗へ戻り、誤差が同分散・無相関である仮定に対応するのである。

この最小化の一階条件は正規方程式

$$A^T{\mathrm{\Sigma }}^{-1}Ax=A^T{\mathrm{\Sigma }}^{-1}y$$

である。$A^T{\mathrm{\Sigma }}^{-1}A$ が正定値なら一意解があり、数値計算は第2章のQRやCholeskyへ接続する。${\mathrm{\Sigma }}^{-1}$ が入ることで内積が変わり、同じデータでも推定の重み付けが変化するのである。

計算上は前処理（白色化）が有効である。$\mathrm{\Sigma }$ の分解として $\mathrm{\Sigma }=L{L}^T$（$L$ は下三角）を取ると、

$$(y-Ax{)}^T{\mathrm{\Sigma }}^{-1}(y-Ax)=\parallel L^{-1}(y-Ax){\parallel }_2^2$$

となる。よって

$$\tilde{y}=L^{-1}y,\tilde{A}=L^{-1}A$$

と置けば、問題は通常の最小二乗

$$\underset{x}{min}\parallel \tilde{y}-\tilde{A}x{\parallel }_2^2$$

へ還元される。これは「相関のある誤差を、変換で無相関にする」という意味であり、線形代数として明快である。

さらに事前分布を入れるとMAP推定が現れる。例えば $x\sim \mathcal{N}(0,{\mathrm{\Lambda }}^{-1})$ を仮定すると、事後最大化は

$$\underset{x}{min}(y-Ax{)}^T{\mathrm{\Sigma }}^{-1}(y-Ax)+x^T\mathrm{\Lambda }x$$

となり、二次の正則化（リッジ型）を得る。ここでも正定値行列が内積を定め、推定が幾何として理解できるのである。

5.6　マルコフ連鎖

マルコフ連鎖は、状態 $X_t$ が直前の状態のみに依存する確率過程であり、

$$Pr(X_{t+1}=j\mid X_t=i)=P_{ij}$$

で表される。$P$ は確率遷移行列であり、各行が確率分布になるため

$$P_{ij}\ge 0,\sum _j{P}_{ij}=1$$

を満たす。時間発展は分布ベクトル $p_t$ を用いて

$$p_{t+1}^T=p_t^{T}P$$

と書け、確率過程が線形代数の反復として表現されるのである。

定常分布 $\pi$ は

$${\pi }^{T}P={\pi }^T,\sum _i{\pi }_i=1,{\pi }_i\ge 0$$

を満たす分布であり、固有値1に対応する左固有ベクトルである。連鎖が既約（どの状態からも他へ到達可能）かつ非周期であれば、初期分布に依らず $p_t\to \pi$ となり、長時間のふるまいが一意に定まるのである。

収束の速さはスペクトルで特徴づけられる。$P$ の固有値を $1={\lambda }_1,{\lambda }_2,\dots$ とすると、第二固有値の大きさが1に近いほど混合は遅くなり、差 $1-|{\lambda }_2|$（スペクトルギャップ）が大きいほど混合は速くなる。したがって反復法としての収束解析と同じ言葉で、確率過程の時間スケールが語れるのである。

グラフ上のランダムウォークは特に重要である。重み付きグラフで $P=D^{-1}W$ とすると、これは隣接ノードへ重みに比例して移動する過程であり、定常分布は ${\pi }_i\propto D_{ii}$ となる。正規化ラプラシアン

$$L_{\mathrm{rw}}=I-D^{-1}W=I-P$$

を用いると、$P$ の固有構造とラプラシアンの固有構造が直接につながり、拡散の遅いモードがクラスタ構造を反映するという第4章の議論が確率過程として裏付けられるのである。

可逆性（詳細釣り合い）も中心概念である。ある分布 $\pi$ に対して

$${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$$

が成り立つとき、連鎖は $\pi$ に関して可逆であり、解析が容易になる。多くのMCMC法はこの条件を満たすように設計され、複雑な分布からのサンプリングを可能にするのである。

マルコフ連鎖は推定や学習の計算にも現れる。反復による期待値評価、サンプリングに基づく近似、拡散としての平滑化などであり、行列の反復と確率の反復が同じ数式で記述できる点が重要である。したがって確率モデルを立てることは、同時に計算可能な反復構造を設計することでもあるのである。

本章では、期待値と分散から始めて、分布の選択が尤度と損失を決める流れ、共分散行列が線形代数として推定を統一する流れ、さらにマルコフ連鎖が反復行列として解析できることを示したのである。次章では、これらの推定や学習で現れた目的関数をどのように最小化するかを、凸性・双対性・勾配法の言葉で整理し、計算手順へ落とし込むのである。

第6章：最適化

本章では、推定や学習で現れる目的関数を最小化するための数学を、凸性・制約・双対性・反復法として整理するのである。線形代数で扱った正定値性、確率統計で現れた最尤推定や正則化が、最適化の言葉で統一され、計算手続きへ直結するのである。

6.1　最小化問題：凸性とニュートン法

最適化の基本形は

$$\underset{x\in {\mathbb{R}}^d}{min}f(x)$$

である。$f$ が滑らかであれば勾配 $\mathrm{\nabla }f(x)$ とヘッセ行列 ${\mathrm{\nabla }}^{2}f(x)$ が定義され、停留点は $\mathrm{\nabla }f(x)=0$ を満たす。停留点が最小か最大か鞍点かは ${\mathrm{\nabla }}^{2}f(x)$ の符号（固有値）で判定され、${\mathrm{\nabla }}^{2}f(x)\succ 0$ なら局所最小である。

凸性は局所情報から大域結論を得るための条件である。集合 $C$ 上で $f$ が凸とは、任意の $x,y\in C$ と $t\in [0,1]$ に対して

$$f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$$

が成り立つことである。凸であれば局所最小は大域最小であり、複雑な関数でも最小値の取り違えが起きないという強い性質を持つのである。

滑らかな凸関数には一次の特徴づけがある。$f$ が凸かつ微分可能なら

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$$

が任意の $x,y$ で成り立つ。これは接線が常に下から支えることを意味し、最適性条件として $\mathrm{\nabla }f(x^{\star })=0$ が大域最適性を示す根拠になるのである。

二次関数は最適化の基準系である。$Q\succ 0$ に対して

$$f(x)=\frac{1}{2}{x}^{T}Qx-b^{T}x$$

を最小化すると、最適性条件は

$$Qx=b$$

となり、正定値一次方程式に帰着する。したがって最適化の反復は、線形代数の反復解法（共役勾配法など）と同じ構造を持つのである。

ニュートン法は局所2次近似に基づく反復である。$x_k$ 周りの2次展開

$$f(x)\approx f(x_k)+\mathrm{\nabla }f(x_k{)}^T(x-x_k)+\frac{1}{2}(x-x_k{)}^T{\mathrm{\nabla }}^{2}f(x_k)(x-x_k)$$

を最小化すると、ニュートン方向 $p_k$ は

$${\mathrm{\nabla }}^{2}f(x_k)p_k=-\mathrm{\nabla }f(x_k)$$

の解として得られ、更新は

$$x_{k+1}=x_k+p_k$$

となる。最小化そのものが「毎回、正定値系を解く」問題へ落ちる点が本質である。

ニュートン法は適切な条件下で局所二次収束を示す。最適解の近傍でヘッセ行列が非特異かつ十分滑らかであれば、誤差が二乗で縮むため反復回数が少なくて済む。しかし、ヘッセ行列が不定（鞍点近傍）であったり、遠方では2次近似が悪かったりすると発散も起こり得る。そこで実用では、直線探索によりステップ長 ${\alpha }_k$ を選び

$$x_{k+1}=x_k+{\alpha }_k{p}_k$$

とするのである。

ヘッセ行列の解法が計算を支配するため、ニュートン法は数値線形代数と不可分である。大規模問題では ${\mathrm{\nabla }}^{2}f$ を明示せず、ヘッセ行列とベクトルの積 $v\mapsto {\mathrm{\nabla }}^{2}f(x)v$ のみで方向を近似する方法（準ニュートン法や共役勾配を内側に回す方法）が用いられる。これは第2章で扱う反復法・低ランク近似と同様の思想であり、行列を作らないことが計算可能性を決めるのである。

凸性の二次条件も重要である。$f$ が2回微分可能なら、$f$ が凸であることは

$${\mathrm{\nabla }}^{2}f(x)⪰0(\mathrm{\forall }x)$$

と同値である。強凸性はさらに

$${\mathrm{\nabla }}^{2}f(x)⪰mI$$

を満たすことであり、最小解の一意性と勾配法の収束率を与えるのである。

6.2　ラグランジュ乗数= コストの導関数

制約付き最適化の基本形は

$$\underset{x}{min}f(x)\text{s.t.}g(x)=0$$

である。制約があると、勾配ゼロだけでは解を特徴づけられない。ラグランジアン

$$L(x,\lambda )=f(x)+{\lambda }^{T}g(x)$$

を導入し、停留条件

$${\mathrm{\nabla }}_{x}L(x,\lambda )=0,g(x)=0$$

で解を特徴づけるのである。

幾何学的には、制約面 $g(x)=0$ 上での最小では、$\mathrm{\nabla }f(x^{\star })$ が制約の法線方向に含まれ、制約の勾配 $\mathrm{\nabla }{g}_i(x^{\star })$ の線形結合として表される。すなわち

$$\mathrm{\nabla }f(x^{\star })+\sum _i{\lambda }_i\mathrm{\nabla }{g}_i(x^{\star })=0$$

となり、$\lambda$ が接平面と法線方向の関係を調整する係数になるのである。

ラグランジュ乗数の解釈は感度である。制約を $g(x)=c$ として右辺を微小に変えるとき、最適値 $p(c)$ の導関数が

$$\frac{dp}{dc}=-{\lambda }^{\star }$$

として現れる（符号は定式化に依る）。したがって $\lambda$ は制約を1だけ緩めたときに目的値がどれだけ改善するかを表す。これは物理では反力、経済では影響価格として現れ、学習では正則化係数の解釈にも接続するのである。

不等式制約

$$h(x)\le 0$$

を含めると、KKT条件が中心になる。ラグランジアンを

$$L(x,\lambda ,\nu )=f(x)+{\lambda }^{T}g(x)+{\nu }^{T}h(x)$$

とし、条件は

$${\mathrm{\nabla }}_{x}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=0,g(x^{\star })=0,h(x^{\star })\le 0,{\nu }^{\star }\ge 0,{\nu }_i^{\star }{h}_i(x^{\star })=0$$

である。最後の相補性条件は、制約が効いていないときは乗数が0になることを示し、活性制約だけが最適性に関与するという意味を持つのである。

二次目的と線形制約は特に重要である。例えば

$$\underset{x}{min}\frac{1}{2}{x}^{T}Qx-b^{T}x\text{s.t.}Ax=c$$

では、KKT条件はブロック行列の一次方程式になる。

$$\left[\begin{array}{cc}Q& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}x\\ \lambda \end{array}\right]=\left[\begin{array}{c}b\\ c\end{array}\right]$$

よって制約付き最小化は、対称だが不定な線形系を解く問題へ帰着する。ここでの数値的難しさ（条件数、前処理、疎性の利用）が計算の成否を決めるのである。

正則化は制約の別表現でもある。例えば $\parallel x{\parallel }_2^2$ を罰するリッジは、制約 $\parallel x{\parallel }_2^2\le r$ の下の最小化と双対的に対応し、ラグランジュ乗数が正則化係数に対応する。従って「罰則項を足す」操作は、制約付き問題を無制約へ変換する手段として理解できるのである。

6.3　線形計画法，ゲーム理論，双対性

線形計画（LP）は

$$\underset{x}{min}{c}^{T}x\text{s.t.}Ax=b,x\ge 0$$

の形で表される。目的も制約も線形であるため、可行集合は多面体になり、最適解は多面体の頂点に存在する。よって最適化が組合せ的な構造を持つが、双対性により解析が非常に強力になるのである。

このLPの双対は

$$\underset{y}{max}{b}^{T}y\text{s.t.}{A}^{T}y\le c$$

である。弱双対性として、任意の可行解 $x$ と $y$ に対し

$$b^{T}y\le c^{T}x$$

が成り立つ。したがって双対可行解は目的値の下界（最小化の場合）を与え、解の良さを証明する手段になるのである。

強双対性は条件の下で最適値が一致することを述べる。LPでは可行性が満たされれば一般に強双対性が成立し、最適解 $x^{\star },y^{\star }$ で

$$c^T{x}^{\star }=b^T{y}^{\star }$$

となる。さらに相補性条件

$$x_i^{\star }(c_i-(A^T{y}^{\star }{)}_i)=0$$

が成り立ち、どの制約が効いているかが構造として読み取れるのである。

双対性は感度解析にも直結する。$b$ を少し変えると最適値がどう変わるかは双対解 $y^{\star }$ が与え、$c$ を変えるときは primal の構造が影響する。これは制約の影響度が双対変数として定量化されることを意味し、モデルの解釈にも役立つのである。

ゲーム理論のゼロ和ゲームはLPとして書ける。利得行列 $M$ に対し、行プレイヤーが混合戦略 $p$、列プレイヤーが $q$ を選ぶと期待利得は $p^{T}Mq$ である。ミニマックス定理により

$$\underset{q}{min}\underset{p}{max}{p}^{T}Mq=\underset{p}{max}\underset{q}{min}{p}^{T}Mq$$

が成立し、この値の計算はLPへ落ちる。混合戦略は確率ベクトルであるため、制約が線形で保たれるのである。

データサイエンスでは、双対はアルゴリズム設計の別表現を与える。支持ベクトル機械（SVM）は、マージン最大化の primal と、内積（カーネル）だけで表される dual の形を持つ。輸送問題や最適輸送でも、dual がポテンシャル関数として現れ、計算と解釈の中心になるのである。

双対ギャップ

$$c^{T}x-b^{T}y$$

は最適性の証明に使える。反復法で primal と dual の可行解を同時に更新できれば、この差が0へ近づくことを停止判定にできる。これは数値計算の誤差評価を理屈で支える重要な仕組みである。

6.4　最小へ向かって進む勾配降下法

勾配降下法（GD）は

$$x_{k+1}=x_k-{\eta }_k\mathrm{\nabla }f(x_k)$$

で更新する。ここで ${\eta }_k>0$ はステップ幅であり、局所情報のみで反復が進むため、大規模問題で基本となるのである。

勾配が最急降下方向であることは内積に依存する。ユークリッド内積 $⟨u,v⟩=u^{T}v$ の下では、一次近似

$$f(x+\mathrm{\Delta })\approx f(x)+\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }$$

を最も減らす単位ベクトルは $-\mathrm{\nabla }f(x)/\parallel \mathrm{\nabla }f(x){\parallel }_2$ である。したがって勾配法は「最も急に下がる方向へ小さく進む」という意味を持つのである。

解析の中心は滑らかさである。$\mathrm{\nabla }f$ が $L$-リプシッツ連続とは

$$\parallel \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y){\parallel }_2\le L\parallel x-y{\parallel }_2$$

である。このとき

$$f(x-\eta \mathrm{\nabla }f(x))\le f(x)-\eta (1-\frac{L\eta }{2})\parallel \mathrm{\nabla }f(x){\parallel }_2^2$$

が成り立ち、$0<\eta <2/L$ を取れば単調減少が保証される。よって $L$ は許されるステップ幅の上限を決めるのである。

強凸性を仮定すると収束率が評価できる。$f$ が $m$-強凸かつ $L$-滑らかであれば、固定ステップ $\eta =1/L$ で

$$f(x_k)-f(x^{\star })\le {(1-\frac{m}{L})}^k(f(x_0)-f(x^{\star }))$$

のような線形収束が得られる。比 $L/m$ は条件数に相当し、谷が細長いほど収束が遅くなるのである。

二次関数での挙動は明瞭である。$f(x)=\frac{1}{2}{x}^{T}Qx$（$Q\succ 0$）では、勾配法は

$$x_{k+1}=(I-\eta Q)x_k$$

という線形反復になる。固有分解 $Q=V\mathrm{\Lambda }{V}^T$ を用いると、各固有方向での縮み率は $|1-\eta {\lambda }_i|$ となり、最大固有値と最小固有値の比が大きいと、ある方向では進み過ぎ、別の方向では進みが遅いというジグザグが生じるのである。

前処理は内積を変える操作である。正定値行列 $M\succ 0$ を導入し

$$x_{k+1}=x_k-\eta M^{-1}\mathrm{\nabla }f(x_k)$$

とすると、$M$ による座標のスケーリングが入る。二次関数なら $M$ を $Q$ に近づけることで等方化され、収束が改善される。これは線形方程式における前処理付き反復と同一の考え方である。

座標降下法も同じ枠内にある。成分ごとに更新する方法は、疎なモデル（${\ell }^1$ 正則化など）で有効であり、1回の更新が軽い。勾配法の設計は、1回の更新コストと反復回数の交換条件を最小にすることへ帰着するのである。

6.5　確率的勾配降下法とADAM

大規模データでは、目的関数が和で表されることが多い。例えば経験損失

$$f(x)=\frac{1}{n}\sum _{i=1}^n{\ell }_i(x)$$

である。このとき全勾配 $\mathrm{\nabla }f(x)$ の計算は $n$ に比例して重く、反復を増やしにくい。そこでミニバッチ $B_k$ を取り、

$$g_k=\frac{1}{|B_k|}\sum _{i\in B_k}\mathrm{\nabla }{\ell }_i(x_k)$$

を勾配推定として用いるのが確率的勾配降下法（SGD）である。

SGDは

$$x_{k+1}=x_k-{\eta }_k{g}_k$$

で更新し、$g_k$ が不偏推定 $\mathbb{E}[g_k\mid x_k]=\mathrm{\nabla }f(x_k)$ を満たす状況で解析される。勾配にノイズがあるため、目的値は単調に下がらないこともあるが、1ステップが軽いため総計算として有利になり得るのである。

ステップ幅の設計が要である。凸最適化では、${\eta }_k$ を減衰させ

$$\sum _{k=1}^{\mathrm{\infty }}{\eta }_k=\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{\eta }_k^2<\mathrm{\infty }$$

のような条件を満たすと収束が保証される理論がある。実務では初期は大きく、後半は小さくするスケジュールが多く、学習率が誤差床を決める形になるのである。

モメンタム法は速度変数を導入する。代表形は

$$v_{k+1}=\beta v_k+(1-\beta )g_k,x_{k+1}=x_k-\eta v_{k+1}$$

であり、勾配方向の平均を取ることで谷方向に加速し、ノイズにもある程度平滑化効果を持つ。これは二次関数では重い球が斜面を転がるモデルとして解釈でき、振動の抑制に寄与するのである。

適応学習率は座標ごとにスケールを調整する。AdaGradは過去の二乗勾配和 $s_t$ を用いて

$$x_{t+1}=x_t-\eta \frac{g_t}{\sqrt{s_t}+ϵ}$$

の形にし、頻繁に現れる方向ではステップが小さくなる。これは疎な特徴が多い問題で効果を持つが、$s_t$ が単調増加して学習率が過度に小さくなることがある。

Adamは一次モーメントと二次モーメントの移動平均を併用する。勾配 $g_t$ に対し

$$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t,v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2$$

を計算し、初期バイアスを補正して

$${\hat{m}}_t=\frac{m_t}{1-{\beta }_1^t},{\hat{v}}_t=\frac{v_t}{1-{\beta }_2^t}$$

とし、

$$x_{t+1}=x_t-\eta \frac{{\hat{m}}_t}{\sqrt{{\hat{v}}_t}+ϵ}$$

で更新する。二次モーメントが座標ごとのスケール差を吸収し、一次モーメントがモメンタムとして働くのである。

Adamの性質は、勾配のスケールが座標で大きく異なる深層学習で有利になりやすい点にある。一方で、常に良い一般化を与えるとは限らず、最適解近傍での収束挙動や重み減衰との整合が重要になる。そこでAdamWのように、重み減衰を勾配から分離して扱う変種が用いられることも多いのである。

確率的最適化の理解には、確率統計の集中とノイズの分散が直接に関わる。ミニバッチが小さいほど $g_k$ の分散は大きくなり、探索は荒くなるが局所から抜けやすい面も出る。逆にミニバッチが大きいほど勾配は正確になるが、1ステップが重くなり、更新回数が減る。従って計算資源とノイズの性質の釣り合いが、収束点と到達速度を左右するのである。

次の表は更新の要点を整理したものである。

手法	更新の中心	使う統計量	進み方の特徴
GD	全勾配	なし	1回が重いが方向は安定
SGD	ミニバッチ勾配	勾配の不偏推定	1回が軽いが揺らぎを含む
Momentum	速度の蓄積	一次モーメント	振動を抑え谷方向に加速
AdaGrad/RMSProp	座標ごとの縮尺	二次モーメント	スケール差へ適応しやすい
Adam	一次＋二次モーメント	移動平均と補正	深層学習で扱いやすい傾向

本章では、凸性が大域最適性を保証すること、制約がラグランジュ乗数とKKT条件で整理できること、双対性が証明と感度を与えること、そして勾配法とその確率的拡張が大規模学習を可能にすることを示したのである。次章では、これらの最適化が実際に学習器の構成へどう組み込まれ、ニューラルネットワークの学習が連鎖律と勾配計算として実装されるのかを数式で述べるのである。

第7章：データからの学習

本章では、データから規則性を獲得して予測や識別を行う学習を、深層ニューラルネットワークを軸に数式で記述するのである。線形代数で現れた行列積・部分空間・ノルムと、確率統計で現れた尤度・損失、最適化で現れた勾配法が、同一の枠組みで結び付くことを確認するのである。

7.1　深層ニューラルネットワークの構成

深層ニューラルネットワークは、線形変換と非線形変換の合成として表される。入力 $h^{(0)}=x$ に対し、各層 $\ell =1,\dots ,L$ を

$$z^{(\ell )}=W^{(\ell )}{h}^{(\ell -1)}+b^{(\ell )},h^{(\ell )}={\varphi }^{(\ell )}\left(z^{(\ell )}\right)$$

と定義し、最終出力 $\hat{y}=h^{(L)}$ から損失 $L(\hat{y},y)$ を定めるのである。ここで $W^{(\ell )}$ は重み行列、$b^{(\ell )}$ はバイアス、${\varphi }^{(\ell )}$ は要素ごとの活性化関数である。

この形は、写像 $x\mapsto \hat{y}$ が行列の積と非線形の合成であることを意味する。線形代数の観点では、各層が張る列空間やヌル空間ではなく、ヤコビアン（微分）を通した局所的な線形近似が重要になる。すなわち、入力近傍での変化は

$$\hat{y}(x+\delta )\approx \hat{y}(x)+J(x)\delta$$

と書け、$J(x)$ の特異値が入力の微小変動がどれだけ増幅されるかを支配するのである。

活性化関数 $\varphi$ は表現力を与える中心要素である。もし全層が線形であれば全体は1つの線形変換 $W_{\mathrm{eq}}x+b_{\mathrm{eq}}$ に畳み込まれ、深さの意味が消える。したがって非線形性は不可欠であり、ReLU $\varphi (u)=max(0,u)$、tanh、シグモイドなどの選択は勾配伝播や表現の分割の仕方に影響するのである。

深さが増すと表現力が増すという主張は、合成が関数の形を細かく分割できることに対応する。ReLUネットワークの入力空間は多数の線形領域に分割され、それぞれで線形写像として振る舞う。従って深さは、低ランク近似のような単純な表現では捉えにくい複雑な境界を、線形片の組合せとして構成する能力を与えるのである。

一方で、深さは最適化の難しさも増やす。勾配は連鎖律により多層のヤコビアンの積として現れるため、ヤコビアンの特異値が1より小さい方向では勾配が減衰し、1より大きい方向では勾配が爆発し得る。これが勾配消失・勾配爆発として現れ、初期化や正規化、残差構造が重要になるのである。

初期化は、前向き信号と逆向き勾配のスケールを揃えるために設計される。例えば ReLU を仮定したとき、$W_{ij}^{(\ell )}$ を平均0の分布から

$$\mathrm{Var}(W_{ij}^{(\ell )})\approx \frac{2}{n_{\ell -1}}$$

となるように選ぶと、層を通る信号の分散が過度に変形しにくい。ここで $n_{\ell -1}$ は前層のユニット数であり、行列の列数に対応するのである。

正規化層は、内部表現の分布を整えることで学習を安定化させる。バッチ正規化はミニバッチ平均 ${\mu }_B$ と分散 ${\sigma }_B^2$ を用いて

$$\tilde{z}=\frac{z-{\mu }_B}{\sqrt{{\sigma }_B^2+ϵ}},h=\gamma \tilde{z}+\beta$$

と変換する。これは各層の座標系を動的に整える操作であり、条件数の改善と似た役割を果たすのである。

残差接続は、写像を

$$h^{(\ell )}=h^{(\ell -1)}+F^{(\ell )}(h^{(\ell -1)})$$

の形にする。これにより、恒等写像が常に含まれ、深さを増しても情報の通り道が確保される。線形化するとヤコビアンが $I+\mathrm{\nabla }F$ の形になり、勾配の過度な減衰が起きにくくなる点が重要である。

損失関数の選択も構成要素である。回帰では二乗誤差

$$L(\hat{y},y)=\frac{1}{2}\parallel \hat{y}-y{\parallel }_2^2$$

が基本であり、分類ではソフトマックスと交差エントロピーが基本である。クラス数 $K$、ロジット $a\in {\mathbb{R}}^K$ に対して

$$p_k=\frac{e^{a_k}}{\sum _{j=1}^K{e}^{a_j}},L=-\sum _{k=1}^K{y}_k\log p_k$$

と置くと、確率モデルとしての整合が得られ、勾配も解析しやすいのである。

最後に、正則化はネットワークの自由度を制御する。代表的には重みの ${\ell }^2$ 罰則

$$f(\theta )=\frac{1}{n}\sum _{i=1}^{n}L({\hat{y}}_i,y_i)+\lambda \sum _{\ell }\parallel W^{(\ell )}{\parallel }_F^2$$

があり、これは第6章のラグランジュ形式と同じである。ノルムを抑えることは、局所的なリプシッツ定数やスペクトルノルムを間接的に抑え、過度な増幅を避ける方向に働くのである。

7.2　畳み込みニューラルネットワーク

畳み込みニューラルネットワーク（CNN）は、空間構造を持つデータを効率よく扱うために、局所性と重み共有を組み込んだモデルである。2次元入力 $x$ とフィルタ $k$ の畳み込みを

$$(y{)}_{i,j}=\sum _{u,v}{k}_{u,v}{x}_{i-u,j-v}$$

と書くと、これは入力の局所領域に同一の線形作用素を滑らせる操作である。従ってCNNの核は、線形代数の言葉では特殊構造を持つ行列による線形変換である。

畳み込みは行列として表現できる。入力をベクトル化すると $y=Tx$ と書け、$T$ はテプリッツ型（境界条件次第で巡回近似も可能）の巨大な行列になる。実装上は $T$ を明示せずに畳み込み演算を行うが、理論上は第4章のテプリッツ行列や巡回行列の枠内で理解できるのである。

重み共有はパラメータ数を劇的に削減する。全結合層では $W$ が入力次元と出力次元の積の自由度を持つのに対し、畳み込みではフィルタサイズの自由度に制限される。これは、学習すべき写像が平行移動に対して同変であるという仮定をモデルへ埋め込むことに相当するのである。

同変性は数式で表せる。シフト作用素 $S$ に対して、畳み込み演算子 $\mathcal{C}$ は

$$\mathcal{C}(Sx)=S(\mathcal{C}x)$$

を満たす（境界の扱いに依存するが、中心思想は同じである）。この性質により、画像中の位置が異なる同種のパターンを同一のフィルタで検出でき、データ効率が改善されるのである。

ストライドとプーリングはダウンサンプリングである。ストライドは計算点を間引くことにより出力解像度を落とし、平均プーリングや最大プーリングは局所集約により表現を粗視化する。周波数領域の観点では、ダウンサンプリングは折り返し（エイリアシング）と関係するため、平滑化と組み合わせる設計が重要になるのである。

畳み込みの周波数領域表現は、第4章のフーリエ変換と直結する。巡回境界条件を仮定すると、畳み込みはDFTで対角化され

$$\hat{y}(\omega )=\hat{k}(\omega )\hat{x}(\omega )$$

となる。従ってフィルタは周波数ごとの増幅係数として解釈でき、低周波を通す平滑化や高周波を強調するエッジ抽出が自然に説明されるのである。

現代的CNNでは、畳み込みブロックに正規化や残差接続が組み合わされる。これは7.1で述べた勾配伝播の安定化と同じ理由であり、畳み込みが特殊行列であることと矛盾しない。むしろ、巨大行列の反復における前処理と同様に、学習の数値的性質を整える役割を担うのである。

さらに、チャネル次元の扱いはテンソル演算である。入力 $x\in {\mathbb{R}}^{H\times W\times C}$ に対し、複数フィルタで出力チャネルを作り、点ごとの線形結合（$1\times 1$ 畳み込み）でチャネル混合を行う。これは局所の空間処理とチャネルの線形代数を分離する構成であり、低ランク近似のような分解的発想とも親和性があるのである。

7.3　誤差逆伝播法と連鎖律

誤差逆伝播法は、合成写像の微分を効率よく計算する方法である。ニューラルネットワークは層の合成であるから、損失 $L$ の微分は連鎖律によりヤコビアンの積として表される。だがヤコビアンを明示的に作ると計算量が膨大になるため、局所的な微分を再利用しつつ、必要な形（ベクトルとの積）だけを計算するのである。

計算グラフの言葉で、前向き計算が中間変数を生成し、後ろ向き計算が随伴変数（感度）を伝播する。層 $\ell$ の出力 $h^{(\ell )}$ に対し、上流から来る勾配を

$${\delta }^{(\ell )}=\frac{\partial L}{\partial z^{(\ell )}}$$

と置くと、次の層へは

$$\frac{\partial L}{\partial h^{(\ell -1)}}=(W^{(\ell )}{)}^T{\delta }^{(\ell )}$$

が伝播する。ここで転置が現れる点は、内積に関する随伴（アジョイント）であり、線形代数の構造そのものである。

線形層 $z=Wx+b$ では、勾配は行列積で書ける。上流勾配を $\delta =\partial L/\partial z$ とすると

$$\frac{\partial L}{\partial W}=\delta x^T,\frac{\partial L}{\partial b}=\delta ,\frac{\partial L}{\partial x}=W^T\delta$$

となる。従って学習は、外積 $\delta x^T$ を大量に計算して重み行列を更新する過程であり、行列演算の効率が計算全体を支配するのである。

要素ごとの非線形 $h=\varphi (z)$ では、

$$\frac{\partial L}{\partial z}=\frac{\partial L}{\partial h}\odot {\varphi }^{\prime }(z)$$

となる（$\odot$ は要素積）。シグモイドやtanhは飽和域で ${\varphi }^{\prime }(z)$ が小さくなり勾配が減衰しやすいが、ReLUは $z>0$ で ${\varphi }^{\prime }(z)=1$ を持つため勾配が通りやすい。活性化選択が勾配伝播のスケールを変えることが数式で明示されるのである。

分類でよく使うソフトマックスと交差エントロピーは、組として勾配が簡潔になる。ロジット $a$、確率 $p=\mathrm{softmax}(a)$、正解ラベル $y$ に対し

$$L(a,y)=-\sum _k{y}_k\log p_k$$

とすると

$$\frac{\partial L}{\partial a}=p-y$$

が得られる。この形は数値的に安定であり、確率モデルとしての意味も明確であるため、学習の基本部品になっているのである。

逆伝播はヤコビアンの明示的構成を避け、ヤコビアン転置とベクトルの積を逐次計算する。これは線形代数で言えば、巨大行列の作用を明示せずに評価する反復法と同型である。従って深層学習の計算は、疎性やブロック構造を活かしつつ、必要な積だけを高速に計算するという数値計算の哲学に沿っているのである。

数値的安定性にも注意が要る。例えばソフトマックスでは $e^{a_k}$ がオーバーフローし得るため、

$$p_k=\frac{e^{a_k-\underset{j}{max}{a}_j}}{\sum _j{e}^{a_j-\underset{j}{max}{a}_j}}$$

のように平行移動不変性を用いて安定化する。これは解析上は同値でありながら計算を破綻させないための工夫であり、学習が数値計算であることを示しているのである。

7.4　ハイパーパラメータ：重大な決定

学習率、バッチサイズ、正則化係数、初期化、ネットワークの幅・深さ、活性化、正規化の有無などは、学習結果を大きく左右する。これらは単なる設定値ではなく、統計的にはバイアスと分散、最適化的には収束と安定性、線形代数的にはスペクトルと条件数に対応する。従ってハイパーパラメータは、モデル・データ・計算の三者の整合を取るための数学的選択と捉えるべきである。

学習率 $\eta$ は更新量のスケールを定める。大きすぎれば反復が不安定になり、小さすぎれば進みが遅くなる。滑らかな凸関数では $L$-滑らかさが上限を与えるが、深層学習では局所曲率が場所により大きく変化するため、一定学習率だけで全過程を説明しにくい。そこで減衰スケジュールやウォームアップなどにより、初期と後半で異なる時間スケールを与える設計が用いられるのである。

バッチサイズ $B$ は勾配推定の分散を支配する。$B$ が大きいほど $g$ は $\mathrm{\nabla }f$ に近づき反復は滑らかになるが、1回の計算量が増える。$B$ が小さいほどノイズが増えるが、探索が粗くなることで局所構造に対して過敏になりにくい面もある。これは第5章の集中不等式の言葉で、標本平均の分散が $1/B$ に比例して下がるという事実と整合するのである。

正則化係数 $\lambda$ は自由度の抑制度合いを決める。重み減衰（${\ell }^2$ 罰則）はノルムを縮め、局所的な増幅を抑える方向に働く。${\ell }^1$ 型の正則化は疎性を促し、特徴選択や頑健性に関係するが、最適化の難しさも変える。どの正則化が適切かは、データの生成仮定とモデルの表現の過剰さに依存するのである。

初期化は、学習の入り口で勾配の通りを決める。初期重みが大きすぎると活性化が飽和域へ入り勾配が弱くなりやすい。小さすぎると信号が弱くなり表現が育ちにくい。He型やXavier型のような分散設計は、層ごとの入力次元と出力次元に合わせてスケールを整える試みであり、行列の作用が層を通っても破綻しにくいようにしているのである。

ネットワークの幅と深さは、表現力と最適化性質を同時に変える。幅を増せばパラメータ数が増え、表現力は高まるが、過度に自由になるとデータへの当てはまりが強くなり得る。深さを増せば表現の階層化が進むが、勾配伝播の問題が増えるため、残差接続や正規化などの工夫がより重要になる。これらは単独で決めるのではなく、学習率や正則化と組で整合させる必要があるのである。

ドロップアウトは確率的にユニットを無効化する正則化である。訓練時にマスク $m$ を導入して

$$h=\varphi (z)\odot m,m_i\sim \mathrm{Bernoulli}(p)$$

のようにし、推定の揺らぎを通じて共適応を抑える。確率統計の観点では、モデル平均化に近い効果を持ち、最適化の観点ではノイズを追加して探索を変形するのである。

データ前処理や特徴スケーリングも影響が大きい。入力のスケールが大きく異なると、同じ学習率でも更新の実効スケールが座標ごとに変わる。これは条件数の悪化として現れ、勾配法の進みを妨げる。従って平均0・分散1への標準化や、画像での正規化は、学習を数値的に扱いやすい座標へ写す操作である。

評価指標と停止規則も設計要素である。訓練損失が下がり続けても、未観測データに対する誤差が改善しないことは起こり得る。そこで訓練用とは別に検証用データを設け、汎化誤差の推定を行う。これは第5章の推定の議論に沿っており、誤差のばらつきがどの程度かを意識する必要があるのである。

7.5　機械学習の世界

機械学習は、観測データから規則性を抽出し、未知データへの予測や推論を行う体系である。教師あり学習では入力 $x$ と出力 $y$ の対応から関数 $f_{\theta }$ を学び、教師なし学習では $x$ だけから構造（クラスタ、低次元表現、生成モデルなど）を学ぶ。強化学習では行動と報酬の相互作用から方策を学び、確率過程と最適化が前面に出るのである。

教師あり学習の基本は経験リスク最小化である。データ $(x_i,y_i)$ に対して

$$\underset{\theta }{min}\frac{1}{n}\sum _{i=1}^{n}L(f_{\theta }(x_i),y_i)+\mathrm{\Omega }(\theta )$$

を解く。ここで $\mathrm{\Omega }$ は正則化であり、推定の不安定さを抑える役割を持つ。これは第6章の無制約最適化として見えると同時に、第5章の最尤推定や事前分布としても解釈できるのである。

汎化とは、訓練データでなく真の分布に対する誤差が小さいことである。訓練誤差と汎化誤差の差は、関数族の大きさとデータ数に依存し、過度に柔軟なモデルでは訓練誤差が小さくても汎化が悪化し得る。従って学習は、表現力を増やすだけでは成立せず、正則化・データ拡張・モデル構造などで制約を与えることが不可欠である。

表現学習は、特徴を人手で設計するのではなく、データから中間表現 $h$ を獲得する考え方である。深層学習では $h^{(\ell )}$ が階層的表現となり、低層は局所的特徴、高層は抽象的特徴を担うことが多い。線形代数の言葉では、各層が非線形な写像で部分空間の取り方を変え、分離しやすい座標系へデータを写していると解釈できるのである。

自己教師あり学習は、教師信号を外部から与えずに、データ自身から学習課題を構成する。例えば一部の情報を隠して予測する課題や、異なる変換で得た表現を一致させる課題により、表現が獲得される。ここでは損失設計が中心となり、確率分布の仮定と情報の保存・不変性の仮定が、最適化問題の形として現れるのである。

モデルの評価では、目的に応じた指標が必要になる。分類では精度だけでなく適合率・再現率、ROCやAUCが用いられ、回帰ではMSEやMAEが用いられる。確率出力を扱うときは対数尤度や校正も重要であり、単に当たるかどうかではなく確率として整合しているかが問われる。これは第5章の確率モデルの選択が、評価の指標と直結することを意味するのである。

学習の計算は行列計算の集合である。前向き計算は主に行列積、逆伝播も行列積と要素積の組合せであるため、計算資源の制約が学習設計に強く影響する。大規模化に伴い、低精度演算、分散計算、近似法が用いられ、ここでも数値線形代数の観点が不可欠になるのである。

本章では、深層ネットワークが線形変換と非線形変換の合成として表され、勾配計算が転置を伴う行列演算として実装されることを示したのである。今後は、表現の設計（同変性や不変性の組込み）、確率モデルとしての整合、そして計算可能性の制約を同時に満たす形で、学習がより大規模・多様なデータへ広がると考えられるのである。

その他参考文献

• Gilbert Strang, Linear Algebra and Learning from Data, SIAM.
• MIT OpenCourseWare, 18.06 Linear Algebra, Lecture Notes / ZoomNotes.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press.
• Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.
• Emmanuel Candès, Justin Romberg, Terence Tao, Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information.
• Ulrike von Luxburg, A Tutorial on Spectral Clustering.
• Diederik P. Kingma, Jimmy Ba, Adam: A Method for Stochastic Optimization.
• Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, Gradient-Based Learning Applied to Document Recognition.
• David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams, Learning representations by back-propagating errors.
• Peter H. Schönemann, A generalized solution of the orthogonal Procrustes problem.