Learning to Order Things

Journal of Arti ial In telligen e Resear h 10 (1999) 243-270 Submitted 10/98; published 5/99 Learning to Order Things William W. Cohen w ohen resear h.a tt. Here w e onsider the problem of learning ho w to order instan es giv en feedba k in the form of preferen e judgmen ts, i.e., statemen ts to the ee t that one instan e should b e rank ed ahead of another. W e outline a t w o-stage approa h in whi h one rst learns b y on v en tional means a binary pr efer en e fun tion indi ating whether it is advisable to rank one instan e b efore another. Here w e onsider an online algorithm for learning preferen e fun tions that is based on F reund and S hapire's \Hedge " algorithm. In the se ond stage, new instan es are ordered so as to maximize agreemen t with the learned preferen e fun - tion. W e sho w that the problem of nding the ordering that agrees b est with a learned preferen e fun tion is NP-omplete. Nev ertheless, w e des rib e simple greedy algorithms that are guaran teed to nd a go o d appro ximation. Finally, w e sho w ho w metasear h an b e form ulated as an ordering problem, and presen t exp erimen tal results on learning a om-bination of \sear h exp erts," ea h of whi h is a domain-sp e i query expansion strategy for a w eb sear h engine. Ho w ev er, there are man y appli ations in whi h it is desirable to order rather than lassify instan es. Su h orderings ould b e onstru ted based on a learned probabilisti lassier or regression mo del and in fa t often are. F or instan e, it is ommon pra ti e in information retriev al to rank do umen ts a ording to their probabilit y of relev an e to a query, as estimated b y a learned lassier for the on ept \relev an t do umen t." An adv an tage of learning orderings dire tly is that preferen e judgmen ts an b e m u h easier to obtain than the lab els required for lassi ation learning. F or instan e, in the email appli ation men tioned ab o v e, one approa h migh t b e to rank messages a ording to their estimated probabilit y of mem b ership in the lass of \urgen t" messages, or b y some n umeri al estimate of urgen y obtained b y regression. Supp ose, ho w ev er, that a user is presen ted with an ordered list of email messages, and ele ts to read the third message rst. Giv en this ele tion, it is not ne essarily the ase that message three is urgen t, nor is there suÆ ien t information to estimate an y n umeri al urgen y measures.