TY - GEN

T1 - Learning to order things

AU - Cohen, William W.

AU - Schapire, Robert E.

AU - Singer, Yoram

PY - 1998/1/1

Y1 - 1998/1/1

N2 - There are many applications in which it is desirable to order rather than classify instances. Here wc consider the problem of learning how to order, given feedback in the form of prefcrencc judgments, i.e., statements to the effect that one instance should be ranked ahead of another. We outline a two-stage approach in which one first learns by conventional means a preference function, of the form PREF(u, v), which indicates whether it is advisable to rank u before v. New instances are then ordered so as to maximize agreements with the learned preference function. We show that the problem of finding the ordering that agrees best with a preference function is NP-complete, even under very restrictive assumptions. Nevertheless, we describe a simple greedy algorithm that is guaranteed to find a good approximation. We then discuss an on-line learning algorithm, based on the "Hedge" algorithm, for finding a good linear combination of ranking "experts." We use the ordering algorithm combined with the on-line learning algorithm to find a combination of "search experts/' each of which is a domain-specific query expansion strategy for a WWW search engine, and present experimental results that demonstrate the merits of our approach.

AB - There are many applications in which it is desirable to order rather than classify instances. Here wc consider the problem of learning how to order, given feedback in the form of prefcrencc judgments, i.e., statements to the effect that one instance should be ranked ahead of another. We outline a two-stage approach in which one first learns by conventional means a preference function, of the form PREF(u, v), which indicates whether it is advisable to rank u before v. New instances are then ordered so as to maximize agreements with the learned preference function. We show that the problem of finding the ordering that agrees best with a preference function is NP-complete, even under very restrictive assumptions. Nevertheless, we describe a simple greedy algorithm that is guaranteed to find a good approximation. We then discuss an on-line learning algorithm, based on the "Hedge" algorithm, for finding a good linear combination of ranking "experts." We use the ordering algorithm combined with the on-line learning algorithm to find a combination of "search experts/' each of which is a domain-specific query expansion strategy for a WWW search engine, and present experimental results that demonstrate the merits of our approach.

UR - http://www.scopus.com/inward/record.url?scp=28444495042&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=28444495042&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:28444495042

SN - 0262100762

SN - 9780262100762

T3 - Advances in Neural Information Processing Systems

SP - 451

EP - 457

BT - Advances in Neural Information Processing Systems 10 - Proceedings of the 1997 Conference, NIPS 1997

PB - Neural information processing systems foundation

T2 - 11th Annual Conference on Neural Information Processing Systems, NIPS 1997

Y2 - 1 December 1997 through 6 December 1997

ER -