A Convergent Solution to Tensor Subspace Learning

  • 格式:pdf
  • 大小:172.20 KB
  • 文档页数:6

AConvergentSolutiontoTensorSubspaceLearningHuanWang1ShuichengYan2,ThomasHuang2XiaoouTang1,31IE,ChineseUniversity2ECE,UniversityofIllinois3MicrosoftResearchAsia

ofHongKong,HongKongatUrbanaChampaign,USABeijing,Chinahwang5@ie.cuhk.edu.hk{scyan,huang}@ifp.uiuc.eduxitang@microsoft.com

AbstractRecently,substantialeffortshavebeendevotedtothesubspacelearningtechniquesbasedontensorrepresentation,suchas2DLDA[Yeetal.,2004],DATER[Yanetal.,2005]andTensorSubspaceAnalysis(TSA)[Heetal.,2005].Inthiscontext,avitalyetunsolvedproblemisthatthecomputa-tionalconvergencyoftheseiterativealgorithmsisnotguaranteed.Inthiswork,wepresentanovelso-lutionprocedureforgeneraltensor-basedsubspacelearning,followedbyadetailedconvergencyproofofthesolutionprojectionmatricesandtheobjec-tivefunctionvalue.Extensiveexperimentsonreal-worlddatabasesverifythehighconvergencespeedoftheproposedprocedure,aswellasitssuperiorityinclassificationcapabilityovertraditionalsolutionprocedures.

1IntroductionSubspacelearningalgorithms[Brand,2003]suchasPrinci-palComponentAnalysis(PCA)[TurkandPentland,1991]andLinearDiscriminantAnalysis(LDA)[Belhumeuretal.,1997]traditionallyexpresstheinputdataasvectorsandof-teninahigh-dimensionalfeaturespace.Inrealapplications,theextractedfeaturesareusuallyintheformofamultidi-mensionalunion,i.e.atensor,andthevectorizationprocessdestroysthisintrinsicstructureoftheoriginaltensorform.Anotherdrawbackbroughtbythevectorizationprocessisthecurseofdimensionalitywhichmaygreatlydegradethealgo-rithmiclearnabilityespeciallyinthesmallsamplesizecases.Recentlysubstantialeffortshavebeendevotedtotheem-ploymentoftensorrepresentationforimprovingalgorith-miclearnability[VasilescuandTerzopoulos,2003].Amongthem,2DLDA[Yeetal.,2004]andDATER[Yanetal.,2005]aretensorizedfromthepopularvector-basedLDAalgorithm.Althoughtheinitialobjectivesofthesealgo-rithmsaredifferent,theyallendupwithsolvingahigher-orderoptimizationproblem,andcommonlyiterativepro-cedureswereusedtosearchforthesolution.Acollec-tiveproblemencounteredbytheirsolutionproceduresisthattheiterativeproceduresarenotguaranteedtocon-verge,sinceineachiteration,theoptimizationproblemisapproximatelysimplifiedfromtheTraceRatioform

argmaxUkTr(UkTSpkUk)/Tr(UkTSkUk)

1

totheRatio

TraceformargmaxUkTr[(UkTSkUk)−1(UkTSpkUk)]in

ordertoobtainaclosed-formsolutionforeachiteration.Con-sequently,thederivedprojectionmatricesareunnecessarytoconverge,whichgreatlylimitstheapplicationofthesealgo-rithmssinceitisunclearhowtoselecttheiterationnumberandthesolutionisnotoptimaleveninthelocalsense.Inthiswork,byfollowingthegraphembeddingformula-tionforgeneraldimensionalityreductionproposedby[Yanetal.,2007],wepresentanewsolutionprocedureforsub-spacelearningbasedontensorrepresentation.Ineachit-eration,insteadoftransformingtheobjectivefunctionintotheratiotraceform,wetransformthetraceratiooptimiza-tionproblemintoatracedifferenceoptimizationproblemmaxUkTr[UkT(Spk−λSk)Uk]whereλistheobjectivefunc-

tionvaluecomputedfromthesolution(Uk|nk=1)ofthepre-

viousiteration.Then,eachiterationisefficientlysolvedwiththeeigenvaluedecompositionmethod[Fukunaga,1991].Adetailedproofispresentedtojustifythatλ,namelythevalueoftheobjectivefunction,willincreasemonotonously,andalsoweprovethattheprojectionmatrixUkwillconvergeto

afixedpointbasedonthepoint-to-setmaptheories[Hogan,1973].Itisworthwhiletohighlightsomeaspectsofoursolutionproceduretogeneralsubspacelearningbasedontensorrep-resentationhere:

1.Thevalueoftheobjectivefunctionisguaranteedtomonotonouslyincrease;andthemultipleprojectionma-tricesareprovedtoconverge.Thesetwopropertiesen-surethealgorithmiceffectivenessandapplicability.

2.Onlyeigenvaluedecompositionmethodisappliedforiterativeoptimization,whichmakesthealgorithmex-tremelyefficient;andthewholealgorithmdoesnotsuf-ferfromthesingularityproblemthatisoftenencoun-teredbythetraditionalgeneralizedeigenvaluedecompo-sitionmethodusedtosolvetheratiotraceoptimizationproblem.

3.Theconsequentadvantagebroughtbythesoundtheo-reticalfoundationistheenhancedpotentialclassification

1MatricesSpkandSkarebothpositivesemidefiniteandmore

detaileddefinitionsaredescribedafterward.

IJCAI-07629