An Efficient Boosting Algorithm for Combining Preferences

Yoav FreundRaj IyerRobert E. SchapireYoram Singer

article1998JMLR2,236 citations

Introduces RankBoost, a foundational boosting algorithm that efficiently combines multiple weak preference orderings into an accurate global ranking with proven training bounds and generalization guarantees across tasks like meta-search and collaborative filtering.

Listen

Modern digital systems frequently face the challenge of combining multiple distinct rankings into a single, high-quality ordered list. In practical domains such as web search aggregation (meta-search) and collaborative filtering for recommendation engines, users express preferences on different numerical scales, and systems may only provide partial orderings. Existing approaches often rely on absolute numerical scores or computationally intractable optimization methods, creating a pressing need for efficient algorithms that learn directly from relative ordering preferences.

The article introduces and evaluates RankBoost, an efficient machine learning algorithm designed to combine multiple weak ranking rules into a highly accurate combined ranking function. The objective was to demonstrate the theoretical soundness, computational scalability, and empirical effectiveness of RankBoost across diverse ranking benchmarks compared to established baselines.

The researchers formulated a mathematical framework for preference learning based on pair misorderings and proved theoretical bounds for training and generalization error. They developed specialized, linear-time implementations for binary rankings and bipartite feedback settings, in which items are categorized into preferred versus non-preferred groups. To test practical performance, the authors conducted two primary empirical evaluations: a web meta-search task combining query expansions across two query sets (210 machine learning and 290 university queries), and a movie recommendation task using the EachMovie dataset containing 2.8 million ratings from over 61,000 viewers, comparing RankBoost against linear regression, nearest-neighbor, and vector similarity baselines across varying feature sizes and data densities.

The key findings demonstrate that RankBoost reliably outperforms or matches alternative techniques. First, in the movie recommendation experiment, RankBoost achieved lower pair disagreement and superior precision metrics compared to linear regression and nearest neighbors across all feature set sizes. Second, while vector similarity performed comparably or slightly better on small feature sets (up to 200 features) and sparse feedback, RankBoost scaled significantly better as the number of features grew from 100 to 2,000 and as feedback density increased, whereas vector similarity plateaued or degraded. Third, in the meta-search domain, RankBoost closely tracked or exceeded the single best query template across top-ranked cutoffs, achieving a superior average rank (4.38 compared to 5.33–6.80 for individual templates in the machine learning domain). Finally, enforcing positive cumulative weights on binary weak rankings successfully prevented overfitting on test data, outperforming unconstrained variants.

These results indicate that prioritizing relative orderings rather than raw numerical scores provides substantial performance advantages in collaborative filtering and search retrieval. Because the algorithm avoids the NP-complete combinatorial bottlenecks of previous ranking frameworks and scales linearly in common retrieval scenarios, organizations can deploy it in high-throughput production systems with lower computational risk and improved recommendation quality. Unlike fixed correlation methods, RankBoost adapts dynamically as user feedback volume expands.

Organizations developing ranking and recommendation platforms should consider adopting RankBoost or incorporating correlation-based methods into RankBoost as weak learners to create hybrid models that perform well on both small and large datasets. Prior to deployment, teams should evaluate their problem structure to exploit bipartite feedback optimizations and test whether constraining weak ranking weights to positive values improves out-of-sample generalization.

While the empirical and theoretical results provide high confidence in RankBoost’s effectiveness, the findings are subject to certain boundaries: baseline regression and nearest-neighbor methods were tested in specific configurations that may not reflect alternative normalizations, and precision metrics were shown to be inherently sensitive to total feedback volume. Further pilot testing is advisable when applying the framework to non-bipartite feedback scenarios or domains with noisy user feedback.

Center for Computational Learning Systems Columbia University Living Wisdom School Princeton University The Hebrew University of Jerusalem efficient algorithm formal framework query expansion RankBoost algorithm collaborative filtering binary weak rankings

Freund et al (1998).pdf

Paper: Experiments with a New Boosting Algorithm, Yoav Freund et al. (1996). This foundational paper introduces the original AdaBoost algorithm that RankBoost directly generalizes to preference learning and ranking tasks.

Paper: Learning to rank using gradient descent, Chris Burges et al. (2005). This work extends preference learning from boosting frameworks to neural network gradient descent for web search ranking.

