Revenue optimization with relevance constraint in sponsored search

Yunzhang Zhu, Gang Wang, Junli Yang, Dakan Wang, Jun Yan, Zheng ChenData Mining and Audience Intelligence for Advertising @ KDD 2009 · DOI

TL;DR

This paper tackles the challenge of balancing ad relevance and revenue in sponsored search. They introduce a novel "trade-off" model that allows search engines to tune a parameter to achieve a desired balance between showing users highly relevant ads and maximizing the revenue generated from those ads.

What Problem Does This Paper Address?

Search engines make a significant portion of their revenue from sponsored ads displayed alongside search results. The effectiveness of these ads hinges on two factors: relevance to the user's query and the revenue they generate for the search engine. While previous work focused on optimizing for either relevance (leading to more clicks) or revenue (considering ad bids), these approaches often compromised the other. This paper addresses the gap by proposing a unified framework that explicitly allows search engines to control the trade-off between maximizing user-perceived relevance and maximizing their own income.

Methods

The authors build upon existing "learning to rank" (LTR) methods. They start by reviewing two primary approaches:

  1. Learning for High Relevance: This method aims to maximize the number of clicks by ranking ads that are most likely to be relevant to the user's query.
  2. Revenue Direct-Optimization (RDO): This approach directly incorporates ad bidding prices into the ranking function to maximize total revenue.

The core contribution is a trade-off learning model. This model combines the objectives of relevance and revenue optimization into a single objective function. This is achieved by introducing a trade-off parameter (μ). By adjusting this parameter, search engines can dynamically shift their focus between maximizing relevance (lower μ) and maximizing revenue (higher μ), or find an optimal balance in between. The algorithms are built using pairwise learning, where the model learns from user click data to infer preferences between pairs of ads. They utilize logistic regression for optimization.

Datasets

The paper uses a dataset consisting of three months of click-through log data, including ad clicks and impressions. For evaluation, they sampled queries where at least three ads were returned. The data was split into 80% for training and 20% for testing. A subset of ads with at least 100 impressions in the training data was used to incorporate CTR features, creating a "new ads" vs. "old ads" distinction for feature evaluation.

Key Insights and Ideas

  • Relevance vs. Revenue is a True Trade-off: The paper empirically demonstrates that optimizing solely for relevance can lead to lower revenue, and vice-versa. Figure 1 visually illustrates this conflict.
  • A Tunable Parameter is Crucial: The introduction of a single trade-off parameter (μ) provides a practical mechanism for search engines to align their ranking strategy with business goals, rather than being forced into an "all or nothing" approach.
  • CTR Estimation Challenges: The authors acknowledge that CTR estimation is particularly challenging for "new" ads with few impressions, necessitating a split in their experimental evaluation to handle this.
  • Feature Importance: The paper explores the impact of different feature sets (9 vs. 12 features, including CTR-related ones) on both relevance and revenue scores, highlighting how feature selection can influence performance.

Key Results

  • Baseline Comparisons:
    • The "Learning to Rank" baseline achieved the highest relevance scores (0.5461 with 9 features, 0.6154 with 12 features) but lower revenue scores (0.4891 with 9 features, 0.4935 with 12 features).
  • The "Revenue Direct-Optimization" (RDO) approach achieved higher revenue scores (0.4899 with 9 features, 0.5312 with 12 features) but lower relevance scores. RDO showed a relative revenue improvement of 19.7% (9 features) and 7.3% (12 features) over learning to rank.
  • Trade-off Performance: The proposed trade-off model, visualized in Figures 2 and 3, shows that by adjusting the parameter λ (which is related to μ), search engines can achieve a spectrum of results. For instance, sacrificing a small amount of relevance can lead to a substantial increase in revenue, and vice-versa. This suggests that an optimal point exists between the two extremes.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the CTR features are only reliable for "old" ads with a significant number of impressions.
  • The authors mention that their approach does not consider the effect of generalized second-price auctions on the actually received revenue, focusing instead on the simpler Pay-Per-Click (PPC) model.
  • Future Work:
    • Investigate more features, particularly additional CTR and relevance features, to further improve revenue scores.
  • Explore more sophisticated methods for choosing the trade-off parameter λ, or even constructing an "ideal criterion" to determine the optimal trade-off for search engines in the long term.
  • Continue exploring revenue optimization from the direction of exploring more features.

Summary updated

BibTeX
@inproceedings{zhu2009revenue,
  author = {Yunzhang Zhu and Gang Wang and Junli Yang and Dakan Wang and Jun Yan and Zheng Chen},
  title = {{Revenue optimization with relevance constraint in sponsored search}},
  booktitle = {Data Mining and Audience Intelligence for Advertising @ KDD},
  year = {2009},
  doi = {10.1145/1592748.1592756},
}
Figure