流形學習中的算法研究

摘要：詳細介紹了一種新的機器學習的方法——流形學習。流形學習是一種新的非監督學習方法，可以有效地發現高維非線性數據集的內在維數并進行維數約簡，近年來越來越受到機器學習和認知科學領域的研究者的重視。目前已經出現了很多有效的流形學習算法，如等度規映射(ISOMAP)、局部線性嵌套(Locally Linear Embedding ，LLE)等。詳細講述了當前常用的幾種流形學習算法以及在流形方面已經取得的研究成果，并對流形學習目前在各方面的應用作了較為細致的闡述。最后展望了流形學習的研究發展趨勢，且提出了流形學習中仍需解決的關鍵問題。

關鍵詞：流形學習；主流形；局部線性嵌套；等度規映射；變分法；互信息

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2007)07－0214－04

0引言

機器學習過程中，往往面臨龐大的數據量，要在保證數據信息足夠完整的條件下合理地約簡數據集，是對其提出的嚴峻挑戰。以往的系統大多使用線性方法（如維數約簡中的線性主成分分析（PCA）等），通過特征的線性組合來降維，本質上是把數據投影到線性子空間，這種方法相對簡單且容易計算。但由于現實中有用特征往往不是特征的線性組合，線性方法不能有效地處理龐大的高維數據。經試驗發現，許多高維采樣數據均由少數隱含變量所決定，這些隱含變量是以嵌套在高維歐式空間的組合型非線性流形存在的。為此，本文提出了一種新的機器學習方法——流形學習算法。

目前，在流形學習上存在大量的研究方法。按照對觀測空間數據幾何結構的分析將其分成五個主要的研究領域，即神經網絡、主流形、譜分析、變分法和互信息。本文從上述幾方面對流形學習的一些方法進行了總結。

1主要研究方法與成果

1．1主流形

1．1．1主流形框架

自相合就是對于f的每個點（在X分布下）都是所有點的集合。這樣，Hastie強調主曲線的非參數方法，即曲線類型未知，在曲線簇中選擇滿足自相合的有中間性的曲線。但實驗證明這種算法存在模型偏差和估計偏差，并且在實際應用過程中經常采用局部光滑子或者樣條函數來近似尋優，這偏離了原有的自相合性質。

之后的BR主曲線[2]改進了HS主曲線的算法，減小了估計偏差對實際曲線的影響，但其產生的數據不穩定，有可能得到光滑但不正確的主曲線。T主曲線[3]引入了半參數法，算法過程中利用EM算法來估計主曲線，且假定噪聲是正態分布的，這與HS主曲線的無參數原則相背離。Kégl證明了在理論分布下定義的K主曲線[4]的存在性和唯一性，利用統計學方法用多邊形線算法來估計K主曲線。這是第一次可以證明主曲線存在，但是限制條件是曲線的長度必須預先固定。Smola提出了試圖向高維推廣的基于統計學習理論的正則主流形，采用監督學習中的量化誤差最小理論下的正則化來尋找具有多種正則項的正則主流形[5]。Delicado給出了主定向點概念和基于定向點的D主曲線[6]理論，這保持了自相合特點，并且利用參數模型可以向高維推廣。Verbeek提出了K主曲線[7]算法，即用局部主成分算法來構造K段線段，再連接成光滑的主曲線，不足之處是無法向高維推廣。

1．1．3主流形的應用

主曲線最初應用于斯坦福線性加速器上，其目標函數可由磁鐵之間的光滑度來控制。之后，在其他方面應用也很廣泛，如生態學、語音識別、智能交通[8]等。

1．2譜分析

譜分析是一種經典的數學分析方法。與經典的譜分析不同的是，流形學習中的譜分析是利用局部結構來描述整體的，不具備全局線性結構。其目的是尋找最優基函數的組合來構造數據集內在低維嵌套結構，實質上最終目標還是期望獲得具有全局線性坐標的數據結構。采用譜分析來完成流形學習的方法包括等度規映射（ISOMAP）、局部線性嵌套（LLE）、Laplacian特征映射和核主成分分析（KPCA）。

1．2．1等度規映射（Isometric Feature Mapping，ISOMAP）[9]

多維尺度變換(MDS)是一種非監督的維數約簡方法。其基本思想是:約簡后的低維空間中任意兩點間的距離應該與它們在原始空間中的距離相同。等距映射(ISOMAP)算法的基本思想是在多維尺度變換的基礎上，力求保持數據點的內在幾何性質，即保持兩點間的測地距離，如圖2所示。ISOMAP算法的核心就是要估計兩點間的測地距離:保證離得很近的點間的測地距離用歐氏距離代替；離得較遠的點間的測地距離用最短路徑來逼近。

1．2．5核主成分分析（Kernel Principal Component Analysis，KPCA）[13]

核主成分分析是利用積分算子核函數的特性來分析觀測空間數據集的結構。核函數能使數據集在特征空間的度量性質在原空間得以實現，這樣，利用核函數來構造數據集在特征空間的協方差矩陣，并求取在映射空間的結構。這使得可能在數據集的觀測空間維數較低時，獲得較高維淹沒子流形的特征分析。

1．2．6譜分析的應用

譜分析的主要作用是用于維數約簡，可以應用在數據可視化、分類等方面。在不同距離、不同方向或不同姿態和光照強度下，同一個對象能夠形成多種不同的圖像。一個對象所有圖像的集合可以看做是以位置、尺度、姿態、光照等為參數的一個高維空間流形。如果每一個像素均對應于空間中的一維，那么一幅圖像就可以看做高維圖像抽象空間中的一個點，一個對象在不同方向上所有圖像的集合就是圖像空間中的一個連續流形。利用流形學習算法，可以給出以流形存在的圖像的內在低維結構，使得降維后的圖像特征能夠有效地得到識別[14]。

