特異値分解によるベクトルの次元削減

# 内容
ゼロから作るDeep Learning 2の自然言語処理における次元削減の部分を理解した気分になる．
なぜ特異値分解（SVD）の$U$が密なベクトルとして使えるのかを考える．

# 次元削減の使い時
**疎なベクトルを密なベクトルにしたい！**というのが次元削減のモチベーション．
データを2次元で可視化するなど，他の目的もあります．

「**疎なベクトル**」とは，ほとんどの要素が0であるようなベクトル．情報を持たない要素が多い．

```math
\boldsymbol{x_1} = (1, 0, 0, 0, 0, 0, 0, 0)\\
\boldsymbol{x_2} = (0, 0, 1, 0, 0, 0, 0, 1)\\
\boldsymbol{x_3} = (0, 1, 0, 0, 0, 0, 0, 0)
```

「**密なベクトル**」とは，0である要素が少ないベクトル．多くの要素が情報を持っている．

```math
\boldsymbol{\hat{x}_1} = (0.8, 0.1, 0.1, 0.4)\\
\boldsymbol{\hat{x}_2} = (0.1, 0.2, 0.7, 0.5)\\
\boldsymbol{\hat{x}_3} = (0.6, 0.3, 0.1, 0.2)
```

※数字に意味はありません．

疎なベクトルには

- 次元数が多く計算量が膨大
- ノイズに弱い

といった問題があるため，次元を落として密なベクトルにしよう！ということ．
どのように次元を落とすかというと，**元のベクトルの情報をなるべく保持したまま**次元を落としたい．
上の疎なベクトルの例では4～7番目の要素は全て0だからなくなっても各ベクトルの情報は維持できるはず．
そこで登場するのが，特異値分解です．（他にも次元削減の方法はたくさんある）

