A framework for massive scale personalized promotion

Many companies, e.g. Linkedin, Pinterest, Yahoo!, have developed solutions for large-scale optimization based on predictive models. (Xu et al., 2015) focused on online advertisement pacing. The authors developed user response prediction models and optimized for performance goals under budget constraints. (Agarwal et al., 2012) focused on online content recommendation. The authors developed personalized click shaping plans by solving a LP problem in its dual space. (Gupta et al., 2016)(Gupta et al., 2017)(Zhao et al., 2018) study the problem of email volume control. The predicted responses at different levels of email volume served as coefficients of engagement maximization problems. To our knowledge, there are few published studies on large-scale personalized incentive optimization.

Incentive response modeling should establish causal relationship between incentive and user response. The model is used in a counterfactual way to answer the question ”what if users are given incentive levels different from that is observed”. There is a large volume of literature on counterfactual modeling, e.g. (Bonner and Vasile, 2018)(Hartford et al., 2016)(Swaminathan and Joachims, 2015). We use inverse propensity score (IPS) (Austin, 2011)(Rosenbaum and Rubin, 1983) to weight sample data when the data collection process is not randomized. This is assumed in our framework unless otherwise stated.

Shape constraints include constraints on monotonicity and convexity (concavity). They are a form of regularization, introducing bias and prior knowledge. Shape constraints are helpful in below scenarios.

• •

  Monotonicity or convexity (concavity) is desired for interpretability. For example, in economy theory, marginal gain on increasing promotion incentive should be positive but diminishing (Kahneman and Tversky, 2013). In our experience, promotion response is non-decreasing, but the marginal gain does not necessarily decrease. We thus propose to apply just monotonicity constraint to promotion response models.

• •

  Prior knowledge on function shapes exists, but training data is too sparse to guarantee such shapes without regularization. In our experience, this is usually true for promotion response modeling, because a reasonable model is required as early as possible after a promotion campaign kicks off, allowing very limited time for training data collection. At the same time, we do know that response rate should monotonically increase with incentive.

The related works section of (Gupta et al., 2018) summarized four categories of shape-constrained models:

• •

  General additive models (GAMs). A GAM is a summation of multiple one dimensional functions. Each of the 1-d function takes one input feature, and is responsible for enforcing the desired shape for that input.

• •

  Max-affine functions, which express piece-wise linear convex functions as the max of a set of affine functions. If the derivative with respect to an input is restricted to be positive/negative, monotonicity can also be enforced.

• •

  Monotonic neural networks. Neural networks can be viewed as recursive functions, with the output of one layer serving as the next layer’s input. For a recursive function to be convex increasing, it is sufficient if its input function and the function itself are convex increasing. For a recursive function to be convex, it is sufficient if its input function is convex and the recursion is convex increasing.

• •

  Lattice networks (You et al., 2017). The simplest form of lattice network is linear interpolation built on a grid of input space. Monotonicity and convexity are enforced as linear constraints on first and second order derivatives when solving for the model. The grid dimension grows exponentially with the input dimension, so the authors ensembled multiple low-dimension lattice networks built on different subsets of inputs to handle high dimensional data.

(Gupta et al., 2018) showed that lattice network has more expressive power than monotonic neural network since the former allows convex and concave inputs to coexist, and that lattice network is at least as good as monotonic neural network in accuracy.

Our work proposes the DIPN architecture (discussed in section 4) that constrains NN to be monotonic for one input i.e. the incentive level. It does not aim to compete with state-of-the-art shape constrained models in terms of expressiveness, but instead aim to provide high accuracy and interpretability for promotion response modeling.

Because the number of users is large, and $f(x_{i},c_{i})$ is usually nonlinear and non-convex, Equation 1 can be difficult to solve. We can restrict promotion incentive $c_{i}$ to a fixed number of $D$ levels: $\{{d_{j}}|j=0,1,...D-1\}$, and use assignment probability variables $z_{ij}\in[0,1]$ to turn Equation 1 into an LP.

