深く考えれば奥深い「特異値分解」をわかりやすく丁寧に

# 特異値分解の利用
特異値分解(SVD,Singular Value Decomposition)はNLPでWord-Document Matrixからword vectorを作成する際に次元削減として重要な手法です。

機械学習を勉強している方ならいつか必ず当たる壁でもあります。特に証明の箇所で他のQiitaには調べた限りではあまり見られなかったベクトル空間からの考え方を導入しています。

何か不備等あればコメントでお待ちしております🙇‍♀️。

noteにてNLPを1から学べる教材を作成する過程で特異値分解の説明のために作成しました。興味のある方はぜひご覧ください。

https://note.com/tat5453/

(現在作成中です2024年10月中の完成を見込んでいるので暫くお待ちください。)

# 定義
まず、特異値分解の定義は以下のようになります

```math
A=UΣV^T
```
$A$:任意の行列(m×n)
$U$:直行行列(m×m)
$Σ$:対角成分が非負で降順であり非対角成分が0である行列(m×n)
$V$:直行行列(n×n)
行列の形式で書くと、
```math
A = (u_1\ \ u_2\ \ \cdots \ \ u_m)
\begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 & 0   & \cdots & 0\\
0   & \sigma_2 & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & \sigma_r &  0  & \cdots & 0\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0
\end{pmatrix}
\begin{pmatrix}
v_1^T \\
v_2^T \\
\vdots\\
v_n^T \\
\end{pmatrix}
```
```math
(但し、 \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0)
```
具体的に考えてみましょう👀


***
#### Uについて
一言で言うと$A$の行空間を表した行列になります。
具体的には、
$U$はrをAの階数として
$u_1,u_2,...u_r$👉行空間の正規直交基底(m×1)
$u_{r+1},u_{r+2},...,u_m$👉左零空間の正規直交基底(m×1)

になります。
```math
U = (u_1\ u_2\ \cdots \ u_m)
```
但し、
```math
u_iはAの行空間の正規直交基底 \cdots i=1,2,...,r
```
```math
u_iはAの左零空間の正規直交基底 \cdots i=r+1,r+2,...,m
```
:::note info
行空間とは行ベクトルが張る空間のことです。言い換えれば、行ベクトルの線形結合によって表せる全てのベクトルになります。
結論だけ言うと、$A$の行空間の正規直交基底は$AA^T$の固有ベクトルで表すことが出来て、合計でr個あります。
($A$をm×n行列とし、$r=rank(A)$とする)
***
具体的な説明は以下の様になります👇
行空間は例えば、以下の行列を考えた時、
```math
A=
\begin{pmatrix}
1 & 2 & 3  \\
1 & 3 & 2  \\
1 & 3 & 1  \\
\end{pmatrix}
```
行ベクトルはそれぞれの**行**をとって、
```math
\begin{pmatrix}
1\\
2 \\
3 \\
\end{pmatrix}
\begin{pmatrix}
1\\
3 \\
2 \\
\end{pmatrix}
\begin{pmatrix}
3\\
2 \\
1 \\
\end{pmatrix}
```
の3種類になります。これらの線形結合で表すことが出来るベクトル全ての空間が行空間です。
しかし、行空間の正規直交基底(互いに直交している大きさが1の基底)は行の個数と等しいとは限らないので注意しましょう。個数は合計でr個あります。($r=rank(A)$)
***
さらに、$A$の行空間は$AA^T$の行空間と一致します。
$AA^T$の各要素は$A$の行ベクトル同士の内積を取ったものになるので、$AA^T$の各行は$A$の行空間の正規直交基底で表すことが出来るためです。

加えて、$AA^T$は対称行列なのでその固有ベクトルは直交します。そのため$AA^T$の行空間の正規直交基底は固有ベクトルで表すことが出来ます。

以上から$A$の行空間の正規直交基底は$AA^T$の固有ベクトルで表すことが出来ます。
:::