Cover for An Efficient Boosting Algorithm for Combining Preferences

Abstract

We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several applications, such as that of combining the results of different search engines, or the “collaborative-filtering” problem of ranking movies for a user based on the movie rankings provided by other users. In this work, we begin by presenting a formal framework for this general problem. We then describe and analyze an efficient algorithm called RankBoost for combining preferences based on the boosting approach to machine learning. We give theoretical results describing the algorithm’s behavior both on the training data, and on new test data not seen during training. We also describe an efficient implementation of the algorithm for a particular restricted but common case. We next discuss two experiments we carried out to assess the performance of RankBoost. In the first experiment, we used the algorithm to combine different web search strategies, each of which is a query expansion for a given domain. The second experiment is a collaborative-filtering task for making movie recommendations.

Topics

efficient algorithm formal framework query expansion recommendation theoretical result user preferences web searches collaborative filtering weak learner preference information

Keywords

RankBoost algorithm collaborative filtering binary weak rankings relative preferences partial order multiple rankings

1. Introduction
2. A Formal Framework for the Ranking Problem
2.1 Example: Meta-search
3. A Boosting Algorithm for the Ranking Task
3.1 The RankBoost Algorithm
3.2 Choosing αt and Criteria for Weak Learners
3.3 An Efficient Implementation for Bipartite Feedback
4. Finding Weak Rankings
5. Generalization Error
5.1 Probabilistic Model
5.2 Sampling Error Definitions
5.3 VC Analysis
6. Experimental Evaluation of RankBoost
6.1 Meta-search
6.1.1 DESCRIPTION OF TASK AND DATA SET
6.1.2 EXPERIMENTAL PARAMETERS AND EVALUATION
6.2 Movie Recommendations
6.2.1 DESCRIPTION OF TASK AND DATA SET
6.2.2 EXPERIMENTAL PARAMETERS
6.2.3 ALGORITHMS FOR COMPARISON
6.2.4 PERFORMANCE MEASURES
6.2.5 EXPERIMENTAL RESULTS
6.2.6 DISCUSSION
7. Conclusion
Acknowledgements
Appendix A. Performance Measures for the Movie Task
References

Knowls

Knowl 1 — The RankBoost Algorithm
algorithm
RankBoost is a boosting algorithm designed to learn an accurate ranking function over an instance space $X$ by combining a collection of weak ranking functions. The learning problem is defined over an initial probability distribution $D$ on pairs of instances $X \times X$ , where $D(x_0, x_1) > 0$ indicates that instance $x_1$ should be ranked higher than instance $x_0$ .

At each boosting round $t = 1, \dots, T$ , RankBoost supplies the current distribution $D_t$ over pairs to a weak learner, which returns a weak ranking $h_t: X \to \mathbb{R}$ . RankBoost selects a weight parameter $\alpha_t \in \mathbb{R}$ and updates the distribution: pairs misordered by $h_t$ (where $h_t(x_1) \le h_t(x_0)$ ) have their weights increased, while correctly ordered pairs (where $h_t(x_1) > h_t(x_0)$ ) have their weights decreased. A normalization factor $Z_t$ ensures $D_{t+1}$ is a valid probability distribution. After $T$ rounds, the final ranking scoring function is $H(x) = \sum_{t=1}^T \alpha_t h_t(x)$ , which ranks instance $x_1$ above $x_0$ whenever $H(x_1) > H(x_0)$ .

The general implementation of RankBoost requires $O(|\Phi|)$ time and space per round, where $|\Phi|$ is the number of pairs $(x_0, x_1)$ with non-zero initial feedback weight.
Input: Initial distribution $D$ over pairs $X \times X$ , weak learner procedure, number of rounds $T$
Output: Combined scoring function $H: X \to \mathbb{R}$
Initialize $D_1(x_0, x_1) = D(x_0, x_1)$ for all $(x_0, x_1) \in X \times X$
for $t = 1$ to $T$ do
    Train weak learner using pair distribution $D_t$
    Receive weak ranking $h_t: X \to \mathbb{R}$
    Choose weight $\alpha_t \in \mathbb{R}$
    Compute normalization factor:
         $Z_t = \sum_{x_0, x_1} D_t(x_0, x_1) \exp(\alpha_t (h_t(x_0) - h_t(x_1)))$
    Update distribution for all $(x_0, x_1) \in X \times X$ :
         $D_{t+1}(x_0, x_1) = \frac{D_t(x_0, x_1) \exp(\alpha_t (h_t(x_0) - h_t(x_1)))}{Z_t}$
