Robust Reductions from Ranking to Classification

Maria-Florina Balcan^{1}, Nikhil Bansal^{2}, Alina Beygelzimer^{2}, Don Coppersmith^{3}, John Langford^{4}, and Gregory B. Sorkin^{2}

1 Carnegie Melon University, Pittsburgh, PA

                             ninamf@cs.cmu.edu

2 IBM Thomas J. Watson Research Center, Yorktown Heights + Hawthorne, NY

                     {bansal,beygel,sorkin}@us.ibm.com

3 IDA Center for Communications Research, Princeton, NJ

                             dcopper@idaccr.org

4 Yahoo Research, New York, NY

                              jl@yahoo-inc.com

Abstract. We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ nr where n is the number of elements.

1 Introduction

We consider the problem of ranking a set of instances. In the most basic version, we are given a set of unlabeled instances belonging to two classes, 0 and 1, and the goal is to rank all instances from class 0 before any instance from class 1. A common measure of success for a ranking algorithm is the area under the ROC curve (AUC). The associated loss, 1 − AUC, measures how many pairs of neighboring instances would have to be swapped to repair the ranking, normalized by the number of 0s times the number of 1s. The loss is zero precisely when all 0s precede all 1s; one when all 1s precede all 0s. It is greater for mistakes at the beginning and the end of an ordering, which satisfies the intuition that an unwanted item placed at the top of a recommendation list should have a higher associated loss than when placed in the middle.

In binary classification, where the problem is simply to predict whether a label is 0 or 1, the loss is measured by the error rate, i.e., the probability of a misclassification. Here any misclassified instance incurs the same loss independent of how other instances are classified, while the AUC loss depends on the whole (ranked) sequence of instances.

It is natural to ask whether we need fundamentally different algorithms to optimize these two loss functions. This paper shows that the answer is no, in the sense that the problem of optimizing the AUC can be reduced to classification so that good performance on the classification problem implies good performance on the AUC problem. The classification problem is to predict, given a random pair of instances with different labels, whether the first instance should be ordered before the second.

We show that there is a robust mechanism for translating any binary classifier learning algorithm into a ranking algorithm.

Relation to Score-Based Ranking: A common way to generate a ranking is to learn a scoring function f : X → ℝ, which assigns a real-valued score to each example in the instance space X, and then rank test examples in the order of their scores.

If f is learned by minimizing some loss function that depends on individual examples, this approach is not robust. The fundamental difficulty is exhibited by highly unbalanced test sets. If we have one 1 and many 0s, a pointwise loss on the 1 with a perfect prediction for the 0s can greatly harm the AUC while only slightly affecting the pointwise loss with respect to the induced distribution. For concreteness, let f(x) be 1 if the predicted label is 1, and 0 otherwise. Then if n is the number of elements in the test set, f can induce an AUC loss of 1 with classification loss of 1/n. Thus such schemes transform pointwise loss l to AUC loss nl. The same observation holds for regrets in place of losses: pointwise regret r translates into AUC regret nr. Regret here is the difference between the incurred loss and the lowest achievable loss on the problem. The motivation for regret analysis is to separate avoidable loss from noise intrinsic to the problem, so that bounds apply nontrivially even for problems with large intrinsic noise.

To avoid the robustness problem, many score-based ranking algorithms optimize loss functions that depend on pairs of examples, e.g., the probability that a pair of examples with different labels is misranked (see [AHR05,CLV05,FIS+03,RCM+05]).

Another approach, taken in [CSS99,AM07] as well as here, is to learn a preference function c : X × X → {0, 1} on pairs of examples. If c(x, x′) = 1 then c ranks x higher than x′, and c(x, x′) = 0 indicates the opposite preference. Notice that while a scoring function imposes a total order on the entire instance space, a preference function is not required to be transitive. If, for example, the underlying distribution is such that an optimal preference function is non-transitive, then not imposing a total order on the entire space may result in a better performance on limited subsets on which the algorithm is invoked. Since c is not necessarily consistent with a linear ordering on a test set U, there is a need for a subsequent step which produces an ordering of U based on the learned c. Because c is typically learned using a binary classification algorithm, we call it a classifier.

Relation to the Feedback Arc Set Problem: Consider a set U with a hidden bipartition into a set of winners and a set of losers. Imagine that every element (also called player) of U plays all other elements, and the outcome of each play is determined by a classifier c. The tournament induced by c on U does not have to be consistent with any linear ordering. We want to find the best way to rank the elements in U so that all winners are ordered before all losers.

A natural objective, dating back to Slater [Sla61], is to find an ordering which agrees with the tournament on as many player pairs as possible, i.e., minimizes the number of inconsistent pairs where a higher-ranked player (one ordered closer to the beginning of the list) lost to a lower-ranked player. This is the NP-hard “minimum feedback arc set problem in tournaments”. (Although the hardness was conjectured for a long time, it was proved only recently; see [A06].)

A mistake is defined as a winner–loser pair where the loser beats (i.e., is preferred to) the winner. Section 4 proves that a solution to the feedback arc set problem satisfies a basic guarantee: If the classifier c makes at most k mistakes on U, then the algorithm minimizing the number of inconsistent pairs produces an ordering, or equivalently a transitive tournament, with at most 2k mistakes on U. Section 5 shows that this bound is tight.

Instead of solving feedback arc set, another natural way to break cycles is to rank instances according to their number of wins in the tournament produced by c. The way ties are broken is inessential; for definiteness, let us say they are broken against us. Coppersmith, Fleischer, and Rudra [CFR06] proved that this algorithm provides a 5-approximation for the feedback arc set problem. An approximation, however, does not generally imply that the ratio of the number of mistakes made by the approximation to the number of mistakes made by c is finite. For example, c may make no mistakes (i.e., make correct predictions on all winner–loser pairs) while inducing a non-transitive tournament on the winners or the losers, so an approximation that does not know the labeling can incur a non-zero number of mistakes. We prove, however, that the algorithm that orders the elements by their number of wins, has the same regret and loss transforms as an optimal solution to the NP-hard feedback arc set problem. Again, Section 5 shows that solving feedback arc set does no better.

