Learning to order things

There are many applications in which it is desirable to order rather than c lassify instances. Here we consider the problem of learning how to order in stances given feedback in the form of preference judgments, i.e., statement s to the effect that one instance should be ranked ahead of another. We out line a two-stage approach in which one first learns by conventional means a binary preference function indicating whether it is advisable to rank one instance before another. Here we consider an on-line algorithm for learning preference functions that is based on Freund and Schapire's "Hedge" algori thm. In the second stage, new instances are ordered so as to maximize agree ment with the learned preference function. We show that the problem of find ing the ordering that agrees best with a learned preference function is NP- complete. Nevertheless, we describe simple greedy algorithms that are guara nteed to find a good approximation. Finally, we show how metasearch can be formulated as an ordering problem, and present experimental results on lear ning a combination of "search experts," each of which is a domain-specific query expansion strategy for a web search engine.