英文版学习课件：Feature Selection for Ranking

FeatureSelectionforRanking

Cenfangming2007.10ABSTRACT

TherealityisthatmanyfeatureselectionmethodsusedinclassificationaredirectlyappliedtorankingWearguethatbecauseofthestrikingdifferencesbetweenrankingandclassification,itisbettertodevelopdifferentfeatureselectionmethodsforranking.

InthispaperweproposeanewfeatureselectionmethodDefinetherankingaccuracyintermsofaperformancemeasureoralossfunctionastheimportanceofthefeatureandthecorrelationbetweentherankingresultsoftwofeaturesasthesimilaritybetweenthem.Wealsodemonstratehowtosolvetheoptimizationprobleminanefficientway.Wehavetestedtheeffectivenessofourfeatureselectionmethodontwoinformationretrievaldatasetsandwithtworankingmodel1.INTRODUCTION

RankingSVMandRankNet

First,featureselectioncanhelpenhanceaccuracyinmanymachinelearningproblems,whichstronglyindicatesthatfeatureselectionisalsonecessaryforranking

Second,featureselectioncanalsohelpimprovetheefficiencyoftraining.Ininformationretrieval,especiallyinwebsearch,usuallythedatasizeisverylargeandthustrainingofrankingmodelsiscomputationallycostly.

Therehavebeennomethodsoffeatureselectiondedicatedlyproposedforranking.Mostofthemethodsusedinrankingweredevelopedforclassification.Featureselectionmethodsinclassificationfallintothreecategorie

Thefirstcategory,whichisnamedfilter,featureselectionisdefinedasapreprocessingstepandcanbeindependentfromlearning.thatinformationgain(IG)andchi-square(CHI)areamongthemosteffectivemethodsoffeatureselectionforclassification.

ThesecondcategoryreferredtoaswrapperutilizesthelearningsystemasablackboxtoscoresubsetsoffeaturesThethirdcategorycalledtheembeddedmethodperformsfeatureselectionwithintheprocessoftraining.Second,theevaluationmeasures(e.g.meanaverageprecision(MAP)andnormalizeddiscountedcumulativegain(NDCG))usedinrankingproblemsaredifferentfromthosemeasuresusedinclassification

1)inrankingusuallyprecisionismoreimportantthanrecallwhileinclassificationbothprecisionandrecallareimportant;

SeveralproblemsmayarisewhenapplyingthefeatureselectionmethodstorankingFirst:existingfeatureselectionmethodsforclassificationarenotsuitableforranking.Inranking,anumberoforderedcategoriesareused,representingtherankingrelationshipbetweeninstances,whileinclassificationthecategoriesare“flat”

2)

inrankingcorrectlyrankingthetop-ninstancesismorecriticalwhileinclassificationmakingacorrectclassificationdecisionisofequalsignificanceforallinstances.

Thefollowingarethepropertiesofthenovelmethodforfeatureselectioninranking1)Themethodmakesuseofrankinginformation,insteadofsimplyviewingtheranksasflatcategories.2)Inspiredbytheworkin[1][14][27],itconsidersthesimilaritiesbetweenfeatures,andtriestoavoidselectingredundantfeatures.3)Itmodelsfeatureselectionforrankingasamulti-objectiveoptimizationproblem.Thefinalobjectiveistofindasetoffeatureswithmaximumimportanceandminimumsimilarity.4)Itprovidesagreedysearchalgorithmtosolvetheoptimizationproblem.Thecorrespondingsolutionproducedisproventobeequivalenttotheoptimalsolutiontotheoriginalproblemundercertaincondition.2.FEATURESELECTIONMETHOD

2.1OverviewSupposethegoalistoselect(1≤t≤m)featuresfromtheentirefeatureset{1,2,…,}.Inourmethodwefirstdefinetheimportancescoreofeachfeature,anddefinethesimilaritybetweenanytwofeaturesand.Thenweemployanefficientalgorithmtomaximizethetotalimportancescoresandminimizethetotalsimilarityscoresofasetoffeatures.

