部分空間法
機械学習を行うために、マシーンに食わせるデータを準備します。
その際にデータの次元数（大きさ）が小さい方がより学習に効果的なので、
$d$次元特徴ベクトル空間を重要な情報をもつ$r(≤d)$次元空間に縮小します。
9章では、教師なし学習次元削除手法の
主成分分析、特異値分解、 部分空間法、カーネル主成分分析、カーネル部分空間法
について取り上げています。
部分空間法、カーネル主成分分析、カーネル部分空間法は難しいので後半に分けます。
なお、はじめてのパターン認識 第４章 確率モデルと識別関数 前半（観測データの線形変換）の話と通じていますので先にご覧ください。
9.1 部分空間 (Subspace)
ある構造を持った集合Xについて、空間と呼ばれる構造を保つための部分集合のこと。
１次結合
線形結合、線形和ともいう。ベクトルの定数倍と加え合わせ。
例 2次元数ベクトル $V = (2,3)$と $W = (1,2)$を用いて、$2V + 3W$ としたら$(7,12)$というベクトルが作れる。
d次元ベクトル空間Vの部分空間の定義は、
$x_1,....x_r (≤ d)$を$V$のベクトルとする$x_1,....x_r$の１次結合全体の集合。
$W = {a_1x_1 + ... a_rx_r | a_i ∈ R, i = 1, ....r}$ は$V$の部分空間となる。
つまり、$W$が$x_1,....x_r$で張られる$r$次元の部分空間であるとは$x_1,....x_r$は1次独立。
どの$x_i$も他の$r -1$個の$x_j (j ≠ i)$の線形結合で表すことができないということである。
上記の部分空間の定義から、$W$が$V$の部分空間であるための必要十分条件は、
- $W ≠ θ$
- $x,y \in W \Rightarrow x + y \in W$
- $x \in W, \lambda \in R \Rightarrow \lambda x \in W$
ということが成り立っている。
下記は部分空間への射影ベクトルとその直交成分
9.2 主成分分析 (Principal Component Analysis PCA)
主成分分析は共分散行列の固有値問題を解き、大きな固有値を持つ固有ベクトルで部分空間を構成して、元の情報を表現する。目的は，なるべく少ない合成変数で，なるべく多くの情報を把握するという情報の縮約である。
分散 (variance)
各データが平均値（期待値）からどれだけ離れて散らばっているかを示すもの
通常平均値とデータの距離の二乗の平均で求める
共分散 (covariance)
複数の対応するデータ群での平均とデータ群内の各データの差を掛けあわせて平均を取ったもの
分散・共分散行列 (variance・covariance matrix)
ある変数xの分散は共分散としてはxとxの共分散と表すことができるので、
それらを含んだ共分散行列
標準偏差 (standard deviation)
分散は符号の影響を排除し、ばらつきの大きさのみを見るため二乗しているもの
標準偏差は元データの単位と同様になるよう分散の正の平方根を取ったもの
固有値問題 (eigenvalue problem)
線形変換の固有値、及び固有ベクトルを求める問題
寄与率 (contributing rate)
観測データの全情報量に対してどの程度の情報量を個々の主成分が集めたかを示す比率
累積寄与率 (cumulative contribution ratio)
比率が大きい順番に固有値を足し算をした積算量を全情報量で割り算した比率になっている
取り上げたいくつかの主成分はもとの全情報量の何割になっているかを示す指標で、取り上げた主成分でどれくらい説明できたかどうか判断する指標
第1主成分
X軸とY軸の散布図を書いて、点々の真中ほどに直線を引いたもの
第2主成分
XとYの平均値（重心）を通って、第1主成分である直線に直角の線を引いたもの
学習データ$x_i=(x_i1,...x_id)^{\mathrm{T}}(i = 1,...,N)$の分散が最大になる方向への線形変換を求める手法。
N個のデータからなるデータ行列を$X = (x1,...x_N)^{\mathrm{T}}$、それから平均ベクトル$\bar{x}=(\bar{x_1}...,\bar{x_d})^{\mathrm{T}}$を引き算したデータ行列を$\bar{X}=(x_1 - \bar{x}....,x_N - \bar{x})^{\mathrm{T}}$とすると、
\sum = Var\{\bar{X}\} = \frac{1}{N}\bar{X}^{\mathrm{T}}\bar{X}\
で定義される。
$N$個のデータ$x_i - \bar{x}$を$係数ベクトルa_j$ = $(a_{j1}...a_{jd})^{\mathrm{T}}(j = 1....,d)$を用いて線形変換すると、
s_j = (s_{1j},....s_{Nj})^{\mathrm{T}} = \bar{Xa}_j
が得られる。この変換後のデータの散文は、$s_{1j},....s_{Nj}$の平均が0となるので、
Var\{{s_j}\} = \frac{1}{N}{s}_j^Ts_j = \frac{1}{N}(\bar{Xa}_j)^{\mathrm{T}}(\bar{Xa}_j) = \frac{1}{N}{a}_j^T\bar{X}^{\mathrm{T}}\bar{Xa}_j = a_j^TVar\{{\bar{X}\}}a_j \
となる。この分散が最大となる射影ベクトルは、係数ベクトル$a_j$のノルムを1に制約したラグランジェ関数
E(a_j) = a_j^TVar\{{\bar{X}\}}a_j - \lambda(a_j^T - 1)
を最大にする$a_j$を見つければよい、$\lambda$はラグランジェ未定定数である、$a_j$で微分して0としておけば、
$\frac{\partial E(a_j)}{\partial a_j} = 2Var{{\bar{X}}}a_j - 2\lambda a_j = 0 $より$Var \{\bar{X}\}a_j = \lambda a_j$ (式9.2)
が得られる。これは、元のデータの共分散行列に関する固有値問題を解くことにより。分散最大となる射影ベクトル$a_j$が得られることを示している。
(式9.2)を解いて得られる固有値を$\lambda_1\geq...\geq\lambda_d$とし、対応する固有ベクトルを$a_1,...,a_d$とする。共分散行列が実対称行列であることから、固有ベクトルは相互に直交し、
a^T_ia_j = \delta = \left\{\begin{array}{rcr} 1 & (i = j) \\ 0 & (i \neq j) \end{array}\right.
が成り立つ。$\delta$はクロネッカーのデルタ。
元のデータの共分散行列は$d$×$d$の行列なので、得られる非ゼロ固有値の数は共分散行列のランクで決まり、最大$d$である。最大固有値に対応する固有ベクトルで線形変換した特徴の分散は、
Var\{{s_1}\} = a^T_1Var\{\bar{X}\}a_1 = \lambda _1a^T_1a_1 = \lambda _1
となり、最大固有値に一致する。最大固有値に対応する固有ベクトルで、線形変換された特徴量を第1成分という。$k$番目の固有値に対応する固有ベクトルで変換された特徴量を第$k$主成分という。変換された特徴量の分散は固有値に一致するので、全分散量は
V_{total} = \sum_{i=1}^d \lambda _i
となり、これは元データのもつ全分散量とも一致する。第$k$主成分の分散の全分散に対する割合
c_k = \frac{\lambda _k}{V_{total}}
を、第$k$成分の寄与率という。また、第$k$成分までの累積寄与率$\gamma _k$は
\gamma _k = \frac{\sum_{i=1}^k \lambda _i}{V_{total}}
で定義される。
9.3 特異値分解 (Singular Value Decomposition SVD)
行列を複数の行列の積に分解する手法として、グラム-シュミットの正規直交基底を得るためのQR分解がある。一方、主成分分析に密接に関連した行列の分解法に特異値分解(SVD)がある。任意の$n \times p$行列$X$は、
$X = U \Lambda V^{\mathrm{T}}$
= (u_1 u_2 ... u_p)
\left(
\begin{array}{cccc}
\sqrt{λ_1} & 0 & \ldots & 0 \\
0 & \sqrt{λ_2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & \sqrt{λ_p}
\end{array}
\right)
\left(
\begin{array}{cccc}
\upsilon^T_1 \\
\upsilon^T_2 \\
\vdots \\
\upsilon^T_p
\end{array}
\right)
のように三つの行列の積に分解することができる。これを、特異値分解という。
ここで、$U$は$XX^{\mathrm{T}}$の非ゼロ固有値に対応する固有ベクトルからなる、$n \times p$列正規直交行列である。$V$は、$X^{\mathrm{T}}X$の非ゼロ固有値に対応する固有ベクトルからなる、$p \times p$列正規直交行列である。$\Lambda$は、$XX^{\mathrm{T}}$または$X^{\mathrm{T}}X$の非ゼロ固有値の平方根（特異値という）を、$\lambda_1\geq \lambda_2 \geq ... \geq \lambda_p$の順に並べて対角要素とした$p \times p$対角行列である。
特異値分解と主成分分析の関係は、$n \times p$行列$X$を$p$個の属性をもつ$n$個のデータ（あらかじめ平均ベクトルが引かれているものとする）と考えれば、$X^{\mathrm{T}}X$は共分散行列であり、その固有値と固有のベクトルが$\lambda _i$と $\upsilon _i$そのものになっていることから明らかである。また、$X= U \Lambda V^{\mathrm{T}}$より$XV = U \Lambda$が成り立つことから、
(X\upsilon _1 \ \ X\upsilon _2 \ \ ... \ \ X\upsilon _p) = (\sqrt{\lambda _1 u_1} \ \ \sqrt{\lambda _2 u_2} \ \ ... \ \ \sqrt{\lambda _p u_p})
となる。データ行列を$\upsilon_1$で線形変換したベクトルが$\sqrt{\lambda_1u_1}$となるので、その分散は、
Var\{{X_\upsilon{_1}}\} = (X_\upsilon{_1})^{\mathrm{T}}(X_\upsilon{_1}) = \left( \sqrt{\lambda _1 u_1} \right)^{\mathrm{T}}\left( \sqrt{\lambda _1 u_1} \right) = \lambda_1
となり、第1主成分の最大固有値に一致し最大となる。
第1主成分から第$q(\leq p)$主成分までの$\upsilon_i$で構成された部分空間
\tilde{V} = (\upsilon_1 \ \ ... \upsilon_q)
へのデータ$X$の射影は$X\tilde{V}$は、共分散行列が
Var{\{X\tilde{V}\}} = (X\tilde{V})^{\mathrm{T}}(X\tilde{V}) = \tilde{V}^{\mathrm{T}}X^{\mathrm{T}}X\tilde{V} = \tilde{V}^{\mathrm{T}}V\Lambda^{\mathrm{T}}U^{\mathrm{T}}U\Lambda\tilde{V}^{\mathrm{T}}\tilde{V} \\ = \tilde{V}^{\mathrm{T}}V\Lambda^{\mathrm{2}}V^{\mathrm{T}}\tilde{V}
となる。$\tilde{V}^{\mathrm{T}}V$は、
\tilde{V}^{\mathrm{T}}V = \left(
\begin{array}{cccc}
\upsilon^T_1 \\
\vdots \\
\upsilon^T_q
\end{array}
\right) \ \
(\upsilon_1 \ \ ... \upsilon_q) = \left(
\begin{array}{cccc}
1 & 0 & \ldots & 0 & 0 & \ldots & 0 \\
0 & 1 & \ldots & 0 & 0 & \ldots & 0 \\
\vdots & \ddots & \ddots & 0 & \vdots & \vdots & \vdots \\
0 & \ldots & 0 & 1 & 0 & \ldots & 0
\end{array}
\right)
となるので、共分散行列は、
Var\{X\tilde{V}\} = \lambda^2_q
となる。$\Lambda_q$は、特異値分解の最初の$q$個の特異値以外を0とした対角行列である。$\Lambda$の代わりに$\Lambda_q$を用いた行列の分解
\tilde{X} = U\Lambda_qV^{\mathrm{T}} = \sum_{i=1}^q \sqrt{\lambda _i u_i u^T_i}
は、$X$のランク$q$の誤差最小という意味での最良近似となっている。