| |
Abstract:
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
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 "prefer
(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.
|
