張軍平復旦計算與智能學院DimensionReduction

----理解數據幾何結構OutlineMotivationSurveyOurWorksDiscussion/ConclusionMotivationBigData

BiometricAuthenticationInternet/MobileVisualSearchMultimediaBioinformaticsPrecisionMedicineCurseofDimensionalityUnderlyingDimensionVisualizationComputationalEfficiency三維空間超球的體積計算：立方體體積計算：隨著維度d的增加，有：幾乎所有的高維空間都會遠離其中心，最小值和最大值的距離會不可辨別(CopiedfromMarioKoppen)對高斯分布的影響(CopiedfromWiki)Survey可視化技術

StatisticalProperty(統計特性)---PCA/ICADiscriminability（判別特性）---LDAUnderlyingDimension（內在維度）----

Manifold

Learning

ConditionalIndependent（條件獨立）---SDRandKDR

Correlation（相關性）---CCA

Sparsity（稀疏性）---NMF,Lasso………高維數據可視化的策略主成分分析--數據的統計特性MaximizeVariance（最大化方差）

X矩陣N*d;d維度；N樣本數MinimizeResidualErrors（最小化殘差）SingleValueDecomposition(奇異值分解，SVD)

(CopiedfromMarkusRingnér)Discriminability（判別性）LinearDiscriminantAnalysis(LDA)Within-varianceBetween-varianceObjective:Dimensionreduction:ManifoldLearning[H.S.Seung&D.D.Lee.2000][Tenenbaumetal,2000][RoweisandSaul,2000]UnderlyingDimensionGeneratedfromLow-dimensionalvariables.InterpretabilityExample:PCASubspaceofTranslatedFacesDefinitionAmanifoldisatopologicalspacethatislocallyEuclidean(i.e.,aroundeverypoint,thereisaneighborhoodthatistopologicallythesameastheopenunitballin).IsometricMapping[Tenenbaumetal.,2000]Step1:

Givenaneighborhoodsize$k$,computepairwisedistanceofeachpointanditsneighboringpoints.Step2:ComputeGeodesicdistancebetweenfar-awaypointsbyutilizinggraphdistanceStep3:EmployMultidimensionalscalingtocalculateitslow-dimensionalsubspace.LocallyLinearEmbedding[RoweisandSaul,2000]LLEStep1:Computetheneighborsofeachdatapoint,XiStep2:ComputetheweightsWijthatbestreconstructeachdatapointXifromitsneighbors,minimizethecostinEq.(1)Step3:ComputethevectorYibestreconstructedbytheweightWij,minimizingthequadraticforminEq.(2)byitsbottomnonzeroeigenvectors.

推導拉格朗日-->求導--->歸一化StochasticNeighborEmbeddingConvertingthehigh-dimensionalEuclideandistancesbetweendata

pointsintoconditionalprobabilitiesthatrepresentsimilaritiest-SNEDespitethestrongperformanceofthesetechniquesonartificialdatasets,theyareoftennotverysuccessfulatvisualizingreal,high-dimensionaldataSammonmapping,CCA,MVU,LLE,LE,Isomap,SNE

areincapableofretainingboththelocalandtheglobalstructureofthedatainasinglemap.Avariationofstochasticneighborembedding

SignificantlybettervisualizationbyReducingthetendencyofcrowdpointstogetherinthecenterofthemap.Crowdproblem—t-SNE

SymmetrizedversionoftheSNEcostfunctionwithsimplergradients

UsesaStudent-tdistributionratherthanaGaussiantocomputethesimilaritybetweentwopointsinthelow-dimensionalspace.

Heavy-taileddistributioninthelow-dimensionalspacetoalleviateboththecrowdingproblemandtheoptimizationproblemsofSNE.Studentt-distributionStudentt-distributionwithonedegreeoffreedomHeavy-taileddistributioninthelow-dimensionalmap.實際效果MNISTSparsity---InterpretabilityFeaturerepresentation(Parts):Non-negativeMatrixFactorization

[SeungandLee,1999]數據的拓撲結構--克萊因瓶GunnarCarlss