end for
return $H(x) = \sum_{t=1}^T \alpha_t h_t(x)$
Knowl 2 — Training Loss Bound for RankBoost
theoretical result
Let $X$ be an instance space, and let $D$ be a probability distribution over pairs $(x_0, x_1) \in X \times X$ representing the preference that $x_1$ should be ranked above $x_0$ . Let $H(x) = \sum_{t=1}^T \alpha_t h_t(x)$ be the combined scoring function produced after $T$ rounds of RankBoost with step sizes $\alpha_t \in \mathbb{R}$ and weak rankings $h_t: X \to \mathbb{R}$ .

The ranking loss of $H$ with respect to distribution $D$ is the expected probability of misordering a pair:

$\mathrm{rloss}_D(H) = \sum_{x_0, x_1 \in X} D(x_0, x_1) [[H(x_1) \le H(x_0)]] = \Pr_{(x_0, x_1) \sim D}[H(x_1) \le H(x_0)],$

where $[[\pi]]$ evaluates to 1 if predicate $\pi$ holds and 0 otherwise. This loss is upper-bounded by the product of the normalization factors $Z_t$ computed at each round:

$\mathrm{rloss}_D(H) \le \prod_{t=1}^T Z_t,$

where for each round $t \in \{1, \dots, T\}$ ,

$Z_t = \sum_{x_0, x_1 \in X} D_t(x_0, x_1) \exp(\alpha_t (h_t(x_0) - h_t(x_1))).$

This bound guarantees that choosing $\alpha_t$ and $h_t$ on each round to minimize $Z_t$ greedily minimizes an upper bound on the training ranking loss.
Knowl 3 — RankBoost for Bipartite Feedback (RankBoost.B)
algorithm
In bipartite feedback settings, the instance space $X$ contains two disjoint subsets: a negative set $X_0$ (unpreferred or irrelevant instances) and a positive set $X_1$ (preferred or relevant instances), where the objective is to rank every instance in $X_1$ above every instance in $X_0$ . A direct implementation of RankBoost requires $O(|X_0||X_1|)$ space and time per round.

RankBoost.B improves the per-round time and space complexity to $O(|X_0| + |X_1|)$ by decomposing the distribution over pairs into the product of two separate weight vectors over individual instances: $D_t(x_0, x_1) = v_t(x_0) v_t(x_1)$ for all $x_0 \in X_0$ and $x_1 \in X_1$ . The algorithm maintains individual instance weights $v_t(x)$ initialized uniformly over $X_0$ and $X_1$ , and updates them separately using normalization factors $Z_t^0$ and $Z_t^1$ such that the pair normalization factor satisfies $Z_t = Z_t^0 \cdot Z_t^1$ .
Input: Disjoint subsets $X_0$ and $X_1$ of instance space $X$ , number of rounds $T$
Output: Combined scoring function $H: X \to \mathbb{R}$
Initialize instance weights $v_1(x)$ :
    for each $x \in X_1$ do $v_1(x) = \frac{1}{|X_1|}$
    for each $x \in X_0$ do $v_1(x) = \frac{1}{|X_0|}$
for $t = 1$ to $T$ do
    Train weak learner using pair distribution $D_t(x_0, x_1) = v_t(x_0) v_t(x_1)$
    Receive weak ranking $h_t: X \to \mathbb{R}$
    Choose weight $\alpha_t \in \mathbb{R}$
    Compute normalization constants:
         $Z_t^1 = \sum_{x \in X_1} v_t(x) \exp(-\alpha_t h_t(x))$
         $Z_t^0 = \sum_{x \in X_0} v_t(x) \exp(\alpha_t h_t(x))$
    Update instance weights for next round:
        for each $x \in X_1$ do $v_{t+1}(x) = \frac{v_t(x) \exp(-\alpha_t h_t(x))}{Z_t^1}$
        for each $x \in X_0$ do $v_{t+1}(x) = \frac{v_t(x) \exp(\alpha_t h_t(x))}{Z_t^0}$
