\documentstyle[jair,twoside,11pt,psfig,theapa]{article}

% \jairheading{ }{ }{ }{ }{ }
\jairheading{10}{1999}{243-270}{10/98}{5/99}

\ShortHeadings{Learning to Order Things}{Cohen, Schapire, \& Singer}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\figline}{\rule{\textwidth}{1pt}}

\newcommand{\pot}{\pi}
\newcommand{\oset}{{S}}
\newcommand{\eset}{{X}}
\newcommand{\esett}{\eset^t}
\newcommand{\cset}{{\cal C}}
\newcommand{\gset}{{\cal G}}
\newcommand{\tset}{{\cal T}}
\newcommand{\rsys}{{R}}
\newcommand{\ssys}{{P}}
\newcommand{\Rsys}{{\cal R}}
\newcommand{\feedback}{{F}}
\newcommand{\donno}{{\bot}}
\newcommand{\pvec}{{\bf w}}
\newcommand{\vvec}{{q}}
\newcommand{\pvecinst}[2]{w^{#1}_{#2}}
\newcommand{\pvect}{w^t}
\newcommand{\pveci}{w_i}
\newcommand{\pvecti}{\pvecinst{t}{i}}
\newcommand{\ndis}{{\bf D}}
\newcommand{\nagr}{{\rm AGREE}}
\newcommand{\disagree}{{\rm DISAGREE}}
\newcommand{\nincom}{{\bf I}}
\newcommand{\ndisw}[2]{\ndis_{#1}({#2})}
\newcommand{\nagrw}[2]{\nagr_{#1}({#2})}
\newcommand{\edge}[2]{#1 \rightarrow #2}
\newcommand{\edgegen}{\edge{u}{v}}
\newcommand{\edgegeninv}{\edge{v}{u}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\newcommand{\half}{{1 \over 2}}
\newcommand{\Wedge}{{\cal W}}
\newcommand{\Hedge}{{\rm Hedge}}
\newcommand{\WWedge}{\tilde{\cal W}}
\newcommand{\incomp}{<>}
\newcommand{\nin}{{\not\in}}
\newcommand{\Loss}{{\rm Loss}}
\newcommand{\prefer}{{\rm PREF}}
\newcommand{\prefert}{\prefer^t}
\newcommand{\ofun}{{f}}
\newcommand{\APPROX}{{\rm APPROX}}
\newcommand{\OPT}{{\rm OPT}}
\newcommand{\rhoapprox}{\hat{\rho}}

\newcommand{\parens}[1]{\left({#1}\right)}

\newfont{\msym}{msbm10}
\newcommand{\reals}{\mbox{\msym R}}

%
%   The following commands define and indent theorem-like environments
%
\newsavebox{\theorembox}
\newsavebox{\lemmabox}
\newsavebox{\corollarybox}
\newsavebox{\propositionbox}
\newsavebox{\examplebox}
\savebox{\theorembox}{\bf Theorem}
\savebox{\lemmabox}{\bf Lemma}
\savebox{\corollarybox}{\bf Corollary}
\savebox{\propositionbox}{\bf Proposition}
\savebox{\examplebox}{\bf Example}
\newtheorem{theorem}{\usebox{\theorembox}}
\newtheorem{lemma}{\usebox{\lemmabox}}[section]
\newtheorem{corollary}[lemma]{\usebox{\corollarybox}}
\newtheorem{proposition}[lemma]{\usebox{\propositionbox}}
\newtheorem{example}{\usebox{\examplebox}}
\newtheorem{definition}{{\sc Definition}\rm }[section]
\newtheorem{definitions}[definition]{{\sc Definitions\rm }}
\newtheorem{assumption}{{\sc Assumption}\rm }[section]
\newtheorem{assumptions}[assumption]{{\sc Assumptions\rm }}
\newtheorem{observation}{{\sc Observation}\rm }[section]
\newtheorem{observations}[observation]{{\sc Observations\rm }}

\newcommand{\trm}[1]{{\em {#1}}}
\newcommand{\yy}[1]{{\it [wc note: #1]}\/}
\newcommand{\ct}[1]{{[cite: #1]}}
\newcommand{\cut}[1]{}

%
% Miscellaneous commands for proofs
%
\newcommand{\qedsketch}{\;\;\;\Box}
% \newcommand{\qed}{\;\;\;\rule[0.1mm]{2mm}{2mm}}
\newcommand{\qed}{\;\;\;\Box}
\newenvironment{proof}{\noindent{\bf Proof:~~}}{\(\qed\)}
\newlength{\saveskip}
\setlength{\saveskip}{\baselineskip}
\newenvironment{proofsketch}{%
   \noindent{\bf Proof sketch:~~}%
   }%
  {\(\qedsketch\)}
\newenvironment{claim}{{\bf Claim:~~}}{}
\newcommand{\case}[1]{{\small \sc Case #1:}}
\newcommand{\subcase}[1]{{\em Case #1:}\/}
\newcommand{\basis}{{\small \sc Basis }}
\newcommand{\induction}{{\small \sc Induction }}
\newcommand{\construction}{{\small \sc Construction: }}
\newcommand{\correctness}{{\small \sc Correctness: }}
\newcommand{\analysis}{{\small \sc Analysis: }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\setcounter{page}{243}

\title{Learning to Order Things}

\author{%
\name William W. Cohen \email wcohen@research.att.com \\
\name Robert E. Schapire \email schapire@research.att.com \\
\name Yoram Singer \email singer@research.att.com \\
\addr AT\&T Labs, Shannon Laboratory, 180 Park Avenue\\
Florham Park, NJ 07932, USA}

\maketitle

\begin{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 instances given feedback in the form of preference judgments,
{\it 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 binary {\em 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$''
algorithm.  In the second stage, new instances are ordered so as to
maximize agreement with the learned preference function.  We show that
the problem of finding the ordering that agrees best with a learned
preference function is NP-complete.  Nevertheless, we describe simple
greedy algorithms that are guaranteed to find a good approximation.
Finally, we show how metasearch can be formulated as an ordering
problem, and present experimental results on learning a combination of
``search experts,'' each of which is a domain-specific query expansion
strategy for a web search engine.
\end{abstract}

%% ===================================================================

\section{Introduction} \label{intro:sec}

Work in inductive learning has mostly concentrated on learning
to classify. However, there are many applications in which it is
desirable to order rather than classify instances. An example might be
a personalized email filter that prioritizes unread mail.  Here we
will consider the problem of learning how to construct such orderings
given feedback in the form of \trm{preference judgments}, {{\it i.e.},
statements that one instance should be ranked ahead of another.

Such orderings could be constructed based on a learned probabilistic
classifier or regression model and in fact often are. For instance, it
is common practice in information retrieval to rank documents according
to their probability of relevance to a query, as estimated by a learned
classifier for the concept ``relevant document.'' An advantage of
learning orderings directly is that preference judgments can be much
easier to obtain than the labels required for classification learning.

For instance, in the email application mentioned above, one approach
might be to rank messages according to their estimated probability of
membership in the class of ``urgent'' messages, or by some numerical
estimate of urgency obtained by regression.  Suppose, however, that a
user is presented with an ordered list of email messages, and elects
to read the third message first.  Given this election, it is not
necessarily the case that message three is urgent, nor is there
sufficient information to estimate any numerical urgency measures.
However, it seems quite reasonable to infer that message three should
have been ranked ahead of the others.  Thus, in this setting,
obtaining preference information may be easier and more natural than
obtaining the labels needed for a classification or regression
approach.

Another application domain that requires ordering instances is
\trm{collaborative filtering}; see, for instance, the papers contained
in Resnick and Varian~\citeyear{ResnickVarian97}. In a typical
collaborative filtering task, a user seeks recommendations, say, on
movies that she is likely to enjoy. Such recommendations are usually
expressed as ordered lists of recommended movies, produced by
combining movie ratings supplied by other users.  Notice that each
user's movie ratings can be viewed as a set of preference judgements. In
fact, interpreting ratings as preferences is advantageous in several
ways: for instance, it is not necessary to assume that a rating of
``7'' means the same thing to every user.

In the remainder of this paper, we will investigate the following
two-stage approach to learning how to order. In stage one, we learn a
\trm{preference function}, a two-argument function $\prefer(u,v)$
which returns a numerical measure of how certain it is that $u$ should
be ranked before $v$.  In stage two, we use the learned preference
function to order a set of new instances $X$; to accomplish this, we
evaluate the learned function $\prefer(u,v)$ on all pairs of instances
$u,v\in{}X$, and choose an ordering of $X$ that agrees, as much as
possible, with these pairwise preference judgments.  

For stage one, we describe a specific algorithm for learning a
preference function from a set of ``ranking-experts''. The algorithm
is an on-line weight allocation algorithm, much like the weighted
majority algorithm~\cite{LittlestoneWa94} and
Winnow~\cite{Littlestone88}, and, more directly, Freund and
Schapire's~\citeyear{FS95} ``Hedge'' algorithm.  For stage two, we show
that finding a total order that agrees best with such a preference
function is NP-complete.  Nevertheless, we show that there are
efficient greedy algorithms that always find a good approximation to
the best ordering.

We then present some experimental results in which these algorithm are
used to combine the results of several ``search experts,'' each of
which is a domain-specific query expansion strategy for a web search
engine. Since our work touches several different fields we defer the
discussion of related work to Sec.~\ref{related:sec}.

%% ===================================================================

\section{Preliminaries} \label{prel:sec}

Let $\eset$ be a set of instances.
For simplicity, in this paper, we always assume that $\eset$ is finite.
A \trm{preference function} \prefer{} is a binary function \(
\prefer:\eset\times\eset\rightarrow[0,1]\).  A value of $\prefer(u,v)$
which is close to $1$ (respectively $0$) is interpreted as a strong
recommendation that $u$ should be ranked above (respectively, below)
$v$.  A value close to $1/2$ is interpreted as an abstention from
making a recommendation. As noted earlier, the hypothesis of our
learning system will be a preference function, and new instances will
be ranked so as to agree as much as possible with the preferences
predicted by this hypothesis.

In standard classification learning, a hypothesis is constructed by
combining primitive features. Similarly, in this paper, a preference
function will be a combination of primitive preference functions. In
particular, we will typically assume the availability of a set of $N$
primitive preference functions $\rsys_1,\ldots,\rsys_N$. These can
then be combined in the usual ways, for instance with a boolean or
linear combination of their values. We will be especially interested in
the latter combination method.

It is convenient to assume that the $\rsys_i$'s are well-formed in
certain ways. To this end, we introduce a special kind of preference
function called a {rank ordering} which is defined by an ordering
function. Let $\oset$ be a totally ordered set. We assume without loss
of generality that $\oset\subseteq \reals$. An \trm{ordering function
into \oset} is any function $\ofun:\eset\rightarrow\oset$, where we
interpret an inequality $f(u) > f(v)$ to mean that $u$ is ranked above
$v$ by $f$. It is sometimes convenient to allow an ordering function
to ``abstain'' and not give a preference for a pair $u$, $v$. We
therefore allow $\oset$ to include a special symbol $\donno$ not in
$\reals$, and we interpret $f(u)=\donno$ to mean that $u$ is
``unranked.'' We define the symbol $\donno$ to be incomparable to all
the elements in $\oset$ (that is, $\donno \not< s$ and $s \not< \donno$
for all $s\in\oset$).

An ordering function $\ofun$ induces the
preference function $\rsys_\ofun$, defined as
\[ \rsys_\ofun(u,v) = 
    \left\{ 
	\begin{array}{ll}
	  1 & \mbox{if $\ofun(u)>\ofun(v)$}\\ 
	  0 & \mbox{if $\ofun(u)<\ofun(v)$}\\ 
	  \half & \mbox{otherwise.}\\
	\end{array}
    \right.
\]
We call $\rsys_f$ a \trm{rank ordering for $\eset$ into
$\oset$}.  If $\rsys_f(u,v)=1$, then we say that $u$ is preferred
to $v$, or $u$ is ranked higher than $v$.  
Note that
$\rsys_\ofun(u,v)=\half$ if either $u$ or $v$ (or both) is unranked.

We will sometimes describe and manipulate preference functions as
directed weighted graphs. The nodes of a graph correspond to the
instances in $X$. Each pair $(u,v)$ is connected by a directed edge with
weight $\prefer(u,v)$.  Since an ordering function $f$ induces a
preference function $R_f$, we can also describe ordering functions as
graphs. In Fig.~\ref{rsys:fig} we give an example of two ordering
functions and their corresponding graphs. For brevity, we do not draw
edges $(u,v)$ such that $\prefer(u,v)=\half$ or $\prefer(u,v)=0$.

\begin{figure}[t]
\centerline{\psfig{figure=PS/rsys.eps,height=5.0cm}}
\caption{Left and middle: Two ordering functions and their graph
representation. Right: The graph representation of the preference
function created by a weighted (${1 \over 4}$ and ${3 \over 4}$)
combination of the two functions. Edges with weight of $\half$ 
or $0$ are omitted.
\label{rsys:fig}}
\end{figure}

To give a concrete example of rank orderings, imagine learning to order
documents based on the words that they contain. To model this, let
$\eset$ be the set of all documents in a repository, and for $N$ words
$w_1,\ldots,w_N$, let $\ofun_{i}(u)$ be the number of occurrences of
word $w_i$ in document $u$. Then $\rsys_{\ofun_i}$ will prefer $u$ to
$v$ whenever $w_i$ occurs more often in $u$ than $v$. As a second
example, consider a metasearch application in which the goal is to
combine the rankings of several web search engines on some fixed query.
For $N$ search
engines $e_1,\ldots,e_N$, one might define $\ofun_{i}$ so that
$\rsys_{\ofun_i}$ prefers web page $u$ to web page $v$ whenever $u$ is
ranked ahead of $v$ in the list $L_i$ produced by the corresponding
search engine.
To do this, one could let $\ofun_i(u) = -k$ for the web page $u$
appearing in the $k$-th position in the list $L_i$, and let
$\ofun_i(u)=-M$ (where $M>|L_i|$) for any web page $u$ not appearing
in $L_i$.

Feedback from the user will be represented in a similar but more
general way. We will assume that feedback is a set element pairs
$(u,v)$, each representing an assertion of the form ``$u$ should be
preferred to $v$.'' This definition of feedback is less restricted
than ordering functions. In particular, we will not assume that the
feedback is consistent---cycles, such as $a>b>a$, will be allowed.

%% ===================================================================

\section{Learning a Combination of Ordering Functions}
\label{learn:sec}

In this section, we consider the problem of learning a good linear
combination of a set of ordering functions. Specifically, we assume
access to a set of {\em ranking experts}, each of which generates an
ordering function when provided with a set of instances.  For
instance, in a metasearch problem, each ranking expert might be a
function that submits the user's query to a different search engine;
the domain of instances might be the set of all web pages returned by
any of the ranking experts; and the ordering function associated with
each ranking expert might be represented as in the example above ({\it
i.e.}, letting $\ofun_i(u) = -k$ for the $k$-the web page $u$ returned
by $i$-th search engine, and letting $\ofun_i(u)=-M$ for any web page
$u$ not retrieved by the $i$-th search engine).  The user's feedback
will be a set of pairwise preferences between web pages. This feedback
may be obtained directly, for example, by asking the user to
explicitly rank the URL's returned by the search engine; or the
feedback may be obtained indirectly, for example, by measuring the
time spent viewing each of the returned pages.

We note that for the metasearch problem, an approach that works
directly with the numerical scores associated with the different
search engines might not be feasible; these numerical scores might not
be comparable across different search engines, or might not be
provided by all search engines.  Another problem is that most web
pages will not be indexed by all search engines.  This can be easily
modeled in our setting: rather than letting $\ofun_i(u)=-M$ for a web
page $u$ that is not ranked by search engine $i$, one could let
$\ofun_i(u)=\donno$. This corresponds to the assumption that the
search engine's preference for $u$ relative to ranked web pages is
unknown.

We now describe a weight allocation algorithm that uses the preference
functions $\rsys_i$ to learn a preference function of the form \(
\prefer(u,v) = \sum_{i=1}^N w_i\rsys_i(u,v) \).  We adopt the on-line
learning framework first studied by
Littlestone~\citeyear{Littlestone88} in which the weight $w_i$
assigned to each ranking expert $i$ is updated incrementally.

Formally, learning is assumed to take place in a sequence of rounds.
On each round $t$, we assume the learning algorithm is provided with a
set $\esett$ of instances to be ranked, for which each ranking expert
$i\in\{1,\ldots,N\}$ provides an ordering function $\ofun_i^t$.  (In
metasearch, for instance, $\ofun_i^t$ is the ordering function
associated with the list $L_i^t$ of web pages returned by the $i$-th
ranking expert for the $t$-th query, and $X^t$ is the set of all web
pages that appear in any of the lists $L_1^t,\ldots,L_N^t$.)  Each
ordering function $\ofun_i^t$ induces a preference function
$\rsys_{\ofun^t_i}$, which we denote for brevity by $\rsys_i^t$.  The
learner may compute $\rsys^t_i(u,v)$ for any and all preference
functions $\rsys^t_i$ and pairs $u,v\in{}\esett$ before producing a
combined preference function $\prefert$, which is then used to produce
an ordering $\rhoapprox^t$ of $\esett$. (Methods for producing an
ordering from a preference function will be discussed below.)

After producing the ordering $\rhoapprox^t$, the learner receives
feedback from the environment. We assume that the feedback is an
arbitrary set of assertions of the form ``$u$ should be preferred to
$v$.'' That is, the feedback on the $t$-th round is a set
$\feedback^t$ of pairs $(u,v)$.  

The algorithm we propose for this problem is based on the ``weighted
majority algorithm'' of Littlestone and Warmuth~\citeyear{LittlestoneWa94}
and, more directly, on Freund and Schapire's \citeyear{FS95} ``Hedge''
algorithm.  We define the \trm{loss} of a preference function $\rsys$
with respect to the user's feedback $\feedback$ as
\begin{equation}
\Loss(\rsys,\feedback) =
\frac{\sum_{(u,v)\in\feedback} (1-\rsys(u,v))}{|\feedback|} =
1 - {1 \over |\feedback|} \sum_{(u,v)\in\feedback} \rsys(u,v) ~ .
\label{loss_def:eqn}
\end{equation}
This loss has a natural probabilistic interpretation. If $\rsys$ is
viewed as a randomized prediction algorithm that predicts that $u$
will precede $v$ with probability $\rsys(u,v)$, then
$\Loss(\rsys,\feedback)$ is the probability of $\rsys$ disagreeing
with the feedback on a pair $(u,v)$ chosen uniformly at random
from $\feedback$. 

It is worth noting that the assumption on the form of the feedback can
be further relaxed by allowing the user to indicate the degree to which
she prefers $u$ over $v$. In this case, the loss should be normalized
by the weighted sum of feedback pairs. Since this generalization is
rather straightforward, we assume for brevity that the feedback is an
unweighted set of assertions over element pairs.

We now can use the $\Hedge$ algorithm almost verbatim, as shown in
Figure~\ref{hedge4rank:alg}.  The algorithm maintains a positive
weight vector whose value at time $t$ is denoted by $\pvec^t =
(\pvecinst{t}{1},\ldots,\pvecinst{t}{N})$.  If there is no prior
knowledge about the ranking experts, we set all initial weights to be
equal so that $\pvecinst{1}{i} = 1/N$. 

On each round $t$, the weight vector $\pvec^t$ is used to combine the
preference functions of the different experts to obtain the preference
function $\prefert(u,v) = \sum_{i=1}^N \pvecinst{t}{i}
\rsys^t_i(u,v)$.  This preference function is next converted into an
ordering $\rhoapprox^t$ on the current set of elements $\eset^t$. For
the purposes of this section, the method of producing an ordering is
immaterial; in particular, any of the methods described in
Sec.~\ref{sec:combine} could be used here. Based on this ordering, the
user provides feedback $\feedback^t$, and the loss for each preference
function $\Loss(\rsys^t_i,\feedback^t)$ is evaluated as in
Eq.~(\ref{loss_def:eqn}). Finally, the weight vector $\pvec^t$ is
updated using the multiplicative rule
\[
\pvecinst{t+1}{i} =
	\frac{\pvecinst{t}{i} \cdot \beta^{Loss(\rsys^t_i,\feedback^t)}}{Z_t}
\]
where $\beta\in [0,1]$ is a parameter, and $Z_t$ is a normalization
constant, chosen so that the weights sum to one after the update.
Thus, in each round, the weights of the ranking experts are adjusted
so that experts producing preference functions with relatively large
agreement with the feedback are increased.


\begin{figure}[t]
\normalsize
{\bf Allocate Weights for Ranking Experts} \newline
{\bf Parameters:}
\begin{minipage}[t]{4.5in}
$\beta\in [0,1]$,
initial weight vector $\pvec^{1}\in [0,1]^N$
    with $\sum_{i=1}^N \pvecinst{1}{i} = 1$\\
$N$ ranking experts,
number of rounds $T$
\end{minipage} \newline

{\noindent {\bf Do for}} $t=1,2,\ldots,T$
\begin{enumerate}
 \item Receive a set of elements $\esett$ and ordering functions
$\ofun^t_1,\ldots,\ofun^t_N$.  Let $\rsys^t_i$ denote the
preference function induced by $\ofun^t_i$.

 \item Compute a total order
$\rhoapprox^t$ which approximates
\[ \prefert(u,v) = \sum_{i=1}^N w^t_i\rsys^t_i(u,v)
\]
(Sec.~\ref{sec:combine} describes several ways of
approximating a preference function with a total order.) 

 \item Order $\esett$ using $\rhoapprox^t$.
 \item Receive feedback $\feedback^t$ from the user.
 \item Evaluate losses $\Loss(\rsys^t_i,\feedback^t)$ as defined in
		Eq.~(\ref{loss_def:eqn}).
 \item Set the new weight vector
\[
\pvecinst{t+1}{i} =\frac{\pvecinst{t}{i} \cdot \beta^{\Loss(\rsys^t_i,\feedback^t)}}
{Z_t}
\]
where $Z_t$  is a normalization
constant, chosen so that $\sum_{i=1}^N \pvecinst{t+1}{i} = 1$.
\end{enumerate}
\figline
\caption{The on-line weight allocation algorithm.}
\label{hedge4rank:alg}
\end{figure}

We now give the theoretical rationale behind this algorithm.
Freund and Schapire~\citeyear{FS95} prove general results about
$\Hedge$ which can be applied directly to this loss function.
Their results imply almost immediately a bound on the cumulative loss
of the preference function $\prefert$ in terms of the loss of the best
ranking expert, specifically:

\begin{theorem} \label{thm:experts}
For the algorithm of Fig.~\ref{hedge4rank:alg},
\[
\sum_{t=1}^T \Loss(\prefert, \feedback^t) \leq
    a_\beta \min_i \sum_{t=1}^T \Loss(\rsys^t_i, \feedback^t)
               + c_\beta \ln N
\]
where $a_\beta = \ln(1/\beta) / (1-\beta)$
and $c_\beta = 1 / (1-\beta)$.
\end{theorem}

Note that $\sum_{t} \Loss(\prefert, \feedback^t)$ is the cumulative
loss of the combined preference functions $\prefert$, and
$\sum_{t} \Loss(\rsys^t_i, \feedback^t)$ is the cumulative loss of the
$i$th ranking expert.
Thus, Theorem~\ref{thm:experts} states that the cumulative loss of the
combined preference functions will not be much worse than that of
the best ranking expert.

\begin{proof}
We have that
\begin{eqnarray*}
\Loss(\prefert, \feedback^t) &=&
  1 - \frac{1}{\feedback^t}
        \sum_{(u,v)\in\feedback^t} \sum_i w^t_i \rsys^t_i(u,v) \\
&=&
 \sum_i w^t_i \parens{  1 - \frac{1}{\feedback^t}
        \sum_{(u,v)\in\feedback^t} \rsys^t_i(u,v) } \\
&=&
 \sum_i w^t_i \Loss(\rsys^t_i(u,v), \feedback^t).
\end{eqnarray*}
Therefore, by Freund and Schapire's~\citeyear{FS95} Theorem~2,
\begin{eqnarray*}
\sum_{t=1}^T \Loss(\prefert, \feedback^t) &=&
\sum_{t=1}^T \sum_i w^t_i \Loss(\rsys^t_i(u,v), \feedback^t) \\
&\leq&
    a_\beta \min_i \sum_{t=1}^T \Loss(\rsys^t_i, \feedback^t)
               + c_\beta \ln N.
\end{eqnarray*}
\end{proof}

Of course, we are not interested in the loss of $\prefert$ (since it
is not an ordering), but rather in the performance of the actual
ordering $\rhoapprox^t$ computed by the learning algorithm.
Fortunately, the losses of these can be related using a kind of
triangle inequality.
Let
\begin{equation} \label{disagree:eqn}
 \disagree(\rho,\prefer) = \sum_{u,v:\rho(u)>\rho(v)} (1-\prefer(u,v)) ~ .  
\end{equation}

\begin{theorem}
For any $\prefer$, $\feedback$ and total order defined by an ordering
function $\rho$,
\begin{equation}
\Loss(\rsys_{\rho}, \feedback) \leq \frac{\disagree(\rho, \prefer)}{|\feedback|}
           + \Loss(\prefer, \feedback).
\label{eqn:triang}
\end{equation}
\end{theorem}

\begin{proof}
For $x,y\in [0,1]$, let us define $d(x,y)=x(1-y)+y(1-x)$.
We now show that $d$ satisfies the triangle inequality.
Let $x$, $y$ and $z$ be in $[0,1]$, and let $X$, $Y$ and $Z$ be
independent Bernoulli ($\{0,1\}$-valued) random variables with
probability of outcome $1$ equal to $x$, $y$ and $z$, respectively.
Then
\begin{eqnarray*}
d(x,z) &=& \Pr[X\neq Z] \\
&=& \Pr[  (X\not=Y \wedge Y=Z) ~\vee~ (X=Y \wedge Y\not=Z)]\\
&\leq& \Pr[X\neq Y \vee Y\neq Z] \\
&\leq& \Pr[X\neq Y] + \Pr[Y\neq Z] \\
&=& d(x,y) + d(y,z).
\end{eqnarray*}

For $[0,1]$-valued functions $f,g$ defined on $X\times X$, we next
define \[D(f,g)=\sum_{u,v: u\neq v} d(f(u,v), g(u,v)).\]
Clearly, $D$ also satisfies the triangle inequality.

Let $\chi_{\feedback}$ be the characteristic function of $\feedback$
so that $\chi_{\feedback}: X\times X\rightarrow \{0,1\}$ and
$\chi_{\feedback}(u,v) = 1$ if and only if $(u,v)\in \feedback$.
Then from the definition of $\Loss$ and $\disagree$, we have
\begin{eqnarray*}
|\feedback| \; \Loss(\rsys_{\rho}, \feedback) &=&
  D(\rsys_{\rho}, \chi_{\feedback}) \\
&\leq& D(\rsys_{\rho}, \prefer) + D(\prefer, \chi_{\feedback})\\
&=&  \disagree(\rho, \prefer)
           + |\feedback| \;\Loss(\prefer, \feedback).
\end{eqnarray*}
\end{proof}

Notice that the learning algorithm $\Hedge$ minimizes the second term on
the right hand side of Eq.~(\ref{eqn:triang}). Below, we consider
the problem of finding an ordering $\rho$ which minimizes the first term,
namely, $\disagree$.

%% ===================================================================

\section{Ordering Instances with a Preference Function}
\label{sec:combine}

\subsection{Measuring the Quality of an Ordering}

We now consider the complexity of finding a total order that agrees
best with a learned preference function.  To analyze this, we must
first quantify the notion of agreement between a preference function
$\prefer$ and an ordering. One natural notion is the following:  Let
$X$ be a set, $\prefer$ be a preference function, and let $\rho$ be a
total ordering of $\eset$, expressed again as an ordering function
({{\it i.e.}, $\rho(u)>\rho(v)$ if and only if $u$ is above $v$ in the
order). For the analysis of this section, it is convenient to use the
measure $\nagr(\rho,\prefer)$, which is defined to be the sum of
$\prefer(u,v)$ over all pairs $u,v$ such that $u$ is ranked above $v$
by $\rho$:
\begin{equation}
\nagr(\rho,\prefer) = \sum_{u,v:\rho(u)>\rho(v)} \prefer(u,v).
\label{agree:eqn}
\end{equation}
Clearly, $\nagr$ is a linear transformation of the measure
$\disagree$ introduced in Eq.~(\ref{disagree:eqn}), and hence
maximizing $\nagr$ is equivalent to minimizing $\disagree$.
This definition is also closely related to similarity metrics used
in decision theory and information
processing~\cite{KemenySnell62,Fishburn70,Roberts79,French89,Yao95}
(see the discussion in Sec.~\ref{related:sec}).

\subsection{Finding an Optimal Ordering is Hard}

Ideally one would like to find a $\rho$ that maximizes
$\nagr(\rho,\prefer)$.  The general optimization problem is of little
interest in our setting, since there are many constraints on the
preference function that are imposed by the learning algorithm. Using
the learning algorithm of Sec.~\ref{learn:sec}, for instance,
$\prefer$ will always be a linear combination of simpler functions.
However, the theorem below shows that this optimization problem is
NP-complete even if $\prefer$ is restricted to be a linear combination
of well-behaved preference functions.  In particular, the problem is
NP-complete even if all the primitive preference functions used in the
linear combination are rank orderings which map into a set $\oset$
with only three elements, one of which may or may not be
$\donno$. (Clearly, if $\oset$ consists of more than three elements
then the problem is still hard.)

\begin{theorem} \label{npc:thm}
The following decision problem is NP-complete for any set $\oset$ with
$|\oset|\geq{}3$:

\begin{minipage}[t]{5.7in}
{\tt Input:} A rational number $\kappa$;
a set $\eset$; a collection of $N$ ordering functions
$\ofun_i:\eset\rightarrow\oset$; and a preference function $\prefer$
defined as
\begin{equation}
\prefer(u,v) = \sum_{i=1}^N w_i\rsys_{\ofun_i}(u,v)
\label{prefdef:eqn}
\end{equation}
where $\pvec=(w_1,\ldots,w_N)$ is a rational weight vector in $[0,1]^N$
with $\sum_{i=1}^N \pveci = 1$.

% \noindent
{\tt Question:} Does there exist a total order $\rho$ such that
$\nagr(\rho,\prefer) \geq \kappa$?
\end{minipage}
\end{theorem}

\begin{proof}
The problem is clearly in NP since a nondeterministic algorithm can
guess a total order and check the weighted number of agreements in
polynomial time. 

To prove that the problem is NP-hard we reduce from
CYCLIC-ORDERING \cite{GalilMegido77,GJ}, defined as follows: ``Given
a set $A$ and a collection $C$ of ordered triples $(a,b,c)$ of
distinct elements from $A$, is there a one-to-one function $f: A
\rightarrow \{1,2,\ldots,|A|\}$ such that for each $(a,b,c) \in C$ we
have either $f(a)>f(b)>f(c)$ or $f(b)>f(c)>f(a)$ or
$f(c)>f(a)>f(b)$?''

Without loss of generality, $\oset$ is either $\{0,1,\donno\}$ or
$\{0,1,2\}$.
We first show that the problem of finding an optimal total order is
hard when $\oset=\{0,1,\donno\}$.  Given an instance of
CYCLIC-ORDERING, we let $\eset=A$. For each triplet $t=(a,b,c)$ we
will introduce three ordering functions $\ofun_{t,1}$, $\ofun_{t,2}$,
and $\ofun_{t,3}$, and define them so that
$\ofun_{t,1}(a)>\ofun_{t,1}(b)$, $\ofun_{t,2}(b)>\ofun_{t,2}(c)$, and
$\ofun_{t,3}(c)>\ofun_{t,3}(a)$.  To do this, we let $\ofun_{t,1}(a) =
\ofun_{t,2}(b) = \ofun_{t,3}(c) = 1$, $\ofun_{t,1}(b) = \ofun_{t,2}(c)
= \ofun_{t,3}(a) = 0$, and $\ofun_{t,i}(\cdot)=\donno$ in all other
cases.  We let the weight vector be uniform, so that
$w_{t,i}=\frac{1}{3|C|}$.
Let
\[\kappa = \frac{5}{3} + \frac{|A|(|A|-1)/2-3}{2}.\]

Define $\rsys_t(u,v)=\sum_{i=1}^{3}w_{t,i}\rsys_{\ofun_{t,i}}(u,v)$,
which is the contribution of these three functions to $\prefer(u,v)$.
Notice that for any triplet $t=(a,b,c) \in C$,
$\rsys_t(a,b)=\frac{2}{3|C|}$ whereas $\rsys_t(b,a)=\frac{1}{3|C|}$,
and similarly for $b,c$ and $c,a$.
In addition, for any pair $u,v\in A$ such that at least one of them does
not appear in $t$, we get that $\rsys_t(u,v) = \frac{1}{2|C|}$.
Since a total order $\rho$ can
satisfy at most two of the three conditions $\rho(a)>\rho(b)$,
$\rho(b)>\rho(c)$, and $\rho(c)>\rho(a)$, the largest possible
weighted number of agreements associated with this triple is exactly
$\kappa/|C|$.  

If the number of weighted
agreements is at least $\kappa$, it must be exactly
$\kappa$, by the argument above; and if there are exactly
$\kappa$ weighted agreements, then the total order must satisfy
{exactly\/} $2$ out of the possible $3$ relations for each three
elements that form a triplet from $C$. Thus, the constructed rank
ordering instance will be positive if and only if the original
CYCLIC-ORDERING instance is positive.

The case for $\oset=\{0,1,2\}$ uses a similar construction; however,
for each triplet $t=(a,b,c)$, we define six ordering functions,
$\ofun_{t,1}^j$, $\ofun_{t,2}^j$, and $\ofun_{t,3}^j$, where
$j\in\{0,1\}$. The basic idea here is to replace each $\ofun_{t,i}$
with two functions, $\ofun_{t,i}^0$ and $\ofun_{t,i}^1$, that agree on
the single ordering constraint associated with $\ofun_{t,i}$, but
disagree on all other orderings. For instance, we will define these
functions so that $\ofun_{t,1}^j(a)>\ofun_{t,1}^j(b)$ for $j=0$ and
$j=1$, but for all other pairs $u,v$, 
$\ofun_{t,1}^1(u)>\ofun_{t,1}^1(v)$ iff
$\ofun_{t,1}^0(v)>\ofun_{t,1}^0(u)$.  Averaging the two orderings
$\ofun_{t,1}^0$ and $\ofun_{t,1}^1$ 
will thus yield the same preference expressed by the original function
$\ofun_{t,1}$ ({\it i.e.}, a preference for $a>b$ only).

In more detail, we let $\ofun_{t,1}^j(a) = \ofun_{t,2}^j(b) =
\ofun_{t,3}^j(c) = 2 - j$, $\ofun_{t,1}^j(b) = \ofun_{t,2}^j(c) =
\ofun_{t,3}^j(a) = 1 - j$, and $\ofun_{t,i}^j(\cdot) = 2j$ in all
other cases. We again let the weight vector be uniform, so that
$w_{t,i}^j=\frac{1}{6|C|}$.
Similar to the first case, we define
$\rsys_t(u,v)=\sum_{i,j}w_{t,i}\,\rsys_{\ofun_{t,i}^j}(u,v)$.
It can be verified that $\rsys_t$ is identical to the $\rsys_t$
constructed in the first case.
Therefore, by the same argument,
the constructed rank ordering instance will be
positive if and only if the original CYCLIC-ORDERING instance is positive.
\end{proof}

\vspace{0.1cm}

Although this problem is hard when $|\oset|\geq 3$, the next theorem
shows that it becomes tractable for linear combinations of rank
orderings into a set $\oset$ of size two.  Of course, when
$|\oset|=2$, the rank orderings are really only binary
classifiers. The fact that this special case is tractable underscores
the fact that manipulating orderings (even relatively simple ones) can
be computationally more difficult than performing the corresponding
operations on binary classifiers.

\begin{theorem} \label{tractable:thm}
The following optimization problem is solvable in linear time:

% \noindent
\begin{minipage}[t]{5.7in}
{\tt Input:} A set $\eset$; a set $\oset$ with $|\oset|=2$;
a collection of $N$ ordering functions $\ofun_i:\eset\rightarrow\oset$;
and a preference function $\prefer$ defined by Eq.~(\ref{prefdef:eqn}).

% \noindent
{\tt Output:} A total order defined by an ordering function
$\rho$ which maximizes $\nagr(\rho,\prefer)$.
\end{minipage}
\end{theorem}
\begin{proof}
Assume without loss of generality that the two-element set $\oset$ is
$\{0,1\}$, and define $\rho(u) = \sum_i \pveci \ofun_i(u)$. We now
show that any total order\footnote{Notice that in
case of a tie, so that $\rho(u)=\rho(v)$ for distinct $u,v$, $\rho$
defines only a partial order. The theorem holds for any total order
which is consistent with this partial order, {\it i.e.}, for any
$\rho'$ so that $\rho(u)>\rho(v) \Rightarrow \rho'(u)>\rho'(v)$.}
consistent with $\rho$ maximizes $\nagr(\rho,\prefer)$.
Fix a pair $u,v\in X$ and let
\[
\vvec_{b_1 b_2} = \sum_{i \mbox{ s.t. }
	\ofun_i(u) = b_1 , \ofun_i(v)=b_2} \pveci ~ .
\]
We can now rewrite $\rho$ and $\prefer$ as
\[
\begin{array}{lclcclcl}
\rho(u) & = & \vvec_{10} + \vvec_{11} & &
\prefer(u,v) & = & \vvec_{10} + \half \vvec_{11} + \half \vvec_{00} ~~  \\
\rho(v) & = & \vvec_{01} + \vvec_{11} & &
\prefer(v,u) & = & \vvec_{01} + \half \vvec_{11} + \half \vvec_{00} ~ .
\end{array}
\]
Note that both $\rho(u)-\rho(v)$ and $\prefer(u,v)-\prefer(v,u)$ are
equal to $\vvec_{10}-\vvec_{01}$. Hence, if $\rho(u)>\rho(v)$ then
$\prefer(u,v)>\prefer(v,u)$. Therefore, for each pair $u,v\in X$, the
order defined by $\rho$ agrees on {\em all} pairs with the pairwise
preference defined by $\prefer$.
In other words, we have shown that
\begin{equation} \label{eqn:maxpref}
\nagr(\rho,\prefer) =
   \sum_{\{u,v\}} \max\{\prefer(u,v), \prefer(v,u)\}
\end{equation}
where the sum is over all unordered pairs.
Clearly, the right hand side of Eq.~(\ref{eqn:maxpref}) maximizes the
right hand side of Eq.~(\ref{agree:eqn}) since at most one of $(u,v)$
or $(v,u)$ can be included in the latter sum.
\end{proof}

\subsection{Finding an Approximately Optimal Ordering}

\begin{figure}[t]
\normalsize
\begin{tabbing}1234\=1234\=1234\=1234\=1234\=1234\=\kill
{\bf Algorithm Greedy-Order}\\
{\bf Inputs:} an instance set $X$; a preference function $\prefer$\\
{\bf Output:} an approximately optimal ordering function $\rhoapprox$\\
{\bf let} $V = X$\\
{\bf for} each $v\in{}V$ {\bf do}
 \( \pot(v) = \sum_{u\in{}V} \prefer(v,u) - \sum_{u\in{}V} \prefer(u,v)
   \)\\
{\bf while} $V$ is non-empty {\bf do}\\
\>{\bf let} $t = \arg\max_{u\in V} \pot(u)$\\
\>{\bf let} $\rhoapprox(t) = |V|$\\
\>$V = V - \{t\}$\\
\>{\bf for} each $v\in{}V$ {\bf do}
     \( \pot(v) = \pot(v) + \prefer(t,v)  - \prefer(v,t)
      \)\\
{\bf endwhile}
\end{tabbing}
\figline
\caption{The greedy ordering algorithm.
\label{gen_combine:alg}}
\end{figure}

Theorem~\ref{npc:thm} implies that we are unlikely to find an
efficient algorithm that finds the optimal total order for a weighted
combination of rank orderings. Fortunately, there do exist efficient
algorithms for finding an {\em approximately\/} optimal total
order. In fact, finding a good total order is closely related to the
problem of finding the minimum feedback arc set, for which there exist
good approximation algorithms; see, for instance, \cite{Shmoys97} and
the references therein.  However, the
algorithms that achieve the good approximation results for the minimum
feedback arc set problem are based on (or further approximate) a
linear-programming relaxation
\cite{Seymour95,EvenNaRaSc95,BergerShor97,EvenNaScSu98}
which is rather complex to implement and quite slow in practice.

We describe instead a simple greedy algorithm which is very simple to
implement. Figure~\ref{gen_combine:alg} summarizes the greedy
algorithm.  As we will shortly demonstrate, this algorithm produces a
good approximation to the best total order. 

The algorithm is easiest to describe by thinking of $\prefer$ as a
directed weighted graph, where initially, the set of vertices $V$ is
equal to the set of instances $X$, and each edge $\edgegen$ has weight
$\prefer(u,v)$. We assign to each vertex $v\in{}V$ a \trm{potential}
value $\pot(v)$, which is the weighted sum of the outgoing edges {\em
minus\/} the weighted sum of the ingoing edges. That is,
\begin{eqnarray*} \pot(v) & = &
	\sum_{u\in{}V} \prefer(v,u) - 
	\sum_{u\in{}V} \prefer(u,v) ~.
\end{eqnarray*}
The greedy algorithm then picks some node $t$ that has maximum
potential\footnote{Ties can be broken arbitrarily in case of two or
more nodes with the same potential.}, and assigns it a rank by setting
$\rhoapprox(t)=|V|$, effectively ordering it ahead of all the remaining
nodes. This node, together with all incident edges, is then deleted
from the graph, and the potential values $\pot$ of the remaining
vertices are updated appropriately. This process is repeated until the
graph is empty. Notice that nodes removed in subsequent iterations will
have progressively smaller and smaller ranks.

\begin{figure}[t]
\centerline{\psfig{figure=PS/rsys_greedy.eps,height=4.5cm}}
\caption{Behavior of the greedy ordering algorithm. The leftmost
graph is the original input. From this graph, node $b$ will be
assigned maximal rank and deleted, leading to the middle graph; from
this graph, node $d$ will deleted, leading to the rightmost graph.
In the rightmost graph, node $c$ will be ranked ahead of node $a$,
leading the total ordering $b>d>c>a$.
\label{rsysgreedy:fig}}
\end{figure}

As an example, consider the preference function defined by the
leftmost graph of Fig.~\ref{rsysgreedy:fig}. (This graph is identical
to the weighted combination of the two ordering functions from
Fig.~\ref{rsys:fig}.)  The initial potentials the algorithm assigns
are: $\pot(b)=2$, $\pot(d)=3/2$, $\pot(c)=-5/4$, and $\pot(a)=-9/4$.
Hence, $b$ has maximal potential. It is given a rank of $4$, and then
node $b$ and all incident edges are removed from the graph.

The result is the middle graph of Fig.~\ref{rsysgreedy:fig}.  After
deleting $b$, the potentials of the remaining nodes are updated:
$\pot(d) = 3/2$, $\pot(c) = -1/4$, and $\pot(a) = -5/4$.  Thus, $d$
will be assigned rank $|V|=3$ and removed from the graph, resulting
in the rightmost graph of Fig.~\ref{rsysgreedy:fig}.

After updating potentials again, $\pot(c)=1/2$ and $\pot(a)=-1/2$.
Now $c$ will be assigned rank $|V|=2$ and removed, resulting in a
graph containing the single node $a$, which will finally be assigned
the rank $|V|=1$.  The ordering produced by the greedy algorithm is
thus $b>d>c>a$.

The next theorem shows that this greedy algorithm comes within a
factor of two of optimal.

\begin{theorem} \label{thm:approx}
Let $\OPT({\prefer})$ be the weighted agreement achieved by an optimal
total order for the preference function $\prefer$, and let
$\APPROX({\prefer})$ be the weighted agreement achieved by the greedy
algorithm.  Then
\[ \APPROX({\prefer}) \geq \frac{1}{2}\OPT({\prefer}) ~ . \]
\end{theorem}

\begin{proof}
Consider the edges that are incident on the node $v_j$ which is
selected on the $j$-th repetition of the {\bf while} loop of
Figure~\ref{gen_combine:alg}. The ordering produced by the algorithm
will agree with all of the outgoing edges of $v_j$ and disagree with
all of the ingoing edges. Let $a_j$ be the sum of the weights of the
outgoing edges of $v_j$, and $d_j$ be the sum of the weights of the
ingoing edges.  Clearly \( \APPROX({\prefer}) \geq{} \sum_{j=1}^{|V|}
a_j \).  However, at every repetition, the total weight of all
incoming edges must equal the total weight of all outgoing edges. This
means that $\sum_{v\in{}V} \pot(v)=0$, and hence for the node
$v^\star$ that has maximal potential, $\pot(v^\star)\geq 0$.  Thus on
every repetition $j$, it must be that $a_j\geq{}d_j$, so we have that
\[ \OPT({\prefer}) \;\;\leq{}\;\; 
	\sum_{j=1}^{|V|} (a_j + d_j) 
	\;\;\leq{}\;\; \sum_{j=1}^{|V|} (a_j+a_j)
	\;\;\leq{}\;\; 2\cdot \APPROX({\prefer}).
\]
The first inequality holds because $\OPT({\prefer})$ can at best include
every edge in the graph, and since every edge is removed exactly once,
each edge must contribute to some $a_j$ or some $d_j$.
\end{proof}

\begin{figure}[t]
\centerline{\psfig{figure=PS/bad_node.eps,height=5.0cm}}
\caption{An example of a graph (left) for which the node-based greedy
algorithm achieves an approximation factor of $\half$ by constructing
the partial order on the right.}
\label{bad_node:fig}
\end{figure}

In passing, we note that there are other natural greedy algorithms that
do not achieve good approximations. Consider, for example, an
algorithm that starts from a graph consisting of all the nodes but
with no edges, and iteratively adds the highest weighted edge in the
graph, while avoiding cycles. It can be shown that this algorithm can
produce a very poor partial order, given an adversarially chosen
graph; there are cases where the optimal total order achieves a
multiplicative factor of $O(|V|)$ more weighted agreements than
this ``edge-based'' greedy algorithm.

\subsection{Improvements to the Greedy Algorithm}

The approximation factor of two given in Theorem~\ref{thm:approx} is
tight. That is, there exist problems for which the greedy algorithm
approximation is worse than the optimal solution by a factor arbitrarily
close to two. Consider the graph shown on the left-hand side of
Fig.~\ref{bad_node:fig}. An optimal total order ranks the instances
according to their position in the figure, left to right, breaking
ties randomly, and achieves $\OPT(\prefer)=2k+2$ weighted
agreements. However, the greedy algorithm picks the node labeled $k+1$
first and orders all the remaining nodes randomly, achieving as few
as $\APPROX(\prefer)=k+2$ agreements. For large $k$, the ratio
$\APPROX(\prefer)/\OPT(\prefer)$ approaches $\half$.

For graph of Figure~\ref{bad_node:fig}, there is another simple
algorithm which produces an optimal ordering: since the graph is
already a partial order, picking any total order consistent with this
partial order gives an optimal result.
To cope with problems such as the one of
Figure~\ref{bad_node:fig}, we devised an improvement to the greedy
algorithm which combines a greedy method with topological
sorting. The aim of the improvement is to find better approximations
for graphs which are composed of many strongly connected components.

\begin{figure}[t]
{\bf Algorithm SCC-Greedy-Order} \newline
{\bf Inputs:} an instance set $X$; a preference function $\prefer$\\
{\bf Output:} an approximately optimal ordering function $\rhoapprox$\\ \\
{\bf Define} ~
\( \prefer^\prime(u,v) = \max\{\prefer(u,v) - \prefer(v,u),\; 0\} ~ .\) \\
{\bf Find} strongly connected components $U_1,\ldots,U_k$ of the
	graph $G=(V,E)$ where
	\[ V=X \mbox { and } E = \{(u,v)\mid\prefer^\prime(u,v) > 0\} ~ . \]
{\bf Order} the strongly connected components in any way consistent
with the partial order $<_{\rm scc}$:
\[ U<_{\rm scc}U' \mbox{~iff~} \exists u\in{}U,u'\in{}U' :
	\mbox{$(u,u')\in E$}
\]
{\bf Use} algorithm {\bf Greedy-Order} or full enumeration to order the
instances within each component $U_i$ according to $\prefer^\prime$. \\
\figline
\caption{The improved greedy ordering algorithm.}
\label{sccgreedy:alg}
\end{figure}

As before, the modified algorithm is easiest to describe by thinking
of $\prefer$ as a weighted directed graph.  Recall that for each pair of 
nodes $u$ and $v$, there exist two edges: one from $u$ to $v$ with
weight $\prefer(u,v)$ and one from $v$ to $u$ with weight
$\prefer(v,u)$. In the modified greedy algorithm we will pre-process
the graph. For each pair of nodes, we remove the edge with the smaller
weight and set the weight of the other edge to be
\[\mid{\prefer(v,u) - \prefer(u,v)}\mid ~ . \]
For the special case where
$\prefer(v,u)=\prefer(u,v)=\half$, we remove both edges. In the reduced
graph, there is at most one directed edge between each pair of nodes.
Note that the greedy algorithm would behave identically on the transformed
graph since it is based on the weighted {\em differences} between the
incoming and outgoing edges. 

We next find the strongly connected components\footnote{Two nodes $u$
and $v$ are in the same strongly connected component iff there are
directed paths from $u$ to $v$ and from $v$ to $u$.} of the reduced
graph, ignoring (for now) the weights.  One can now split the edges of
the reduced graph into two classes: \trm{inter-component} edges
connect nodes $u$ and $v$, where $u$ and $v$ are in different strongly
connected components; and \trm{intra-component} edges connect nodes
$u$ and $v$ from the same strongly connected component.  It is
straightforward to verify that any optimal order agrees with all the
inter-component edges. Put another way, if there is an edge from
node $u$ to node $v$ of two different connected components in the
reduced graph, then $\rho(u)>\rho(v)$ for any optimal total order
$\rho$.

The first step of the improved algorithm is thus to totally order the
strongly connected components in some way consistent with the partial
order defined by the inter-component edges.  More precisely, we pick a
total ordering for the components consistent with the partial order
$<_{\rm scc}$, defined as follows: for components $U$ and $U'$,
$U<_{\rm scc}U'$ iff there is an edge from some node $u\in{}U$ to
some node $u'\in{}U'$ in the reduced graph. 

We next order the nodes within each strongly connected component, thus
providing a total order of all nodes. Here the greedy algorithm can be
used.  As an alternative, in cases where a component contains only a
few elements (say at most five), one can find the optimal order
between the elements of the component by a brute-force approach, {\it
i.e.}, by full enumeration of all permutations.

\begin{figure}[tp]
\centerline{\hbox{
	{\psfig{figure=PS/scc1.eps,height=3.5cm}}
	\hspace{0.2cm}
	{\Huge\bf $\Rightarrow$}
	\hspace{0.2cm}
	{\psfig{figure=PS/scc2.eps,height=3.5cm}}
	\hspace{0.2cm}
	{\Huge\bf $\Rightarrow$}
	\hspace{0.2cm}
	{\psfig{figure=PS/scc3.eps,height=3.5cm}}}}
	\vspace{0.5cm}
\centerline{\psfig{figure=PS/scc4.eps,height=1.4cm}}
\caption{An illustration of the approximation algorithm for finding
a total order from a weighted combination of ordering functions. The
original graph (top left) is reduced by removing at least one edge
for each edge-pair $(u,v)$ and $(v,u)$ (middle). The strongly connected
components are then found (right). Finally, an ordering is found within
each strongly connected component which yield the order $b>c>d>a$ (bottom).}
\label{impapprox:fig}
\end{figure}

The improved algorithm is summarized in Figure~\ref{sccgreedy:alg} and
illustrated in Figure~\ref{impapprox:fig}. There are four elements in
Figure~\ref{impapprox:fig} which constitute two strongly connected
components in the reduced graph ($\{b\}$ and $\{a,c,d\}$). Therefore,
$b$ is assigned the top rank and ranked above $a$, $c$ and $d$.  If
the brute-force algorithm were used to order the components, then we
would check all $3!$ permutations between $a$, $c$ and $d$ and output
the total order $b>c>d>a$, which is the optimal order in this toy
example.

In the worst case, the reduced graph contains only a single strongly
connected component. In this case, the improved algorithm generates
the same ordering as the greedy algorithm.  However, in the
experiments on metasearch problems described in
Sec.~\ref{exper:sec}, many of the strongly connected components are
small; the average size of a strongly connected component is less than
five.  In cases such as these, the improved algorithm will often
improve on the simple greedy algorithm.

\subsection{Experiments with the Ordering Algorithms}

Ideally, each algorithm would be evaluated by determining how closely
it approximates the optimal ordering on large, realistic problems.
Unfortunately, finding the optimal ordering for large graphs is
impractical. We thus performed two sets of experiments with the
ordering algorithms described above.  In the first set of experiments,
we evaluated the algorithms on small graphs---specifically, graphs for
which the optimal ordering could be feasibly found with brute-force
enumeration.  In these experiments, we measure the ``goodness'' of the
resulting orderings relative to the optimal ordering.  In the second
set of experiments, we evaluated the algorithms on large graphs for
which the optimal orderings are unknown.  In these experiments, we
compute a ``goodness'' measure which depends on the total weight of
all edges, rather than the optimal ordering.

In addition to the simple greedy algorithm and its improvement, we
also considered the following simple randomized algorithm: pick a
permutation at random, and then output the better of that permutation
and its reverse.  It can be easily shown that this algorithm achieves
the same approximation bound on expected performance as the greedy
algorithm.  (Briefly, one of the two permutations must agree with at
least half of the weighted edges in the graph.)  The random algorithm
can be improved by repeating the process, {\it i.e.}, examining many
random permutations and their reverses, and choosing the permutation
that achieves the largest number of weighted agreements.  

In a first set of experiments, we compared the performance of the
greedy approximation algorithm, the improved algorithm which first
finds strongly connected components, and the randomized algorithm on
graphs of nine or fewer elements.
For each number of elements, we generated $10,\!000$ random graphs by
choosing $\prefer(u,v)$ uniformly at random, and setting
$\prefer(v,u)$ to $1-\prefer(u,v)$. For the randomized algorithm, we
evaluated $10 n$ random permutations (and their reverses) where 
$n$ is the number of instances (nodes). To have a fair comparison between
the different algorithms on the smaller graphs, we always used the
greedy algorithm (rather than a brute-force algorithm) to order the
elements of each strongly connected component of a graph.

To evaluate the algorithms, we examined the reduced graph and
calculated the average ratio of the weights of the edges chosen by the
approximation algorithm to the weights of the edges that were chosen by
the optimal order. More precisely, let $\rho$ be the optimal order and
$\hat{\rho}$ be an order chosen by an approximation algorithm.  Then
for each random graph, we calculated
\[
{
\displaystyle
\sum_{\displaystyle u,v: \hat{\rho}(u) > \hat{\rho}(v)}
	\max\{\prefer(u,v)-\prefer(v,u), 0\}
	\over
\displaystyle
\sum_{\displaystyle u,v: {\rho}(u) > {\rho}(v)}
	\max\{\prefer(u,v)-\prefer(v,u), 0\}
} ~ .
\]
If this measure is 0.9, for instance, then the total weight of the
edges in the total order picked by the approximation algorithm is 90\%
of the corresponding figure for the optimal algorithm.

\begin{figure}[tp]
\centerline{\hbox{
	\psfig{figure=PS/approx.ps,width=0.48\textwidth}
	\hspace{0.5cm}
	\psfig{figure=PS/runt.ps,width=0.48\textwidth}}}
\caption{Comparison of goodness (left) and the running time (right)
of the approximations achieved by the greedy algorithms and the randomized
algorithm as a function of the number of ranked elements
for random preference functions with $3$ through $9$ elements.}
\label{approx_emp:fig}
\end{figure}

\begin{figure}[tp]
\centerline{\hbox{
	\psfig{figure=PS/approx_large.ps,width=0.48\textwidth}
	\hspace{0.5cm}
	\psfig{figure=PS/runt_large.ps,width=0.48\textwidth}}}
\caption{Comparison of goodness (left) and the running time (right)
of the approximations achieved by the greedy algorithms and the randomized
algorithm as a function of the number of ranked elements
for random preference functions with $3$ through $30$ elements.
Note that the graphs for Greedy and SCC+Greedy coincide for
most of the points.}
\label{approx_emp_large:fig}
\end{figure}

We averaged the above ratios over all random graphs of the same
size. The results are shown on the left hand side of
Figure~\ref{approx_emp:fig}.  On the right hand side of the
figure, we show the average running time for each
of the algorithms as a function of the number of elements. When the
number of ranked elements is more than five, the greedy algorithms
outperform the randomized algorithm, while their running time is much
smaller. Thus, if a full enumeration had been used to find the optimal
order of small strongly connected components, the approximation would
have been consistently better than the randomized algorithm.

We note that the greedy algorithm also generally performs better on
average than the lower bound given in Theorem~\ref{thm:approx}. In
fact, combining the greedy algorithm with pre-partitioning of the graph
into strongly connected components often yields the optimal order.

In the second set of experiments, we measured performance and running
time for larger random graphs. Since for large graphs we cannot find
the optimal solution by brute-force enumeration, we use as a ``goodness''
measure the ratio of the weights of the edges that were left in the reduced graph
after applying an approximation algorithm to the {\em total} weight of
edges in the graph. That is, for each random graph we calculated
\[
{
\displaystyle
\sum_{\displaystyle u,v: \hat{\rho}(u) > \hat{\rho}(v)}
	\max\{\prefer(u,v)-\prefer(v,u), 0\}
	\over
	\displaystyle
	\sum_{\displaystyle u,v}
	\max\{\prefer(u,v)-\prefer(v,u), 0\}
} ~ .
\]
We ran the three algorithms with the same parameters as above ({\it i.e.},
$10,\!000$ random graphs). The results are given in
Figure~\ref{approx_emp_large:fig}. The advantage of the greedy algorithms
over the randomized algorithm is even more apparent on these larger problems.
Note also that for large graphs the performance of the two greedy
algorithms is indistinguishable. This is mainly due to the fact that large
{\em random} graphs are strongly connected with high probability.

To summarize the experiments, when there are six or more elements the
greedy algorithm clearly outperforms the randomized algorithm even if
many randomly chosen permutations are examined. Furthermore, the
improved algorithm which first finds the strongly connected components
outperforms the randomized algorithm for all graph sizes.  In practice
the improved greedy algorithm achieves very good
approximations---within about 5 percent of optimal, for the cases in
which optimal graphs can be feasibly found.

%% ===================================================================

\section{Experimental Results for Metasearch} \label{exper:sec}

So far, we have described a method for learning a preference function,
and a means of converting a preference function into an ordering of
new instances. We will now present some experimental results in
learning to order. In particular, we will describe results on learning
to combine the orderings of several web ``search experts'' using the
algorithm of Figure~\ref{hedge4rank:alg} to learn a preference
function, and the simple greedy algorithm to order instances using the
learned preference function.  The goals of these experiments are to
illustrate the type of problems that can be solved with our method; to
empirically evaluate the learning method; to evaluate the ordering
algorithm on large, non-random graphs, such as might arise in a
realistic application; and to confirm the theoretical results of the
preceding sections.  We thus restrict ourselves to comparing the
learned orderings to individual search experts, as is suggested by
Theorem~\ref{thm:experts}, rather than attempt to compare this
application of learning-to-order with previous experimental techniques
for metasearch, e.g.,
\cite{LochbaumIPM89,KantorTREC94,BoyanAAAIWS96,BartellSIGIR94}.

We note that this metasearch problem exhibits several properties that
suggest a general approach such as ours. For instance, approaches that
learn to combine similarity scores are not applicable, since the
similarity scores of web search engines are often unavailable. In the
experiments presented here, the learning algorithm was provided with
ordered lists for each search engine without any associated scores. To
further demonstrate the merits of our approach, we also describe
experiments with partial feedback---that is, with preference judgments
that are less informative than the relevance judgments more typically
used in improving search engines.

\subsection{Test Problems and Encoding}

We chose to simulate the problem of learning a domain-specific search
engine---{\it i.e.}, an engine that searches for pages of a
particular, narrow type.  Ahoy!~\cite{Ahoy} is one
instance of such a domain-specific search engine. As test cases, we
picked two problems: retrieving the home pages of machine learning
researchers (ML), and retrieving the home pages of universities
(UNIV).  To obtain sample queries, we obtained a listing of machine
learning researchers, identified by name and affiliated institution,
together with their home pages,\footnote{From
http://www.aic.nrl.navy.mil/$\sim$aha/research/machine-learning.html,
a list maintained by David Aha.}  and a similar list for universities,
identified by name and (sometimes) geographical
location.\footnote{From Yahoo!}  Each entry on a list was viewed as a
query, with the associated URL the sole relevant web page.

\begin{table}[t]
\begin{small}
\begin{center}
\begin{tabular}{|l|l|}
\hline
ML Search Experts	& UNIV Search Experts\\
\hline
NAME					& NAME                            \\
``NAME''				& ``NAME''                          \\
title:``NAME''				& ``NAME'' PLACE                    \\
NAME +LASTNAME title:``home page''	& title:NAME                      \\
NAME +LASTNAME title:homepage 		& title:``NAME''                    \\
NAME +LASTNAME machine learning		& title:``NAME'' PLACE              \\
NAME +LASTNAME ``machine learning''	& NAME title:``home page''          \\
NAME +LASTNAME case based reasoning	& NAME title:``homepage''           \\
NAME +LASTNAME ``case based reasoning''	& NAME welcome                    \\
NAME +LASTNAME PLACE			& NAME url:index.html             \\
NAME +LASTNAME ``PLACE''		& NAME url:home.html              \\
NAME +LASTNAME url:index.html		& ``NAME'' title:``home page''        \\
NAME +LASTNAME url:home.html		& ``NAME'' title:``homepage''         \\
NAME +LASTNAME url:\verb|~|*LASTNAME*	& ``NAME'' welcome                  \\
NAME +LASTNAME url:\verb|~|LASTNAME	& ``NAME'' url:index.html           \\
NAME +LASTNAME url:LASTNAME		& ``NAME'' url:home.html            \\
					& ``NAME'' PLACE title:``home page''  \\
					& ``NAME'' PLACE title:``homepage''   \\
					& ``NAME'' PLACE welcome            \\
					& ``NAME'' PLACE url:index.html     \\
					& ``NAME'' PLACE url:home.html \\ \hline
\end{tabular}
\end{center}
\end{small}
\caption{Search (and ranking) experts used in the metasearch experiments.
In the associated queries, NAME is replaced with the person's (or
university's) full name, LASTNAME with the person's last name, and
PLACE is replaced with the person's affiliation (or university's
location). Sequences of words enclosed in quotes must appear as a
phrase, and terms prefixed by {\tt title:} and {\tt url:} must appear
in that part of the web page. Words prefixed by a ``+'' must appear in
the web page; other words may or may not appear.}
\label{expert:tab}
\end{table}

We then constructed a series of special-purpose ``search experts'' for
each domain.  These were implemented as query expansion methods which
converted a name/affiliation pair (or a name/location pair) to a
likely-seeming Altavista query.  For example, one expert for the UNIV
domain searched for the university name appearing as a phrase,
together with the phrase ``home page'' in the title; another expert
for the ML domain searched for all the words in the person's name plus
the words ``machine'' and ``learning,'' and further enforces a strict
requirement that the person's last name appear.  Overall, we defined 16
search experts for the ML domain and 22 for the UNIV domain; these are
summarized in Table~\ref{expert:tab}. Each search expert returned the
top 30 ranked web pages.  In the ML domain, there were 210 searches for
which at least one search expert returned the named home page; for the
UNIV domain, there were 290 such searches.  The task of the learning
system is to find an appropriate way of combining the output of these
search experts.

To give a more precise description of the search experts,
for each query $t$, we first constructed the set $\eset^t$ consisting
of all web pages returned by all of the expanded queries defined by
the search experts.  Next, each search expert $i$ was represented as a
preference function $\rsys^t_i$.  We chose these preference functions
to be rank orderings defined with respect to an ordering function
$\ofun^t_i$ in the natural way: we assigned a rank of $\ofun^t_i=30$
to the first listed page, $\ofun^t_i=29$ to the second-listed page, and
so on, finally assigning a rank of $\ofun^t_i=0$ to every page not
retrieved in the top 30 by the expanded query associated with expert $i$.

To encode feedback, we considered two schemes.  In the first, we
simulated complete relevance feedback---that is, for each query, we
constructed feedback in which the sole relevant page was preferred to
all other pages.  In the second, we simulated the sort of feedback
that could be collected from ``click data''---{\it i.e.}, from
observing a user's interactions with a metasearch system.  For each
query, after presenting a ranked list of pages, we noted the rank of
the one relevant web page.  We then constructed a feedback ranking in
which the relevant page is preferred to all preceding pages.  This
would correspond to observing which link the user actually followed,
and making the assumption that this link was preferred to previous
links.

It should be emphasized that both of these forms of feedback are
simulated, and contain less noise than would be expected from real
user data. In reality some fraction of the relevance feedback would be
missing or erroneous, and some fraction of click data would not
satisfy the assumption stated above.

\subsection{Evaluation and Results}

To evaluate the expected performance of a fully-trained system on
novel queries in this domain, we employed leave-one-out testing.  For
each query $t$, we trained the learning system on all the other
queries, and then recorded the rank of the learned system on query
$t$.  For complete relevance feedback, this rank is invariant of the
ordering of the training examples, but for the ``click data''
feedback, it is not; the feedback collected at each stage depends on
the behavior of the partially learned system, which in turn depends on
the previous training examples. Thus for click data training, we
trained on 100 randomly chosen permutations of the training data and
recorded the median rank for $t$.

\subsubsection{Performance Relative to Individual Experts}

The theoretical results provide a guarantee of performance relative to
the performance of the best individual search (ranking) expert. It is
therefore natural to consider comparing the performance of the learned
system to the best of the individual experts. However, for each search
expert, only the top 30 ranked web pages for a query are known; if the
single relevant page for a query is not among these top 30, then it is
impossible to compute any natural measures of performance for this
query. This complicates any comparison of the learned system to the
individual search experts.

However, in spite of the incomplete information about the performance
of the search experts, it is usually possible to tell if the learned
system ranks a web page higher than a particular expert.\footnote{The
only time this cannot be determined is when neither the learned system
nor the expert ranks the relevant web pages in the top 30, a case of
little practical interest.} Motivated by this, we performed a sign
test: we compared the rank of the learning systems to the rank given
by each search expert, checking to see whether this rank was lower,
and discarding queries for which this comparison was impossible.  We
then used a normal approximation to the binomial distribution to test
the following two null hypotheses (where the probability is taken over
the distribution from which the queries are drawn):
\begin{description}
\item[H1.] With probability at least 0.5, the search expert performs better
than the learning system ({\it i.e.}, gives a lower rank to the relevant
page than the learning system does.)
\item[H2.] With probability at least 0.5, the search expert performs
no worse than the learning system ({\it i.e.}, gives an equal or lower rank
to the relevant page.)
\end{description}

In training, we explored learning rates in the range $[0.001,0.999]$.
For complete feedback in the ML domain, hypothesis H1 can be
rejected with high confidence ($p>0.999$) for every search expert and
every learning rate $0.01\leq{}\beta{}\leq{}0.99$.  The same holds in
the UNIV domain for all learning rates $0.02\leq{}\beta{}\leq{}0.99$.
The results for click data training are nearly as strong, except that
2 of the 22 search experts in the UNIV domain show a greater
sensitivity to the learning rate: for these engines, H1 can only be
rejected with high confidence for $0.3\leq{}\beta\leq{}0.6$.  To
summarize, with high confidence, in both domains, the learned ranking
system is no worse than any individual search expert for moderate
values of $\beta$.

Hypothesis H2 is more stringent since it can be rejected only if we
are sure that the learned system is strictly {\em better\/} than the
expert.  With complete feedback in the ML domain and
$0.3\leq{}\beta{}\leq{}0.8$, hypothesis H2 can be rejected with
confidence $p>0.999$ for 14 of the 16 search experts. For the
remaining two experts the learned system does perform better more
often, but the difference is not significant. In the UNIV domain, the
results are similar. For $0.2\leq{}\beta\leq{}0.99$, hypothesis H2 can
be rejected with confidence $p>0.999$ for 21 of the 22 search experts,
and the learned engine tends to perform better than the single
remaining expert.  

Again, the results for click data training are only
slightly weaker.  In the ML domain, hypothesis H2 can be rejected for
all but three experts for all but the most extreme learning rates; in
the UNIV domain, hypothesis H2 can be rejected for all but two experts
for $0.4\leq{}\beta\leq{}0.6$.  For the remaining experts and learning
rates the differences are not statistically significant; however, it
is not always the case that the learned engine tends to perform
better.

To summarize the experiments, for moderate values of $\beta$ the
learned system is, with high confidence, strictly better than most of
the search experts in both domains, and never significantly worse than
any expert.  When trained with full relevance judgments, the learned
system performs better on average than any individual expert.

\subsubsection{Other Performance Measures}

\begin{figure}[tph]
\centerline{\vbox{
		\psfig{figure=PS/ML-topk.ps,height=0.29\textheight}
		\vspace{0.5cm}
		\psfig{figure=PS/Univ-topk.ps,height=0.29\textheight}
		\vspace{0.2cm}
		\psfig{figure=PS/learn_rate_ml.ps,height=0.29\textheight}}}
\caption{Top and middle: Performance of the learned system versus
individual experts for two different domains. Bottom: the percentage
of time the relevant web page was in the top-$k$ list for $k=1$,$4$,
and $8$.}
\label{topk:fig}
\end{figure}

We measured the number of queries for which the correct web page was
in the top $k$ ranked pages, for various values of $k$.  These results
are shown in Figure~\ref{topk:fig}.  Here the lines show the
performance of the learned systems (with $\beta=0.5$, a generally
favorable learning rate) and the points correspond to the individual
experts.  In most cases, the learned system closely tracks the
performance of the best expert at every value of $k$.  This is
especially interesting since no single expert is best at all values of
$k$.

The final graph in this figure investigates the sensitivity of this
measure to the learning rate $\beta$. As a representative
illustration, we varied $\beta$ in the ML domain and plotted the
top-$k$ performance of the system learned from complete feedback for
three values of $k$.  Note that performance is roughly comparable over
a wide range of values for $\beta$. 

Another plausible measure of performance is the average rank of the
(single) relevant web page.  We computed an approximation to average
rank by artificially assigning a rank of 31 to every page that was
either unranked, or ranked above rank 30.  (The latter case is to be
fair to the learned system, which is the only one for which a rank
greater than 30 is possible.) A summary of these results for
$\beta=0.5$ is given in Table~\ref{res:table}, together with some
additional data on top-$k$ performance.  In the table, we give the
top-$k$ performance for three values of $k$, and average rank for
several ranking systems: the two learned systems; the naive query,
{\it i.e.}, the person or university's name; and the single search
expert that performed best with respect to each performance
measure. Note that not all of these experts are distinct since several
experts scored the best on more than one measure.  

The table illustrates the robustness of the learned systems, which are
nearly always competitive with the best expert for every performance
measure listed. The only exception to this is that the system trained
on click data trails the best expert in top-$k$ performance for small
values of $k$.  It is also worth noting that in both domains, the
naive query (simply the person or university's name) is not very
effective: even with the weaker click data feedback, the learned
system achieves a 36\% decrease in average rank over the naive query
in the ML domain, and a 46\% decrease in the UNIV domain.


\begin{table}[t]
{\footnotesize
\begin{center}
\begin{tabular}{|l|cccc|cccc|} \hline
& \multicolumn{4}{|c|}{ML Domain} & \multicolumn{4}{|c|}{University Domain} \\
& Top 1 & Top 10 & Top 30 & Avg Rank & Top 1 & Top 10 & Top 30 & Avg Rank\\ \hline
Learned (Full Feed.) &  %r5
114 & {\bf 185} & {\bf 198} & {\bf 4.9} & 111 & 225 & 253 & {\bf 7.8} \\
Learned (Click Data) & %r5
 93 & {\bf 185} & {\bf 198} & {\bf 4.9} &  87 & {\bf 229} & {\bf 259} & {\bf 7.8} \\ 
\hline
Naive & %e11ml/e11univ
89 & 165 & 176 & 7.7 & 79 & 157 & 191 & 14.4 \\
\hline
Best (Top 1) & %e20ml/e27univ
{\bf 119} & 170 & 184 & 6.7 & {\bf 112} & 221 & 247 & 8.2\\
Best (Top 10) & %e16ml/e22univ
114 & {182} & 190 & 5.3 & 111 & { 223} & 249 & 8.0\\
Best (Top 30) & %e17ml/e22univ
 97 & 181 & {194} & 5.6 & 111 & 223 & { 249} & 8.0\\
Best (Avg Rank) & %e16ml/e22univ
114 & 182 & 190 & {5.3} & 111 & 223 & 249 & { 8.0}\\
\hline
\end{tabular}
\caption{Comparison of learned systems and individual search queries.
\label{res:table}}
\end{center}}
\end{table}

To summarize the experiments, on these domains the learned system not
only performs much better than naive search strategies, but also
consistently performs at least as well as, and perhaps slightly better
than, any single domain-specific search expert.  This observation holds
regardless of the performance metric considered; for nearly every
metric we computed, the learned system always equals, and usually
exceeds, the performance of the search expert that is best for that
metric.  Finally, the performance of the learned system is almost as
good with the weaker ``click data'' training as with complete relevance
feedback.

%% ===================================================================

\section{Related Work} \label{related:sec}

Problems that involve ordering and ranking have been investigated in
various fields such as decision theory, the social sciences, information
retrieval and mathematical economics~%
\cite{Black58,KemenySnell62,Cooper68,Fishburn70,Roberts79,%
SaltonMc83,French89,Yao95}.
Among the wealth of literature on the subject, the closest to ours
appears to be the work of Kemeny and Snell~\citeyear{KemenySnell62} which
was extended by Yao~\citeyear{Yao95} and used by Balabanov{\'\i}c and
Shoham~\citeyear{BalaSh97} in their FAB collaborative filtering system.
These works use a similar notion of ordering functions and feedback;
however, they assume that both the ordering functions and the feedback are
complete and transitive. Hence, it is not possible to leave elements
unranked, or to have inconsistent feedback which violates the
transitivity requirements. It is therefore difficult to combine and
fuse inconsistent and incomplete orderings in the Kemeny and Snell
model.

There are also several related intractability results. Most of them
are concerned with the difficulty in reaching consensus in voting
systems based on preference ordering. Specifically,
Bartholdi, Tovey and Trick~\citeyear{BartholdiToTr89}
study the problem of finding a winner in an
election when the preferences of all voters are irreflexive,
antisymmetric, transitive, and complete. Thus, their
setting is more restrictive than ours. They study two similar schemes
to decide on a winner of an election.  The first was invented by
Dodgson~\citeyear{Carroll} (better known by his pen name, Lewis
Carroll) and the second is due to Kemeny~\citeyear{Kemeny59}. For both
models, they show that the problem of finding a winner in an election
is NP-hard. Among these two models, the one suggested by Kemeny is the
closest to ours. However, as mentioned above, this model is more
restrictive as it does not allow voters to abstain (preferences are
required to be complete) or to be inconsistent (all preferences are transitive).

As illustrated by the experiments, the problem of learning to rank is
closely related to the problem of combining the results of different
search engines. Many methods for this have been proposed by the
information retrieval community, and many of these are adaptive, using
relevance judgments to make an appropriate choice of parameters.
However, generally, rankings are combined by combining the scores that
were used to rank documents \cite{LochbaumIPM89,KantorTREC94}. It is
also frequently assumed that other properties of the objects
(documents) to be ranked are available, such as word frequencies.  In
contrast, in our experiments, instances are atomic entities with no
associated properties except for their position in various
rank-orderings. Similarly, we make minimal assumptions about the
rank-orderings---in particular, we do not assume scores are available.
Our methods are thus applicable to a broader class of ranking
problems.

General optimization methods have also been adopted to adjust
parameters of an IR system so as to improve agreement with a set of
user-given preference judgments. For instance, Boyan, Freitag, and
Joachims~\citeyear{BoyanAAAIWS96} use simulated annealing to improve
agreement with ``click data,'' and Bartell, Cottrell and Belew
\citeyear{BartellSIGIR94} use conjugate gradient descent to choose
parameters for a linear combination of scoring functions, each
associated with a different search expert. Typically, such approaches
offer few guarantees of efficiency, optimality, or generalization
performance.

Another related task is \trm{collection fusion}.  Here, several searches
are executed on disjoint subsets of a large collection, and the
results are combined.  Several approaches to this problem that do not
rely on combining ranking scores have been described
\cite{TowellML95,VoorheesSIGIR94}. However, although the
problem is superficially similar to the one presented here, the
assumption that the
different search engines index {\em disjoint\/} sets of documents
actually makes the problem quite different.  In particular, since it
is impossible for two engines to give different relative orderings to
the same pair of documents, combining the rankings can be done
relatively easily.

Etzioni~et~al.~\citeyear{EtzioniFOCS96} formally considered another
aspect of metasearch---the task of optimally combining information
sources with associated costs and time delays.  Our formal results are
disjoint from theirs, as they assume that every query has a single
recognizable correct answer, rendering ordering issues
unimportant.

There are many other applications in machine learning, reinforcement
learning, neural networks, and collaborative filtering that employ
ranking and preferences, e.g.,~%
\cite{UtgoffSaxena87,UtgoffClouse91,Caruna96,ResnickVarian97},
While our work is not directly
relevant, it might be possible to use the framework suggested in this
paper in similar settings. This is one of our future research goals.

Finally, we would like to note that the framework and algorithms
presented in this paper can be extended in several ways. Our current
research focuses on efficient {batch} algorithms for combining
preference functions, and on using restricted ranking experts for
which the problem of finding an optimal total ordering can be solved
in polyomial time~\cite{FreundIyScSi98}.

%% ===================================================================

\section{Conclusions}

In many applications, it is desirable to order rather than
classify instances.  We investigated a two-stage approach to learning
to order in which one first learns a preference function by
conventional means, and then orders a new set of instances by
finding the total ordering that best approximates the preference
function.  The preference function that is learned is a binary
function $\prefer(u,v)$, which returns a measure of confidence
reflecting how likely it is that $u$ is preferred to $v$.  This is
learned from a set of ``experts'' which suggest specific orderings,
and from user feedback in the form of assertions of the form ``$u$ should
be preferred to $v$''.

We have presented two sets of results on this problem.  First, we
presented an online learning algorithm for learning a weighted
combination of ranking experts which is based on an adaptation of
Freund and Schapire's $\Hedge$ algorithm.  Second, we explored the
complexity of the problem of finding a total ordering that agrees best
with a preference function.  We showed that this problem is
NP-complete even in a highly restrictive case, namely, preference
predicates that are linear combinations of a certain class of
well-behaved ``experts'' called rank orderings.  However, we also
showed that for any preference predicate, there is a greedy algorithm
that always obtains a total ordering that is within a factor of two of
optimal. We also presented an algorithm that first divides the set of
instances into strongly connected components and then uses the greedy
algorithm (or full enumeration, for small components) to find an
approximately good order within large strongly connected
components. We found that this approximation algorithm works very well
in practice and often finds the best order.

We also presented experimental results in which these algorithms were
used to combine the results of a number of ``search experts,'' each of
which corresponds to a domain-specific strategy for searching the web.
We showed that in two domains, the learned system closely tracks and
often exceeds the performance of the best of these search
experts. These results hold for either traditional relevance feedback
models of learning, or from weaker feedback in the form of simulated
``click data.''  The performance of the learned systems also clearly
exceeds the performance of more naive approaches to searching.

%% ===================================================================

\section*{Acknowledgments}
We would like to thank Noga Alon, Edith Cohen, Dana Ron, and Rick Vohra
for numerous helpful discussions. An extended abstract of this paper
appeared in {\it Advances in Neural Information Processing Systems 10},
MIT Press, 1998.

\bibliography{ranking}
\bibliographystyle{theapa}

\end{document}
