A Unified Framework for Marketing Budget Allocation

[KDD2019] A Unified Framework for Marketing Budget Allocation

这次是kdd2019的论文分享,本篇是做预算分配的,因为跟我最近做的工作有些关系,所以刚好整理一下。

背景

预算分配核心是解决该把钱投在哪的问题,本篇文章意在提出一种做预算分配的通用框架,包括两个步骤,首先通过历史数据去学习需求曲线,也可称为市场响应模型(market response model),然后基于模型进行优化预算分配。

框架示意图

整个市场可以根据不同的商品、客户、消费习惯等维度分为多个组(定价歧视的分组,segment),为了将预算分配给各个组,我们需要根据每个组的预算来预测每个组的销量变化情况。尽管一些黑盒的预测方法,如深度学习,已经广泛应用于一些预测问题,但是这样预测和制定决策之间还有很大的gap,其中一个重要的问题就是很难将黑盒的预测结果转化成分配决策。相反,如logit demand curve有明确的表达形式,并且广泛应用于经济学之中,它的缺点则是智能对于每一个市场分组来拟合,并不能利用不同分组下的通用的信息,这会造成很严重的数据分离的问题,因此文中提出一种半黑盒的预测模型,用神经网络来扩展logit demand curve的能力。预测模型的输入被分成两部分:独立的变量和环境变量(上下文变量)。环境变量是市场本身的属性,比如商品品牌、顾客属性、消费时间等等。同时可以证明market cost(市场对于价格最敏感的点)只跟bias parameter有关,所以可以用相同的神经网络来计算不同segment的bias parameter,而弹性参数可以在拟合数据的时候求出,这样销量和花费的变动关系可以有一个显示的表示。

一旦需求曲线确定了,预算分配则可以表示成一个优化问题。用\(N\)表示segment数量,预算分配需要优化\(N\)个变量,在一定预算约束下最大化销量。由于logit demand cruve是非凸的,所以优化问题也是非凸的,文中提出一种办法可以将该问题转化成等价的凸问题。

同时,这个框架可以兼容多种业务约束,包括花费上限、利润下限、或者roi下限。因为有时候价格需要以99结尾,比如19.99,所以有时候变量需要从一个固定的集合取值,本框架也支持对于离散问题的优化求解,可以将该问题转化成一个多选择的背包问题(MCKP,Multiple Choice Knapsack Problem),近似在\(\mathcal{O}(N)\)的时间复杂度下求解。

市场响应(Market Response)

Logit Response Model

logit response model