end for
return $H(x) = \sum_{t=1}^T \alpha_t h_t(x)$
Knowl 4 — Methods for Choosing Step Size and Base Ranker Criteria in RankBoost
model/method
In each round $t$ of RankBoost, the objective is to select a weak ranking $h$ and a step size $\alpha$ to minimize the normalization factor $Z = \sum_{x_0, x_1} D(x_0, x_1) \exp(\alpha(h(x_0) - h(x_1)))$ . Three analytical and numerical methods exist:
1. General Numerical Search: For an arbitrary real-valued weak ranking $h: X \to \mathbb{R}$ , $Z(\alpha)$ is strictly convex in $\alpha$ (except in trivial degenerate cases) and its unique minimum can be found numerically via binary search.
2. Exact Minimization for Binary Weak Rankings: When $h(x) \in \{0, 1\}$ , let the weights of misordered, tied, and correctly ordered pairs be:
$W_b = \sum_{x_0, x_1} D(x_0, x_1)[[h(x_0) - h(x_1) = b]] \quad \text{for } b \in \{-1, 0, +1\}.$

Abbreviating $W_{+1}$ as $W_+$ and $W_{-1}$ as $W_-$ , the normalization factor is $Z = W_- e^{-\alpha} + W_0 + W_+ e^\alpha$ . Minimizing $Z$ with respect to $\alpha$ yields:

$\alpha = \frac{1}{2} \ln \left( \frac{W_-}{W_+} \right), \quad \text{giving} \quad Z = W_0 + 2\sqrt{W_- W_+}.$
1. Approximation Method for Weak Rankings in $[0, 1]$ : Using the convexity bound $e^{\alpha x} \le \left(\frac{1+x}{2}\right) e^\alpha + \left(\frac{1-x}{2}\right) e^{-\alpha}$ for $x \in [-1, 1]$ , $Z$ is upper-bounded by:
$Z \le \left( \frac{1-r}{2} \right) e^\alpha + \left( \frac{1+r}{2} \right) e^{-\alpha},$

where $r = \sum_{x_0, x_1} D(x_0, x_1)(h(x_1) - h(x_0))$ . Minimizing this upper bound yields:

$\alpha = \frac{1}{2} \ln \left( \frac{1+r}{1-r} \right), \quad \text{which implies} \quad Z \le \sqrt{1 - r^2}.$

Under this method, the weak learner aims to maximize $|r|$ . If $r < 0$ , $\alpha$ becomes negative, naturally reversing the weak ranking.
Knowl 5 — Efficient Weak Ranking Selection via Potential Functions
algorithm
Given $n$ ranking features $f_1, \dots, f_n$ where each $f_i: X \to \mathbb{R} \cup \{\bot\}$ maps instances to scores or an abstention symbol $\bot$ , WeakLearn constructs binary weak rankings $h: X \to \{0, 1\}$ defined by a feature index $i$ , a threshold $\theta \in \mathbb{R}$ , and a default value $q_{\mathrm{def}} \in \{0, 1\}$ :

$h(x) = \begin{cases} 1 & \text{if } f_i(x) > \theta, \\ 0 & \text{if } f_i(x) \le \theta, \\ q_{\mathrm{def}} & \text{if } f_i(x) = \bot. \end{cases}$

