特異値分解とその応用 2009年5月12日 計算理工学専攻　張研究室 山本有作.

Presentation on theme: "特異値分解とその応用 2009年5月12日 計算理工学専攻　張研究室 山本有作."— Presentation transcript:

1 特異値分解とその応用 2009年5月12日 計算理工学専攻　張研究室 山本有作

2 目次 特異値分解とその基本的性質 画像圧縮への応用 情報検索への応用

3 特異値分解とその基本的性質

4 対称行列の固有値分解 A = VDVT 定理１ 任意の n×n 実対称行列 A は次の形に分解できる。 ここで， V： n×n の直交行列
D：　n×n の対角行列 D = diag (l1 , l2 , … , ln ) 　　　 　（ただし l1 ≧l2 ≧ … ≧ln ） これを A の固有値分解と呼ぶ。 l1 , l2 , … , ln は A の固有値， V の第 i 列 vi は li に対応する固有ベクトルとなる。 A = VDVT

5 行列の特異値分解 A = US VT 定理２ = A U S VT 任意の m×n 実行列 A （m ≧ n）は次の形に分解できる。
ここで， U：　m×m の直交行列 V：　n×n の直交行列 S：　m×n の対角行列 S = diag (s1 , s2 , … , sn ) 　　　 　（ただし s1 ≧s2 ≧ … ≧sr > sr+1 = …= sn = 0） これを A の特異値分解，s1 , s2 , … , sn を A の特異値と呼ぶ。 0 でない特異値の個数 r は行列 A のランクに等しい。 A = US VT = A U S VT

6 特異ベクトル 右特異ベクトルと左特異ベクトル これらを使うと，A はランク1の行列の和として表現できる。
V の各列 v1, v1, …, vn を右特異ベクトルと呼ぶ。 U の各列 u1, u1, …, um を左特異ベクトルと呼ぶ。 右特異ベクトル，左特異ベクトルは，それぞれ Rn， Rm の正規直交基底をなす。 これらを使うと，A はランク1の行列の和として表現できる。 A = s1u1v1T + s2u2v2T + … + srurvrT A = × × + × × + + × × s1 v1 s2 v2 sr vr u1 u2 ur

7 特異値分解の意味 幾何学的意味 行列 A をかける線形写像において，元の空間と行き先の空間に適当に直交座標を定めると，写像は対角行列で表される。 v3 v4 A による乗算 u1 v2 u2 u3 vi 成分（i = 1, …, r）は si 倍され，ui 方向を向く v1 元の空間 行き先の空間 vi 成分（i = r +1, …, n） は 0 になる。

8 像空間・核空間との関係 像空間 Im(A) = {y∈Rm | ∃x∈Rn 　s.t. y = Ax} Im(A) = span{u1, u2, …, ur} 核空間 Ker(A) = {x∈Rn | Ax = 0} Ker(A) = span{vr+1, vr+2, …, vn} すなわち，特異値分解が与えられると，像空間・核空間の正規直交基底が特異ベクトルによって陽的に表される。

9 定理２の証明 証明の流れ m×m 正定値対称行列 AAT の固有値を {si2}，固有ベクトルを {ui} とする。 s1 ≧ … ≧sr > sr+1 = …= sm = 0 とする。 AT ui = 0 （i = r+1, …, m）を示す。 vi = (1/si) ATuiにより，ベクトル vi （i =1, 2, …, r）を求める。これら が正規直交系をなすことを示す。 V = [v1, v2, … , vn] が直交行列となるように vr+1, …, vn を定める。 U = [u1, u2, … , um] とし，UTAV が対角行列となることを示す。

10 固有値分解との関係 A の左特異ベクトルは AAT の固有ベクトル A の右特異ベクトルは ATA の固有ベクトル
定理２の証明より明らか。 A の右特異ベクトルは ATA の固有ベクトル 実際に ATAvi を計算してみればよい。 A の特異値は AAT （ATA ）の固有値の正の平方根

11 ランク１の行列の和による行列の近似 近似 A – Ak = x1y1T + x2v2T + … + xkykT 問題 応用
A を次のようにランク１の行列 k 個（k ≦ r）の和で近似する。 近似誤差を || A – Ak ||F で定義する。 || A ||F = (Tr(ATA))1/2 = (Si=1m Sj=1n aij2)1/2 問題 {xi}，{yi} をどのように取れば，近似誤差が最小になるか？ そのときの近似誤差は？ 応用 情報圧縮，情報検索など A – Ak = x1y1T + x2v2T + … + xkykT ～

12 ランク１の行列の和による行列の最適近似 定理３ （Eckart & Young の定理）
ランク１の行列 k 個（k ≦ r）の和による A の最適近似は，A の最初の k 個の特異値と特異ベクトルを用いて次のように与えられる。 また，近似誤差は特異値を用いて次のように書ける。 Ak を A の打ち切り型特異値分解と呼ぶ。 Ak = s1u1v1T + s2u2v2T + … + skukvkT || A – Ak ||F = (S i=k+1r si2)1/2 = A U S VT 打ち切り = Ak Uk Sk VkT

