通往線性代數的聖母峰 : 特徵值分解(EVD)、奇異值分解(SVD) 與主成分分析(PCA)

聖母峰的譬喻很有趣,原文來自交大周志成老師的線代啟示錄部落格,周老師文章裡曾說線代領域有兩座聖母峰,一座叫Jordan Form用來判斷矩陣相似問題,另一座就是奇異值分解(SVD,Singular Value Decomposition)。

特徵值( Eigenvalue )、奇異值( Singular Value )以及相關的矩陣觀念(正交、正規、跡數、對稱、轉置共軛、么正、可逆與不可逆、行列式、實數域與複數域、正定與半正定、可對角化、相似、秩…etc )在線性代數中都是重要的觀念,不過篇幅有限不可能一一討論,所以本文的重點將放在 SVD 的原理與類似方法的比較,因此延伸的線性代數知識都將予以簡化或略過以免模糊焦點。

SVD的基本概念與應用

作為線性代數中最重要的矩陣分解工具,奇異值分解( SVD )的主要應用就是「對特定資料集合做拆解,以便找出相對數量少卻富含重要資訊的要素組成新資料集合,並以此來近似原先的資料集合」,達到以簡馭繁或是減少雜訊的目的( a low-dimensional representation of a high-dimensional matrix )。

例如文件探勘的典型問題,是要在大量文件當中,根據為數眾多的單字來建構出數量遠較原本為少的「概念」來呈現文章複雜的意義。

因為動輒幾千字的文章( in rows )往往可以拆解為成千上百個獨立的單字( in columns )與出現頻率( values ),若是數量過多除了不易分析之外,同時每一個單字當作單獨的變數,又往往又不足以充分表達一個完整的意義( sparse problem )。

利用 SVD 萃取文章概念,並將之用於建立個別文件的索引,正是Latent Semantic Analysis 的重要手法,了解SVD,也就能稍微體會各種搜尋引擎服務(例如圖書館、電子郵件、網站)是如何有效找到使用者想要的資訊了。

從資料視覺來看,SVD就是一個把文件( Doc )拆解成實際存在的文字( Term )與建構得到的概念( 通常稱之為Component 或 Concept,實際上就是 Latent Variable )之間關連性的過程,可參照下面的示意圖(請勿理解為數學式)。

SVD-conceptual-framework

假如原先的 Doc 有 10 萬筆,而所有文章內容總共可辨識出 30000 種 Term,因此從每當以關鍵字來查詢 Doc 時,程式都要對每份文件逐一檢查該文件與這 30000 種 Term 之間的關係(想像一下,如果用 for 迴圈…)。

但若是能透過 SVD 計算並建構出 200 個可用於描述這 10 萬筆 Doc 約 65% 資訊的重要 Concept ,那麼程式在判別文件時僅需對照 200 個 Concept 即可,相比之下可以提升的效率相信一目了然。

作為取捨,用較少資訊的集合來代表完整資訊集合必然會導致資訊遺漏的問題,也就是不可能完全正確,其主要對應的挑戰就是 Machine Learning 中判斷訓練效果的兩個重要指標:「 Precision ( 例如,所有被預測為正確的結果當中,事實上也正確的比率 )」及「 Recall (所有已知結果分類的案例中,有多少事實上正確的個案也被演算法預測為正確)」,這可以對應到統計學「 Type I 」及「 Type II 」推論錯誤的概念。

特徵值分解與奇異值分解

當然,資料檢索只是 SVD 的其中一種應用,過濾雜訊、以簡馭繁的技巧在很多資料分析的場合都派得上用場,像是影像辨識經常可以看到 SVD 的身影,同時 SVD 也是資料探勘( Data Mining )做分群( Clustering )會應用的方法。


(Resource: University of Pennsylvania – Spring 2013 : Math 312)

不過儘管應用廣泛,SVD並不是矩陣分析的唯一選擇。從教科書的編排來看,要學習 SVD 免不了要從特徵值、特徵方程式以及另一個相當類似的方法 – 特徵值分解( EVD,Eigenvalue Decomposition ) 開始說起。

