特異値分解の利用

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

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

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

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

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

定義

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

A=UΣV^T

$A$:任意の行列(m×n)
$U$:直行行列(m×m)
$Σ$:対角成分が非負で降順であり非対角成分が0である行列(m×n)
$V$:直行行列(n×n)
行列の形式で書くと、

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}

(但し、 \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)

になります。

U = (u_1\ u_2\ \cdots \ u_m)

但し、

u_iはAの行空間の正規直交基底 \cdots i=1,2,...,r

u_iはAの左零空間の正規直交基底 \cdots i=r+1,r+2,...,m

行空間とは行ベクトルが張る空間のことです。言い換えれば、行ベクトルの線形結合によって表せる全てのベクトルになります。
結論だけ言うと、$A$の行空間の正規直交基底は$AA^T$の固有ベクトルで表すことが出来て、合計でr個あります。
($A$をm×n行列とし、$r=rank(A)$とする)

具体的な説明は以下の様になります👇
行空間は例えば、以下の行列を考えた時、

A=
\begin{pmatrix}
1 & 2 & 3  \\
1 & 3 & 2  \\
1 & 3 & 1  \\
\end{pmatrix}

行ベクトルはそれぞれの行をとって、

\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$の固有ベクトルで表すことが出来ます。

$A$の左零空間とは以下の式を満たす正規直交基底$u_i(i=1,2,...,m-r)$で構成される空間のことです。
($A$をm×n行列とし、$r=rank(A)$とする)

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)

になります。

V = (v_1\ v_2\ \cdots \ v_n)

但し、

v_iはAの列空間の正規直交基底 \cdots i=1,2,...,r

v_iはAの零空間の正規直交基底 \cdots i=r+1,r+2,...,n

$A$の列空間とは先ほど説明した$A$の行空間の列ベクトルverです。
$A$の列空間の正規直交基底は$A^TA$の固有ベクトルで表すことが出来て、合計でr個あります。
($A$をm×n行列とし、$r=rank(A)$とする)

$A$の零空間とは以下の式を満たす正規直交基底$v_i(i=1,2,...,n-r)$で構成される空間のことです。
($A$をm×n行列とし、$r=rank(A)$とする)

Av_i=0

合計でn-r個あります。

Σについて

$Σ$は「対角成分が非負で降順であり非対角成分が0である行列」とあります。具体的には以下のような形状の行列になります。

Σ = \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}

但し、

\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0

r = rank(A)

この$σ_i$は特異値(singular value)と呼ばれAの階数に等しい数特異値が存在します。

導出(読み飛ばしても🙆‍♀️,読んでおくと理解が深まります)

まず始めに、$AA^T$と$A^TA$の固有値が等しいことを示します。

固有値が等しいことの証明

(証明)
$AA^T$の固有値の1つを$ \lambda_1 $,それに対応する固有ベクトルを$u_1$とする。この時、

(AA^T) u_1 = \lambda_1u_1

両辺に$A^T$　をかけて

A^T(AA^T) u_1 = A^T\lambda_1u_1

(A^TA)A^T u_1 = \lambda_1(A^Tu_1)

(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)

(A^TA)v_1 = \lambda_1v_1

よって、$\lambda_1$は$A^TA$の固有値でもあり、それに対応する固有ベクトルは、

v_1 = \frac{A^T u_1}{|A^T u_1|}

となる。
(証明終わり)

また、以上の内容から

v_1 = \frac{A^T u_1}{|A^T u_1|}

という関係について求まりました。次に特異値$\sigma_1$を使って、

Av_1=\sigma_1u_1

の関係が成り立つことを示します。👇

特異値に関する関係の証明

$|A^T u_1|$について$A^T$はn×m行列,$u_1$はm×１の縦ベクトルであるので、
$A^T u_1$はn×1の縦ベクトルである。

縦ベクトルの大きさ(知っている方は読み飛ばしてください)
ベクトルの大きさはそれぞれの要素の二乗を足して平方根を取ることで求められるので、例えば、n×1の縦ベクトル

v=\begin{pmatrix}
  a \\
  b \\
  c
\end{pmatrix}