Results: The core theorem (Theorem 1) says that a pairwise classifier with regret r implies AUC regret at most 2r, for arbitrary distributions over instances. For example, if the binary error rate is 20% due to inherent noise and 5% due to the errors made by the classifier, then AUC regret is at most 10%, i.e., only the 5% are at most doubled. The same statement holds for losses in place of regrets. As shown in [AM07] (see Section 5), this is best possible with any deterministic algorithm. Section 6 proves that Theorem 1 holds for a natural generalization of AUC regret to multiple labels.

In a subsequent paper, Ailon and Mohri [AM07] describe a randomized quick-sort reduction, which guarantees that AUC loss is bounded by binary loss, in expectation over the randomness of the algorithm. They also define a generalization of AUC loss to multiple labels, and show that the expected generalized AUC loss is bounded by twice the binary loss. This generalization encodes the generalization we analyze in Section 6 as a special case. Using the decomposition in Theorem 1, the argument in [AM07] could potentially be extended to bound AUC regret, rather than loss. The quick-sort algorithm is more efficient, requiring only O(n log n) instead of Θ(n^{2}) classifier evaluations at test time, which makes it practical in larger settings. On the other hand, the guarantees in [AM07] are in expectation over the algorithm’s randomness. It would be interesting to see a bound on the variance of the incurred loss.

Cohen, Schapire, and Singer [CSS99] operate in a similar two-stage setting: They first learn a preference function that takes a pair of instances and returns a score predicting how certain it is that the first instance should be ranked before the second. The learned function is then evaluated on all pairs of instances in the test set and the instances are ordered using the degree-based algorithm used here. One of the results they show is that the agreement of an optimal feedback arc set ordering with the learned predictions is at most twice the agreement obtained by their algorithm. To translate this result into the language of losses, let Mfa be the AUC loss of the minimum feedback arc set ordering and Approx be the AUC loss of the approximation. Then the result says that 1 − Approx ≥ \frac{1}{2}(1 − Mfa) or Approx ≤ \frac{1}{2} + Mfa/2. The result is difficult to compare with the results given here, as the settings are different. A rough comparison requires specializations and yields a bound that is weaker than ours: As we show in Section 4, Mfa ≤ 2 Bin, where Bin is the loss of the pairwise predictor, so the result of [CSS99] roughly says that Approx ≤ \frac{1}{2} + Bin (which is essentially vacuous because a random ordering has expected AUC loss of 1/2), while we show that Approx ≤ 2 Bin, modulo the slight difference in the binary problem.

Curiously, the relationship of ranking to classification is functionally tighter than has been proven for regression to binary classification (r ↦ \sqrt{r}) [LZ05].

2 Preliminaries

Classification: A binary classification problem is defined by a distribution P over X × {0, 1}, where X is some observable feature space and {0, 1} is the binary label space. (For simplicity of presentation, assume that the spaces are finite.) The goal is to find a classifier c : X → {0, 1} minimizing the classification loss on P given by

e(c, P) = Pr_{(x,y)∼P} [c(x) ≠ y].

The classification regret of c on P is defined as

r(c, P) = e(c, P) − min_{c^{∗}} e(c^{∗}, P),

where the minimum is taken over all classifiers c^{∗} : X → {0, 1}.

Ranking: Where U ⊆ X is an unlabeled set, and x, x′ ∈ U, a preference function π(x, x′, U) = 1 if π “prefers” x to x′, and 0 otherwise. For simplicity, let π(x, x′, U) = 1 − π(x′, x, U) for x ≠ x′. If π is consistent with some linear ordering of U, we call π itself an ordering of U, and denote π_{U}(x, x′) = π(x, x′, U). For a labeled set S = {(x_{1}, y_{1}), …, (x_{n}, y_{n})}, let U_{S} = {x_{1}, …, x_{n}} denote the unlabeled set corresponding to S.

The AUC loss of an ordering π_{U_{S}} on a set S = {(x_{1}, y_{1}), …, (x_{n}, y_{n})} is defined as

l(π_{U_{S}}, S) = \frac{∑_{i≠j} 1(y_{i} > y_{j})π_{U_{S}}(x_{i}, x_{j})}{∑_{i<j} 1(y_{i} ≠ y_{j})}.

Indices i and j in the summations range from 1 to n, and 1(·) is the indicator function which is 1 if its argument is true, and 0 otherwise. By convention, 0s should be ordered ahead of 1s, so any pair where a 1 is ordered before a 0 contributes to the loss.

A pair of examples (x_{1}, y_{1}), (x_{2}, y_{2}) is called mixed if y_{1} ≠ y_{2}.

Algorithm 1 Auc-Train (labeled set S, binary learning algorithm A)

1. Define the (multi)set U_{S} = {x : (x, y) ∈ S}.

2. Let S′ = {(⟨x_{1}, x_{2}, U_{S}⟩, 1(y_{1} < y_{2})) : (x_{1}, y_{1}), (x_{2}, y_{2}) ∈ S and y_{1} ≠ y_{2}}.

3. return c = A(S′).

Algorithm 2 Degree (unlabeled set U, classifier c)

1. For x ∈ U, let deg(x) = |{x′ : c(x, x′, U) = 1, x′ ∈ U}|.

2. Sort U in descending order of deg(x), breaking ties arbitrarily.

An AUC problem is defined by a distribution D over (X × {0, 1})^{∗}. The goal is to find an ordering π minimizing the expected AUC loss on D, given by

l(π, D) = E_{S∼D}l(π_{U_{S}}, S).

As an example, consider the internet search problem, where there is some underlying distribution of queries, each yielding a set of search results. This process generates a distribution over subsets; whether or not the subsets have the same size is inessential for the analysis. Note that D is allowed to encode arbitrary dependencies between examples.

The AUC regret of π on D is given by rauc(π, D) = l(π, D)−min_{π^{∗}} l(π^{∗}, D), where the minimum is taken over all preference functions π^{∗} transitive on any subset in the support of D.

