Combined regression and ranking

D. SculleyKDD 2010 · DOI

TL;DR

This paper introduces a novel method called Combined Regression and Ranking (CRR) that simultaneously optimizes for both accurate prediction of numerical values (regression) and correct ordering of items (ranking). CRR demonstrates strong performance across various tasks, often matching the best of separate regression or ranking approaches, and even improving regression on challenging minority class problems.

What Problem Does This Paper Address?

Many real-world applications require models that excel at two distinct tasks: predicting a precise numerical value (regression) and establishing a correct order or preference among items (ranking). For instance, in online advertising, predicting click-through rates (pCTR) is crucial for both ranking ads effectively in auctions and for pricing them accurately in next-price auctions. A model that perfectly predicts numerical values might still produce a poor ranking, and vice-versa. This paper addresses the challenge of building a single model that effectively handles both objectives simultaneously, avoiding the pitfalls of optimizing for one at the expense of the other.

Methods

The core contribution is the Combined Regression and Ranking (CRR) algorithm. CRR unifies regression and ranking objectives into a single optimization problem by combining their respective loss functions with a tunable parameter, $\alpha$, that balances their importance. The paper proposes an efficient implementation using stochastic gradient descent (SGD), which is well-suited for large-scale datasets. Instead of explicitly constructing the potentially massive set of all pairwise comparisons for ranking, CRR samples these pairs on-the-fly, making it computationally feasible. The paper details how SGD updates are instantiated for both squared loss (common in regression) and logistic loss (common in classification and probability estimation).

Datasets

The paper evaluates CRR on several datasets:

  • RCV1: A large-scale benchmark corpus for text mining, used for topic identification tasks with varying class distributions, including extreme minority classes.
  • LETOR 4.0: A benchmark dataset for learning to rank, derived from TREC challenge data, used for evaluating both ranking and regression performance on document retrieval tasks.
  • Proprietary Click Prediction Data: A large-scale dataset from sponsored search advertisements on Google Search, used to evaluate CRR's effectiveness in a real-world commercial application.

Key Insights and Ideas

  • The "Best of Both Worlds" Synergy: CRR often achieves performance comparable to the best specialized regression-only or ranking-only models, suggesting a powerful synergy between the two objectives.
  • Regression Boosted by Ranking on Minority Classes: A surprising and significant finding is that incorporating ranking constraints can actually improve regression performance, especially in datasets with skewed or minority class distributions. The ranking information provides valuable implicit constraints that help stabilize regression estimates when direct data is scarce.
  • Avoiding Degenerate Models: By optimizing both objectives simultaneously, CRR guards against learning models that are excellent at one task but perform arbitrarily poorly on the other (e.g., always predicting 0 for regression to achieve high accuracy on a majority class, but yielding a useless ranking).
  • Scalability is Key: The paper emphasizes the importance of efficient computation for real-world applications. The use of SGD and on-the-fly sampling of ranking pairs makes CRR practical for massive datasets.

Key Results

  • RCV1 Experiments: CRR achieved "best of both" performance (best MSE and AUC Loss) on 16 out of 40 tasks. On another 19 tasks, it was within 0.001 of the best performance. Notably, CRR significantly outperformed the regression-only method on minority class problems (less than 10% positive examples), showing statistically significant improvement (p=0.002).
  • LETOR 4.0 Experiments: CRR's ranking performance (MAP and NDCG) was statistically indistinguishable from the ranking-only method and significantly better than the regression-only method. While its MSE was not as good as the regression-only method, it was substantially better than the ranking-only method.
  • Click Prediction Experiments: CRR achieved "best of both" performance, matching the regression-only method's MSE and the ranking-only method's AUC Loss. A 0.8% reduction in AUC Loss, though small, was statistically significant and noted as having a large potential impact in practice.

Limitations and Future Work

  • Linear Models: The current CRR framework is primarily described for linear models (using dot products). The authors suggest extending it to non-linear models by incorporating kernels, similar to techniques used in other machine learning contexts.
  • Pairwise Ranking: The paper uses a pairwise approach for ranking. Future work could explore more sophisticated ranking functions, such as list-wise approaches or methods that directly optimize metrics like MAP or NDCG, in conjunction with regression.
  • L1 Regularization: The paper focuses on L2 regularization. Investigating the use of L1 regularization for sparsity in CRR models is suggested as a future direction.
  • Parameter Sensitivity: While the paper notes CRR is not overly sensitive to the $\alpha$ parameter, further exploration of optimal $\alpha$ values for specific tasks could be beneficial.

Summary updated

BibTeX
@inproceedings{sculley2010combined,
  author = {D. Sculley},
  title = {{Combined regression and ranking}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2010},
  doi = {10.1145/1835804.1835928},
}
Figure