3.5　特征值分解

“分而治之”的策略經常被用于機器學習的算法設計中，許多數學對象可以通過分解成多個子成分或者尋找相關特征，來更好地理解整體。例如，整數可以分解為質數。十進制整數12可以用十進制或二進制等不同方式表示，但素數分解是具有唯一性的，通過素數分解可以獲得一些有用的信息。例如，12=2×2×3，通過這個表示可以知道12不能被5整除，或者12的倍數可以被2整除等信息。同理，可以通過將矩陣分解成多個子矩陣的方法來發現原矩陣中本來不明顯的函數性質。本節將對特征值分解方法進行講解。

特征值分解（Eigen-Decomposition）是使用最廣的矩陣分解方法之一，是一種將矩陣分解成由其特征向量和特征值表示的矩陣之積的方法。

方陣A的特征向量是指與A相乘后相當于對該向量進行放縮的非0向量x：

Ax=λx

標量λ被稱為這個特征向量對應的特征值（Eigen value）。非0向量x稱為方陣A對應于特征值λ的特征向量。

“特征”在模式識別和圖像處理中是非常常見的一個詞匯。要認識和描繪一件事物，首先要找出這個事物的特征。因此，要讓計算機識別一個事物，首先就要讓計算機學會理解或者抽象出事物的特征。不論某一類事物的個體如何變換，都存在于這類事物中的共有特點才能被作為“特征”。例如，計算機視覺中常用的SIFT特征點（Scale-Invariant Feature Transform）就是一種很經典的用于視覺跟蹤的特征點，即使被跟蹤的物體的尺度、角度發生了變化，這種特征點依然能夠找到關聯。

在機器學習中，特征向量選取是整個機器學習系統中非常重要的一步。線性代數中的“特征”是抽象的。矩陣乘法對應了一個變換，是把任意一個向量變成另一個方向或長度不同的新向量。在這個變換過程中，原向量會發生旋轉、伸縮變化。如果矩陣對某一個向量或某些向量只發生伸縮（尺度）變化，而沒有產生旋轉變化（也就意味著張成的子空間沒有發生改變），這樣的向量就是特征向量。可以通過圖3.10來理解特征向量的概念。

可以看出，圖3.10中左圖通過仿射變換，發生了形變，但是，圖像的中心縱軸在變形后并未發生改變。對比上面左右兩圖中的淺色向量，可以看出其發生了方向的改變，但是深黑色向量的方向依然保持不變，因此深黑色向量可以看作該變換的一個特征向量。深黑色向量在從圖3.10左圖變換成右圖時，既沒有被拉伸也沒有被壓縮，其特征值為1。所有沿著垂直線的向量也都是特征向量，它們的特征值相等。這些沿著垂直線方向的向量構成了特征值為1的特征空間。

如果v是矩陣A的特征向量，那么任何放縮后的向量sv（s∈R，s≠0）也是矩陣A的特征向量。此外，sv和v有相同的特征值。基于特征向量的該特性，通常可以只考慮單位特征向量。假設矩陣A有n個線性無關的特征向量{x1，x2，…，xn}，它們對應的特征值分別為{λ1，λ2，…，λn}。將n個線性無關的特征向量連接一個矩陣，使得每一列是一個特征向量V=[x1，x2，…，xn]，用特征值構成一個新的向量λ=[λ₁，λ₂，…，λ_n]T，此時矩陣A的特征分解如下所示。

A=Vdiag（λ）V-1

值得注意的是，并不是所有矩陣都可以特征值分解，一個大小為Rn×n的矩陣A存在特征向量的充要條件是矩陣A含有n個線性無關的特征向量。