Pattern Recognition and Machine Learning

588 12.CONTINUOUSLATENTVARIABLES

Substitutingthisexpansionbackintotheeigenvectorequation,weobtain

1 N N N

N L ¢(xn)¢(xn)TL aim¢(Xm)= AiL ain¢(Xn),

n=l m=l n=l

(12.77)

Thekeystepis nowtoexpressthisintermsofthekernelfunctionk(xn,xm)=

¢(Xn)T¢(xm),whichwedobymultiplyingbothsidesby¢(xZ)Ttogive

1 N m N

N Lk(XI'Xn) L aimk(Xn,xm)= AiLaink(XI'Xn),

n=l m=l n=l

Thiscanbewritteninmatrixnotationas

(12.78)

(12.79)

whereaiisanN-dimensionalcolumnvectorwithelementsaniforn= 1,...,N.

Wecanfindsolutionsforaibysolvingthefollowingeigenvalueproblem

(12.80)

Exercise 12.26

inwhichwehaveremoveda factorofK frombothsidesof(12.79). Notethat

thesolutionsof(12.79)and(12.80)differonlybyeigenvectorsofK havingzero

eigenvaluesthatdonotaffecttheprincipalcomponentsprojection.

Thenormalizationconditionforthecoefficientsaiisobtainedbyrequiringthat

theeigenvectorsinfeaturespacebenormalized.Using(12.76)and(12.80),wehave

N N

1 =V;Vi=L L ainaim¢(xn)T¢(xm)=a;K~=AiNa;ai' (12.81)

n=lm=l

Havingsolvedtheeigenvectorproblem,theresultingprincipalcomponentpro-

jectionscanthenalsobecastintermsofthekernelfunctionsothat,using(12.76),

theprojectionofa pointxontoeigenvectoriisgivenby

N N

Yi(X)=¢(x)TVi=L ain¢(x)T¢(xn)=L aink(X,xn) (12.82)

n=l n=l

andsoagainis expressedintermsofthekernelfunction.

IntheoriginalD-dimensionalxspacethereareDorthogonaleigenvectorsand

hencewecanfindatmostDlinearprincipalcomponents. ThedimensionalityM

ofthefeaturespace,however,canbemuchlargerthanD(eveninfinite),andthus

wecanfinda numberofnonlinearprincipalcomponentsthatcanexceedD. Note,

however,thatthenumberofnonzeroeigenvaluescannotexceedthenumberNof

datapoints,because(evenifM > N)thecovariancematrixinfeaturespacehas

rankatmostequaltoN.ThisisreflectedinthefactthatkernelPCAinvolvesthe

eigenvectorexpansionoftheN xNmatrixK.