主成分分析と特異値分解 - logical

　主成分分析および特異値分解の数学的背景を解説する。本稿は初歩的な確率論および大学初年度レベルの線形代数の知識を前提とする。

主成分分析
特異値分解

主成分分析

　 $X_1, \dots, X_n$ を確率変数とする。このとき、 $X_i$ と $X_j$ の共分散 $\mathrm{Cov}(X_i, X_j)$ を第 $(i, j)$ 成分とする $n \times n$ 行列

　 $P = \begin{pmatrix} \mathrm{Var}(X_1) & \mathrm{Cov}(X_1, X_2) & \cdots & \mathrm{Cov}(X_1, X_n)\\ \mathrm{Cov}(X_2, X_1) & \mathrm{Var}(X_2) & \cdots & \mathrm{Cov}(X_2, X_n)\\ \vdots & \vdots & \ddots & \vdots\\ \mathrm{Cov}(X_n, X_1) & \mathrm{Cov}(X_n, X_2) & \cdots & \mathrm{Var}(X_n)\\ \end{pmatrix}$

を $X_1, \dots, X_n$ の共分散行列という。これを $\Sigma$ とおく。
　 $\mathrm{Cov}(X_i, X_j)$ = $\mathrm{Cov}(X_j, X_i)$ であるので $\Sigma$ は対角行列となる。
　また、 $X_1, \dots, X_n$ の線形結合で表される確率変数
　 $Y = a_1X_1 + \cdots + a_nX_n$ ,
　 $Z = b_1Z_1 + \cdots + b_nZ_n$
　( $a_1, \dots, a_n, b_1, \dots, b_n$ は実数)
に対して $Y$ と $Z$ の共分散は

　 $\mathrm{Cov}(Y, Z) = (a_1, \dots, a_n) \Sigma \begin{pmatrix} b_1\\ \vdots\\ b_n \end{pmatrix}$

と計算できる。言い方を変えれば $\Sigma$ は $X_1, \dots, X_n$ が張る実ベクトル空間上の共分散で定義される二次形式に対応する行列となっている。
　任意の確率変数 $X$ に対して $\mathrm{Var}(X) \geq 0$ であるので共分散行列は非負正定値対称行列となる。よって $\Sigma$ は直行行列で対角化可能で固有値はすべて非負実数となる。この固有値を大きい順に並べて $\lambda_1, \dots, \lambda_n$ とおく。このとき $\lambda_i$ を $X_1, \dots, X_n$ の第 $i$ 主成分という。
　第 $i$ 主成分に対応する固有ベクトルから決まる $X_1, \dots, X_n$ の線形結合を $W_i$ とおく。このとき $W_1, \dots, W_n$ の共分散行列は対角行列となり、対角成分は $\lambda_1, \dots, \lambda_n$ となる。言い方を変えれば

　 $\mathrm{Var}(W_i) = \lambda_i,$
　 $\mathrm{Cor}(W_i, W_j) = 0, (i \neq j)$

が成り立つ。
　主成分分析とは主成分およびその固有ベクトルを求めることである。主成分に対応する固有ベクトルは上記のとおり共分散の意味でよい性質を持つ基底となる。 $X_1, \dots, X_n$ が多次元の観測データの各成分であるとき、主成分分析はデータの成分を線形変換することでデータの共分散の意味で簡潔な表現を与える。特に相対的に小さな主成分に対応する固有ベクトルをデータにおけるばらつきが小さいとして無視することでデータの次元の削減が可能となる。(ただし各成分の尺度がそろっている必要がある。)

特異値分解

　特異値分解とは複素数係数の行列に対する以下の定理で与えらえる分解のことをいう。

定理1
　 $M$ を複素数係数の $m \times n$ 行列とする。 $M$ のランクを $r$ とおく。
このとき $m$ 次ユニタリ行列 $U$ , $n$ 次ユニタリ行列 $V$ と正の実数 $\mu_1 \geq \cdots \geq \mu_r$ が存在して

　 $M = U\Sigma V^{\ast}$ ,
　( $\Sigma$ は $m \times n$ 行列で $1 \leq i \leq r$ に対して $(i, i)$ 成分が $\mu_i$ , それ以外の成分が0.)

が成立する。
　さらに上記の分解において $\mu_1 \geq \cdots \geq \mu_r$ は $M$ を定めれば一意に決まる。

証明
　 $M^{\ast}M$ はエルミート行列であるのでユニタリ行列によって対角化可能。また任意の $n$ 次元複素ベクトル $v$ に対して

　 $v^{\ast}M^{\ast} M v = (Mv)^{\ast} Mv \geq 0$

