Causal Inference Based Single-branch Ensemble Trees For Uplift Modeling

Two distinguishing characteristics of CIET are splitting criteria for tree generation and the single-branch ensemble method, respectively.

As for splitting criteria in estimating uplift, it is motivated by our expectation to achieve the maximum difference between the distributions of the treatment and control groups. Given a class-labeled dataset with $N$ samples, $N^{T}$ and $N^{C}$ are sample size of the treatment and control groups (recall that $N=N^{T}+N^{C}$, $T$ and $C$ represent the treatment and control groups). Formally, in the case of a balanced randomized experiment, the estimator of the difference in sample average outcomes between the two groups is given by:

where $P^{T}$ and $P^{C}$ are the probability distribution of the outcome for the two groups. Motivated by Eq. (1), the divergence measures for uplift modeling we propose are lift gain and its ratio, namely LG and LGR for short. The corresponding mathematical forms of LG and LGR can be thus expressed as

where $P_{0}^{T}$ and $P_{0}^{C}$ are the initial probability distribution of the outcome for the two groups, $\tau_{0}=(P_{0}^{T}-P_{0}^{C})N_{R}$. And $N_{R}$ and $Y_{R}$ for a node logic $R$ represent coverage and correction classification, while $P_{R}^{T}$ and $P_{R}^{C}$ are the corresponding probability distribution of the outcome for both groups, respectively. Evidently, both Eq. (2) and Eq. (3) represent the estimator for uplift, which are proposed as two criteria in our ms. Compared to the standard binary tree with left and right branches, only one branch is created after each node splitting in this ms. It is characterized by the fact that both LG and LGR are calculated using the single-branch observations that present following a node split. Accordingly, subscript $k$ indicating binary branches doesn’t exist in the above equation. Furthermore, the second term of LG makes every node partition better than randomization, while LGR has the identical advantages to information gain ratio.

The proposed splitting criterion for a test attribute A is then defined for any divergence measure $D$ as

where $D(P^{T}(Y):P^{C}(Y)|A)$ is the conditional divergence measure. Apparently, $\Delta$ is the incremental gain in divergence following a node splitting. Substituting for $D$ the $LG$ and $LGR$, we obtain our proposed splitting criteria $\Delta_{LG}$ and $\Delta_{LGR}$. The intuition behind these splitting criteria is as follows: we want to build a single-branch tree such that the distribution divergence between the treatment and control groups before and after splitting an attribute differ as much as possible. Thus, an attribute with the highest $\Delta$ is chosen as the best splitting one. In order to achieve it, we need to calculate and find the best splitting point for each attribute. In particular, an attribute is sorted in descending order by value when it is numerical. For categorical attributes, some encoding methods are adopted for numerical type conversion. The average of each pair of adjacent values in an attribute with $n$ value, forms $n-1$ splitting points or values. As for this attribute, the point of the highest $\Delta$ can be seen as the best partition one. Furthermore, the best splitting attribute with the highest $\Delta$ can be achieved by traversing all attributes. As for the best splitting attribute, the instances are thus divided into two subsets at the best splitting point. One feeds into a single-branch node, while the other is censored. Note that the top–down, recursive partition will continue unless there is no attribute that explains the incremental estimation with statistical significance. Also, histogram-based method can be employed to select the best splitting for each feature, which can reduce the time complexity effectively.

Due to noise and outliers in the dataset, a node may merely represent these abnormal points, resulting in model overfitting. Pruning can often effectively deal with this problem. That is, using statistics to cut off unreliable branches. Since none of the pruning methods is essentially better than others, we use a relatively simple pre-pruning strategy. If $\Delta$ gain is less than a certain threshold, node partition would stop. Thus, a smaller and simpler tree is constructed after pruning. Naturally, decision-makers prefer less complex inference rules, since they are considered to be more comprehensible and robust from business perspective.

