From Feature Space to Primal Space: KPCA and Its Mixture Model
Haixian Wang · InTech eBooks · 2010
New Advances in Machine Learning 106involved.However, the price one has to pay for this saving is that the time complexity is not under control.Motivated by the idea "divide and rule", Zheng et el.(2005) proposed another improved algorithm for KPCA as follows.First, the entire data set was divided into some smaller data sets, then the sample covariance matrix of each smaller data set was approximately computed, and finally kernel principal components were extracted by combining these approximate covariance matrices.With their method, the computational demand and memory requirement are effectively relieved.However, the advantages relate with many factors such as the required accuracy of extracted components, the number of the divided smaller data sets (which is usually empirically set), and the data to be processed.As a generic methodology, another thread of speeding up kernel machine learning is to seek a low-rank approximation to the kernel matrix.Since, as noted by several researchers, the spectrum of the kernel matrix tends to decay rapidly, the low-rank approximation often achieves sufficient precision of the requirement.Williams and Seeger (2001) used Nystr öm method to compute the approximate eigenvalue decomposition of the kernel matrix.Also, Smola and Sch ölkopf (2000) presented a sparse greedy approximation technique.These two methods yield similar forms and performances.Another limitation of KPCA is that it defines only a global projection of the samples.When the distribution of the data points is complex and non-convex, a global subspace based on KPCA may fail to deliver good performance in terms of feature extraction and recognition.In input space, Tipping and Bishop (1999) and Roweis and Ghahramani (1999) introduced mixture of PCA to remedy the same shortcoming of PCA.Kim et al. (2002b) used mixture-of-eigenfaces for face recognition.There are many other papers on face recognition using mixture method, but as they do not focus on KPCA, references are omitted.The contributions of this chaper are twofold: Firstly, viewing KPCA as a problem in primal space with the "samples" created by using the incomplete Cholesky decomposition, we show that KPCA is equivalent to performing linear PCA in the primal space using the created samples.So, the same kernel principal components as the standard KPCA are produced.Consequently, all the improved methods dealing with linear PCA (such as the constrained EM algorithm and the GHA method mentioned above), as well as directly diagonalizing the covariance matrix, could be applied to the created samples in the primal space to extract kernel principal components.Theoretical analysis and experimental results on both artificial and real data have shown the superiority of the proposed method for performing KPCA in terms of computational efficiency and storage space, especially when the number of the data points is large.Secondly, we extend KPCA to a mixture of local KPCA models by applying the mixture model of the probabilistic PCA in the primal space.While KPCA uses one set of features to model the data points, the mixture of KPCA uses more than one set of features.Therefore, the mixture of KPCA is expected to represent data more effectively and has better recognition performance than KPCA, which is also confirmed by the experiments.The remainder of this chaper is organized as follows.The standard KPCA is briefly reviewed in Section 2, and in Section 3, we formulate KPCA in the primal space using the incomplete Cholesky decomposition.Next, we extend KPCA to its mixture model in Section 4. Experimental results are presented in Section 5.In Section 6, we draw the conclusion. Kernel Principal Component AnalysisSuppose x i ∈ R l , i = 1, . . ., n, are n observations.The basic idea of KPCA is as follows.First, the samples are mapped into some potentially high-(and possibly infinite-) dimensional feature www.intechopen.com How to referenceIn order to correctly reference this scholarly work, feel free to copy and paste the following: Haixian Wang (2010).