Uniform Convergence, Stability and Learnability for Ranking Problems

1 Introduction

The most central issue in learning theory focuses on the problem of characterizing learnability. The fundamental work [Blumer et al., 1989; Alon et al., 1997], at least for supervised classification and regression, showed that learnability is equivalent to the uniform convergence of the empirical risk to the expected risk, and that if a problem is learnable, it is learnable with ERM (Empirical Risk Minimizer). Uniform convergence, however, does not hold in the general learning setting [Alon et al., 1997; Vapnik, 1998], and Shalev-Shwartz et al. [2010] established stability as a sufficient and necessary condition for learnability.

Ranking problems try to learn a real-valued function so as to assign scores to instances, and then a relative ranking of instances is derived based on these scores. What is important is the relative rankings rather than the scores themselves. For example, Alice would like to search for documents that are relevant to a given topic, and what she wants is a ranked list in which the relevant documents are placed higher than irrelevant ones, no matter which score is assigned to which document. During the past decade, ranking problems have attracted much attention and have been found useful in various applications. Considering that ranking is quite different from traditional learning settings such as classification and regression, it is interesting to study what conditions can be used to characterize the learnability of ranking.

∗This research was supported by 973 Program (2010CB327903), NSFC (61073097, 61021062) and Baidu Fund (181315P00651).

In this paper, we show that the ranking uniform convergence is sufficient but not necessary for ranking learnability with AERM (Asymptotic Empirical Risk Minimizer), and further present a sufficient condition for ranking uniform convergence with respect to the bipartite ranking loss, which is used commonly in literature. Then, we explore ranking stability as an alternative tool to characterize the ranking learnability in place of ranking uniform convergence. We show that the previous uniform stability is not necessary for ranking learnability, and thus introduce the average stability and prove that it is sufficient and necessary for learnability of ranking. This characterization holds even for ranking problems without ranking uniform convergence, and thus we provide a more convenient tool than ranking uniform convergence to characterize the learnability of ranking problems.

The rest of this paper is organized as follows. Section 2 introduces the related work and Section 3 provides background. Section 4 discusses the relationships between the ranking uniform convergence and ranking learnability. Section 5 introduces the ranking average stability and proves its equivalence with learnability. Section 6 concludes with future work.

2 RelatedWork

The study on ranking can be traced back to 1970's in social choice theory [Arrow, 1970] and some statistics research [Lehmann, 1975], while early studies on learning to rank in the machine learning community could be dated back to Cohen et al. [1999]. Many studies have been devoted to designing efficient algorithms for ranking problems under different settings, e.g., the online ranking algorithm [Crammer and Singer, 2002; Weng and Lin, 2011], neural network algorithm [Burges et al., 2005], boosting-style algorithms [Cohen et al., 1999; Freund et al., 2003; Rudin and Schapire, 2009], univariate loss algorithms [Kotlowski et al., 2011], regression algorithms [Herbrich et al., 2000], listwise approaches [Cao et al., 2007], etc. Considering that most approaches work with convex surrogate loss functions, many studies have been devoted to the asymptotic consistency of ranking approaches based on surrogate loss functions [Cl´emenc¸on et al., 2008; Duchi et al., 2010; Gao and Zhou, 2012].

Various generalization bounds have been developed to estimate the ranking performance of algorithms beyond training data based on different measures such as VC-dimension and cover number [Freund et al., 2003; Agarwal et al., 2005; Rudin and Schapire, 2009; Wang et al., 2012]. In place of function space, Agarwal and Niyogi [2009] presented a new generalization bound based on the ranking uniform stability, whereas such stability is proven to be far from necessary for ranking learnability, as shown by Example 1 (Section 5.1).

Learnability has always been one of the most central issues in machine learning, whereas the traditional work [Blumer et al., 1989; Alon et al., 1997; Shalev-Shwartz et al., 2010] can not be applied directly to ranking problems since the ranking loss is based on pairwise instances from different classes rather than single instance. Therefore, Agarwal and Roth [2005] presented the first work on ranking learnability by providing a sufficient condition and a necessary condition, separately, for ranking learnability based on two different measures of function space. To the best of our knowledge, our work presents the first sufficient and necessary condition for ranking learnability, and such characterization does not rely on any space complexity measure, but rather on the way the algorithm searches.