As noted above, it is impossible to observe both the control and treatment outcomes for an individual, which makes it difficult to find measure of loss for each observation. It leads that uplift evaluation should differ drastically from the traditional machine learning model evaluation. That is, improving the predictive accuracy of the outcome does not necessarily indicate that the models will have better performance in identifying targets with higher uplift. In practice, most of the uplift literature resort to aggregated measures such as uplift bins or curves. Two key metrics involved are area under uplift curve (AUUC) and Qini coefficient (Gutierrez and Gérardy 2016), respectively. In order to define AUUC, binned uplift predictions are sorted from largest to smallest. For each $t$, the cumulative sum of the observations statistic is formulated as below,

where the $t$ subscript implies that the quantity is calculated on the first or top $t$ observations. The higher this value, the better the uplift model. The continuity of the uplift curves makes it possible to calculate AUUC, i.e. area under the real uplift curve, which can be used to evaluate and compare different models. As for Qini coefficient, it represents a natural generalization of Gini coefficient to uplift modeling. Qini curve is introduced with the following equation,

There is an obvious parallelism with the uplift curve since $f(t)=g(t)(N_{t}^{T}+N_{t}^{C})/N_{t}^{T}$. The difference between the area under the actual Qini curve and that under the diagonal corresponding to random targeting can be obtained. It is further normalized by the area between the random and the optimal targeting curves, which is defined as Qini coefficient.

The following representation of three algorithms includes: selecting the best split for each feature using the splitting criteria described above, learning a top-down induced single-branch tree and forming ensemble trees with each resulting tree progressively.

Algorithm 1 depicts how to find the best split of a single feature $F$ on a given dataset $D[group\_key,feature,$ $target]$ using a histogram-based method with the proposed two splitting criteria. Gain_left and Gain_right are the uplift gains for the child nodes after each node partition. If the maximum value of Gain_left is greater than that of Gain_right, the right branch is censored and vice versa. Thus, the best split with its corresponding splitting logic, threshold and uplift gain is found, which is denoted by Best$\_$Direction, Best$\_$Threshold and Best$\_\Delta$. Besides, there are several thresholds to be initialized before training a CIET model, including minimum number of samples at a inner node $min\_samples$, minimum recall $min\_recall$ and minimum uplift gain required for splitting $min\_\Delta$. The top-down process would continue only when the restrictions are satisfied.

Algorithm 2 presents a typical algorithmic framework for top–down induction of a single-branch uplift tree, which is built in a recursive manner using a greedy depth-first strategy. The parameter $max\_depth$ represents the depth of the tree and $cost$ indicates the threshold of LG or LGR. As the tree grows deep, more instances are censored since they are not covered by the node partition logic of each layer. As a result, each child node subdivides the original dataset hierarchically into a smaller subset until the stopping criterion is satisfied. Tracing the splitting logics on the path from the root to leaf nodes in the tree, an ”IF-THEN” inference rule is thus extracted.

Finally, adopting a divide-and-conquer strategy, the above tree-building process is repeated on the censored samples to form ensemble trees, resulting in the formation of a set of inference rules as shown in Algorithm 3.

Dataset We can test the methodology with numerical simulations. That is, generating synthetic datasets with known causal and non-causal relationships between the outcome, action (treatment/control) and some confounding variables. More specifically, both the outcome and the action/treatment variables are binary. A synthetic dataset is generated with the $make\_uplift\_classification$ function in ”Causal ML” package, based on the algorithm in (Guyon 2003). There are 3,000 instances for the treatment and control groups, with response rates of 0.6 and 0.5, respectively. The input consist of 11 features in three categories. 8 of them are used for base classification, which are composed of 6 informative and 2 irrelevant variables. 2 positive uplift variables are created to testify positive treatment effect. The remaining one is a mix variable, which is defined as a linear superposition of a randomly selected informative classification variable and a randomly selected positive uplift variable.

Parameters and Results There are four hyper-parameters in CIET: $criterion\_type$, $max\_depth$ and $rule\_count$. $criterion\_type$ includes two options, LG and LGR. More precisely, two main factors of business complexity and difficulty in online deployment, determine parameter assignment. Due to the requirement of model generalization and its interpretability, $max\_depth$ is set to 3. That is, the business logics of a single inference rule are always less than or equal to 3. And, $rule\_count$ is given a value of 3, indicating that a set of no more than three rules is defined to model the causal effect of a treatment on the outcome. Meanwhile, the default values for $min\_samples$, $min\_recall$, $cost$ and $min\_\Delta$ are 50, 0.1, 0.01 and 0, respectively.