Tournaments: A tournament is a complete graph with no self-loops, in which each edge is directed one way or the other, so that for every pair of vertices i ≠ j, either i → j is an edge or j → i is an edge, but not both. The edge i → j says that i beats j (“i is preferred to j”). Since we adopt the convention that 0s should be ordered ahead of 1s, ideally 0s should beat 1s. We write deg(i) for the outdegree of vertex i, so deg(i) = ∑_{j} 1(i → j), where the indicator function 1(i → j) is 1 if i → j is an edge and 0 otherwise. Thus we generally expect 0s to have large outdegree and 1s small outdegree; however, we allow and analyze arbitrary tournaments.

3 Ordering by the Number of Wins

In this section, we describe the reduction and prove the main result.

The reduction consists of two components. The training part, Auc-Train (Algorithm 1), takes a set S of labeled examples of type X × {0, 1} and transforms all mixed pairs in S into binary examples for the oracle learning algorithm. The binary classification problem induced by the reduction is to predict, given a random mixed pair of examples in a subset U ⊆ X together with U itself, whether the first example should be ordered before the second in U.

The reason why the classifier has to depend on U is that a regret reduction cannot throw away any information; otherwise the adversary could encode conflicting pairwise preferences based on the value of the subset. An alternative is to introduce an assumption that for any pair of unlabeled instances, their optimal pairwise ordering is independent of the drawn subset, whenever the instances are drawn together [AM07].

For any process D generating datasets S, we can define the induced distribution by first drawing S from D, then drawing a random mixed pair (x_{1}, y_{1}), (x_{2}, y_{2}) from S, and generating (⟨x_{1}, x_{2}, U_{S}⟩, 1(y_{1} < y_{2})). We denote this induced distribution by Auc-Train(D), admittedly overloading the notation.

The test part, Degree (Algorithm 2), uses the pairwise classifier c learned in Algorithm 1 to run a tournament on a test set U, and then ranks the elements of U in decreasing order of their number of wins in the tournament, breaking ties arbitrarily. Recall that we expect 0s to beat 1s, and thus have larger outdegree. (In the algorithm and below, we omit angle brackets from calls to c.)

For the analysis, it is best to think of the classifier c as an adversary playing against the ranking algorithm Degree. The goal of c is to pay little in classification regret while making Degree(·, c) pay a lot in AUC regret.

Theorem 1 below reduces the regret problem to the following combinatorial problem. Given a set U with each element labeled either 0 or 1, the adversary c starts with a tournament of its choice where every 0 beats every 1. Then c can choose to invert the outcome of any game between a 0 and a 1, and she is charged for each such “mistake”. Again, c can choose any (not necessarily transitive) subtournaments on the 0s and on the 1s for free. The resulting tournament is shown to the algorithm.

Without seeing the labels, the algorithm needs to approximate c’s tournament with a transitive tournament (or equivalently, a linear order). The goal of the algorithm is to minimize the number of mistakes it makes (i.e., pairs where a 1 precedes a 0 in the order). If c were itself consistent with a linear order, the algorithm could simply output that, at a cost in mistakes identical to the adversary’s. In general it is not, and we would expect the cost of the more-constrained linear order to be higher. Our goal is to show that the reduction is robust in the sense that c cannot cause Degree to make many mistakes without making many mistakes itself. More precisely, Degree never makes more than twice as many mistakes as c. This combinatorial result (Theorem 2) is invoked (n − 1) times in the proof of the main theorem below.

Theorem 1. For all distributions D and all pairwise classifiers c,

rauc(Degree(·, c), D) ≤ 2r(c, Auc-Train(D)).  (1)

Note the quantification in the above theorem: it applies to all settings where Algorithms 1 and 2 are used; in particular, D may encode arbitrary dependences between examples.

Proof. Given an unlabeled test set U ∈ X^{n}, the joint distribution D induces a conditional distribution D(Y_{1}, …, Y_{n} | U) over the set of label sequences {0, 1}^{n}.

In the remainder of the paper, let Q denote this conditional distribution. We prove the theorem by fixing U, taking the expectation over the draw of U at the end.

Let U be identified with {1, …, n}. The pairwise loss of ordering i before j in U is defined as

l_{Q}(i, j) = E_{y^{n}∼Q} \frac{1(y_{i} > y_{j})}{∑_{u<v} 1(y_{u} ≠ y_{v})}.

If l_{Q}(i, j) < l_{Q}(j, i), the regret r_{Q}(i, j) of ordering i before j is 0; otherwise, r_{Q}(i, j) = l_{Q}(i, j) − l_{Q}(j, i) and r_{Q}(i, j) is called proper. Thus if r_{Q}(i, j) is proper, then r_{Q}(j, i) = 0.

Lemma 1 presented below this proof, establishes a basic property of pairwise regrets. It says that for any i, j, and k, if r_{Q}(i, j) and r_{Q}(j, k) are proper, r_{Q}(i, k) = r_{Q}(i, j) + r_{Q}(j, k).

We can assume without loss of generality that the ordering minimizing the AUC loss (thus having zero AUC regret) on U is ⟨1, 2, …, n⟩. It is easy to see that all regretzero pairwise predictions must be consistent with the ordering, i.e., r_{Q}(i, j) = 0 for all 1 ≤ i < j ≤ n. Indeed, all r_{Q}(i, i + 1) must be 0; otherwise swapping i and i + 1 decreases the overall regret, contradicting the assumption that ⟨1, 2, …, n⟩ is regret minimizing. Thus all r_{Q}(i + 1, i) are proper and repeated application of Lemma 1 implies that, for any j > i, r_{Q}(j, i) is proper, which in turn implies that r_{Q}(i, j) = 0.

Applied repeatedly, Lemma 1 says that for any pair i < j, the regret r_{Q}(j, i) can be decomposed as r_{Q}(j, i) = ∑_{k=i}^{j−1} r_{Q}(k + 1, k). Since U is fixed throughout the proof, we omit the subscript U from the produced ordering π_{U} and the optimal ordering π_{U}^{∗}. Thus the AUC regret of π = π_{U} on Q can be decomposed as a sum of pairwise regrets (where ⟨U, y^{n}⟩ denotes the unlabeled sample U labeled with y^{n}):

rauc(π, Q) = l(π, Q) − min_{π^{∗}} l(π^{∗}, Q)

= E_{y^{n}∼Q}[l(π, ⟨U, y^{n}⟩)] − min_{π^{∗}} E_{y^{n}∼Q}[l(π^{∗}, ⟨U, y^{n}⟩)]

