Uplift Modeling with ROC: An SRL Case Study

Abstract

Uplift modeling is a classi cation method that determines the incremental impact of an action on a given population. Uplift modeling aims at maximizing the area under the uplift curve, which is the di erence between the subject and control sets' area under the lift curve. Lift and uplift curves are seldom used outside of the marketing domain, whereas the related ROC curve is frequently used in multiple areas. Achieving a good uplift using an ROC-based model instead of lift may be more intuitive in several areas, and may help uplift modeling reach a wider audience. We alter SAYL, an uplift-modeling statistical relational learner, to use ROC instead of lift. We test our approach on a screening mammography dataset. SAYL-ROC outperforms SAYL on our data, though not significantly, suggesting that ROC can be used for uplift modeling. On the other hand, SAYL-ROC returns larger models, reducing interpretability.

Introduction

Uplift modeling is a modeling and classi cation method initially used in marketing to determine the incremental impact of an advertising campaign on a given population [ 8 ]. Seminal work includes Radcli e and Surry's true response modeling [ 8 ], Lo's true lift model [ 4 ], and Hansotia and Rukstales' incremental value modeling [ 3 ]. In some applications, especially medical decision support systems, gaining insight into the underlying classi cation logic can be as important as system performance. Reviewing the classi cation logic in medical problems can be an important method to discover disease patterns that may not be known or easily otherwise gleaned from the data. Such insight can be achieved using rule-learners. Decision trees [ 9, 10 ], inductive logic programming (ILP) [ 7 ], and statistical relational learning (SRL) [ 6 ] methods have been proposed.

Uplift modeling aims at maximizing uplift, which is the di erence in a model or intervention M 's lift scores over the subject and control sets: U plif tM = Lif tM (subject)

Lif tM (control): (1) Given a fraction such that 0 1, a model M 's lift is de ned as the number of positive examples amongst the model's -highest ranking examples. Uplift thus captures the additional number of positive examples obtained due to the intervention. Quality of an uplift model is often evaluated by computing an uplift curve [ 9 ], generated by ranging from 0 to 1 and plotting U plif tM . The higher the uplift curve, the more pro table a marketing model/intervention is. The area under the uplift curve (AUU) is often used as a metric to optimize.

Let P be the number of positive examples and N the number of negative examples in a given dataset D. Lift represents the number of true positives detected by model m amongst the top-ranked fraction . Varying 2 [0; 1] produces a lift curve. The area under the lift curve (AUL) for a given model and data becomes:

Z AU L =

Lif t(D; )d 1 P +N

X ( k+1 2 k=1 k)(Lif t(D; k+1) + Lif t(D; k)) (2)

Let s be the subject set, and c the controls. For a given , we can rewrite equation 1 as:

U plif tM ( ) = Lif tM (s; )

Lif tM (c; ): Since uplift is a function of a single value for , the area under the uplift curve (AUU) is the di erence between the areas under the lift curves (AUL) for the subjects and the controls, (AU L):

AU U = AU Ls

AU Lc = (AU L):

Lift and uplift curves are seldom used outside of the marketing domain, whereas the related ROC curve is frequently used in the machine learning and biomedical informatics communities. Especially in the biomedical domain, using ROC may be more intuitive, and may help uplift modeling reach a wider audience. This work investigates the use of the area under the ROC curve (AUR) as an alternate scoring method, while still resulting in a good model uplift. We alter SAYL [ 6 ], the state-of-the-art relational uplift modeling algorithm, to select rules that optimize (AU R) instead of (AU L). We test our approach on a screening mammography dataset. 2

Lift and ROC Area Under the Curve There is a strong connection between AUL and AUR. Let probability for the positive class or skew, then:

P = P +N be the prior (

2 AU L = P + (1

) AU R) [11; p:549]:

Uplift modeling aims at optimizing uplift, the di erence in lift over two sets. It constructs a new classi er such that: (AU L ) > (AU L) As discussed in [ 6 ], by expanding and simplifying we get:

AU Ls

AU Lc > AU Ls

AU Lc Ps( s + (1 2 s)AU Rs )

