49
24

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

PCAとSVDの関係性を示す

Last updated at Posted at 2018-12-27

次元削減の手法である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番目の軸との掛け算で出てきます。

svd_2.png

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

svd_3.png

比較

$(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を呼び出しています。)

49
24
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
49
24

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?