= E_{y^{n}∼Q} \frac{∑_{i,j} 1(y_{i} > y_{j})π(i, j)}{∑_{u<v} 1(y_{u} ≠ y_{v})} − min_{π^{∗}} E_{y^{n}∼Q} \frac{∑_{i,j} 1(y_{i} > y_{j})π^{∗}(i, j)}{∑_{u<v} 1(y_{u} ≠ y_{v})}

= max_{π^{∗}} E_{y^{n}∼Q} \frac{∑_{i,j}[1(y_{i} > y_{j})π(i, j) − 1(y_{i} > y_{j})π^{∗}(i, j)]}{∑_{u<v} 1(y_{u} ≠ y_{v})}

= ∑_{i<j:π(j,i)=1} r_{Q}(j, i) = ∑_{k=1}^{n−1} |{i ≤ k < j : π(j, i) = 1}| · r_{Q}(k + 1, k).

The last equality follows by repeated application of Lemma 1.

The classification regret can also be written in terms of pairwise regrets:

r(c,Auc-Train(Q)) = e(c, Auc-Train(Q)) − min_{c^{∗}} e(c^{∗}, Auc-Train(Q))

= max_{c^{∗}} E_{y^{n}∼Q} [\frac{∑_{i,j}[1(y_{i} > y_{j})c(i, j, U) − 1(y_{i} > y_{j})c^{∗}(i, j, U)]}{∑_{u<v} 1(y_{u} ≠ y_{v})}]

= ∑_{i<j:c(j,i,U)=1} r_{Q}(j, i) = ∑_{k=1}^{n−1} |{i ≤ k < j : c(j, i, U) = 1}| · r_{Q}(k + 1, k).

Let g_{k} and f_{k} denote the coefficients with which the term r_{Q}(k + 1, k) appears in the above decompositions of rauc(π, Q) and r(c, Auc-Train(Q)) respectively. To complete the proof it suffices to show that g_{k} ≤ 2f_{k} for each k.

Fix k and consider a bipartition of U into a set {1, …, k} of “winners” and a set {k + 1, …, n} of “losers”. In this terminology, g_{k} is the number of winner–loser pairs where the loser has at least as many wins as the winner, and f_{k} is the number of winner–loser pairs where the loser beats the winner (in the tournament induced by c on U). Theorem 2 below shows that g_{k} ≤ 2f_{k}, completing this proof.

We prove the lemma used in the proof above.

Lemma 1. For any i, j, and k in {1, …, n}, if r_{Q}(i, j) and r_{Q}(j, k) are proper,

r_{Q}(i, k) = r_{Q}(i, j) + r_{Q}(j, k).

Proof. We have

r_{Q}(i, j) + r_{Q}(j, k) = E_{y^{n}∼Q} \frac{I(y^{n})}{∑_{u<v} 1(y_{u} ≠ y_{v})},

where

I(y^{n}) = 1(y_{i} = 1, y_{j} = 0) − 1(y_{i} = 0, y_{j} = 1) + 1(y_{j} = 1, y_{k} = 0) − 1(y_{j} = 0, y_{k} = 1)
= 1(y_{i} = 1, y_{j} = 0, y_{k} = 0) + 1(y_{i} = 1, y_{j} = 0, y_{k} = 1)
− 1(y_{i} = 0, y_{j} = 1, y_{k} = 0) − 1(y_{i} = 0, y_{j} = 1, y_{k} = 1)
+ 1(y_{i} = 0, y_{j} = 1, y_{k} = 0) + 1(y_{i} = 1, y_{j} = 1, y_{k} = 0)
− 1(y_{i} = 0, y_{j} = 0, y_{k} = 1) − 1(y_{i} = 1, y_{j} = 0, y_{k} = 1)
= 1(y_{i} = 1, y_{k} = 0) − 1(y_{i} = 0, y_{k} = 1).

Recall that

E_{y^{n}∼Q} \frac{1(y_{i} = 1, y_{k} = 0)}{∑_{u<v} 1(y_{u} ≠ y_{v})} = l_{Q}(i, k), E_{y^{n}∼Q} \frac{1(y_{i} = 0, y_{k} = 1)}{∑_{u<v} 1(y_{u} ≠ y_{v})} = l_{Q}(k, i).

Thus r_{Q}(i, j)+r_{Q}(j, k) = l_{Q}(i, k)−l_{Q}(k, i) = r_{Q}(i, k). (Since r_{Q}(i, j)+r_{Q}(j, k) > 0, we have l_{Q}(i, k) > l_{Q}(k, i) and r_{Q}(i, k) is proper.)

Let T be a tournament and let the vertices of T be arbitrarily partitioned into a set W of “winners” and a set L of “losers”. Call the triple (T, W, L) a winner–loser partitioned tournament, and denote it by T. We show that for any T, the number of winner–loser pairs where the loser’s degree is larger than or equal to the winner’s, is at most twice the number of winner–loser pairs where the loser beats the winner. Formally, define two measures:

g(T) = ∑_{ℓ∈L} ∑_{w∈W} 1(deg(ℓ) ≥ deg(w)),
f(T) = ∑_{ℓ∈L} ∑_{w∈W} 1(ℓ → w).

Theorem 2. For any winner–loser partitioned tournament T, g(T) ≤ 2f(T).

Since the number of edges from L to W is equal to the total number of edges out of L minus the number of edges from L to L, we can rewrite

f(T) = ∑_{ℓ∈L} ∑_{w∈W} 1(ℓ → w) = ∑_{ℓ∈L} deg(ℓ) − \binom{|L|}{2}.

Both f(T) and g(T) depend only on the degrees of the vertices of T, so rather than working with a (labeled) tournament, a relatively complex object, we can work with a (labeled) degree sequence.

Landau’s theorem [Lan53] says that there exists a tournament with outdegree sequence d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} if and only if, for all 1 ≤ i ≤ n, ∑_{j=1}^{i} d_{j} ≥ ∑_{j=1}^{i}(j − 1), with equality for i = n.

