PCAとSVDの関係性を示す

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

  - PCA
  - SVD
  - 比較

## PCA

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

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

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

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

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

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

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

```math
\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}$ の長さを変えればどれだけでも大きくできてしまうため、

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

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

```math
\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}$ の固有値問題

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

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

```math
\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)$ 式と同じく

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

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

<img src="https://qiita-image-store.s3.amazonaws.com/0/271209/848a940f-291f-c49f-b944-7225a9218554.png" width=90%>

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

<img src="https://qiita-image-store.s3.amazonaws.com/0/271209/4898d3db-0b9d-d7d7-6401-5cafad522a95.png" width=90%>

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

<img src="https://qiita-image-store.s3.amazonaws.com/0/271209/6486f918-ebae-2652-3dfc-f5e09514057c.png" width=95%>


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

```math
(\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では、

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

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

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

と表される行列になります。
詳しくは <a href='https://qiita.com/sakami/items/d01fa353b4e1f48623a8' target='_blank'>SVD（特異値分解）解説</a> を参照してください。
上のリンクでは各行をデータ点として捉えていますが、今回は各列がデータ点に対応すると考えます。

<img src="https://qiita-image-store.s3.amazonaws.com/0/271209/9e7b5f43-9e15-7d01-98ab-9a254e389d2e.png" width=100%>

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

![svd_2.png](https://qiita-image-store.s3.amazonaws.com/0/271209/eb252abe-9278-02af-acd2-a29212b1d8a5.png)

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

![svd_3.png](https://qiita-image-store.s3.amazonaws.com/0/271209/209c51cb-6736-5d45-cba4-8454e571042a.png)

## 比較

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

```math
\sigma_k = \sqrt{\lambda_k}
```

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

```math
\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}$ は直交し、

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

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

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

<img src="https://qiita-image-store.s3.amazonaws.com/0/271209/507fe76f-74b5-6241-aae7-e5a8fa2c71fc.png" width=60%>

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

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