13 定理３の証明 補題４ m×n 行列の空間 Rm×n における内積を，(A, B) = Tr(ATB) で定義 する。
このとき，mn 個のランク１行列 uivjT （i = 1, 2, …, m, j = 1, 2, …, n）は，この内積に関して正規直交系をなす。 Rm×n は mn 次元であるから，これら mn 個の行列は Rm×n の正規 直交基底をなす。

14 定理３の証明（続き） 証明の流れ {uivjT} は Rm×n における基底であるから，A – Ak を {uivjT} で展 開してみる。
{uivjT} は正規直交基底であるから，|| A – Ak ||F は展開係数の２ 乗和の平方根となる。 これが最小になるよう， Ak の展開係数を決める。ただし，0 でない 展開係数の数が k 個となるようにする。

15 画像圧縮への応用

16 画像圧縮の必要性 画像は一般的にデータ量が多い。 画像データの転送・記憶を効率的に行うために，圧縮ができれば望ましい。

17 行列の近似を用いた画像圧縮 画像を行列と見る ランク１の行列の和による近似 200×320 ピクセルの白黒画像データ
これを 200×320 の行列と見なす。 データ量は 200×320 個の実数 ランク１の行列の和による近似 この行列をランク１の行列 k 個の和で近似できたとすると，データ量は k×( ) 個の実数 k が小さければ，データは大きく圧縮できる。 最適なランク１行列を求めるために，Eckart & Young の定理が利用できる。

18 特異値分解を用いたアルゴリズム アルゴリズム Ak = s1u1v1T + s2u2v2T + … + skukvkT
A の特異値分解 A = US VT を計算 近似誤差 || A – Ak ||F = (S i=k+1r si2)1/2 が十分小さくなるよう，ランク１行列の個数 k を決定 s1u1, …, skuk, v1, …, vk が圧縮データ データを復元するには，次のようにして Ak を計算する。 このデータ圧縮方式は，近似誤差の意味で，最適な圧縮となっている。 Ak = s1u1v1T + s2u2v2T + … + skukvkT

19 例題の画像データに対する特異値分布 特異値の分布から，ある次数 k で打ち切ったときの近似誤差が推定できる。

20 打ち切り次数と復元画像の品質

21 情報検索への応用

22 効率的な情報検索の必要性 膨大な情報の中から必要な情報を引き出すことの難しさ キーワードによる検索の問題点 課題 文献データベース
インターネット上のファイル キーワードによる検索の問題点 synonymyの問題：　内容的には関係の深い文書でも，たまたまそのキーワードを使っていないために検索から漏れる。 polysemyの問題：　同じキーワードを使っていても，内容的には関係のない文書がヒットする。 課題 単なるキーワードのマッチングではなく，文書の意味内容に基づく分類／検索ができないか？

23 LSIの原理 (1) ベクトル空間モデル Term-Document Matrix 単語が行，文書が列に対応する行列A
要素 aij は，文書 j 中に単語 i が出てくる回数を表す。

24 LSIの原理 (1) ベクトル空間モデル 例： 文書のタイトルを内容とするデータベース ９個の文書 内容的に大きく２つの分野に分けられる。
例：　文書のタイトルを内容とするデータベース ９個の文書 内容的に大きく２つの分野に分けられる。 c1: Human machine interface for Lab ABC computer applications c2: A survey of user opinion of computer system response time c3: The EPS user interface management system c4: Systems and human systems engineering testing of EPS-2 c5: Relation of user-perceived response time to error measurement m1: The generation of random, binary, unordered trees m2: The intersection graph of paths in trees m3: Graph minors IV: Widths of trees and well-quasi-ordering m4: Graph minors: A survey

25 LSIの原理 (1) ベクトル空間モデル Term-Document Matrixの例 Document Term
ｃ１　ｃ２　ｃ３　ｃ４　ｃ５　ｍ１　ｍ２　ｍ３　ｍ４ human １　　０　　０　　１　　０　　０　　０　　０　　０　　 interface １　　０　　１　　０　　０　　０　　０　　０　　０ computer １　　１　　０　　０　　０　　０　　０　　０　　０ user ０　　１　　１　　０　　１　　０　　０　　０　　０ system ０　　１　　１　　２　　０　　０　　０　　０　　０ response ０　　１　　０　　０　　１　　０　　０　　０　　０ time ０　　１　　０　　０　　１　　０　　０　　０　　０ EPS ０　　０　　１　　１　　０　　０　　０　　０　　０ survey ０　　１　　０　　０　　０　　０　　０　　０　　１ tree ０　　０　　０　　０　　０　　１　　１　　１　　０ graph ０　　０　　０　　０　　０　　０　　１　　１　　１ minor ０　　０　　０　　０　　０　　０　　０　　１　　１ Term

26 LSIの原理 (1) ベクトル空間モデル Term-Document Matrix を用いた文書間の近さの計算 単語間の近さの計算
２本の列ベクトル ai，aj の内積の値（またはベクトルのなす角度）により，２つの文書の近さを判定。 内積の値が大きい　→　文書の内容が近い 単語間の近さの計算 ２本の行ベクトルの内積の値（またはベクトルのなす角度）により，２つの単語の近さを判定。

