Arbeitsgruppe Bülthoff - Face Rec

1 Max-Planck-Institutf r biologische KybernetikSpemannstra e 38 72076 T bingen GermanyArbeitsgruppe B lthoffTechnicalReportNo December NonlinearComponentAnalysisasaKernelEigen valueProblemBernhardSch olkopf AlexanderSmola andKlaus RobertM ullerAbstractWedescribeanewmethodforperf orminganonlinearformofPrincipalComponent Anal ysis Bytheuseofintegraloperatorkernelfunction s wecane cientlycomputeprincipalcomponentsinhigh dimensionalfeaturespaces relatedtoinputspacebysomenonlinearmap forinstancethespaceofallpossible pixelproductsin images Wegivethederivationofthemethod alongwithadiscussionofothertechniqueswhi chcanbemadenonlinearwiththekernelapproac h andpresent rstexperimentalresultsonnonlinearfea tureextractionforpatternrecognition ASandKRMarewithGMDF irst ForschungszentrumInformationstechnik RudowerChaussee Berlin ASandBSweresupportedbygrantsfromtheStudi enstiftungdesdeutschenVolkes BSthankstheGMDF irstforhospitalityduringtwovisits ASandBSthankV Vapnikforintroducingthemtokernelrepresen tationsofdotproductsduringjointworkonSup portVectormachines Thisworkpro tedfromdiscussionswithV Blanz L Bottou C Burges H B ultho K Gegenfurtner P Ha ner N Murata P Simard S Solla V Vapnik andT Vetter WearegratefultoV Blanz C Burges andS Sollaforreadingapreliminaryversionofthem anuscript Thisdocumentisavailableas pub mpi memos TR psviaanonymousftpfromftp mpik tueb mpg deorfromtheWorldWideWeb http www mpik

2 Tueb mpg de bu html IntroductionPrincipalComponentAnalysis PCA isapower fultechniqueforextractingstructurefrompo ssi blyhigh dimensionaldatasets Itisreadilyper formedbysolvinganEigenvalueproblem orbyusingiterativealgorithmswhichestimat eprinci palcomponents forreviewsoftheexistingliter ature seeJolli e andDiamataras Kung PCAisanorthogonaltransformationofthecoor dinatesysteminwhichwedescribeourdata Thenewcoordinatevaluesbywhichwerep resentoutdataarecalledprincipalcomponent s Itisoftenthecasethatasmallnumberofprinci palcomponentsissu cienttoaccountformostofthestructureinthe data Thesearesometimescalledthefactorsorlaten tvariablesofthedata ThepresentworkgeneralizesPCAtothecasewhe rewearenotinterestedinprincipalcompo nentsininputspace butratherinprincipalcom ponentsofvariables orfeatures whicharenon linearlyrelatedtotheinputvariables Amongtheseareforinstancevariablesobtaine dbytakinghigher ordercorrelationsbetweeninputvariables Inthecaseofimageanalysis thiswouldamountto ndingprincipalcomponentsinthespaceofprod uctsofinputpixels Tothisend weareusingthemethodofex pressingdotproductsinfeaturespaceinterms ofkernelfunctionsininputspace Givenanyal gorithmwhichcanbeexpressedsolelyintermso fdotproducts i e withoutexplicitusageofthevariablesthemse lves thiskernelmethodenablesustoconstructdi erentnonlinearversionsofit Aizerman Braverman

3 Rozonoer Boser Guyon Vapnik Eventhoughthisgen eralfactwasknown Burges themachinelearningcommunityhasmadelittle useofit theexceptionbeingSupportVectormachines Vap nik Inthispaper wegivesomeexamplesofnon linearmethodsconstructedbythisapproach Foroneexample thecaseofanonlinearformofprin cipalcomponentanalysis weshallgivedetailsandexperimentalresults Sections forsomeothercases weshallbrie ysketchthealgorithms Sec Inthenextsection wewill rstreviewthestan dardPCAalgorithm Inordertobeabletogener alizeittothenonlinearcase weshallthenformu lateitinawaywhichusesexclusivelydotprod ucts InSec weshalldiscussthekernelmethodforcomputin gdotproductsinfeaturespaces To gether thesetwosectionsformthebasisforSec whichpresentstheproposedkernel basedalgo rithmfornonlinearPCA Followingthat Sec willdiscusssomedi erencesbetweenkernel basedPCAandothergeneralizationsofPCA InSec weshallgivesome rstexperimentalresultsonkernel basedfeatureextractionforpatternrecog nition Afteradiscussionofotherapplicationsofthe kernelmethod Sec weconcludewithadis cussion Sec Finally sometechnicalmaterialwhichisnotessential forthemainthreadoftheargumenthasbeenrele gatedintotheappendix PCAinFeatureSpacesGivenasetofMcenteredob servationsxk k M xk RN PMk xk PCAdiagonal izesthecovariancematrix C MMXj xjx j Todothis onehastosolvetheEigenvalueequa tion v Cv forEigenvalues andv RNnf g AsCv MPMj xj v xj allsolutionsvmustlieinthespanofx xM

