中科院自动化研究所-机器学习之一流形学习-manifoldl

MachineLearningandDataMining2004中国科学院自动化研究所流形学习问题杨剑中国科学院自动化研究所2004年12月29日MachineLearningandDataMining2004中国科学院自动化研究所维数约简增加特征数增加信息量提高准确性增加训练分类器的难度维数灾难解决办法：选取尽可能多的,可能有用的特征,然后根据需要进行特征约简.MachineLearningandDataMining2004中国科学院自动化研究所特征选择特征约简特征抽取依据某一标准选择性质最突出的特征经已有特征的某种变换获取约简特征试验数据分析，数据可视化（通常为2维或3维）等也需要维数约简特征约简MachineLearningandDataMining2004中国科学院自动化研究所线性维数约简方法流形和维数约简.流形学习的一些数学基础.几种流形学习算法简介：LLE,Isomap,LaplacianEigenmap.流形学习问题的简单探讨.OutlineMachineLearningandDataMining2004中国科学院自动化研究所线性约简方法通过特征的线性组合来降维.本质上是把数据投影到低维线性子空间.线性方法相对比较简单且容易计算.两种经典且广泛使用的线性变换的方法:主成分分析(PCA);多重判别分析(MDA).MachineLearningandDataMining2004中国科学院自动化研究所主成分分析(PCA)PCA的目的：寻找能够表示采样数据的最好的投影子空间.PCA的求解：对样本的散布矩阵进行特征值分解,所求子空间为过样本均值,以最大特征值所对应的特征向量为方向的子空间.PrincipalcomponentMachineLearningandDataMining2004中国科学院自动化研究所主成分分析PCA对于椭球状分布的样本集有很好的效果,学习所得的主方向就是椭球的主轴方向.PCA是一种非监督的算法,能找到很好地代表所有样本的方向,但这个方向对于分类未必是最有利的.MachineLearningandDataMining2004中国科学院自动化研究所线性判别分析(LDA)1LDA是一种监督的维数约简方法.LDA的思想:寻找最能把两类样本分开的投影直线.LDA的目标:使投影后两类样本的均值之差与投影样本的总类散布的比值最大.BestprojectiondirectionforclassificationMachineLearningandDataMining2004中国科学院自动化研究所线性判别分析(LDA)2LDA的求解:经过推导把原问题转化为关于样本集总类内散布矩阵和总类间散布矩阵的广义特征值问题.MachineLearningandDataMining2004中国科学院自动化研究所多重判别分析(MDA)MDA把LDA推广到多类的情况.对于c-类问题,MDA把样本投影到c-1维子空间.目标和解法与LDA相似,只是类内散布矩阵的定义更为复杂,求解的广义特征值问题也更为复杂.MachineLearningandDataMining2004中国科学院自动化研究所-1-0.500.51-1-0.500.5105101520线性方法的缺点线性方法对于很多数据不能进行有效的处理.现实中数据的有用特性往往不是特征的线性组合.RMachineLearningandDataMining2004中国科学院自动化研究所流形学习和维数约简流形是线性子空间的一种非线性推广.流形是一个局部可坐标化的拓扑空间.流形学习是一种非线性的维数约简方法.MachineLearningandDataMining2004中国科学院自动化研究所流形学习的可行性1许多高维采样数据都是由少数几个隐含变量所决定的,如人脸采样由光线亮度,人离相机的距离,人的头部姿势,人的脸部肌肉等因素决定.2从认知心理学的角度,心理学家认为人的认知过程是基于认知流形和拓扑连续性的.RMachineLearningandDataMining2004中国科学院自动化研究所流形学习的一些数学基础参考文献:陈省身,陈维桓,微分几何讲义.北京大学出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陈维桓,微分流形初步(第二版).高等教育出版社,2001MachineLearningandDataMining2004中国科学院自动化研究所集合上的拓扑是的满足以下性质的子集族:(i)对属于它的任意多元素的并集是封闭的;(ii)对属于它的有限多元素的交集是封闭的;(iii)且,称是一个拓扑空间.XXX),(X拓扑MachineLearningandDataMining2004中国科学院自动化研究所如果对空间中的任意两点存在和使得称是一个Hausdorff拓扑空间.),(X,yx)(xA)(yB,BA),(XHausdorff空间MachineLearningandDataMining2004中国科学院自动化研究所设M是一个Hausdorff拓扑空间,若对每一点都有P的一个开领域U和的一个开子集同胚,则称M为n维拓扑流形,简称为n维流形.,MpnR流形的定义MachineLearningandDataMining2004中国科学院自动化研究所假定是同胚,其中是中的开集,则称为流形M的一个坐标卡,并且把在中的坐标称为点的坐标,nRUU)(:nR),(U流形在本质上是局部可坐标化的拓扑空间.)(U)(pnR))((pUpMx1x2R2zxx:coordinateforz坐标卡MachineLearningandDataMining2004中国科学院自动化研究所设是n维流形M的两个坐标卡.若当时,和它的逆映射都是次可微的,则称是相关的.),(),,(2211UU)()(:212211112UUUUrCr21UU),(),,(2211UU相关rCMachineLearningandDataMining2004中国科学院自动化研究所设M是n维流形,假定是M上坐标卡的一个子集合,且满足以下条件:(1)构成M的一个开覆盖;(2)属于的任意两个坐标卡都是相关的;(3)是极大的,则称是M上的一个微分结构.}:),{(IU}:{IUrCrC微分结构MachineLearningandDataMining2004中国科学院自动化研究所设M是n维流形,若在M上指定了一个微分结构,则称为一个n维微分流形.属于的坐标卡称为该微分流形的容许坐标卡.当时,称M为光滑流形.rC),(MrCrC),(Ur微分流形MachineLearningandDataMining2004中国科学院自动化研究所设是定义在光滑流形M上的连续函数.若在点,存在M的一个容许坐标卡使得,是在点处光滑的函数,则称函数在点处是光滑的.RMf:Mx),(UUxRUf)(:1)(xfx光滑函数MachineLearningandDataMining2004中国科学院自动化研究所光滑映射NMf:Mx),(Ux)())((:11VVfUff)(x设M,N分别是m维,n维光滑流形,是连续映射.设,若存在M在点x处的容许坐标卡及N在点处的容许坐标卡,使得是在点处光滑的映射,则称映射在点处是光滑的.处处光滑的映射称为光滑映射.)(xf),(VMachineLearningandDataMining2004中国科学院自动化研究所光滑流形M在点x的切向量是一个满足下列条件的映射(1)有(2)有(3)有光滑流形的切向量是曲线的切向量的一种推广.vRCvx:,,xCgf);()()(gvfvgfv,,RCfx);()(fvfv).()()()()(fvxggvxfgfv,,xCgf切向量MachineLearningandDataMining2004中国科学院自动化研究所设M是m维光滑流形,用表示M在点处的全体切向量的集合,则在中有自然的线性结构,使得成为m维向量空间,称其为M在点的切空间.MTx00xMTx00xMx0MTx0切空间MachineLearningandDataMining2004中国科学院自动化研究所黎曼流形就是以光滑的方式在每一点的切空间上指定了欧氏内积的微分流形.Riemann流形RMachineLearningandDataMining2004中国科学院自动化研究所与流形学习有关的参考文献与机器学习,统计学等相关的各种杂志和会议论文~lawhiu/manifold/MachineLearningandDataMining2004中国科学院自动化研究所流形学习问题设是一个低维流形,是一个光滑嵌入,其中Dd.数据集是随机生成的,且经过f映射为观察空间的数据流形学习就是在给定观察样本集的条件下重构f和.V.deSilvaandJ.B.Tenenbaum.Globalversuslocalmethodsinnonlineardimensionalityreduction.NeuralInformationProcessingSystems15(NIPS'2002),pp.705-712,2003.dRYDRYf:}{iy)}.({iiyfx}{ix}{iyMachineLearningandDataMining2004中国科学院自动化研究所几种流形学习算法局部线性嵌入(LLE).S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.等距映射(Isomap).J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.拉普拉斯特征映射(LaplacianEigenmap).M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,Vol.15,Issue6,pp.1373–1396,2003.MachineLearningandDataMining2004中国科学院自动化研究所局部线性嵌入(LLE)前提假设：采样数据所在的低维流形在局部是线性的,即每个采样点可以用它的近邻点线性表示.学习目标：在低维空间中保持每个邻域中的权值不变,即假设嵌入映射在局部是线性的条件下,最小化重构误差.求解方法：特征值分解.MachineLearningandDataMining2004中国科学院自动化研究所LLE算法1计算每一个点的近邻点,一般采用K近邻或者邻域.2计算权值使得把用它的K个近邻点线性表示的误差最小,即通过最小化来求出.3保持权值不变,求在低维空间的象,使得低维重构误差最小.，ijWiYijWjijiXWXijWiXiXiXMachineLearningandDataMining2004中国科学院自动化研究所LLE算法示意图MachineLearningandDataMining2004中国科学院自动化研究所LLE算法的求解1计算每一个点的近邻点.2对于点和它的近邻点的权值,3令,低维嵌入是M的最小的第2到第d＋1个