另外,以計量方法從事探索性研究、行為與心理學研究時經常使用概念類似的主成分分析( PCA ,Principal Component Analysis )以及從 PCA 延伸的因素分析( FA,Factor Analysis )而不是SVD (關於 PCA 與 FA 的簡單比較,可參考:主成份分析(Principal Component Analysis)與因素分析(Factor Analysis) )。

這三者之間究竟有何不同?實作上的差異在哪裡?這也正是許多分析人員傻傻分不清楚的地方。

雖然在網路上已經有許多關於 SVD 的討論,但在閱讀時卻經常引起更多疑惑,因此我們藉這個機會做一個整理與比較,希望看完這系列文章的你也能離心中的解答更近一點。

註:以下只討論實數域,欲討論複數域,請戰鬥力強大的讀者參考:Hermitian矩陣,自行替換符號。

特徵值分解(EVD)

現在離討論 SVD 、EVD、PCA 三者異同還有很長一段路要走,我們必須先從了解「特徵值」的基本定義開始。

現有一個 n x n 的矩陣 A (*提示 1 ),若能找到一個非零向量 x ,使得:

則稱 x 為 A 的特徵向量,其中純量 lambda :

就是與 A 及特徵向量 x 對應的特徵值。

這個算式的厲害之處,是提供了抽象線性轉換的基礎,藉由向量 x 可執行平移、拉伸及旋轉(延伸閱讀請看此),並藉由 lambda 來決定變化量的大小,同時還能保留原資料集的重要性質。

進一步看,一個 n x n 的矩陣可找到 n 個特徵向量及 n 個特徵值,當我們把 A 的特徵向量集合在一起變為矩陣 X,自然就會得到由對應的特徵值形成的一個對角線矩陣,除了對角線上的特徵值外皆為零,稱為 Lambda,符號為:

這時原式變為:

同時根據矩陣運算規則,上式可變為:

這個推演又有何獨到之處呢?透過這個算式,對於任意 P 次方的矩陣 A,其分解為:

儘管原資料的計算複雜度呈指數上升,我們卻僅需處理只有對角線有數值的特徵值矩陣 X 就能充分得到原資料的訊息,原本的矩陣越複雜,可以節省的計算效率就越多。

以上,就是特徵值分解( EVD )。

分解完成,但是該怎麼使用?藉由上式分解 n 維度的A矩陣,從中找出較重要的 Concept / Component (依特徵值大小排序),例如 k 個維度,重新組成具代表性但是維度較少的新矩陣進行應用。

這意味著我們能在不損失太多資訊的情況下,使用下式縮減過後的矩陣來取代原先的矩陣:

其中 AX_{k} 稱為 A 的 k 維度表述( a k-dimensional representation of A)。

奇異值分解( SVD )

輪到奇異值分解,仍以同樣的 n x n 矩陣A 為例(*提示 1 ),將能找到一個非零純量的奇異值 sigma:

以及兩個特徵向量:

它們將使得以下式子成立:

以及

A^Tu_sigmaV

仿照前面的說明方式,進一步把所有特徵向量集合起來成為左特徵向量 U 與右特徵向量 V ,則得到:

AV_U sigma

以及

A^TU_V sigma^T

進一步可以寫成:

其中 Sigma

為一數值遞減的對角線矩陣( 第一個元素最大 ),除了對角線上的奇異值以外皆為零,同時奇異值為非負數值,U 與 V 都是正交矩陣( Column-orthonormal Matrix )。這就是奇異值分解( Singular Value Decomposition)了。

怎麼詮釋 SVD 的結果呢?

中間的 Sigma 奇異值矩陣所代表的是分解萃取得到的 Component 重要性,矩陣 U 代表的是第 i 筆觀察值對應第 j 個 Component 的關係(左特徵向量),矩陣 V 代表的是第 j 個 Component 對應第 k 個變數的關係(右特徵向量)。

這樣一來,不管是樣本觀察值與潛在變數之間的關係,或是原變數與潛在變數之間的關係,都能一目了然。

除此之外,也可以仿照 EVD 的作法,計算縮減後的精實版矩陣。

