Eigenvector and Eigenvalue in Machine Learning – PCA

by allenlu2007

本文主要參考 George Dallas, Principal Component Analysis 4 Dummies: Eigenvectors, Eigenvalues and Dimension Reduction“.

拜 machine learning 之賜,Eigenvalue decomposition based 的 Principal Components Analysis (PCA) 也變得炙手可熱。

從前只有在線性代線最後幾章帶過的 eigenvalue and eigenvector, 突然有了新的重要性。

 

Eigenvalue/eigenvector 在控制,信號處理都有非常重要的地位。不過傳統上是從 model matrix 出發 (如 channel model, MIMO model, control plant model), 找出 model 的 structure 必須使用 eigenvalue decomposition.

實際的 input signal 可以被分解成 eigenvector 的 linear combination.  由此可以容易的得到 output signal.  或者分開 signal and interference.

但在 machine learning 問題中,所處理的 voice, image 包含非常多的高維 data (高維 data 也勍是 vector)。這些 vectors 形成高維的 data matrix.  

Machine learning 的問題是如何從高維的 data matrix 找到 data 內部的結構?  如果能找到其中的結構,就可以更有效率的 represent data (e.g. data compression, dimension reduction, clustering, data generation, etc.) 或是分開不同的 data (data classification, outliner detection, etc.) 

其實 data matrix 比 model matrix 更直覺以及更容易理解。 (假設 PSD matrix, 大的 eigenvalue 對應大的 data variance/information, 方向是 eigenvector)

一般人可能很難 picture 出 wireless channel model 或 MIMO channel model 的 eigenvalue/ eigenvector 長什麼樣子或有什麼直覺 (communication expert 除外)。但在 machine learning 的 data matrix 就很直覺如下所述。

 

What is Principal Component Analysis : Eigenvalue and Eigenvector 直觀解釋

簡單來說,PCA 就是找到最大 variance 的 dimension.  如下的 data. NewImage

Projected 的 data variance 最小。所以不是 principal component.

NewImage

Projected 的 data variance 最大。所以是 principal component: variance 基本上對應(最大)的 eigenvalue.  line 的方向對應 eigenvector. 

NewImage

 

Based on Andrew Ng’s explanation,  他是用 projection 的 error minimal 來解釋。如何確認是否 equivalent??

 

What is Principal Component Analysis : Eigenvalue and Eigenvector 數學解釋

Consider a data set of n points x_jj=1,ldots,n in mathbf{R}^m. We can represent this data set as a m times n matrix X = [x_1 , ldots, x_n], where each x_j is a n-vector. The variance maximization problem is to find a direction u in mathbf{R}^m such that the sample variance of the corresponding vector u^TX = (u^Tx_1,ldots,u^Tx_n) is maximal.

Recall that when u is normalized, the scalar u^Tx is the component of x along u, that is, it corresponds to the projection of x on the line passing through 0 and with direction u.

Here, we seek a (normalized) direction u such that the empirical variance of the projected values u^Tx_ju=1,ldots,n, is large. If hat{x} is the vector of averages of the x_j‘s, then the average of the projected values is u^That{x}. Thus, the direction of maximal variance is one that solves the optimization problem

 max_{u ::: |u|_2 = 1} : frac{1}{n} sum_{j=1}^n left( (x_j-hat{x})^Tu right)^2.  

The above problem can be formulated as

 max_{u ::: |u|_2 = 1} : u^TSigma u,  

where

 Sigma := frac{1}{n} sum_{j=1}^n (x_j-hat{x})(x_j-hat{x})^T   

is the m times m sample covariance matrix of the data.

 

以上的數學解釋其實和直觀解釋一致,只差求解部份。optimization 問題本身是一個 constraint quadratic optimization 問題。

因為 covariance matrix sigma 是 positive semi-definite (PSD==symmetry), 因此是 convex optimization. (wrong!, 因為是 max, 所以 negative definite 才是 convex optimization).  不過即使不是 ND or PSD.  Solution 都是一樣的,就是 abs(maximum eigenvalue)?  相反 min 就是 abs(minimum eigenvalue). (really?)

結論: PCA is NOT convex optimization!

例子如下:

NewImage

NewImage

 

更多的 variance, eigenvalue, eigenvector 解釋

 EVD:  Sigma = U Lambda U^T  (symmetry == PSD)

where Lambda = mbox{bf diag}(lambda_1,dots,lambda_n) contains the eigenvalues, and U an orthogonal matrix of eigenvectors

 max_{u ::: |u|_2 = 1} : u^TSigma u,   =  max_{u ::: |u|_2 = 1} : u^TSigma u,  = λmax  (because uU = u’, norm = 1)

反之 min (xxx) =    λmin

 

意即最大的 variance 就是等於最大的 eigenvalue, 方向就是對應的 eigenvector.

最小的 variance 就等於最小的 eigenvalue (假設 PSD), 方向就是對應的 eigenvector.

如果 eigenvalue 為 0, 代表是可以 reduce dimension.   

 

Total variance of data 定義為所有 variance sum. 也會等於所有 eigenvalue sum

 mbox{bf Tr} Sigma = mbox{bf Tr} (U Lambda U^T) = mbox{bf Tr} (U^T U Lambda) = mbox{bf Tr} Lambda = lambda_1 + ldots + lambda_n.  

當我們 project 原來 data 到兩個最大的 eigenvalue 對應 eigenvector plan 上 (其他 dimension 都 reduced!). 

When we project the data on a two-dimensional plane corresponding to the eigenvectors u_1,u_2 associated with the two largest eigenvalues lambda_1,lambda_2, we get a new covariance matrix PSigma P^T, where P= [u_1,u_2]^Tthe total variance of the projected data is

 mbox{bf Tr} (P Sigma P^T ) = lambda_1 + lambda_2.  

Hence, we can define the ratio of variance ‘‘explained’’ by the projected data as the ratio:

 frac{lambda_1 + lambda_2}{lambda_1 + ldots + lambda_n}.  

If the ratio is high, we can say that much of the variation in the data can be observed on the projected plane.

這就是 PCA 的原理!

在最大保持原有 data 的 variance 下 reduce dimension.  所謂 variance 就是 information, 也就是 data 內在的結構。

當然我們也可以反向操作。也就是挑最小的幾個 eigenvalues 以及對應的 eigenvectors,在projection 後保持最小的 variance (minimization instead of maximization).  實務上可能沒有太大的用處。因為 information 都被 toss away!   乾脆把原始 data toss away 就算了。

In summary,  PCA 對應的是  PSD (也就是 symmetry) matrix 的 eigenvalue/eigenvector decomposition.

可以用在

* Dimension reduction

* Data compression (same as above)

* Outliner detection

* PCA 的本質是 covariance matrix 的 constraint maximization (optimization).  在這個前提下 (PSD matrix), 是一個 convex optimization (wrong! 應該是 ND matrix 才是 convex optimization).  根據 Boyd, 即使非 PSD, 解也是最大的 eigenvalue.  PCA 不是 convex optimization!!!

Advertisements