To find the weak ranking maximizing $|r| = \left| \sum_{x_0, x_1} D(x_0, x_1)(h(x_1) - h(x_0)) \right|$ , the instance potential is defined as $\pi(x) = \sum_{x'} (D(x', x) - D(x, x'))$ . Because $\sum_{x} \pi(x) = 0$ , $r$ simplifies to:

$r = \sum_{x: f_i(x) > \theta} \pi(x) - q_{\mathrm{def}} \sum_{x \in X_{f_i}} \pi(x),$

where $X_{f_i} = \{x \in X_\Phi \mid f_i(x) \neq \bot\}$ , and $X_\Phi$ is the support of the feedback. Precomputing $\pi(x)$ takes $O(|\Phi|)$ time and $O(|X_\Phi|)$ space. Scanning candidate thresholds in sorted order allows evaluating all thresholds in $O(|\Phi| + \sum_{i=1}^n |X_{f_i}|) = O(|\Phi| + n|X_\Phi|)$ time. For bipartite feedback, $\pi(x) = d(x)s(x)$ can be computed in $O(|X_\Phi|)$ time, reducing the total running time to $O(n|X_\Phi|)$ .
Input: Distribution $D$ over $X \times X$ , ranking features $\{f_i\}_{i=1}^n$ , candidate thresholds $\{\theta_j\}_{j=1}^J$ with $\theta_1 = \infty > \dots > \theta_J = -\infty$ for each $f_i$ , ranked instance sets $X_{f_i}$
Output: Best weak ranking parameters $(i^*, \theta^*, q_{\mathrm{def}}^*)$
for each $x \in X_\Phi$ do
     $\pi(x) = \sum_{x' \in X_\Phi} (D(x', x) - D(x, x'))$
end for
$r^* = 0$
for $i = 1$ to $n$ do
     $L = 0$
     $R = \sum_{x \in X_{f_i}} \pi(x)$
     $\theta_0 = \infty$
    for $j = 1$ to $J$ do
         $L = L + \sum_{x: \theta_{j-1} \ge f_i(x) > \theta_j} \pi(x)$
        if $|L| > |L - R|$ then
             $q = 0$
        else
             $q = 1$
        end if
        if $|L - q R| > |r^*|$ then
             $r^* = |L - q R|$
             $i^* = i$
             $\theta^* = \theta_j$
             $q_{\mathrm{def}}^* = q$
        end if
    end for
end for
return $(i^*, \theta^*, q_{\mathrm{def}}^*)$
Knowl 6 — WeakLearn with Positive Cumulative Weights Constraint
model/method
When combining binary weak rankings $h(x) = [[f_i(x) > \theta]]$ derived from ranking features $f_i$ , allowing negative boosting weights $\alpha_t < 0$ permits arbitrary non-monotonic mappings from a feature's score to its contribution in the final score $H(x)$ . In domains such as meta-search and document retrieval, higher feature scores naturally indicate higher relevance, and non-monotonic assignments increase the hypothesis class complexity and risk overfitting.

To enforce monotonicity, the WeakLearn.cum variant requires that for every distinct weak ranking $h$ , its cumulative weight across all boosting rounds:

$\sum_{t: h_t = h} \alpha_t > 0$

remains strictly positive. On each round, WeakLearn.cum selects the weak ranking that maximizes $|r|$ subject to this non-negativity constraint on its cumulative weight. While this constraint slightly slows training loss reduction, empirical evaluation shows that it substantially reduces test error and prevents overfitting over long boosting runs.
Knowl 7 — Generalization Error Bound for Bipartite Ranking
theoretical result
Consider a bipartite ranking setting where negative instances $X$ and positive instances $Y$ are sampled independently from distributions $D_0$ over $X$ and $D_1$ over $Y$ . Let $S_0 = \langle x_1, \dots, x_m \rangle \sim D_0^m$ and $S_1 = \langle y_1, \dots, y_n \rangle \sim D_1^n$ be independent training sets of sizes $m$ and $n$ .

Let $\mathcal{H}$ be a base class of binary weak ranking functions with VC-dimension $d \ge 2$ , and let $\mathcal{C}$ be the class of combined pairwise decision functions $H: X \times Y \to \{-1, +1\}$ formed by thresholded linear combinations of $T$ base rankers:

$H(x, y) = \mathrm{sign}\left(\sum_{t=1}^T \alpha_t h_t(y) - \sum_{t=1}^T \alpha_t h_t(x)\right), \quad h_t \in \mathcal{H}, \; \alpha_t \in \mathbb{R}.$

Define the true generalization error as $\varepsilon(H) = \Pr_{x \sim D_0, y \sim D_1}[H(x, y) \neq 1]$ and the empirical training error as $\hat{\varepsilon}(H) = \frac{1}{mn} \sum_{i=1}^m \sum_{j=1}^n [[H(x_i, y_j) \neq 1]]$ .

For any $\delta > 0$ , with probability at least $1 - \delta$ over the choice of training samples $S_0$ and $S_1$ , all functions $H \in \mathcal{C}$ simultaneously satisfy:

$|\hat{\varepsilon}(H) - \varepsilon(H)| \le 2\sqrt{\frac{d'(\ln(2m/d') + 1) + \ln(18/\delta)}{m}} + 2\sqrt{\frac{d'(\ln(2n/d') + 1) + \ln(18/\delta)}{n}},$