:::note info
$A$の左零空間とは以下の式を満たす正規直交基底$u_i(i=1,2,...,m-r)$で構成される空間のことです。
($A$をm×n行列とし、$r=rank(A)$とする)
```math
A^Tu_i=0
```
合計でm-r個あります。
:::

***
#### Vについて
一言で言うと$A$の列空間を表した行列になります。
具体的には、
$V$はrをAの階数として
$v_1,v_2,...,v_r$👉列空間の正規直交基底(n×1)
$v_{r+1},v_{r+2},...,v_n$👉零空間の正規直交基底(n×1)

になります。
```math
V = (v_1\ v_2\ \cdots \ v_n)
```
但し、
```math
v_iはAの列空間の正規直交基底 \cdots i=1,2,...,r
```
```math
v_iはAの零空間の正規直交基底 \cdots i=r+1,r+2,...,n
```
:::note info
$A$の列空間とは先ほど説明した$A$の行空間の列ベクトルverです。
$A$の列空間の正規直交基底は$A^TA$の固有ベクトルで表すことが出来て、合計でr個あります。
($A$をm×n行列とし、$r=rank(A)$とする)
:::

:::note info
$A$の零空間とは以下の式を満たす正規直交基底$v_i(i=1,2,...,n-r)$で構成される空間のことです。
($A$をm×n行列とし、$r=rank(A)$とする)
```math
Av_i=0
```
合計でn-r個あります。
:::
***
#### Σについて
$Σ$は「対角成分が非負で降順であり非対角成分が0である行列」とあります。具体的には以下のような形状の行列になります。
```math
Σ = \begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 & 0   & \cdots & 0\\
0   & \sigma_2 & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & \sigma_r &  0  & \cdots & 0\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0
\end{pmatrix}
```
但し、
```math
\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0
```
```math
r = rank(A)
```
この$σ_i$は特異値(singular value)と呼ばれAの階数に等しい数特異値が存在します。




# 導出(読み飛ばしても🙆‍♀️,読んでおくと理解が深まります)
まず始めに、$AA^T$と$A^TA$の固有値が等しいことを示します。
##### 固有値が等しいことの証明
(証明)
$AA^T$の固有値の1つを$ \lambda_1 $,それに対応する固有ベクトルを$u_1$とする。この時、
```math
(AA^T) u_1 = \lambda_1u_1
```
両辺に$A^T$　をかけて
```math
A^T(AA^T) u_1 = A^T\lambda_1u_1
```
```math
(A^TA)A^T u_1 = \lambda_1(A^Tu_1)
```
```math
(A^TA)\frac{A^T u_1}{|A^T u_1|} = \lambda_1(\frac{A^T u_1}{|A^T u_1|})
```
$v_1=\frac{A^T u_1}{|A^T u_1|}$とおくと、($v_1$の大きさは1)
```math
(A^TA)v_1 = \lambda_1v_1
```
よって、$\lambda_1$は$A^TA$の固有値でもあり、それに対応する固有ベクトルは、
```math
v_1 = \frac{A^T u_1}{|A^T u_1|}
```
となる。
(証明終わり)
***
また、以上の内容から
```math
v_1 = \frac{A^T u_1}{|A^T u_1|}
```
という関係について求まりました。次に特異値$\sigma_1$を使って、
```math
Av_1=\sigma_1u_1
```
の関係が成り立つことを示します。👇

##### 特異値に関する関係の証明
$|A^T u_1|$について$A^T$はn×m行列,$u_1$はm×１の縦ベクトルであるので、
$A^T u_1$はn×1の縦ベクトルである。

:::note info
**縦ベクトルの大きさ**(知っている方は読み飛ばしてください)
ベクトルの大きさはそれぞれの要素の二乗を足して平方根を取ることで求められるので、例えば、n×1の縦ベクトル
```math
v=\begin{pmatrix}
  a \\
  b \\
  c
\end{pmatrix}
```
の大きさの二乗は$|v|^2 = a^2 + b^2 + c^2$となる。
これは転置をとったベクトルとの内積と等しい。
```math
v^T v=\begin{pmatrix}
  a\ b\ c
\end{pmatrix}\begin{pmatrix}
  a \\
  b \\
  c
\end{pmatrix} 
= a^2 + b^2 + c^2
=|v|^2
```
結論として、縦ベクトルの大きさを求めたい場合は転置したものとの内積を取れば良く
```math
|v|^2 = v^T v
```
で求めることが出来る。
:::


