Learning to Blend by Relevance

Wei Chu(褚崴)arXiv 2010 · arXiv

TL;DR

This paper introduces "blending," a new ranking problem where documents from multiple, potentially heterogeneous domains must be ranked together. They propose two novel algorithms, GPL and GBlend, that jointly optimize ranking functions across domains, outperforming independent optimization approaches on benchmark and real-world search data.

What Problem Does This Paper Address?

The rise of specialized search engines (e.g., for images, videos, or Q&A) means that a single ranking system can no longer suffice. Each domain often has its own unique features and relevance correlations. However, users prefer a unified search experience, not multiple search boxes. This paper addresses the challenge of creating a single, relevant ranking list from documents originating from diverse domains, which may have different feature spaces and relevance criteria. The core problem is how to effectively blend these disparate ranking lists into one coherent, ordered output.

Methods

The authors tackle the blending problem with two novel machine learning algorithms:

  • GPL (Gaussian Process Learning): This algorithm leverages Gaussian processes to model correlations between heterogeneous features from different domains. It learns ranking functions by inferring these correlations from inter-domain observations, allowing it to handle domains with distinct feature sets. GPL is designed for linear functions and can be kernelized for non-linearity, though this increases computational cost.
  • GBlend (Gradient Boosting Blending): This approach builds upon the Gradient Boosting Decision Trees (GBDT) framework. GBlend learns multiple ranking forests simultaneously, one for each domain, by synchronizing the gradient computation stages of individual boosting processes. This joint optimization ensures that the forests collectively minimize the blending loss. GBlend is designed to be efficient and capable of handling large-scale, non-linear data.

Both methods emphasize joint optimization, meaning they learn the ranking functions for all domains concurrently, rather than learning them independently and then trying to combine their outputs. This is a key departure from simpler approaches that might learn individual models and then apply transformations to blend their scores.

Datasets

The paper uses a combination of benchmark datasets and real-world data:

  • Benchmark Datasets: Five benchmark datasets (used for metric regression problems) were merged in pairs to create blending problems. These datasets were normalized, discretized into ordinal labels, and then used to generate preference pairs.
  • Commercial Search Engine Data: A large-scale dataset of approximately 300,000 web and answer documents from a commercial search engine was used to evaluate GBlend. This dataset included dedicated web (A, A') and answer (B, B') datasets, as well as a mixed dataset (C, C') containing inter-domain pairs.

Key Insights and Ideas

  • The limitations of independent optimization: The paper strongly argues that learning ranking functions for each domain separately and then trying to blend them leads to suboptimal solutions. This is because the optimal function for an individual domain might not contribute to the overall best blended ranking.
  • The power of joint optimization: By learning ranking functions for all domains simultaneously, the algorithms can better capture inter-domain dependencies and achieve a more globally optimal blended ranking.
  • Feature correlation is key: GPL's ability to model correlations between features, even if they are not common across domains, is crucial for effective blending, especially when sample sizes are limited.
  • GBDT for scalability: GBlend leverages the efficiency and non-linearity of GBDT to handle large-scale real-world blending problems, making it practical for commercial applications.
  • Inter-domain pairs are essential: The paper highlights that inter-domain preference pairs (e.g., a web document being more relevant than an answer document for a given query) are critical for learning effective blending functions.

Key Results

  • GPL outperforms baselines: On benchmark datasets, GPL significantly beat baselines that used independent optimization, especially for high-dimensional data.
  • GBlend outperforms baselines: In the commercial search engine scenario, GBlend significantly outperformed baseline GBDT models that used independent optimization. The best GBlend model achieved nearly a 3% improvement in nDCG10 over the best baseline.
  • Impact of inter-domain data: Experiments showed that using inter-domain data (dataset C) significantly improved blending performance, even when combined with dedicated domain data (A and B). Larger subsets of inter-domain data generally led to better blending loss and nDCG10 scores.
  • Linear transformations are often sufficient: For independent optimization baselines, linear transformations for score blending were found to perform nearly as well as non-linear ones, suggesting that the core challenge lies in the learning of the base ranking functions themselves.

Limitations and Future Work

  • Blending criterion: The paper focuses solely on blending by relevance. The authors suggest exploring other blending criteria, such as diversity, as an interesting future direction.
  • Feature correlation in GBlend: While GPL handles feature correlation, GBlend currently does not explicitly model it. The authors propose equipping GBlend with this capability as a future research avenue.
  • Other loss functions: The current framework is based on pairwise learning. Adapting other ranking loss functions (e.g., listwise) to the blending problem is also suggested.
  • Computational cost of GPL: While GPL is effective, its kernelized version can be computationally prohibitive for large datasets. Future work might involve approximations or more efficient implementations.

Summary updated

BibTeX
@misc{chu2010learning,
  author = {Wei Chu(褚崴)},
  title = {{Learning to Blend by Relevance}},
  year = {2010},
  eprint = {1001.4597},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1001.4597},
}
Figure