Recall that a sequence ⟨a_{1}, …, a_{n}⟩ is majorized by ⟨b_{1}, …, b_{n}⟩ if the two sums are equal and if, when each sequence is sorted in non-increasing order, the prefix sums of the b sequence are at least as large as (dominate) those of the a sequence. (For a comprehensive treatment of majorization, see [MO79].) Landau’s condition is precisely that ⟨d_{1}, …, d_{n}⟩ is majorized by ⟨0, …, n − 1⟩. (With the sequences sorted in increasing order, Landau’s condition is that prefix sums of the degree sequence dominate those of the progression, which is the same as saying that the suffix sums of the degree sequence are dominated by the suffix sums of the progression.) This allows us to take advantage of well-known properties of majorization, notably that if A′ is obtained by averaging together any elements of A, then A majorizes A′.

This allows us to restate Theorem 2 in terms of a sequence and majorization, rather than a tournament, but first we relax the constraints. First, where the original statement requires elements of the degree sequence to be non-negative integers, we allow them to be non-negative reals. Second, the original statement requires that we attach a winner/loser label to each element of the degree sequence. Instead, we aggregate equal elements of the degree sequence, and for a degree d_{i} of (integral) multiplicity m_{i}, assign arbitrary non-negative (but not necessarily integral) portions to winners and losers: w_{i} + ℓ_{i} = m_{i}.

Let D = (D, W, L) be such a generalized “winner–loser labeled compressed sequence”. Note that the majorization condition applies only to the values {d_{i}, m_{i}}, not the labeling. The definitions of f and g above are easily extended to this broader domain: g(D) = ∑_{i} ∑_{j≤i} l_{i}w_{j}, f(D) = ∑_{i} l_{i}d_{i} − \binom{∑_{i} l_{i}}{2}, where we define \binom{x}{2} = x(x − 1)/2 for all x (not just integers). If we prove g ≤ 2f over this larger domain, the inequality holds in particular for plain winner–loser labeled degree sequences (the case where all weights happen to be integral). That is, Theorem 3, below, implies Theorem 2.

Theorem 3. For any winner–loser labeled compressed sequence D = (D, W, L) where D is majorized by ⟨0, …, n − 1⟩, g(D) ≤ 2f(D).

Proof. We begin with an outline of the proof. Define a compressed sequence D as being canonical if it consists of at most three degrees: a smallest degree d_{1} having only losers (w_{1} = 0), a middle degree d_{2} potentially with both winners and losers (w_{2}, ℓ_{2} ≥ 0), and a largest degree d_{3} having only winners (ℓ_{3} = 0). We first establish that any canonical sequence has g(D)−2f(D) ≤ 0. We then show how to transform any degree sequence to a canonical one with a larger (or equal) value of g − 2f, which completes the argument.

We first show that a canonical sequence D has g − 2f ≤ 0. For the canonical configuration, g = w_{2}ℓ_{2} and f = ℓ_{1}d_{1} + ℓ_{2}d_{2} − \binom{ℓ_{1}+ℓ_{2}}{2}, and hence our goal is to show that

ℓ_{1}d_{1} + ℓ_{2}d_{2} ≥ (ℓ_{1} + ℓ_{2})(ℓ_{1} + ℓ_{2} − 1)/2 + w_{2}ℓ_{2}/2  (2)

By Landau’s condition applied to ℓ_{1} and ℓ_{1} + w_{2} + ℓ_{2}, we have the following two relations:

ℓ_{1}d_{1} ≥ \binom{ℓ_{1}}{2}  (3)

and

ℓ_{1}d_{1} + (ℓ_{2} + w_{2})d_{2} ≥ \binom{ℓ_{1} + w_{2} + ℓ_{2}}{2}.  (4)

Multiplying (3) by w_{2}/(ℓ_{2} + w_{2}) and (4) by ℓ_{2}/(ℓ_{2} + w_{2}) and adding them, we obtain that

ℓ_{1}d_{1} + ℓ_{2}d_{2} ≥ \frac{1}{ℓ_{2} + w_{2}} (w_{2}\binom{ℓ_{1}}{2} + ℓ_{2}\binom{ℓ_{1} + ℓ_{2} + w_{2}}{2}) .  (5)

A simple calculation shows that the right side of inequality (5) is exactly equal to the right hand side of (2). This proves that g ≤ 2f for a canonical sequence.

If a sequence is not canonical then there are two consecutive degrees d_{i} and d_{j} (j = i + 1) such that one of the cases 1a, 1b, or 2 (described below) holds. In each case we apply a transformation producing from the degree sequence D a new degree sequence D′, where:

– the total weight of winners in D′ is equal to that of D; similarly for losers, and thus for the total weight; furthermore, the total weight on each degree remains integral;

– D′ maintains the majorization needed for Landau’s theorem;

– the value of g − 2f is at least as large for D′ as for D; and – either the number of nonzero values w_{i} and ℓ_{i} or the number of distinct degrees

d_{i} is strictly smaller for D′ than for D, and the other is no larger for D′ than for D.

We first sketch the cases and then detail the transformations.

Case 1a d_{i} has only winners (l_{i} = 0).

Apply Transformation 1a, combining the two degrees into one.

Case 1b d_{j} has only losers (w_{j} = 0).

Apply Transformation 1b, combining the two degrees into one.

Case 2 All of w_{i}, l_{i}, w_{j} and l_{j} are nonzero.

Apply Transformation 2, leaving the degrees the same but transforming the weights so that one of them is equal to 0 and one of the preceding cases applies, or the weights obey an equality allowing application of Transformation 3, which combines the two degrees into one.

Either there is some pair i, j to which one of the cases applies, or the sequence is canonical. We argue this by showing that if there is no pair i, j for which Cases 1a or 1b apply, then either the sequence is canonical, or there is a pair to which Case 2 applies. First, note that for any i ≠ n, l_{i} > 0 (else Case 1a applies to i, i+1) and for any i ≠ 1, w_{i} > 0 (else Case 1b applies to i − 1, i). In particular, for any 1 < i < n, both l_{i}, w_{i} > 0. If n ≥ 4 this implies immediately that Case 2 applies to the pair 2, 3. If n = 1, D is automatically canonical. If n = 2 and l_{2} = 0 or w_{1} = 0 then D is canonical, while if both l_{2}, w_{1} > 0 we may apply Case 2 (since, as we first argued, l_{1}, w_{2} > 0). Finally, if n = 3, we know l_{1}, l_{2}, w_{2}, w_{3} > 0. If w_{1} = l_{3} = 0 then D is canonical, and otherwise Case 2 applies.

