There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the form of preference judgments, i.e., statements to the effect that one instance should

Advances in Neural Information Processing Systems 10, Morgan Kaufmann, 1998.WilliamW.CohenRobertE.SchapireYoramSinger

AT&TLabs,180ParkAve.,FlorhamPark,NJ07932wcohen,schapire,singer@research.att.com

Abstract

Therearemanyapplicationsinwhichitisdesirabletoorderratherthanclassify

instances.Hereweconsidertheproblemoflearninghowtoorder,givenfeedback

intheformofpreferencejudgments,i.e.,statementstotheeffectthatoneinstance

shouldberankedaheadofanother.Weoutlineatwo-stageapproachinwhichone

rstlearnsbyconventionalmeansapreferencefunction,oftheformPREF,

whichindicateswhetheritisadvisabletorankbefore.Newinstancesare

thenorderedsoastomaximizeagreementswiththelearnedpreferencefunc-

tion.Weshowthattheproblemof ndingtheorderingthatagreesbestwith

apreferencefunctionisNP-complete,evenunderveryrestrictiveassumptions.

Nevertheless,wedescribeasimplegreedyalgorithmthatisguaranteedto nda

goodapproximation.Wethendiscussanon-linelearningalgorithm,basedonthe

“Hedge”algorithm,for ndingagoodlinearcombinationofranking“experts.”

Weusetheorderingalgorithmcombinedwiththeon-linelearningalgorithmto

ndacombinationof“searchexperts,”eachofwhichisadomain-speci cquery

expansionstrategyforaWWWsearchengine,andpresentexperimentalresults

thatdemonstratethemeritsofourapproach.

1Introduction

Mostpreviousworkininductivelearninghasconcentratedonlearningtoclassify.However,therearemanyapplicationsinwhichitisdesirabletoorderratherthanclassifyinstances.Anexamplemightbeapersonalizedemail lterthatgivesapriorityorderingtounreadmail.Herewewillconsidertheproblemoflearninghowtoconstructsuchorderings,givenfeedbackintheformofpreferencejudgments,i.e.,statementsthatoneinstanceshouldberankedaheadofanother.

Suchorderingscouldbeconstructedbasedonalearnedclassi erorregressionmodel,andinfactoftenare.Forinstance,itiscommonpracticeininformationretrievaltorankdocumentsaccordingtotheirestimatedprobabilityofrelevancetoaquerybasedonalearnedclassi erfortheconcept“relevantdocument.”Anadvantageoflearningorderingsdirectlyisthatpreferencejudgmentscanbemucheasiertoobtainthanthelabelsrequiredforclassi cationlearning.

Forinstance,intheemailapplicationmentionedabove,oneapproachmightbetorankmessagesaccordingtotheirestimatedprobabilityofmembershipintheclassof“urgent”messages,orbysomenumericalestimateofurgencyobtainedbyregression.Suppose,however,thatauserispresentedwithanorderedlistofemailmessages,andelectstoreadthethirdmessage rst.Giventhiselection,itisnotnecessarilythecasethatmessagethreeisurgent,noristheresuf cientinformationtoestimateanynumericalurgencymeasures;however,itseemsquitereasonabletoinferthatmessagethreeshouldhavebeenrankedaheadoftheothers.Thus,inthissetting,obtainingpreferenceinformationmaybeeasierandmorenaturalthanobtainingtheinformationneededforclassi cationorregression.