27 LSIの原理 (2) ベクトル空間モデルの問題点
文書間の関連が十分に表現されない 内容的に関連のある文書でも，使用する単語に共通なものが少ないと，列ベクトルどうしの内積は０に近くなる。 原因 列ベクトルの張る空間の自由度が大きすぎて，互いに直交する方向の数が多すぎる。

28 LSIの原理 (2) ベクトル空間モデルの問題点
関連のある文書ベクトルどうしが直交する例 a1 a2 a3 a1 a2 a3 Term-Document Matrix A a1，a2，a3 の位置関係

29 LSIの原理 (3) 次元の縮小 基本的なアイディア 各単語の軸は完全に独立ではないはず（ex. car と automobile）。
列ベクトルを低次元の部分空間に射影することにより，内容的に近い文書どうしを近くに集める。

30 LSIの原理 (3) 次元の縮小 次元縮小による文書のクラスタリング
高次元の文書ベクトル集合をできるだけ良く近似する低次元空間（平面）への射影を求める。 a2 a1 a1 a1とa3は直交 a1とa3は非直交 a3 a4 a5 a3 a7 a6 高次元空間 低次元空間（平面）

31 LSIの原理 (3) 次元の縮小 何次元の空間に射影すべきか？ 大きすぎると，関連のある文書ベクトルどうしが直交してしまう。
小さすぎると，関連のない文書ベクトルどうしも重なってしまう。 この２つのトレードオフから，経験的に最適な次元数を決定

32 LSIの原理 (3) 次元の縮小 次元を指定したとき，どうやって部分空間を求めるか？
元のベクトル集合をもっともよく近似する部分空間を求める。 部分空間の次元をkとするとき，|| A – A(k) ||F を最小化するランクkの行列 A(k) を求めればよい。 特異値分解（SVD）を利用することにより可能

33 LSIの原理 (4) 特異値分解の利用 A = UΣVt 特異値分解の復習 任意の m×n 行列 A （m≧n） は，次の形に分解できる。
ここで， U：　m×n の直交行列 V：　n×n の直交行列 Σ：　n×n の対角行列Σ=diag (σ1 , σ2 , … , σn ) 　　　 　（ただしσ1 ≧σ2 ≧ … ≧σn ） これをAの特異値分解，σ1 , σ2 , … , σn をAの特異値と呼ぶ。 A = UΣVt

34 LSIの原理 (4) 特異値分解の利用 Eckart & Young の定理 A(k) = UΣ(k) Vt ： 打ち切り型特異値分解
Aの列ベクトルの集合をもっともよく近似するランク k の行列A(k) （k≦n） は，Σにおいてσk+1 以下の特異値をすべて０とした行列Σ(k) =diag (σ1 , σ2 , … , σk , 0, … , 0 ) を用いて次のように求められる。 A(k) = UΣ(k) Vt　　　　：　打ち切り型特異値分解

35 LSIの原理 (4) 特異値分解の利用 打ち切り型特異値分解の作成 LSIによる文書間の近さの計算 = A U Σ Vt = Ak Uk
(1) Term-Document Matrix Aを作成し，特異値分解 (2) 打ち切り型特異値分解 Ak = UkΣkVkt を作成 (3) Ak の２本の列ベクトルの内積から，文書間の近さを計算 特異値分解 = A U Σ Vt 打ち切り型 特異値分解 = Ak Uk Σk Vkt

36 LSIの原理 (5) キーワードによる検索 LSIによる文書間の近さの計算（続き） キーワードによる検索
A(k) の２本の列ベクトル ai(k)，aj(k) の内積は，元のAの列ベクトル ai，ajを使うと以下のように書ける。 U(k) U(k) t は k 次元部分空間への射影演算子と見なせる。 キーワードによる検索 与えられたキーワード群から単語空間での列ベクトル bi （pseudo-objectと呼ぶ） を作成し，以下のようにして任意の文書ベクトル aj との近さλを計算する。 λの値の大きな順に，キーワードに近い文書として答えを返す。 ai(k)・ aj(k) = ai・ U(k) U(k)t aj λ = bi・ U(k) U(k)t aj

37 今後の課題 打ち切り型特異値分解の効率的な計算法 最適な打ち切り次元数の計算 特異値分解の更新
疎行列であるTerm-Document Matrixに適した計算法 並列化アルゴリズム 最適な打ち切り次元数の計算 現在は，経験的に最適な値を設定 最適な打ち切り次数は，理論的に計算できるか？ 特異値分解の更新 データベースに文書を追加すると，特異値分解の再計算が必要 最初から計算し直すことなく，特異値分解を更新できるか？

38 レポート課題 特異値分解の他の応用例を１つ挙げ，特異値分解がどのように使われるかを数式を交えて説明せよ。 締め切り： ６月２日（火）
締め切り：　６月２日（火） 提出先：　３号館南館４階４７９号室 　　または　

39 様々な応用 文書以外のマルチメディア検索への応用 新材料設計への応用 （Oak Ridge国立研究所）
大学におけるエッセイの採点への応用 （Colorado大学）