This document provides an overview of kernel principal component analysis (KPCA). KPCA extends regular PCA to handle nonlinear dimensionality reduction by mapping data points into a high-dimensional feature space using kernels. It works by first computing the normalized kernel matrix and then solving the eigenvalue problem to obtain the principal components in feature space. These principal components can then be used to represent new data points through the kernel trick, allowing nonlinear dimensionality reduction without explicitly computing the high-dimensional feature mappings. KPCA is useful when data lies on a nonlinear manifold but regular PCA cannot unfold it.
This document provides an overview of kernel principal component analysis (KPCA). KPCA extends regular PCA to handle nonlinear dimensionality reduction by mapping data points into a high-dimensional feature space using kernels. It works by first computing the normalized kernel matrix and then solving the eigenvalue problem to obtain the principal components in feature space. These principal components can then be used to represent new data points through the kernel trick, allowing nonlinear dimensionality reduction without explicitly computing the high-dimensional feature mappings. KPCA is useful when data lies on a nonlinear manifold but regular PCA cannot unfold it.
This document provides an overview of kernel principal component analysis (KPCA). KPCA extends regular PCA to handle nonlinear dimensionality reduction by mapping data points into a high-dimensional feature space using kernels. It works by first computing the normalized kernel matrix and then solving the eigenvalue problem to obtain the principal components in feature space. These principal components can then be used to represent new data points through the kernel trick, allowing nonlinear dimensionality reduction without explicitly computing the high-dimensional feature mappings. KPCA is useful when data lies on a nonlinear manifold but regular PCA cannot unfold it.
This document provides an overview of kernel principal component analysis (KPCA). KPCA extends regular PCA to handle nonlinear dimensionality reduction by mapping data points into a high-dimensional feature space using kernels. It works by first computing the normalized kernel matrix and then solving the eigenvalue problem to obtain the principal components in feature space. These principal components can then be used to represent new data points through the kernel trick, allowing nonlinear dimensionality reduction without explicitly computing the high-dimensional feature mappings. KPCA is useful when data lies on a nonlinear manifold but regular PCA cannot unfold it.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 26
LECTURE :KERNEL PCA
Rita Osadchy Some slides are due to Scholkopf, Smola, Muller, and Precup
Dimensionality Reduction Data representation Inputs are real-valued vectors in a high dimensional space.
Linear structure Does the data live in a low dimensional subspace?
Nonlinear structure Does the data live on a low dimensional submanifold?
Given some problem, how do we know what classes of functions are capable of solving that problem? VC (Vapnik-Chervonenkis) theory tells us that often mappings which take us into a higher dimensional space than the dimension of the input space provide us with greater classification power.
Example in
2 R
These classes are linearly inseparable in the input space.
Example: High-Dimensional Mapping
We can make the problem linearly separable by a simple mapping
: R2 R3 2 ( x1 , x2 ) a ( x1 , x2 , x12 + x2 )
Kernel Trick High-dimensional mapping can seriously increase computation time. Can we get around this problem and still get the benefit of high-D? Yes! Kernel Trick K (xi , x j ) = ( xi )T ( x j ) Given any algorithm that can be expressed solely in terms of dot products, this trick allows us to construct different nonlinear versions of it.
Popular Kernels
Kernel Principal Component Analysis (KPCA)
Extends conventional principal component analysis (PCA) to a high dimensional feature space using the kernel trick. Can extract up to n (number of samples) nonlinear principal components without expensive computations.
Making PCA Non-Linear
Suppose that instead of using the points xi we would first map them to some nonlinear feature space ( xi ) E.g. using polar coordinates instead of cartesian coordinates would help us deal with the circle.
Extract principal component in that space (PCA) The result will be non-linear in the original data space!
Derivation Suppose that the mean of the data in the feature space is n Covariance:
1 = ( xi ) = 0 n i =1
1 n C = ( xi ) ( xi )T n i =1 Eigenvectors
Cv = v
Derivation Cont. Eigenvectors can be expressed as linear combination of features:
v = i ( xi ) i =1
Proof:
1 n Cv = ( xi ) ( xi )T v = v n i =1 thus
1 n 1 n v= ( xi ) ( xi )T v = ( ( xi ) v) ( xi )T n i =1 n i =1
Showing that
xx v = ( x v) x T
Showing that
xx v = ( x v) x T
Derivation Cont. So, from before we had,
1 n 1 n v= ( xi ) ( xi )T v = ( ( xi ) v) ( xi )T n i =1 n i =1 just a scalar
this means that all solutions v with = 0 lie in the span of ( x1 ),.., ( xn ) , i.e.,
v = i ( xi ) i =1
Finding the eigenvectors is equivalent to finding the coefficients i
Derivation Cont. By substituting this back into the equation we get: n 1 n n ( xi ) ( xi )T jl ( xl ) = j jl ( xl ) n i =1 l =1 l =1
We can rewrite it as n 1 n n ( xi ) jl K ( xi , xl ) = j jl ( xl ) n i =1 l =1 l =1
Multiply this by ( xk ) from the left:
n 1 n n ( xk )T ( xi ) jl K ( xi , xl ) = j jl ( xk )T ( xl ) n i =1 l =1 l =1
Derivation Cont. By plugging in the kernel and rearranging we get:
K 2 j = n j K j We can remove a factor of K from both sides of the matrix (this will only affects the eigenvectors with zero eigenvalue, which will not be a principle component anyway):
K j = n j j We have a normalization condition for the j vectors:
v vj =1 T j
jl jk ( xl ) (xk ) = 1 jT K j = 1 T k =1 l =1
Derivation Cont. By multiplying K j = n j j by j and using the normalization condition we get:
j n T j = 1, j j For a new point x, its projection onto the principal components is:
( x) v j = ji ( x) ( xi ) = ji K ( x, xi ) T T i =1 i =1
Normalizing the feature space
In general, ( xi ) may not be zero mean. Centered features:
1 n ( xk ) = ( xi ) ( xk ) n k =1 ~ The corresponding kernel is:
~ ~ T ~ K ( xi , x j ) = ( xi ) ( x j ) 1 1 n = ( xi ) ( xk ) ( x j ) ( xk ) n k =1 n k =1 1 n 1 n 1 = K ( xi , x j ) K ( xi , xk ) K ( x j , xk ) + 2 n k =1 n k =1 n n T
l , k =1
K (x , x ) l k
Normalizing the feature space (cont)
1 n 1 n 1 ~ K ( xi , x j ) = K ( xi , x j ) K ( xi , xk ) K ( x j , xk ) + 2 n k =1 n k =1 n l , k =1
K (x , x l
In a matrix form ~ K = K - 211/n K + 11/n K11/n
where 11/n is a matrix with all elements 1/n.
Summary of kernel PCA
Pick a kernel Construct the normalized kernel matrix of the data (dimension m x m): ~ K = K - 211/n K + 11/n K11/n
Solve an eigenvalue problem:
~ K i = i i
For any data point (new or old), we can represent it as
y j = ji K ( x, xi ), j = 1,.., d i =1
Example: Input Points
Example: KPCA
Example: De-noising images
Properties of KPCA Kernel PCA can give a good reencoding of the data when it lies along a non-linear manifold. The kernel matrix is n x n, so kernel PCA will have difficulties if we have lots of data points.
