1流形學(xué)習(xí)專題介紹王瑞平人臉識(shí)別課題組中國(guó)科學(xué)院計(jì)算技術(shù)研究所2010/05/06@VMRGroupBookReading/project/faceId/paperreading/vlpr/1流形學(xué)習(xí)專題介紹王瑞平2010/05/06@VMRG2提綱研究背景基本知識(shí)介紹經(jīng)典方法概覽總結(jié)討論2提綱研究背景3提綱研究背景基本知識(shí)介紹經(jīng)典方法概覽總結(jié)討論3提綱研究背景4從降維問題說起降維的動(dòng)機(jī)原始觀察空間中的樣本具有極大的信息冗余樣本的高維數(shù)引發(fā)分類器設(shè)計(jì)的“維數(shù)災(zāi)難”數(shù)據(jù)可視化、特征提取、分類與聚類等任務(wù)需求4從降維問題說起降維的動(dòng)機(jī)5從降維問題說起降維的動(dòng)機(jī)增加特征數(shù)增加信息量提高準(zhǔn)確性增加訓(xùn)練分類器的難度維數(shù)災(zāi)難解決辦法：選取盡可能多的,可能有用的特征,然后根據(jù)需要進(jìn)行特征/維數(shù)約簡(jiǎn).5從降維問題說起降維的動(dòng)機(jī)增加特征數(shù)增加信息量提高準(zhǔn)確性增加6從降維問題說起降維的動(dòng)機(jī)特征選擇特征約簡(jiǎn)特征提取依據(jù)某一標(biāo)準(zhǔn)選擇性質(zhì)最突出的特征實(shí)驗(yàn)數(shù)據(jù)分析，數(shù)據(jù)可視化（通常為2維或3維）等也需要維數(shù)約簡(jiǎn)經(jīng)已有特征的某種變換獲取約簡(jiǎn)特征6從降維問題說起降維的動(dòng)機(jī)特征選擇特征約簡(jiǎn)特征提取依據(jù)某一標(biāo)7降維方法概述線性降維通過特征的線性組合來降維本質(zhì)上是把數(shù)據(jù)投影到低維線性子空間線性方法相對(duì)比較簡(jiǎn)單且容易計(jì)算代表方法主成分分析(PCA)線性判別分析(LDA)多維尺度變換(MDS)7降維方法概述線性降維8線性降維方法主成分分析(PCA)[Jolliffe,1986]降維目的：尋找能夠保持采樣數(shù)據(jù)方差的最佳投影子空間求解方法：對(duì)樣本的散度矩陣進(jìn)行特征值分解,所求子空間為經(jīng)過樣本均值,以最大特征值所對(duì)應(yīng)的特征向量為方向的子空間Principalcomponent8線性降維方法主成分分析(PCA)[Jolliffe,19線性降維方法主成分分析(PCA)[Jolliffe,1986]PCA對(duì)于橢球狀分布的樣本集有很好的效果,學(xué)習(xí)所得的主方向就是橢球的主軸方向.PCA是一種非監(jiān)督的算法,能找到很好地代表所有樣本的方向,但這個(gè)方向?qū)τ诜诸愇幢厥亲钣欣?線性降維方法主成分分析(PCA)[Jolliffe,110線性降維方法線性判別分析(LDA)[Fukunaga,1991]降維目的：尋找最能把兩類樣本分開的投影直線，使投影后兩類樣本的均值之差與投影樣本的總類散度的比值最大求解方法：經(jīng)過推導(dǎo)把原問題轉(zhuǎn)化為關(guān)于樣本集總類內(nèi)散度矩陣和總類間散度矩陣的廣義特征值問題Bestprojectiondirectionforclassification10線性降維方法線性判別分析(LDA)[Fukunaga,11降維方法概述線性降維主成分分析(PCA)[Jolliffe,1986]線性判別分析(LDA)[Fukunaga,1991]PCALDA11降維方法概述線性降維PCALDA12降維方法概述線性降維主成分分析(PCA)[Jolliffe,1986]線性判別分析(LDA)[Fukunaga,1991]多維尺度變換(MDS)[Cox,1994]xixjdijMappingzizjgij原始空間，可能非歐式低維歐式空間12降維方法概述線性降維xixjdijMappingzizj13線性降維方法的不足原始數(shù)據(jù)無法表示為特征的簡(jiǎn)單線性組合比如：PCA無法表達(dá)Helix曲線流形1-DHelix曲線流形13線性降維方法的不足原始數(shù)據(jù)無法表示為特征的簡(jiǎn)單線性組合114線性降維方法的不足真實(shí)數(shù)據(jù)中的有用信息不能由線性特征表示比如：如何獲取并表示多姿態(tài)人臉的姿態(tài)信息比如：如何獲取運(yùn)動(dòng)視頻序列中某個(gè)動(dòng)作的對(duì)應(yīng)幀#1引自J.B.Tenenbaumetal.2000#2引自Jenkinset.al,IROS2002#2#114線性降維方法的不足真實(shí)數(shù)據(jù)中的有用信息不能由線性特征表示15降維方法概述線性降維傳統(tǒng)非線性降維核主成分分析(KPCA)[Scholkopf,1998]主曲線(PrincipalCurves)[Hastie,1989][Tibshirani,1992]自組織映射(SOM)[Kohonen,1995]產(chǎn)生式拓?fù)溆成?GTM)[Bishop,1998]…15降維方法概述線性降維16降維方法概述基于流形學(xué)習(xí)的非線性降維保距特征映射(ISOMAP)[Tenenbaum,2000]局部線性嵌入(LLE)[Roweis,2000]拉普拉斯特征映射(LE,LaplacianEigenmap)[Belkin,2001]HessianLLE(HLLE)[Donoho,2003]局部切空間對(duì)齊(LTSA,LocalTangentSpaceAlignment)[Zhang,2004]最大方差展開(MVU/SDE,MaximumVarianceUnfolding)[Weinberger,2004]局部保持映射(LocalityPreservingProjections)[He,2003]…16降維方法概述基于流形學(xué)習(xí)的非線性降維17提綱研究背景基本知識(shí)介紹經(jīng)典方法概覽總結(jié)討論17提綱研究背景18流形學(xué)習(xí)框架什么是流形？流形是線性子空間的一種非線性推廣拓?fù)鋵W(xué)角度：局部區(qū)域線性，與低維歐式空間拓?fù)渫呶⒎謳缀谓嵌龋河兄丿Bchart的光滑過渡黎曼流形就是以光滑的方式在每一點(diǎn)的切空間上指定了歐氏內(nèi)積的微分流形#1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow18流形學(xué)習(xí)框架什么是流形？#1引自S.T.Roweis19流形的數(shù)學(xué)定義設(shè)是一個(gè)Hausdorff拓?fù)淇臻g，若對(duì)每一點(diǎn)都有的一個(gè)開鄰域和的一個(gè)開子集同胚,則稱為維拓?fù)淞餍?簡(jiǎn)稱為維流形.流形學(xué)習(xí)框架#1引自M.H.Law,2004#1Mx1x2R2Rnzxx:coordinateforzU19流形的數(shù)學(xué)定義流形學(xué)習(xí)框架#1引自M.H.Law,20一些基本數(shù)學(xué)概念拓?fù)?，Hausdorff空間，坐標(biāo)卡，微分結(jié)構(gòu)光滑函數(shù)，光滑映射，切向量，切空間…參考文獻(xiàn)陳省身,陳維桓,微分幾何講義.北京大學(xué)出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陳維桓,微分流形初步(第二版).高等教育出版社,2001流形學(xué)習(xí)框架20一些基本數(shù)學(xué)概念流形學(xué)習(xí)框架21流形學(xué)習(xí)的目的流形學(xué)習(xí)是一種非線性的維數(shù)約簡(jiǎn)方法高維觀察數(shù)據(jù)的變化模式本質(zhì)是由少數(shù)幾個(gè)隱含變量所決定的如：人臉采樣由光線亮度、人與相機(jī)的距離、人的頭部姿勢(shì)、人的面部表情等因素決定從認(rèn)知心理學(xué)的角度，心理學(xué)家認(rèn)為人的認(rèn)知過程是基于認(rèn)知流形和拓?fù)溥B續(xù)性的流形學(xué)習(xí)框架#1引自Linetal.PAMI2008#121流形學(xué)習(xí)的目的流形學(xué)習(xí)框架#1引自Linetal.22流形學(xué)習(xí)的數(shù)學(xué)定義設(shè)

是一個(gè)低維流形,是一個(gè)光滑嵌入,其中D>d.數(shù)據(jù)集是隨機(jī)生成的,且經(jīng)過f映射為觀察空間的數(shù)據(jù)流形學(xué)習(xí)就是在給定觀察樣本集的條件下重構(gòu)

f

和.V.deSilvaandJ.B.Tenenbaum.Globalversuslocalmethodsinnonlineardimensionalityreduction.NeuralInformationProcessingSystems15(NIPS'2002),pp.705-712,2003.22流形學(xué)習(xí)的數(shù)學(xué)定義設(shè)是一個(gè)23非線性降維高維數(shù)據(jù)空間data/observationspace低維嵌入空間embedding/coordinatespace保持一定幾何拓?fù)潢P(guān)系，如測(cè)地距離/鄰域線性重構(gòu)關(guān)系流形學(xué)習(xí)示例23非線性降維高維數(shù)據(jù)空間低維嵌入空間保持一定幾何拓?fù)潢P(guān)系，24提綱研究背景基本知識(shí)介紹經(jīng)典方法概覽總結(jié)討論24提綱研究背景25經(jīng)典流形學(xué)習(xí)方法一覽方法簡(jiǎn)稱所保持的幾何屬性全局/局部關(guān)系計(jì)算復(fù)雜度ISOMAP點(diǎn)對(duì)測(cè)地距離全局非常高LLE局部線性重構(gòu)關(guān)系局部低LE局部鄰域相似度局部低HLLE局部等距性局部高LTSA局部坐標(biāo)表示全局+局部低MVU局部距離全局+局部非常高Logmap測(cè)地距離與方向局部非常低DiffusionMapsdiffusion距離全局中等25經(jīng)典流形學(xué)習(xí)方法一覽方法簡(jiǎn)稱所保持的幾何屬性全局/局部關(guān)26經(jīng)典方法分類結(jié)構(gòu)圖26經(jīng)典方法分類結(jié)構(gòu)圖27等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部線性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重點(diǎn)介紹的幾個(gè)方法27等距映射(ISOMAP)重點(diǎn)介紹的幾個(gè)方法28等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部線性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重點(diǎn)介紹的幾個(gè)方法28等距映射(ISOMAP)重點(diǎn)介紹的幾個(gè)方法29代表性算法-1ISOMAP(Isometricfeaturemapping)保持全局測(cè)地距離測(cè)地距離反映數(shù)據(jù)在流形上的真實(shí)距離差異等距映射基于線性算法MDS，采用“測(cè)地距離”作為數(shù)據(jù)差異度量#1引自J.B.Tenenbaumetal.2000#1歐式距離vs.測(cè)地距離最短路徑近似測(cè)地距離降維嵌入空間29代表性算法-1ISOMAP(Isometricfea30多維尺度變換(MDS)MDS是一種非監(jiān)督的維數(shù)約簡(jiǎn)方法.MDS的基本思想:約簡(jiǎn)后低維空間中任意兩點(diǎn)間的距離應(yīng)該與它們?cè)谠呔S空間中的距離相同.MDS的求解:通過適當(dāng)定義準(zhǔn)則函數(shù)來體現(xiàn)在低維空間中對(duì)高維距離的重建誤差,對(duì)準(zhǔn)則函數(shù)用梯度下降法求解,對(duì)于某些特殊的距離可以推導(dǎo)出解析解法.30多維尺度變換(MDS)MDS是一種非監(jiān)督的維數(shù)約簡(jiǎn)31MDS的準(zhǔn)則函數(shù)31MDS的準(zhǔn)則函數(shù)32MDS的示意圖32MDS的示意圖33MDS的失效33MDS的失效34測(cè)地線:流形上連接兩個(gè)點(diǎn)的最短曲線例如：球面上的測(cè)地線就是球面上的大圓弧測(cè)地距離：測(cè)地線的長(zhǎng)度ABFigurefrom/GreatCircle.html測(cè)地距離34測(cè)地線:流形上連接兩個(gè)點(diǎn)的最短曲線ABFiguref35ISOMAP算法流程1計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn)(用K近鄰或鄰域).2在樣本集上定義一個(gè)賦權(quán)無向圖如果和互為近鄰點(diǎn),則邊的權(quán)值為3計(jì)算圖中兩點(diǎn)間的最短距離,記所得的距離矩陣為

.4用MDS求低維嵌入坐標(biāo),

令低維嵌入是

的第1大到第d大的特征值所對(duì)應(yīng)的特征向量.35ISOMAP算法流程1計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn)(用K近鄰或36M.Bernstein,V.Silva,J.C.Langford,J.B.Tenenbaum證明了如下的漸進(jìn)收斂定理.假設(shè)采樣點(diǎn)是隨機(jī)均勻抽取的,則

漸進(jìn)收斂定理給定

則只要樣本集充分大且適當(dāng)選擇K,不等式

至少以概率成立.圖距離逼近測(cè)地距離36M.Bernstein,V.Silva,J.C.37ISOMAP實(shí)驗(yàn)結(jié)果FiguresfromISOMAPpaper37ISOMAP實(shí)驗(yàn)結(jié)果FiguresfromISOMA38Figurefrom/handfig.htmlISOMAP實(shí)驗(yàn)結(jié)果38Figurefromhttp://isomap.st39FiguresfromISOMAPpaperISOMAP實(shí)驗(yàn)結(jié)果39FiguresfromISOMAPpaperISO40InterpolationonStraightLinesintheProjectedCo-ordinatesFiguresfromISOMAPpaper40InterpolationonStraightLi41代表性算法-1ISOMAP(Isometricfeaturemapping)前提假設(shè)數(shù)據(jù)所在的低維流形與歐式空間的一個(gè)子集整體等距該歐式空間的子集是一個(gè)凸集思想核心較近點(diǎn)對(duì)之間的測(cè)地距離用歐式距離代替較遠(yuǎn)點(diǎn)對(duì)之間的測(cè)地距離用最短路徑來逼近算法特點(diǎn)適用于學(xué)習(xí)內(nèi)部平坦的低維流形不適于學(xué)習(xí)有較大內(nèi)在曲率的流形計(jì)算點(diǎn)對(duì)間的最短路徑比較耗時(shí)41代表性算法-1ISOMAP(Isometricfea42ISOMAP-summaryInheritsfeaturesofMDSandPCA:guaranteedasymptoticconvergencetotruestructurePolynomialruntimeNon-iterativeAbilitytodiscovermanifoldsofarbitrarydimensionalityPerformwellwhendataisfromasinglewellsampledclusterFewfreeparametersGoodtheoreticalbaseforitsmetricspreservingproperties42ISOMAP-summaryInheritsfea43ProblemswithISOMAPEmbeddingsarebiasedtopreservetheseparationoffarawaypoints,whichcanleadtodistortionoflocalgeometryFailstonicelyprojectdataspreadamongmultipleclustersWell-conditionedalgorithmbutcomputationallyexpensiveforlargedatasets43ProblemswithISOMAPEmbeddin44ImprovementstoISOMAPConformalIsomap–capableoflearningthestructureofcertaincurvedmanifoldsLandmarkIsomap–approximateslargeglobalcomputationsbyamuchsmallersetofcalculationReconstructdistancesusingk/2closestobjects,aswellask/2farthestobjects44ImprovementstoISOMAPConfor45等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部線性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重點(diǎn)介紹的幾個(gè)方法45等距映射(ISOMAP)重點(diǎn)介紹的幾個(gè)方法46代表性算法-2LLE(Locallylinearembedding)顯式利用“局部線性”的假設(shè)保持局部鄰域幾何結(jié)構(gòu)–重構(gòu)權(quán)重權(quán)重對(duì)樣本集的幾何變換具有不變性46代表性算法-2LLE(Locallylineare47代表性算法-2LLE(Locallylinearembedding)前提假設(shè)采樣數(shù)據(jù)所在的低維流形在局部是線性的每個(gè)采樣點(diǎn)均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示學(xué)習(xí)目標(biāo)低維空間中保持每個(gè)鄰域中的重構(gòu)權(quán)值不變?cè)谇度胗成錇榫植烤€性的條件下，最小化重構(gòu)誤差最終形式化為特征值分解問題47代表性算法-2LLE(Locallylineare48LLE算法示意圖48LLE算法示意圖49LLE算法流程

1計(jì)算每一個(gè)點(diǎn)的近鄰點(diǎn),一般采用K近鄰或者鄰域.2計(jì)算權(quán)值使得把用它的K個(gè)近鄰點(diǎn)線性表示的誤差最小,即通過最小化來求出.3保持權(quán)值不變,求在低維空間的象,使得低維重構(gòu)誤差最小.49LLE算法流程1計(jì)算每一個(gè)點(diǎn)的近鄰點(diǎn),50LLE算法的求解1計(jì)算每一個(gè)點(diǎn)的近鄰點(diǎn).2對(duì)于點(diǎn)和它的近鄰點(diǎn)的權(quán)值,3令,低維嵌入是M的最小的第2到第d＋1個(gè)特征向量.

50LLE算法的求解1計(jì)算每一個(gè)點(diǎn)的近鄰點(diǎn).51LLE實(shí)驗(yàn)結(jié)果51LLE實(shí)驗(yàn)結(jié)果52LLE實(shí)驗(yàn)結(jié)果52LLE實(shí)驗(yàn)結(jié)果53LLE實(shí)驗(yàn)結(jié)果鄰域參數(shù)的影響53LLE實(shí)驗(yàn)結(jié)果鄰域參數(shù)的影響54FigurefromLLEpaperLLE實(shí)驗(yàn)結(jié)果54FigurefromLLE實(shí)驗(yàn)結(jié)果55LLE實(shí)驗(yàn)結(jié)果55LLE實(shí)驗(yàn)結(jié)果56代表性算法-2LLE(Locallylinearembedding)優(yōu)點(diǎn)算法可以學(xué)習(xí)任意維的局部線性的低維流形算法歸結(jié)為稀疏矩陣特征值計(jì)算，計(jì)算復(fù)雜度相對(duì)較小缺點(diǎn)算法所學(xué)習(xí)的流形只能是不閉合的算法要求樣本在流形上是稠密采樣的算法對(duì)樣本中的噪聲和鄰域參數(shù)比較敏感56代表性算法-2LLE(Locallylineare57NumericalIssuesCovariancematrixusedtocomputeWcanbeill-conditioned,regularizationneedstobeusedSmalleigenvaluesaresubjecttonumericalprecisionerrorsandtogettingmixedBut,sparsematricesusedinthisalgorithmmakeitmuchfasterthenIsomap57NumericalIssuesCovariancem58等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部線性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重點(diǎn)介紹的幾個(gè)方法58等距映射(ISOMAP)重點(diǎn)介紹的幾個(gè)方法59代表性算法-3LE(LaplacianEigenmap)基本思想：在高維空間中離得很近的點(diǎn)投影到低維空間中的象也應(yīng)該離得很近.求解方法：求解圖拉普拉斯算子的廣義特征值問題.59代表性算法-3LE(LaplacianEigenma60拉普拉斯算子設(shè)M是光滑的黎曼流形,f是M上的光滑函數(shù),是f的梯度,則稱線性映射為M上的拉普拉斯算子,其中div是散度算子.60拉普拉斯算子設(shè)M是光滑的黎曼流形,f是M上61圖上的拉普拉斯算子設(shè)G是一個(gè)圖,v是它的頂點(diǎn),是v的自由度,w(u,v)是連接頂點(diǎn)u,v的邊的權(quán)值,令

其中T

是對(duì)角矩陣,對(duì)角線的元素為

,則稱L

為圖G上的拉普拉斯算子.61圖上的拉普拉斯算子設(shè)G是一個(gè)圖,v是它的頂點(diǎn),62LaplacianEigenmap算法流程1從樣本點(diǎn)構(gòu)建一個(gè)近鄰圖,圖的頂點(diǎn)為樣本點(diǎn),離得很近兩點(diǎn)用邊相連(K近鄰或鄰域).2給每條邊賦予權(quán)值如果第

個(gè)點(diǎn)和第j個(gè)點(diǎn)不相連，權(quán)值為0，否則;3計(jì)算圖拉普拉斯算子的廣義特征向量,求得低維嵌入.令D為對(duì)角矩陣L是近鄰圖上的拉普拉斯算子,求解廣義特征值問題.62LaplacianEigenmap算法流程1從樣本63LaplacianEigenmap實(shí)驗(yàn)結(jié)果(1)63LaplacianEigenmap實(shí)驗(yàn)結(jié)果(1)64300mostfrequentwordsoftheBrowncorpusrepresentedinthespectraldomainLaplacianEigenmap實(shí)驗(yàn)結(jié)果(2)64300mostfrequentwordsoft65LaplacianEigenmap實(shí)驗(yàn)結(jié)果(2)Thefirstisexclusivelyinfinitivesofverbs,thesecondcontainsprepositionsandthethirdmostlymodalandauxiliaryverbs.Weseethatsyntacticstructureiswell-preserved.

65LaplacianEigenmap實(shí)驗(yàn)結(jié)果(2)The66代表性算法-3LE(LaplacianEigenmap)優(yōu)點(diǎn)算法是局部非線性方法，與譜圖理論有很緊密的聯(lián)系.算法通過求解稀疏矩陣的特征值問題解析地求出整體最優(yōu)解，效率非常高算法使原空間中離得很近的