\(i\)个segment的logit model定义为 \[ d_i(c):=\frac{D_i}{1+\exp{\{-(a_i+b_ic\}}},i=1,\cdots,N \] 其中\(c\)是该市场上的单位花费,\(D_i>0\)表示第\(i\)个segment的全部市场销量,\(c\)既可以大于0也可以小于0,正的花费表示价格折扣,负的花费表示增加附加费。因为每个市场分组都很稳定,所以\(D_i\)可以通过统计的方式得到。\(b_i\)表示敏感度,在一般的情况下,\(b_i>0\)。需求曲线最陡点在\(\hat{c}_i=-a_i/b_i\),我们成这个点为市场花费(market cost),它表示了市场上的平均花费,同时销量在其附近变动时候变化最敏感。随着花费增加,销量会逐渐降低,这是由于边际效应递减。

衡量敏感度的通用方式为弹性,类比价格弹性,我们定义花费弹性为销量变化百分比与花费变化百分比的比值: \[ e_i(c_1,c_2)=\frac{[d_i(c_2)-d_i(c1)]c_1}{[c_2-c_1]d_i(c_1)} \] \(c\)处的弹性可以使得\(c_2\rightarrow c_1\)时取得 \[ e_i(c)=\nabla_cd_i(c)\frac{c}{d_i(c)} \] 根据以上我们可以推 \[ \begin{aligned} \nabla_cd_i(c)=&\frac{D_ib_i\exp{\{-(a_i+b_ic\}}}{[1+\exp{\{-(a_i+b_ic\}}]^2}\\ e_i(c)=&\nabla_cd_i(c)\frac{c}{d_i(c)}\\ =& \frac{D_ib_i\exp{\{-(a_i+b_ic\}}}{[1+\exp{\{-(a_i+b_ic\}}]^2} \cdot \frac{(1+\exp{\{-(a_i+b_ic\}})c}{D_i} \\ =& \frac{b_ic}{1+\exp{\{(a_i+b_ic\}}} \end{aligned} \] 所以当\(\hat{c}_i=-a_i/b_i\)时,\(e_i(\hat{c}_i)=-a_i/2\)

Semi-black-box Model

logit对于数据的使用能力有限,当我们对于每个segment都学习出一个\(a_i\)\(b_i\),并没有使用segment之间相同的数据,所以认为此处的\(c\)为独立变量,环境变量用\(\mathbf{x}_i\)表示,环境变量对于所有segment是通用的,并不会因为segment不同而改变(此处指的应该是有控制的改变,如对于某个segment人为改变花费,而环境变量contextual variables并不能控制),传统的神经网络可以将\(\mathbf{x}_i\)\(c\)都作为输入,而logit只能利用\(c\)作为输入。

假设1:弹性是由环境变量决定的。

相比于直接预测最终的销量,我们用神经网络\(e(\mathbf{x}_i)\)来估计market cost处的的弹性,基于\(e(\mathbf{x}_i)\),弹性的信息可以在不同segment间共享,传统的logit model可以扩展成 \[ d_i(c):=\frac{D_i}{1+\exp{\{2e(\mathbf{x}_i)-b_ic\}}} \] 同时利用了神经网络的表达能力,也显式地表示了价格弹性。

\(e(\mathbf{x}_i)\)的参数需要学习,定义市场份额\(q_i(c)\)\[ q_i(c):=\frac{d_i(c)}{D_i}=\frac{1}{1+\exp{\{-(a_i+b_ic)\}}} \] 其中\(a_i=-2e(\mathbf{x}_i)\)。因为\(D_i\)可以从历史数据上统计得到,所以可以构造训练数据\(\{([\mathbf{x_i}, c_1],\hat{q}_{i1}),\cdots,([\mathbf{x_i}, c_{M_i}],\hat{q}_{i{M_i}})\},i=1,\cdots,N\)。参数可以通过梯度下降来最小化负似然函数 \[ \mathcal{J}=-\frac{1}{\sum_{i=1}^NM_i}\sum_{i=1}^N\sum_{j=1}^{M_i}[ \hat{q}_{ij}\log q_{ij}+(1-\hat{q}_{ij})\log (1-q_{ij}) ] \]

预算分配

对于\(N\)个segments,预算分配需要决定每个segment的花费\(c_i\),用\(\mathbf{c}:=[c_1,\cdots,c_N]\),我们的目标是找到一个最优的\(\mathbf{c}\)在预算约束下来最大化总销量, \[ \begin{aligned} \min_\mathbf{c} && -\sum_{i=1}^N d_i(c_i)\\ \text{s.t.} && \sum_i^Nd_i(c_i)\leq B \end{aligned} \] 其中\(B\)表示预算上限,它既可以为正也可以为负,正的表示花费上限约束,负的表示利润下限约束。

因为\(\sum_{i=1}^Nd_i(c_i)c_i=\sum_{i=1}^ND_iq_i(c_i)c_i\)是一个非凸的函数,直接求解过于困难,所以可以把这个问题转换成等价的凸优化问题。因为\(q_i(c_i)\)是一个严格递增的函数(一般情况下\(b_i>0\)),我们可以得到它的反函数 \[ c_i(q_i)=-\frac{a_i}{b_i}-\frac{1}{b_i}[\ln(1-q_i)-\ln q_i], q_i\in(0,1),i=1,\cdots,N \] 定义\(\mathbf{q}:=[q_1,\cdots,q_N]\),约束\(g(\mathbf{q})\)可以表示为 \[ g(\mathbf{q}):=\sum_{i=1}^ND_iq_ic_i(q_i)-B \] 对其求导之后可以发现\(g(\cdot)\)是个凸函数,所以原问题可以写成凸优化问题 \[ \begin{aligned} \min_\mathbf{q} && \sum^N_{i=1} D_iq_i \\ \text{s.t.} && g(\mathbf{q})\leq 0 \end{aligned} \] 通过引入一个对偶变量\(\lambda\),使用拉格朗日乘子法来优化这个问题 \[ \begin{aligned} \mathcal{L}=& -\sum^N_{i=1}D_iq_i + \lambda (\sum^N_{i=1}D_iq_ic_i(q_i)-B) \\ =& \sum^N_{i=1}(\lambda D_iq_ic_i(q_i)-D_iq_i)-\lambda B \end{aligned} \] 根据KKY条件有 \[ \begin{aligned} g(\mathbf{q}^*) \leq &0\\ \lambda^*\geq& 0\\ \lambda^*g(\mathbf{q}^*)=&0\\ \nabla_{q_i}(\lambda^*D_iq_i^*c_i(q_i^*)-D_iq_i^*)=&0\\ i=1,\cdots,N \end{aligned} \] 其中\(\mathbf{q}^*\)\(\lambda^*\)是原问题和对偶问题的最优解。

\(g(\tilde{q})\)表示表示\(g(\mathbf{q})\)的最小值,对\(g(\mathbf{q})\)\(q_i\)的偏导,并令其为0: \[ \ln\frac{\tilde{q}_i}{1-\tilde{q}_i} + \frac{\tilde{q}_i}{1-\tilde{q}_i}=a_i-1,i=1,\cdots,N \] 利用Lambert W函数,\(g(\tilde{\mathbf{q}})\)是唯一的 \[ \tilde{\mathbf{q}}_i=\frac{W(\exp(a_i-1))}{W(\exp(a_i-1))+1},i=1,\cdots,N \]\(g(\tilde{\mathbf{q}})>0\),无解,当\(g(\tilde{\mathbf{q}})=0\)\(\mathbf{q}^*=\tilde{\mathbf{q}}\),当\(g(\tilde{\mathbf{q}})<0\),则以下假设成立

假设2:存在\(\mathbf{q}\)使得\(g(\mathbf{q})<0\)

当以上假设成立时,约束函数\(g(\mathbf{q})\)满足Slater’s condition,而KKT条件提供了最优的充分必要条件。

又根据KKT条件有 \[ \begin{aligned} \nabla_{q_i}(\lambda^*D_iq_i^*c_i(q_i^*)-D_iq_i^*)=&0\\ \lambda^*(c_i(q_i^*)+q_i\nabla_{q_i}c_i(q_i^*))=&1\\ \lambda^*(c_i(q_i^*i)+q_i\nabla_{q_i}c_i(q_i^*))=&1\\ \lambda^*( -\frac{a_i}{b_i}-\frac{1}{b_i}[\ln(1-q_i^*)-\ln q_i^*] + q_i^* (-\frac{1}{b_i}[\frac{-1}{1-q_i^*}-\frac{1}{q_i^*}]) )=&1 \\ \lambda^*( -a_i+\ln\frac{q_i^*}{1-q_i^*} + q_i^* ([\frac{1}{1-q_i^*}+\frac{1}{q_i^*}]) )=&b_i \\ \lambda^*( -a_i+\ln\frac{q_i^*}{1-q_i^*} + \frac{1}{1-q_i^*} )=&b_i \\ \lambda^*( -a_i+\ln\frac{q_i^*}{1-q_i^*} + \frac{1-q_i^*+q_i^*}{1-q_i^*} )=&b_i \\ \lambda^*( 1-a_i+\ln\frac{q_i^*}{1-q_i^*} + \frac{q_i^*}{1-q_i^*} )=&b_i \\ \end{aligned} \] 因为\(b_i>0\),所以我们有\(\lambda^*\neq0\)

定义\(x_i:=\frac{q_i^*}{1-q_i^*}\),带入上式有 \[ \begin{aligned} \ln x_i+x_i=&a_i+\frac{b_i}{\lambda^*}-1\\ x_ie^{x_i}=&\exp(a_i+\frac{b_i}{\lambda^*}-1) \end{aligned} \] 因为等式右边恒大于0,有 \[ x_i=W(\exp(a_i+\frac{b_o}{\lambda^*}-1)) \] 其中\(W(\cdot)\)是Lambert W函数,所以 \[ q_i^*=\frac{x_i}{x_i+1}=\frac{W(\exp(a_i+\frac{b_o}{\lambda^*}-1))}{W(\exp(a_i+\frac{b_o}{\lambda^*}-1))+1} \] 因为\(\lambda^*\neq0\),根据KKT条件,我们有\(g(\mathbf{q}^*)=0\),所以最优性条件为 \[ \begin{aligned} g(\mathbf{q}^*)=&\sum^N_{i=1}D_iq_i^*c_i(q_i^*)-B=0\\ q_i^*=&\frac{W(\exp(a_i+\frac{b_o}{\lambda^*}-1))}{W(\exp(a_i+\frac{b_o}{\lambda^*}-1))+1}, i=1,\cdots,N\\ \lambda^*\geq&0 \end{aligned} \] 可以发现所有原始变量都可以被同一个对偶变量表示出来,定义 \[ q_i(\lambda):=\frac{W(\exp(a_i+\frac{b_o}{\lambda}-1))}{W(\exp(a_i+\frac{b_o}{\lambda}-1))+1},\lambda\in(0,+\infty),i=1,\cdots,N \]\[ \begin{aligned} f(\lambda):=&\sum^N_iD_iq_i(\lambda)\\ g(\lambda):=&g(\mathbf{q}(\lambda)),\lambda \in(0,+\infty) \end{aligned} \] 所以找到使得\(g(\lambda)=0\)的根\(\lambda^*\)就可以得到原问题的最优解\(\mathbf{q}^*=\mathbf{q}(\lambda^*)\)

通过分别对\(f(\lambda)\)\(g(\lambda)\)求导,可得两个函数的导数都是恒小于零,所以两个函数严格单调递减,所以可以通过二分法来找到最优解。

algo

总结

文章后面给出了几种扩展以及实验,实验先是利用模拟的数据和离线数据集做了验证,之后在淘票票上做了ab测试,roi有40%的提升。

本篇意在提出一个通用的预算分配的框架,同时为了解决数据分离的问题,引入了神经网络构造了半黑盒的预测模型,在之后优化阶段,通过一些比较好的性质,比如对bias parameter的性质假设,构造了高效、简单的求解算法,避免了预测阶段使用黑盒模型导致优化困难的问题。