の大きさの二乗は$|v|^2 = a^2 + b^2 + c^2$となる。
これは転置をとったベクトルとの内積と等しい。

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

結論として、縦ベクトルの大きさを求めたい場合は転置したものとの内積を取れば良く

|v|^2 = v^T v

で求めることが出来る。

よって、

|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$より、

|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であることを利用している。
そのため、

v_1 = \frac{A^T u_1}{\sqrt{\lambda_1}}

Av_1 = \frac{A A^Tu_1}{\sqrt{\lambda_1}}

$u_1$は$AA^T$の固有値$\lambda_1$に対応する固有ベクトルなので$AA^Tu_1=\lambda_1u_1$より

Av_1 = \frac{\lambda_1 u_1}{\sqrt{\lambda_1}}

Av_1 = \sqrt{\lambda_1} u_1

$\sigma_1 = \sqrt{\lambda_1}$とすると、

Av_1 = \sigma_1 u_1

となり、$\sigma_1$を特異値と言います。(特異値は定数)

特異値分解(SVD)の導出

$A$の階数を$r$として、($r=rank(A)$)
$AA^T$の固有ベクトル(m×1)はr個あるので

u_1,u_2,...,u_r

$A^TA$の固有ベクトル(n×1)もr個あるので

v_1,v_2,...,v_r

と書けます。
先ほどの証明により、

Av_1 = \sigma_1 u_1

Av_2 = \sigma_2 u_2

\vdots

Av_r = \sigma_r u_r

が成立するので、行列で

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個あるので、それらを

u_{r+1},u_{r+2},...,u_m

として、
零空間の説明から$Av_i=0$を満たすiはn-r個あるので、それらを

v_{r+1},v_{r+2},...,v_n

とする。
これらを使うと以下のように拡張できる。

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}

\downarrow

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}

AV=UΣ

但し、

V = (v_1\ \ v_2\ \ \cdots \ \ v_n) \ \ \ \cdots n×n行列

U = (u_1\ \ u_2\ \ \cdots \ \ u_m) \ \ \ \cdots m×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}
 \ \ \ \cdots m×n行列

これを少し変形すれば特異値分解の完成です。

AV=UΣ

AVV^{-1}=UΣV^{-1}

A=UΣV^{-1}

A=UΣV^{T}

最後の式変形は「対称行列の固有ベクトルを並べると直交行列」という性質と直交行列の定義$V^T = V^{-1}$　を利用しました。

$A^TA$は以下の式変形から対称行列です。

(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$ととります。つまり、

\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_r \geq 0

となるように並び順を選びます。
先ほどの証明の中で特異値$\sigma_i = \sqrt{\lambda_i}$と導かれたので、特異値についても同様の順番で、

\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0

となります。

特異値分解の利用

特異値分解を再喝すると、以下の様になります。

A=UΣV^T

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}

(但し、 \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0)

計算を進めると、

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}

=u_1\sigma_1v_1^T + u_2\sigma_2v_2^T + \cdots + u_r\sigma_rv_r^T

= \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であることから、左の項ほど数字的に大きくなり影響度が大きくなることが分かります。
逆に右に行くほど影響度も小さくなることになります。

A= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T + \cdots + \sigma_ru_rv_r^T

\ \ \ \ \ \ \ 大←--------------→小

実際のNLPでは$A$は$10^6×10^6$とかなり大きいので、特異値分解の右の方の項を考えないという近似が極めて有用です。

A= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T + \cdots + \sigma_ru_rv_r^T

\approx \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T

= (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}

= U^{'}Σ^{'}{V^T}^{'}

となり、次元をkまで($k<r$)減らすことに成功します。
繰り返しの説明になるがこの近似の本質は影響力の少ない部分をカットしたということになります。
例えば、Aの行空間を次元削減したい場合はAに特異値分解をして、$U'$を得ることで行空間の要らない部分をカットしたことになります。

U=(u_1\ \ u_2\ \ \cdots \ \ u_k \ \cdots \ \ u_r \ \cdots \ \ u_m)

=(u_1\ \ u_2\ \ \cdots \ \ u_k)