3 Background

The bipartite ranking problem focuses on two classes, i.e., a positive class and a negative class, where the objective is to learn a real-valued function to rank future positive instances higher than negative ones. Formally, let X be an instance space and assume that positive instances are chosen randomly and independently (i.i.d.) according to some (unknown) underlying distribution D+ over X, and negative instances are chosen similarly according to some (unknown) underlying distribution D- over X. A ranking problem is specified by a real-valued function class H, an instance space X with respect to distributions D+ and D-, and a cost (e.g., "loss" and "objective") function c: H×X ×X → R, where it aims to minimize the expected risk

over the class H. Distributions D+ and D- are unknown, and what we have is a training sample (S+, S-) with

being sampled i.i.d. according to distributions D+ and D-, respectively. Based on this sample, we can define the empirical risk ˆR(h, S+, S-), with respect to h ∈ H, to be

Formally, a (deterministic) ranking algorithm is a mapping A : ∪∞m=1 X m × ∪∞n=1X n → H from training sample (S+, S-) to a real-valued function AS+,S- : X → R, where AS+,S- ∈ H.

Throughout this paper, we consider symmetric ranking algorithms, i.e., algorithms depending upon the given training sample but not on the order of instances in the training sample, and we assume that the cost function is bounded by some constant B, i.e.,

The bipartite ranking loss, which is commonly studied in literature for bipartite ranking problems, is:

where I[·] denotes the indicator function which returns one if its argument is true and zero otherwise. Based on this cost function, the empirical risk ˆR(h, S+, S-) becomes an evaluation criterion, Area Under the ROC Curve (AUC), with respect to function h on the training sample (S+, S-), which has been studied in detail [Cortes and Mohri, 2003; Agarwal et al., 2005].

A ranking algorithm would like, in essence, to pick a realvalued function h ∈ H such that its expected risk approaches the minimal expected risk, i.e.,

where we denote by h∗ = arg infh∈HR(h). Since distributions D+ and D- are unknown but demonstrated by training sample (S+, S-), a natural method is to minimize the empirical ˆR(h, S+, S-). A ranking algorithm A is said to be an ERM (Empirical Risk Minimizer) if it minimizes the empirical risk, i.e.,

A ranking algorithm A is said to be an AERM (Asymptotic Empirical Risk Minimizer) with rate ϵerm(m, n) under distributions D+ and D- if

where we denote by ˆhS+,S- = arg infh∈H ˆR(h, S+, S-).

A ranking algorithm is universally an AERM with rate ϵerm(m, n) if it is an AERM with rate ϵerm(m, n) under all distributions D+ and D- over X. Here and wherever mentioning about ϵ(m, n), it requires ϵ(m, n) → 0 as m, n → ∞. Note that ERM is a special case of AERM and we will mainly focus on AERM in this paper.

A ranking algorithm A is said to be consistent with rate ϵcon(m, n) under distributions D+ and D- if

A ranking algorithm A is universally consistent with rate ϵcon(m, n) if it is consistent with rate ϵcon(m, n) under all distributions D+ and D- over X. Based on this definition, we give the following notion of ranking learnability:

Definition 1 A bipartite ranking problem with real-valued class H is learnable if there exists a universally consistent algorithm for such problem, i.e., there exists a ranking algorithm A and rate ϵcon(m, n) such that

where ϵcon(m, n) → 0 as m, n → ∞.

4 UniformConvergence and Learnability

In this section, we study the relationship between ranking uniform convergence and ranking learnability. Our result shows that ranking uniform convergence is sufficient but not necessary for ranking learnability. For bipartite ranking loss, we present a sufficient condition for uniform convergence.

We introduce the ranking uniform convergence as follows:

Definition 2 For a ranking problem with real-valued function class H, the ranking uniform convergence holds with rate ϵuni-con(m, n) if

where ϵuni-con(m, n) → 0 as m, n → ∞.

By using the facts

