高维特征降维技术

高维降维理论与技术高维降维理论与技术 吴飞浙江大学计算机学院2021年3月Email:1ReferenceTurk,MatthewA.;Pentland,AlexP.FaceRecognitionusingEigenface，Proc IEEE CVPR 1991,p586-591M.S.Bartlett,H.M.Lades,andT.J.Sejnowski.IndependentComponentRepresentationsforFaceRecognition,InProc.SPIEConf.onHumanVisionandElectronicImagingIII,volume3299,pages528-539,1998.JBTenenbaumetc.AGlobalGeometricFrameworkforNonlinearDimensionalityReduction,Science 290(5500):2319-2323,22December2000SamT.Roweis,LawrenceK.Saul,NonlinearDimensionalityReductionbyLocallyLinearEmbedding,Science 290(5500):2323-2326,22December2000特征降维的意义特征降维的意义Complexstimulicanberepresentedbypointsinahigh-dimensionalvectorspaceTheytypicallyhaveamuchmorecompactdescriptionDimensionalityreduction:findingmeaningfulhiddenlow-dimensionalstructures中心极限定律与维数灾难特征降维的意义特征降维的意义CurseofDimensionality：维数灾难ThetermdimensionalitycurseisoftenusedasavagueindicationthathighdimensionalitycausesproblemsinsomesituationsThetermwasfirstusedbyBellmanin1967forcombinatorialestimationofmultivariatefunctions.维数如果超过15维，那么QueryPoint距离与最远邻居最近，使得欧拉距离失去意义人脑生理特性对特征约减研究的启发人脑生理特性对特征约减研究的启发l由由于于人人脑脑对对外外界界认认知知的的手手段段多多样样而而导导致致获获取取的的信信息息维维数数过过高高，如如人人脑脑有有三三千千个个听听觉觉神神经经纤纤维维和和一一百百万万个个视视觉觉神神经经纤纤维维人人脑脑总总共大概有共大概有100100亿左右的神经纤维亿左右的神经纤维l如如果果不不进进行行降降维维处处理理将将导导致致人人脑脑对对信信息息处处理理的的效效率率和和精精确确度度下下降降，因因此此人人脑脑在在对对这这些些感感知知神神经经纤纤维维处处理理时时，均均通通过过了了复复杂杂的的降降维处理维处理Tenenbaum 2000Tenenbaum 2000。lB.B.Tenenbaum,Tenenbaum,V.V.De De Silva,Silva,J.J.C.C.Langford,Langford,A A Global Global Geometric Geometric Framework Framework for for Nonlinear Nonlinear Dimensionality Dimensionality Reduction,Science 290(5500):22,December 2000Reduction,Science 290(5500):22,December 2000特征约减的必要性：以人脸为例特征约减的必要性：以人脸为例太阳系宇宙所有电子总量太阳系宇宙所有电子总量太阳系宇宙所有电子总量太阳系宇宙所有电子总量1010的的的的7979次方次方次方次方大脑对外界信息感知：只会处理大脑对外界信息感知：只会处理“有意义局有意义局部部图形图形图形图形:含有含有含有含有1000010000三角面片的三角面片的三角面片的三角面片的3D3D地形模型地形模型地形模型地形模型(丘陵丘陵丘陵丘陵)图象图象图象图象:216*252:216*252个象素点个象素点个象素点个象素点（人脸）（人脸）（人脸）（人脸）音频音频音频音频:10000:10000个采样点构成的个采样点构成的个采样点构成的个采样点构成的1 1秒长秒长秒长秒长度音频（爆炸）度音频（爆炸）度音频（爆炸）度音频（爆炸）视频视频视频视频:25-30:25-30帧帧帧帧/秒采样率秒采样率秒采样率秒采样率 构成的视构成的视构成的视构成的视频流（运动）频流（运动）频流（运动）频流（运动）什么什么是特是特征？征？特征降维方法：特征人脸方法特征降维方法：特征人脸方法子空间Subspace方法也就是平常说的奇异值分解方法SingularValueDecomposition或者主成分分析方法PrincipleComponentAnalysisEigenX方法，如EigenEye,EigenFinger、Eigen-edge等等方法Turk,MatthewA.;Pentland,AlexP.FaceRecognitionusingEigenface，Proc IEEE CVPR 1991,p586-591特征人脸方法已成为经典的算法2021年3月23日GoogleScholar查询得到的引用率特征降维方法特征降维方法奇异值分解理论特征降维方法特征降维方法奇异值分解示列P值越大，丧失信息越少。特征维数很高时，一值越大，丧失信息越少。特征维数很高时，一些特征根很微小，甚至为零，那么可以忽略。些特征根很微小，甚至为零，那么可以忽略。如果将矩阵A看成由0.96，1.72和2.28，0.96两个2维的对象组成，为了将这两个对象由2维降维成1维，我们可以如下处理：0.96，1.72*0.6，0.8=1.9522.28，0.96*0.6，0.8=2.136形式上而言，2维对象由2维空间被映射到了1维空间，从而被降维特征降维方法特征降维方法隐性语义索引奇异值分解方法在文本分析中也叫做隐藏语义索引Latent Semantic Indexing特征降维方法特征降维方法隐性语义索引：建立文档词汇矩阵Query:Computer-basedinformationlook-upAnR“inthecolumnlabeledREL(relevant)indicatesthattheuserwouldhavejudgedthedocumentrelevanttothequery(heredocuments1and3arerelevant).Termsoccurringinboththequeryandadocument(computer andinformation)areindicatedbyanasteriskintheappropriatecell;anMintheMATCHcolumnindicatesthatthedocumentmatchesthequeryandwouldhavebeenreturnedtotheuser.Documents1and2illustratecommonclassesofproblemswithwhichtheproposedmethoddeals.Document1isarelevantdocument,which,however,containsnoneofthewordsinthequery.Itwould,therefore,notbereturnedbyastraightforwardtermoverlapretrievalscheme.Document2isanon-relevantdocumentwhichdoescontaintermsinthequery,andthereforewouldbereturned,despitethefactthatthequerycontextmakesitclearenoughtoahumanobserverthatadifferentsenseofatleastoneofthewordsisintended.特征降维方法特征降维方法隐性语义索引：文档词汇隐藏关系的索引下面的处理方式与SVD处理根本雷同特征降维方法特征降维方法隐性语义索引：文档词汇隐藏关系的索引特征降维方法特征降维方法隐性语义索引：文档词汇隐藏关系的索引Therearetwoclassesofdocuments:fiveabouthuman-computerinteraction(c1-c5)andfouraboutgraphs(m1-m4).Ifwesetourselvesistofinddocumentsrelevanttothequery:humancomputerinteraction.Simpletermmatchingtechniqueswouldreturndocumentsc1,c2andc4sincetheyshareoneormoretermswiththequery.However,twootherdocumentswhicharealsorelevant(c3andc5)aremissedbythismethodsincetheyhavenotermsincommonwiththequery.SVD Decomposition对得到的Term-Document矩阵进行SVD分解SVD for Technical Memo ExampleSVD for Technical Memo ExampleSVD for Technical Memo Example选取最大的2个特征根及其对应的特征向量Computing fundamental comparison quantities from the SVD modelThreebasicallysortsofcomparisonsofinterest:Comparingtwoterms(How similar are terms i and j?)Comparingtwodocuments(How similar are documents i and j?),Comparingatermandadocument(How associated are term i and document j?).Instandardinformationretrievalapproaches,theseamountrespectively,tocomparingtworows,comparingtwocolumns,orexaminingindividualcellsoftheoriginalmatrixoftermbydocumentdata,XHerewemakesimilarcomparisons,butusethematrixXhihat,sinceitispresumedtorepresenttheimportantandreliablepatternsunderlyingthedatainXComputing two termsComputing two documentsComputing a term and a documentSVD for Technical Memo ExampleBefore SVD and After SVD for Technical Memo ExampleBeforeAfter百度输入百度输入“杨卫后的隐性文法分析结果杨卫后的隐性文法分析结果谷歌输入谷歌输入“杨卫后的隐性文法分析结果杨卫后的隐性文法分析结果特征降维：特征人脸方法特征降维：特征人脸方法人脸图像表示PrincipalComponentAnalysisAN x Npixelimageofaface,representedasavectoroccupiesasinglepointinN2-dimensionalimagespace.Imagesoffacesbeingsimilarinoverallconfiguration,willnotberandomlydistributedinthishugeimagespace.Therefore,theycanbedescribedbyalowdimensionalsubspace.MainideaofPCA:Tofindvectorsthatbestaccountforvariationoffaceimagesinentireimagespace.Thesevectorsarecalledeigenvectors.Constructafacespaceandprojecttheimagesintothisfacespace(eigenfaces).特征降维：特征人脸方法特征降维：特征人脸方法Image RepresentationTrainingsetofimagesofsizeN*NarerepresentedbyvectorsofsizeN21,2,3,MExample AverageImageandDifferenceImagesTheaveragetrainingsetisdefinedby=(1/M)Mi=1i Eachfacediffersfromtheaveragebyvectori=i CovarianceMatrixAcovariancematrixisconstructedas:C=AAT,whereA=1,MofsizeN2xN2FindingeigenvectorsofN2xN2 matrixisintractable.Hence,usethematrixATAofsizeM xMandfindeigenvectorsofthissmallmatrix.SizeofthismatrixisM*MSizeofthismatrixisN2xN2EigenvaluesandEigenvectors-DefinitionIfvisanonzerovectorandisanumbersuchthatAv=v,thenvissaidtobeaneigenvectorofAwitheigenvalue.ExampleHowtoCalculateEigenvectors?EigenvectorsofCovarianceMatrix TheeigenvectorsviofATAare:ConsidertheeigenvectorsviofATAsuchthatATAvi=iviPremultiplyingbothsidesbyA,wehaveAAT(Avi)=i(Avi)Face SpaceTheeigenvectorsofcovariancematrixareui=Aviuiresemblefacialimageswhichlookghostly,hencecalledeigenfacesProjectionintoFaceSpaceAfaceimagecanbeprojectedintothisfacespaceby k=UT(k);k=1,MRecognitionThetestimage,isprojectedintothefacespacetoobtainavector,:=UT()Thedistanceoftoeachfaceclassisdefinedbyk2=|-k|2;k=1,MAdistancethreshold,c,ishalfthelargestdistancebetweenanytwofaceimages:c=maxj,k|j-k|;j,k=1,MRecognitionFindthedistance,betweentheoriginalimage,anditsreconstructedimagefromtheeigenfacespace,f,2=|f|2,wheref=U*+Recognitionprocess:IFctheninputimageisnotafaceimage;IFcANDkcforallktheninputimagecontainsanunknownface;IFcANDk*=minkkctheninputimagecontainsthefaceofindividualk*LimitationsofEigenfacesApproachVariationsinlightingconditionsDifferentlightingconditionsforenrolmentandquery.Brightlightcausingimagesaturation.DifferencesinposeHeadorientation-2Dfeaturedistancesappeartodistort.Expression-Changeinfeaturelocationandshape.LinearDiscriminantAnalysisPCAdoesnotuseclassinformationPCAprojectionsareoptimalforreconstructionfromalowdimensionalbasis,theymaynotbeoptimalfromadiscriminationstandpoint.LDAisanenhancementtoPCAConstructsadiscriminantsubspacethatminimizesthescatterbetweenimagesofsameclassandmaximizesthescatterbetweendifferentclassimagesMeanImagesLetX1,X2,XcbethefaceclassesinthedatabaseandleteachfaceclassXi,i=1,2,chaskfacialimagesxj,j=1,2,k.WecomputethemeanimageiofeachclassXias:Now,themeanimageofalltheclassesinthedatabasecanbecalculatedas:ScatterMatricesWecalculatewithin-classscattermatrixas:Wecalculatethebetween-classscattermatrixas:ProjectionWefindtheproductofSW-1andSBandthencomputetheEigenvectorsofthisproduct(SW-1.SB).Usesametechniqueaseigenfacesapproachtoreducethedimensionalityofscattermatrixtocomputeeigenvectors.FormamatrixUthatrepresentsalleigenvectorsofSW-1.SBbyplacingeacheigenvectoruiaseachcolumninthatmatrix.EachfaceimagexjXicanbeprojectedintothisfacespacebytheoperationi=UT(xj)特征降维：特征人脸方法特征降维：特征人脸方法特征人脸根据人脸协方差矩阵求取特征根和特征向量；每个特征向量是一个特征人脸；将特征根进行排序，选取前假设干个最大的特征根所对应的特征向量组成了“人脸空间；完成了从“像素点空间到“人脸空间的转换特征降维特征降维：特征人脸方法：特征人脸方法特征人脸：例如400个人脸与对应的36个特征人脸非负矩阵分解non-negativematrixfactorization针对先前矩阵分解过程中可能出现负数，而使得分解结果失去意义的局限性，非负矩阵分解被提出，其意义在于以非线性的方式实现对非负多元数据的局部化、线性和低维描述，它为分析局部特征和整体特征之间的关系提供了一种思路，即整体特征是局部特征的非负线性组合，局部特征在构成整体特征时不会产生正负抵消的情况 D.D.Lee,H.S.Seung,Learningthepartsofobjectsbynon-negativematrixfactorization,Nature401,788-791(1999)H.S.SeungandD.D.Lee.TheManifoldwaysofperception,Science290,2268-69(2000)IntroductionNMF(NonnegativeMatrixFactorization):Theory:Perceptionofthewholeisbasedonperceptionofitsparts.Comparisonwithanothertwomatrixfactorizationmethods:PCA(PrincipleComponentsAnalysis)VA(Vectorquantization)Comparison:Commonfeatures:Representafaceasalinearcombinationofbasisimages.Matrixfactorization:VWHV:nmmatrix.Eachcolumnofwhichcontainsnnonnegativepixelvaluesofoneofthemfacialimages.W:(nr):rcolumnsofWarecalledbasisimages.H:(rm):eachcolumnofHiscalledencoding.Comparison(contd)NMFPCAVQRepresentation:parts-BasedholisticholisticBasisImage:localizedfeatureseigenfaceswholefaceConstrainsonallowmultipleeachfaceiseachcolumnofHisWandH:basisimagestoapproximatedby constrainedtobearepresentaface,alinearcombi-unaryvector,everybutonlyadditive nationofallfaceisapproximat-combinationstheeigenfacesedbyasinglebasisimage.DatarepresentationNon-negativeConstraintsConstraints矩阵W和H的元素只能为非负值W：BaseimageH：EncodingExamplePCAExampleNMFIsperceptionoftheWholebasedonperceptionofitsParts?Thereispsychologicalandphysiological evidenceforpart-basedrepresentationinthebrainNMF:tolearnpartsPCA:tolearnholistic,notparts-basedNothaveobviousvisualinterpretationImplementationofNMFLimitationofNMFNotsuitableforlearningpartsforcomplexcases:requirefullyhierarchicalmodelswithmultiplelevelsofhiddenvariables.NMFdoesnotlearnanythingaboutthe“syntacticrelationshipsbetweenparts:NMFassumesthatthehiddenvariablesarenonnegative,butmakesnoassumptionabouttheirstatisticaldependency.特征降维：独立成分分析方法特征降维：独立成分分析方法区别A.Hyvarinen,Surveyonindependentcomponentanalysis.NeuralComputingSurveys,2:94-128,1999相同之处：独立成分分析IndependentComponentAnalysis,ICAandPCAprojectdatamatricesintocomponentsindifferentspaces.独立成分分析起源于盲源分割blindsourceseparation特征降维：独立成分分析方法特征降维：独立成分分析方法区别不同之处：PCAfindstheuncorrelatedcomponentsofmaximumvariance.Itisidealforcompressingdataintoalower-dimensionalspacebyremovingtheleastsignificantcomponents.ICAfindsthestatisticallyindependentcomponents.ICAistheidealchoiceforseparatingmixedsignalsandfindingthemostrepresentativecomponents.特征降维：独立成分分析方法特征降维：独立成分分析方法原理根底s1s2s3s4x1x2x3x4a11a12a13a14xi(t)=ai1*s1(t)+ai2*s2(t)+ai3*s3(t)+ai4*s4(t)Here,i=1:4.In vector-matrix notation,and dropping index t,this is x=A*sICA模型A:分解矩阵s：观测向量x:信号源特征降维：独立成分分析方法特征降维：独立成分分析方法原理根底特征降维：独立成分分析方法特征降维：独立成分分析方法算法概述特征降维：独立成分分析方法特征降维：独立成分分析方法人脸基降维方法其中y的每一行代表一个独立人脸基，m*m矩阵W在训练中得到特征降维：独立成分分析方法特征降维：独立成分分析方法人脸基降维方法特征降维：独立成分分析方法特征降维：独立成分分析方法人脸基降维方法示意特征降维：独立成分分析方法特征降维：独立成分分析方法降维后特征表达方法特征降维：独立成分分析方法特征降维：独立成分分析方法独立系数降维方法特征降维：独立成分分析方法特征降维：独立成分分析方法独立系数降维方法那么U中的每一列表示训练库所对应每个人脸图像的独立系数人脸基特征降维：独立成分分析方法特征降维：独立成分分析方法人脸基降维方法示意特征降维：独立成分分析方法特征降维：独立成分分析方法降维后特征表达方法特征降维：独立成分分析方法特征降维：独立成分分析方法人脸基独立图像基独立图像基独立系数基独立系数基特征降维方法：独立成分分析方法特征降维方法：独立成分分析方法PCA与ICA对数据的别离效果比照Showthescatterplotsofthe14imagedataset,projectedtoatwo-dimensionalsubspaceidentifiedbythefirsttwoprincipalcomponentsandthefirsttwoindependentcomponents.Darkpointscorrespondtotheclassoftools(oneofthe14classes),andgreen(light)pointscorrespondtotheother13classes.特征降维：非线性降维特征降维：非线性降维AGlobalGeometricFrameworkforNonlinearDimensionalityReduction(Isomap)Joshua B.Tenenbaum,Vin de Silva,John C.LangfordLocallyLinearEmbedding(LLE)Sam T.Roweis and Lawrence K.Saul非线性降维：流形学习非线性降维：流形学习特征降维方法：特征降维方法：Overview特征降维方法：特征降维方法：MDSMDS例子特征降维方法：特征降维方法：MDS特征降维方法：线性降维局限性特征降维方法：线性降维局限性特征降维方法：特征降维方法：ISOMAP降维降维目的人脸的三维：两个方向Pose+Lighting特征降维方法：特征降维方法：ISOMAP降维降维ISOMAP中的术语特征降维方法：特征降维方法：ISOMAP降维降维ISOMAP的性质特征降维方法：特征降维方法：ISOMAP降维降维ISOMAP的本征距离求取特征降维方法：特征降维方法：ISOMAP降维降维ISOMAP的本征距离示列特征降维方法：特征降维方法：ISOMAP降维降维ISOMAP的算法流程特征降维方法：特征降维方法：ISOMAP降维降维特征降维方法：特征降维方法：ISOMAP降维降维特征降维方法：特征降维方法：LLE降维降维LLE的算法流程特征降维方法：特征降维方法：LLE降维降维LLE的算法数学解释特征降维方法：特征降维方法：LLE降维降维LLE的算法示意LLE的例子特征降维方法：特征降维方法：LLE降维降维LLE的例子特征降维方法：特征降维方法：LLE降维降维结论结论流形学习的可行性许多高维采样数据都是由少数几个隐含变量所决定的,如人脸采样由光线亮度,人离相机的距离,人的头部姿势,人的脸部肌肉等因素决定.从认知心理学的角度,心理学家认为人的认知过程是基于认知流形和拓扑连续性的。