Transformation 1a: In Case 1a, where d_{i} has only winners, change D to a new sequence D′ by replacing the pair (d_{i}, w_{i}, 0), (d_{j}, w_{j}, l_{j}) by their “average”: the single degree (d′, w′, l′), where

w′ = w_{i} + w_{j}, l′ = l_{j}, d′ = \frac{w_{i}d_{i} + (w_{j} + l_{j})d_{j}}{w_{i} + w_{j} + l_{j}} .

The stated conditions on a transformation are easily checked. The total weight of winners is clearly preserved, as is the total weight of losers and the total degree (out-edges). Summing weights preserves integrality. The number of distinct degrees is reduced by one, and the number of nonzero weights may be decreased by one or may remain unchanged. The Landau majorization condition holds because D′, as an averaging of D, is majorized by it, and majorization is transitive. The only non-trivial condition is the non-decrease in g − 2f. The number of loser–winner pairs where the loser outranks the winner remains the same, so g(D) = g(D′). Also, f depends only on the total weight of losers (which is unchanged) and on the average degree of losers. This average degree would be unchanged if w_{i} were 0; since w_{i} ≥ 0, the average degree may decrease. Thus f(D) ≥ f(D′), and (g − 2f)(D) ≤ (g − 2f)(D′), as desired.

Transformation 1b: Symmetrically to Transformation 1a, obtain D′ by replacing the pair of labeled weighted degrees (d_{i}, w_{i}, l_{i}) and (d_{j}, 0, l_{j}) with a single one (d′, w′, l′), where w′ = w_{i}, l′ = l_{i} + l_{j}, and d′ = [(l_{i} + w_{i})d_{i} + l_{j}d_{j}]/(l_{i} + w_{i} + l_{j}).

Transformation 2: Where w_{i}, l_{i}, w_{j} and l_{j} are all nonzero, we begin with one case, which leads to one other. In the usual case, we transform D to D′ by replacing the pair (d_{i}, w_{i}, l_{i}), (d_{j}, w_{j}, l_{j}) with (d_{i}, w_{i} + x, l_{i} − x), (d_{j}, w_{j} − x, l_{j} + x), for some value of x (positive or negative) to be determined. This affects only the labeling, not the weighted degree sequence itself, and is therefore legitimate as long as the four quantities w_{i} + x, l_{i} − x, w_{j} − x and l_{j} + x are all non-negative.

Defining Δ = (g − 2f)(D′) − (g − 2f)(D), we wish to choose x to make Δ > 0.

Δ = {[(l_{j} + x)(w_{i} + x + w_{j} − x) + (l_{i} − x)(w_{i} + x)] − [l_{j}(w_{i} + w_{j}) + l_{i}w_{i}]}
− 2{[(l_{i} − x)d_{i} + (l_{j} + x)d_{j}] − [l_{i}d_{i} + l_{j}d_{j}]}
= x(w_{j} + l_{i} − 2(d_{j} − d_{i}) − x) = x(a − x),

where a = w_{j} + l_{i} − 2(d_{j} − d_{i}). This is a simple quadratic expression with negative coefficient on x^{2}, so its value increases monotonically as x is varied from 0 to a/2, where the maximum is obtained. (Note that a may be negative.) If a = 0 then we do not use this transformation but Transformation 3, below. Otherwise, vary x from 0 to a/2 stopping when x reaches a/2 or when any of w_{i} + x, l_{i} − x, w_{j} − x and l_{j} + x becomes 0. Call this value x^{⋆}, and use it to define the transformation.

If any of w_{i} + x, l_{i} − x, w_{j} − x and l_{j} + x is 0 then the number of nonzero weights is decreased (while the number of distinct degrees is unchanged). Otherwise, x^{⋆} = a/2. In that case, the new D′ has a = 0 (the optimal “weight shift” has already been performed). With a = 0 we apply Transformation 3, which reduces the number of nonzero weights.

Transformation 3: Similar to Cases 1a and 1b, transform D to D′ by replacing the pair (d_{i}, w_{i}, l_{i}), (d_{j}, w_{j}, l_{j}) with a single degree (d′, w′, l′) that is their weighted average,

w′ = w_{i} + w_{j}, l′ = l_{i} + l_{j}, d′ = \frac{(w_{i} + l_{i})d_{i} + (w_{j} + l_{j})d_{j}}{w_{i} + l_{i} + w_{j} + l_{j}} .

This gives

Δ = (g − 2f)(D′) − (g − 2f)(D)

= (l_{i}w_{j}) − 2(l_{i}d′ + l_{j}d′ − l_{i}d_{i} − l_{j}d_{j})

= l_{i}w_{j} + \frac{2(d_{j} − d_{i})(w_{i}l_{j} − w_{j}l_{i})}{w_{i} + l_{i} + w_{j} + l_{j}}.

We apply this transformation only in the case where Transformation 2 fails to give any improvement because its “a” expression is equal to 0, i.e., d_{j} −d_{i} = (w_{j} +l_{i})/2. Making the corresponding substitution gives

Δ = l_{i}w_{j} + \frac{(w_{j} + l_{i})(w_{i}l_{j} − w_{j}l_{i})}{w_{i} + l_{i} + w_{j} + l_{j}}

= \frac{(l_{i}w_{j})(l_{j} + w_{i}) + (l_{j}w_{i})(l_{i} + w_{j})}{w_{i} + l_{i} + w_{j} + l_{j}} > 0.

This reduces the number of distinct degrees by one, without increasing the number of nonzero weights.

Concluding the argument, we have shown that any non-canonical configuration D can be replaced by a configuration with a strictly smaller total of distinct degrees and nonzero weights, and at least as large a value of g − 2f. Since D had at most n distinct degrees and 2n nonzero weights originally, a canonical configuration D^{⋆} is reached after at most 3n − 1 transformations. (All that is important is that the number of transformations is finite: that a canonical configuration is eventually reached.) Then, (g − 2f)(D) ≤ (g − 2f)(D^{⋆}) ≤ 0.