Solution $z_{ij}$ of Equation 2 should be on one of the vertices of its feasible polytope, hence most of the values of $z_{ij}$ should be $0$ or $1$. For fractional $z_{ij}$ in solutions, we treat $z_{ij},\forall i$ as a probability simplex and sample from it. This is usually good enough for production usage.

Equation 2 can be solved by commercial solvers implementing off-the-shelf algorithms such as primal-dual or simplex. If the number of users is too large, Equation 2 can be solved by dual ascent (Boyd et al., 2011). Note the dual problem of the LP can be decomposed into many user-level optimization problems and solved in parallel. A few specialized large-scale algorithms can also be applied to problems with the structure of Equation 2, e.g. (Zhong et al., 2015)(Zhang et al., 2020).

One advantage of Equation 2 is that $f(x_{i},d_{j})$ is computed before solving the optimization problem. Hence the specific choice of the functional form of $f(x_{i},d_{j})$ does not affect the difficulty of the optimization problem. Whether $f(x_{i},d_{j})$ is a logistic regression model or a DNN model is transparent to Equation 2.

Sometimes promotion campaigns have more than one constraints. A commonly seen example is that overlapped subgroups of users are subject to separate budget constraints. In general, we can model any constraints by predictive modeling, and then formulate a multiple-constraint problem. Suppose for each user $i$ there are $K$ kinds of costs modeled by:

The multiple-constraint optimization problem is:

A frequently seen alternative to constrain the total budget $B$ is to constrain budget per capita $b$. The corresponding formulation is as below.

Equation 4 and Equation 5 are both LPs since $f(x_{i},d_{j})$ and $g_{k}(x_{i},d_{j})$ are pre-computed coefficients. They can be solved by the same solvers used for Equation 2.

Sometimes it is desired to be able to make incentive decisions for a stream of incoming users. It is not possible to put such users together and solve one optimization problem beforehand. However, if we can assume the dual variables is stable over a short period of time, such as one hour, we can solve the optimization problem with users in the previous hour, and reuse the optimal dual variables in the next hour. This assumption is usually not applicable to general optimization problems, but when the amount of users is large and user population is stable, it holds. This approach can also be viewed from the perspective of shadow price (Boyd and Vandenberghe, 2004). The Lagrangian multiplier can be interpreted as the marginal objective gain when one more unit of budget is available. This marginal gain should not change rapidly for a stable user population.

We thus break down the optimization step into a dual variable solving step and a decision making step. The decision making step can make incentive decision for a single user. Consider the dual formulation of Equation 2, and let $\lambda$ be the Lagrangian multiplier for the budget constraint:

If $\lambda$ is given, Equation 6 can be decomposed into a per user optimization policy:

Equation 7 is applicable to unseen users as long as $x_{i}$ is known.

”User’s optimal incentive level” is the lowest level for a certain user to be converted. If we offer less incentive, we will lose a user conversion(situation A). If we offer more incentive, we waste a certain amount of marketing funds.

For illustration, we could relax constraint by supposing that optimal $z$ is on its $[0,1]$ boundary, omit the notation of index $i$ and rewrite formula 7 as

where $r(d,y)=y-\lambda d$.

Figure 2 illustrates wrong prediction leads to wrong best incentive level. In this section, Figure 4 illustrates two situations of them in more details. Considering $d^{*}$ is the optimal incentive level for user $i$, according to Equation 7, we hope our prediction function satisfy $f(d_{j})-\lambda d_{j}<f(d^{*})-\lambda d^{*},\forall d_{j}\neq d^{*}$. If due to lack of data, $f(d_{k})-\lambda d_{k}>f(d^{*})-\lambda d^{*}$, incentive level $d_{k}\neq d^{*}$ will be chosen, and a wrong decision will be made.