The stratified sampling method is used to divide the synthetic dataset into training and test sets in a ratio of fifty percent to fifty percent. Figure 1 shows the uplift curves of the four analyzed classifiers. The AUUC of CIET with LG and LGR are 294 and 292 on the training set, which are significantly greater than 266 and 265 for the decision trees for uplift modeling with KL divergence and squared Euclidean distance. At the 36th percentile of the population, the cumulative profit increase reach 303 and 354 for LG and LGR, resulting in a growth rate of more than 18$\%$ and 37$\%$ compared to baselines. Besides, AUUC shows little variation in the training and test datasets, indicating that the stability of CIET is also excellent. According to Table 2, Qini coefficients of CIET are also obviously greater, with an increase of more than 24.5$\%$ and 17.8$\%$. Furthermore, all three rules are determined by uplift and informative variables as expected, which can be seen from Table 1.

Dataset We use the publicly available dataset $Credit$ $Approval$ from the UCI repository as one of the real-world examples, which contains 690 credit card applications. All the 15 attributes and the outcome are encoded as nonsense symbols, where $A7\neq v$ is applied as the condition for dividing the dataset into treatment and control groups. There are 291 and 399 observations in the two groups with response rates of 0.47 and 0.42, respectively. Attributes with more than 25$\%$ difference in distribution between the two groups should be removed before any experiments are performed. This leads that 12 attributes are left as input variables. For further preprocessing, categorical features are binarized through one-hot encoding.

Parameters and Results Based on the business decision-making perspective, the initial parameters are also the same as above.

In order to avoid the distribution bias caused by the division on such small sample size dataset, there is no need to divide $Credit\ Approval$ into training and test parts. Figure 2 shows the uplift curves for the four analyzed classifiers, from which we can see that CIET is able to obtain higher AUUC and Qini coefficients. As shown in Table 3, the former increases from 37$\sim$40 at baselines to 42$\sim$48 at CIET approximately, while the latter also improves significantly from 0.20$\sim$0.23 to 0.25$\sim$0.31. Especially when LGR serves as the splitting criterion, the cumulative profit has a distinguished peak of 74.5, while only 48.4$\%$ of the samples are covered.

Dataset We further extend our CIET to precision marketing for new customer application. A telephone marketing campaign is designed to promote customers to apply for personal credit loans at a national financial holdings group in China via its official mobile app. The target is 1/0, indicating whether a customer would submit an application or not. The data contains 53,629 individuals, consisting of a treated group of 32,984 (receiving marketing calls) and a control group of 20,645 (not receiving marketing calls). These two groups have 300 and 124 credit loan applications with response rates of 0.9% and 0.6%, which are typical values in real world marketing practice. There are 24 variables in all, which are characterized as credit card-related information, loan history, customer demographics et al.

Parameters and Results All parameters are the same as in the above experiments. The dataset is first divided into training and test sets in a ratio of sixty percent to forty percent. The response rates are consistent across two sets for two groups. Figure 3 diplays the results graphically. As for the training dataset, CIET based on LG and LGR reach AUUC of about 104 and 89, while the decision trees based on KL divergence and squared Euclidean distance are 73 and 72. It can be seen that CIET achieves a significant improvement compared to baselines on this real-world dataset even with a very low response rate. Moreover, as can be seen in Table 4, Qini coefficient based on our approaches increases to 0.30$\sim$0.41 from 0.16$\sim$0.17 on the training dataset. Meanwhile, Qini coefficient changes little when crossing to test dataset, indicating a better stability. Consequently, classifier with our CIET for precision marketing is effectively improved as well as stabilized in terms of AUUC and Qini coefficient. At present, CIET has already been applied to personal credit telemarketing.