特徵值與奇異值的空間意義

乍看之下,特徵值分解( EVD ):

與奇異值分解( SVD ):

雖然兩者形式十分類似,但從空間運用來看卻有很大不同,前 University of Michigan / Stanford University 的數學教授 Cleve Moler 在他的教科書上是這麼說的:

"Eigenvalues play an important role in situations where the matrix is a transformation from one vector space onto itself."

"Singular values play an important role where the matrix is a transformation from one vector space to a different vector space, possibly with a different dimension."

戰鬥力強大的讀者請參考Moler 教授的例子,來辨別兩者求線性獨立的差異,EVD就是在解 Linear differential equation 問題;而SVD 則能夠處理 OverdeterminEVD system / UnderdeterminEVD system。接著來談談 PCA 吧。作為近代統計與線性代數極具影響力的理論交會點,我們需要分別從線性代數的角度和統計的角度來看。

主成分分析( PCA )

承續前面用來說明 SVD 與 EVD 的矩陣 A,不過這裡要做一件暫時看起來無關的事:把它乘上自己的轉置矩陣 A^{T},得到新矩陣

AA^T

A^TA

這個步驟有何特別之處呢?

若 A 不再是 n x n 矩陣而是 30 x 20 矩陣,則對 30 x 20 矩陣 A 而言 AA^{T} 將是 30 x 30 矩陣(*提示 1 ),同時 A^{T}A 則為 20 x 20 矩陣(*提示 1 ),但不管哪一個矩陣,都將有一模一樣的非零特徵值,不過矩陣中含 0 的個數可能不一樣,這是因為矩陣大小不同的關係,當然對應特徵向量也會改變。

同樣重要的是,這兩者都將具備對稱的性質(*提示 2 )。繼續往前之前,我們也需要稍微複習基礎統計學。對一個具有 n 個觀察值的變數 A ,其平均數為所有數值加總再除以觀察個數:

若推廣到 n 個變數,代號統一設為 x ,觀察個數一樣有 n 筆資料,則可以把平均數寫成向量形式:

其中

其餘以此類推。

變異數則是計算個別觀察值與平均數的距離平方,加總,再除以觀察個數 -1,以變數 A 為例:

若加入另一具 n 個觀察值的變數 Z ,則 A、Z 的共變異數為計算各自觀察值與各自平均數距離,兩者相乘後予以加總,再除以觀察個數 -1:

接著這裡要再做一件看起來無關的事:mean-centering。

把剛才的 x 分別減去平均數

得到一個 n x m 的新矩陣,暫稱為 B ,它會長得像下面這樣:

Mean-centering 是一般常見的資料處理手法,視覺化結果可參考 UCSD 數學教授 Glenn Tesler 的講義範例:

若是這時靈機一動把 B 給轉置( Transpose )…,將得到 m x n 的矩陣:

想像一下,假如把 B 乘上 B^{T} 得到:

BB^T

則根據矩陣乘法,是不是隱約感覺它很像是共變異數的公式呢?

事實上,n x n (*提示 1 )的共變異數矩陣 S 等於:

對共變異數矩陣 S 而言,對角線為變數與自身的共變異數,即該變數的變異數 Var (),而對角線外的數值呈現兩變數之間的共變異數。

實務上, S 中的 1 / n 經常省略不計算,讀者不妨品味一下箇中理由。也就是說,程式化時只用這個形式已經足夠:

根據先前 AA^{T} 具備對稱的性質(*提示 2 ), S 也將是對稱方陣。

扯了這麼遠,到底什麼是 PCA ?

對任意資料集,PCA 所做的就是先計算共變異數矩陣 S ,再把 S 進行分解,找出主成分( Component )、特徵值與特徵向量,並依照特徵值大小予以篩選適當的主成分數量來達到壓縮的效果。

聽起來是不是有點熟悉?

如果你還對特徵值分解與奇異值分解有點印象…,則不難推出:

而且

接著你愛用哪一種方式分析都行。

特徵值分解、奇異值分解與主成分分析的關聯