the user response prediction function frequently gives a high prediction $f(d_{k})$ at a lower incentive level $d_{k}$. And because $d_{k}<d^{*}$, user $i$ didn’t get a satisfactory incentive, we will lose a customer.

In this situation, we introduce prior knowledge to constrain the response curve’s shape: users’ expected response monotonically increases with the promotion incentive. Therefore, $f(d_{k+1})-f(d_{k})$ must greater than zero.

In other situations, a very high prediction $f(d_{k})$ is given at a higher incentive level $d_{k}$. And because $d_{k}>d^{*}$, $d_{k}-d^{*}$ marketing funds is wasted.

In situation B, we introduce another prior knowledge to constrain the response curve’s shape: the incentive-response curves are smooth. Therefore, $(f(d_{k})-f(d_{k-1}))-(f(d_{k-1})-f(d_{k-2}))$ should not be too large.

Based on the discussion of these two situations above, we introduce a novel deep-learning structure DIPN to avoid both situations as far as possible.

Isotonic embedding transforms an incentive level to a vector of binary values. Each digit in the vector represents one level. All digits representing levels lower than or equal to the input level are ones. We use $e(c)\in\{0,1\}^{D}$ to denote the $D$-digit isotonic embedding of incentive level $c$, and $d_{j}$ to denote the incentive level of the $j-th$ digit, thus

If we fit a logistic regression response curve with non-negative weights using isotonic embedding as input, the resulting curve will be monotonically increasing with incentive. Several examples are given in Figure 6.

It is trivial to show the monotonicity of $f(c)$ since $sigmoid$ function is monotonic, and

In DIPN, the non-negative weights are output of DNN layers. These weights are thus personalized. We name the personalized non-negative weight the uplift weight, because it is proportion to the uplift value, defined as the incremental response value corresponding to one unit increase in incentive value.

In a binary classification scenario, the prediction function of DIPN is:

where $w_{j}(x)$ is the uplift weight representation, and $e_{j}(c)$ is the isotonic embedding. $w_{j}(x)$ is learned by a neural network using ReLU activation function in last layer so that $w_{j}(x)$ is non negative .

For two consecutive incentive levels $d_{j}$ and $d_{j+1}$, $w_{j+1}$ is a uplift measure for the incremental treatment effect of increasing incentive from $d_{j}$ to $d_{j+1}$. To see this, approximate $sigmoid$ function by its first order expansion around $d_{j}$:

where $g$ is $sigmoid$ function and $g^{\prime}$ is its first order derivative, $z_{j}=\sum_{j}w_{j}e_{j}(d_{j})+b$. Hence in a small region surrounding $d_{j}$, if $g^{\prime}(z_{j})$ can be seen as a constant, $w_{j+1}$ is proportional to the uplift value at $f(d_{j})$.

Smoothness means that response value does not change much as the incentive level varies. Users’ incentive-response curves are usually smooth when fitted with sufficient amount of unbiased data. We therefore add regularization in the DIPN loss function to enforce smoothness.

where $M$ is the number of training data points, $log\_loss$ measures the degree of fitting to training data, $smoothness\_loss$ measures smoothness of predicted response curve, and $\alpha>0$ balances the two losses.

The definition of $log\_loss$ and the definition of $smoothness\_loss$ are given in Equation 15 and Equation 16 respectively. User index $i$ in Equation 15 and user feature vector $x_{i}$ in Equation 16 are omitted for simplicity.

One necessary and sufficient condition of smoothness of the predicted response curve is the uplift values of consecutive incentive levels are as close as enough. As we have proven in subsection 4.2 that the uplift value can be approximated by the uplift weight representation, we want the difference of the uplift weights $(w_{j+1}-w_{j})^{2}$ to be small enough. $(w_{j+1}w_{j})$ is added to denominator of $smoothness\_loss$ to normalize the differences over all incentive levels.

For stability, the training process is split into two phases-bias net learning phase (BLP) and uplift net learning phase (ULP).

BLP learns the bias net while ULP learns the uplift net. In BLP, only samples with lowest incentive are used for training, and only bias net is activated which is easy to converge.

In ULP, all samples are used and variables in bias net are fixed. The fixed bias net sets up a robust initial boundary for uplift net learning. Bias net’s prediction will be inputted to isotonic layer to enhance uplift net’s capability based on the consumption that users with similar bias are more likely to have similar uplift responses.

Another difference in UWLP is smoothness loss’s weight $\alpha$. $\alpha$ will be decaying gradually in UWLP as we observed that larger $\alpha$ helped model converging faster at the beginning of training. The logloss will dominates total loss eventually. $\alpha$’s updating formula is given as follow:

where $\alpha^{u}$ is initial upper bound of $\alpha$, $\alpha^{l}$ is final lower bound of $\alpha$, $\gamma$ controls decaying speed.

We use synthetic dataset, for which we know the ground truth of data generation process, to evaluate our promotion solution. The feature space consists of three 1-in-n categorical variables, with $n_{1}$, $n_{2}$, and $n_{3}$ categories, respectively. The joint distribution of the three categories consists of $n_{1}n_{2}n_{3}$ different combinations. For each combination, we randomly generate four parameters $a\sim U(0,1)$, $b=1-a$, $\mu\sim U(-50,150)$, and $\delta\sim U(0,50)$, where $U(l,u)$ is the uniform distribution bounded by $l$ and $u$. A curve $y=f(x)$ is then generated as follows:

The discrete version is:

The curves of $y=f(x)$ is used as the ground truth of the expected response $y$ on different incentive $x$, for each joint category of users. Without loss of generality, we constrain the incentive range to be $[0,100]$. It’s easy to see that the curve is monotonically increasing, convex if $\mu<0$, and concave if $\mu>100$.

To generate pseudo dataset with noise and and sparsity, we first generate a random integer $z$ between 1 and 1000 with equal probability, for each feature combination. With $z$ being the number of data points for this combination, we randomly choose a promotion integer $p$ between 1 and 100 with equal probability for each data point. With promotion $p$ and expected response $y=f(p)$, a $0/1$ label is generated with probability $y$ of being 1.

On this dataset, we generated 20000 data points, 5000 training samples, 5000 validation samples and 10000 testing samples.

The evaluation metrics for the response models are shown below tables. Table 2 shows the simulation results on synthetic data with $n_{1}=2,n_{2}=2,n_{3}=2$. DIPN showed the highest future response rate and lowest future cost. Table 3 shows the simulation results on synthetic data with $n_{3}=2,n_{2}=5,n_{3}=7$. Again, DIPN showed the highest future response rate and lowest future cost. Table 4 shows the results on a real promotion campaign, DIPN showed the lowest future cost and the same future response rate as that of DNN. Overall DIPN consistently outperformed other models in our test.

We deployed our solution at Alipay and evaluated it in multiple marketing campaigns using A/B tests. Our solution consistently showed better performance than baselines, and was eventually deployed to all users. We show A/B test results for three marketing campaigns for HuaBei. HuaBei is a online micro-loan service launched by Ant Financial. It has about 300 million users according to public data. The incentive is electronic cash voucher, with usability subject to different terms in different campaigns. These campaigns include:

• •

  Preferred Payment: the voucher can be cashed if a user set Huabei as the default payment method in the mobile application of Alipay.

• •

  New User: the voucher can be cashed if a user activates the Huabei service.

• •

  User Churn Intervention: the voucher can be cashed when a user uses Huabei to make a purchase.

All these campaigns have their corresponding business targets strongly correlated with voucher usage, so we use the usage rates as well as the monetary costs as evaluation metrics. Table 5 shows the relative improvements of DIPN compared to DNN model baselines. DIPN models use $30\%$ traffic in each experiment. 95 percentile confidence intervals are shown in square brackets. In all of the experiments, costs were significantly reduced. In two experiments, average voucher use rates were significantly increased.