なので $M^{\ast}M$ は非負正定値。よって $M^{\ast}M$ の固有値はすべて非負実数。その固有値を大きい順に $\lambda_1, \dots, \lambda_n$ とおく。また $V$ を $n$ 次ユニタリ行列で $V^{\ast}M^{\ast} M V$ が対角行列でその対角成分が左上から順に $\lambda_1, \dots, \lambda_n$ となるものとする。このとき $V$ の第 $i$ 列ベクトルを $v_i$ とかくと

　 $M^{\ast}Mv_i = \lambda_i v_i$

が成り立つ。
　 $\lambda_1, \dots, \lambda_n$ のうちゼロでないものの個数を $s$ とし、 $1 \leq i \leq s$ に対して $m$ 次元ベクトル $u_i$ を

　 $u_i = \frac{1}{\sqrt{\lambda_i}}Mv_i$

で定義する。このとき、 $\{u_1, \dots, u_s\}$ はそれらで張られるベクトル空間の正規直交基底となっている。なぜならば

　 $u_i^{\ast} u_j = \frac{1}{\sqrt{\lambda_i \lambda_j}} (Mv_i)^{\ast} Mv_j = \frac{1}{\sqrt{\lambda_i \lambda_j}} v_i^{\ast} M^{\ast} Mv_j = \frac{\lambda_j}{\sqrt{\lambda_i \lambda_j}} v_i^{\ast} v_j = \frac{\lambda_j}{\sqrt{\lambda_i \lambda_j}} \delta_{i, j} = \delta_{i, j}$

となるからである。(ここで $\delta$ はKroneckerのデルタ関数。)
　 $u_{s+1}, \dots, u_m$ を $m$ 次元ベクトルで $\{u_1, \dots, u_s\}$ と合わせて $\mathbb{C}^{m}$ の正規直交基底となるものとする。 $U$ を $u_1, \dots, u_m$ を並べた行列とする。 $u_1, \dots, u_m$ が正規直交基底なので $U$ はユニタリ行列。
　このとき $U^{\ast} M V$ の第 $(i, i)$ 成分は $\sqrt{\lambda_i}$ でそれ以外の成分はゼロとなる。なぜならば $U^{\ast} M V$ の第 $(i, j)$ 成分 $= u_i^{\ast} M v_j$ であり

$i \leq s$ のとき
　 $u_i^{\ast} M v_j = \frac{1}{\sqrt{\lambda_i}} (M v_i)^{\ast} M v_j = \frac{1}{\sqrt{\lambda_i}} v_i^{\ast} M^{\ast} M v_j = \frac{\lambda_j}{\sqrt{\lambda_i}} v_i^{\ast} v_j = \frac{\lambda_j}{\sqrt{\lambda_i}} \delta_{i, j}$

$i > s$ かつ $j \leq s$ のとき
　 $u_i^{\ast} M v_j = \sqrt{\lambda_j} u_i^{\ast}u_j = 0$

$i > s$ かつ $j > s$ のとき
　 $(M v_j)^{\ast} M v_j = v_j^{\ast} M^{\ast} M v_j = \lambda_j = 0$ より $M v_j = 0$ よって $u_i^{\ast} M v_j = 0$

となるからである。
　 $\Sigma = U^{\ast} M V$ とおくと $M = U \Sigma V^{\ast}$ となるので、 $s = r$ が言えれば定理の前半が証明できたことになる。これは $M = U \Sigma V^{\ast}$ の両辺のランクを考えれば自明である。( $U, V$ はユニタリ行列なので右辺のランクは $\Sigma$ のランクと一致する。)
　あとは $\mu_1, \dots, \mu_r$ の一意性を証明すればよい。定理の条件を満たす分解 $M = U \Sigma V^{\ast}$ が与えられたとする。このとき

　 $V^{\ast} M^{\ast} M V = V^{\ast} V \Sigma^{\ast} U^{\ast} U \Sigma V^{\ast} V = \Sigma^{\ast} \Sigma = \begin{pmatrix}\mu_1^2 & & & \\ & \ddots & & \\ & & \mu_r^2 & \\ & & & O\end{pmatrix}$

となるので $\mu_1, \dots, \mu_r$ は $M^{\ast} M$ の固有値の平方根。即ち、上述の方法で得られたもの以外存在しない。
（証明終わり）

　定理1の $M$ の分解を $M$ の特異値分解といい、 $\mu_i$ を $M$ の第 $i$ 特異値という。
　特異値分解によって行列の低ランク近似が得られる。 $s < r$ とし、 $\Sigma'$ を第 $s$ 特異値までを対角成分に並べた行列とする。このとき $M' = U \Sigma' V^{\ast}$ はランク $s$ の $M$ とサイズの等しい行列となり、そのような行列の中である意味で最も良く $M$ を近似した行列となる。この近似の尺度を説明するために以下の定義を行う。