PCAとSVDの関係性を示す

次元削減の手法であるPCA（主成分分析）とSVD（特異値分解）の関係性について考えていきます。

• PCA
• SVD
• 比較

PCA

あるデータ点を $\boldsymbol{x}_i$ で表します。各次元は特徴量になります。
簡単のため、全データ点で各次元の平均が0になるような場合を考えます。

まず、データ点を1次元に削減する場合、PCAでは

z_i = \boldsymbol{u}^\mathrm{T}\boldsymbol{x}_i

の分散が最大になるように、データ点 $\boldsymbol{x}_i$ を変換するベクトル $\boldsymbol{u}$ を求めます。
全データ点について考えると、

\boldsymbol{z}^\mathrm{T} = \boldsymbol{u}^\mathrm{T}X \tag{1}

の分散を最大化します。
ここで、変換後の分布 $P(\boldsymbol{z})$ に正規分布を仮定しています。
正規分布のエントロピー（情報量）を最大化するには分散を最大化すればよいため、分散の最大化を目的にしています。

よって、最大化するべき目的関数は、

\begin{align}
  \sigma_z^2 &= \frac{1}{N} \sum_i z_i^2 \\
  &= \frac{1}{N} \sum_i \boldsymbol{u}^\mathrm{T}\boldsymbol{x}_i\boldsymbol{x}_i^\mathrm{T}\boldsymbol{u} \\
  &= \boldsymbol{u}^\mathrm{T} \left(\frac{1}{N} \sum_i \boldsymbol{x}_i\boldsymbol{x}_i^\mathrm{T} \right) \boldsymbol{u} \\
  &= \boldsymbol{u}^\mathrm{T} \sigma_x^2 \boldsymbol{u} \tag{2}
\end{align}

となります。
この値は、 $\boldsymbol{u}$ の長さを変えればどれだけでも大きくできてしまうため、

\boldsymbol{u}^\mathrm{T}\boldsymbol{u} = 1　\tag{3}

という制限を設けて、Lagrangeの未定乗数法を用いると、

\begin{align}
\frac{\partial \mathcal{L}}{\partial \boldsymbol{u}} &= \frac{\partial}{\partial \boldsymbol{u}} \left( \boldsymbol{u}^\mathrm{T} \sigma_x^2 \boldsymbol{u} - \lambda \left(\boldsymbol{u}^\mathrm{T}\boldsymbol{u} - 1 \right)  \right) \\
&= 2 \sigma_x^2 \boldsymbol{u} - 2 \lambda \boldsymbol{u}
\end{align}

なので、データ点の分散共分散行列 $\sigma_\boldsymbol{x}$ の固有値問題

\sigma_x^2 \boldsymbol{u} = \lambda \boldsymbol{u} \tag{4}

を解けばよいことがわかります。
ここで、$(4)$ 式の両辺に左から $\boldsymbol{u}^\mathrm{T}$ を掛けると、$(3)$ 式を用いて、

\begin{align}
\boldsymbol{u}^\mathrm{T} \sigma_x^2 \boldsymbol{u} &= \boldsymbol{u}^\mathrm{T} \lambda \boldsymbol{u} \\
&= \lambda \|\boldsymbol{u}\|^2 \\
&= \lambda
\end{align}

となることから、$(2)$ 式を参照すると、各固有値 $\lambda$ は、変換後の分散の大きさを表していることがわかります。

さて、これを高次元の場合に拡張するのは簡単で、$(1)$ 式と同じく

Z = U^\mathrm{T}X \tag{5}

という変換を考えた場合、$U$ が $XX^\mathrm{T}$ の固有ベクトルを並べた行列になるときに $Z$ の分散が最大になります。図で表すと、

$Z$、$X$ の各列が各データ点に対応し、$U^\mathrm{T}$ の各行が固有ベクトルに対応します。

これをm次元に削減するには、$U^\mathrm{T}$ の中で、固有値が大きい順にm個の固有ベクトルを選択して、$X$ を変換してやればよいです。

つまり、変換後の次元数がmの場合、

(\boldsymbol{z}_1, \boldsymbol{z}_2, \cdots, \boldsymbol{z}_n) =
\begin{pmatrix}
\boldsymbol{u}_1^{\mathrm{T}} \\
\boldsymbol{u}_2^{\mathrm{T}} \\
\vdots \\
\boldsymbol{u}_m^{\mathrm{T}}
\end{pmatrix}
(\boldsymbol{x}_1, \boldsymbol{x}_2, \cdots, \boldsymbol{x}_n)

となります。

SVD

SVDでは、

X = U \Sigma V^\mathrm{T} \tag{6}

という変形をします。
ここで、$U$ は $XX^\mathrm{T}$ の、$V$ は $X^\mathrm{T}X$ の固有ベクトルを並べた行列になります。$\Sigma$ は、特異値 $\sigma$ を用いて、

\Sigma = 
\begin{pmatrix}
\sigma_1 &          &        &          \\
         & \sigma_2 &        &          \\
         &          & \ddots &          \\
         &          &        & \sigma_n
\end{pmatrix}

と表される行列になります。
詳しくは SVD（特異値分解）解説 を参照してください。
上のリンクでは各行をデータ点として捉えていますが、今回は各列がデータ点に対応すると考えます。

リンク先でも書いたとおり、特異値 $\sigma$ は対応する軸の「重要度」みたいなものを表します。
例えば $\sigma_2$ を考えたときには、$X$ を計算するときの貢献は、2番目の軸との掛け算で出てきます。

つまり、 $\sigma$ の値が大きければ大きいほど、その軸が $X$ を表すのに重要である、と考えることができます。
大きい順にm個の特異値に対応する $V^\mathrm{T}$ の軸を選べば、もとのデータを次元削減することができます。

比較

$(5)$ 式における $U$ は $XX^\mathrm{T}$ の固有ベクトル行列であり、$(6)$ 式における $U$ と一致します。
また、特異値 $\sigma_k$ は $XX^\mathrm{T}$ の固有値 $\lambda_k$ を用いて、

\sigma_k = \sqrt{\lambda_k}

と表されるので、$(5)$ 式において大きい順にm個の固有値をとると、それは $(6)$ 式において大きい順にm個の特異値をとった場合に対応します。
よって、2つの式を比較することができ、$(6)$ 式に左から $U^\mathrm{T}$ を掛けると、

\begin{align}
U^\mathrm{T}X &= U^\mathrm{T} U \Sigma V^\mathrm{T} \\
&= \Sigma V^\mathrm{T}
\end{align}

ここで、 $U$ は実対称行列（$XX^\mathrm{T}$）の固有ベクトル行列なので、それぞれの $\boldsymbol{u}$ は直交し、

U^{\mathrm{T}}U = I

と書けることを使っています。（ $I$ は単位行列）

つまり、$(6)$ 式の表現で、変換後のデータを表す行列は、PCAでは $\Sigma V^\mathrm{T}$ となり、SVDでは $V^\mathrm{T}$ となります。
$\Sigma$ は対角行列なので、$V^\mathrm{T}$ の各行を $\sigma_k$ 倍する効果があります。

これは、もとのデータ点の各次元（各特徴量）が独立なときは、センチメートルで測っていたものをメートルになおすようなもので、意味がありません。

よって、PCAとSVDは、本質的に等価な処理をしている、ということができます。
（実は、scikit-learnのPCAも、内部ではSVDを呼び出しています。）