A further generalization of Theorem 3 may be found in [BCS06].

4 An Upper Bound for Minimum Feedback Arc Set

This section shows an analog of Theorem 2 for an optimal solution to the feedback arc set problem. (The decomposition argument in Theorem 1 is algorithmindependent and applies here as well.) For a tournament T and an ordering π, a back edge is an edge i → j in T such that j is ordered before i in π. Let back(T, π) denote the number of back edges induced by π in T.

For a winner–loser partitioned tournament T = (T, W, L) and any minimum feedback arc set ordering π of T, let g′(T, π) be the number of winner–loser pairs where the loser comes before the winner in π, and as before let

f(T) = ∑_{ℓ∈L} ∑_{w∈W} 1(ℓ → w)

be the number of winner–loser pairs where the loser beats the winner.

Theorem 4. For any winner–loser partitioned tournament T = (T, W, L) and any minimum feedback arc set ordering π of T, g′(T, π) ≤ 2f(T).

Proof. Let k_{w} be the smallest possible number of back edges in the subtournament induced by W. Define k_{l} similarly for the subtournament induced by L. Let k_{w}^{π} and k_{l}^{π} be the number of back edges in π that go from W to W and from L to L, respectively. Denote the number of remaining (i.e., winner–loser or loser–winner) back edges in π by k_{o}^{π}.

Consider another ordering σ where all winners are ordered before all losers, and both the winners and the losers are ordered optimally among themselves, i.e., with k_{w} and k_{l} back edges respectively. The number of back edges in σ is back(T, σ) = k_{w} + k_{l} + f(T). But we also have back(T, σ) ≥ back(T, π) since π minimizes the number of back edges, and thus k_{w} + k_{l} + f(T) ≥ k_{w}^{π} + k_{l}^{π} + k_{o}^{π}. Since k_{w} ≤ k_{w}^{π} and k_{l} ≤ k_{l}^{π} by definition of k_{w} and k_{l}, we have f(T) ≥ k_{o}^{π}.

Consider any winner–loser pair with the loser ordered before the winner. If w → l is the edge, it is a back edge in π and thus is counted by k_{o}^{π}. If l → w is the edge instead, it is counted by f(T). Thus g′(T, π) is at most k_{o}^{π} +f(T). Since f(T) ≥ k_{o}^{π}, this number is never more than 2f(T), which implies g′(T, π) ≤ 2f(T).

The proof above immediately shows that for any T and any ordering π_{α} of T with at most (1 + α) · opt(T) back edges, g′(T, π_{α}) ≤ (2 + α)f(T) + α(k_{w} + k_{l}), where opt(T) is the minimum number of back edges in T, and k_{w} and k_{l} are as in the proof above. Thus, a FAS approximation does not generally guarantee that if f is 0, then so is g′ (a guarantee provided by Degree and FAS). For example, T may make correct statements about all winner–loser pairs while inducing a nontransitive tournament on the winners or the losers, so an approximation that does not know the winner–loser labeling can incur a non-zero number of mistakes.

5 Lower Bounds

We first show that Theorem 2 is best possible: the Degree ranking really can make twice as many mistakes as the adversary. Recall that f denotes the number of winner–loser pairs where the loser beats the winner, and g the number of winner– loser pairs where the loser outranks the winner. The example below generates an infinite family of tournaments with g = 2f.

Example 1. With n odd, let every vertex have degree (n − 1)/2; note that the degree sequence ⟨\frac{n−1}{2}, …, \frac{n−1}{2}⟩ does indeed respect Landau’s condition, so it is realizable as a tournament. Label (n−1)/2 of the vertices as winners and (n+1)/2 as losers. With ties broken against us, all winners are ordered after all losers. This gives f = \frac{n+1}{2} · \frac{n−1}{2} − \binom{(n+1)/2}{2} = (n + 1)(n − 1)/8, while g = \frac{n+1}{2} · \frac{n−1}{2} = (n + 1)(n − 1)/4 = 2f. (A similar example gives a lower bound of 2 − O(1/n) with ties broken optimally for the algorithm.)

In a subsequent paper, Ailon and Mohri [AM07] give a simple algorithm-independent example showing that no deterministic algorithm can achieve a constant factor of less than 2 on the regret ratio. The example puts all the probability mass on a single three element subset. The induced tournament is a directed 3-cycle, and the bipartition is chosen adversarily depending on the ordering output by the algorithm. By symmetry, there are only two different orderings (clockwise and counterclockwise). In both cases, the adversary can make the algorithm pay for both mixed pairs while paying for only one misordering. This example implies that Theorem 4 is also best possible.^{5}

6 Generalization to Multipartite Ranking

The result in Section 3 can be extended to the case when examples belong to more than two classes. In the extreme case, all examples can have different labels. The labels typically form an ordered set, arising naturally in applications where labels represent discretized ratings (e.g., survey results can be graded from ‘strongly agree’

5 The preliminary version of this paper contained a construction of a family of tournaments, for which an optimal solution to the feedback arc set problem gives g ≥ (2−ϵ)f, for any ϵ > 0. We decided to omit the construction since it is superseded by the above lower bound example in [AM07].

to ‘strongly disagree’, search results can be graded from ‘most relevant’ to ‘least relevant’).

A natural way of extending the definition of ranking loss to account for the order in the values, is to weigh the loss of putting an example with label y_{j} before an example with label y_{i} < y_{j} by the difference y_{j} −y_{i}. Formally, the generalized AUC loss of an ordering π on a set S = (1, y_{1}), …, (n, y_{n}) is defined as

l(π, S) = \frac{∑_{i≠j} π(i, j, \{1, …, n\})(y_{i} − y_{j})_{+}}{∑_{i<j} |y_{i} − y_{j}|} ,

where we use the operator (A)_{+} = A · 1(A > 0).

As in the bipartite case, let Q denote the distribution of label sequences of the set {1, …, n}. Then the generalized loss of ordering i before j is

l_{Q}(i, j) = E_{y^{n}∼Q} \frac{(y_{i} − y_{j})_{+}}{∑_{u<v} |y_{u} − y_{v}|}.