and ˆR(ˆhS+,S- , S+, S-) ≤ ˆR(h∗ , S+, S-), we have

Lemma 1 For a ranking problem with real-valued function class H, if the ranking uniform convergence holds with rate ϵuni-con(m, n), then, for an AERM with rate ϵerm(m, n), this ranking problem is learnable with rate ϵcon(m, n) = 2ϵuni-con(m, n) + ϵerm(m, n).

This lemma states that ranking uniform convergence implies ranking learnability with AERM, and such ranking problem is learnable. However, it is not a necessary condition owing to some "trivial" situations: for a ranking problem with function class H that could be extremely complex without ranking uniform convergence, we add a single function ˜h such that c(˜h, x+, x-) < infh∈H c(h, x+, x-), as shown in Figure 1. This ranking problem is now trivially learnable with ERM which always picks ˜h, yet the ranking uniform convergence does not hold. To exclude such cases, one could, inspired from [Vapnik, 1998], introduce stronger notions such as strict ranking consistency and one-side uniform convergence 1 , whereas we will present a different tool to study the ranking learnability in Section 5.2.

In the following of this section, we focus on the bipartite ranking loss given by Eq. (1) and explore a sufficient condition for ranking uniform convergence. Let us recall a combinatorial parameter: bipartite rank-shatter coefficient [Agarwal et al., 2005], defined below with our notations.

Definition 3 (Bipartite rank-shatter coefficient) For positives m and n, and a ranking problem with function class H, the (m, n)-th bipartite rank-shatter coefficient is

where Bh(S+, S-) is a matrix, whose (i, j) element

This coefficient plays the similar role as the shatter coefficient plays in binary classification. We present the following sufficient condition for ranking uniform convergence, analogous to the third milestone in learning theory [Vapnik, 1998].

Theorem 1 For a ranking problem with real-valued function class H, the ranking uniform convergence holds if

as m, n → ∞. Specifically, the ranking uniform convergence holds with rate

if r(H, 2m, 2n) is finite as m, n → ∞; otherwise

Proof For any ϵ > 0 and distributions D+ and D-, we have

from [Agarwal et al., 2005, Theorem 17]. Further, we set ϵ = 4√(m+ n)/mn if r(H, 2m, 2n) is finite as m, n → ∞; otherwise, ϵ = √16G(m, n). By using the formula

this theorem follows by simple calculation.

It is easy to observe that G(m, n) → 0 is equivalent to

as m, n → ∞; therefore, we have Corollary 1 For a ranking problem with function class H, the ranking uniform convergence holds if, as m, n → ∞,

1 Due to space limit, we omit the detailed discussion on strict ranking consistency and one-side uniform convergence, and also omit some detailed proofs of results such as Lemma 1 and Theorem 1. We will present them in a longer version.

Combining Lemma 1 with Theorem 1, we establish the relationships among G(m, n), ranking uniform convergence and ranking learnability, as shown in Figure 2. It is, however, not clear whether ranking uniform convergence implies limm,n→∞G(m, n) = 0, and thus we leave the following open problem:

Problem 1 Does limm,n→∞G(m, n) equal to zero if the ranking uniform convergence holds?

5 Ranking Stability and Learnability

Section 5.1 shows that previous uniform stability is not necessary for ranking learnability and introduces average stability. Section 5.2 proves our main result: a ranking problem is learnable if and only if there exists a universally average stable AERM.

5.1 Ranking Stability

Given a sample (S+, S-) ∈ X m × X n with

we define, for i ∈ [m] and z+ ∈ X,

to be the sample with the i-th instance x+i in S+ replaced by another z+. Similarly, we can define Sj,z- . For real number α, we denote by ⌊α⌋ the biggest integer smaller than α.

Several notions of stability have been proposed to study the performance of learning algorithms [Kearns and Ron, 1999; Bousquet and Elisseeff, 2002; Rakhlin et al., 2005; Mukherjee et al., 2006; Gao and Zhou, 2010]. For bipartite ranking, Agarwal and Niyogi [2009] gave the definition of ranking uniform stability, which is equivalent to