where $d' = 2(d + 1)(T + 1) \log_2(e(T + 1))$ .
Knowl 8 — Formal Ranking Framework and Pairwise Ranking Loss
definition
In the preference combination learning framework:
- The instance space is a domain $X$ .
- The learner receives $n$ ranking features $f_1, \dots, f_n$ , where each $f_i: X \to \mathbb{R} \cup \{\bot\}$ assigns a real score (higher indicating greater preference) or the abstention symbol $\bot$ .
- Feedback is provided by a function $\Phi: X \times X \to \mathbb{R}$ , where $\Phi(x_0, x_1) > 0$ means $x_1$ should be ranked above $x_0$ , and $|\Phi(x_0, x_1)|$ represents the importance of this ordering. $\Phi$ satisfies $\Phi(x, x) = 0$ and $\Phi(x_0, x_1) = -\Phi(x_1, x_0)$ .
- A pair $(x_0, x_1)$ is crucial if $\Phi(x_0, x_1) > 0$ . A normalized initial distribution $D$ over crucial pairs is defined as:
$D(x_0, x_1) = c \cdot \max\{0, \Phi(x_0, x_1)\}, \quad \text{where } c = \left(\sum_{x_0, x_1 \in X} \max\{0, \Phi(x_0, x_1)\}\right)^{-1}.$
- The learning algorithm outputs a scoring function $H: X \to \mathbb{R}$ to minimize the ranking loss:
$\mathrm{rloss}_D(H) = \sum_{x_0, x_1} D(x_0, x_1) [[H(x_1) \le H(x_0)]].$

When evaluating partial orders under uniform random tie-breaking, the expected ranking loss assigns an error of $1/2$ to tied pairs:

$\mathrm{rloss}_D(H) = \sum_{x_0, x_1} D(x_0, x_1) [[H(x_1) < H(x_0)]] + \frac{1}{2} \sum_{x_0, x_1} D(x_0, x_1) [[H(x_1) = H(x_0)]].$

Knowl 9 — Meta-Search Performance Comparison across Query Templates

data/table

RankBoost was evaluated on a domain-specific meta-search task using 4-fold cross-validation on two domains: machine learning researcher homepages (ML, 210 base queries, 16 search templates) and university homepages (UNIV, 290 base queries, 22 search templates). Search templates retrieved top-30 URLs from AltaVista, and feedback rewarded ranking the correct homepage $u^*$ above all other URLs $u$ .

RankBoost combined the search templates into a single ranking using 50 boosting rounds for ML and 40 rounds for UNIV. The table reports the number of base queries where the correct homepage appeared in the top $k$ positions ( $k \in \{1, 2, 5, 10, 20, 30\}$ ) and the average rank (with unranked URLs set to rank 31, and RankBoost scores capped at rank 31). Bold values indicate the best score across individual search templates evaluated directly on the test set.

Domain / Strategy	Top 1	Top 2	Top 5	Top 10	Top 20	Top 30	Avg Rank
ML Domain
RankBoost	102	144	173	184	194	202	4.38
Best (Top 1)	117	137	154	167	177	181	6.80
Best (Top 10)	112	147	172	179	185	187	5.33
Best (Top 30)	95	129	159	178	187	191	5.68
University Domain
RankBoost	95	141	197	215	247	263	7.74
Best single query	112	144	198	221	238	247	8.17

On the ML domain, RankBoost achieved an average rank of 4.38, substantially better than the best individual template (5.33), and outperformed every single template for $k \ge 20$ . On the UNIV domain, where one search template ("NAME" PLACE) was consistently superior across individual queries, RankBoost closely matched it at small $k$ and outperformed it at $k \in \{20, 30\}$ , improving overall average rank from 8.17 to 7.74.