如果可能的話,我希望能在本文的第一段就進行說明,但不以長篇論述預留伏筆,將很難回答這個出自直覺但實際上複雜得多的問題:這三種方法是否根本一模一樣?

好了,如果你回到默默地出現好幾次的(*提示 1 ),其實它是早就藏好的錦囊妙計:A 是一個 n x n 矩陣。

更精確地說,我們用來做範例的 A 不僅是 n x n 的方陣,而且必須對稱

之所以如此,是為了配合 EVD適用性的限制(對稱的n x n 矩陣),因為在實數矩陣中,對稱矩陣同時也是正規的。對於實數正規矩陣 A,若且唯若它能夠寫成以下形式,同時其特徵向量兩兩正交:

而SVD 基本上因為是一個精確表達( an exact representation of any matrix ),因此適用於任何資料矩陣(任意m x n 矩陣)。

至於 PCA ,一個或許聽來很奇妙但應不意外的事實是(*提示 2 ),共變異數矩陣 S ,必然會是方陣而且對稱。 於是乎, PCA 也適用於任意 m x n 矩陣,而且多數統計方法不同的是,它也不須指定機率分配,因此就是一種無母數方法。

一般而言,把SVD視為EVD的廣義版本應無太多爭議,只不過兩者計算出來的值,除了對稱方陣外絕大部份時候並沒有直接關係,這從上面引述 Moler 教授的話應不難理解(畢竟空間運用方式不一樣)。

而 PCA 與 SVD 的關係,則尚有些機巧可探。已知 PCA 的核心運用了:

對 B 與 B^{T} 分別執行 SVD,得到:

整理得到

由於 V 為正交矩陣

因此

有發現什麼了嗎?運用 SVD 計算 PCA 之後,居然恰好得到一個特徵值為 2 次方的 EVD!

這也隱含了,共變異數矩陣 S 的奇異值是特徵值的平方根。

PCA 與 SVD 的概念視覺化

雖然文中盡可能以簡化的方式來整理(畢竟太難我也看不懂),但公式化的推演閱讀並不容易,由視覺化結果猜想或許更有助於理解方法的基本原理。

(Source: wiki)

從概念圖來看 PCA ,圖中的黑點代表原始資料的分佈,而兩個箭頭代表的是藉由 PCA 建構出的Component (此例有兩個), PCA 就是用這些 Component 為座標重新定義向量空間,以精簡的維度(新座標軸)呈現的同時盡可能保留資訊(即變動趨勢),來分析原始資料。不妨想像一下,若要增加新的Component ,其位置應該在哪才能最大化掌握資料的變動趨勢?

另外這是多個向量在三度空間的情形:

SVD 方面,分解概念表示為如下:

SVD 的幾何運作其實就是把任意矩陣 A 變換分解成先旋轉、伸縮、再旋轉的過程。對於伸縮與旋轉的概念, PCA 也完全適用(不要以為 Rotation 是因素分析的專利)。

矩陣旋轉原理,請戰鬥力強大的讀者參閱:三維空間的旋轉矩陣

(Source: Mathematics)

至此,篇首的問題已經回答了大半,特徵值分解與奇異值分解兩者概念雖相似但實際上並不相等,而 PCA 恰可作為 EVD 與 SVD 的交點。

另由公式上則不難猜想, PCA 藉由兩種方法計算出的特徵值,很多時候可能差不多,實際上在統計 R 軟體裡與 PCA 有關的套件中,就有一些是透過 SVD 來計算的。

關於剩下的這個部分,留待下次以實作數字來驗證。

更多統計迷思大破解:

* 主成分分析(PRINCIPAL COMPONENT ANALYSIS)與因素分析(FACTOR ANALYSIS)

* 隨機性、大數法則與中央極限定理

* 廣義線性模型觀點:統計迴歸分析(REGRESSION)的基本原理與結構

* 一場關於猜的魔術:統計估計的形成

(Visited 28,290 times, 129 visits today)

Wendell.Huang

科技公司嫌棄太活潑,消費品牌挑剔太沉悶…, 經常必須解釋自己在學什麼, 不小心就摔破對方眼鏡的業餘書呆子。

3 Comments

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *