Fabrice

Tanguy Elias

Marc

Carine Bruno

Anaïs Raphael Hugo

Tout d'abord, je tiens à exprimer ma profonde gratitude à Sihem AMER-YAHIA et Szymon JAROSZEWICZ pour avoir accepté de rapporter cette thèse. Je tiens également à remercier Marie-Jeanne LE-SOT, Tias GUNS et Philippe LERAY pour leur participation au sein du jury de thèse.

Cette thèse n'aurait pas atteint ce niveau sans l'accompagnement constant de mes encadrants, Bruno CREMILLEUX et Nicolas VOI-SINE. Avoir une telle équipe d'encadrement a été une véritable chance.

Bruno : Ton accueil chaleureux à Caen, nos nombreux dîners et discussions, ton soutien pendant la période difficile du covid, et ton engagement pour que je vive pleinement mon doctorat ont été essentiels. Je te suis très reconnaissant pour tout cela et pour ton accompagnement dans la planification de ma carrière post-thèse.

Nicolas : Ta motivation pour mon travail, ta disponibilité constante, nos longues réunions et même nos échanges du quotidien ont été essentiels. Nos moments partagés lors des différentes conférences, enrichis de discussions et de nombreuses photos, resteront toujours de très beaux souvenirs.

Je tiens également à remercier Marc BOULLÉ. Ta collaboration a été très précieuse pour plusieurs parties de cette thèse. Merci pour nos discussions sur les thématiques Bayésiennes et pour ton accueil dans ton bureau à chaque fois.

CHAPTER 1

Introduction 1

Context and motivation

'Would a teenage boy buy the same clothes as his grandmother? Probably not. But when they get sick, they're likely to receive the same medical treatment, despite their many differences. And so will everyone else' [START_REF] Jackson | What is personalized medicine?[END_REF]. This highlights the importance of personalised medicine, which tailors medical treatment to a patient's unique characteristics and genetic information. However, estimating the effect of medical treatments at the individual level is a complex task because it requires observing an individual's behaviour with and without treatment, which is impossible to do simultaneously. This is because it is impossible to treat and not treat the same person at the same time and to observe the difference between the two alternative behaviours.

This problem exists in many fields, including marketing, medicine and the social sciences. We often face the challenge of identifying the individuals who are most likely to benefit from a particular intervention (treatment), i.e. the individuals on whom the treatment will have the most positive effect. In marketing, for example, the goal is to design a campaign that effectively motivates customers to buy a particular product. This is one of the current challenges faced by Orange, a French telecommunications company where this thesis was carried out. Finding the most effective marketing campaign, i.e. the optimal treatment, for each customer that will result in the maximum number of purchases would be extremely valuable. Here, an optimal treatment is defined as the treatment among several options that maximises the probability of a desired outcome. In economics, another example is the analysis of the impact of funded training programmes on the earnings of trainees and non-trainees in the labour market, as described in [START_REF] Angrist | Treatment effect[END_REF].

To identify the individuals who should receive a particular intervention (also called a treatment or action), a first simple strategy is to compare the average outcomes of the treatment group (those who receive the intervention) and the control group (those who do not). This comparison helps determine whether or not the intervention was beneficial on average, however such a comparison is not sufficient in a lot of situations. To illustrate, let's take a study of 200,000 individuals, half of them, i.e. 100,000 individuals, were contacted about an internet offer while the other half did not. (cf. Fig. 1.1). 70% of the contacted group purchased the offer, while only 50% of the non-contacted group did. This suggests a positive impact of the marketing campaign, with a 20% increase in purchases. However, if we examine the data more closely, we will see that the treatment effect varies across different subgroups. In our example, as shown in Fig. 1.1, the intervention had a negative impact on younger people: only 30% of young customers made a purchase when contacted, compared to an 80% purchase rate when not contacted. This suggests that the intervention may have discouraged them from purchasing the product. For seniors, the opposite effect was observed. All of the contacted seniors took advantage of the internet offer, but only 20% of them took advantage of the internet offer when no one contacted them. With this information, a marketing team would not have targeted everyone, but only a subset of customers, each with their optimal treatment.

From conventional methods to uplift modeling 1.2.1 Response Modeling and A/B Testing

Traditional methods, particularly in marketing, have been used to either identify potential targets for marketing campaigns or to determine the optimal treatment to assign to all customers. This has been done using response modeling and A/B testing, respectively. In this section, we provide a brief discussion of each of these techniques and highlight their limitations.

Response modeling [START_REF] Victor | The true lift model: a novel data mining approach to response modeling in database marketing[END_REF] has long been used to predict the outcome of individuals after treatment. It has been used to predict whether or not a person will buy a product after receiving a marketing campaign. However, the disadvantage Figure 1.1: Example of treatment effect estimation of this method is that it tries to predict the probability of a particular outcome without considering the effect of the treatment on that outcome. For example, a person may decide to buy the product regardless of whether they receive the marketing campaign. In this case, contacting them is an unnecessary cost. They also might decide not to buy the product if they receive the campaign, whereas their decision would be different if they do not receive it (like the young clients in our previous example).

A/B testing [START_REF] Tamburrelli | Towards automated a/b testing[END_REF] is also often used in these situations. It is most commonly used to compare two versions of a web page of a software system on different users. It involves randomly dividing a sample of users into two groups, a treatment group and a control group, and then measuring a metric of interest, such as the number of clicks or the conversion rate. By comparing the results of the two groups with statistical tests, researchers can determine which version of the two treatments (the variations of the web page) is more effective. The disadvantage of A/B testing is that it does not search for individuals to target with a marketing campaign, but it searches for the treatment that will be assigned to everyone and will yield the greatest profit in average. So, it cannot discover groups that should be avoided like the senior group in our previous example (cf. Fig. 1.1).

The need for uplift modeling

To address the limitations of traditional approaches, it is necessary to take into account different categories of customers:

1. The persuadables: customers who respond positively to a marketing campaign only because they have received the treatment ⇒Treatment has a positive effect.

2. The sure-things: customers who will always respond positively to a marketing campaign ⇒Treatment has no effect in this case because they would buy anyway.

3. The lost causes: customers who would not respond positively anyway ⇒Treatment has no effect in this case either.

4. The do-not-disturb: customers who would respond positively but did not because of the marketing campaign ⇒The treatment has a negative effect in this case.

Estimating the treatment effect per subgroup as shown in Fig. 1.1 may be complex in real scenarios, particularly in high-dimensional data where it may not be possible to determine the relevant subgroups. This is where uplift modeling can be useful. In marketing, "uplift" refers to the treatment effect, and uplift modeling seeks to estimate the effect of a treatment on an outcome variable at the individual level. It comes to overcome the drawbacks of response modeling and A/B testing.

A formal difference between supervised learning and uplift modeling

Uplift modeling should not be confounded with supervised learning. Supervised learning algorithms, such as those used in classification and response modeling, aim to estimate a single probability distribution for a target variable and can help avoiding lost causes (as presented above). This can be interpreted as training a classifier to predict the individuals that are most likely to have a positive response.

On the other side, the goal of the treatment effect estimation, for example in marketing applications, is not to predict likely buyers but to predict the people who will buy only because they received a treatment. In uplift modeling, we distinguish two different groups, the treatment group and the control group. The treatment group consists of people who received a treatment, and the control group consists of people who did not receive a treatment. The goal is then to create a model that learns not the probability of a particular response, but the difference between two outcome probabilities: the outcome probability in the treatment group and the outcome probability in the control group.

Background on Uplift Modeling

In this section, we will introduce the basic concepts and formal definitions related to uplift modeling. We begin with an example that we will refer to throughout this section to illustrate the formal definitions. Consider the case of a telecom company with customers subscribing to a basic internet package. The company is evaluating a new promotional campaign offering selected customers a free one-month upgrade to a premium internet package. It wants to predict the probability that customers will retain the premium package (i.e. become paying customers) after the promotional period based on this campaign. In this example, the treatment, denoted T , is whether the customer receives the promotional offer or not. This is coded as '1' if the customer receives the offer and '0' if she does not. The outcome, denoted Y , is also binary, whether the customer upgrades to the premium package and pays for it after the promotion period ('1' if yes, '0' if no). Each customer can have two potential outcomes: Y (T = 0), the potential outcome if she had received no treatment; and Y (T = 1), the potential outcome if she had received the treatment.

The ITE, which corresponds to the Individual Treatment Effect, can then be defined as:

IT E = Y (T = 1) -Y (T = 0)
The goal of treatment effect estimation is to calculate the ITE. However, the ITE can never be calculated because only one of Y (T = 1) and Y (T = 0) can be observed, i.e. a client cannot be treated and not treated at the same time. This issue is known as the Fundamental Problem of Causal Inference. The unobserved potential outcome can also be called the counterfactual of the observed outcome.

Since we cannot calculate the ITE, two communities simultaneously tackled this challenge: (a) The Heterogeneous Treatment Effect community that focuses on calculating the Conditional Average Treatment Effect (CATE) and (b) the uplift modeling community. The objectives of each of these two communities are discussed below.

1.3. Background on Uplift Modeling

Conditional Average Treatment Effect. Since the ITE cannot be calculated, we can instead, under some assumptions that we state below, estimate the conditional average treatment effect (CATE). A client being described by a vector x, the CATE can then be defined as:

CAT E : τ (x) := E[Y (T = 1) -Y (T = 0) | X = x] (1.1)
where X is a random variable describing a set of features.

It has been shown that the CATE is the best estimator for the ITE in terms of the mean squared error [START_REF] Sören | Metalearners for estimating heterogeneous treatment effects using machine learning[END_REF].

Observational data. The CATE estimation approaches are often developed for observational data. Observational data refers to data collected without the use of a controlled experiment, where treatments are assigned to the individuals or clients without randomization. Observational data are collected without the company assigning the promotional offer to specific customers. Instead, customers may themselves decide whether or not to take up the offer, or the promotional offer may be available only to a subset of customers who meet certain criteria (such as being on a particular current plan or having a particular usage behaviour). The company then collects data on outcomes (i.e. whether customers retain the premium package after the promotional period) and any relevant characteristics of the individuals. As a consequence, CATE estimation meets the challenge of nonrandom assignment of the treatment leading to selection bias. Uplift data bias will be described in Section 2.5 and non-random assignment will be particularly discussed in Chapter 5.

Uplift Modeling. Uplift modeling is a practical branch of the CATE estimation basically developed for the applications of the marketing field. Uplift modeling assumes a randomized control trial, where data is collected in a controlled experiment and customers are randomly assigned to treatment and control groups. In other words, there is no dependence between the characteristics of the instances (customers) and the treatment assignment. In this case the uplift of an individual described by a vector x, denoted Uplift(x), is defined by:

Uplift(x) = E[Y | T = 1, X = x] -E[Y | T = 0, X = x].
(1.

2)

The link between the CATE and Uplift estimation tasks. Both of the CATE estimation task and the uplift estimation task are equivalent under a set of assumptions:

• Conditional independence assumption (CIA) This assumption is also referred to as the unconfoundedness assumption or the strong ignorability assumption). It implies that the treatment assignment is independent of the two potential outcomes:

(Y (T = 1), Y (T = 0)) ⊥ T | X

In the context of the earlier example, the CIA would assume that there is no unobserved variable, such as customer satisfaction, that affects both the customer's decision to accept the offer and their decision to remain on the free plan. If such a variable exists and is not accounted for, it may confound the relationship between treatment and outcome and thus bias the estimate of the treatment effect. This assumption is untestable and its validity is based on expert knowledge of the data.

• Stable Unit Treatment Value (SUTVA) assumption

The treatment given to one subject has no effect on other subjects, i.e. subjects do not interfere with each other. Again, in the context of our earlier example on telecom data, this assumes that whether a client takes the offer does not affect the decision of another customer(s), for example his neighbours or friends, to buy the premium package. This is an important assumption, because otherwise the treatment effect estimation will not be correct.

• Overlap assumption Each subject has a non-zero probability of being in the treatment or control group. In other words, no sub-population is entirely in the treatment or control group:

0 < P (T = 1 | X = x) < 1
The overlap assumption in our previous scenario means that for any given customer, regardless of their characteristics (such as age, loyalty to the company, current plan, past usage data, etc.), there should be a non-zero probability that they will take up the promotional offer (treatment) and a non-zero probability that they will not.

Given these assumptions, we can consider the tasks of CATE (Conditional Average Treatment Effect) estimation (see Equation 1.1) and uplift estimation (see Equation 1.2) to be equivalent (for a mathetmatical proof please refer to [START_REF] Zhang | A unified survey of treatment effect heterogeneity modelling and uplift modelling[END_REF][START_REF] Jacob | Cate meets ml[END_REF]). There is significant overlap in the methodologies used for uplift modeling and CATE estimation, to the extent that certain approaches have been independently reinvented within each community. Throughout this thesis, the terms 'Uplift' and 'CATE' will be used interchangeably to refer to the treatment effect.

Challenges we tackle in this thesis

This thesis basically tackles 3 problems that already exist in the uplift modeling literature: (1) Automating Uplift Models (2) Data bias (3) High dimensionality. We discuss below each of them.

Automating Uplift Models

According to [START_REF] Zöller | Benchmark and survey of automated machine learning frameworks[END_REF], Automated machine learning (AutoML) aims to reduce the demand for data scientists by enabling domain experts to build machine learning applications automatically without extensive knowledge of statistics and machine learning. To the best of our knowledge, the challenge of automating uplift appproaches has not been tackled in the uplift modeling research area.

As we will see in Section 2.2, there is a wide range of uplift methods [START_REF] Zhang | A unified survey of treatment effect heterogeneity modelling and uplift modelling[END_REF] such as meta-learners and direct approaches. A meta-learner is an algorithm that combines traditional supervised learning algorithms for uplift estimation while direct approaches are a set of algorithms specifically designed for uplift modeling. The main drawback of all these approaches is that they require parameters to be set. Meta learners also present an additional requirement, which is the choice of the machine learning algorithm to be used. All of these are clear limitations for nonmachine learning experts to use these tools. Even for machine learning experts, they need to test different parameter values and different learning algorithms with meta learners to find the optimal combination that fits the data at hand. That is why automatic parameter-free uplift modeling algorithms are needed.

Data Bias

Uplift modeling assumes that treatment and control groups are drawn from the same distribution. While this strong assumption is potentially valid in experimental data and controlled trials, it often does not hold in real-world scenarios. The CATE estimation example given above in Fig. 1.1 was relatively straightforward because the treatment and control groups were of equal size. In addition, treatment assignment did not depend on the features of the instances. This was reflected in the equal representation of young and old people in each of the treatment groups. In real-world scenarios, it is easier to collect control data than to collect treatment data. That is why the treatment group tends to be more biased: it is difficult to apply treatments to individuals and collect the corresponding data, often due to ethical, political or economic constraints. This often leads to unequal sizes of treatment and control groups, which has been referred to in recent work as Imbalanced Treatment Conditions (ITC) [START_REF] Betlei | Uplift prediction with dependent feature representation in imbalanced treatment and control conditions[END_REF], and can complicate the estimation of CATE. Also, even when the two treatment groups are of equal size, there are often dependencies between the treatment assignment and the characteristics of the instances. For example, the treatment group may consist mostly of young individuals, while the control group may consist mostly of older individuals.

High Dimensionality

Identifying subgroups with different treatment effects when there are hundreds to thousands of features is a more complicated task. Telecom companies like Orange often has this type of problem with marketing and telecom data. This data has information generated and collected through their network infrastructure, customer interactions, and billing systems. It includes various dimensions, customer demographics, usage patterns, call records, service subscriptions, customer interactions, and billing information. Uplift modeling algorithms can suffer when there are large numbers of features, leading to overfitting and computational and interpretability problems. Since uplift modeling is a different problem than supervised learning, traditional feature selection approaches (which have been extensively studied in the literature) are not applicable.

Contributions

The contributions of this thesis are as follows:

1. We propose a user parameter free Bayesian approach for uplift discretisation that we called UMODL. It uses a density estimation approach based on the MDL principle. UMODL defines a space of discretization models and a prior distribution. From this model space, a Bayesian optimal evaluation criterion is defined to evaluate a discretization model. A search algorithm is then used to find the model with the optimal criterion. An experimental protocol evaluates the discretisation approach as a univariate uplift estimator. We show that UMODL is a good uplift estimator resistant to overfitting.

2. While a discretization approach is basically designed to handle continuous data, we show how to take advantage of UMODL to handle categorical data to do value grouping in order to be able to separate the different values of the categorical variable with distinct uplift and group the ones with similar behavior (similar treatment effect).

3. While the feature selection approaches for uplift modeling are very limited, we introduce a new feature selection approach for uplift modeling called UMODL-FS based on UMODL. Once the intervals dividing a variable X 1.6. Thesis outline are found using the UMODL discretization approach, UMODL-FS calculates an importance score on the found intervals. An experimental protocol shows that UMODL-FS is very resistant to noise and is able to find the set of variables that lead to the best uplift model.

4.

We propose a Bayesian decision tree algorithm for uplift modeling, UB-DT.

We transform the uplift tree learning problem into an optimisation problem.

The goal is to find the uplift tree model that is most probable given the data according to Bayes law. So a global evaluation criterion for an uplift tree model is described, and a search algorithm is presented to search for the optimal uplift decision tree according to the global evaluation criterion.

A random forest extension, that we called UB-RF, is also presented. A benchmark study shows the efficiency of our method against state-of-theart modeling algorithms.

5. We study a type of bias in the uplift modeling process called the Non-Random Assignment (NRA) bias. We carry out an experimental study of the effect of the NRA bias on the different uplift modeling approaches and UB-DT. We propose a reweighting method to improve an uplift modeling method called the class transformation approach, which our study found to be the most sensitive to the NRA bias.

6. Finally, we provide an introduction to telecom data and show how uplift modeling can be performed to deal with it. We apply our feature selection, discretization, decision trees and random forests on real world telecom data. We introduce Kuplift, a new Python package that we have developed to implement our Bayesian algorithms.

Thesis outline

This thesis is structured as follows. Chapter 2 presents an overview of the literature made in both the uplift modeling and CATE estimation communities, including a description of the modeling approaches, evaluation metrics and feature selection techniques. An overview of a density estimation approach called MODL is then presented. Finally, an overview of possible biases in the uplift modeling process is given. Chapter 3 presents UMODL, our Bayesian approach to uplift discretisation and density estimation. We also show how UMODL can be used for feature selection for uplift. In Chapter 4 we present UB-DT, a new Bayesian decision tree for uplift modeling. We present our global evaluation criterion for an uplift tree and a detailed proof. We discuss the algorithm used to find the uplift tree with the best criterion. We then extend it to a random forest algorithm. In Chapter 5 we present the experimental study we conducted to evaluate the uplift modeling approaches and UB-DT against the Non-Random Assignment bias.

In Chapter 6 we perform additional evaluation experiments for the UMODL discretization approach, UMODL-FS, UB-DT, and UB-RF on real telecom data. Finally, in Chapter 7 we summarise the contributions of the thesis and discuss research perspectives.

Corresponding Articles

International Conferences

Introduction

The work presented in this thesis lies at the intersection of several topics (cf. Fig. 2.1): uplift modeling, Bayesian approaches and data bias. In this chapter we provide background information on each of these topics.

We start by addressing several points in uplift modeling. First, we review state-ofthe-art uplift modeling approaches in Section 2.2 and evaluation metrics for uplift models in Section 2.3. In addition, we discuss in Section 2.4 feature selection techniques developed in the literature specifically for uplift modeling problems. Next, in Section 2.5 we discuss potential biases that may exist in the uplift modeling process. We will divide them into two main categories: 1. modeling bias, which occurs mainly during the training phase of an uplift model. 2. deployment bias, which occurs when we apply a learned uplift model to a real-world scenario during the deployment phase.

A large part of the contribution of this thesis is to propose Bayesian approaches for uplift discretisation, uplift feature selection and uplift decision trees based on a density estimation technique known as Minimum Optimised Description Length (MODL) [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF]. In the last section of this chapter, we will present the MODL density estimation and the MODL decision tree approaches. These will serve as preliminary knowledge for our contributions presented in Chapter 3 and Chapter 4.

Review of existing Uplift modeling approaches

The uplift modeling literature and a branch of the causal inference literature have recently approached each other [START_REF] Gutierrez | Causal inference and uplift modelling: A review of the literature[END_REF]. In this section, we review uplift approaches developed in both literatures. We divide them into two categories [START_REF] Zhang | A unified survey of treatment effect heterogeneity modelling and uplift modelling[END_REF]: Metalearners, whose building blocks are traditional supervised ML algorithms, and Direct approaches, which are algorithms tailored specifically for uplift modeling.

Metalearners

Meta-learning, or learning to learn, is the science of systematically observing how different machine learning approaches perform on a wide range of learning tasks, and then learning from this experience [START_REF] Vanschoren | Meta-learning. Automated machine learning: methods, systems, challenges[END_REF]. Following the same idea, in uplift modeling meta-learners are a set of algorithms that exploit traditional supervised learning algorithms to estimate the CATE. One of the main advantages of these algorithms is that they are constructed by merging off-the-shelf algorithms in a specific way. They include simple and intuitive techniques such as the singlemodel and two-model approaches, as well as more sophisticated methods such as the X-Learner, R-Learner and DR-Learner. In this section, we will take a look at each of these approaches.

The Single-model Approach [42, 5]

As its name implies, the Single-model approach (also called the S-learner) consists of learning a single model using the treatment variable as an additional feature, without giving it a special role. In other words, the Single-model approach considers the concatenation of the treatment and the covariates (T, X) as the features. Thus a response function μ(x, t) is defined as: μ(x, t)

:= E [Y | (X = x, T = t)].
This function can be learnt using any ML algorithm. CATE estimation τ (x) is then calculated as: τ (x) = μ(x, 1) -μ(x, 0)

Although the Single-model approach is simple, it may not be able to predict the difference between the two potential outcomes (i.e. uplift). It can have very poor performance [START_REF] Sören | Metalearners for estimating heterogeneous treatment effects using machine learning[END_REF] and is not often used in practical problems. This is because the approach relies on a single algorithm that is trained solely to learn the estimation of the output variable. Also, in high dimensional data, the treatment variable can have a less importance for the learnt model. In addition, algorithms such as LASSO or decision trees that perform variable selection internally may not select the treatment variable during the training phase.

The Two-model Approach [31]

The Two-model approach, also known as the T-learner [START_REF] Sören | Metalearners for estimating heterogeneous treatment effects using machine learning[END_REF], is a simple and intuitive approach for estimating the conditional average treatment effect (CATE). The idea is to create two predictive models for the treatment and control groups to estimate μ1 (

x) = E[Y |X, T = 1] and μ0 (x) = E[Y |X, T = 0].
The CATE is then estimated as the difference between the predictions of these two models:

τ (x) = μ1 (x) -μ0 (x)
One advantage of the Two-model approach is that it can use any supervised learning algorithm to construct the predictive models. However, a problem with this approach is that it tries to predict the outcomes separately in each of the treatment and control groups, rather than the uplift itself. This can be problematic if the average response is weak or noisy. Additionally, if the data used to estimate the treatment effect is biased, the global estimator will be biased. A study on the limitations of the Two-model approach can be found in [START_REF] Nicholas | Real-world uplift modelling with significance-based uplift trees[END_REF].

Inverse Propensity Weighting (IPW) [59]

The idea behind inverse propensity weighting (IPW) is to estimate the treatment effect while accounting for dependencies between the treatment and the instances' features. Using the sampling probability in the treatment and control groups, subjects are weighted by the inverse probability. That will give higher weights to instances that are under-represented in the treatment group, and lower weights for the ones who are over-represented. It's like creating a "pseudo population" in which the treatment is independent of the variables. The sampling probability in the treatment group is called the propensity score [START_REF] Rubin | Estimating causal effects from large data sets using propensity scores[END_REF] denoted e(x) = P (T = 1|X = x). Economists used the inverse propensity weighting for estimating the Average Treatment Effect1 (AT E). Assuming that the real propensity scores are known, the ATE for a population of size N indexed by i is defined as:

AT E = 1 N i T i Y i e(X i ) - 1 N i (1 -T i )Y i (1 -e(X i ))
Also, the same principle can be used for CAT E estimation. Then the inverseprobability-weighted outcome for an individual i denoted Y IP W i is:

Y IP W i = (T i -e(X i ))Y i e(X i )(1 -e(X i ))
A regression of Y IP W i would behave as an oracle estimator of the treatment effect where counterfactuals are present in the data. However, the problem is that the propensity score is usually unknown and must be estimated from the data. As a result, Y IP W i estimate may be incorrect if the propensity score function is not correctly specified. Additionally, it can suffer from high variance, especially when the estimated propensity score is small.

Doubly-robust learner [39]

The Doubly-robust learner (also known as the DR-learner) combines the Twomodel approach and the inverse propensity weighting. Data is divided into three parts of equal size. Conditional mean outcomes μ1 (x) = E[Y |X, T = 1] and μ0 (x) = E[Y |X, T = 0] are learnt on the first part of the data. Propensity scores e(X) are learnt on the second part of the data. The outcome is then transformed to be :

Y DR-L i = T i -e(X i ) e(X i ) (1 -e(X i )) (Y i -μT i (X i )) + μ1 (X i ) -μ0 (X i )
and regressed on the third part of the data.

This approach is called "doubly robust" because it is unbiased if either the propensity score or the conditional mean outcomes are correctly specified. However, it can be more computationally intensive to implement than other methods.

X-learner [42]

The X-Learner is a meta-learner that estimates the treatment effect separately for each treatment group. This may be helpful in case of imbalanced treatment and control conditions. The X-Learner is composed of several stages. The first one (identical to the Two-model approach) estimates the response functions μ0 (x) and μ1 (x) using any supervised learning algorithm. The second step consists of estimating the imputed treatment effect for each individual in the control and treatment groups, denoted by D0 i , D1 i respectively. This is done by assigning treatment effects to individuals in one group based on the outcome estimator of the other group, that is:

D1 i := Y i -μ0 (X i )
, where subject i belongs to the treatment group D0 i := μ1 (X i ) -Y i , where subject i belongs to the control group The third step is to estimate uplift in two ways: by modeling the imputed treatment effects in the treatment group and those of the control group. Thus we obtain τ1

(x) = E[ D1 | X = x] and τ0 (x) = E[ D0 | X = x].
Finally, the CATE estimation τ (x) is the weighted average of these two estimates:

τ (x) = ê(x)τ 0 (x) + (1 -ê(x))τ 1 (x)
where ê(x) = P (T = 1 | X = x) is the propensity score estimation [START_REF] Rubin | Estimating causal effects from large data sets using propensity scores[END_REF]. The advantage of the X-learner is that it combines information from the control group to estimate the treatment effect in the treatment group and vice versa. So it may perform better than the Two-model approach. However, it requires learning four models, increasing complexity and parameters tuning.

R-learner [52]

The R-Learner is a two step algorithm that estimates the treatment and control outcomes μ(x) and the propensity score e(x). The CATE is estimated by minimizing the following loss function:

L[τ (x)] = 1 n N i=1 Y i -μ(-i) (X i ) -T i -ê(-i) (X i ) τ (X i ) 2
where ê(-i) and μ(-i) denote the out-of-fold held-out predictions made without using the i th training sample.

Class-Transformation approach [38]

The principle of this approach is to map the uplift modeling problem to a usual supervised learning problem. The outcome variable Y is transformed into a variable Z as illustrated in Eq. 2.2.1. Then a machine learning algorithm is used to learn a model and to predict P (Z|X). The estimated uplift of

an individual i is τi = 2 × P (Z = 1|X i ) -1 Z =        1, if T = 1 and Y = 1 1, if T = 0 and Y = 0 0, otherwise.
Several studies [START_REF] Diemert | A Large Scale Benchmark for Uplift Modeling[END_REF][START_REF] Jaskowski | Uplift modeling for clinical trial data[END_REF] show that this approach has a better performance than the two-model approach. However, as shown in the experiments we conduct in Chapter 5, the Class-Transformation approach may be very sensitive to the Nonrandom assignment bias (see Section 2.5.1).

Direct Approaches

Unlike metalearners, direct approaches are specifically designed for treatment effect estimation and uplift modeling. Various algorithms have been proposed in the literature, such as tree-based methods, SVM-based methods, and deep learning methods. Random forest-based methods were also proposed as a natural extension of tree-based methods by combining several uplift tree models into a single uplift model. In this section, we will examine these methods, focusing on treebased methods because they are one of the best learning approaches on tabular data, while being interpretable, which is crucial in many fields such as marketing, especially when dealing with customers, as is the case with the Orange Group.

Tree-based and Random forest methods

Tree-based methods for uplift modeling build decision trees for estimating the CATE or uplift. Unlike traditional decision trees, the goal is not to find leaves with pure class distributions, but to find leaves that estimate the treatment effect.

The main advantage of tree-based methods lies in their interpretability, which is very important for many applications. However, a major drawback is that the induction of an optimal uplift decision tree from a data set is NP-hard [START_REF] Ge Naumov | Np-completeness of problems of construction of optimal decision trees[END_REF], and the tree-learning process is usually greedy.

To overcome the issue of high variance in decision trees, random forests have been proposed for uplift modeling. They typically perform better when a large number of trees are included in the forest. However, unlike decision trees, random forests lack interpretability. [START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF] is similar to traditional decision tree algorithms in machine learning, but it introduces a new splitting criterion based on information theory. It can handle multiple treatments and an arbitrary number of classes. The proposed splitting criterion is based on distribution divergences, with the goal of maximizing the differences between the class distributions in the treatment and control sets. For each non-leaf node, the criterion for a split test is calculated as follows: where A represents a split test performed on a non-leaf node (for example x < v, where v is a real number, presents a test A) and where D(p : q) is a divergence measure between two probabilities p and q such as Kullback-Leibler divergence (KL), squared Euclidean Distance (ED), Chi-squared divergence (Chi). The criterion selects a test that leads to the most divergent class distributions in each branch. The gain D gain (A) obtained from a test A is calculated by subtracting the divergence between class distributions on the entire dataset from the divergence between class distributions due to test A. The class divergence between treatment and control groups of a test A is simply the sum of the class divergence between treatment groups for each value of the test A (each child node, denoted by a). In other words:

Uplift Decision Tree algorithm

D (P (Y |T = 1) : P (Y |T = 0) | A) = a N (a) N D (P (Y |T = 1, a) : P (Y |T = 0, a))
where N (a) denotes the number of instances for the outcome of the test A is a.

The authors argued that the ED divergence measure may perform better since it's symmetric and more stable.

A normalization step is performed in order to prevent bias toward tests with a large number of outcomes and tests that tend to separate treatment and control groups. The algorithm is followed by a pruning step to avoid overfitting. Additionally, a number of parameters must be set, such as the maximum depth and the minimum number of samples required to perform a split.

Uplift Incremental Value modeling (UpliftIVM) [START_REF] Hansotia | Incremental value modeling[END_REF] is one of the earliest tree-based uplift approaches proposed in the uplift modeling community. Unlike the Uplift decision tree approach that tries to maximize the estimated treatment effect in each child node, the UpliftIVM tries to maximize the difference between the treatment effect of the left and right child nodes. UpliftIVM searches for the split s that maximizes the following splitting criterion:

∆µ(s) := |τ L -τR |
Each of τL and τR are estimated as the treatment effect in the left and right nodes. More precisely:

τL = n L i=1 T i Y i n L i=1 T i - n L i=1 (1 -T i ) Y i n L i=1 (1 -T i )
,

and τR = n R i=1 T i Y i n R i=1 T i - n R i=1 (1 -T i ) Y i n R i=1 (1 -T i )
where n L and n R denote the number of instances in the left and right child nodes.

Causal trees [4] are different from traditional decision trees in that they are designed to be an honest approach. According to [START_REF] Wager | Estimation and inference of heterogeneous treatment effects using random forests[END_REF], an honest approach requires that we do not use the same set of data to both learn and to conduct inference. In a causal tree, the training data (of size n s ) is used to create tree splits (to build the entire tree) and the estimation data is used to estimate the uplift values in the leaves. When learning a causal tree, the goal is to find the split s that maximizes the following splitting criterion:

∆µ(s) := n L n τ 2 L + n R n τ 2 R Rewards treatment effect heterogeneity - 1 n + 1 n s S 2 1L p + S 2 0L 1 -p + S 2 1R p + S 2 0R

-p

Penalizes splits leading to small leaf nodes where S 0L , S 1L , S 0R and S 0R denote sample variances in treatment and control groups in each of the left and right leaves. p denotes treatment probability in the data. The CATE estimation in a Causal tree is done using inverse propensity score in each leaf node.

The approaches mentioned previously belong to the category of tree-based methods. In the literature, forest-based methods have also been developed as a natural extension of these approaches [START_REF] Soltys | Ensemble methods for uplift modeling[END_REF]. Typically, a forest is constructed by combining multiple trees and then computing their average predictions.

Causal forests [START_REF] Wager | Estimation and inference of heterogeneous treatment effects using random forests[END_REF] Causal forests is a random forest algorithm that uses Causal trees as its base learner. Similar to random forest-like algorithms, k causal trees are trained and then used to provide a treatment effect estimation τt (x) for each example x in a test set. The prediction of the Causal forest is then the average of the predictions provided by the Causal trees, i.e., τ (x) = 1 k t τt (x). The authors showed the estimations of the causal forests are asymptotically Gaussian and unbiased. [START_REF] Zhao | Uplift modeling with multiple treatments and general response types[END_REF] algorithm is a random forest algorithm designed to directly maximize a new performance measure called the expected performance through its splitting criterion.

The Contextual Treatment Selection (CTS)

• Expected response: The expected response is an evaluation measure where multiple treatments and/or outcomes can be considered. It defines a new random variable z i , such that:

z i = N k=1 Y i P T =k I {h (x i ) = k} I{T = k}
where P T =k is the prior probabilities of the treatment and h (x i ) is an uplift model resulting in the optimal treatment and I (.) is the Iverson bracket (the 0/1 indicator function), equal to one if the predicted optimal treatment is equal to the assigned treatment, and zero otherwise.

When the predicted optimal treatment is equal to the observed treatment,z i becomes equal to the outcome scaled by the probability of the treatment. Thus the expected response of an uplift model is then the expectation of z i , E[z i ], calculated as follows:

E[z i ] = E[Y | T = h(x i )] = 1 N N i=1 z i
• Splitting criterion: Suppose s is a candidate split that divides a space ϕ into left and right subspaces, resp. ϕ l and ϕ r . The goal is to perform the split s that leads to the greatest increase in the expected response. The increase in expected response is calculated as:

∆µ(s) =P {X ∈ ϕ l | X ∈ ϕ} max t l =0,...,K E [Y | X ∈ ϕ l , T = t l ] +P {X ∈ ϕ r | X ∈ ϕ} max tr=0,...,K E [Y | X ∈ ϕ r , T = t r ] -max t=0,...,K E[Y | X ∈ ϕ, T = t]
Note that we subtract the maximum response of the parent node, to be able to calculate the gain achieved by s.

Note that all splits in the CTS approach are binary splits. Similarly to the Uplift decision tree approach, a number of parameters should be set by the user, such as the minimum number of samples required to split a node and a regularization term.

Other forest-based methods were also proposed. [START_REF] Guelman | Uplift random forests[END_REF] studied decision trees for uplift modeling and pointed to their high variance problem. So, they presented the Uplift Random Forest algorithm. Later, [START_REF] Guelman | A decision support framework to implement optimal personalized marketing interventions[END_REF] presented the Causal Conditional Inference Forest to solve both the variable selection bias in the splitting criterion and the overfitting problem of the Uplift Random Forest algorithm. [START_REF] Soltys | Ensemble methods for uplift modeling[END_REF] performed an extensive study on ensemble methods and proposed a bagging algorithm for uplift modeling.

Support vector machine-based methods

The support vector machine algorithm has been adapted for uplift modeling problems [START_REF] Zaniewicz | Support vector machines for uplift modeling[END_REF][START_REF] Zaniewicz | L_p support vector machines for uplift modeling[END_REF]. [START_REF] Zaniewicz | Support vector machines for uplift modeling[END_REF] proposed an SVM-based approach called L 1 -USVM, where the main idea is to use two parallel hyperplanes that divide the sample space into three regions of different treatment effects: positive, neutral and negative treatment effects. In this way, the uplift modeling problem becomes a three-class classification problem. The two hyperplanes are:

H 1 : ⟨w, x⟩ -b 1 = 0, H 2 : ⟨w, x⟩ -b 2 = 0
where b 1 , b 2 are the intercepts and w is the normal vector to the hyperplanes. The CATE predictions are then obtained according to the following equations:

τ (x) =        +1 if ⟨w, x⟩ > b 1 and ⟨w, x⟩ > b 2 , 0 if ⟨w, x⟩ ≤ b 1 and ⟨w, x⟩ > b 2 , -1 if ⟨w, x⟩ ≤ b 1 and ⟨w, x⟩ ≤ b 2
The same authors then proposed L p -USVM [START_REF] Zaniewicz | L_p support vector machines for uplift modeling[END_REF], which extends L 1 -USVM by using the L p norm for the regularisation for w instead of the L 1 norm. Improved optimisation algorithms were also proposed in the same paper. According to [START_REF] Zaniewicz | L_p support vector machines for uplift modeling[END_REF], L p -USVM does not suffer from discontinuity problems unlike L 1 -USVM and improves convergence and efficiency.

The main drawback of this approach is its complexity due to the additional hyperplane and its variables.

Deep Learning-based methods

Deep learning based methods have also been proposed in the literature. We briefly review the different contributions. The Causal Effect Variational Autoencoder (CEVAE) proposed by [START_REF] Louizos | Causal effect inference with deep latent-variable models[END_REF], is a neural network latent variable model for causal effect estimation. It learns a latent set of confounders from the observed covariates. The Treatment Effect with Disentangled Autoencoder (TEDVAE) [START_REF] Zhang | Treatment effect estimation with disentangled latent factors[END_REF] improves CEVAE by taking into account not only the confounding variables that are correlated with both the treatment and outcome variables (see Section 2.5.1), but also the instrumental factors that affect only the treatment and the risk factors that affect only the outcome. Generative Adversarial Network for Individualised Treatment Effects (GANITE) [START_REF] Yoon | Ganite: Estimation of individualized treatment effects using generative adversarial nets[END_REF] attempts to learn the counterfactual distributions using a Generative Adversarial Network (GAN) while generating CATE estimates for the instances. Counterfactual Regression (CFR) [START_REF] Shalit | Estimating individual treatment effect: generalization bounds and algorithms[END_REF] extends the two-model approach. First, a representation learning is performed to minimise the discrepancy between the two distributions P (X|T = 1) and P (X|T = 0), then two neural networks are trained on each of the treatment and control groups to estimate the CATE. DeepTreat [3] is a single-model based approach. First, it consists of a bias-removing auto-encoder to control the trade-off between bias reduction and information loss. It learns a new representation for the covariates X where the treatment groups are balanced. It then trains a single neural network to predict the outcome Y using the concatenated features and the treatment variables.

Deep learning-based methods excel at learning large datasets, but are less effective for small datasets (as in medical applications). In addition, they lack interpretability, which is sometimes crucial in some applications. Their parameters are also difficult to tune.

Evaluation metrics

An important part of building a machine learning model is being able to evaluate it. An evaluation metric is used to evaluate the predictive performance of a learning algorithm. They help to evaluate model results in order to select the best model among several. For example, in supervised learning, such as classification or regression, metrics like the F1 score, accuracy, area under the curve (AUC) can be used. They all depend on two values for each instance in the data set, the predicted value and the actual value.

However, as mentioned earlier, one of the main problems with uplift modeling is that the actual uplift values cannot be observed. We cannot simultaneously observe both outcomes for a given individual with and without treatment. That's why performance measures of the supervised setting are inoperative.

In this section we present the performance measures used in the case of uplift modeling to assess the quality of the predicted treatment effects.

Group-level uplift based metrics

Uplift per decile [START_REF] Victor | The true lift model: a novel data mining approach to response modeling in database marketing[END_REF][START_REF] Patrick | Quality measures for uplift models[END_REF] Evaluating the quality of the estimated uplift values is a challenge, as it is not possible to do it directly or define a loss function. One solution is to rank the instances based on their estimated uplift values and evaluate the resulting ranking. Since comparing true uplift values is infeasible, researchers proposed comparing the estimated uplift within bins or groups. Specifically this is done by sorting the instances in descending order by their predicted uplift values (separately for each of the treatment and control groups), then dividing them into deciles, and calculating uplift per decile d,denoted μ(X d ), such that:

û (X d ) = E [Y | X d , T = 1] -E [Y | X d , T = 0]
where X d denotes the individuals of a particular decile d.

The predictions of a good uplift model will yield a decreasing uplift-per-decile bins as presented on the left figure of Fig. 2.2. On the contrary, a bad uplift model will yield increasing uplift-per-decile bins or random bins as shown in the right figure of Fig. 2.2.

The uplift-per-decile chart can help practitioners (for example in the marketing field) to target the subjects in the first deciles (with higher predicted uplift values) since they are persuadables and to avoid subjects in other bins. However, the uplift-per-decile chart does not allow to compute the Gain of uplift targeting a particular ratio of subjects and does not give us a numerical evaluation metric for uplift models.

Qini Curve

The Qini curve was first proposed in [START_REF] Radcliffe | Using control groups to target on predicted lift: Building and assessing uplift model[END_REF] to plot the absolute incremental responses of the treated group compared to the control group. Let D T , D C be respectively the treatment and control groups, ordered by the predictions of an uplift model; N T , N C be the total number of instances in D T and D C

V (k) = R T (k) -R C (k) N T N C
Let's take an example of qini curves similar to the one presented by [START_REF] Radcliffe | Using control groups to target on predicted lift: Building and assessing uplift model[END_REF]. Assume a dataset containing 100K treated individuals and 100K non-treated individuals. The number of positive responses in the treatment group is 30K against 10K in the control group. Fig. 2.3 shows two Qini curves presenting the performance of two different uplift models, a Qini curve V random showing the performance of the random model [START_REF] Radcliffe | Using control groups to target on predicted lift: Building and assessing uplift model[END_REF] and a Qini curve V * showing the performance of an optimal uplift model. A random model is the model that assigns treatment randomly to subjects. An optimal model (in yellow) assigns higher scores to all treated responders than all non-responders. It is a theoretical curve that assumes that all treated responders have positive outcomes because of the treatment. Thus it climbs at 45 • , assuming that positive outcomes are due to the treatment, then proceeds horizontally and finally goes down due to the negative effects of the treatment.

By targeting the top 50% of instances according to model A, the gain will be 20K, while targeting the top 50% of instances according to model B the uplift gain will be 25K It's clear that the uplift model B outperforms model A. Note that targeting the whole population will yield a gain equivalent to the average treatment effect (ATE), which is 20K in our case.

Several variants of the qini curve were used in the literature. Also the uplift curve [START_REF] Rzepakowski | Decision trees for uplift modeling[END_REF], which is quite similar to the qini curve, was introduced. Uplift curve As just mentioned, the uplift curve is an another variant of the qini curve that was also widely used in the literature [START_REF] Rzepakowski | Decision trees for uplift modeling[END_REF][START_REF] Jaskowski | Uplift modeling for clinical trial data[END_REF][START_REF] Nassif | Uplift modeling with roc: An srl case study[END_REF][START_REF] Soltys | Ensemble methods for uplift modeling[END_REF]. To our knowledge, [START_REF] Rzepakowski | Decision trees for uplift modeling[END_REF] were the first to introduce the uplift curve. It is obtained by subtracting the lift curve obtained on the control set from the lift curve obtained on the treatment set. The values of the uplift curve can then be calculated by:

U (k) = R T (k) -R C (k)
In [START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF], the authors renormalized the curves by the number of examples of their respective treatment groups. So U (k) can then be calculated by:

U (k) = R T (k) N T - R C (k) N C
To compare several uplift models, we need a numerical value describing the performance of each model. Mainly, two measures were proposed in the literature, named the Qini coefficient and the AUUC :

• Qini Coefficient Q [56]
The qini coefficient is a generalization of the Gini coefficient. It provides an evaluation of how far the qini curve V (k) is from the random curve V random and how close it is from the optimal curve V * . The qini curve is generated by varying k from 0 to 100. Subsequently, the area under the qini curve, denoted as AU C(V ), can be computed. The qini coefficient Q of an uplift model can then be calculated as follows:

Q = AU C(V ) -AU C (V random ) AU C (V * ) -AU C (V random )
The Qini coefficient will be referred to as 'qini' or 'qini value' throughout the remainder of the thesis.

• Area Under the Uplift Curve (AUUC) [START_REF] Rzepakowski | Decision trees for uplift modeling[END_REF] As the name implies, it is area under the uplift curve.

AU U C = 100 0 U (k)dk
Sometimes the area under the diagonal line is subtracted from this quantity [START_REF] Diemert | A Large Scale Benchmark for Uplift Modeling[END_REF][START_REF] Jaskowski | Uplift modeling for clinical trial data[END_REF]. Several variants of the metrics described above were proposed in the literature. For the interested reader, please refer to [START_REF] Devriendt | Learning to rank for uplift modeling[END_REF].

Precision in the Estimation of Heterogeneous Effects (PEHE)

When the ground truth uplift values are observed, which happens in synthetic datasets, where data are simulated, the precision in the estimation of heterogeneous effect (PEHE) [START_REF] Hill | Bayesian nonparametric modeling for causal inference[END_REF] can be used. It acts as a mean-squared error (RMSE) for uplift problems.

PEHE = 1 n n i (τ (x i ) -τ (x i )) 2

Feature selection for uplift models

The telecommunications industry collects huge amounts of data [START_REF] Calabrese | Urban sensing using mobile phone network data: a survey of research[END_REF]. Data that can be collected includes the location of phones, call records, timestamps and call duration. In addition, SMS records such as SMS length, frequency and timestamps can be collected. The industry also collects information about internet usage, such as user IDs, the types of websites visited and the number of bytes transferred. It often has hundreds to thousands of features. This may cause serious challenges to machine learning models such as the curse of dimensionality [START_REF] Richard Bellman | Dynamic programming[END_REF].

Large number (and often noisy) features may lead machine learning algorithms to overfitting and decreased performance. In addition, interpretability of machine learning decisions in the presence of a large number of features is not practical.

That's why dimensionality reduction techniques, including feature selection, is a crucial step in machine learning for improving the efficiency of models. Feature selection help to simplify models, making them easier to interpret, reducing computation power, cost and training time, and facilitating data visualization.

The literature of feature selection is extensive [START_REF] Guyon | An introduction to variable and feature selection[END_REF]. In this section, we will first provide a high-level overview of the main feature selection families of methods, explain why they are not well-suited for uplift modeling problems, and then take a look at the contributions of feature selection methods specifically for uplift modeling.

Feature selection in classical machine learning

Feature selection is a very large research domain that was Different feature selection techniques were designed for supervised, unsupervised and semi supervised learning. Supervised feature selection can be broadly categorized as filter, wrapper, and embedded methods. Filter methods select subsets of variables as a preprocessing step, independently of the chosen machine learning algorithm. Wrapper methods evaluate subsets of features, allowing for the evaluation of interactions between different variables. Embedded methods perform feature selection as part of the learning process; for example, decision trees such as CART [START_REF] Leo Breiman | Classification and Regression Trees[END_REF] perform internal feature selection, and LASSO method constructs linear models while penalizing regression coefficients. Other feature selection techniques were also developed for unsupervised learning. A review of unsupervised feature selection can be found in [START_REF] Alelyani | Feature selection for clustering: A review[END_REF]. Finally, when high-dimensional data is available with only a subset of labeled samples, semi-supervised feature selection techniques [START_REF] Zhao | Semi-supervised feature selection via spectral analysis[END_REF] were developed to face a new challenge.

A new problem, a new challenge Conventional feature selection techniques try to find the most relevant features for outcome prediction. However, as previously presented, in uplift modeling we try to estimate the difference between two outcome distributions, which make traditional feature selection techniques innoperative.

Feature selection for uplift modeling

To the best of our knowledge, only two articles in the uplift modeling literature that discuss feature selection. Zhao et al. [START_REF] Zhao | Feature selection methods for uplift modeling[END_REF] propose filter and embedded feature selection methods for uplift. They compare them with conventional feature selection methods. Their results show that traditional feature selection approaches are not effective in the uplift modeling context. In [START_REF] Hu | Customer feature selection from high-dimensional bank direct marketing data for uplift modeling[END_REF], the author suggests performing a second step in the feature selection process to remove redundant features. The article calculates a correlation coefficient between each variable and all other variables. If two features have a correlation coefficient greater than 0.8, one of them is removed. While removing redundant features is an important step, this approach may not be feasible on real data due to computational constraints.

Following, we briefly present the filter and embedded methods that were proposed by [START_REF] Zhao | Feature selection methods for uplift modeling[END_REF].

Filter methods

Filter methods are used in a pre-processing step independently of an uplift model.

F-Filter

The F filter method uses the F statistic to test the significance of the interaction between the treatment variable and a feature in a linear regression. An interaction in linear regression occurs when the effect of an independent variable (for instance a feature X) on the outcome variable Y depends on another independent variable (in our case the treatment variable T ). In order to capture non-linear interactions, the authors extended this approach by adding higher-order terms of the feature in the regression. More specifically, a linear regression model with interaction is presented as:

Y = α + δT + R r=1 β r X r + R r=1 θ r T X r
The interaction term +ϵ where X is the feature for which a score is to be calculated. α, δ, β and θ are the coefficients and ϵ represents the error term. R is the higher-order term (a hyperparameter set by the user). Since θ is the coefficient of the interaction term, its significance indicates the strength of the treatment effect for the feature X. To examine the significance of θ, we should contrast the model with interaction above with the linear regression model without an interaction term. A linear regression model without interaction can be presented as:

Y = α ′ + δ ′ T + R r=1 β ′ r X r + ϵ ′
The F-filter feature selection calculates the importance score of a feature X as the F-statistic for the coefficient of the interaction term θ:

F = (RSS -RSS ′ / R) RSS ′ / (N -R -2)
where RSS and RSS ′ are the Residual Sum of Squares for the fitted model with and without interaction respectively. The value of F can be used with an Fdistribution calculator with degrees of freedom (R, N -R -2) to calculate a p-value. The null hypothesis states that there is no statistical difference between the linear regression model with and without interaction.

Likelihood ratio (LR) filter Similar to the F-filter, the LR filter uses the likelihood ratio test statistic for the interaction coefficient in a logistic regression.

The likelihood test static measures whether adding a parameter to our model , e.g. the interaction term, will make our model fit the data significantly better. Again, this is achieved by comparing the models that include the interaction term with those that do not.

Bin-based divergence Filter

Bin based Divergence filter approach comes from the split criteria of the uplift trees. The bin-based method first divides a feature into equally sized bins then estimates the divergence between the outcome distributions in each of the treatment groups. Let p i and q i denote the outcome distribution in each of the treatment and control groups respectively for the bin i:

I i=1 N i N D(p i : q i )
where N i is the number of instances in the bin i and D corresponds to a distribution divergence measure. Three measures were used: the Kullback-Leibler divergence (KL), the squared Euclidean Distance (ED) and the chi-squared divergence (Chi).

Again, the number of bins is a hyperparameter to be set by the user.

Embedded methods

Embedded methods for feature selection generate importance scores by training an uplift model. The authors proposed to generate importance scores from an uplift decision tree model. At each split, the gain in the distribution divergence is calculated:

∆ = k∈{ left, right } n k n D (p k , q k ) -D(p, q)
where n is the number of instances in the parent node.

The importance score of a feature X can be calculated by summing all the gains of all the splits where X was used.

The filter feature selection approaches described above are all parametric, while embedded methods can be time consuming as they rely on the performance of an uplift model. The authors showed that bin-based approaches outperformed other methods. The F and LR filters showed improved performance when the hyperparameter R was set to a value greater than 1, which allows non-linear patterns in the data to be detected.

Biases in uplift modeling

Most machine learning algorithms work well when the training and test data come from the same distribution. They guarantee their performance if the deployment data has the same distribution as the data on which the learning algorithm was trained. However, when the distributions are different, the performance of these models deteriorates [START_REF] Wouter | An introduction to domain adaptation and transfer learning[END_REF]. In other words, a machine learning model will not "generalise" well if the training data does not reflect the population on which the model is tested. This phenomenon is also called data bias.

To overcome this, it's important to ensure that the training data matches the distribution of the test data by collecting new data. However, in many applications it is impossible or expensive to collect new data to rebalance the training and test sets [START_REF] Sinno | A survey on transfer learning[END_REF]. That's why research areas such as domain adaptation have grown to develop techniques to bring the training and test distributions closer together [START_REF] Wouter | An introduction to domain adaptation and transfer learning[END_REF].

Like any other machine learning algorithm, uplift modeling can also be prone to data bias. Additionally, as it is a distinct problem from conventional supervised learning, there are specific types of bias that are unique to the uplift modeling problem.

In this section we discuss different sources and types of bias that can be observed in an uplift problem. We divide them into two categories: modeling bias and deployment bias. As their names imply, a modeling bias occurs during the training phase of an uplift model while the deployment bias occurs during the deployment of the uplift model in a real world application.

Modeling bias

Modeling bias typically occurs during the training phase of an uplift model. In principle, the ideal scenario for performing uplift modeling is within a randomised control trial setting, where the data is generated under controlled conditions and biases are minimised between the data from different treatments. However, in practical applications, data is collected from observational studies, i.e. gathered without the subject of a research experiment, where the data generation process is not controlled, and biases are often present.

In this section, we present three types of modeling bias: non-random assignment bias (NRA), non-response bias and confounding variables.

Non-random assignment bias

Non-random assignment (also known as selection bias) [START_REF] Zhang | A unified survey of treatment effect heterogeneity modelling and uplift modelling[END_REF] happens when there are differences between treatment and control groups. Formally, this bias occurs when P (T = 1|X) ̸ = P (T = 0|X) (which also means P (X|T = 1) ̸ = P (X|T = 0)). This can be seen as a covariate shift (see Section 2.5.2) between treatment and control groups. Usually it is easier to collect control data and the treatment group is the most biased because it is more challenging to apply a treatment to individuals and collect the corresponding data due to ethical, political or economic constraints.

This bias problem has been studied in the literature on clinical studies where the goal is to estimate the "Average Treatment Effect" (ATE) defined as

E[Y i (T = 1)- Y i (T = 0)].
In order to estimate it, the "Propensity Score Matching" (PSM) [START_REF] Rubin | Using propensity scores to help design observational studies: Application to the tobacco litigation[END_REF] is used to extract balanced treatment groups on which ATE is estimated. Similarly, in the uplift literature, since uplift methods assume the homogeneity between treatment groups, PSM is used to extract an unbiased sample from a biased dataset. Uplift modeling is applied subsequently as carried in [START_REF] Olaya | A survey and benchmarking study of multitreatment uplift modeling[END_REF]. However, this procedure clearly suffers from a loss of data.

This type of bias is discussed and an experimental evaluation of its effect is carried out in Chapter 5.

Non-response bias

Let's consider a marketing campaign for an internet offer. The treatment group receives the campaign by e-mail, while the control group is not contacted. Nonresponse bias occurs when some individuals in the treatment group are considered to have received the treatment, however, they did not really receive it. For instance, some individuals do not check their emails regularly, and hence they did not read the received email. If there is a common pattern among the people who do not read the email, this leads to non-response bias. For instance, if all older persons in the treatment group do not check regularly their emails, we cannot attribute their buying behaviour to the assigned treatment. This type of bias is called non-response bias and refers to the case where individuals do not respond to the treatment (e.g. do not answer the phone call, do not read the received email or sms). These individuals are part of the treatment group even though they did not actually receive the treatment.

Non-response bias is a phenomenon that also occurs in medical contexts, particularly in clinical trials. For example, consider a clinical trial in which researchers give a drug to one group of people (the treatment group) and a placebo to another group of people (the control group). Some people may not consume the drug, perhaps because they experience more unwanted side effects. This can lead to non-response bias.

The pattern in which non-response occurs can have a significant impact on the data, introducing noise. Rubin's noise taxonomy [START_REF] Roderick | Statistical analysis with missing data[END_REF] provides a systematic approach to classifying different types of noise and missing data. Through this lens, non-response bias is identified as a form of noise that can be categorized:

• Missing not at random (MNAR): happens when the non-response depends on unobserved causes (not included in the variables).

• Missing at random (MAR): occurs when non-response is conditional on covariates X. In other words, when the probability of being a non-response depends only on the observed attributes.

• Missing completely at random (MCAR): occurs when the non-response is completely independent of the initial variable and the covariates. Thus, subjects with MCAR non-response are a random sample.

The specific patterns in which non-response bias occurs can affect the data in distinct ways, presenting unique challenges in each case.

Confounding variables

Confounding variables are not exactly a type of bias, but can be considered a problem in treatment effect estimation. They violate the conditional independence assumption (or unconfoundedness assumption) described in Section 1.3.

Confounding variables are variables that are correlated with both the outcome and the treatment variables. In other words, when individuals who are more likely to have a particular outcome are more likely to receive a treatment. As an example [START_REF] Amin Pourhoseingholi | How to control confounding effects by statistical analysis[END_REF], let's take a medical study investigating the relationship between coffee drinking and lung cancer. If the people (coffee drinkers) in the treatment group of the study were also smokers (without taking the effect of smoking into account), the study might conclude that coffee drinking increases the risk of lung cancer.

According to [START_REF] Amin Pourhoseingholi | How to control confounding effects by statistical analysis[END_REF][START_REF] Jager | Confounding: what it is and how to deal with it[END_REF], there are 3 methods to reduce the effect of confounding variables and distribute them evenly between the treatment groups:

• Randomization helps prevent selection bias. It consists of randomly assigning subjects to treatment and control groups.

• Matching can be used to match individuals from the treatment group with another from the control group based on one or more selection criteria. For example if age, sex and eating habits are the matching variables then a vegeterian male of 25 years in the treatment group is matched with another from the control group. Also, techniques like Propensity score matching can be useful. This was also illustrated in an uplift modeling benchmark study by [START_REF] Olaya | A survey and benchmarking study of multitreatment uplift modeling[END_REF] • Restriction is used especially in clinical trials. If the confounder variable is known, the idea is to eliminate variations in the study by restricting the study for example on the same age or sex for example.

In summary, modeling bias primarily arises from the data used for training an uplift model. They can be caused by differences in the distribution of the treatment and control groups, as is the case with non-random assignment, by the presence of confounding variables or non-response bias. Such biases have the potential to yield poor learning models and erroneous interpretation of the impact of a treatment on the behavior of subjects.

Deployment bias

As with any machine learning problem, uplift modeling can face the problem of deployment bias. Deployment bias occurs when the available data is not representative of the general population, also known as "data shift" [START_REF] Wouter | An introduction to domain adaptation and transfer learning[END_REF][START_REF] Jose | A unifying view on dataset shift in classification[END_REF]. A data shift occurs between a source domain (where we have access to training data) and a target domain (where we apply our machine learning model and where labels are typically not available). Reasons for data shifts can include an outdated training set, different or limited data sources, sample selection bias, or changes in the behaviour of individuals. Before proceeding, note that domain-specific functions given below are denoted by the subscripts S and T a for the "source" and "target" domains, respectively. For example, P S (X|Y ) and P T a (X|Y ) denote the source and target class conditional distributions, respectively. The most common data shifts are:

• Prior shift: refers to changes in the distribution of the output variable.

A prior shift occurs when the prior probabilities of the classes are different, i.e. P S (Y ) ̸ = P T a (Y ), while the posterior distributions are equivalent, P S (X|Y ) = P T a (X|Y ).

• Covariate shift: refers to the case where P S (X) ̸ = P T a (X) while P S (Y |X) ̸ = P T a (Y |X). It most commonly occurs when there is a sample selection bias. For example, a face recognition algorithm that has been trained on young faces, but is used on a dataset of older faces, will suffer from the covariate shift problem. The relationship between input and output is the same, but the training data is not representative of the population of interest.

• Concept shift (also referred to as "concept drift" [START_REF] Gama | A survey on concept drift adaptation[END_REF]) refers to the change in relationships between input and output variables. For example, on a property platform where users mark each listing as "interesting" or "not interesting", changes in the economic situation may change consumers' buying habits over time. In this case, it is not the data distribution or the class distribution that has changed, but the relationship between the data and class variables. Formally, a concept drift occurs if one of the following situations occurs:

-P S (Y |X) ̸ = P T a (Y |X) and P S (X) = P T a (X) -P S (X|Y ) ̸ = P T a (X|Y ) and P S (Y ) = P T a (Y )
It is also related to data drift, where models are trained and deployed online in non-stationary environments.

To summarize, deployment bias can arise when the distribution of labels, covariates, or their relationship differs between the training and deployment data. It is also possible for multiple types of shifts to occur simultaneously. Deployment bias is not specific to uplift modeling problems, it is a commonly recognised issue in various domains of machine learning.

MODL: Minimum Optimized Description Length

This thesis proposes an uplift discretization approach and a new Bayesian decision tree algorithm for uplift modeling based on the Minimum Optimized Description Length (MODL). MODL is a Bayesian approach for density estimation through discretization for supervised learning. It is founded on the Minimum description length (MDL) principle.

In this section, we introduce the MDL principle and present the MODL discretization approach [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF] and the MODL decision trees [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF] as preliminaries for the rest of the thesis.

MDL: Minimum Description Length principle

The Minimum Description Length (MDL) principle [START_REF] Rissanen | Modeling by shortest data description[END_REF] is derived from Shannon's information theory [START_REF] Elwood | A mathematical theory of communication[END_REF] and allows finding the simplest model that best describes the data. The MDL principle is used to select the best model, among a family of models, by taking into account the complexity of the models and the complexity of the data according to the model. According to the MDL principle, the best model M that describes the data D is the model with the minimum description length L(M, D), s.t. L(M, D) = L(M ) + L(D|M ), where L(M ) is the model's description length and L(D|M ) is the description length of the data encoded by the model.

The MODL approach for discretization

The MODL (Minimum Optimized Description Length) [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF] approach is a nonparametric Bayesian approach for discretization and conditional probability estimation, based on the Minimum Description Length (MDL) principle. Let us first introduce the link between a Bayesian and a MDL model selection problem.

A Bayesian approach for model selection From a Bayesian perspective, the best model M , among a family of models, is found by maximizing the posterior probability P (M |D), i.e., to find the one that is most likely given the data. Using Bayes rule, maximizing P (M |D), while taking into account that P (D) is constant for all the candidate models, is equivalent to maximizing the product of the prior and the posterior probabilities: P (M )P (D|M ).

A MDL approach for model selection The previous approach can also be seen from an information theory perspective by using the MDL approach [START_REF] Rissanen | Modeling by shortest data description[END_REF]. As previously mentioned, the goal of the MDL approach is to select the model with the minimal description length L(M |D). Replacing the previously introduced probabilities by their negative log, allows interpreting them as Shannon's code length [START_REF] Elwood | A mathematical theory of communication[END_REF], s.t.:

-log P (M |D) corresponds to L(M |D).

Parameters of a discretization model

The MODL approach comes to apply the MDL approach to the discretization problem to help find the best discretiza-tion model M that maximizes the posterior probability P (M |D). First the data values of a variable are sorted. Then a space of discretization models is defined. A discretization model is described by a set of parameters:

• the number of intervals I

• the boundaries of the intervals, i.e. the number of instances in each interval i denoted N i

• the frequencies of the classes in each interval, i.e., the number of instances in each interval i with class j denoted N ij An Evaluation criterion for a discretization model Using these parameters, the MODL approach defines a prior distribution on a discretization model M . It exploits the hierarchy of the parameters and assumes a uniform distribution at each stage of the hierarchy with independence across intervals. The MODL approach defines then the cost of a model C(M ), i.e., which is the negative log of the posterior probability by:

C(M ) = log N + log N + I -1 I -1 + I i=1 log N i + J -1 J -1 + I i=1 (1 -W i ) log N i ! N i.1 !..N i.J ! Likelihood
Using a search algorithm the MODL approach can score all possible discretization models and selects the one with the minimal criterion.

The MODL classification trees

The MODL approach can also be applied to classification trees [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF]. It allows for the definition of a global criterion for a decision tree model, enabling the selection of the tree model with the minimal tree criterion among a family of tree models. It is distinguished from other tree approaches by being a user parameter-free approach and by defining a global criterion to evaluate a tree model. As a Bayesian approach, it tries to select the most probable tree model given the data by maximizing the posterior probability P (T ree|Data) of a tree model T ree. This is achieved by maximizing the product of the prior probability of the tree and the likelihood of the data given the model, i.e., P (T ree)P (Data|T ree). the set of internal nodes S T ree (an internal node is a node with at least two children).

the set of of leaf nodes L T ree the subset of variables K T ree used by T ree chosen among K variables in the dataset, where K T ree is the number of variables in K T ree .

• The distribution of instances in the structure is described by:

the choice of the test variable X s (also called segmentation variable) for each internal node s its number of partitions I s , where I s > 2 for all internal nodes.

the distribution of instances in each partition i for each internal node s, denoted by: {N si. } 1≤i≤Is

• The distribution of the classes in the structure is defined by the class frequency in each leaf node l denoted by: {N l.j } 1≤j≤J

An Evaluation criterion for a tree model Using these parameters, the prior distribution and the likelihood of T ree are defined. An evaluation criterion C(T ree) is then presented as the negative logarithm of the posterior probability, s.t.:

C(T ree) = -log P (T ree)P (Data|T ree)

= log(K + 1) + log K + K T ree -1 K T ree + + s∈S Tn log K T ree + C Ris (I s ) log 2 + log N s. + I s -1 I s -1 + + s∈S Tc log K T ree + C Ris (I s ) log 2 + log B (V Xs , I s ) + + l∈L T C Ris (1) log 2 + log N l. + J -1 J -1 + + l∈L T log N l. ! N l.1 !N l.2 ! . . . N l.J !
where V Xs is the number of values of a categorical variable X s , B (V Xs , I s ) is the number of possible divisions of V Xs into I s groups and C Ris (I s )2 is Rissanen optimal encoding of an integer I s [START_REF] Wallace | Coding decision trees[END_REF]. A detailed proof can be found in [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF].

Once the tree criterion C(T ree) is defined, a greedy search algorithm is then used to find the tree model that minimizes C(T ree). The algorithm starts from the root node and looks for the best partition according to the tree criterion presented above. The leaves are partitioned as long as the tree criterion is improved. Each leaf is partitioned with MODL discretization presented earlier in Section 2.6.2.

The authors of [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF] claimed that this algorithm may create under-fitted trees and proposed a post-pruning algorithm to find trees that improve C(T ree).

Conclusion

The work of this thesis is at the intersection of Bayesian approaches, Uplift modeling and Data bias.

In this chapter, we have first presented in Section 2.2 the state of the art in uplift modeling approaches. We presented two types of approaches: the metalearners and the direct approaches. The metalearners divide the uplift estimation problem into several steps, each of which can be performed using any supervised machine learning algorithm. The direct approaches, on the other hand, are a set of algorithms specifically designed for uplift modeling. Several algorithms have been proposed in the literature such as decision trees, random forests, SVM and deep learning based methods.

Since one of the main problems with uplift modeling is that the actual uplift values cannot be observed, special metrics have been developed to evaluate its learning algorithms. We presented in Section 2.3 the evaluation metrics used to assess the performance of uplift modeling algorithms. Among the most well-known metrics are the AUUC and the Qini coefficient.

We thereafter introduced the feature selection approaches proposed in the uplift modeling literature. As uplift modeling is a different problem from supervised learning, new feature selection algorithms are required to correctly find the features that contain the treatment effect information. This is accentuated by the fact that the applications of uplift estimation, such as telecommunications data, contain a large number of collected features.

We went on to present the problem of data bias in the uplift problem. Again, as this is a different problem to supervised learning, different types of bias occur in each of the modeling and deployment phases. The modeling bias includes the NRA bias, the non-response bias and the confounding bias.

Finally, the MODL approach is presented. The MODL (Minimum Optimized Description Length) approach is a Bayesian density estimation approach developed in Orange. The MODL approach was designed for the supervised setting and was later extended to the unsupervised setting [START_REF] Mahrsi | Co-clustering network-constrained trajectory data[END_REF], sequence mining [START_REF] Egho | A user parameter-free approach for mining robust sequential classification rules[END_REF], and applied to the design of several learning algorithms such as Naive Bayes [START_REF] Boullé | Compression-based averaging of selective naive Bayes classifiers[END_REF] and Decision Trees [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF]. This thesis proposes an uplift Bayesian approach based on MODL.

Contents

Introduction

In this chapter, we present a parameter-free feature selection method for uplift modeling founded on a Bayesian approach. Following a part of literature on feature selection that performs a discretization of numerical features [START_REF] Liu | Feature selection via discretization[END_REF][START_REF] Sharmin | Simultaneous feature selection and discretization based on mutual information[END_REF] as a basis for feature selection, we first describe an automatic feature discretization method for uplift modeling that we call UMODL -for Uplift MODL (c.f. Section 2.6).

As a popular data preprocessing technique in data mining, data discretization converts continuous data into a set of categories that appropriately retains as much information as possible from the original continuous attribute. While data The newly proposed discretization technique can also be used as a univariate uplift estimator. The uplift modeling problem can be viewed as a density estimation challenge, where the goal is to estimate the regions in a variable space where the density of the target variable Y significantly differs between the treatment and control groups. A discretization method can then be useful. Our newly proposed method, UMODL (Uplift Minimum Optimized Description Length), is based on the MODL approach [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF], a discretization approach that aims to split a continuous feature into a list of intervals. UMODL discretizes a variable by taking into account the presence of treatment and control groups and facilitates the estimation of the density of the outcome variable for each treatment group within each interval. This is achieved by simply counting the number of instances in each interval and the number of positive outcomes for each treatment group.

For an intuitive understanding, consider the left part of Fig. 3.1, which shows the variable X next to the output distribution in the treatment and control groups. Our goal is to determine the optimal discretization shown in the right of Fig. 3.1. The discretization process can be seen as an estimate of the treatment effect, as it isolates regions with different treatment effect values. Consequently, the uplift value can be calculated individually for each interval by calculating

CAT E i = P i (Y = 1 | T = 1) -P i (Y = 1 | T = 0) for each interval i.
UMODL is based on a space of discretization models and a prior distribution. From this model space, we define a Bayesian optimal evaluation criterion of a discretization model for uplift. We then propose an optimization algorithm that finds a near-optimal discretization for uplift estimation in O(n log n) time. Experiments demonstrate the high performance of this new discretization method.

We then describe UMODL-FS a parameter-free feature selection method for uplift built upon UMODL. Once UMODL identifies the Bayesian optimal discretization for a feature, UMODL-FS is employed to assess the difference in outcome distributions between the treatment and control groups. It is a filter-based method (c.f Section 3.5) that can be used as a pre-processing step before training an uplift model to eliminate features that are not relevant to the uplift estimation. Lastly, we conduct an experimental protocol that validates the effectiveness of UMODL-FS in eliminating irrelevant features and helping the uplift model in achieving superior performance compared to state-of-the-art techniques.

The chapter is structured as follows: Section 3.2 first presents the evaluation criterion of a Bayesian optimal discretization model for uplift and its proof. It then presents the search algorithm and the post-optimisation steps to find the parameters that lead to the best evaluation criterion. Section 3.3 presents the quality evaluation experiments of the discretization approach on a set of synthetic uplift data samples and concludes with a discussion of the results. Finally, Section 3.5 presents the UMODL feature selection approach, the experimental protocol and the results. This work is the object of the following publication: Rafla, M., Voisine

UMODL

This section introduces UMODL, a novel approach for uplift discretization. We first describe the parameters of an uplift discretization model, which will be used to define the prior and the likelihood of an uplift discretization. The defined prior and likelihood are then used to compute an evaluation criterion for an uplift 48 3.2. UMODL discretization model.

After establishing the evaluation criterion, we present the search algorithm that identifies the Bayesian optimal uplift discretization for a given variable. In other words, the search algorithm will be used to automatically find the parameters that lead to the best criterion.

UMODL Criterion

In Section 2.6, we presented the MODL (Minimum Optimized Description Length) approach. MODL is a Bayesian approach for density estimation through discretization for supervised learning. It is founded on the Minimum descriptiom length (MDL) principle.

While MODL properly exploits discretization for density estimation, it is not suitable for uplift modeling since uplift deals with two treatment groups and the estimation of the conditional probabilities of the outcome variable Y given an attribute X also depends on the treatment variable T .

We now introduce the new criterion that we propose to define the best discretization model for uplift. Let M be an uplift discretization model and D denotes data. From a Bayesian point of view, the best uplift discretization model is found by maximizing the posterior probability of the model given the data P (M |D). Let us consider the Bayes rule:

P (M | D) = P (M )P (D | M ) P (D) (3.1)
Given that P (D) is constant, maximizing P (M |D) is equivalent to maximizing P (M )P (D|M ), i.e the prior probability and the likelihood of the data given the chosen model.

Remark:

This optimisation problem represents a trade-off between the prior probability and the likelihood. A simple discretization model with an extremely high prior probability can be represented by a single interval model. However, the likelihood associated with such a model is significantly low. On the other hand, a discretization model characterised by a very high likelihood would be an elementary interval model, where each value of the variable has its own distinct interval. However, this type of model is associated with a significantly low prior probability.

Before determining the posterior probability for an uplift discretization model and presenting the UMODL criterion, let us first introduce some notations:

(W i =1) or not (W i =0)
We define an uplift discretization model M by the number of intervals, the bounds of the intervals, the presence or absence of a treatment effect, class frequencies per interval or for each treatment per interval. In other words, a model M is defined by the following parameters (cf. Fig. 3.2):

{I, {N i }, {W i }, {N i.j } W i =0 , {N itj } W i =1 }
These parameters are exploited according to a particular hierarchy when defining the prior distribution of M denoted P (M ). This hierarchy requires the parameters to be selected in a particular order. We will discuss the hierarchy of the parameters in the next section. The evaluation criterion C(M ) which is the cost of an uplift discretization model M is defined then by:

C(M ) = -log P (M ) × P (D|M )
Taking the negative log turns the maximization problem to a minimization one. M is optimal if C(M ) is minimal.

How to define the prior distribution ?

To define the prior distribution of the model parameters P (M ):

1. We first exploit the hierarchy of the parameters of a discretization model. This hierarchy requires the parameters to be selected in a particular order. First, we determine the number of intervals I, followed by the location of these I intervals or boundaries. Next, we determine whether each interval contains a treatment effect or not. Finally, we decide the distribution of the outcome variable within each interval or the distribution of the outcome variable for each treatment.

Next, we assume a uniform distribution at each stage of this hierarchy.

In other words, we assume that (a) The number of intervals I is equally likely to be any value between 1 and N .

(b) Given the number of intervals I, each possible way of dividing the data into I intervals has an equal probability.

(c) There is an equal probability that an interval i contains a treatment effect or not. Therefore, the value of the term W i has an equal chance of being either 1 or 0.

(d) Given an interval i and the value of W i , every distribution of the class values in the interval is equiprobable, or alternatively, every distribution of the class values for each treatment in the interval is equiprobable.

3. Finally, we assume the independence of the distributions across intervals. This assumption is based on the IID hypothesis [START_REF] Boullé | Recherche d'une représentation des données efficace pour la fouille des grandes bases de données[END_REF]. This assumption enables the evaluation of the model's prior as a product of multiple terms, which will be demonstrated next concerning the prior definition (Eq. 3.3) and its proof, as well as the likelihood definition in Eq. 3.10. By taking the negative logarithm, the prior can be assessed as the sum of these terms, as illustrated in the UMODL criterion in Eq. 3.2.

The UMODL criterion

Using the components described above (the parameter hierarchy, the uniform distribution assumption and the independence assumption), we express C(M ) in terms of the parameters of an uplift discretization model and obtain Eq. 3.2, which we demonstrate below.

C(M ) = log N + log N + I -1 I -1 + I × log 2 + I i=1 (1 -W i ) log N i + J -1 J -1 + I i=1 (1 -W i ) log N i ! N i.1 !..N i.J ! Likelihood + I i=1 W i t log N it. + J -1 J -1 + I i=1 W i t log N it. ! N it1 !..N itJ ! Likelihood (3.2)

UMODL

Proof of Eq 3.2. We express P (M ) and P (D|M ) according to the parameters of an uplift discretization model. We introduce a prior distribution by exploiting the hierarchy of the models' parameters. Assuming the independence of the local distributions across the intervals, we obtain:

P (M ) = P (I) × P ({N i }|I)× i P (W i |I) (1 -W i ) × P ({N i.j }|I, {N i }) + W i × t P ({N itj }|I, {N it. }) (3.3)
We express each of the terms of Eq. 3.3 according to the parameters of M assuming a uniform distribution for each parameter. Assuming that the number of intervals I is uniformly distributed between 1 and N , the first term in Eq. 3.3 becomes:

P (I) = 1 N (3.4)
Given a number of intervals I, all the discretizations into I intervals (i.e. the choices of the bounds) are equiprobable. Computing the probability of an interval set leads to a combinatorial calculation of the number of all possible interval sets or equivalently the number of ways of distributing the N instances in the I intervals, with counts N i per interval. The second term of Eq. 3.3 is then:

P ({N i }|I) = 1 N +I-1 I-1 (3.5)
For a given interval i, we assume that a treatment can have an effect or not, with equal probability, i.e. P (W i |I) = 1 2 . We obtain:

i P (W i |I) = 1 2 I (3.6)
In the case of an interval i where there is not effect of the treatment (W i = 0), UMODL describes one unique distribution of the outcome variable. Given an interval i, its number of examples N i is known. Assuming that each of the class distributions is equiprobable, we end up also with a combinatorial problem:

P ({N i.j }|I, N i ) = 1 N i +J-1 J-1 (3.7)
In the case of an interval i with an effect of the treatment (W i = 1), UMODL describes two distributions of the outcome variable, with and without the treatment. Given an interval i and a treatment t, we know the number of examples

N it.
. Assuming that each of the distributions of class values is equiprobable, we get:

P ({N itj }|I, N it. ) = 1 N it. +J-1 J-1 (3.8)
After defining the models' prior, we define the likelihood P (D|M ) of the data given the uplift discretization model. For each multinomial distribution of the outcome variable (a single or two distinct distributions per interval depending on whether the treatment has an effect or not), we assume that all possible observed data D i consistent with the multinomial model are equiprobable. Using multinomial terms, we obtain the following likelihood term:

P (D|M ) = i P (D i |M ) (3.9) = i (1 -W i ) × 1 (N i !/N i.1 !..N i.J !) + W i × t 1 (N it. !/N it1 !..N itJ !) (3.10)
Combining the prior P (M ) (Eq 3.4 to 3.8) with the likelihood P (D|M ) (Eq. 3.10), we obtain P (M )P (D|M ). Taking the negative log yields to the UMODL criterion presented in Eq. 3.2. Coming back to Eq. 3.2, the prior terms of the first line come from Eq. 3.4 to 3.6. In the second line of Eq. 3.2 (modeling a situation w/o a treatment effect) and the third line (situation with a treatment effect), the first terms are prior terms (Eqs 3.7-3.8) and the second terms are likelihood terms (Eq. 3.10).

Search algorithm and post-optimization

We sketch below our search algorithm to find the best model w.r.t. the UMODL criterion. This algorithm finds the optimal values of the parameters that minimize C(M ). The principle of this algorithm is inspired by the search algorithm [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF] which we adapt to our criterion. As an optimal search algorithm is not practical due to the complexity of the problem, we build a greedy algorithm 1 .

Greedy Search algorithm

The search algorithm is a greedy bottom-up algorithm with the following steps:

• The algorithm starts by making an elementary discretization such that all examples with the same value have their own interval,

• Compute the costs of all possible merges i.e. try to merge adjacent intervals,

• Merge the two adjacent intervals that decrease C(M ) the most,

• Recalculate the cost of all possible adjacent merges and select the merge that reduces C(M ) the most,

• Repeat until no merge decreases C(M ).

While this algorithm is complex, it can be implemented in O(n log n) time [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF].

Post-optimization

This greedy search algorithm can fall into a local minimum, so post-optimization steps are needed to perturb the interval bounds. We used post-optimization steps that consist of recurrent splits, merges, merge splits, and merge merge splits of adjacent intervals, as described in [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF] but designed in this work for uplift.

Conclusion

The presented discretization approach is a density estimation approach for uplift modeling. We model the probability of Y conditionally on the explanatory variable X and a binary treatment variable T . The search algorithm we present is looking for the parameters I, {W i }, {N i }, {N i.j }, {N itj }, and {W i } that minimize the cost of the model. In other words, the search algorithm tries to find the optimal discretization in the Bayes sense that best estimates the real densities of the outcome variable Y conditionally on X and T . Once a discretization and its parameters are defined, the estimation of the CATE for each interval is simple. As shown in Fig. 3.2, assuming a binary outcome variable Y and given W i = 1, we have

P i (Y = 1|T = 1) = N i11 /(N i11 + N i10 ) and P i (Y = 1|T = 0) = N i10 /(N i01 + N i00 ), therefore CAT E i = P i (Y = 1|T = 1) -P i (Y = 1|T = 0). For intervals with W i = 0, CAT E i is considered insignificant.
The UMODL discretization method has the advantage of not relying on userspecified parameters. All parameters are automatically determined by the search algorithm (Section 3.2.2). In addition, UMODL does not require any prior assumptions about the data distribution. It also facilitates interpretation, as each identified interval represents the distribution of a set of examples.

UMODL quality evaluation experiments

This section experimentally evaluates whether UMODL is a good estimator of uplift. The principle of the experiments is to generate data with different synthetic uplift patterns in order that results of UMODL can be compared to true uplift. A synthetic uplift pattern is a data pattern where P (Y = 1|X, T = 1) and P (Y = 1|X, T = 0) are identified for each example. Therefore several indicators can be observed: (1) the number of intervals founded by UMODL w.r.t. the characteristics of the uplift pattern, (2) the RMSE (root mean squared error) between the real uplift and the estimated uplift by UMODL computed for each instance and (3) the number of instances needed by UMODL to find the uplift pattern. We generate synthetic uplift patterns of different characteristics for simulating various situations.

Description

The experimental protocol is made of the following steps:

1. Define a particular synthetic uplift pattern of one dimension.

2. Generate several train samples according to the defined pattern with 40 different number of instances (also called data size) ranging from 10 to 100,000 instances. For each data size, generate ten datasets. All generated data are uniformly distributed on the [0, 10] numerical domain for each of the treatment (T = 1) and control groups (T = 0).

3. Generate a test set of 10,000 instances based on the defined uplift pattern.

4. For each training sample, apply the UMODL approach to search for the best discretization model.

5.

For each experiment, the obtained discretization model is then applied to the test set, and RMSE is computed by comparing for each data point: (a) the CATE estimation in the found interval and (b) the real CATE value.

6. By observing both the number of found intervals for each dataset and the RMSE values, we can determine whether the UMODL approach manages to find the synthetic pattern or not.

7. Repeat these steps with different synthetic uplift patterns.

Synthetic uplift patterns

We generate four bin-based patterns and one continuous pattern. We use patterns of different characteristics2 to evaluate how UMODL performs both in various situations and different rates of uplift. The patterns are illustrated in Fig. 3.3 and depicted below.

• Crenel pattern 1 (cf. Fig. 3.3a): this crenel pattern is made of 10 intervals containing a repeated sequence of a positive treatment effect followed by a negative one. We generated five versions of this pattern with different uplift values. In other words, this pattern was generated with different θ values, where a positive treatment effect is equal to θ -(1 -θ), resulting in 2θ -1, and a negative treatment effect is equal to (1 -θ) -θ, which simplifies to 1 -2θ.

• Crenel pattern 2 (cf. Fig. 3.3b): is a slightly different crenel pattern similarly made of 10 intervals containing a repeated sequence of a positive treatment effect followed by no treatment effect. We generated five versions of this pattern with different treatment effects (uplift). In other words, this pattern was generated with different θ values, where a positive treatment effect is equal to θ -(1 -θ), resulting in 2θ -1.

• Trigonometric pattern (cf.

Results

Results are given in Figures 3.4, 3.5 and 3.6. We start by the central question "Is UMODL a good estimator of uplift?" and provide complementary observations. Is UMODL a good estimator of uplift? From Figures 3.4 (left) and 3.5 (left), we clearly see that even when the treatment effect is very small per interval (grey curves), UMODL is able to find the proper number of intervals of the uplift patterns. This is also illustrated by the RMSE curves (Figures 3.4 (right) and 3.5 (right)) showing that RMSE always converges towards 0 for sufficiently large datasets. Similar performances are reported with the trigonometric pattern (cf. Fig. 3.6a), the scissors pattern (cf. Fig. 3.6b) and the continuous pattern (cf. Fig. 3.6c) except that the number of estimated intervals is not a relevant indicator for the continuous pattern because this pattern is continuous.

How many instances are needed to find the uplift pattern according to its characteristics? When the differences of densities between adjacent intervals get smaller, UMODL needs more instances to give prominence to a model with more intervals. This is typically the case with the scissors pattern (cf. Fig. 3.6b). Analogous behaviors are observed in Figures 3.4 and 3.5. For example, in Fig. 3.4, the blue curve finds the uplift pattern with less instances than the red curve. Interestingly, UMODL succeeds in finding the appropriate intervals even when there is no treatment effect (for example, identifying the intervals [START_REF] Alelyani | Feature selection for clustering: A review[END_REF][START_REF] Angrist | Treatment effect[END_REF], [3,4], [START_REF] Athey | Machine learning methods for estimating heterogeneous causal effects[END_REF][START_REF] Richard Bellman | Dynamic programming[END_REF], . . . in the results of the crenel pattern 2, as depicted in Fig. 3.5).

Does UMODL overfit?

Another important aspect of the UMODL discretization is that the UMODL method does not overfit, i.e. UMODL always finds the ten intervals of the underlying patterns and does not consider extra intervals even when the data size increases significantly (cf. Fig. 3.4 and Fig. 3.5). With the continuous pattern, UMODL goes on to consider more intervals as long as the size of the data increases (cf. Fig. 3.6c) which is appropriate since the pattern is continuous and there is no defined intervals.

How to deal with categorical variables?

So far, our experiments have only been carried out on synthetic data with continuous attributes, as this type of data requires discretization when performing density estimation. However, it is crucial to acknowledge the existence of another type of data: categorical data, which can be considered as grouped information covering categories such as job type, phone type, and subscription type, among others.

When dealing with categorical data, the objective shifts from discretizing the variable to performing value grouping. In other words, given a categorical variable, the goal is to group the values of the variable that have similar behaviour: either the same outcome distribution or the same treatment effect. Assuming a variable 'Subscription' that has 3 possible values 'Prepaid', 'Postpaid', 'Family Plan', the number of possible groupings of these values is equal to the number of Bell, which counts the number of possible partitions of a set. These sets are: Yet a basic technique for dealing with categorical variables in data mining tasks is unsupervised label encoding. Unsupervised label encoding involves assigning an integer value to each instance of a categorical variable. This assignment can be done either randomly or according to the lexicographic order of the categorical values. The UMODL approach can then be used to discretize the variable as if it were a continuous numerical attribute. However, unsupervised label encoding alone may not be sufficient for a discretization task because UMODL considers an order for the values, and this order may not be efficient. This inefficiency occurs because the numerical values assigned to each category are random and unrelated to the outcome distribution or the uplift.

In this section, I will show why an unsupervised label encoding is not efficient and propose an adequate uplift-based label encoding that allows better value grouping and improves the UMODL discretization approach.

Why unsupervised label encoding is not efficient ?

An unsupervised label encoding may be particularly inefficient in cases where there is an imbalance in the size of different values. For instance, consider a scenario with a 'subscription' variable having three distinct values: 'Prepaid', 'Postpaid', and 'Family Plan', each having a different level of uplift (see Table 3 By assigning the integer values 1, 2 and 3 to 'Prepaid', 'Postpaid' and 'Family plan' respectively, in the given order, we can encode these values. In this situation, the resulting density plot is shown in Fig. In Fig. 3.7, an ideal discretization according to this encoding requires each categorical variable value to be separated into a separate interval, with the parameter W = 1 in each interval. However, if there are very few examples for a 'Family Plan' value (as shown in Table 3.1), the robust UMODL method is less likely to create an interval where there are very few examples. Although this would improve the likelihood component (see Eq. 3.2), the three-interval model significantly increases the cost of the prior component. Instead, UMODL would choose a two-interval model, with the first interval consisting of 'Prepaid' and the second interval including both 'Postpaid' and 'Family Plan'. This approach achieves a trade-off that balances the costs of the likelihood and the prior components.

However, by reordering the encoding of the values, UMODL can achieve a better trade-off, which will be discussed in the next section.

A numerical illustration For instance, let's consider the the data in Table 3.1 comprising 12,000 examples, which includes 5,970 'prepaid', 5,970 'postpaid', and only 60 'Family Plan'. Each value is equally distributed between the treatment and control groups. Assume we have randomly encoded the values of the categorical variable as depicted in Fig. 3.7. In that case, as discussed before, UMODL will opt the the two interval model named M 1 , as shown in Fig. 3.8. Based on the information provided in Table 3.1, we can determine that C(M 1 ) = 6737.02. The prior cost of M 1 islog P (M 1 ) = 52.1976, while the likelihood term cost amounts tolog P (D|M 1 ) = 6684.82. UMODL being a robust method would choose the tradeoff between the prior and the likelihood of M 1 rather than a three-interval model. A three-interval model, named M 2 in Fig. 3.8 will have a cost of C(M 2 ) = 6740.88, consisting of a priorlog P (M 2 ) = 68.439 and a likelihoodlog P (D|M 2 ) = 6672.4.

As demonstrated, the cost of M 1 is lower, despite having a worse likelihood. This is because introducing an additional interval with a limited number of examples proved to be expensive. M 1 also proved to be much better than the null model M ∅ , i.e. the model with only one interval. This model assumes that there is only one probability distribution and treats the variable as a random variable. The null model is shown in 3.9. Calculating the cost of this model yields C(M ∅ ) = 8322.96. The cost of the prior of this model is certainly less than the other models presented log P (M ∅ ) = 19.47. However, the cost of the likelihood of our data given this model is very large; -log P (D|M ∅ ) = 8303.4, Note: These calculations can simply be done using the criterion equation in Eq. 3.2 and the information of data sizes in Table 3.1. In summary, an unsupervised approach to label encoding assigns a random ranking to categorical values, which is often not optimal. In the following section, I present an uplift-based label encoding that allows UMODL to find a better trade-off for value grouping for categorical variables.

An uplift-based label encoding for UMODL

In the earlier example, 'Family Plan' and 'Postpaid' values were grouped by UMODL despite having different uplift values. A solution is to intelligently encode categorical values by the order of the uplift values: 'Prepaid' as 1, 'Family Plan' as 2, and 'Postpaid' as 3. This groups similar uplift values, as seen in Fig. 3.10. Based on this encoding, the UMODL discretization method selects the two-interval model, M 3 , as optimal. This model accurately groups {P repaid, F amilyP lan} and {P ostpaid} together, effectively grouping values with similar uplifts.

The cost of M 3 is given by C(M 3 ) = 6728.4, with a prior's cost oflog P (M 3 ) = 52.19 and a likelihood oflog P (D|M 3 ) = 6676.2. The proposed encoding does not always yield improvements, though it doesn't negatively affect discretization. If 'Family Plan' had an uplift value of 0.9, reencoding and applying UMODL discretization would result in a two-interval model grouping P ostpaid, F amilyP lan. While not highly accurate, it is the best achievable trade-off given the data.

Note:

The examples above involve a situation with parameter W has the value 1 for each interval, indicating a treatment effect. The UMODL criterion (Eq. 3.2) identifies intervals with significant uplift and unique outcome variable distributions, with the search algorithm determining parameter W for each interval. In cases where the uplift for each categorical variable value is minimal (W = 0), encoding values based on uplift is ineffective. Instead, we focus on encoding values according to the outcome distribution within each interval. I propose that the ideal solution would involve developing an algorithm that combines both encoding approaches (ranking by uplift values and ranking by outcome distribution). Designing such an algorithm presents a promising perspective for this thesis.

UMODL Feature Selection

As previously discussed in Section 2.4, the telecommunications sector collects significant amounts of data (containing hundreds to thousands of features) derived from services such as mobile internet, home internet, SMS and phone calls. This data contains a significant amount of noise and irrelevant features, which can cause significant challenges for supervised machine learning models, such as the curse of dimensionality. Feature selection serves as an essential step to increase model efficiency and improve interpretability.

In this section I describe how the UMODL discretization method can be used to develop a novel feature selection technique, which I have named 'UMODL-FS', tailored to uplift modeling. I then present the experimental protocol we used to evaluate whether UMODL-FS efficiently improves the uplift models.

Description of UMODL feature selection

In this section I will explain the UMODL feature selection technique. The UMODL Feature Selection (UMODL-FS) calculates the importance of a feature X by first discretizing it using the UMODL discretization approach. The method then computes the summed Euclidean distances between the outcome distributions within the treatment and control groups over the intervals found. To elaborate further:

1. Given a feature X, we apply the UMODL discretization method to find the optimal uplift discretization model as presented in Section 3.2.1.

2. Compute for X an importance score (described below), denoted by imp.s(X), which is the divergence measure of the treatment effect over the found intervals.

3. We repeat these steps for each feature of the dataset.

4. All features with imp.s(X) > 0 are considered relevant for the uplift estimation, while any feature with imp.s(X) = 0 is eliminated.

We define imp.s(X) as follows. Assuming p i = P i (Y = 1|T = 1) and q i = P i (Y = 1|T = 0). We define:

imp.s(X) =    I i=1 N i N D(p i : q i ), if I > 1 0, otherwise . (3.11)
where the distribution divergence measure D is the squared euclidean distance. We choose the squared euclidean distance for the divergence since it is symmetric and stable [START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF]. UMODL-FS considers irrelevant for the uplift estimation any feature with imp.s(X) = 0 and keeps for the uplift modeling any feature with imp.s(X) > 0. When UMODL finds a single interval for a feature, it means there is only one distribution for all instances and thus a non-informative feature (i.e . imp.s(X) = 0). Unlike feature selection methods of the literature [START_REF] Zhao | Feature selection methods for uplift modeling[END_REF], our approach does not require parameters to set, and there is no need to give the number of features to keep or delete.

Experimental Protocol

To compare UMODL-FS to the state-of-art uplift feature selection methods (cf. Section 3.5), we design the following experimental protocol:

1. For each dataset, we generate eleven variants of the dataset, each with an incremental total number (from 0 to 100) of noise features. Noise features are sampled from N (0, 1) for each of the treatment and control groups.

2. For each variant, we apply the following feature selection methods (previously described in Section 2.4): (a) KL-filter (b) Chi-filter (c) ED-filter (d) LR-filter (e) F-filter (f) UMODL-FS.

For KL-filter, Chi-filter and ED-filter, we set the number of bins to 10.

3.

To have the same number of features for each feature selection method and perform a fair comparison, we pick the M most important features, where M is the number of all features deemed informative by UMODL-FS.

4. With these sets of features, we build uplift models: a two-model approach with logistic regression [START_REF] Günter | Heterogeneous treatment effects and optimal targeting policy evaluation[END_REF] and X-Learner with linear regression [START_REF] Jacob | Cate meets ml[END_REF].

5. The learning process is done with stratified ten-fold cross-validation. Test samples are used to evaluate the performance of uplift models based on the selected features.

6. The qini coefficient metric [START_REF] Devriendt | Learning to rank for uplift modeling[END_REF] is used to evaluate the performance of the uplift model.

Datasets

Experiments are conducted on two publicly available datasets which are usual on the uplift community:

1. Criteo dataset [START_REF] Diemert | A Large Scale Benchmark for Uplift Modeling[END_REF]: a real large scale dataset constructed by assembling data resulting from several incrementality tests in advertising. In the experiments, we use a random sample of 10,000 instances with the 'visit' variable as outcome variable.

2. Zenodo synthetic dataset3 : this dataset was created for evaluating feature selection methods for uplift modeling. It has three types of features: (a) uplift features influencing the treatment effect on the conversion probability (outcome variable is 'conversion'); (b) classification features influencing the conversion probability independent of the treatment effect; (c) irrelevant features. This dataset consists of 100 trials of different patterns. Each trial has 10,000 instances and 36 features.

Results

Fig. 3.11 presents the results on the use of UMODL-FS for uplift modeling. In all experiments, UMODL-FS selects the set of features leading to the uplift model with the best qini coefficient (therefore the best uplift model) whatever the used uplift approach. Remarkably, the more noisy features are added, the more the qini difference between UMODL-FS and other feature selection methods increases. Fig. 3.12 indicates the percentage of added noisy features which are selected by the different feature selection methods according to the number of added noisy features. UMDOL-FS never selects a noisy feature. It illustrates the clear ability of UMODL-FS to remove noisy features. On the contrary, all other methods select noisy features and the percentage of the selected noisy ones increases as the number of added noisy features increases. To sum up, the more the number of added noisy features, the more the feature selection methods of the literature select irrelevant features as informative. In contrast, UMODL-FS always neglects irrelevant features and has the most stable qini coefficients. Moreover, UMODL-FS does not require to set a parameter giving the number of features to keep.

Conclusion

In this chapter, we have proposed a new non-parametric Bayesian approach for uplift discretization and feature selection. We have defined UMODL, a Bayes optimal evaluation criterion of a discretization model for uplift modeling and a search algorithm to find the best model. We have conducted an experimental protocol to assess UMODL as an uplift estimator through discretization. We defined different synthetic uplift patterns and generated accordingly several datasets with several data sizes. The use of synthetic data gave us the advantage to know the true uplift value and thus be able to compare the estimated uplift value by our approach and the true one. By observing the RMSE of the predicted uplift values and the number of found intervals by data size, we were able to infer the following chacarteristics: 1. UMODL is a good uplift estimator through discretization.

UMODL does not overfit

It needs sufficient number of instances to give prominence to a model with more intervals

We have also shown that UMODL can effectively handle categorical variables, and we have introduced an adequate label encoding technique that helps UMODL to identify more appropriate intervals, especially when there is an imbalance in the values of a variable.

Finally, we have presented UMODL-FS, a feature selection method for uplift. We conducted an experimental protocol on real and synthetic datasets, where the idea was to gradually add noisy features and build several uplift models, each with a different feature selection method as a preprocessing step. Experiments show that UMODL-FS removes irrelevant features and clearly outperforms state of the art methods by providing uplift models with the highest and most stable qini coefficients. The method is parameter free, making it easy to use.

Introduction

Decision tree algorithms have been developed in state-of-the-art uplift modeling approaches (see Section 2.2.2). These algorithms aim to partition the feature space into distinct branches with the aim of identifying leaf nodes that have the most important difference in the outcome distribution between the treatment and control groups. The main advantage of these algorithms is their interpretability, which is very important for telecom companies when dealing with clients.

However, a significant drawback of state-of-the-art uplift decision tree algorithms is the need for user-defined parameters to train a decision tree model [START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF]. Examples of these parameters include the maximum depth of the tree, the maximum number of features to be used, and the minimum number of instances required in a leaf node. These decision tree algorithms depend only on local independent splits at each node. Once a tree model has been trained, a pruning step is performed to avoid overfitting and improve the predictive performance of the model. This chapter introduces a novel user parameter-free decision tree algorithm called UB-DT that is specifically designed for uplift modeling. UB-DT is characterized by a Bayesian global criterion for an uplift decision tree that evaluates the quality of an induced uplift decision tree. The Bayesian evaluation global criterion for uplift decision trees T is defined by the posterior probability of T given uplift data.

In this chapter, we first define the parameters of an uplift decision tree model and demonstrate how to derive an uplift tree global criterion using these parameters. Our aim is to convert the uplift tree learning problem into an optimization problem, in which the goal is to search for the parameters that yield the best possible uplift tree model (i.e., with the highest global criterion score). Then, we present a search algorithm and introduce an extension for random forests, namely UB-RF.

Finally, we evaluate our proposed approaches using large scale experiments on real and synthetic datasets. These experiments show the efficiency of our methods over other state-of-art uplift modeling approaches.

The chapter is structured as follows: Section 4.2 presents the evaluation criterion for an uplift decision tree T. It starts by presenting the parameters of T and the notations associated. Then it presents the evaluation criterion with a detailed proof in Section 4.2.3. We then present the decision tree algorithm that searches for the Bayesian optimal uplift tree model with the best criterion and its extension to a random forests algorithm. Finally in Section 4.3, we compare UB-DT and UB-RF with several uplift approaches on real and synthetic datasets.

Uplift Bayesian Decision Tree approach

UB-DT is made up of two ingredients: a global criterion C(T) for a binary uplift decision tree T and a tree search algorithm to find the most probable optimal tree. We start by presenting the structure of an uplift tree model. Then we describe the new global criterion for an uplift decision tree and the algorithm to give the best tree. Finally we show how the approach is straightforwardly extended to random forests. We define a binary uplift decision tree model T by its structure and the distribution of instances and class values in this structure. The structure of T consists of the set of internal nodes S T and the set of leaf nodes L T . The distribution of the instances in this structure is described by the partition of the segmentation variable X s for each internal node s, the class frequency in each leaf node where there is no treatment effect, and the class frequency on each treatment in the leaf nodes with a treatment effect. More precisely, T is defined by:

Parameters of an uplift tree model

• the subset of variables K T used by model T. This includes the number of the selected variables K T and their choice among a set of K variables provided in a dataset, we note K = |K|.

• a binary variable I n indicating the choice of whether each node n is an internal node (I n = 1) or a leaf node (I n = 0).

• the distribution of instances in each internal node s, which is described by the segmentation variable X s of the node s and how the instances of s are distributed on its two child nodes.

• a binary variable W l indicating for each leaf node l if there is a treatment effect (W l = 1) or not (W l = 0). If W l = 0, l is described by the distribution of the output values {N l.j. } 1≤j≤J , where N l.j. is the number of instances of output value j in leaf l. If W l = 1, l is described by the distribution of the class values per treatment {N l.jt } 1≤j≤J,1≤t≤2 , where N l.jt is the number of instances of output value j and treatment t in leaf l.

These parameters are automatically optimized by the search algorithm (presented in Section 4.2.4) and not fixed by the user. In the rest of the paper, the following notations N s. , N si. , N l. and N l..t will additionally be used to respectively designate the number of instances in node s, in the i th child of node s, in the leaf l and treatment t in leaf l.

Uplift tree evaluation criterion

We now present the new global criterion C(T) which is an uplift tree model evaluation criterion. UB-DT applies a Bayesian approach to select the most probable uplift tree model T that maximizes the posterior probability P (T|Data). Let us consider the Bayes rule:

P (T|Data) = P (T)P (Data|T) P (Data)
Following the same approach of the UMODL discretization model criterion in Chapter 3, giving that P (Data) is constant, maximizing P (T|Data) is equivalent to maximizing the product of the prior and the likelihood i.e. P (T) × P (Data | T). This product represents a trade-off problem. On one hand, maximising the likelihood component requires a tree model with a number of leaf nodes equal to the number of data points. However, this leads to a smaller prior component. On the other hand, optimising the prior probability requires a decision tree model consisting of only a root node, but this results in a significantly reduced likelihood component.

Taking the negative log turns the maximization problem into a minimization one:

C(T) = -log (P (T) × P (Data|T))
where C(T) is the cost of the uplift tree model T. T is optimal if C(T) is minimal.

How to define the prior distribution P (T)?

To define the prior distribution of a tree model T, we first exploit the hierarchy of the presented uplift tree parameters. This hierarchy describes the dependence relationships between parameters and requires the parameters to be selected in a particular order. The hierarchy of the tree model is described from the root node to its children and recursively to the leaves.

We also assume the independence of the distribution of the outcome values between children nodes. This assumption allows the prior of the model to be evaluated as a product of several terms. Taking the negative log, the prior can be evaluated as the sum of these terms (cf. Eq. 4.1). Furthermore, we assume a uniform distribution of parameters at every stage of the hierarchy, as described in Section 4.2.3.

Using the components of the prior term described above (the parameter hierarchy, the uniform distribution assumption and the independence assumption), we show next the global evaluation criterion for an uplift decision tree and its detailed proof.

The Bayesian decision tree criterion

Combining the prior term P (T) and using the likelihood terms on the tree leaves, we express the negative log of the posterior probability, our criterion C(T), as follows (cf. Eq. 4.1):

C(T) = log(K + 1) + log K + K T -1 K T Variable selection + s∈S Tn log 2 + log K T + log(N s. + 1)
Prior of internal nodes

+ l∈L T log 2 Treatment effect W + l∈L T log 2 + l∈L T (1 -W l ) log N l. + J -1 J -1 + l∈L T W l t log N l..t + J -1 J -1
Prior of leaf nodes

+ l∈L T (1 -W l ) log N l. ! N l.1. !N l.2. ! . . . N l.J. ! + l∈L T W l t log N l..t ! N l.1t !..N l.Jt ! Tree Likelihood (4.1)
The next section explains the different terms shows the proof of the criterion in.Eq. 4.1.

C(T) proof of Equation 4.1

We express the prior and the likelihood of a tree model, resp. P (T) and P (Data|T) according to the hierarchy of the uplift tree parameters. Assuming the independence between all the nodes, the prior probability of an uplift decision tree is thus defined as:

P (T) = P (K T ) Variable selection × s∈S T P (I s ) P (X s | K T ) P (N si. | K T , X s , N s. , I s )
Prior of internal nodes

× P ({W l }) Treatment effect W × l∈L T P (I l ) (1 -W l ) × p ({N l.j } | K T , N l. ) + W l × t P ({N l.jt } | K T , N l..t ) Prior of leaf nodes (4.2)
The first line is the prior probability of the variable selection, the second line the prior of internal nodes and the third line the prior of the leaf nodes.

Variable selection probability

A hierarchical prior is chosen: first the choice of the number of selected variables K T , then the choice of the subset K T among K variables. By using a uniform prior the number K T can have any value between 0 and K in an equiprobable manner. For the choice of the subset K T , we assume that every subset has the same probability. Then the prior of the variable selection can be defined as:

P (K T ) = 1 K + 1 1 K + K T -1 K T

Prior of internal nodes

Each node can either be an internal node or a leaf node with equal probability. This implies that:

P (I s ) = 1 2
The choice of the segmentation variable is equiprobable between 1 and K T . We obtain:

P (X s |K T ) = 1 K T
All splits of an internal node s to two intervals are equiprobable. We then obtain:

P (N si. | K T , X s , N s. , I s ) = 1 N s + 1

Prior of leaf nodes

Similar to the prior of internal nodes, each node can either be internal or a leaf node with equal probability leading to

P (I l ) = 1 2
For each leaf node, we assume that a treatment can have an effect or not, with equal probability, we get:

P ({W l }) = l 1 2
In the case of a leaf node l where there is not effect of the treatment (W l = 0), UB-DT describes one unique distribution of the class variable. Assuming that each of the class distributions is equiprobable, we end up also with a combinatorial problem:

P ({N l.j } | K T , N l. ) = 1 N l. + J -1 J -1
In a leaf node with an effect of the treatment (W i = 1), UB-DT describes two distributions of the outcome variable, with and without the treatment. Given a leaf l and a treatment t, we know the number of instances N l..t Assuming that each of the distributions of class values is equiprobable, we get:

P ({N l.jt } | K T , N l..t ) = 1 N l..t + J -1 J -1

Tree likelihood

After defining the tree's prior probability, we establish the likelihood probability of the data given the tree model. The class distributions depend only of the leaf nodes. For each multinomial distribution of the outcome variable (a single or two distinct distributions per leaf depending on whether the treatment has an effect or not), we assume that all possible observed data D l consistent with the multinomial model are equiprobable. Using multinomial terms, we end up with:

P (Data | T) = l∈L P (Data l |T) = l∈L (1 -W l ) × 1 N l. !/N l.1. !N l.2. ! . . . N l.J. ! + W l × t 1 (N l..t !/N i.1t !..N i.Jt !) (4.3)
By combining the prior and the likelihood (resp. Eq. 4.2 and 4.3) and by taking their negative log, we obtain C(T) and thus Eq. 4.1 is proved.

Search algorithm

The induction of an optimal uplift decision tree from a data set is NP-hard [START_REF] Ge Naumov | Np-completeness of problems of construction of optimal decision trees[END_REF]. Thus, learning the optimal decision tree requires exhaustive search and is limited to very small data sets. As a result, heuristic methods are required to build uplift decision trees. Algorithm 1 (see below) selects the best tree according to the global criterion. Algorithm 1 chooses a split among all possible splits in all terminal nodes only if it minimizes the global criterion of the tree. The algorithm continues as long as the global criterion is improved. Since a decision tree is a partitioning of the feature space, a prediction for a future instance is then the average uplift in its corresponding leaf. This algorithm is deterministic and thus it always leads to the same local optimum. In Section 4.3 we perform several experiments that show the quality of the trees that are built. The next section shows how to extend this algorithm to build random forests.

Algorithm 1: UB-DT algorithm input : T the root tree output: the tree T * which minimizes the proposed criterion T * ← T while C(T * ) decreases:

T ′ ← T * for leaf l in L T : for X in K: Get the best Split S X (l) according to UMODL T X ← T * + S X (l) if C(T X )<C(T ′ ): T ′ ← T X if C(T ′ )<C(T * ):
T * ← T ′ Prediction: The output of a tree is a partition of the feature space. The predicted uplift for each instance is the average uplift of its leaf node.

UB-RF

Random forests are an ensemble machine learning algorithm consisting of multiple decision trees. They were first proposed by [START_REF] Breiman | Random forests[END_REF], where the author showed their efficiency against other classifiers such as support vector machines. Random forests were shown to have better performance and lower variance. However, one problem is that they lack the interpretability provided by a single decision tree.

UB-DT can be easily extended to random forests. In this extension, a split is randomly selected from all possible splits that improve the global criterion. The number of individual trees included in the random forest is determined by the analyst, and the overall prediction of the forest is calculated as the mean of all individual tree predictions. Algorithm 2 provides a detailed description of the Random Forest algorithm, hereafter referred to as UB-RF. The grid pattern can be considered as a tree-friendly pattern whereas the continuous pattern is much more difficult. We generated several datasets according to these patterns with several different numbers of instances (also called data size) ranging from 100 to 100,000 instances. Uplift models were built using 10-fold stratified cross validation and the RMSE (Root Mean Squared Error) was used to evaluate the performance of the models.

Results: Fig. 4.3 gives the RMSE for the two synthetic patterns according to the data size for different uplift methods. We see that UB-DT is a good estimator for uplift. With UB-DT, RMSE decreases and converges to zero when data sizes increase both for the grid and continuous patterns. This is the expected behavior of a good uplift estimator. This also means that UB-DT, thanks to its global criterion, avoids overfitting of uplift trees. The two-model approach with decision trees also shows competitive performance. UB-DT clearly outperforms the other tree-based methods, these latter having similar performances. With the continuous pattern, KL-DT, Chi-DT, ED-DT and CTS-DT approaches have lower performances (their RMSE are around 0.5). To avoid a cluttered visualisation, their performances are not included in Fig. 4.3b. . Gerber [START_REF] Gerber | Social pressure and voter turnout: Evidence from a large-scale field experiment[END_REF]: a policy-relevant dataset used to study the effect of social pressure on voter turnout, 8. Right Heart Catheterization (RHC) [START_REF] Connors | The effectiveness of right heart catheterization in the initial care of critically ill patients. support investigators[END_REF]: a real dataset from the medical domain, the treatment indicates whether a patient received a RHC and the outcome is whether the patient died at any time up to 180 days after admission to the study.

UB-DT and UB-RF versus state of the art methods

Each dataset was used with different settings of treatment and outcome variables. For all datasets, each treatment and outcome variables are binary. Table 4.1 provides the most relevant specifications about the data sets.

Results 6 We evaluate the uplift models by using the qini coefficient metric [START_REF] Devriendt | Learning to rank for uplift modeling[END_REF]. Fig. 4.4a (resp. Fig. 4.4b) shows the overall average ranking of tree based methods (resp. meta-learners and forest-based methods) according to its qini coefficient performance against each dataset. Compared to other tree-based methods and to the two-model approach with decision trees, Fig. 4.4a shows that UB-DT achieves the best performance. Table 4.2 reports the results of the experiment for the qini coefficient. This table shows that UB-DT is also a good estimator of the uplift on real data. Fig. 4.4b shows that both UB-RF, X-Learner and 2M have the best rank. Table 4.3 indicates that the random forest strategy improves the performance of the uplift models (the values of the qini coefficients are higher with UB-RF than UB-DT). UB-RF has the best performance on 4 out of the 14 experiments. With no altering to the main conclusions, a comparative study between the uplift approaches with 10 and 50 trees is shown in Appendix A.1. UB-RF has the best average ranking when the number of trees is increased to 50.

Computation time

In this part, we compare the computation time of different uplift modeling algorithms. However, comparing the computation time of these uplift methods should be performed carefully, as it is strongly influenced by the quality of the implementation and the programming language used. For metalearners, it also depends on the complexity of the chosen supervised learning algorithm. We present in Table 4.4 the computation time for each uplift approach with respect to the first fold in each dataset. This allows us to get a general idea of the time consumption of the current implementation of our approach compared to the other state-of-the-art approaches, and to determine whether it is tractable and can still be used by the research community. Table 4.4 shows that causal forests are the fastest learning approach of all tested uplift modeling approaches. We also note that the tested version is implemented in the C programming language. Their computation times range from 1.4 seconds to 16.9 seconds. X-learner, R-learner, DR-learner and 2M come in second place, their computation times range from 7.6 seconds (for the 2M approach) to 33.2 seconds (for the DR-learner).

The uplift random forests (KL-RF, Chi-RF, ED-RF, CTS-RF, UB-RF) have the longest computation times. Especially UB-RF is computationally expensive. UB-RF is based on the UMODL discretization approach (see Chapter 3), for which the complexity is N log N . The search algorith of the UMODL discretization depends on the size of the data, the type of columns and the number of unique values in the columns. The UB-RF algorithm takes longer to find the optimal split for continuous variables. The more values a variable has, the longer the algorithm takes. For example, UB-RF takes the longest time on the criteo dataset, which contains 14 continuous variables, half of which have more than 1000 values. On the contrary, the gap between the time consumption of UB-RF and other forest-based approaches is the smallest on the Hillstrom and Starbucks datasets, which each contain a small number of continuous variables.

In addition, our implemented version of UB-RF is in Python and its implementation is sub-optimal. This observation leads to future works to optimize the algorithm and its implementation.

Conclusion

In this chapter, we have presented a new parameter-free method called UB-DT for uplift decision trees. We have designed a Bayesian approach to select the most probable uplift tree model T that maximizes the posterior probability P (T|Data). Contrary to state-of-art uplift decision tree approaches, UB-DT is characterized by a global criterion to build a tree, so the splits in one node depend on the splits in the other nodes. This approach avoids overfitting and the need for a pruning step. A search algorithm finds the tree that optimizes this criterion. We have shown that our approach is easily extended to random forests and we have defined UB-RF. Evaluations on real and synthetic data sets show that UB-DT is a good uplift estimator and our tree and forests methods perform competitively with state-of-art uplift modeling approaches including non tree methods.

Introduction

Uplift modeling algorithms assume that the treatment and control groups are drawn from the same distribution. While this strong assumption is potentially valid in experimental data and controlled trials, it often does not hold in realworld scenarios. The nature of real-world data is mainly observational, which means that it is collected without conducting a controlled experiment. Consequently, we cannot guarantee that the treatment and control groups have the same distribution. As outlined in Section 1.3, two distinct communities are attempting to address the problem of treatment effect estimation: the heterogeneous treatment effect estimation community, via the CATE estimation task, and the uplift modelling community. In the former, CATE estimation algorithms take into account non-random assignment bias (described in Section 2.5.1) and any difference between the distributions of the treatment and control groups. Examples of these algorithms include DR-Learner and X-Learner, as discussed in Section 2.2.1. Conversely, uplift modeling assumes equivalence of the two distributions. This is a strong assumption that rarely holds in real-world data, such as the telecom data.

In this chapter, we revisit the definition of the non-random assignment bias and we address the following research questions:

1. What is the impact of NRA bias on the main uplift modeling and CATE estimation approaches1 ?

2. Does our newly proposed Uplift Bayesian Decision Tree (UB-DT) algorithm perform well in the presence of NRA bias?

3. How can the bias effect be reduced?

To answer the first and second questions, we design an experimental protocol to evaluate the impact of NRA bias on state-of-the-art uplift methods. Our study allows us to identify several behavioural aspects of uplift methods. To address the third question, we define a reweighting method based on the inverse propensity weighting (IPW) approach to reduce the impact of NRA bias on the performance of the class transformation approach, which is found to be one of the methods most affected by NRA bias. Our experimental results show that this bias reduction method significantly improves the performance of the class transformation approach in the presence of NRA bias.

The remainder of this chapter is organized as follows. Section 5.2 describes the problem setting and our experimental protocol for evaluating the impact of NRA bias. We present our reweighting method in Section 5.3 then conclude in Section 5.4 This work is the object of the following publication: Rafla, M., Voisine, N., & Crémilleux, B. (2022, April). Evaluation of Uplift Models with Non-Random Assignment Bias. In Advances in Intelligent Data Analysis XX: 20th International Symposium on Intelligent Data Analysis, IDA 2022, Rennes, France, April 20-22, 2022, Proceedings (pp. 251-263). Cham: Springer International Publishing.

Evaluation of uplift with biased data

This section presents the NRA bias and the experimental protocol that we designed to assess performance of uplift methods under this bias.

Problem setting

Some state-of-art uplift methods assume that data are unbiased and that the treatment group comes from the same distribution as the control group, which is not true for real data. In practice, there are often differences between treatment and control groups, also known as Non-Random Assignment bias, a prevalent type of bias in uplift modeling [START_REF] Zhang | A unified survey of treatment effect heterogeneity modelling and uplift modelling[END_REF]. Formally, this bias occurs when P (T = 1|X) ̸ = P (T = 0|X) (which also means P (X|T = 1) ̸ = P (X|T = 0)). Usually it is easier to collect control data and the treatment group is the most biased because it is more challenging to apply a treatment to individuals and collect the corresponding data due to ethical, political or economic constraints.

This bias problem has been studied in the literature on clinical studies where the goal is to estimate the "Average Treatment Effect" (ATE) defined as E[Y i (T = 1) -Y i (T = 0)]. In order to estimate it, the "Propensity Score Matching" (PSM) [START_REF] Rubin | Using propensity scores to help design observational studies: Application to the tobacco litigation[END_REF] is used to extract balanced treatment groups on which ATE is estimated. Similarly, in the uplift literature, since uplift methods assume the homogeneity between treatment groups, PSM is used to extract an unbiased sample from a biased dataset. Uplift modeling is applied subsequently as carried in [START_REF] Olaya | A survey and benchmarking study of multitreatment uplift modeling[END_REF]. However, this procedure clearly suffers from a loss of data.

Designing of the experimental protocol

This section describes the experimental protocol that we designed to evaluate the behavior of uplift methods under the NRA bias. The principle, to create a NRA bias and observe its impact, is to introduce imbalances in the data regarding the initial distribution of the variables. We do this by modifying proportions of individuals in a non-random way (for example, decreasing the proportion of specific socio-professional categories or ages till it disappears in the data). Such a protocol must satisfy several conditions to correctly evaluate the impact of NRA in order to avoid introducing a bias due to the protocol itself.

• The chosen variables to introduce bias have to be correlated with the outcome Y or Y given the treatment T , otherwise the bias will not affect the uplift modeling.

• In contrast, the choice of the values of the variables, according to which the proportions of individuals vary, is random. If not, the construction of the populations E1 and E2 (which will be explained below) may be biased.

• The bias must be tunable in order to change its rate and quantify its impact on the uplift methods.

• The created bias is only in the treatment group in order to imitate the natural phenomena as previously explained in Section 5.2.1.

• The total size of each of the biased learning samples is always the same in order to avoid any variation in the performance due to different learning data sizes.

More precisely, as shown in Fig. 5.1, two populations E1 and E2 are created. This is done by choosing a set of variables V and dividing its values into two groups, C1 and C2, such that the number of individuals defined by the values of C1 is equivalent to the number of individuals defined by C2. Let E1 (resp. E2) be the population whose variables correspond to C1 (resp. C2) and whose sizes are N 1 and N 2 respectively. We use a 10-fold cross-validation. In the first training sample, E1 and E2 have an equal size (i.e. N 1 = N 2), it is considered unbiased and gives a reference value of the qini coefficient. The NRA bias is gradually introduced in the treatment group by increasing the size of E1 and decreasing the size of E2 while preserving the total size of the treatment group. We identify the bias rate of a sample by the variable b where b = (N 1 -N 2) × 100/N . b goes from b = 0 in the unbiased situation to b = 100 the most biased situation according to the NRA bias. An uplift model is then learned on each biased sample defined by b. All models are then tested on the same test sample and evaluated using the qini coefficient. The evolution of the qini coefficient according to b allows studying the behavior of an uplift method towards the NRA bias.

Experiments

In this section, we introduce the datasets, the uplift modelling approaches and the details of the experiments.

Datasets

We use several real and synthetic datasets from different fields that are widely used in the literature. All these datasets have been previously described in Section 3.5.3 and in Section 4.3.2. Below is a brief description of the datasets used:

1. Criteo [START_REF] Diemert | A Large Scale Benchmark for Uplift Modeling[END_REF]: a usual marketing dataset for uplift modeling.

2. Hillstrom2 : another classical marketing dataset for uplift modeling.

3. Gerber [START_REF] Gerber | Social pressure and voter turnout: Evidence from a large-scale field experiment[END_REF]: a policy-relevant dataset. 5. Megafon4 : a synthetic dataset created by telecom companies for uplift modeling.

6. Zenodo5 : a synthetic dataset containing trigonometric patterns specifically designed for uplift modeling. This dataset consists of 100 trials of different patterns. We only used the first trial of the dataset.

7. Continuous and Grid patterns: two synthetic datasets, each consisting of two variables.

8. Information: a marketing dataset. 9. Starbucks: an advertising promotion dataset.

10. Bank: a marketing campaign conducted by a bank.

Uplift methods

We test 18 uplift methods: two-model approach (2M); classtransformation approach (CT), each with Xgboost and logistic regression (LR); DR-learner (DR); X-learner, R-learner and S-learner, each with Xgboost and linear regression (LinR). Direct-approaches based on random forests (RF) and decision trees (DT) are tested as well: KL, ED [START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF] and CTS [START_REF] Zhao | Uplift modeling with multiple treatments and general response types[END_REF].

Implementation details For each dataset (except Synth1 and Synth2) and for each uplift method, the experimental protocol is run twice with different compositions of the set of variables V on which the bias is created: once including the most important variable within the dataset and once with the second most important variable (The use of a non-informative or random variable in the bias generation process won't yield a difference between the treatment and control groups). For Synth1 and Synth2, V contains the two variables of these datasets. Moreover, given a set V , the experiment is repeated twice in order to provide different splittings of C1 and C2.

Results

Qini coefficients variability according to b

Fig. 5.2 illustrates a subset of the results. We observe that the NRA bias strongly affects the performance of uplift models (the higher the bias rate, the more significant the decrease of the qini coefficient).

To provide a global view of the results, we compute for each dataset and each uplift method the average qini coefficient, i.e., the average of qini coefficients according to the bias rates going from b = 0 to b = 100. We show the result of the average qini for all datasets in Table 5.1 and Table 5.2. Each dataset name is followed by the variable V used to introduce the bias. We have tested different splits of V in C1 and C2. These variations are indicated by an apostrophe after the variable name in both Table 5.1 and Table 5.2.

Overall ranking

To better compare the methods according to their resistance to NRA bias, Fig. 5.3 shows the average rank obtained by each method based on the average qini coefficient (all divisions of V are taken into account).

The results of our experiments show the following conclusions:

• The models with the highest resistance to the NRA bias are mainly the meta-learners: the X-learner, the R-learner, the DR-learner and our newly The figure title consists of the dataset name followed by the variable used to generate the bias. In the legend, a method name is followed by the associated learning algorithm. proposed UB-RF method. The qini coefficient generally decreases only when the bias rate is increased. Table 5.3 shows the reference qini and the average qini coefficients for each of these methods. The reference qini coefficient (denoted Ref.qini) is the qini coefficient when b = 0

• While traditional tree-based methods show limited effectiveness, their random forest counterparts show improved performance, especially the ED-RF model.

• In contrast to other tree-based techniques, our UB-DT model shows competitive performance compared to meta-learners and the UB-RF method. Although it does not perform better -which is an expected behaviour for a simple decision tree -the effectiveness of the UB-DT model is remarkable.

In fact, it even has a higher average rank than state-of-the-art random forest algorithms.

• The class-transformation approach is particularly sensitive to the bias introduced, as its qini coefficient performance deteriorates significantly even in the presence of minimal bias.

Methods comparison with statistical tests

We study now the significance of the results regarding the comparison of the uplift methods (cf. Table 5.2) by using a statistical test. Following the study [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF],

we choose the Friedman test with the post hoc test of Nemenyi to compare the performance (average qini coefficient) of more than two methods across several datasets. Fig. 5.4 depicts the results with a heatmap. The null hypothesis states that there is no significant difference in performance according to the average qini coefficients between two methods across the datasets. With a value of p (pvalue) smaller than 0.05, the null hypothesis is rejected (in green in Fig. 5.4). Figures 5.4 and 5.3 confirm our previous conclusions. They show that the classtransformation and tree-based approaches are the least resistant to NRA bias, and their performance differs significantly from the most resistant methods. The methods that show the most resistance to NRA bias include our method UB-RF, the R-learner, X-learner and DR-learner. Notably, there are no significant differences between these top performers in terms of their resistance to NRA bias.

Method to reduce the NRA bias impact

Method Description

In the previous section, our experimental protocol showed that the class-transformation approach is highly sensitive to the NRA bias. In this section, we examine the impact of reweighting individuals using propensity scores on the resilience of the class transformation approach to the NRA bias. Propensity scores represent the probability of an individual receiving a treatment (T = 1) based on their vector of observed variables X i , i.e. P (T = 1|X i ). This strategy is inspired by the literature on domain adaptation, where samples from a source dataset are weighted according to their relevance to a target dataset [START_REF] Wouter | An introduction to domain adaptation and transfer learning[END_REF].

The principle of the method is to weight individuals in the treatment group based on their corresponding weights in the control group, thereby making the biased population (treatment group) more similar to the unbiased population (control group). In observational studies, the propensity scores are not directly known, but can be estimated from the data using a regression algorithm. This method weights each individual i of the treatment group by w(X i ) s.t.:

w(X i ) = P (T = 0|X i )/P (T = 1|X i ) (5.1)
We estimate the probabilities of Eq. 5.1 by using logistic regression and xgboost. Then the uplift method integrates the weights to amplify the role of the under-represented individuals in the treatment group and estimate τi . We named wt-1 (resp. wt-2) the use of the logistic regression (resp. xgboost) in the weighting method.

We evaluate our weighting method with the class-transformation approaches since they are the most affected approaches by the NRA bias according to our experiments and they use traditional machine learning algorithms where weights can be given directly at each line (individual).

Results

Results show a large enhancement in the performance with the class-transformation methods (cf. Fig. 5.5). Table 5.4 details the results with the class-transformation based methods. The same as before, "Ref.qini" denotes the reference qini, that is the qini value of a method without bias (i.e. b = 0) and without weighting. The Mean Absolute Error (MAE), given by the formula M AE = 1 n n j=1 |Ref.qini j -Averageqini j |, indicates the difference between the qini obtained by an uplift method and the reference qini. Here n is the total number of experiments performed. The smaller the gap is, the better the weighting.

With the reweighting method, the gap is much smaller especially when the class transformation is combined with the logistic regression (LR). The best average qini values are also obtained with weighting, except for the Zenodo, Bank and Gerber datasets. It is also worth noting that on the Bank and Gerber datasets, the class transformation approach shows poor performance (as indicated by the negative Ref.qini values) even when no bias is introduced (b = 0). In these cases, the reweighting method does not improve much or at all the class transformation approach, specially when the dataset is already hard to learn an uplift model.

Conclusion

In this chapter we define the non-random assignment bias (NRA) in the context of uplift modeling. NRA bias occurs when samples are not equally distributed between the treatment and control groups, i.e. when P (T = 1) ̸ = P (T = 0). This bias is often observed in real world data. To explore the impact of NRA bias, we have designed an experimental protocol that simulates it in a dataset. The goal of the protocol is to generate NRA bias and study its effects on state-of-the-art uplift methods, as well as our newly proposed decision tree and random forest approaches, UB-DT and UB-RF.

Our experiments revealed different behaviours between the uplift methods. Our novel random forest approach, UB-RF, showed resilience to NRA bias. Several meta-learners, such as the X-learner, R-learner and DR-learner, also maintained strong performance when confronted with NRA bias. Also, our proposed decision tree method UB-DT, showed to have a good performance compared to the state-of-the art decision tree and random forest approaches. In contrast, the class transformation approach proved to be the least resilient to NRA bias. In the final section of this chapter, we propose to reweight the data using the inverse of the propensity scores when using the class transformation approach. This reweighting technique significantly improves the performance of the class transformation method in the presence of NRA bias.

Introduction

Telecommunications data refers to the vast amount of information generated and collected by telecommunications companies through their network infrastructure, customer interactions, and billing systems. As discussed in Section 2.4, this data includes various dimensions, customer demographics, usage patterns, call records, service subscriptions, customer interactions, and billing information. Leveraging this wealth of telecom data can provide valuable insights into customer behavior and churn prediction, enabling telecom companies to proactively manage customer retention strategies.

That is why data scientists and decision makers are trying to get the most out of telecom data by pre-processing it and learning uplift models to predict uplift scores for each of their future customers. Learning uplift models may seem simple when using state-of-the-art uplift algorithms, but it is often very challenging because of the parameters that should be defined by the user. The main drawback of all the uplift approaches is that they require parameterization. Meta learners also have an additional requirement, which is the choice of the machine learning algorithm to be used. All this is a clear limitation for non-machine learning experts to use these tools. Even for machine learning experts, they need to test different parameter values and different learning algorithms with meta learners to find the optimal combination that fits the data at hand. Therefore, the parameter-free approaches proposed in this thesis are very much needed, especially in industrial contexts.

In this chapter, we first show how uplift modeling can be performed to deal with telecom data. Then we evaluate state-of-the-art uplift approaches for model learning and feature selection and compare them to our proposed approaches.

Uplift methodology

This work is the object of the following publication: Rafla, M., Voisine, N., & Crémilleux, B. (2023, September)

Uplift methodology

In this section we provide important steps to follow when applying uplift modeling on telecom data:

• Outcome Definition. The outcome variable needs to be defined based on the marketing goal. For example, it could be whether a customer made a purchase or renewed their subscription within a specific time period after receiving the treatment. This outcome will be used to measure the uplift.

• Treatment Assignment. A group of customers needs to be exposed to a marketing treatment, while another group serves as a control group that does not receive the treatment. The treatment can be a specific marketing campaign, promotional offer, or any other intervention. Uplift is then modeled from the data of 2 groups.

• Data Preparation. The telecom data needs to be preprocessed and prepared for uplift modeling. This includes cleaning the data, handling missing values, and transforming variables into a suitable format. Data bias should also be addressed either at this step using propensity score matching or in the next step of model learning.

• Uplift model learning. The model predicts the uplift score, which represents the difference in the probability of a positive outcome between the treatment and control groups.

• Model Evaluation. The uplift model needs to be evaluated using appropriate metrics. These metrics help assess the model's performance in identifying customers who are most likely to respond positively to the marketing treatment.

• Targeting and Decision Making. Once the uplift model is built and evaluated, it can be used to target customers for the marketing intervention. The model can identify customers who have a high likelihood of being positively influenced by the treatment. These customers can then be prioritized for the marketing campaign, maximizing the impact and return on investment.

• Iterative Refinement. Uplift modeling is an iterative process. The model's performance should be continuously monitored and refined based on the observed outcomes. This helps improve the targeting strategy and optimize the uplift achieved from the marketing interventions.

An experimental study on telecom data

In this section, we conduct different experiments to evaluate our Bayesian approaches on real data, specifically derived from Orange marketing campaigns conducted in 2013 (data specifications are shown in Table 6.1). The original Orange dataset contains 2700 variables. However, for the purpose of efficient computation, we have selected a subset of this dataset using Khiops software1 , keeping only 101 variables. We also added 50 noise variables to this dataset to better evaluate the feature selection approaches. First, we compare our uplift Bayesian decision trees and random forests versus the state-of-art uplift modeling algorithms. We then evaluate the impact of UMODL discretization and feature selection as preprocessing steps on these state-of-the-art uplift modeling algorithms.

UB-DT and UB-RF

In this part, we conduct a study to evaluate the performance of the UB-DT and UB-RF algorithms on our dataset. We also compare their performance with the state-of-art uplift modeling algorithms. More particularly, we evaluate the following algorithms: 1. X-learner 2. R-learner 3. DR-learner 4. Two model approach 5. Random forest algorithm based on the ED criterion 6. UB-RF 7. UB-DT Each of the X-learner, R-learner, DR-learner and the Two model approach was used with a random forest algorithm and a logistic regression as base models. All random forests are learnt using 10 trees. Each model is learnt using a 10-fold cross validation. We use the qini metric [START_REF] Devriendt | Learning to rank for uplift modeling[END_REF][START_REF] Radcliffe | Using control groups to target on predicted lift: Building and assessing uplift model[END_REF] to evaluate the uplift models. Results Figure 6.1 shows the qini curves [START_REF] Devriendt | Learning to rank for uplift modeling[END_REF] for each model, aggregating data from all test folds. The corresponding qini values are given in Table 6.2. Looking at the results, we see that UB-RF (shown in pale pink color) outperforms all other uplift modeling algorithms. Even a single decision tree with the UB-DT approach shows remarkable efficiency and competes well with other methods.

Variable transformation

This section demonstrates the impact of employing a variable transformation with the UMODL discretization as an initial preprocessing step. When the UMODL discretization is applied to a non-informative variable, the result is a single interval, i.e. the transformed variable follows a uniform distribution for all examples. In such cases, UMODL discretization discards this variable. Consequently, the process of transforming variables can be seen as inherently involving a feature selection step.

We carry out our experiments in three stages: the first with the original variables, the second with only a feature selection step, and the third with the variable transformation incorporated as a preprocessing step. As just mentioned, it should be noted that this third stage is considered to combine both feature selection and transformation. Again the model is built using a 10-fold cross-validation approach.

Results Table 6.3 presents the performance of uplift modeling algorithms under the three scenarios given above: 1. without any preprocessing step (i.e. original variables) 2. with UMODL-FS as a preprocessing step 3. with variable transformation as a preprocessing step. The results indicate that feature selection significantly improves the performance of all uplift modeling algorithms compared to the original dataset (without any preprocessing). Applying variable transformation yields similar improvements for all uplift modeling algorithms, with the exception of ED-RF. When comparing the impact of feature selection and variable transformation, the benefits appear to depend on the uplift approach used. For example, when logistic regression is used as the base learner, variable transformation appears to offer better improvements. In the contrary, when random forests are used as the base learner, feature selection shows to perform better. By performing feature selection and variable transformation, the state-of-the-art uplift models achieved the best results, close to those obtained with UB-RF (see Table 6

Feature Selection

We evaluate the following feature selection methods: KL, LR filter, F filter and UMODL-FS. Each feature selection method gives a score to each variable in the data. The principle of the experiment is to feed the top-k features selected by each of the feature selection method into an uplift modeling algorithm and then observe the performance of the model. We use an incremental approach, first introducing only the top-1 feature. We then incrementally add an additional set of fifteen features at each step, continuing this iterative process until all features Results Figure 6.2 shows the performance obtained with the two model approach and X-learner respectively. Each of these two models are used with a random forest of 10 trees. UMODL-FS shows a good performance selecting the top features leading to performant uplift models. In addition, UMODL-FS automatically determines the features to eliminate without user intervention. In contrast, the other feature selection methods cannot automatically determine an appropriate cut-off score for a feature to be discarded or considered.

Kuplift Library

This section gives a brief introduction to Kuplift2 and how to use it. Kuplift is a Python library that implements our parameter-free Bayesian methods. It implements uplift Bayesian decision trees, random forests, discretization and feature selection. It provides a standard interface (like scikit-learn [START_REF] Kramer | Scikit-learn. Machine learning for evolution strategies[END_REF] and causalml [START_REF] Chen | Causalml: Python package for causal machine learning[END_REF]).

UB-DT and UB-RF

Conclusion

In this chapter, we first discussed in Section 6.2 important steps required to perform uplift modeling on telecommunications data. These steps include defining the outcome, assigning the treatment, preparing the data, learning the uplift model, and finally evaluating the model. We highlight that the uplift modeling process is iterative and requires ongoing monitoring and refinement to achieve the greatest possible benefit from a marketing campaign.

Then in Section 6.3, we conducted a series of experiments using real telecom data from the French company Orange. First, we compared our proposed uplift modeling methods, UB-DT and UB-RF, with state-of-the-art approaches. The results show the efficiency of our methods. We then implemented variable transformation and feature selection as preprocessing steps for the traditional approaches to improve their performance. We explained how variable transformation inherently involves feature selection. Based on our experimental results, these two preprocessing steps significantly improved the effectiveness of the uplift algorithms.

We observed that variable transformation was particularly useful when the base learner was a logistic regression model. However, feature selection showed higher efficiency when the base learner was a random forest algorithm. In our final experiment, we highlighted the advantages of a parameter-free feature selection approach. This method automatically identifies the cutoff number of informative features in the data, eliminating the need for users to manually set this parameter.

Our conclusion suggests that it is advantageous to use parameter-free approaches when developing an uplift model. These techniques eliminate the need to select a specific base learner, set parameters for a specific algorithm, perform extensive preprocessing, or determine a cutoff number of features for a feature selection approach. This strategy simplifies the modeling process and reduces the potential for error.

Finally, in Section 6.4, we introduced Kuplift, our Python package which implements all the algorithms mentioned in this thesis.

CHAPTER 7

Conclusions and Perspectives

Conclusion

This thesis contributes to the field of uplift modeling. It was conducted in collaboration with the French telecommunications company Orange. In particular, this thesis addresses three main challenges:

1. The parameterization problem for existing uplift modeling algorithms.

2. Data bias in uplift modeling.

The high dimensionality problem in uplift modeling.

We address these challenges by first proposing in Chapter 3 the UMODL approach. UMODL aims to identify the model that is most likely given the data. This means finding the model that maximizes the posterior probability P (M |D). By applying Bayes' theorem, we find that maximizing the posterior probability is similar to maximizing the product of the prior probability and the likelihood. Thus, UMODL specifies a space of models and a prior distribution. From this model space, a Bayesian optimal evaluation criterion is defined, which is determined by taking the negative logarithm of the stated posterior probability. A search algorithm is then used to find the model with the optimal criterion. This approach is completely user parameter free and can be applied to a variety of model types.

For an uplift discretization model (see Section 3.2.1), the prior distribution is defined by the number of intervals, the bounds of those intervals, the presence or absence of a treatment effect in each interval, and the class frequencies per treatment in each interval (or per interval). The prior distribution is defined by assuming the independence of the distributions across intervals and by assuming a uniform distribution for each parameter. We have shown that the UMODL discretization, being a density estimation approach, is a good univariate uplift estimator. Finding a set of intervals with different treatment effects is equivalent to estimating the treatment effect for each instance in those intervals. We have conducted an experimental protocol to assess UMODL as an uplift estimator through discretization. We have defined different synthetic uplift patterns and generated accordingly several datasets with several data sizes. The use of synthetic data gave us the advantage to know the true uplift value and thus be able to compare the estimated uplift value by our approach and the true one. By observing the RMSE of the predicted uplift values and the number of found intervals by data size, we were able to infer the following characteristics: 1. UMODL is a good uplift estimator through discretization. 2. UMODL does not overfit 3. It needs sufficient number of instances to give prominence to a model with more intervals We proceeded to show the application of the UMODL discretization technique to categorical variables. Essentially, the discretization attempts to create a set of intervals that can partition a continuous variable into distinct categories while preserving the maximum amount of information from the original continuous attribute. One obvious method for applying the UMODL discretization strategy to a categorical variable is to transform the categorical values into numerical values using traditional label encoding. In the same chapter, Section 3.4, we explain why traditional label encoding is inadequate, and then propose a supervised uplift-based label encoding. The proposed encoding ranks the categorical values of a variable according to their respective uplift values. This technique efficiently groups instances with similar uplift values, as explained in Section 3.4.2.

In the last part of Chapter 3, we introduced UMODL-FS, a feature selection method that was shown experimentally to be efficient at eliminating noise variables and to find the set of variables that lead to uplift models with the best qini. The UMODL-FS approach computes a divergence measure between the treatment and control distributions for each interval found in a variable. The sum of the divergences over the intervals becomes the score of the variable. Additionally to selecting the most informative set of features, UMODL-FS allows us to continue selecting top features, as long as it gives them an importance score greater than zero. Once a score of zero is reached, no additional features are selected, thus establishing a threshold for feature selection. However, determining an appropriate cut-off score for feature selection cannot be done for other state-of-the art feature selection approaches. We conducted an experimental protocol on real and synthetic datasets, where the idea was to gradually add noisy features and build several uplift models, each with a different feature selection method as a preprocessing step. Experiments show that UMODL-FS removes irrelevant features and clearly outperforms state of the art methods by providing uplift models with the highest and most stable qini.

Following the same Bayesian approach, in Chapter 4 we propose a new userparameter-free uplift Bayesian decision tree approach, which we call UB-DT. Unlike conventional decision tree learning approaches, we transform the uplift decision tree learning problem into an optimization problem, where the goal is to find the uplift tree that is most likely given the data. UB-DT consists of two components: a global evaluation criterion for a binary uplift decision tree and a search algorithm to find the optimal tree. A global evaluation criterion evaluates an entire tree model, taking into account all splits in the tree at once. Following the same logic, we have defined the parameters and the evaluation criterion for an uplift decision tree. We have defined the uplift tree model by:

• its structure (a set of internal and leaf nodes),

• the distribution of instances in internal nodes. This is described by the segmentation variable for each node and the way the instances are divided into two child nodes,

• the distribution of instances in leaf nodes. Here, each leaf node could either have a treatment effect, which is described by the distribution of instances per treatment, or it could have no treatment effect, in which case it's represented by the distribution of instances.

These parameters were formally defined as well as their hierarchy, which describes the dependencies between the parameters. The hierarchy of the uplift tree model is described from the root node to its children and recursively to the leaves. We also assume independence of the distribution of outcome values between child nodes and a uniform distribution for each parameter. Again, the global evaluation criterion is defined as the negative logarithm of the posterior probability of an uplift tree model given the data. A search algorithm is then used to find the optimal tree model. The extension of the uplift decision tree search algorithm to random forests is also presented in Section 4.2.5. We evaluated UB-DT versus state-the-art tree-based approaches on 2 synthetic patterns. We generated several datasets according to these patterns with several different numbers of instances ranging from 100 to 100,000 instances. For each dataset, models are learnt using 10-fold cross validation and evaluated using the RMSE. With UB-DT, RMSE decreases and converges to zero when the data size increases for both synthetic patterns. Subsequently, we evaluated UB-DT and UB-RF against state-of-theart uplift algorithms on real and synthetic datasets widely used in the uplift modeling community. The results show that our proposed approaches remain competitive when compared to existing state-of-the-art algorithms.

In Chapter 5, we address the problem of data bias. More particularly, we define the non-random assignment bias (NRA) in the context of uplift modeling. The NRA bias occurs when the treatment and control groups do not have the same distributions of the samples. We designed an experimental protocol to simulate the NRA bias in uplift datasets. The goal of the protocol was to generate the NRA bias in the data and study its effects on state-of-the-art uplift methods, as well as our proposed decision tree and random forest approaches, UB-DT and UB-RF. The results of our experiments showed that the models with the highest resistance to the NRA bias are mainly the meta-learners and our newly proposed UB-RF method. Our UB-DT approach, although being a single tree, showed competitive performance versus the NRA bias. Another conclusion was that the class-transformation approach is particularly sensitive to the NRA bias. In the second contribution of this chapter, we proposed to use a reweighting method based on the propensity scores to weight individuals in the treatment group based on their corresponding weights in the control group, thereby making the biased population more similar to the unbiased population. We tested this approach with the class transformation approach, that was greatly improved with the reweighting method.

In Chapter 6 we performed additional evaluations of our proposed approaches on real telecom data. We first illustrate the steps involved in an uplift modeling process as practiced in telecom companies. Following this, we run a series of experiments to compare UB-DT and UB-RF approaches against state-of-theart methods using real telecom data provided by the French company Orange. We highlighted the importance of parameter-free approaches to liberate us from choosing parameters and/or base learners for meta-learners. We then investigated the effects of preprocessing uplift data via feature selection (using UMODL-FS) and/or variable transformation (using UMODL discretization) on the resultant uplift models. Our analysis showed that when logistic regression is used as the base learner, variable transformation is significantly more beneficial than feature selection. Conversely, when random forests are used as the base learner for metalearners, feature selection becomes the more favorable option. In all our experiments (except the tests with ED-RF approach), preprocessing the data with feature selection or variable transformation was found to lead to better uplift models than only using the original data without preprocessing.

Future directions

In this section we give several perspectives for this thesis. We begin by presenting two axes of perspectives: one that focuses on future directions for our Bayesian uplift approach, and the second on exploring perspectives for uplift modeling. Fig. 7.1 shows a visual illustration of these two axes. Finally, we present a third axis about exploring data bias in the context of uplift modeling.

Extension of our Bayesian approach

Several extensions to our Bayesian approach can be proposed. First, the proposed criterions for UMODL and UB-DT were designed for continuous attributes. For categorical variables, in Section 3.4 we proposed an uplift-based encoding for categorical data. We used this encoding to efficiently convert categorical variables into numerical variables and thus apply the UMODL approach.

However, a new UMODL criterion for categorical variables could be designed. Given a categorical variable, this criterion would aim to group together values that exhibit similar behavior, i.e., have the same uplift density. The MODL approach for categorical variables [START_REF] Boullé | A Bayes optimal approach for partitioning the values of categorical attributes[END_REF] could be considered as a first reference. This new criterion can also be used for uplift feature selection to give more reliable importance scores for categorical variables.

Subsequently, the UMODL criterion for continuous variables that we presented in Chapter 3 could be integrated with the UMODL criterion for categorical variables to extend the uplift decision tree approach. Thus, a new UB-DT criterion could be proposed that makes appropriate splits for both continuous and categorical variables.

Concerning our proposed uplift decision tree approach, we emphasize that improving the search algorithm design and implementation is crucial to make the developed algorithms more tractable. In addition, our proposed uplift decision tree search algorithm can be improved by using a post-optimization algorithm to prevent our search algorithm from falling into local minima [START_REF] Voisine | A bayes evaluation criterion for decision trees[END_REF].

We also note that for simplicity, our proposed UB-DT criterion and search algorithm were designed for binary trees. An extended criterion to General Trees, where each node can have many children, can be defined. This will give the UB-DT approach the freedom to do binary splitting and/or multiple splittings depending on the value of its criterion. This may allow uplift Bayesian decision trees to model more complex patterns.

Finally, the Bayesian approach we present in this thesis is a general approach that can also be applied to a variety of models such as Selective Naive Bayes [START_REF] Boullé | Compression-based averaging of selective naive Bayes classifiers[END_REF], k-nearest-neightbours [START_REF] Ferrandiz | Bayesian instance selection for the nearest neighbor rule[END_REF]. The difference for each type of model is how we de-Figure 7.1: Future directions termine the prior distribution and the model space. As discussed in Chapter 3 and Chapter 4, in general, a prior distribution is determined by exploiting the hierarchical structure of its parameters (each model type has its own set of parameters). This hierarchy indicates the dependencies between parameters and implies that the parameters must be chosen in a certain order when defining the prior distribution.

Future directions for the uplift modeling problem

So far, our Bayesian approach, as well as most of the literature on uplift modeling, has been designed for the case of binary treatment and binary outcome. However, there are applications with multiple treatments, such as when we try to find the optimal marketing campaign among several types of campaigns. Examples of multiple treatments in marketing include choosing the optimal treatment for each customer such as offering a discount on a customer's monthly bill or offering extra data for free or offering free access to a premium service. To our knowledge, the problem of multiple treatments has not been studied much in the literature. Some studies include tree-based approaches for multiple treatments [START_REF] Olaya | A survey and benchmarking study of multitreatment uplift modeling[END_REF][START_REF] Rzepakowski | Decision trees for uplift modeling with single and multiple treatments[END_REF][START_REF] Marco | Interpretable multiple treatment revenue uplift modeling[END_REF].Our Bayesian criterion for discretization and uplift decision trees can also be extended to the case of multiple treatments.

In addition, the continuous treatment problem is very interesting and very needed in various domains such as medical and marketing domains. Examples of continuous treatments are the drug dosage to be given to a patient in the medical field and the length of SMS sent in the marketing field. Modeling continuous variables using the MODL approach was studied in [START_REF] Hue | A new probabilistic approach in rank regression with optimal bayesian partitioning[END_REF] and can be used as a basis of a new uplift criterion for continous treatments and outcomes.

Another type of an uplift modeling problem is the estimation of individual uplift based on sequence data [START_REF] Egho | A user parameterfree approach for mining robust sequential classification rules[END_REF]. Essentially, this involves determining the uplift for each individual, taking into account a sequence of their behaviors. An example of sequence data: a customer initially accepted an Internet offer, then upgraded to a premium package, and then subscribed to a movie platform.

Data bias in uplift modeling

A third axis of perspective is data bias. In this thesis, we have studied a particular type of bias called the non-random assignment bias. In Section 2.5, we have also introduced other types of bias, such as the non-response bias and the deployment bias. These types of biases can be studied in the future. Experimental protocols can be designed to simulate them in the datasets, similar to what we did in Chapter 5. As an example, one potential experimental protocol could be to simulate the deployment bias within the data and then examine its effect on the uplift modeling approaches. This could be accomplished by designing experiments in which we first apply the uplift approach to training data and then test it on data from an identical distribution. Gradually, we would introduce variation into the test data, moving it away from the distribution of the training set. In this way, we can observe the ability of different uplift methods to maintain their generalization and the degree to which they can resist these changes.

A.1 Experimental results with 50 trees

In Chapter 4, we conduct an experimental protocol to compare the performance of the UB-RF approach with state-of-the-art uplift modeling approaches on several datasets. For all approaches, we use 10 trees to construct the uplift models. In this appendix, we present supplementary results in which each of the algorithms is built using 50 trees. The corresponding average qini values are shown in Table A

Figure 2 . 1 :

 21 Figure 2.1: The structure of this chapter is around three topics: Uplift modeling, Data bias and a Bayesian approach called MODL

D

  gain (A) = D (P (Y |T = 1) : P (Y |T = 0) | A) -D (P (Y |T = 1) : P (Y |T = 0))

Figure 2 . 2 :

 22 Figure 2.2: Results of a good uplift model (left) and a bad uplift model (right) represented by an uplift-per-decile chart.

Figure 2 . 3 :

 23 Figure 2.3: Example of qini curves. X-axis shows the percentage of targeted individuals k, sorted by their predicted uplift values. Y-axis present the percentage of the cumulative uplift.

Figure 2 . 4 :

 24 Figure 2.4: Parameters of a MODL decision tree

Figure 3 . 1 :

 31 Figure 3.1: On the left figure, a variable X along with the output distributions. On the right figure, the optimal discretization

•

  X : explanatory variable to discretize • Y : binary outcome variable • N : number of instances in the dataset • J : number of classes of Y • I : number of intervals • N i : number of instances in the interval i • N it. : number of instances in the interval i of treatment t • N i.j : number of instances in the interval i of class j • N itj : number of instances in the interval i of class j and the treatment t • W i : boolean term indicating if the treatment has an effect in interval i

Figure 3 . 2 :

 32 Figure 3.2: Parameters of an uplift discretization model. The presence of a treatment effect (W i = 1) in interval i requires describing the distribution of the outcome variable Y separately for each treatment (part right). In contrast, the absence of a treatment effect (W i = 0) indicates to consider the distribution of the outcome variable Y for the interval i independently of the treatment variable (part left).

Figure 3 . 3 :

 33 Figure 3.3: Synthetic uplift patterns. The X-axis represents variable X and the Yaxis represents P (Y = 1). For Crenel Pattern 1 and Crenel Pattern 2, five versions are generated with different values of θ ∈ {0.6, 0.7, 0.8, 0.9, 1}. The difference between P (Y = 1) in the treatment and control groups represents the uplift.

Fig. 3 .

 3 3c) is a particular bin-based pattern with trigonometric shape where: P (Y = 1|T = 1) = 0.5 + (0.5 × sin(i × 2π 10 )) and P (Y = 1|T = 0) = 0.5 + (0.5 × cos(i × 2π 10 )) • Scissors pattern (cf. Fig. 3.3d) is a bin-based pattern where P (Y = 1|T = 1) = i 10 and P (Y = 1|T = 0) = 1 -i 10 , where i is the interval number. • Continuous pattern (cf. Fig. 3.3e) differs from bin-based patterns. Here P (Y = 1|T = 1) = X/10 P (Y = 1|T = 0) = 0.5.

Figure 3 . 4 :

 34 Figure 3.4: Results obtained for Crenel pattern 1 (cf. Fig. 3.3a). The left (resp. right) figure shows the mean number of found intervals (resp. the mean value of RMSE) on the test set by UMODL according to the dataset size. Different curve colors correspond to different treatment effects. For example, the blue curve corresponds to the crenel pattern of repeated positive uplift (= 1) followed by negative uplift (= -1).

Figure 3 . 5 :

 35 Figure 3.5: Results obtained for Crenel pattern 2 (cf. Fig. 3.3b). The left (resp. right) figure shows the mean number of found intervals (resp. the mean value of RMSE) on the test set by UMODL according to the dataset size. Different curve colors correspond to separate treatment effects. For example, the blue curve corresponds to the crenel pattern of repeated positive uplift (=1) followed by zero uplift.

Figure 3 . 6 :

 36 Figure 3.6: Fig 3.6a, 3.6b, 3.6c present the performances obtained with the trigonometric pattern (cf. Fig. 3.3c), scissors pattern (cf. Fig. 3.3d) and continuous pattern (cf. Fig. 3.3e). Blue curves depict the mean value of the RMSE per dataset size while the green curves indicate the number of found intervals.

  3.7.

Figure 3 . 7 :

 37 Figure 3.7: An unsupervised label encoding of the categorical variable 'subscription'

Figure 3 . 8 :

 38 Figure 3.8: Two different discretization models for a categorical variable

Figure 3 . 9 :

 39 Figure 3.9: The null model: the model with one interval

Figure 3 . 10 :

 310 Figure 3.10: The resulting discretization model by encoding the values of the 'subscription' variable by ascending uplift values

Figure 3 . 11 :

 311 Figure 3.11: Average qini coefficients and their variances according to the number of added noisy features. The X-axis indicates the total number of added noisy features. Y-axis represents the qini coefficients achieved by uplift models.

Figure 3 . 12 :

 312 Figure 3.12: Percentage of selected noisy features according to the number of added noisy features.

  This work is the object of the following publication: Rafla, M., Voisine, N., & Crémilleux, B. (2023, May). Parameter-Free Bayesian Decision Trees for Uplift Modeling. In Advances in Knowledge Discovery and Data Mining: 27th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2023, Osaka, Japan, May 25-28, 2023, Proceedings, Part II (pp. 309-321). Cham: Springer Nature Switzerland.

Figure 4 . 1 :

 41 Figure 4.1: Example of an uplift tree model. Internal nodes are described by the segmentation variable X s and the distribution of instances in each of the two children {N si }. Leaf nodes containing a treatment effect (i.e W l = 1) are described by the class distribution for each treatment. This applies to leaves 4, 5 and 7. Leaf nodes containing no treatment effect (i.e W l = 0) are only described by the class distribution (this is the case of leaf 6).

  (a) Grid pattern (b) Continuous pattern

Figure 4 . 2 :

 42 Figure 4.2: Uplift for 2 synthetic patterns. Fig. 4.2a (grid pattern): uplift values for each cell. Fig. 4.2b (continuous pattern): uplift values are P (Y |T = 0, x1, x2) = 1 -(x1 + x2)/20 while P (Y |T = 1, x1, x2) = (x1 + x2)/20.

Figure 4 . 3 :

 43 Figure 4.3: RMSE obtained by training tree-based methods.

  (a) tree-based methods (b) meta-learners and forest-based methods

Figure 4 . 4 :

 44 Figure 4.4: Overall average ranking of the uplift approaches

Contents 5 . 1 5 . 2 5 . 3

 515253 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 92 Evaluation of uplift with biased data . . . . . . . . . . 93 5.2.1 Problem setting . . . . . . . . . . . . . . . . . . . . . . . 94 5.2.2 Designing of the experimental protocol . . . . . . . . . . 94 5.2.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . 95 5.2.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Method to reduce the NRA bias impact . . . . . . . 103 5.3.1 Method Description . . . . . . . . . . . . . . . . . . . . 103 5.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 104

Figure 5 . 1 :

 51 Figure 5.1: Biased samples generation procedure for one fold (a 10-fold cross validation is used): (1) Variable(s) V is chosen to create E1 and E2. (2) Creating training and test sets with 10-fold cross validation. (3) Random sampling of treatment and control groups. (4) The sizes of the treatment and control groups are always the same throughout the biasing process.

Figure 5 . 2 :

 52 Figure 5.2: Qini coefficients of uplift methods based on NRA bias rates.The figure title consists of the dataset name followed by the variable used to generate the bias. In the legend, a method name is followed by the associated learning algorithm.

Figure 5 . 3 :

 53 Figure 5.3: Overall ranking for the different uplift approaches.

Figure 5 . 4 :

 54 Figure 5.4: Heat map to visualize the comparison between uplift methods. A value of p smaller than 0.05 means that the null hypothesis is rejected.

Figure 5 . 5 :

 55 Figure 5.5: The qini values obtained through class-transformation with Xgboost for varying levels of NRA bias rates, both with and without reweighting. Each figure's title is composed of the dataset's name, followed by the specific variable utilized to generate the bias.

Contents 6 . 1 6 . 2 6 . 3

 616263 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 108 Uplift methodology . . . . . . . . . . . . . . . . . . . . 109 An experimental study on telecom data . . . . . . . . 110 6.3.1 UB-DT and UB-RF . . . . . . . . . . . . . . . . . . . . 110 6.3.2 Variable transformation . . . . . . . . . . . . . . . . . . 111 6.3.3 Feature Selection . . . . . . . . . . . . . . . . . . . . . . 112 6.4 Kuplift Library . . . . . . . . . . . . . . . . . . . . . . . 113 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 114

  Size P(Y=1|T=0) P(Y=1|T=1) P(T=1) No. columns No. continuous variables 20000

Figure 6 . 1 :

 61 Figure 6.1: Qini curves: The x-axis denotes the number of individuals targeted, while the y-axis shows the number of incremental positive outcomes. X-learner R-learner DR-learner 2M LR RF LR RF LR RF LR RF ED-RF UB-RF UB-DT 8.6(2.6) 5.6(3.8) 8.8(2.5) 8.0(2.5) 4.0(4.6) -0.5(2.0) 7.9(2.5) 7.5(4.4) 7.8(2.3) 14.4(5.3) 10.2(3.6)Table 6.2: Qini values multiplied by 100 and variance for each uplift model. In bold the biggest qini value.

Figure 6 . 2 :

 62 Figure 6.2: Uplift models with the top features

Contents 7 . 1 7 . 2

 7172 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 118 Future directions . . . . . . . . . . . . . . . . . . . . . . 122 7.2.1 Extension of our Bayesian approach . . . . . . . . . . . 122 7.2.2 Future directions for the uplift modeling problem . . . . 123 7.2.3 Data bias in uplift modeling . . . . . . . . . . . . . . . . 124

Figure A. 1 :

 1 Figure A.1: Overall average ranking of the uplift approaches

  Search algorithm and post-optimization . . . . . . . . . 54 3.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 55 Description . . . . . . . . . . . . . . . . . . . . . . . . . 56

	3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .	46
	3.2 UMODL . . . . . . . . . . . . . . . . . . . . . . . . . . .	48
	3.2.1 UMODL Criterion . . . . . . . . . . . . . . . . . . . . . 49
	3.2.2 3.3 UMODL quality evaluation experiments . . . . . . .	56
	3.3.1

3.3.2 Synthetic uplift patterns . . . . . . . . . . . . . . . . . . 58 3.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 How to deal with categorical variables? . . . . . . . . 60 3.4.1 Why unsupervised label encoding is not efficient ? . . . 62 3.4.2 An uplift-based label encoding for UMODL . . . . . . . 65 3.5 UMODL Feature Selection . . . . . . . . . . . . . . . . 67 3.5.1 Description of UMODL feature selection . . . . . . . . . 67 3.5.2 Experimental Protocol . . . . . . . . . . . . . . . . . . . 68 3.5.3 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.5.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 70

Table 3 .

 3 .1). 1: Description of the 'subscript' variable. T0Y0 denotes the number of examples with T = 0 and Y = 0. Similarly, T0Y1, T1Y0, and T1Y1 represent examples with respective T and Y values.

	Value	T0Y0 T0Y1 T1Y0 T1Y1 P(Y=1|T=1) P(Y=1|T=0) Uplift
	Prepaid	2102	883 1214 1771	0.6	0.3	0.3
	Postpaid	2098	887	316 2669	0.9	0.3	0.6
	Family Plan	21	9	12	18	0.6	0.3	0.3

Datasets

  We conducted experiments on 8 real and synthetic datasets widely used in the uplift modeling community:

	Dataset	No. Rows	No. Columns	Treatment ratio	Outcome Ratio	Average Uplift	Treatment variable	Outcome variable
	Hillstrom-m	42,613	10	0.5	0.145	0.076	'mens'	'visit'
	Hillstrom-w	42,693	10	0.5	0.128	0.045	'womens'	'visit'
	Hillstrom-mw	64,000	10	0.67	0.146	0.06 'mens' & 'womens'	'visit'
	Gerber-N	229,444	16	0.166	0.31	0.081	'neighbour'	'voted'
	Geber-S	229,461	16	0.166	0.304	0.04	'self'	'voted'
	Starbucks	84,534	9	0.5	0.012	0.009	'promotion'	'purchase'
	Information	20,000	69	0.5	0.2	0.0018	'treatment'	'purchase'
	Bank-tel	15,926	17	0.18	0.05	0.09	'telephone'	'Y'
	Bank-cell	42,305	17	0.6	0.115	0.11	'cellular'	'Y'
	Bank-tel-cel	45,211	17	0.71	0.116	0.107 'telephone'&'cellular'	'Y'
	Megafon	600,000	52	0.5	0.2	-0.18	'treatment'	'conversion'
	Criteo-v 1	13,979,592	12	0.85	0.047	0.68	'treatment'	'visit'
	Criteo-c 1	13,979,592	12	0.85	0.0029	0.37	'treatment'	'conversion'
	RHC	5735	62	0.38	0.35	-0.05	'RHC'	'swang1'

Table 4 .

 4

1: Summary of datasets specifications. 1. Hillstrom 2 : a classical dataset for uplift modeling with data of customers who either received emails featuring men's or women's products, or received no emails, 2. Criteo [19] (previously introduced in Section 3.5.3): a usual marketing dataset for uplift modeling, 3. Bank [49]: a marketing campaign conducted by a bank, 4. Information 3 : a marketing dataset in the insurance domain, a part of the Information R package, 5. Megafon 4 : a synthetic dataset created for uplift modeling. It is generated by telecom companies in order to reproduce the situations encountered by these companies, 6. Starbucks 5 : an advertising promotion tested to improve customers purchases, 7

1.6(1.6)

	Hillstrom-w	0.8(1.6)	5.2(2.5)	5.2(2.6)	6.4(1.2)	-0.4(2.0)	4.8(2.3)
	Hillstrom-mw -0.6(0.8) -0.1(1.2)	-0.8(1.1)	4.4(2.7)	-0.0(1.0)	-0.4(1.4)
	Gerber-n	5.6(0.8) 1.3(0.8)	1.2(0.8)	1.1(0.6)	1.3(0.8)	1.9(0.6)
	Gerber-s	5.5(1.1) 0.4(0.5)	0.4(0.6)	0.5(0.3)	0.4(0.4)	0.8(0.6)
	Criteo-c	8.0(1.5)	4.1(1.4)	4.8(1.5) 15.2(0.3) 1.7(0.3)	13.7(3.2)
	Criteo-v	0.4(0.3)	-1.2(0.2)	-1.1(0.3)	-1.3(0.3)	0.4(1.1)	3.6(1.2)
	Megafon	5.1(0.6)	4.5(0.9)	4.7(0.9)	4.7(0.9)	4.9(0.8)	7.8(0.8)
	Bank-tel	5.4(7.6) -12.5(2.8) -10.8(7.0) -10.2(7.8) -12.8(2.9) 12.8(8.0)
	Bank-cell	11.1(3.0) -2.0(1.5)	-1.4(2.5)	-2.2(1.5)	-3.7(1.5) 38.4(3.4)
	Bank-tel-cell 10.3(1.6) -1.9(1.2)	-1.2(2.1)	-1.8(1.2)	-3.4(1.4) 37.1(2.6)
	Information	4.6(3.4)	-6.3(2.8)	-6.3(2.8)	-2.8(1.5)	-5.4(1.5) 11.8(2.4)
	Starbucks	1.4(1.4) 20.1(3.0) 18.3(3.4) 19.9(3.2) 13.9(3.9) 20.2(3.5)
	RHC	12.8(1.9) 18.4(3.8) 19.9(4.2) 18.4(3.8) 16.7(2.5) 20.7(5.0)

Table 4 .

 4 2: Average qini coefficients and standard deviation (multiplied by 100). The best qini coefficient for each dataset is marked in bold.

	Dataset	XLearner RLearner	DR	2M	KL-RF	Chi-RF	ED-RF	CTS-RF	UB-RF CausalForest
	Hillstrom-m	0.3(2.3)	0.3(1.8)	1.2(1.6)	0.7(2.3)	-0.0(2.1)	-0.9(1.5)	0.7(1.5)	1.1(1.9)	1.8(1.6)	-0.2(1.6)
	Hillstrom-w	6.2(1.7)	6.2(1.4)	6.0(1.4)	4.9(1.1)	6.2(1.1)	7.0(1.0)	6.2(1.1)	5.7(1.3)	6.7(1.1)	2.1(1.9)
	Hillstrom-mw	3.7(2.3)	3.9(2.7) 3.8(2.8)	3.0(2.0)	3.0(1.3)	2.8(1.5)	3.6(2.5)	2.3(2.4)	3.1(1.7)	0.1(1.7)
	Gerber-n	3.7(0.6)	1.9(0.7)	0.5(0.9)	3.1(0.6)	1.8(1.0)	2.1(1.1)	1.9(0.5)	1.4(1.0)	2.7(0.7)	2.9(1.0)
	Gerber-s	2.4(0.9)	1.7(0.7)	0.6(0.9)	2.2(0.8)	1.3(1.0)	1.4(0.6)	1.6(0.8)	1.4(0.7)	1.8(0.8)	3.1(0.5)
	Criteo-c	22.3(1.8) 19.4(1.0) 20.0(0.6) 19.5(1.6) 14.6(3.5) 12.4(4.3) 21.1(2.3)	7.3(3.9)	18.7(1.5)	10.9(2.4)
	Criteo-v	0.3(0.8)	5.3(0.5)	4.8(1.5)	3.9(0.5)	5.4(1.2)	4.8(1.7)	6.1(1.0)	2.4(0.8)	5.7(0.7)	0.4(0.4)
	Megafon	18.2(0.6) 2.6(0.5)	2.2(0.9)	16.6(0.9) 11.2(0.7) 11.0(1.2) 10.8(0.8)	9.2(1.1)	12.8(1.0)	9.7(0.7)
	Bank-tel	14.5(7.6)	2.8(8.8) 16.0(9.0) 21.1(11.6) -15.5(6.3) -6.1(12.6) -15.8(5.6) -18.7(2.9) 26.7(7.2)	25.4(5.3)
	Bank-cell	18.8(4.7) 23.3(3.6) 17.4(6.5) 31.0(3.9)	0.4(2.3)	1.5(2.5)	-2.5(2.6)	-1.0(1.9) 45.5(2.7)	20.8(2.6)
	Bank-tel-cell	16.2(5.6) 23.8(2.5) 17.0(3.4) 30.5(2.7)	1.4(3.4)	-0.4(5.7)	-1.7(3.1)	-0.5(2.3) 46.1(2.1)	23.5(2.9)
	Information	14.9(3.3) 10.0(3.1) 4.1(2.3)	13.7(4.1)	9.6(2.0)	9.7(3.1)	11.2(2.9) 10.6(2.9) 12.0(3.1)	10.5(3.2)
	Starbucks	22.3(4.5) 22.4(3.9) 22.4(3.7) 22.7(4.1) 22.4(2.1) 21.4(3.4) 23.4(3.2) 20.8(3.1) 20.2(3.3)	8.1(3.7)
	RHC	32.4(3.5) 31.3(4.3) 30.3(5.0) 34.6(4.3) 29.6(4.2) 29.7(5.0) 30.0(4.1) 29.1(3.7) 27.2(5.0)	27.6(4.5)

Table 4 .

 4 3: Average qini coefficients and standard deviation (multiplied by 100) across datasets and uplift approaches. In bold, the best value for each dataset

Table 4 .

 4 4: Computational time (in seconds) per Uplift approach for the first fold in each dataset. The last two columns represent the number of continuous columns and those with over 1000 values.

	Dataset	XLearner RLearner	DR	2M	KL-RF Chi-RF ED-RF CTS-RF UB-RF CausalForests	Cont. cols	Cont. cols > 1000 values
	Hillstrom-m	14.769	14.926 15.624	7.966	64.8	66.202	66.728	44.485	60.609	2.023	5	1
	Hillstrom-w	14.486	14.614 15.629	7.664	63.912	61.765	63.633	41.815	65.537	2.03	5	1
	Hillstrom-mw	15.614	14.857	15.78	7.914	99.732	97.967 102.941	69.53	102.351	2.275	5	1
	Gerber-n	19.194	18.79 20.257	9.202 398.158 503.291 350.923	346.62	1139.27	5.37	6	2
	Gerber-s	30.319	29.136 34.821 15.233 432.648 381.878 505.065 300.064 1009.788	16.936	6	2
	Criteo-c	25.204	20.918 21.782 14.061 382.942 375.397 468.533 132.642 2944.905	9.041	14	7
	Criteo-v	24.423	21.084 21.837 13.612 382.189	348.73 337.542 145.127	3013.66	9.218	14	7
	megafon	26.844	24.472 26.519 12.519 205.696 195.138 253.749 229.131	2443.51	24.945	50	50
	Bank-tel	18.47	17.566 17.596	8.826	26.652	28.367	24.809	20.773	61.075	1.413	7	2
	Bank-cell	19.167	19.279 19.328	9.471	91.581	96.933	80.902	53.773	250.195	2.032	7	2
	Bank-tel-cell	19.251	18.681 33.251 15.924	57.693	62.99	52.842	37.069	279.54	2.102	7	2
	Information	25.163	24.581 40.833 21.038	29.226	30.676	28.871	21.899	601.167	1.561	67	13
	Starbucks	22.398	24.225 26.289	7.942 130.392	86.709	69.791	99.973	84.962	5.406	2	1
	RHC	23.142	20.442 20.648	9.644	15.301	15.295	15.663	12.427	166.619	2.153	7	7

Table 5 .

 5 1: Average qini coefficients with standard deviation for tree. In bold, the best value for each dataset.

	Retail-first-redeem-date'	Retail-first-redeem-date	Retail-express-spent-mean'	Retail-express-spent-mean	Gerber-yob'	Gerber-yob	Gerber-cluster'	Gerber-cluster	Starbucks-V5'	Starbucks-V5	Starbucks-V4'	Starbucks-V4	Information-PREM-BANKCARD-CRED-LMT'	Information-PREM-BANKCARD-CRED-LMT	Information-N-OPEN-REV-ACTS'	Information-N-OPEN-REV-ACTS	Bank3-month'	Bank3-month	Bank3-duration'	Bank3-duration	megafone100K-f16'	megafone100K-f16	megafone100K-f35'	megafone100K-f35	Criteo50K-f8'	Criteo50K-f8	Criteo50K-f2'	Criteo50K-f2	hillstrom-m-womens'	hillstrom-m-womens	hillstrom-m-mens'	zenodo-trial0-x32	Dataset
	0.63(0.06) 0.89(0.05) 0.79(0.3) 1.2(0.24) 0.63(0.1) 0.91(0.18) 0.78(0.24) 0.97(0.04) 0.15(0.15) 0.82(0.02) 1.37(0.28) 1.34(0.32) 1.28(0.34) 0.91(0.17)	0.59(0.04) 0.89(0.07) 0.44(0.4) 0.82(0.45) 0.57(0.05) 0.58(0.33) 0.41(0.22) 0.84(0.03) -0.31(0.19) 0.8(0.07) 1.65(0.12) 1.64(0.11) 1.63(0.18) 1.07(0.18)	0.91(0.04) 0.92(0.1) 0.84(0.45) 0.92(0.11) 0.87(0.07) 0.41(0.66) 0.96(0.5) 0.89(0.09) 0.56(0.57) 0.54(0.15) 0.83(0.33) 0.86(0.27) 0.67(0.47) 1.21(0.17)	0.65(0.32) 0.79(0.21) 0.77(0.25) 0.98(0.33) 0.79(0.18) 0.74(0.35) 1.21(0.43) 0.72(0.18) 0.68(0.21) 0.59(0.12) 1.26(0.16) 1.26(0.15) 1.27(0.18) 1.05(0.37)	1.23(0.42) 1.38(0.16) -3.57(0.39) 0.02(0.13) 0.17(0.55) 0.12(0.34) -2.47(0.33) 1.52(0.12) -2.23(0.21) -1.31(0.54) -1.54(0.43) -1.39(0.35) -0.79(0.46) -1.55(0.3)	1.49(0.13) 1.5(0.08) -3.81(0.25) 0.02(0.01) 0.62(0.34) 0.51(0.29) -1.88(0.33) 1.45(0.1) -2.16(0.21) -0.09(0.47) -1.26(0.77) -0.78(0.37) -0.62(0.35) -1.64(0.3)	1.49(0.12) 1.52(0.14) -3.88(0.18) 0.08(0.02) 0.6(0.3) 0.56(0.39) -2.24(0.44) 1.61(0.18) -1.99(0.23) -0.27(0.4) -0.28(0.57) -0.13(0.63) 0.07(0.55) -1.77(0.24)	1.32(0.22) 1.23(0.24) -3.71(0.19) -0.05(0.17) 0.45(0.4) 0.27(0.34) -2.08(0.39) 1.29(0.18) -2.43(0.25) -0.6(0.4) -2.3(0.54) -2.1(0.79) -1.4(0.55) -1.83(0.26)	15.67(0.82) 15.65(0.79) -6.7(3.56) 8.81(2.01) 14.93(0.48) 15.24(0.5) 17.82(2.28) 16.18(0.43) 13.86(1.64) 16.09(0.45) 13.29(0.94) 13.22(2.17) 11.32(1.09) 11.81(2.19)	15.46(0.66) 15.01(0.82) 10.96(2.62) 10.43(1.67) 14.21(2.47) 14.5(1.91) 16.5(2.64) 15.87(0.85) 15.02(2.22) 16.21(0.75) 13.87(2.22) 13.89(2.5) 14.61(2.65) 1.67(3.24)	13.4(7.33) 15.14(3.17) -10.3(4.15) -8.4(5.17) 13.04(6.93) 15.2(3.15) 17.87(1.12) 14.39(3.62) 12.17(2.31) 14.54(4.12) 10.37(1.48) 11.25(2.21) 6.65(2.02) 2.69(3.91)	13.4(7.33) 15.14(3.17) -10.3(4.15) -8.4(5.17) 13.04(6.93) 15.2(3.15) 17.87(1.12) 14.39(3.62) 12.17(2.31) 14.54(4.12) 10.37(1.48) 11.25(2.21) 6.65(2.02) 2.69(3.91)	8.36(0.89) 8.64(0.58) 5.05(1.43) 3.75(0.2) 3.46(0.19) 1.28(0.78) 11.42(0.76) 8.7(0.29) 10.26(0.94) 3.86(0.5) 6.72(1.31) 6.97(1.46) 6.37(1.18) 9.84(1.11)	7.06(2.82) 7.03(2.39) 6.46(1.07) -0.05(2.24) 3.29(1.25) 0.79(1.21) 10.39(1.54) 6.83(1.38) 10.67(0.85) 3.23(1.22) 7.64(1.95) 8.0(1.45) 5.69(2.21) 11.2(1.05)	7.26(0.87) 7.25(0.54) 6.46(1.0) 2.23(2.27) 3.25(0.37) 0.77(1.39) 11.65(0.96) 7.95(0.8) 10.41(0.53) 2.64(1.2) 6.89(1.95) 7.12(1.6) 3.93(3.0) 10.17(0.94)	8.17(0.85) 8.23(0.58) 7.69(0.72) 2.33(1.64) 3.65(0.25) 1.93(1.22) 12.03(1.11) 8.49(0.57) 10.22(0.45) 3.31(0.71) 9.36(0.82) 9.43(0.39) 8.33(1.18) 11.39(0.59)	-1.89(4.27) -6.98(6.17) -17.42(3.99) -14.49(1.38) 6.72(4.73) -4.01(9.69) -22.6(6.17) 11.71(0.78) -21.83(4.47) -11.92(1.74) -16.26(11.81) -4.17(9.21) -12.15(14.25) 1.35(4.26)	-5.64(13.78) 1.49(2.56) -25.64(9.16) -16.51(4.57) 6.23(1.76) -0.81(6.64) -31.11(8.84) -0.71(1.99) -23.21(8.12) -17.67(9.0) -10.0(10.66) -4.59(6.94) -20.0(18.47) -2.64(5.73)	-10.74(2.52) -2.1(1.33) -22.36(4.2) -19.22(2.88) -1.92(1.68) -6.97(3.46) -28.34(9.41) 7.47(0.83) -30.6(1.95) -11.37(1.2) -12.75(10.78) -4.64(3.56) -12.99(10.93) -5.29(3.65)	-3.45(3.84) 4.86(6.14) -13.49(5.09) -8.92(3.61) 5.71(8.14) -11.63(2.33) -27.47(4.41) 14.54(3.08) -21.38(4.59) -6.56(6.02) -7.87(5.22) -9.68(14.3) -13.2(13.59) 6.39(5.59)	2.64(0.2) 2.62(0.2) 11.81(0.9) 2.18(0.13) 2.13(0.37) 2.33(0.28) 15.3(0.53) 2.61(0.16) 15.04(0.3) 2.86(0.17) 2.34(0.65) 2.2(0.85) 1.5(0.79) 8.68(0.5)	2.24(0.36) 2.21(0.29) 5.58(4.57) 2.4(0.23) 0.75(0.5) 0.76(0.46) 14.66(1.41) 2.18(0.45) 14.6(1.15) 2.54(0.33) 1.85(0.84) 2.7(0.63) 1.18(0.8) 8.74(1.36)	2.64(0.26) 2.62(0.19) 7.53(3.44) 1.21(0.67) 1.67(0.26) 1.57(0.27) 15.6(0.25) 2.18(0.21) 15.36(0.19) 2.57(0.22) 2.02(0.7) 2.48(1.0) 0.87(0.58) 7.38(0.6)	2.36(0.51) 2.43(0.23) 11.12(1.65) 1.77(0.44) 1.49(0.32) 1.66(0.34) 15.44(0.57) 2.21(0.24) 15.35(0.46) 2.59(0.19) 2.84(0.86) 2.57(0.75) 1.75(1.24) 8.41(0.41)	10.87(0.79) 10.77(0.95) -2.47(5.1) -1.9(6.06) 11.05(1.12) 11.16(0.53) 9.2(1.65) 9.0(4.47) 6.36(2.3) 6.57(4.14) 1.33(1.21) 2.37(2.84) 0.08(1.53) 10.98(0.93)	10.91(1.81) 10.62(2.51) -0.35(6.92) 1.57(7.56) 11.46(1.18) 11.1(0.93) 9.96(1.15) 8.44(5.07) 7.38(2.41) 6.64(4.83) -0.14(2.78) 0.83(3.71) -0.83(3.06) 11.37(0.34)	10.64(0.34) 10.71(0.41) 7.27(1.07) 7.07(1.9) 11.16(0.58) 11.57(0.22) 7.76(0.58) 10.74(0.36) 7.74(0.41) 10.6(0.28) 8.39(0.92) 9.14(0.44) 8.55(2.36) 11.19(0.22)	10.8(1.19) 10.44(2.09) 0.09(6.61) 2.01(7.11) 10.9(2.86) 11.39(0.97) 9.62(1.28) 8.59(4.7) 7.11(2.03) 6.63(4.43) 1.16(3.23) 1.35(3.89) -0.73(3.23) 11.7(0.58)	0.85(0.67) 1.01(0.44) -1.48(0.53) -0.16(0.55) 0.63(0.61) 0.79(0.52) -0.07(0.38) 1.22(0.53) -0.66(0.33) 1.51(0.66) -0.46(0.52) -0.17(0.55) 0.25(0.41) 1.73(0.42)	0.85(0.67) 1.01(0.44) -1.48(0.53) -0.16(0.55) 0.63(0.61) 0.79(0.52) -0.07(0.38) 1.22(0.53) -0.66(0.33) 1.51(0.66) -0.46(0.52) -0.17(0.55) 0.25(0.41) 1.77(0.4)	1.64(0.7) 1.67(0.59) -0.65(0.28) -0.05(0.6) 0.97(0.6) 1.03(0.59) 0.63(0.53) 1.82(0.52) 0.36(0.36) 1.75(0.65) -0.03(0.52) 0.31(0.4) 0.3(0.49) 1.86(0.4)	0.8(0.67) 0.66(0.75) 0.2(0.35) -0.0(0.71) 0.42(0.66) 0.36(0.49) 0.2(0.62) 0.61(0.81) 0.21(0.47) 0.64(1.34) -0.6(0.56) -0.43(0.72) -0.05(0.74) 0.59(1.17)	Xgboost LR Xgboost LR Xgboost LR Xgboost LR Xgboost LR KL ED CTS UB	R-Learner Class Transformation DR-Learner X-Learner 2M RF

Table 5 .

 5 2: Average qini coefficients and standard deviation. In bold, the best value for each dataset

	4.97(3.75)
	6.51(1.62)
	5.95(0.87)

Table 5 .

 5 3: Reference qini coefficient and average qini coefficients for the best approaches

Table 5 .

 5

	Dataset		Class-Transformation with LR		Class-Transformation with Xgboost
		Ref.qini	w/o weights	wt_1	wt_2	Ref.qini	w/o weights	wt_1	wt_2
	zenodo-trial0-x32	8.27(3.23)	9.65(0.59)	9.39(0.44)	7.12(0.8)	5.81(2.08)	7.06(1.14)	7.03(0.93)	5.84(1.11)
	zenodo-trial0-x32'	8.15(2.33)	9.7(0.48)	9.15(0.96)	7.2(0.97)	5.81(2.08)	7.51(0.98)	7.51(0.73)	5.84(1.11)
	zenodo-trial0-x34	7.85(2.31)	8.99(0.75)	9.66(0.31)	8.1(0.37)	6.45(3.98)	7.9(1.22)	7.57(1.36)	6.97(1.06)
	zenodo-trial0-x34'	7.25(1.94) 10.21(0.21)	8.79(2.62)	6.29(0.77)	5.12(3.36)	8.41(0.85)	7.57(1.36)	4.47(1.36)
	GridPattern-Comb2	18.73(0.0)	18.69(0.04)	18.69(0.03) 18.72(0.03)	21.24(0.1)	21.1(0.21)	21.06(0.35) 21.11(0.25)
	GridPattern-Comb2'	18.73(0.0)	18.71(0.02) 18.71(0.04)	18.7(0.09)	21.25(0.02)	20.96(0.38) 21.09(0.26)	21.08(0.29)
	ContPattern-Comb2	30.92(0.0)	30.92(0.0)	30.92(0.0)	30.92(0.0)	30.35(0.0) 30.35(0.02)	30.32(0.06)	30.23(0.19)
	ContPattern-Comb2'	30.92(0.0)	30.92(0.0)	30.91(0.0)	30.92(0.0)	30.35(0.0) 30.35(0.03)	30.32(0.02)	30.23(0.17)
	hillstrom-w-mens	6.07(2.11)	-4.33(3.78)	4.74(3.55)	4.36(3.56)	1.93(2.05)	-4.31(2.29)	0.39(2.1)	0.96(2.25)
	hillstrom-w-mens'	6.29(2.61)	6.21(0.19)	6.15(0.21)	6.23(0.29)	1.49(1.64)	4.62(1.29)	2.05(1.25)	2.61(1.07)
	hillstrom-w-womens	6.02(1.72)	-5.43(3.65)	4.7(3.38)	4.1(3.55)	2.89(2.53)	-4.78(2.54)	0.31(2.24)	1.6(2.56)
	hillstrom-w-womens'	6.02(1.72)	-5.03(3.72)	4.7(3.38)	4.1(3.55)	2.89(2.53)	-4.56(2.63)	0.31(2.24)	1.6(2.56)
	hillstrom-m-mens	1.19(1.64)	-0.0(0.71)	0.89(0.67)	0.99(0.74)	-0.45(2.99)	0.2(0.35)	0.07(0.31)	0.22(0.45)
	hillstrom-m-mens'	1.05(2.71)	-0.05(0.6)	1.73(0.93)	1.56(0.85)	0.28(2.42)	-0.65(0.28) -0.19(0.67)	-0.25(0.73)
	hillstrom-m-womens	1.51(2.56)	-0.16(0.55)	1.3(0.82)	1.33(0.91)	-0.51(2.57)	-1.48(0.53) -0.83(0.72)	-1.03(0.54)
	hillstrom-m-womens'	1.51(2.56)	-0.16(0.55)	1.3(0.82)	1.33(0.91)	-0.51(2.57)	-1.48(0.53) -0.83(0.72)	-1.03(0.54)
	Criteo50K-f2	10.33(1.86)	2.01(7.11)	6.33(7.24)	8.26(6.97)	6.48(2.22)	0.09(6.61)	2.75(5.97)	5.27(5.39)
	Criteo50K-f2'	8.91(2.11)	7.07(1.9)	7.54(3.53)	7.31(4.16)	5.97(2.46)	7.27(1.07)	5.33(1.11)	4.21(1.38)
	Criteo50K-f8	10.35(1.52)	1.57(7.56)	5.58(7.93)	7.98(7.36)	6.26(2.32)	-0.35(6.92)	3.05(6.21)	5.27(5.76)
	Criteo50K-f8'	9.87(1.6)	-1.9(6.06)	6.27(7.31)	7.44(6.42)	4.32(2.43)	-2.47(5.1)	0.94(5.53)	2.69(4.84)
	megafone100K-f35	2.04(1.27)	1.77(0.44)	1.91(0.6)	2.05(0.25)	13.35(0.81)	11.12(1.65)	11.07(1.75) 12.41(1.43)
	megafone100K-f35'	2.34(1.23)	1.21(0.67)	2.21(0.24)	2.08(0.56)	13.36(1.62)	7.53(3.44)	7.63(3.59)	11.6(2.75)
	megafone100K-f16	2.52(1.55)	2.4(0.23)	2.23(0.32)	2.33(0.33)	13.1(0.99)	5.58(4.57)	5.53(4.52) 10.44(3.43)
	megafone100K-f16'	2.35(1.0)	2.18(0.13)	2.64(0.21)	2.2(0.25)	12.7(1.24)	11.81(0.9)	11.79(0.9) 12.43(0.82)
	Bank3-duration	-15.86(15.84)	-8.92(3.61) -40.62(20.65)	-24.42(9.24) -60.72(61.04) -13.49(5.09) -22.48(6.23) -48.71(11.48)
	Bank3-duration'	-31.91(58.88)	-19.22(2.88) -31.59(20.92) -17.64(6.13) -46.25(36.52)	-22.36(4.2) -30.34(3.35)	-46.31(5.45)
	Bank3-month	-19.5(11.11)	-16.51(4.57) -58.88(15.59)	-16.23(4.8) -48.47(25.77) -25.64(9.16)	-31.7(6.11) -51.89(10.59)
	Bank3-month'	-11.88(17.11) -14.49(1.38) -40.14(12.24)	-18.8(5.58) -54.38(43.57) -17.42(3.99) -26.54(3.27)	-44.99(6.93)
	Information-N-OPEN-REV-ACTS	0.31(2.09)	2.33(1.64)	4.16(0.61)	-0.2(1.02)	8.26(3.16)	7.69(0.72)	8.05(0.73)	7.95(0.86)
	Information-N-OPEN-REV-ACTS'	2.04(2.92)	2.23(2.27)	5.06(0.59)	0.23(1.69)	7.26(3.34)	6.46(1.0)	6.75(0.63)	7.18(0.74)
	Information-PREM-BANKCARD-CRED-LMT	0.96(2.33)	-0.05(2.24)	2.96(2.41)	-1.51(1.65)	5.71(2.27)	6.46(1.07)	5.9(1.0)	6.3(0.9)
	Information-PREM-BANKCARD-CRED-LMT'	0.65(2.45)	3.75(0.2)	4.12(0.37)	0.71(0.69)	7.77(3.79)	5.05(1.43)	5.63(1.43)	7.11(1.15)
	Starbucks-V4	10.73(4.72)	-8.4(5.17) 10.75(7.58)	-4.14(7.05)	1.79(3.52)	-10.3(4.15) -2.34(4.27)	-2.63(4.6)
	Starbucks-V4'	10.73(4.72)	-8.4(5.17) 10.75(7.58)	-4.14(7.05)	1.79(3.52)	-10.3(4.15) -2.34(4.27)	-2.63(4.6)
	Starbucks-V5	15.22(4.33)	10.43(1.67) 15.12(1.48)	11.18(3.51)	4.17(6.69) 10.96(2.62)	10.69(2.06)	6.31(1.88)
	Starbucks-V5'	14.72(5.44)	8.81(2.01) 16.63(0.61)	11.46(3.91)	3.4(5.22)	-6.7(3.56)	-7.12(2.95) -0.39(3.98)
	Gerber-cluster	-0.4(1.72)	-0.05(0.17)	-0.78(0.3)	-0.64(0.27)	-3.37(3.29)	-3.71(0.19)	-3.42(0.3)	-3.72(0.24)
	Gerber-cluster'	-0.7(2.22)	0.08(0.02)	-0.72(0.39)	-0.29(0.38)	-3.73(3.45)	-3.88(0.18) -2.89(0.29)	-3.81(0.16)
	Gerber-yob	-1.18(1.61)	0.02(0.01)	-0.29(0.4)	-0.59(0.26)	-4.18(2.8)	-3.81(0.25) -2.84(0.47)	-3.77(0.4)
	Gerber-yob'	-0.9(1.98)	0.02(0.13)	-1.44(0.32)	-0.64(0.35)	-3.65(3.17)	-3.57(0.39)	-3.2(0.38)	-3.6(0.25)
	Retail-express-spent-mean	1.32(0.8)	0.98(0.33)	0.61(0.46)	1.0(0.5)	0.73(0.88)	0.77(0.25)	0.92(0.32)	0.45(0.22)
	Retail-express-spent-mean'	1.02(0.72)	0.92(0.11)	0.96(0.12)	1.06(0.28)	0.29(0.89)	0.84(0.45)	0.73(0.41)	0.37(0.3)
	Retail-first-redeem-date	1.22(1.03)	0.82(0.45)	0.68(0.27)	1.01(0.22)	0.8(0.98)	0.44(0.4)	0.51(0.38)	-0.06(0.42)
	Retail-first-redeem-date'	1.14(1.36)	1.2(0.24)	1.24(0.27)	1.1(0.29)	0.1(1.06)	0.79(0.3)	0.79(0.2)	-0.02(0.26)
	MAE	0	0.036	0.03	0.021	0	0.05	0.03	0.014

4: Average qini and its variance (shown in brackets) with the classtransformation based methods (in bold, the best value for each dataset). Dataset name is followed by the names of the V variables used to generate the NRA bias.

Table 6 .

 6

1: Data specifications

  .2).

		X-learner	R-learner	DR-learner	Two Model
		LR	RF	LR	RF	LR	RF	LR	RF	ED-RF
	w/o preprocessing	8.6(2.6)	5.6(3.8) 8.8(2.5) 8.0(2.5)	4.0(4.6) -0.5(2.0)	7.9(2.5)	7.5(4.4)	7.8(2.3)
	w/ feature selection 14.2 (3.3) 13.1(4.0) 14.1(3.1) 13.6(3.6) 12.3(5.2) -0.06(1.0) 12.8(1.7) 14.1(3.8) 14.3(4.2)
	w/ transformation 14.3(4.6) 11.6(2.7) 14.0(5.1) 13.6(5.0) 14.3(4.8) 1.7(7.5) 14.8(5.5) 10.0(3.1)	0.4(3.1)

Table 6 .

 6 3: Qini values and variance (multiplied by 100) for each uplift model. In bold the biggest qini value among all the values.

  .1. Starbucks 17.9(4.6) 22.5(3.8 22.4(3.9) 17.6(3.3) 17.3(3.8) 16.9(5.7) 17.1(5.3) 16.9(3.8) 20.2(3.3) 13.8(4.3) RHC 33.0(2.8) 29.3(4.1) 28.2(5.0) 36.8(2.9 34.1(4.8) 34.3(5.1) 34.5(4.7) 32.6(4.6) 30.6(4.4) 30.4(3.7)

	Dataset	XLearner RLearner	DR	2M	KL-RF	Chi-RF	ED-RF	CTS-RF	UB-RF CausalForest
	Hillstrom-m	1.1(2.6)	0.6(2.0)	1.1(1.8)	0.3(2.7)	-1.0(1.5) -0.3(1.6)	-0.4(1.8)	-0.1(1.5)	1.5(1.4	-0.2(2.1)
	Hillstrom-w	4.2(0.9)	6.1(1.6)	6.0(1.7)	4.7(1.5)	4.3(1.5)	4.7(1.3)	4.4(1.2)	4.5(1.4)	6.5(0.9	4.0(1.6)
	Hillstrom-mw	2.9(2.3)	3.8(2.6	3.4(2.7)	2.8(1.9)	0.4(1.1)	0.7(1.0)	0.6(1.8)	1.1(1.1)	3.0(1.7)	0.5(1.0)
	Gerber-n	6.1(0.6	1.9(0.6)	0.6(1.0)	5.7(0.6)	5.3(1.0)	5.4(1.0)	5.7(0.6)	4.2(0.9)	2.8(0.8)	4.5(0.9)
	Gerber-s	5.4(0.8	1.7(0.7)	1.1(0.9)	4.9(1.0)	4.9(0.7)	5.0(1.0)	5.0(0.7)	4.5(0.6)	2.1(0.8)	4.7(0.8)
	Criteo-c	19.6(2.3) 19.3(1.0) 16.6(6.0) 18.4(1.3) 19.6(1.9) 19.1(1.8) 22.0(1.6 10.0(1.9) 20.8(0.9)	15.3(1.9)
	Criteo-v	3.1(0.7)	5.0(0.5)	-3.4(3.5)	2.6(0.7)	5.9(0.5)	5.1(0.6)	6.5(0.5	2.9(0.8)	6.1(0.6)	1.6(0.4)
	Megafon	18.8(0.6	2.6(0.5)	2.3(0.4) 18.3(0.7) 16.5(0.6) 15.9(0.4) 17.2(0.5) 13.8(0.7) 14.3(0.8)	14.0(0.5)
	Bank-tel	-4.8(8.2)	0.9(5.2) -2.7(13.1) 16.4(9.1) -13.9(5.4) -9.1(8.1) -16.6(4.2) -20.5(3.9) 26.0(5.9)	38.5(8.2
	Bank-cell	11.8(4.6) 19.9(5.1) 5.7(11.2) 27.5(3.4)	0.6(3.1)	0.9(2.3)	-0.6(3.1)	-1.7(2.8) 49.0(2.7	30.9(2.3)
	Bank-tel-cell	10.3(4.2) 17.4(8.3) 3.7(10.1) 27.6(3.9)	1.5(3.0)	1.3(3.2)	-2.5(3.7)	-0.6(1.9) 48.6(1.5	32.0(0.9)
	Information	13.0(3.2) 10.1(2.8)	3.3(2.2) 11.8(4.6) 12.9(3.2) 13.1(3.3) 13.3(3.0) 12.4(3.6) 13.6(3.3)	14.1(2.4

Table

A

.1: Average qini values and standard deviation (multiplied by 100) across datasets and uplift approaches. In bold, the best value for each dataset. Each approach was learnt with 50 trees.

The Average Treatment Effect (ATE) measures the difference in the average outcome between the treated group and the control group.

C Ris (I s ) = log 2 (2.865) + log 2 (I s ) + log 2 (log 2 (I s )) + . . .

Our implementation is provided at https://github.com/MinaWagdi/UMODL

Other patterns can be found using the github link provided previously.

https://doi.org/10.5281/zenodo.3653141

For efficiency purposes, model learning was conducted on a random sample of

200,000 instances for each fold.

http://blog.minethatdata.com/2008/03/minethatdata-e-mail-analytics-and-data. html

https://cran.r-project.org/web/packages/Information/index.html

https://ods.ai/tracks/df21-megafon/competitions/megafon-df21-comp/data

https://github.com/joshxinjie/Data_Scientist_Nanodegree/tree/master/ starbucks_portfolio_exercisejoshxinjie

Supplementary results with different uplift approaches can be found in https://github. com/MinaWagdi/UB-DT

For simplicity, both methods will be referred to as 'uplift modeling approaches'.

http://blog.minethatdata.com/2008/03/minethatdata-e-mail-analytics-and-data. html/

https://ods.ai/competitions/x5-retailhero-uplift-modeling/data

https://ods.ai/tracks/df21-megafon/competitions/megafon-df21-comp/data

https://zenodo.org/record/3653141#.YUCYEufgoW8

https://www.khiops.com/

https://github.com/UData-Orange/kuplift

Remerciements

Experiments

We experimentally evaluate the quality of UB-DT as an uplift estimator in Section 4.

Is UB-DT a good uplift estimator?

As we have done previously in Chapter 3, we start our experiments with synthetic datasets. Synthetic datasets are useful because they allow us to create the real CHAPTER 5

Evaluation of Uplift Models with Non-Random Assignment Bias

To facilitate the comparison of the performance of different methods on 50 trees (see Table 4.3) and 10 trees (see Table A.1), we show the delta values in Table A.2. They represent the difference between the qini values in both tables, associated with each uplift approach and each respective dataset. A positive delta value means an improvement in performance when increasing the number of trees from 10 to 50.

When evaluating Table A.2, we note that the performance of UB-RF, along with other forest-based methods (KL-RF, Chi-RF, ED-RF, Causal Forest), shows an improvement as the number of trees increases. Particularly noteable are the positive delta values observed in the Causal Forest approach for all datasets. However, it is to be noted that the initial performance of the Causal Forest approach with 10 trees was poor. The performance of metalearners using xgboost as a base learner decreases as the number of trees is increased. When increasing the number of trees, the performance of UB-RF shows an improvement and at the same time maintains its position among the best uplift approaches. With 50 trees, it has the best average ranking among all the uplift approaches.