高维特征降维技术.ppt

1,高维降维理论与技术,吴飞 浙江大学计算机学院 2009年3月,Email: wufeics.zju.edu.cn,Reference,Turk, Matthew A.; Pentland, Alex P. Face Recognition using Eigenface，Proc IEEE CVPR 1991, p 586-591 M. S. Bartlett, H. M. Lades, and T. J. Sejnowski. Independent Component Representations for Face Recognition,In Proc. SPIE Conf. on Human Vision and Electronic Imaging III, volume 3299, pages 528-539, 1998. JB Tenenbaum etc. A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290 (5500): 2319-2323, 22 December 2000 Sam T. Roweis, Lawrence K. Saul ,Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science 290 (5500): 2323-2326, 22 December 2000,特征降维的意义,Complex stimuli can be represented by points in a high-dimensional vector space They typically have a much more compact description Dimensionality reduction: finding meaningful hidden low-dimensional structures 中心极限定律与维数灾难,特征降维的意义,Curse of Dimensionality：维数灾难,The term dimensionality curse is often used as a vague indication that high dimensionality causes problems in some situations The term was first used by Bellman in 1967 for combinatorial estimation of multivariate functions. 维数如果超过15维，则Query Point距离与最远邻居最近，使得欧拉距离失去意义,人脑生理特性对特征约减研究的启发,由于人脑对外界认知的手段多样而导致获取的信息维数过高，如人脑有三千个听觉神经纤维和一百万个视觉神经纤维（人脑总共大概有100亿左右的神经纤维） 如果不进行降维处理将导致人脑对信息处理的效率和精确度下降，因此人脑在对这些感知神经纤维处理时，均通过了复杂的降维处理Tenenbaum 2000。 B. Tenenbaum, V. De Silva, J. C. Langford, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290 (5500): 22, December 2000,特征约减的必要性：以人脸为例,太阳系（宇宙）所有电子总量10的79次方,大脑对外界信息感知：只会处理“有意义”部分,什么是特征？,特征降维方法：特征人脸方法,子空间（Subspace）方法 也就是平常说的奇异值分解方法（Singular Value Decomposition）或者主成分分析方法（Principle Component Analysis） EigenX方法，如EigenEye,EigenFinger、Eigen-edge等等方法,Turk, Matthew A.; Pentland, Alex P. Face Recognition using Eigenface，Proc IEEE CVPR 1991, p 586-591,特征人脸方法已成为经典的算法,2009年3月23日Google Scholar查询得到的引用率,特征降维方法,奇异值分解理论,特征降维方法,奇异值分解示列,P值越大，丢失信息越少。特征维数很高时，一些特征根很微小，甚至为零，则可以忽略。,如果将矩阵A看成由（0.96，1.72）和（2.28，0.96）两个2维的对象组成，为了将这两个对象由2维降维成1维，我们可以如下处理： （0.96，1.72）*（0.6，0.8）=1.952 （2.28，0.96）*（0.6，0.8）=2.136 形式上而言，2维对象由2维空间被映射到了1维空间，从而被降维,特征降维方法,隐性语义索引,奇异值分解方法在文本分析中也叫做隐藏语义索引（Latent Semantic Indexing）,特征降维方法,隐性语义索引：建立文档词汇矩阵,Query: Computer-based information look-up,An “R“ in the column labeled REL (relevant) indicates that the user would have judged the document relevant to the query (here documents 1 and 3 are relevant). Terms occurring in both the query and a document (computer and information) are indicated by an asterisk in the appropriate cell; an “M“ in the MATCH column indicates that the document matches the query and would have been returned to the user. Documents 1 and 2 illustrate common classes of problems with which the proposed method deals. Document 1 is a relevant document, which, however, contains none of the words in the query. It would, therefore, not be returned by a straightforward term overlap retrieval scheme. Document 2 is a non-relevant document which does contain terms in the query, and therefore would be returned, despite the fact that the query context makes it clear enough to a human observer that a different sense of at least one of the words is intended.,特征降维方法,隐性语义索引：文档词汇隐藏关系的索引,下面的处理方式与SVD处理基本雷同,特征降维方法,隐性语义索引：文档词汇隐藏关系的索引,特征降维方法,隐性语义索引：文档词汇隐藏关系的索引,There are two classes of documents: five about human-computer interaction (c1-c5) and four about graphs (m1-m4).,If we set ourselves is to find documents relevant to the query: “human computer interaction“. Simple term matching techniques would return documents c1, c2 and c4 since they share one or more terms with the query. However, two other documents which are also relevant (c3 and c5) are missed by this method since they have no terms in common with the query.,SVD Decomposition,对得到的Term-Document矩阵进行SVD分解,SVD for Technical Memo Example,SVD for Technical Memo Example,SVD for Technical Memo Example 选取最大的2个特征根及其对应的特征向量,Computing fundamental comparison quantities from the SVD model,Three basically sorts of comparisons of interest: Comparing two terms (“How similar are terms i and j ?“) Comparing two documents (“How similar are documents i and j ?“), Comparing a term and a document (“How associated are term i and document j ?“). In standard information retrieval approaches, these amount respectively, to comparing two rows, comparing two columns, or examining individual cells of the original matrix of term by document data, X Here we make similar comparisons, but use the matrix Xhihat , since it is presumed to represent the important and reliable patterns underlying the data in X,Computing two terms,Computing two documents,Computing a term and a document,SVD for Technical Memo Example,Before SVD and After SVD for Technical Memo Example,Before,After,百度输入“杨卫”后的隐性文法分析结果,谷歌输入“杨卫”后的隐性文法分析结果,特征降维：特征人脸方法,人脸图像表示,Principal Component Analysis,A N x N pixel image of a face, represented as a vector occupies a single point in N2-dimensional image space. Images of faces being similar in overall configuration, will not be randomly distributed in this huge image space. Therefore, they can be described by a low dimensional subspace. Main idea of PCA : To find vectors that best account for variation of face images in entire image space. These vectors are called eigen vectors. Construct a face space and project the images into this face space (eigenfaces).,特征降维：特征人脸方法,Image Representation,Training set of images of size N*N are represented by vectors of size N2 1,2,3,M Example,Average Image and Difference Images,The average training set is defined by = (1/M) Mi=1 i Each face differs from the average by vector i = i ,Covariance Matrix,A covariance matrix is constructed as: C = AAT, where A=1,M of size N2 x N2 Finding eigenvectors of N2 x N2 matrix is intractable. Hence, use the matrix ATA of size M x M and find eigenvectors of this small matrix.,Size of this matrix is M*M,Size of this matrix is N2 x N2,Eigenvalues and Eigenvectors - Definition,If v is a nonzero vector and is a number such that Av = v, then v is said to be an eigenvector of A with eigenvalue . Example,A,l,v,(eigenvectors),(eigenvalues),How to Calculate Eigenvectors?,Eigenvectors of Covariance Matrix,The eigenvectors vi of ATA are:,Consider the eigenvectors vi of ATA such that ATAvi = ivi Premultiplying both sides by A, we have AAT(Avi) = i(Avi),Face Space,The eigenvectors of covariance matrix are ui = Avi,ui resemble facial images which look ghostly, hence called eigenfaces,Face Space,Projection into Face Space,A face image can be projected into this face space by k = UT(k ); k=1,M,Projection of Image1,Recognition,The test image, , is projected into the face space to obtain a vector, : = UT( ) The distance of to each face class is defined by k2 = |-k|2; k = 1,M A distance threshold,c, is half the largest distance between any two face images: c = ½ maxj,k |j-k|; j,k = 1,M,Recognition,Find the distance, , between the original image, , and its reconstructed image from the eigenface space, f, 2 = | f |2 , where f = U * + Recognition process: IF c then input image is not a face image; IF c AND kc for all k then input image contains an unknown face; IF c AND k*=mink k c then input image contains the face of individual k*,Limitations of Eigenfaces Approach,Variations in lighting conditions Different lighting conditions for enrolment and query. Bright light causing image saturation.,Differences in pose Head orientation - 2D feature distances appear to distort. Expression - Change in feature location and shape.,Linear Discriminant Analysis,PCA does not use class information PCA projections are optimal for reconstruction from a low dimensional basis, they may not be optimal from a discrimination standpoint. LDA is an enhancement to PCA Constructs a discriminant subspace that minimizes the scatter between images of same class and maximizes the scatter between different class images,Mean Images,Let X1, X2, Xc be the face classes in the database and let each face class Xi, i = 1,2,c has k facial images xj, j=1,2,k. We compute the mean image i of each class Xi as: Now, the mean image of all the classes in the database can be calculated as:,Scatter Matrices,We calculate within-class scatter matrix as: We calculate the between-class scatter matrix as:,Projection,We find the product of SW-1 and SB and then compute the Eigen vectors of this product (SW-1. SB). Use same technique as eigenfaces approach to reduce the dimensionality of scatter matrix to compute eigenvectors. Form a matrix U that represents all eigenvectors of SW-1. SB by placing each eigenvector ui as each column in that matrix. Each face image xj Xi can be projected into this face space by the operation i = UT(xj ),特征降维：特征人脸方法,特征人脸,根据人脸协方差矩阵求取特征根和特征向量； 每个特征向量是一个特征人脸； 将特征根进行排序，选取前若干个最大的特征根所对应的特征向量组成了“人脸空间”； 完成了从“像素点空间”到“人脸空间”的转换,特征降维 ：特征人脸方法,特征人脸：示例,400个人脸与对应的36个特征人脸,非负矩阵分解（ non-negative matrix factorization ）,针对先前矩阵分解过程中可能出现负数，而使得分解结果失去意义的局限性，非负矩阵分解被提出，其意义在于 以非线性的方式实现对非负多元数据的局部化、线性和低维描述，它为分析局部特征和整体特征之间的关系提供了一种思路，即整体特征是局部特征的非负线性组合，局部特征在构成整体特征时不会产生正负抵消的情况,D. D. Lee, H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature 401, 788-791 (1999) H. S. Seung and D.D. Lee. The Manifold ways of perception,Science 290, 2268-69 (2000),Introduction,NMF (Nonnegative Matrix Factorization): Theory: Perception of the whole is based on perception of its parts. Comparison with another two matrix factorization methods: PCA (Principle Components Analysis) VA (Vector quantization ),Comparison:,Common features: Represent a face as a linear combination of basis images. Matrix factorization: VWH V: nm matrix. Each column of which contains n nonnegative pixel values of one of the m facial images. W: (n r): r columns of W are called basis images. H: (r m): each column of H is called encoding.,Comparison (contd),NMF PCA VQ Representation: parts- Based holistic holistic Basis Image: localized features eigenfaces whole face Constrains on allow multiple each face is each column of H is W and H: basis images to approximated by constrained to be a represent a face, a linear combi- unary vector, every but only additive nation of all face is approximat- combinations the eigenfaces ed by a single basis image.,Data representation,Non-negative Constraints,Constraints 矩阵W和H的元素只能为非负值 W：Base image H：Encoding,Example PCA,Example NMF,Is perception of the Whole based on perception of its Parts?,There is psychological and physiological evidence for part-based representation in the brain NMF: to learn parts PCA: to learn holistic, not parts-based Not have obvious visual interpretation,Implementation of NMF,Limitation of NMF,Not suitable for learning parts for complex cases:require fully hierarchical models with multiple levels of hidden variables. NMF does not learn anything about the “syntactic” relationships between parts: NMF assumes that the hidden variables are nonnegative, but makes no assumption about their statistical dependency.,特征降维：独立成分分析方法,区别,A. Hyvarinen, Survey on independent component analysis. Neural Computing Surveys, 2:94-128, 1999,相同之处：独立成分分析（Independent Component Analysis, ICA）and PCA project data matrices into components in different spaces. 独立成分分析起源于盲源分割（blind source separation）,特征降维：独立成分分析方法,区别,不同之处：PCA finds the uncorrelated components of maximum variance. It is ideal for compressing data into a lower-dimensional space by removing the least significant components. ICA finds the statistically independent components. ICA is the ideal choice for separating mixed signals and finding the most representative components.,特征降维：独立成分分析方法,原理基础,s1,s2,s3,s4,x1,x2,x3,x4,a11,a12,a13,a14,xi(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 * s,ICA模型,A: 分解矩阵 s：观测向量 x: 信号源,特征降维：独立成分分析方法,原理基础,特征降维：独立成分分析方法,算法概述,特征降维：独立成分分析方法,人脸基降维方法,其中y的每一行代表一个独立人脸基，m*m矩阵W在训练中得到,特征降维：独立成分分析方法,人脸基降维方法,特征降维：独立成分分析方法,人脸基降维方法示意,特征降维：独立成分分析方法,降维后特征表达方法,特征降维：独立成分分析方法,独立系数降维方法,特征降维：独立成分分析方法,独立系数降维方法,则U中的每一列表示训练库所对应每个人脸图像的独立系数人脸基,特征降维：独立成分分析方法,人脸基降维方法示意,特征降维：独立成分分析方法,降维后特征表达方法,特征降维：独立成分分析方法,人脸基,独立图像基,独立系数基,特征降维方法：独立成分分析方法,PCA与ICA对数据的分离效果对比,Show the scatter plots of the 14 image dataset, projected to a two-dimensional subspace identified by the first two principal components and the first two independent components. Dark points correspond to the class of tools (one of the 14 classes), and green (light) points correspond to the other 13 classes.,特征降维：非线性降维,A Global Geometric Framework for Nonlinear Dimensionality Reduction (Isomap) Joshua B. Tenenbaum, Vin de Silva, John C. Langford Locally Linear Embedding (LLE) Sam T. Roweis and Lawrence K. Saul,非线性降维：流形学习,特征降维方法：Overview,特征降维方法：MDS,MDS例子,特征降维方法：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降维,结论,流形学习的可行性 许多高维采样数据都是由少数几个隐含变量所决定的, 如人脸采样由光线亮度, 人离相机的距离, 人的头部姿势, 人的脸部肌肉等因素决定. 从认知心理学的角度, 心理学家认为人的认知过程是基于认知流形和拓扑连续性的。,