Knowl 10 — Exact Rank Distribution of Good Items Under Random Tie-Breaking
equation
When evaluating a predicted ranking function $H: X \to \mathbb{R}$ on a set of $N$ items $M$ where ties are broken uniformly at random, let $K$ items be designated as good items $\{t_1, \dots, t_K\}$ ordered such that $H(t_1) \ge \dots \ge H(t_K)$ . For a given good item $t_k$ , define:
- $R = |\{m \in M \mid H(m) > H(t_k)\}|$ , the number of items strictly scored above $t_k$ ,
- $r = |\{t \in \{t_1, \dots, t_{k-1}\} \mid H(t) > H(t_k)\}|$ , the number of good items strictly scored above $t_k$ ,
- $Q = |\{m \in M \mid H(m) = H(t_k)\}|$ , the total number of items tied with $t_k$ ,
- $q = |\{t \in \{t_1, \dots, t_K\} \mid H(t) = H(t_k)\}|$ , the number of good items tied with $t_k$ .
The exact probability that the $k$ -th good item $t_k$ is placed at position $i$ in the final randomly ordered list (for $i \in \{R+1, \dots, R+Q\}$ ) is given by the negative hypergeometric expression:

$\Pr[\mathrm{rank}(t_k) = i] = \frac{\binom{i - R - 1}{k - r - 1} \binom{Q - i + R}{q - k + r}}{\binom{Q}{q}}.$

This probability distribution allows exact analytical computation of expected evaluation metrics under random tie-breaking, including Expected Average Precision (AP), Expected Predicted-Rank-of-Top (PROT), and Expected Coverage:

$\mathbb{E}[\mathrm{AP}] = \frac{1}{K} \sum_{k=1}^K k \sum_{i=k}^{N-K+k} \Pr[\mathrm{rank}(t_k) = i] \frac{1}{i},$

$\mathbb{E}[\mathrm{PROT}] = \sum_{i=1}^{N-K+1} \Pr[\mathrm{rank}(t_1) = i] \frac{1}{i},$

$\mathbb{E}[\mathrm{coverage}] = \sum_{i=K}^N \Pr[\mathrm{rank}(t_K) = i] \frac{K}{i}.$
Knowl 11 — Empirical Comparison on Collaborative Filtering for Movie Recommendation
empirical result
RankBoost was compared against Nearest Neighbor (NN), Linear Regression, and Vector Similarity (VSIM) on the EachMovie dataset (61,625 viewers, 1,628 movies, 2.8 million ratings) across four evaluation metrics: Disagreement (fraction of misordered pairs), Average Precision (AP), Predicted Rank of Top (PROT), and Coverage.

Key empirical findings include:
- Scaling with Feature Set Size: When the number of feature viewers varied from 100 to 2000, RankBoost achieved the lowest disagreement and highest AP, PROT, and coverage among all methods for feature sets larger than 200. RankBoost improved monotonically with feature size, whereas VSIM's performance plateaued and degraded beyond 750 features.
- Feature Density (Ratings per Viewer): As feature density increased from 10–20 to 101–1455 ratings per viewer, RankBoost maintained the best performance across all four metrics. NN improved on disagreement, AP, and coverage, but degraded on PROT (performing worse than random guessing of 0.45 due to default score artifacts on unranked movies). Linear regression showed minimal improvement as feature density increased.
- Feedback Density (Target User Ratings): For small feedback sets ( $\le 40$ movies), VSIM performed comparably to or slightly better than RankBoost. However, as target user feedback density increased beyond 40 ratings, RankBoost consistently improved, while VSIM degraded and converged toward NN performance.

Coverage note — None. The extracted knowls cover all core contributed models, algorithms (RankBoost, RankBoost.B, WeakLearn, WeakLearn.cum), theoretical loss and generalization bounds, evaluation metrics, and experimental results.

References