Regrets are defined as before. Recall that r_{Q}(i, j) is proper if l_{Q}(i, j) − l_{Q}(j, i) ≥ 0.

The lemma below extends Lemma 1 to multiple labels.

Lemma 2. For any i, j, and k in {1, …, n}, if r_{Q}(i, j) and r_{Q}(j, k) are proper,

r_{Q}(i, j) + r_{Q}(j, k) = r_{Q}(i, k).

Proof. Consider any label assignment y^{n} = y_{1} … y_{n} and let Z(y^{n}) = \frac{Q(y^{n})}{∑_{u<v} |y_{u}−y_{v}|}.

A simple case analysis shows that y^{n} contributes equally to both sides of the lemma statement. Indeed, if y_{i} ≤ y_{j} ≤ y_{k}, the contribution is zero to either side. If y_{i} ≥ y_{j} ≥ y_{k}, it contributes Z(y^{n})((y_{i} − y_{j}) + (y_{j} − y_{k})) to r_{Q}(i, j) + r_{Q}(j, k) and Z(y^{n})(y_{i} − y_{k}) to r_{Q}(i, k), so the contributions are equal. It remains to consider two cases.

Case 1, y_{i} ≤ y_{j} and y_{j} ≥ y_{k}. The contribution of y^{n} to the left side is Z(y^{n})[−(y_{j} − y_{i}) + (y_{j} − y_{k})]. If y_{i} ≤ y_{k}, it adds Z(y^{n})(y_{k} − y_{i}) to l_{Q}(k, i); otherwise, it adds Z(y^{n})(y_{i} −y_{k}) to l_{Q}(i, k). In both cases, its contribution to the right side, l_{Q}(i, k)− l_{Q}(k, i), is Z(y^{n})(y_{i} − y_{k}), and so the contributions are equal.

Case 2, y_{i} ≥ y_{j} and y_{j} ≤ y_{k}. Similarly to Case 1, y^{n} donates Z(y^{n})[(y_{i} − y_{j}) − (y_{k} −y_{j})] to the left side, and Z(y^{n})(y_{i} −y_{k}) to the right side, completing the proof.

The proof of Theorem 1 carries through without modifications, using the generalized definition of losses and regrets and Lemma 2 in place of Lemma 1.

7 Relation to Generalization Bounds and Other Work

A number of papers analyze generalization properties of ranking algorithms (see, e.g., [FIS+03,AHR05,AN05,CLV05,RCM+05]). These papers analyze ranking directly by estimating the rate of convergence of empirical estimates of the ranking loss to its expectation. The bounds typically involve some complexity parameter of the class of functions searched by the algorithms (which serves as a regularizer), and some additional quantities considered relevant for the analysis. The examples are assumed to be drawn independently from some fixed distribution.

The type of results in this paper is different. We bound the realized AUC performance in terms of the realized classification performance, thus transferring performance from classification to ranking. Since the analysis is relative, it does not have to rely on any assumptions about the way the world produces data. In particular, the bounds apply when there are arbitrary high-order dependencies between examples, which is important in a number of applications where ranking is of interest.

Cortes and Mohri [CM04] analyzed the relationship between the AUC and the error rate on the same classification problem, treating the two as different loss functions. They derived expressions for the expected value and the standard deviation of the AUC over all classifications with a fixed number of errors, under the assumption that all such classifications are equiprobable (i.e., the classifier is as likely to err on any one example as on any other). There is no connection with the present work.

Acknowledgement We would like to thank COLT reviewers for their comments and suggestions, and Nir Ailon and Mehryar Mohri for helpful discussions.

References

[AHR05] S. Agarwal, S. Har-Peled, and D. Roth. A uniform convergence bound for the area under the ROC curve, Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, 2005.

[AN05] S. Agarwal, P. Niyogi. Stability and generalization of bipartite ranking algorithms, Proceedings of the Eighteenth Annual Conference on Computational Learning Theory (COLT), 32–47, 2005.

[AM07] N. Ailon and M. Mohri. An Efficient Reduction of Ranking to Classification, New York University Technical Report TR-2007-903, 2007.

[A06] N. Alon. Ranking tournaments, SIAM Journal on Discrete Mathematics 20: 137–142, 2006.

[BCS06] N. Bansal, D. Coppersmith, and G.B. Sorkin. A winner–loser labeled tournament has at most twice as many outdegree misrankings as pair misrankings, IBM Research Report RC24107, Nov. 2006.

[CLV05] S. Clémençon, G. Lugosi, N. Vayatis. Ranking and scoring using empirical risk minimization, Proceedings of the Eighteenth Annual Conference on Computational Learning Theory (COLT), 1–15, 2005.

[CSS99] W. Cohen, R. Schapire, and Y. Singer. Learning to order things, Journal of Artificial Intelligence Research 10: 243–270, 1999.

[CFR06] D. Coppersmith, L. Fleischer and A. Rudra. Ordering by weighted number of wins gives a good ranking for weighted tournaments. Proceeding of the 17th Annual Symposium on Discrete Algorithms (SODA), 776–782, 2006.

[CM04] C. Cortes and M. Mohri. AUC optimization versus error rate minimization, Advances in Neural Information Processing Systems (NIPS), 2004.

[FIS+03] Y. Freund, R. Iyer, R. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences, J. of Machine Learning Research 4: 933–969, 2003.

[Lan53] H. Landau. On dominance relations and the structure of animal societies: III. The condition for a score structure, Bull. Math. Biophys., 15: 143–148, 1953.

[LZ05] J. Langford and B. Zadrozny. Estimating Class Membership Probabilities Using Classifier Learners, Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, 2005.

[MO79] A. Marshall and I. Olkin. Inequalities: Theory of majorization and its applications, Mathematics in Science and Engineering, 143, New York, 1979.

[RCM+05] C. Rudin, C. Cortes, M. Mohri, and R. Schapire. Margin-based ranking meets Boosting in the middle, Proceedings of the Eighteenth Annual Conference on Computational Learning Theory (COLT), 2005.

[Sla61] P. Slater. Inconsistencies in a schedule of paired comparisons, Biometrika 48, 303–312, 1961.