Pc( c

2 Ps(1 s)AU Rs Ps(1

Pc(1 (3) (4) (5) (6) and nally

AU Rs AU Rc

AU Rs > Pc 1 AU Rc Ps 1 c : s

In a balanced dataset, we have c = s = 12 and Pc = Ps, so we have that Pc 1 c = 1. If the subject and control sets have the same numbers and skew, Ps 1 s we can conclude that (AU L ) > (AU L) implies (AU R ) > (AU R). If the two sets are skewed or their numbers di er, we cannot guarantee that (AU L ) > (AU L) implies (AU R ) > (AU R), as we can increase uplift with rules that have similar accuracy but cover more cases in the positive set. In general, the two metrics are related, with uplift being more sensitive to variations in coverage when the two groups have di erent size. (7) 3

SAYL-ROC

SAYL [ 6 ] is a Statistical Relational Learner based on SAYU [ 1 ] that integrates uplift modeling with the search for relational rules. Similar to SAYU, every valid rule generated is used to construct a Bayesian network (alongside with current theory rules) via propositionalization, but instead of constructing a single classi er, SAYL constructs two TAN [ 2 ] classi ers; one Bayes net for each of the subject and control groups. Both classi ers use the same set of attributes, but are trained only on examples from their respective groups. SAYL uses the TAN generated probabilities to construct the lift and uplift curves. If a rule improves AUU by threshold , the rule is added to the attribute set. Otherwise, SAYL continues the search.

Algorithm 1 SAYL

Rs fg; M0s; M0c InitClassif iers(Rs) while DoSearch() do es+ RandomSeed(); ?es+ saturate(e); while c reduce(?es+ ) do

M s; M c LearnClassif iers(Rs [ fcg); if Better(M s; M c; M0s; M0c) then

Rs Rs [ fcg; M0s; M0c M s; M c; break end if end while end while

The SAYL algorithm is shown as Algorithm 1. SAYL maintains a current set of clauses, Rs, and current reference classi ers for the subjects M s and controls M c. SAYL requires separate training and tuning sets, accepting a rule only when it improves the score on both sets. This requirement is extended with the threshold of improvement , and a minimal rule coverage requirement minpos. Finally, SAYL has two search modes, greedy and exploration. Refer to [ 6 ] for details.

SAYL guides the rule search by using the AUU score. It computes AUU by computing AUL for each of the groups using the two classi ers, and returning the di erence (AU L) (Equation 4). We implement SAYL-ROC, a SAYL variant that computes AUR instead for each of the groups using the two classi ers, and returns (AU R) as a rule score to guide the search. SAYL thus optimizes for (AU L), while SAYL-ROC optimizes for (AU R).

AU Rs AU Rc

AU Rs > 0:86:

AU Rc 4

Experimental Results

We test SAYL-ROC on a breast cancer mammography dataset, fully described in [ 5 ]. Our subject and control sets are respectively older and younger patients with con rmed breast cancer. Positive instances have in situ cancer, and negative instances have invasive cancer. The aim is to maximize the in situ cases' uplift.

The older cohort has 132 in situ and 401 invasive cases, while the younger 132 one has 110 in situ and 264 invasive. The skews are Ps = 132, s = 132+401 110 (older), and Pc = 110, c = 110+264 (younger). Thus equation 7 becomes: (8)

We use 10-fold cross-validation, making sure all records pertaining to the same patient are in the same fold. We run both SAYL and SAYL-ROC with a time limit of one hour per fold. For each cross-validated run, we use 4 training, 5 tuning and 1 testing folds. For each fold, we used the best combination of parameters according to a 9-fold internal cross-validation using 4 training, 4 tuning and 1 testing folds. We try both search modes, vary minpos between 7 and 13 (respectively 5% and 10% of older in situ examples), and set to 1%, 5% and 10%. We evaluate the nal SAYL and SAYL-ROC models using their nal uplift curves, concatenated from the results of each testing set.

Table 1 compares SAYL-ROC, SAYL, and the ILP-based methods Di erential Prediction Search (DPS) and Model Filtering (MF) [ 7 ], both of which had minpos = 13 (10% of older in situ). A baseline random classi er achieves an AUU of 11. We use the paired Mann-Whitney test at the 95% con dence level to compare two sets of experiments. We plot the uplift curves in Figure 1. AU Lc SAYL and SAYL-ROC signi cantly outperform previous methods (Table 1, Figure 1), but there is no signi cant di erence between the two. Even though SAYLROC is optimizing for (AU R) during its training phase, it returns a slightly better testing (AU L) than SAYL, which optimizes for (AU L).

This result suggests that, on a moderately subject/control skewed data, AUR can indeed be used for uplift modeling. ROC is more frequently used than lift, and may be more intuitive in many domains. Nevertheless, more experiments are needed to establish ROC-based uplift performance. We plan on measuring (AU L) vs. (AU R) for various Equation 7 skews.

SAYL-ROC produces as many rules as ILP-based methods, more than twice that of SAYL. The ILP theory is a collection of independent rules that each individually increases uplift [ 7 ]. It is thus easy to interpret the nal model. SAYL and SAYL-ROC theory rules are conditioned on each other as nodes in a Bayesian network, decreasing rule interpretability especially in larger graphs. Individual rules may not increase uplift, but the nal network does. At an average of 9:3 rules, a SAYL model is interpretable, whereas at 24:7, SAYL-ROC sacri ces interpretability.

We note that Equation 7 depends on both the positive number and skew. Even if the subject and control positive skews were equal, say Pc = 100, Nc = 200, Ps = 10 and Ns = 20, we will have 11 s c = 1 but PPsc = 10, maintaining a subject/control Equation 7 skew.

This work uses the de nition of lift as the number of positives amongst the highest ranking examples. An alternative lift de nition is the fraction of positives amongst the -highest ranking examples. Equation 7 then becomes: (9)

AU Rs > 1 AU Rc 1 eliminating the dependence on the number of positive instances. We plan on investigating how (AU L) and (AU R) empirically relate under this de nition.

In conclusion, SAYL-ROC exhibits a similar performance to SAYL on our data, suggesting that ROC can be used for uplift modeling. SAYL-ROC returns larger models, reducing interpretability. More experiments are needed to test ROC-based uplift over di erent subject/control skews.

Acknowledgments We thank NIH grant R01-CA165229, the Carbone Cancer Center, and NCI grant P30CA014520 for support.

References

1. Davis , J. , Burnside , E.S. , de Castro Dutra, I. , Page , D. , Santos Costa , V. : An integrated approach to learning Bayesian Networks of rules . In: Proceedings of the 16th European Conference on Machine Learning . pp. 84 { 95 . Porto , Portugal ( 2005 )

2. Friedman , N. , Geiger , D. , Goldszmidt , M. : Bayesian network classi ers . Machine Learning 29 , 131 { 163 ( 1997 )

3. Hansotia , B. , Rukstales , B. : Incremental value modeling . Journal of Interactive Marketing 16 ( 3 ), 35 { 46 ( 2002 )

4. Lo , V.S.: The true lift model - a novel data mining approach to response modeling in database marketing . SIGKDD Explorations 4 ( 2 ), 78 { 86 ( 2002 )

5. Nassif , H. , Page , D. , Ayvaci , M. , Shavlik , J. , Burnside , E.S.: Uncovering age-speci c invasive and DCIS breast cancer rules using Inductive Logic Programming . In: ACM International Health Informatics Symposium (IHI) . pp. 76 { 82 . Arlington , VA ( 2010 )

6. Nassif , H. , Kuusisto , F. , Burnside , E.S. , Page , D. , Shavlik , J. , Santos Costa , V.: Score as you lift (SAYL): A statistical relational learning approach to uplift modeling . In: European Conference on Machine Learning (ECML-PKDD) . pp. 595 { 611 . Prague ( 2013 )

7. Nassif , H. , Santos Costa , V. , Burnside , E.S. , Page , D. : Relational di erential prediction . In: European Conference on Machine Learning (ECML-PKDD) . pp. 617 { 632 . Bristol , UK ( 2012 )

8. Radcli e, N.J. , Surry , P.D.: Di erential response analysis: Modeling true response by isolating the e ect of a single action . In: Credit Scoring and Credit Control VI. Edinburgh , Scotland ( 1999 )

9. Radcli e, N.J. , Surry , P.D.: Real-world uplift modelling with signi cance-based uplift trees . White Paper TR-2011-1 , Stochastic Solutions ( 2011 )

10. Rzepakowski , P. , Jaroszewicz , S. : Decision trees for uplift modeling with single and multiple treatments . Knowledge and Information Systems 32 , 303 { 327 ( 2012 )

11. Tu ery, S.: Data Mining and Statistics for Decision Making . John Wiley & Sons, 2nd edn. ( 2011 )