次元削減の手法である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を呼び出しています。)