全文共2520字，預計學習時長6分鐘
這周大家過得怎麼樣？酷暑來襲，趕緊來上堂課靜靜心，降降火吧。
在上周的課程中，我們提到了降維的兩種分類方式：根據根據目標值（target）的參與與否，分為有監督降維和無監督降維；其二，根據高維空間與低維空間的關係，分為線性降維和非線性降維。並且還詳細地討論了兩種線性降維方法：PCA和LDA。
線性\監督
無監督
監督
線性
PCA
LDA
非線性
ISOMAP
KLDA
在本周的課程中，我們將詳細討論非線性降維。
那麼，什麼是線性，什麼是非線性呢？一般而言，線性函數要滿足兩個條件：
PCA和LDA都是高維空間對低維空間的線性變換，因為在變換前後，高維空間和低維空間的向量都保持了同樣的性質，對於空間的任意一個向量均有：
同時滿足了可加性和齊次性，這個關係也叫做疊加原理。當一個理論用了疊加原理時，其實本質是利用了線性關係。如果我們仔細把疊加原理拆開，會發現它正對應著矩陣的乘法。事實上，矩陣的乘法就是根據線性映射的疊加原理來定義的。
在此基礎上，投影就是典型的線性變換，因為投影變換可以用矩陣來表示，而且它是對稱矩陣，矩陣的某些對角元為零，零對角元對應著相應維度的捨棄。
線性降維默認先進行投影變換，然後在找一個是其目標最大化的低維空間，這就意味著最佳的低維空間必定是高維空間無數個線性變換出的空間中的一個。PCA希望在低維空間中保持樣本的最大方差，LDA則希望類間散度大，類內散度小。如果我們更希望直接尋找一個低維空間，使其保持高維空間的結構，這個尋找最類似結構的過程往往是原始空間的非線性變換。
MDS（多維縮放）和ISOMAP（等度量映射）
數學準備：
1.流形（manifold）：局部近似歐氏空間的拓撲空間，流形上的任意一點都有鄰域近似為歐幾裡得空間。（舉個例子，你將一張忽略厚度的紙捲成一個桶狀，那麼這張紙就變成了一個三維空間的二維流形，且這張紙每一點和其鄰域近似平整）
2.內蘊空間（intrinsic space）：流形內部結構的空間
3.測地線：黎曼流形上連接兩點的局部最短的線，它於彎曲空間，類似於直線對於平直空間。
4.跡（trace）：矩陣對角元的和
MDS（Multiple Dimensional Scaling）的目標是儘可能在低維空間保持高維空間的距離信息。樣本之間的距離可以構成一個距離方陣,它的行數和列數均等於樣本數，它的對角元全部為零，因為它的每一個矩陣元都是相應樣本的距離，即:
根據我們的目標，在低維空間的樣本
有關係：
如果我們定義低維空間的內積矩陣D,每個矩陣元代表著樣本於樣本之間的內積，
,在此基礎上，
。假設低維空間的樣本被中心化：
,就有：
則M矩陣的矩陣元求和就有：
我們就可以消去
，就可以用矩陣M來表示內積矩陣D：
特徵值分解的數學本質，就是把矩陣對角化：
其中E為內積矩陣的對角化，V為對應特徵向量組成的矩陣。將其特徵值排序，取到相應的特徵向量，而它們所張成的低維空間，就是使得投影點方差最大的低維空間，但需要注意，我們是對內積矩陣做對角化，得到的對角矩陣仍然是關於內積，而不是坐標，所以我們最後得到的樣本表示為：
這就是MDS的數學原理，它輸入了一個原始空間距離矩陣，並用原始空間的距離矩陣來表示低維空間的內積矩陣，最後輸出低維空間的樣本表示。但裡面有一點可能並不合理，因為我們若要保持原始空間的距離，原始空間又是一個流形，計算樣本的歐幾裡得距離，相當於並沒有利用流形的內蘊空間。
如圖，樣本
的距離應該是紅線，而不是藍線。
ISOMAP（Isometric mapping）不再使用原始空間的歐氏距離，而是使用兩點的測地線距離。測地線的距離計算是根據流形局部具有歐氏空間的性質，對每一個點通過歐氏距離找到若干個臨近點構成連接圖，除了這幾個臨近點，其餘的點的距離均設為無窮大。通過最短路徑算法來得到兩點距離（Dijkstra算法），由此得到樣本的距離矩陣。
除了距離矩陣的定義不同，ISOMAP與MDS的原理一樣，都是通過原始空間的距離矩陣求得低維空間的內積矩陣，最後通過特徵值分解（奇異值分解）來求得低維空間的樣本表示。
KLDA（核化的線性判別分析）
數學準備：
1.kernel trick:將樣本從低維空間映射到高維空間，可以將一個非線性問題轉化為線性問題,且有核函數:
2.表示定理（Representer theorem）：正則化項單調遞增的關於
的優化函數，它的解總可以寫成
3.LDA:線性判別分析
KLDA(Kernelized Linear Discriminant Analysis)就是使用了kernel trick的LDA。我們每一個樣本做高維變換：
左圖為輸入空間，右圖為進行高維變換的空間，可以看到，經過高維變換後，分類會變得非常簡單，一組容易分開的樣本，PCA和LDA都會非常容易。
將
作為我們處理的對象：還是以二分類問題為例，樣本變成了
，樣本的均值向量變成了
，樣本的協方差矩陣變為了
，與LDA一樣，我們假設存在一個投影矩陣W，這些量會在低維空間變成：
類內散度矩陣
，類間散度矩陣就變為
：
優化目標就變為：
在計算協方差矩陣進而計算類間散度矩陣時，和計算類內散度矩陣時，都會涉及到樣本高維變換的乘積
，但我們可以用核函數來表達這個乘積，同時因為每個樣本都會做乘積，所以可以寫成矩陣的形式：
這裡的
並不是樣本的標記，我們定義指示變量
，它是一個向量，維數等於樣本數。它可以按類別挑出樣本，因為當樣本屬於
樣本時，它對應位置的元素為1，否則為零。
根據表示定理，我們重新把優化函數項寫成關於核矩陣的形式，就有：
其中，M是重寫之後的類間散度矩陣，形式比較簡單，但N是重寫的類內散度矩陣，定義為：
這樣的我們的優化目標就變成了：
繼續轉化為一個廣義瑞利商問題，進而成為奇異值分解的問題，就可求得投影以後的空間。
讀芯君開扒
課堂TIPS
ISOMAP屬於流形學習，流形重要特點就是局部結構對應於歐幾裡得空間，使得我們可以在低維空間保持流形的結構，而結構的關鍵屬性就是樣本間的距離，也正因為如此，我們對測地線的計算仍然需要對領域的樣本進行收集，實際上往往得不到有效滿足。也就是說，流形學習的好壞很大程度上取決於數據本身。
KLDA之所以是非線性的，原因就在與對高維空間的變換，然後再進行投影，投影是線性的，但變換卻是非線性的。監督學習體現在那個指示變量，它乘以核矩陣，就可以將屬於一類樣本挑出來，因為其他的為零。
其他常見的流形學習方法有，拉普拉斯特徵映射，局部線性嵌入，和局部切空間對齊，t分布的隨機臨近嵌入等。
kerneltrick是非常強大的一種工具，幾乎是機器學習的通用技術，kernel trick 到底是什麼，背後有著怎樣的意義，請關注下一周的專欄課堂。
留言 點讚 發個朋友圈
我們一起探討AI落地的最後一公裡
作者：唐僧不用海飛絲
如需轉載，請後臺留言，遵守轉載規範