TL;DR
This paper proposes a novel decision-tree learning algorithm for targeted advertising that directly optimizes for expected profit, rather than just predicting response rates. By forcing the decision tree to consider the mailing decision (M) as a final split, the algorithm identifies customer segments where targeted offers are most profitable, outperforming a standard approach in experimental results.
What Problem Does This Paper Address?
Advertisers often want to send targeted offers to potential customers to increase sales. However, sending these offers incurs costs. The challenge is to identify which customers are most likely to respond positively to an offer, not just in terms of subscribing, but in a way that maximizes the advertiser's profit. Traditional approaches either mail to everyone (mass marketing) or use machine learning to predict who will subscribe, but these methods don't explicitly account for the cost of mailing and the potential for negative profit if the wrong people are targeted. This paper addresses the problem of how to make optimal targeting decisions by explicitly modeling the expected profit for different customer segments.
Methods
The core of the paper introduces a modified decision-tree learning algorithm. Standard decision trees learn to predict a target variable (like subscription to MSN) based on input features. This paper's key innovation is to force the decision tree to make the mailing decision (whether to send an advertisement or not, denoted by M) the last split on any path from the root to a leaf. This ensures that each leaf node represents a distinct customer segment for which a specific mailing decision (mail or don't mail) can be made based on maximizing expected profit.
The authors define "Expected Lift in Profit" (ELP) as the difference between the expected profit from mailing and the expected profit from not mailing. This ELP calculation uses probabilities estimated from data, specifically the probability of subscribing given the mailing status and customer features. The algorithm then aims to grow trees that best predict this ELP. They also describe a post-processing step to refine the trees, removing statistically insignificant splits and ensuring the M split is appropriately placed.
Datasets
The paper uses data from a real-world advertising experiment conducted by Microsoft for its MSN subscription service. The dataset consists of approximately 110,000 records of Windows 95 registrants. For each record, the data includes:
- Whether an advertisement was mailed (M).
- Whether the person subscribed to MSN (S).
- Values for 15 predictor variables (X) obtained from the registration form, such as gender and computer memory.
The data was split into a training set (70%) for building the decision trees and a testing set (30%) for evaluating their performance.
Key Insights and Ideas
- Profit-Driven Targeting: The most crucial insight is that simply predicting who will subscribe isn't enough. The decision to target a customer segment must explicitly consider the cost of mailing and the potential revenue, leading to the concept of maximizing "Expected Lift in Profit" (ELP).
- The Importance of the "Mailing Decision" Split: Forcing the mailing decision (M) to be the last split in the decision tree is a heuristic designed to directly optimize for ELP. This ensures that each leaf node represents a segment where a clear "mail" or "don't mail" decision can be made to maximize profit.
- Beyond Response Rate: The paper highlights that even if a segment shows a higher response rate to an advertisement, it might still be unprofitable to target them if the mailing cost is too high or if they are "always-buyers" who would have subscribed anyway.
- Experimental Data is Key: The effectiveness of the proposed approach relies heavily on experimental data where some customers are randomly exposed to the advertisement and others are not. This allows for the estimation of conditional probabilities needed for ELP calculations.
Key Results
- The proposed "FORCE" algorithm, which enforces the mailing decision (M) as the last split, slightly outperformed a standard decision-tree algorithm ("NORMAL") that maximizes predictive accuracy for ELP in the tested MSN advertising experiment, especially for lower benefit values.
- For higher benefit values (rs = ru), both algorithms yielded identical decisions, suggesting that the standard approach was sufficient in those scenarios.
- Both tree-based strategies showed improvement over a naive "mail-to-all" strategy, indicating that identifying profitable segments is indeed valuable. The improvement over mail-to-all decreased as the subscription revenue increased, but remained positive.
- The paper notes that in the specific MSN domain, the standard "NORMAL" algorithm's trees often naturally had splits on M towards the end of paths, which is why the performance difference wasn't dramatic. They expect their "FORCE" algorithm to be more beneficial in domains where this isn't the case.
Limitations and Future Work
- Single Domain Evaluation: The authors acknowledge that their algorithm was only evaluated on a single domain (MSN subscriptions). They suggest that further evaluation on diverse datasets is needed to fully assess its generalizability.
- Experimental Data Difficulty: Obtaining the type of experimental data used (randomized mailing) is noted as being difficult, which limits the applicability of their approach in some real-world scenarios.
- Special Offers: The current work assumes a fixed offer (rs = ru). The authors suggest an interesting extension would be to consider campaigns where the advertisement offers a special price or discount. In such cases, their techniques could be used to simultaneously identify the best discount and the corresponding mailing strategy.
Summary updated