1．3變分法 

從物理學的角度來看，任何一種數據集合的最終存在形式應該是一個穩態，此穩態具有最小能量。Gomes提出采用變分微積分思想來求解偏微分方程[15]。在算法上通過能量最小化迭代使數據點的鄰域關系趨近真實，從而獲得對孤立鄰域點集的全局連通，最終獲得流形結構的有效描述。產生最小能量的目標函數包括四個方面，即包含進了不屬于流形的結構域；沒有包含全部流形；引入的光滑性和連續性的約束；要求結構為凸性的約束。

1．4互信息 

互信息[16]就是在最近鄰區域和流形圖上，假設交互信息是對被觀察空間與被嵌入空間之間的不同概率分布的測量。從信息論的角度來看，在觀測空間數據集和嵌套空間數據集中近鄰數據間的概率的信息熵應該最小。

隨機鄰域映射（SNE）假設高維觀測空間每個數據點具有高斯分布，鄰域意義下概率分布定義如下：

1．5神經網絡

神經生理學上發現，在神經網絡中通過鄰近單元的相互競爭，可以自適應地發展成為對不同性質信號敏感的區域。神經網絡中的自組織映射[17]，是假定輸入數據可以通過神經網絡映射到低維空間，并保證在輸入空間數據集的近鄰關系在低維結構中可以保持。算法上假定每個輸入空間的數據點在低維嵌套空間具有一定的幾何位置，通過競爭來更新數據點的位置，然后逐漸收縮鄰域，最終獲得與輸入空間觀測數據集最近的拓撲結構。但是，這種方法由于鄰域不斷收縮，可能造成不光滑連續，且難以在高維空間進行擴展。

2流形學習中有待解決的問題

盡管流形學習的算法和應用在過去的幾年中已經取得了豐碩的成果，但是由于其數學理論基礎較為復雜，以及多個學科之間交叉、融合，對高維數據中有意義的低維結構的研究中依然有很多值得進一步探討的問題。

流形學習本身是一種全局分析方法，它跟局部分析方法應該是互補關系。如何有效地將兩者結合起來是一個需要研究的問題。

在幾何上分析高度相關、復雜分布的數據集的內在結構。流形是一種幾何研究工具，它本身作為一種發現內在規律的方法，可以作為很多相關后續處理過程的一個基礎。就目前來看，許多實際應用中的數據集合都存在規律性，因此研究流形與數據集的關系有可能成為一個重要領域。

流形的主要特征的個數與錯識率有很大的關系。在將來的工作中，必須找到一個行之有效的方法來估計主要特征的數目。怎樣使用流形的性質來模擬未知的概念和設計新的算法是今后研究的方向。

參考文獻：

［1］HASTIE T，STUETZLE W.Principal curves[J].Journal of the American Statistical Association，1988，84(406):502－516.

[2]BANFIELD J D， RAFTERY A E. Ice floe identification in satellite images using mathematical morphology and clustering about principal curves[J].Journal of the American Statistical Association，1992，87(417):7－16.

[3]TIBSHIRANI R.Principal curves revisited[J]. Statistics and Computation，1992，2:183－190.

[4]KGL B， KRZYZAK A，et al.Learning and design of principal curves[J].Trans. on Pattern Analysis and Machine Intelligence，2000， 22（3）：281－297.

[5]SMOLA A J，MIKA S，SCHOLKOPE B，et al.Regularized principal manifolds:proc.of the 4th European Conference on Couputation Learning Theory[C].New York:Springer，1999:251－256.

[6]DELICADO P.Another look at principal curves and surfaces [J].Journal of Multivariate Analysis，2001， 77(1):84－116.

[7]VERBEEK J J，VLASSIS N， KROSE B.A k－segments algorithm for finding principal curves[J].Pattern Recognition Letters，2000，23(8):1009－1017.

[8]張軍平.博士論文[D].[出版地不詳]:中國科學院自動化研究所，2003.

[9]TENENBAUM J B， VIN de SILVA， LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Scien－ce，2000，290(5500):2319－2323.

[10]ROWEIS S T，SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290（5500）:2324－2326.

[11]BELKIN M， NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data reduction and data representation[J].Neural Computation，2001， 151（6）：1373－1396.

[12]MIKHAIL B，PARTHA N.Using manifold structure for partially labelled classification:proc.of Neural Information Systems:Natural and Synthetic [C].Vancouver，Canada:MII Press，2002:9－14.

[13]SCHLKOPF B， SMOLA A， MULLER R. Nonlinear component analysis as a kernel eigenvalue problem[J].Neural Computation，1998，10(5):1229－1319.

[14]趙連偉，羅四維，趙艷敞，等.高維數據流形的低維嵌入及嵌入維數研究[J].軟件學報，2005， 16（8）：1423－1430.

[15]GOMES J，MOJSILOVIC A. A variational approach to recovering a manifold from sample points:proc.of the 7th European Conference on Computer Vision－partⅡ[C].London:Springer－Verlag，2002:3－17.

[16]HINTON G， ROWEIS S.Stochastic neighbor embedding: proc.of neural Information Systems:Natural and Synthetic[C].Cambridge:MIT press，2003:833－840.

[17]KOHONEN T.Self－organizing maps[M].New York: Springer，1997.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”