# 特異値分解とは
詳しくは[以前の記事](https://qiita.com/KodaiS/items/b72ed968c480ee0f6aef)へ．

```math
X = U\Sigma V^T \quad \cdots (1)
```

のように，$n \times m$行列$X$を$n$次直交行列$U$，$m$次直交行列$V$，対角行列$\Sigma$に分解することを特異値分解と言います．
$\Sigma$の対角成分には$X$の特異値$\sigma_i$を大きい順，つまり$\sigma_i \geq \sigma_{i+1}$に並べます．


次元削減について考えるために，(1)式を成分表示して変形しておきます．ここで$U$の列ベクトルを$\boldsymbol{u}_j \ (j=1, 2, \cdots, n)$，$V$の列ベクトルを$\boldsymbol{v}_k \ (k=1, 2, \cdots, m)$，$\mathrm{rank}X = r$としています．

```math
\begin{align}
X &= 
(\boldsymbol{u}_1, \boldsymbol{u}_2, \cdots, \boldsymbol{u}_n)
\begin{pmatrix}
\sigma_1 & 0        & \cdots & 0        & 0       & \cdots & 0      \\
0        & \sigma_2 & \cdots & 0        & 0       & \cdots & 0      \\
\vdots   & \vdots   & \ddots & \vdots   & \vdots  &        & \vdots \\
0        & 0        & \cdots & \sigma_r & 0       & \cdots & 0      \\
0        & 0        & \cdots & 0        & 0       & \cdots & 0      \\
\vdots   & \vdots   &        & \vdots   & \vdots  &        & \vdots \\
0        & 0        & \cdots & 0        & 0       & \cdots & 0      \\
\end{pmatrix}
\left(
\begin{array}
\boldsymbol{v}_1^T \\
\boldsymbol{v}_2^T \\
\vdots             \\
\boldsymbol{v}_m^T
\end{array}
\right) \\
\end{align}
```

$\Sigma$の非ゼロ要素に対応する部分のみを残して，次のように表記することもあります．

```math
\begin{align}
X &= (\boldsymbol{u}_1, \boldsymbol{u}_2, \cdots, \boldsymbol{u}_r)
\begin{pmatrix}
\sigma_1 & 0        & \cdots & 0        \\
0        & \sigma_2 & \cdots & 0        \\
\vdots   & \vdots   & \ddots & \vdots   \\
0        & 0        & \cdots & \sigma_r \\
\end{pmatrix}
\left(
\begin{array}
\boldsymbol{v}_1^T \\
\boldsymbol{v}_2^T \\
\vdots             \\
\boldsymbol{v}_r^T
\end{array}
\right) \\ \\

&= U_0 \Sigma_0 V_0^T
\quad \cdots (2)
\end{align}
```

# 特異値分解による次元削減
次元削減を考えるために，(2)式を変形してみます．

```math
\begin{align}
X &= U_0 \Sigma_0 V_0^T \\ \\

&= \sigma_1 \boldsymbol{u}_1 \boldsymbol{v}_1
+ \sigma_2 \boldsymbol{u}_2 \boldsymbol{v}_2
+ \cdots
+ \sigma_r \boldsymbol{u}_r \boldsymbol{v}_r
\end{align}
```

$\sigma_i$が降順で並んでいることから，行列$X$を構成するうえで**先頭の項ほど重要な要素**であることがわかります．反対に**小さい$\sigma_i$を係数に持つ項は情報が少ない**ため，切り捨ててしまっても大きな影響はないと言えます．

このような考えから，$m$次元のPPMI行列を$q \ (1 \le q \le r)$次元に削減したい場合，上記の行列${U}_0$の$q$列目までの部分$\tilde{U}$を次元削減したをPPMI行列として利用しよう，というのがゼロつく2の中での説明です．

```math
\begin{align}
U_0 &= \begin{pmatrix}
u_{11} & \cdots & u_{1q} & \cdots & u_{1r} \\
\vdots &        & \vdots &        & \vdots \\
u_{n1} & \cdots & u_{nq} & \cdots & u_{nr}
\end{pmatrix} \\ \\

\tilde{U} &= \begin{pmatrix}
u_{11} & \cdots & u_{1q} \\
\vdots &        & \vdots \\
u_{n1} & \cdots & u_{nq}
\end{pmatrix}
\end{align}
```


# なぜ単語ベクトルとして使えるのか？
さて，次元圧縮したベクトルを取得する方法はわかりましたが，なぜ$U_0$から次元削減した単語ベクトルを取れるのかが疑問です．
この疑問の解決のために，(2)式の両辺に右から$V_0$をかけて次のように変形しておきます．

```math
X V_0 = U_0 \Sigma_0 \quad \cdots (3)
```

(3)式を見れば，データ行列$X$に直交行列$V_0$による線形変換（回転）を施したものが$U_0 \Sigma_0$であることがわかります．

では，行列$V$とは何かを考えるため$V$の求め方を見てみましょう．
特異値分解の(2)式を使って確認してみます．

```math
\begin{align}
X^T X &= (U \Sigma V^T)^T(U \Sigma V^T) \\ \\
&= V \Sigma^2 V^T
\quad \cdots (4)
\end{align}
```

$X^T X$は対称行列，また対角行列$\Sigma$は2乗しても対角行列です．という訳で，(4)式は固有値分解の形に一致しています．$X$がデータ行列だとすると，（データの中心化が必要ですが）$X^T X$は分散共分散行列になります．つまり，(4)式は**分散共分散行列の固有値分解**を表現していて，これはまさに**主成分分析**の手順と同じです．

すると，主成分分析によって得られた行列$V$は，元のデータを主成分空間に写す作用を持つ行列と言えます．
ここで(3)式を改めて見てみましょう．

```math
X V_0 = U_0 \Sigma_0
```

(3)式は，データ行列を主成分空間に写したものが$U_0 \Sigma_0$であると言っています．つまり，**データ行列$X$の情報（分散）をより良く表現した空間へ写したものが$U_0$である**ということです．$\Sigma_0$は各列ベクトルの重要度を保持しています．よって，行列$U_0$をデータ行列の代わりに使おうという訳です．

$U_0$の列ベクトルは主成分空間の軸に対応しています．列ベクトルはその情報（分散）の大きい順に並んでいます．よって，行列$U_0$の全てを使うのではなく，より重要度の大きい軸だけを使い（重要度の少ない軸は切り捨て）ましょうということが可能になります．

# まとめ
特異値分解による次元削減がなぜできるのかを考えました．

```math
X = U\Sigma V^T
```
最初の式に戻ると，データ行列$X$を，主成分空間に写した際のデータ行列$U$，各主成分の重要度を保持した行列$\Sigma$，データを主成分空間へ写すための行列$V$に分解しているということでした．
そして，より重要度の高い軸だけを残すことで情報を保持しつつ次元削減するという目標を達成しているのでした．

数学的に不正確な部分も含まれるかもしれません．ご指摘頂ければ幸いです．

# 参考
以下の書籍，動画を参考にしました．

- 講談社サイエンティフィク　データサイエンスのための数学
- YouTube [データ解析入門 第5回 行列分解 主成分分析と特異値分解](https://www.youtube.com/watch?v=whC4xPrdDCY&t=201s)