よって、
```math
|A^Tu_1|^2 =(A^Tu_1)^T(A^Tu_1)=u_1^T{A^T}^TA^Tu_1=u_1^TAA^Tu_1
```
ここで、$u_1$は$AA^T$の固有値$\lambda_1$に対応する固有ベクトルなので$AA^Tu_1=\lambda_1u_1$より、
```math
|A^Tu_1|^2 =u_1^TAA^Tu_1 = u_1^T\lambda_1u_1 = \lambda_1 u_1^T u_1 = \lambda_i |u_1|^2 = \lambda_1
```
最後の式変形は固有ベクトルの大きさが1であることを利用している。
そのため、
```math
v_1 = \frac{A^T u_1}{\sqrt{\lambda_1}}
```
```math
Av_1 = \frac{A A^Tu_1}{\sqrt{\lambda_1}}
```
$u_1$は$AA^T$の固有値$\lambda_1$に対応する固有ベクトルなので$AA^Tu_1=\lambda_1u_1$より
```math
Av_1 = \frac{\lambda_1 u_1}{\sqrt{\lambda_1}}
```
```math
Av_1 = \sqrt{\lambda_1} u_1
```
$\sigma_1 = \sqrt{\lambda_1}$とすると、
```math
Av_1 = \sigma_1 u_1
```
となり、$\sigma_1$を**特異値**と言います。(特異値は定数)

***
##### 特異値分解(SVD)の導出

$A$の階数を$r$として、($r=rank(A)$)
$AA^T$の固有ベクトル(m×1)はr個あるので
```math
u_1,u_2,...,u_r
```
$A^TA$の固有ベクトル(n×1)もr個あるので
```math
v_1,v_2,...,v_r
```
と書けます。
先ほどの証明により、
```math
Av_1 = \sigma_1 u_1
```
```math
Av_2 = \sigma_2 u_2
```
```math
\vdots
```
```math
Av_r = \sigma_r u_r
```
が成立するので、行列で
```math
A(v_1\ \ v_2\ \ \cdots \ \ v_r) = (u_1\ \ u_2\ \ \cdots \ \ 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}
```
先ほどの左零空間の説明から$A^Tu_i=0$を満たすiはm-r個あるので、それらを
```math
u_{r+1},u_{r+2},...,u_m
```
として、
零空間の説明から$Av_i=0$を満たすiはn-r個あるので、それらを
```math
v_{r+1},v_{r+2},...,v_n
```



とする。
これらを使うと以下のように拡張できる。
```math
A(v_1\ \ v_2\ \ \cdots \ \ v_r) = (u_1\ \ u_2\ \ \cdots \ \ 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}
```
```math
\downarrow
```
```math
A(v_1\ \ v_2\ \ \cdots \ \ v_r\ \ v_{r+1} \ \ v_{r+2}\ \ \cdots\ \ v_n) = (u_1\ \ u_2\ \ \cdots \ \ u_r \ \ u_{r+1}\ \ u_{r+2}\ \ \cdots \ \ \ u_m)
\begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 & 0   & \cdots & 0\\
0   & \sigma_2 & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & \sigma_r &  0  & \cdots & 0\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0
\end{pmatrix}
```


```math
AV=UΣ
```
但し、
```math
V = (v_1\ \ v_2\ \ \cdots \ \ v_n) \ \ \ \cdots n×n行列
```
```math
U = (u_1\ \ u_2\ \ \cdots \ \ u_m) \ \ \ \cdots m×m行列
```
```math
Σ = 
\begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 & 0   & \cdots & 0\\
0   & \sigma_2 & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & \sigma_r &  0  & \cdots & 0\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0
\end{pmatrix}
 \ \ \ \cdots m×n行列
```
これを少し変形すれば特異値分解の完成です。
```math
AV=UΣ
```
```math
AVV^{-1}=UΣV^{-1}
```
```math
A=UΣV^{-1}
```
```math
A=UΣV^{T}
```
最後の式変形は「対称行列の固有ベクトルを並べると直交行列」という性質と直交行列の定義$V^T = V^{-1}$　を利用しました。