4 Hence isequivalentto xk v xk Cv forallk M Theremainderofthissectionisdevotedtoastr aightforwardtranslationtoanonlinearsce nario inordertopreparethegroundforthemethodpro posedinthepresentpaper Weshallnowdescribethiscomputationinanoth erdotproductspaceF whichisrelatedtotheinputspacebyapossibly nonlinearmap RN F x X NotethatF whichwewillrefertoasthefeaturespace couldhaveanarbitrarilylarge possiblyin nite dimensionality Hereandinthefollowing uppercasecharactersareusedforelementsofF whilelowercasecharactersdenoteelementsof RN Again wemaketheassumptionthatwearedealingwithc entereddata i e PMk xk weshallreturntothispointlater UsingthecovariancematrixinF C MMXj xj xj Moreprecisely thecovariancematrixisde nedastheexpectationofxx forconvenience weshallusethesametermtorefertothemaximum likelihoodesti mate ofthecovariancematrixfroma nitesample ifFisin nite dimensional wethinkof xj xj asthelinearoperatorwhichmapsX Fto xj xj X wenowhaveto ndEigenvalues andEigenvectorsV Fnf gsatisfying V CV Bythesameargumentasabove thesolutionsVlieinthespanof x xM Forus thishastwousefulconsequences rst wecanconsidertheequivalentequation xk V xk CV forallk M andsecond thereexistcoe cients i i M suchthatV MXi i xi Combining and weget MXi i xk xi MMXi i xk MXj xj xj xi forallk M De ninganM MmatrixKbyKij xi xj thisreadsM K K where denotesthecolumnvectorwithentries M AsKissymmetric

5 IthasasetofEigenvectorswhichspansthewhol espace thusM K givesusallsolutions ofEq NotethatKispositivesemide nite whichcanbeseenbynoticingthatitequals x xM x xM whichimpliesthatforallX F X KX k x xM Xk Consequently K sEigenvalueswillbenonnega tive andwillexactlygivethesolutionsM ofEq WethereforeonlyneedtodiagonalizeK Let MdenotetheEigenval ues and MthecorrespondingcompletesetofEigenvecto rs with pbeingthe rstnonzeroEigenvalue Wenormalize p Mbyrequir ingthatthecorrespondingvectorsinFbenor malized i e Vk Vk forallk p M Byvirtueof and thistranslatesintoanormalizationconditio nfor p M MXi j ki kj xi xj MXi j ki kjKij k K k k k k Forthepurposeofprincipalcomponentextrac tion weneedtocomputeprojectionsontheEigen vectorsVkinF k p M Letxbeatestpoint withanimage x inF then Vk x MXi ki xi x maybecalleditsnonlinearprincipalcomponen tscorrespondingto Insummary thefollowingstepswerenecessarytocomputet heprincipalcomponents rst com putethedotproductmatrixKde nedby second computeitsEigenvectorsandnormalizethemin F third computeprojectionsofatestpointontotheEig envectorsby Forthesakeofsimplicity wehaveabovemadetheassumptionthattheobser vationsarecentered Thisiseasytoachieveininputspace butmoredi cultinF aswecannotexplicitlycomputethemeanofthem appedobservationsinF Thereis however awaytodoit andthisleadstoslightlymodi edequationsforkernel basedPCA seeAp pendixA