Definition 4 A ranking algorithm A has ranking uniform stability β(m, n) if the it holds that, for any i ∈ [m], j ∈ [n], (S+, S-) ∈ X m × X n , and x+, x-, z+, z- ∈ X 4

where β(m, n) → 0 as m, n → ∞.

The ranking uniform stability, which could be a stronger notion, is enough for tight generalization error bounds, and Agarwal and Niyogi [2009] established such stability for some kernel-based ranking algorithms. It is, however, far from necessary for ranking learnability, as shown by the following Example.

Example 1 There exists a ranking problem with a universally consistent algorithm without ranking uniform stability.

Proof Let X = [-1, 1], H = {hθ : hθ(x) = I[x ≥ θ]} for θ ∈ [-1, 1], the objective t(x) = I[x ≥ 0] and the cost function is given by Eq. (1). Given a sample (S+, S-) ∈ [0, 1]m × [-1, 0)n with S- = {x-1 , x-2 , · · · , x-n }, we set θ∗ = max{x-1 , x-2 , · · · , x-n } and consider the algorithm

For any hθ ∈ H and distributions D+ and D-, it is easy to derive hθ(x+) ≥ hθ(x-) and R(hθ) = Pr[θ ≤ x- < 0]/2. This follows that, for any ϵ ≥ 0,

It is clear that

and combining with Eqn. (2) together, the following holds by setting ϵ = 1/√n,

which proves that AS+,S- is universally consistent.

On the other hand, if we choose an instance z- satisfying max{x-1 , x-2 , · · · , x-n } < z- < 0, then, for any instance xsuch that max{x-1 , x-2 , · · · , x-n } < x- < z-, it holds

which implies that this ranking algorithm has no uniform stability, and thus we complete the proof.

Our weaker notion of stability, which is equivalent to ranking learnability with AERM (proved later), is

Definition 5 A ranking algorithm A has ranking average stability β(m, n) under distributions D+ and D- if, for all i ∈ [m] and j ∈ [n], the following holds:

where β(m, n) → 0 as m, n → ∞.

A ranking algorithm has universally average stability with rate β(m, n) if the stability property holds with rate β(m, n) under all distributions D+ and D-. It is obvious that

Proposition 1 Ranking uniform stability implies ranking average stability.

5.2 Sufficient and Necessary Condition for Ranking Learnability

We begin with a useful lemma as follows:

Lemma 2 For a ranking problem with real-valued function class H, the following holds for every h ∈ H independent of sample (S+, S-),

Proof We first have

for index i ∈ [m] and instance x+ drawn i.i.d. fromD+. In a similar manner,

Based on [Devroye, 1991, Theorem 3], we have

which completes the proof by using Jensen's inequality.

Based on this lemma, we present the first main result:

Theorem 2 For an AERM A with rate ϵerm(m, n), if it has ranking average stability with rate β(m, n) under distributions D+ and D-, then it is consistent with rate

Proof For an AERMA , we have

from Lemma 2 and ˆR(ˆhS+,S- , S+, S-) ≤ ˆR(h∗ , S+, S-). For symmetric algorithm, we have, for all i ∈ [m], j ∈ [n],

by interchanging the roles of x+i , x-j with x+, x-, respectively. Similarly, we have

Combining Eqs. (3) and (4) gives

This completes the proof.

This theorem shows that an average stable AERM is sufficient for consistency under each pair of distributions D+ and D-, and it does not require the universality. Based on this theorem, we have

Corollary 2 A ranking problem is learnable if there exists a universally average stable AERM.

For Theorem 2, we find that the reverse direction does not hold under specific pair of distributions D+ and D-, which can be shown by following example:

Example 2 There exists a ranking problem and distributions D+ and D-, such that any ERM (or any AERM) is consistent but not average stable.

Proof Let the instance space X = [-1, 1], the objective ranking t(x) = I[x ≥ 0], and distributions D+ and D- be any two continuous distributions on [0, 1] and [-1, 0), respectively. We consider the bipartite ranking loss given by Eq. (1) and the hypothesis space

where