:::note info
$A^TA$は以下の式変形から対称行列です。
```math
(A^TA)^T = A^T(A^T)^T = A^TA
```
$V=(v_1\ v_2\ \cdots \ v_n)$は対称行列$A^TA$の固有ベクトルを並べた行列なので「対称行列の固有ベクトルを並べると直交行列」という性質から直交行列です。


:::
これで特異値分解が導出されました🙌
ただ、1つ注意するのはr個の固有値の並べ方です。特異値分解では大きいものから$\lambda_1,\lambda_2,...,\lambda_r$ととります。つまり、
```math
\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_r \geq 0
```
となるように並び順を選びます。
先ほどの証明の中で特異値$\sigma_i = \sqrt{\lambda_i}$と導かれたので、特異値についても同様の順番で、
```math
\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0
```
となります。

# 特異値分解の利用
特異値分解を再喝すると、以下の様になります。
```math
A=UΣV^T
```
```math
A = (u_1\ \ u_2\ \ \cdots \ \ u_m)
\begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 & 0   & \cdots & 0\\
0   & \sigma_2 & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & \sigma_r &  0  & \cdots & 0\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots   & \vdots & \vdots\\
0   & 0   & \cdots & 0 & 0   & \cdots & 0
\end{pmatrix}
\begin{pmatrix}
v_1^T \\
v_2^T \\
\vdots\\
v_n^T \\
\end{pmatrix}
```
```math
(但し、 \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0)
```
計算を進めると、
```math
A=(u_1\sigma_1\ \ u_2\sigma_2\ \ \cdots \ \ u_r\sigma_r\ \ 0\ \  \cdots \ \ 0)
\begin{pmatrix}
v_1^T \\
v_2^T \\
\vdots\\
v_n^T \\
\end{pmatrix}
```
```math
=u_1\sigma_1v_1^T + u_2\sigma_2v_2^T + \cdots + u_r\sigma_rv_r^T
```
```math
= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ru_rv_r^T
```
ここで、$\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0$かつ、$u_i$$v_i$は正規基底なので大きさが1であることから、左の項ほど数字的に大きくなり影響度が大きくなることが分かります。
逆に右に行くほど影響度も小さくなることになります。
```math
A= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T + \cdots + \sigma_ru_rv_r^T
```
```math
\ \ \ \ \ \ \ 大←--------------→小
```
実際のNLPでは$A$は$10^6×10^6$とかなり大きいので、特異値分解の右の方の項を考えないという近似が極めて有用です。
```math
A= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T + \cdots + \sigma_ru_rv_r^T
```
```math
\approx \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T
```
```math
= (u_1\ \ u_2\ \ \cdots \ \ u_k)
\begin{pmatrix}
\sigma_1 & 0   & \cdots & 0 \\
0   & \sigma_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0   & 0   & \cdots & \sigma_k
\end{pmatrix}
\begin{pmatrix}
v_1^T \\
v_2^T \\
\vdots\\
v_k^T \\
\end{pmatrix}
```
```math
= U^{'}Σ^{'}{V^T}^{'}
```
となり、次元をkまで($k<r$)減らすことに成功します。
繰り返しの説明になるがこの近似の本質は影響力の少ない部分をカットしたということになります。
例えば、Aの行空間を次元削減したい場合はAに特異値分解をして、$U'$を得ることで行空間の要らない部分をカットしたことになります。
```math
U=(u_1\ \ u_2\ \ \cdots \ \ u_k \ \cdots \ \ u_r \ \cdots \ \ u_m)
```
```math
=(u_1\ \ u_2\ \ \cdots \ \ u_k)
```