特異値分解

特異値分解（Singular Value Decomposition）とは

特異値分解は、僕にとって行列の本質を探求するプロセスであり、極めて重要な行列分解の一つでもある。

高校や大学の線形代数の授業で、最もよく目にした行列分解といえばLU分解だったのを覚えている。

当時、僕は線形方程式 $Ax=b$ を解くなら、先に A の逆行列を求めればいいだけで、なぜわざわざ手間をかけて行列を分解するのかがずっと理解できなかった。授業でも行列分解の目的についてはほとんど触れられず、むしろ手計算ばかりが強調され、非常に苦い思い出として残っていた。この部分については後の章で触れるので、ぜひ楽しみにしていてほしい。

本題に戻ると、特異値分解はある行列を3つの行列へと分解することができる：

A=U\Sigma V^{T}

ここで $U$ は $AA^T$ の固有ベクトルから構成される行列であり、 $U$ は必ず直交行列になる。

$\Sigma$ は対角行列であり、 $AA^T$ または $A^TA$ の固有値の平方根である。 $AA^T$ の特性上、固有値は必ず非負となる。通常、特異値は大きい順に並べられる。

$V^T$ は $A^TA$ の固有ベクトルから構成される行列であり、こちらも直交行列となる。

エンジニアの視点から言えば、大まかには次のように理解できる。すべての行列はこれら3つの操作に分解できるのだ：

U: 回転

S: 拡大または縮小

V: 回転

しかし、画像という観点から考えてみると、すべての画像は無数のよりシンプルな固有ベクトルが回転や拡大縮小を経て組み合わさったものだと捉えることもできる。

応用

SVDは様々な分野で幅広く用いられている。いくつかの代表的な応用例を紹介し、最後は画像の圧縮を例として締めくくる。

主成分分析

データ分析を行う際、特徴量が多すぎてデータの関係性を直感的に捉えられないことがある。データ分析において一般的な手法の一つが主成分分析（PCA）だ。そのコア概念は、データの分散共分散行列を固有ベクトル（主成分）へと射影し、次元削減を実現することにある。

https://link.medium.com/hqd7YIs1SCb

レコメンデーションシステム

Netflixは自社のレコメンデーションシステムの精度を改善するため、かつてコンテストを開催した。最終的に BellKor’s Pragmatic Chaos チームが10%の改善を達成して優勝を飾った。当時のブレークスルーの一つとなったのは、あるチームがSVDを用いてアルゴリズムを改善したことであり、その後他のチームもこぞってSVDを使い始めた。

レコメンデーションシステムにおいて、ユーザーの嗜好はごく少数の要因からしか影響を受けないはずであり、またレコメンデーションシステムでは欠損値の問題が常につきまとう。そのため、Netflixのコンテストの過程では Funk SVD という手法まで考案され、レコメンデーションシステムで直面しがちなスパース行列の問題を解決すると同時に、2つの行列への分解にとどめることに成功した。

詳細な解説はこのウェブサイトを参考にするといい。

画像圧縮

画像はピクセルで満たされた行列と見なすことができる。画像の行列に対して特異値分解を行うことは、その画像にとって最も重要な固有ベクトルと特異値を見つけ出すことに相当する。上位いくつかの特異値だけを取り出し、重要でないものを削ぎ落とせば、行列のサイズを大幅に削減しながら、良好な品質を保つことができる。

import numpy as np
from PIL import Image
import matplotlib.pyplot as plt

image = Image.open('./pizza.jpg')
image_array = np.array(image.convert('L')) # 轉成灰階比較容易處理

U, S, VT = np.linalg.svd(image_array) # 奇異值分解
k = 50 # 取前 50 個奇異值

# 把原來的圖片矩陣改成 U * S(前 50 個奇異值) * Vt
image_compressed = U[:, :k] @ np.diag(S[:k]) @ VT[:k, :]
image_compressed = np.clip(image_compressed, 0, 255)
image_compressed = image_compressed.astype('uint8')
plt.imshow(image_compressed, cmap='gray')
plt.show()

まずは k = 5 の結果を見てみよう：

Figure_1

なんとなく輪郭はあるが、何なのかは判別できない。

続いて k = 50 の結果を見てみよう：

Figure_50

すでにピザであることは分かるが、解像度はあまり良くない。

さらに k = 200 の結果を見てみよう：

一気に解像度が高くなった。

最後に元の画像を見てみる。美味しそうなピザだ！

あとがき

特異値分解の背後には多くのテーマが関わっている。完全に理解しようとすれば、線形変換、固有値、行列の対角化、対角行列、正定値行列に至るまで、一定の理解が必要となる。そのため、ここでは多くの説明や数学的証明を省略した。

しかし工学的な応用の観点から言えば、特異値分解によって行列の本質を見通せること、どんな行列も3つの小さな行列に分解できること、そして必要に応じて固有値の大きな固有ベクトルをいくつか取り出すだけで、使用領域を大幅に削減しつつ行列の全体像を復元できることさえ知っておけば十分だ。

カテゴリー

ページ

その他