6 Beforeweproceedtothenextsection whichmorecloselyinvestigatestheroleofthe map thefollowingobservationisessential Themap ping usedinthematrixcomputationcanbeanarbitra rynonlinearmapintothepossiblyhigh dimensionalspaceF e g thespaceofallnthor dermonomialsintheentriesofaninputvector Ifwerequirethat shouldnotmapallobserva tionstozero thensuchapwillalwaysexist Notethatinourderivationwecouldhaveusedth eknownresult e g Kirby Sirovich thatPCAcanbecarriedoutonthedotproductmat rix xi xj ijinsteadof however forthesakeofclarityandextendability inAppendixA weshallconsiderthecasewherethedatamustbe centeredinF wegaveadetailedderivation Inthatcase weneedtocomputedotproductsofinputvectors mappedby withapossiblypro hibitivecomputationalcost Thesolutiontothisproblem whichwillbedescribedinthefollowingsectio n buildsonthefactthatweexclusivelyneedtoco mputedotproductsbetweenmappedpat terns in and weneverneedthemappedpatternsexplicitly ComputingDotProductsinFeatureSpaceInorde rtocomputedotproductsoftheform x y weusekernelrepresentationsoftheformk x y x y whichallowustocomputethevalueofthedotpro ductinFwithouthavingtocarryoutthemap ThismethodwasusedbyBoser Guyon Vapnik toextendthe GeneralizedPor trait hyperplaneclassi erofVapnik Chervo nenkis tononlinearSupportVectorma chines Tothisend theysubstituteapriorichosenkernelfunctio nsforalloccurancesofdotproducts Thisway thepowerfulresultsofVapnik Cher vonenkis

7 FortheGeneralizedPortraitcarryovertothen onlinearcase Aizerman Braver man Rozonoer callFthe linearizationspace anduseitinthecontextofthepoten tialfunctionclassi cationmethodtoexpressthedotproductbetwee nelementsofFintermsofele mentsoftheinputspace IfFishigh dimensional wewouldliketobeableto ndaclosedformex pressionforkwhichcanbee cientlycomputed Aizermanetal considerthepossibilityofchoosingkapriori withoutbeingdirectlycon cernedwiththecorrespondingmapping intoF Aspeci cchoiceofkmightthencorrespondtoadotprodu ctbetweenpatternsmappedwithasuit able Aparticularlyusefulexample whichisadirectgeneralizationofaresultpro vedbyPoggio Lemma inthecontextofpolynomialapproximation is x y d Cd x Cd y whereCdmapsxtothevectorCd x whoseentriesareallpossiblen thdegreeorderedproductsoftheentriesofx Forinstance Vapnik ifx x x thenC x x x x x x x or yieldingthesamevalueofthedotproduct c x x x p x x Forthisexample itiseasytoverifythat x x y y x x p x x y y p y y c x c y Ingeneral thefunctionk x y x y d correspondstoadotproductinthespaceofd thordermonomialsoftheinputcoordinates Ifxrepresentsanimagewiththeentriesbeingp ixelvalues wecanthuseasilyworkinthespacespannedbypr oductsofanydpixels providedthatweareabletodoourworksolelyin termsofdotproducts withoutanyexplicitusageofamappedpatternc d x Thelatterlivesinapos siblyveryhigh dimensionalspace eventhoughwewillidentifytermslikex x andx x

8 IntoonecoordinateofFasin thedimensionalityofF theimageofRNundercd stillis N p p N andthusgrowslikeNp Forinstance inputim agesandapolynomialdegreed yieldadimen sionalityof Thus usingkernelsoftheform isouronlywaytotakeintoaccounthigher orderstatisticswithoutacombinatorialexpl osionoftimecomplexity Thegeneralquestionwhichfunctionkcorre spondstoadotproductinsomespaceFhasbeendi scussedbyBoser Guyon Vapnik andVapnik Mercer stheoremoffunctionalanalysisstatesthatif kisacontinuouskernelofapositiveintegralo perator wecanconstructamappingintoaspacewherekac tsasadotprod uct fordetails seeAppendixB Theapplicationof toourproblemisstraightforward wesimplysubstituteanapriorichosenkernelf unctionk x y foralloccurancesof x y Thiswasthereasonwhywehadtoformulatethepr obleminSec inawaywhichonlymakesuseofthevaluesofdotp roductsinF Thechoiceofkthenimplicitlydeterminesthem apping andthefeaturespaceF InAppendixB wegivesomeexamplesofker