2.2ImportanceoffeatureWefirstassignanimportancescoretoeachfeature.Specifically,weproposeusinganevaluationmeasurelikeMAPandNDCGoralossfunction(e.g.pair-wiserankingerrors[10][13])tocomputetheimportancescore.Intheformer,wefirstrankinstancesusingthefeature,evaluatetheperformanceintermsofthemeasure,andthentaketheevaluationresultastheimportancescore.Inthelatter,wealsorankinstancesusingthefeature,andthenviewascoreinverselyproportionaltothecorrespondinglossastheimportancescore

2.3SimilaritybetweenfeaturesInthiswork,wemeasurethesimilaritybetweenanytwofeaturesonthebasisoftheirrankingresults.Thatis,weregardeachfeatureasarankingmodel,andthesimilaritybetweentwofeaturesisrepresentedbythesimilaritybetweentherankingresultsthattheyproduce.wechooseKendall’s𝜏asanexample.TheKendall’s𝜏valueofqueryqforanytwofeatures𝑣𝑖and𝑣𝑗canbecalculatedasfollows,

2.4Optimizationformulation

wewanttoselectthosefeatureswithlargesttotalimportancescoresandsmallesttotalsimilarityscores.Mathematically,thiscanberepresentedasfollows:

In(1),therearetwoobjectives:tomaximizethesumoftheimportancescoresofindividualfeatures,andtominimizethesumofsimilarityscoresbetweenanytwofeatures.wetakeacommonapproachinoptimizationandconvertmulti-objectiveprogrammingtosingleobjectiveprogrammingusinglinearcombination.

2.5Solutiontooptimizationproblem

Theoptimizationin(2)isatypical0-1integerprogrammingproblem.Onepossibleapproachwouldbetoperformexhaustivesearch.However,thetimecomplexityofit,𝑂(𝐶𝑚),istoohightomakeitapplicableinrealapplications.Weneedtolookformorepracticalsolutions.

Inthiswork,weproposeagreedysearchalgorithmfortacklingtheissueAlgorithmGAS(GreedysearchAlgorithmoffeatureSelection)1.ConstructanundirectedgraphG0,inwhicheachnoderepresentsafeature,theweightofnode𝑣is𝜔andtheweightofanedgebetweennode𝑣andnode𝑣is 2.ConstructasetStocontaintheselectedfeatures.InitiallyS0=∅.

3.Fori=1…t,(1)Selectthenodewiththelargestweight,withoutlossofgenerality,supposethattheselectednodeis

(2)Apunishmentisconductedonalltheothernodesaccordingtotheirsimilaritieswith𝑣.Thatis,theweightsofalltheothernodesareupdatedasfollows.(3)Add𝑣tothesetSandremoveitfromgraphGtogetherwithalltheedgesconnectedtoit:4.OutputSt.

Theorem1:WiththegreedysearchalgorithminFig.1onecanfindtheoptimalsolutiontoproblem(2),providedthat𝑆𝑡𝑡,where𝑆denotestheselectedfeaturesetwith𝑡Proof:Thecondition𝑆𝑡indicatesthatwhenselectingthe(t+1)-thfeature,wedonotchangethealready-selectedtfeatures.Denote𝑆𝑡={𝑣𝑘|𝑖i=1,…,t},where𝑣istheki-thfeatureselectedinthei-thiteration.Thenthetaskturnsouttobethatoffindingthe(t+1)-thfeaturesothatthefollowingobjectivecanbemet.

Since,wecanrewrite(3)as

Andsince𝑆𝑡and={𝑣|i=1,…,t𝑡},(4)equals 3.EXPERIMENTSETTINGS

3.1DatasetsInourexperiments,weusedtwobenchmarkdatasets.1)Thefirstdatasetisthe.govdatawhichwasusedinthetopicdistillationtaskofWebtrackofTREC2004[28].2)TheseconddatasetistheOHSUMEDdata[9],whichwasusedinmanyexperimentsininformationretrieval[6][10],includingtheTREC-9filteringtrack[26].3.2Evaluationmeasures

3.2.1Meanaverageprecision(MAP)

MAPisameasureonprecisionofrankingresultsItisassumedthattherearetwotypesofdocuments:positiveandnegative(relevantandirrelevant).Precisionatnmeasurestheaccuracyoftopnresultsforaquery.Averageprecisionofaqueryiscalculatedbasedonprecisionatn:

3.2.2Normalizeddiscountcumulativegain(NDCG)

NDCGisdesignedformeasuringrankingaccuracieswhentherearemultiplelevelsofrelevancejudgment.Givenaquery,NDCGatpositionninisdefined3.3Rankingmodel3.3.1RankingSVM

RankingSVMmakesanextensionofSVMtoranking;incontrasttotraditionalSVMwhichworksoninstances,RankingSVMutilizesinstancepairsandtheirpreferencelabelsintraining.TheoptimizationformulationofRankingSVMisasfollows:

3.3.2RankNet

RankNetalsousesinstancepairsintraining.itemploysaneuralnetworkastherankingfunctionandrelativeentropyaslossfunction.Letbetheestimatedposteriorprobability𝑃andbethe“true”posteriorprobability,andlet.ThelossforaninstancepairinRankNetisdefinedas

3.4Algorithmsforcomparison

Ourproposedalgorithmhastwovariants.Welisttheminthefollowingtable.

Forcomparison,weselectedIGandCHIasthebaselines.IGmeasuresthereductioninuncertainty(entropy)inclassificationpredictionwhenknowingthefeature.CHImeasuresthedegreeofindependencebetweenthefeatureandthecategories.wealsoused“WithAllFeatures(WAF)”asanotherbaseline,inordertoshowthebenefitofconductingfeatureselection.4.EXPERIMENTALRESULTS

4.1The.govdataFig.2showstheperformancesofthefeatureselectionmethodsonthe.govdatasetwhentheyworkaspreprocessorsofRankingSVM.Fig.3showstheperformanceswhenusingRankNetastherankingmodel.Inthefigures,thex-axisrepresentsthenumberofselectedfeatures.ExperimentalresultsindicatethatinmostcasesGAS-LcanoutperformGAS-E,althoughnotsignificantlyExperimentalresultsalsoindicatethatwithGAS-LandGAS-EasfeatureselectionmethodstherankingperformancesofRankingSVMaremorestablethanthosewithIGandCHIasfeatureselectionmethods.4.2OHSUMEDdataFig.4showstheresultsofdifferentfeatureselectionmethodsontheOHSUMEDdatasetwhentheyworkaspreprocessorsofRankingSVMFig.5showstheresultsofdifferentfeatureselectionmethodsontheOHSUMEDdatasetwhentheyworkaspreprocessorsofRankNet4.3Discussions

Fromtheresultsofthetwodatasets,wemadethefollowingobservations:1)Featureselectioncanimprovetherankingperformancemoresignificantlyforthe.govdatasetthanfortheOHSUMEDdataset.

2)OurproposedalgorithmsoutperformIGandCHImoresignificantlyforthe.govdatasetthanfortheOHSUMEDdataset.

Tofigureoutthereasons,weconductedthefollowingadditionalexperiments.WefirstplottedtheimportanceofeachfeatureinthetwodatasetsinFig.6.Thex-axisrepresentsfeaturesandthey-axisrepresentstheirMAPvalueswhentheyareregardedasrankingmodels.Furthermore,weplottedthesimilaritybetweenanytwofeatures(intermsofKendall’s𝜏)inthetwo\datasetsinFig.7.Here,bothx-axisandy-axisrepresentfeatures,andthelevelofdarknessrepresentsthestrengthofsimilarity(thedarker,themoresimilar).Basedonthediscussionsabove,weconcludethatiftheeffectsoffeaturesvarylargelyandthereareredundantfeatures,ourmethodcanworkverywell.Whenapplyingourmethodinpractice,therefore,onecanfirsttestthetwoaspects.5.CONCLUSIONSANDFUTUREWORK

Inthispaper,wehaveproposedanoptimizationmethodforfeatureselectioninranking.hecontributionsofthispaperincludethefollowingpoints.1)Wehavediscussedthedifferencesbetweenclassificationandranking,andmadeclearthelimitationsoftheexistingfeatureselectionmethodswhenappliedtoranking.2)Wehaveproposedanovelmethodtoselectfeaturesforranking,inwhichtheproblemisformalizedasanoptimizationissue.3)Wehaveevaluatedtheproposedmethod