1.Brian T. Bartell, Garrison W. Cottrell, and Richard K. Belew. Automatic combination of multiple ranked retrieval systems. In Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1994.
2.Peter L. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525–536, March 1998.
3.John S. Breese, David Heckerman, and Carl Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 43–52, 1998.
4.Rich Caruana, Shumeet Baluja, and Tom Mitchell. Using the future to “sort out” the present: Rankprop and multitask learning for medical risk evaluation. In Advances in Neural Information Processing Systems 8, pages 959–965, 1996.
5.William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243–270, 1999.
6.Michael Collins. Discriminative reranking for natural language parsing. In Proceedings of the Seventeenth International Conference on Machine Learning, 2000.
7.K. Crammer and Y. Singer. A new family of online algorithms for category ranking. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2002.
8.Koby Crammer and Yoram Singer. Pranking with ranking. In Advances in Neural Information Processing Systems 14, 2001.
9.Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.
10.O. Etzioni, S. Hanks, T. Jiang, R. M. Karp, O. Madani, and O. Waarts. Efficient information gathering on the internet. In 37th Annual Symposium on Foundations of Computer Science, 1996.
11.Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, August 1997.
12.David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992.
13.David Haussler, Michael Kearns, Nick Littlestone, and Manfred K. Warmuth. Equivalence of models for polynomial learnability. Information and Computation, 95(2):129–161, December 1991.
14.Will Hill, Larry Stead, Mark Rosenstein, and George Furnas. Recommending and evaluating choices in a virtual community of use. In Human Factors in Computing Systems CHI’95 Conference Proceedings, pages 194–201, 1995.
15.Raj D. Iyer, David D. Lewis, Robert E. Schapire, Yoram Singer, and Amit Singhal. Boosting for document routing. In Proceedings of the Ninth International Conference on Information and Knowledge Management, 2000.
16.Guy Lebanon and John Lafferty. Cranking: Combining rankings using conditional probability models on permutations. In Proceedings of the Nineteenth International Conference on Machine Learning, 2002.
17.Paul Resnick, Neophytos Iacovou, Mitesh Sushak, Peter Bergstrom, and John Riedl. Grouplens: An open architecture for collaborative filtering of netnews. In Proceedings of Computer Supported Cooperative Work, 1995.
18.Gerard Salton. Automatic text processing: the transformation, analysis and retrieval of information by computer. Addison-Wesley, 1989.
19.Gerard Salton and Michael J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.
20.Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651–1686, October 1998.
21.Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, December 1999.
22.Upendra Shardanand and Pattie Maes. Social information filtering: Algorithms for automating “word of mouth”. In Human Factors in Computing Systems CHI’95 Conference Proceedings, 1995.
23.V. N. Vapnik. Estimation of Dependences Based on Empirical Data. Springer-Verlag, 1982.
24.Marilyn A. Walker, Owen Rambow, and Monica Rogati. SPoT: A trainable sentence planner. In Proceedings of the 2nd Annual Meeting of the North American Chapter of the Associataion for Computational Linguistics, 2001.

Citation

MLA

Freund, Y., et al. “An Efficient Boosting Algorithm for Combining Preferences”. 1998, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8189.

APA

Freund, Y., Iyer, R. D., Schapire, R. E., & Singer, Y. (1998). An Efficient Boosting Algorithm for Combining Preferences. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8189

Chicago

Freund, Y., R. D. Iyer, R. E. Schapire, and Y. Singer. 1998. “An Efficient Boosting Algorithm for Combining Preferences”. Preprint. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8189.

Harvard

Freund, Y. et al. (1998) “An Efficient Boosting Algorithm for Combining Preferences”. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8189.

Vancouver

1. Freund Y, Iyer RD, Schapire RE, Singer Y (1998) An Efficient Boosting Algorithm for Combining Preferences.

BibTeX

@article{freund1998efficient,
  title = {An Efficient Boosting Algorithm for Combining Preferences},
  author = {Freund, Yoav and Iyer, Raj D. and Schapire, Robert E. and Singer, Yoram},
  year = {1998},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8189}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

An Efficient Boosting Algorithm for Combining Preferences

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — The RankBoost Algorithm

Knowl 2 — Training Loss Bound for RankBoost

Knowl 3 — RankBoost for Bipartite Feedback (RankBoost.B)

Knowl 4 — Methods for Choosing Step Size and Base Ranker Criteria in RankBoost

Knowl 5 — Efficient Weak Ranking Selection via Potential Functions

Knowl 6 — WeakLearn with Positive Cumulative Weights Constraint

Knowl 7 — Generalization Error Bound for Bipartite Ranking

Knowl 8 — Formal Ranking Framework and Pairwise Ranking Loss

Knowl 9 — Meta-Search Performance Comparison across Query Templates

Knowl 10 — Exact Rank Distribution of Good Items Under Random Tie-Breaking

Knowl 11 — Empirical Comparison on Collaborative Filtering for Movie Recommendation

References

Citation

BibTeX

Access the Paper