For any h ∈ H, we have R(h) = 1 for the continuous distributions D+ on [0, 1] and thus this ranking algorithm is consistent. On the other hand, an ERM always achieves

which implies that ERM (or any AERM) is not ranking average stable. This completes the proof.

Example 2 shows that a consistent ERM does not imply ranking average stability under the specific pair of distributions D+ and D-, whereas the universal consistency implies the existence of average stable AERMs as follows:

Theorem 3 For a ranking problem with a universally consistent algorithm A with rate ϵcon(m, n), there must exist a ranking algorithm ˆ A such that ˆ A is universally an AERM with rate ϵerm(m, n) and universally ranking average stable with rate ˆ β(m, n), where

Proof Given a sample (S+, S-) ∈ X m ×X n , let ( ˆ S+, ˆ S-) ∈ X ⌊m 1 4 ⌋ × X ⌊n 14 ⌋ be drawn uniformly from S+ and S-, respectively, and define ˆ AS+,S- = Aˆ S+, ˆ S- . We have

where τ1 = m - ⌊m 1 4 ⌋ and τ2 = n - ⌊n 14 ⌋. The first three terms are bounded by cost function |c(h, x+, x-)| ≤ B and the last term can be bounded by Lemma 2 since Aˆ S+, ˆ S- is independent of S+\ ˆ S+ and S-\ ˆ S-. Thus, we obtain

where β(m, n) = 2B m 34 n 34 + 2B m 34 + 2B m 3 4 + B√ 2m + 2n for m ≥ 3 and n ≥ 3. Combining Eqs. (3) with (4), we have

where the last inequality holds from Eq. (5). This shows that ˆ A is average stable with rate β(m, n).

We will use the universal consistency of A to prove that ˆ A is an AERM. Denote by the random event

and it is easy to derive that

Also, we denote by the random event

If ˆ S+ and ˆ S- have no repeated instances from S+ and S-, then S′+ and S′- can be viewed as samples drawn from the uniform distribution over instance in S+ and S-, respectively. Therefore, for universally consistent A , we have

From the formula E[X] = E[X|A] Pr[A] + E[X|B] Pr[B], and by using Eqs. (6), (7) and |c(h, x+, x-)| ≤ B, we have

This theorem follows as desired.

Corollary 2 presents a sufficient condition for ranking learnability, and Theorem 3 shows that such condition is also a necessary condition; therefore, we present a sufficient and necessary condition for ranking learnability as follows:

Theorem 4 A ranking problem is learnable if and only if there exists a universally average stable AERM.

6 Conclusion and FutureWork

Learning to rank has attracted much attention during the past decade, where bipartite ranking is a commonly studied problem setting. Compared to traditional learning settings such as classification and regression, the main difference of bipartite ranking problems lies in the loss function which is based on pairwise instances from different classes in ranking rather than single instance. Due to the dependence of instance pairs, the characterization of learnability for traditional learning setting could not be applied directly to ranking. Therefore, it is desirable to find sufficient and necessary conditions for characterizing the learnability of ranking, and previous work [Agarwal and Roth, 2005] presented a sufficient condition and a necessary condition for ranking learnability, separately, based on two different measures of function space.

In this paper, we show that the ranking uniform convergence is sufficient but not necessary for ranking learnability with AERM. For the special bipartite ranking loss, we provide a sufficient condition for ranking uniform convergence, that is

This condition can be as analogous to the third milestone in learning theory [Vapnik, 1998]. We have not, however, proved that ranking uniform convergence implies G(m, n) → 0, and leave it as an open problem in Problem 1. A possible solution could be motivated from [Blumer et al., 1989] by considering the bipartite rank-shatter coefficient or introducing some new combinatorial parameters.

Considering the ranking uniform convergence is not necessary for ranking learnability, we establish ranking average stability as a sufficient and necessary condition for ranking learnability by proving that ranking learnability is equivalent to ranking average stability with AERM. One important direction for future research is to characterize the learnability of other ranking problems under different settings such as listwise ranking setting [Cao et al., 2007], pointwise ranking setting [Cossock and Zhang, 2008] and the k-height ranking setting [Rudin, 2009].