一个短信决策问题

你是某 App 的运营人员，老板圈定了一批想要召回的用户，让你想办法触达。你文思泉涌，很快写出了一堆精彩的文案，想要通过短信发送给用户。老板说，年轻人不要那么豪横，咱们这次预算有限（只是这次吗？），不能全发短信，只能短信和 Push 搭配着来。所谓好钢要用在刀刃上，你好好考虑一下，哪些用户该发短信，哪些用户该发 Push。

等一下，先别着急拍规则，我是本厂的算命工程师，我有话要说！

决策模型

假设第 $i$ 个用户点击短信的概率为 $p_i^{sms}$，点击 Push 的概率为 $p_i^{push}$，给定的预算最多只能发送 $N$ 条短信。现在我们要决策是否给第 $i$ 个用户发送短信，用 $X_i$ 表示，具体来说，$X_i=1$ 表示给$i$ 个用户发送短信，$X_i=0$ 表示不给第 $i$ 个用户发送短信。此外，考虑到用户的疲劳度（和成本），一天最多只给同一个用户发送一条短信，但是可以给同一个用户发送多条 Push。假设平均给每个用户发送 $k$ 条 Push（发那么多难怪用户不看）。

对于没有收到短信、只收到 Push 的用户，其被召回的概率为 $1-(1-p_i^{push})^k$。根据二项式定理，

$(1+x)^k = \tbinom{k}{0}x^0 + \tbinom{k}{1}x^1 +\tbinom{k}{2}x^2 +\cdots+\tbinom{k}{k}x^k$

当 $x$ 很小时，忽略二阶小量，有

$(1+x)^k\approx1+kx$

故

$1-(1-p_i^{push})^k\approx 1- (1-kp_i^{push})=kp_i^{push}$

即只收到 Push 的用户被召回的概率约为 $kp_i^{push}$。

对于收到短信的用户，考虑两种策略：
① 只给这部分用户发送短信，不发送 Push，则其被召回的概率是 $p_i^{sms}$。
② 同时给这部分用户发送短信和 Push，则其被召回的概率是

$1-(1-p_i^{sms})(1-p_i^{push})^k\approx1-(1-p_i^{sms})(1-kp_i^{push})$

• 使用策略 ① 时，平均召回的用户数为

$\begin{aligned} recall &= \sum_ip_i^{sms}X_i+\sum_ikp_i^{push}(1-X_i)\\ &=\sum_i(p_i^{sms}-kp_i^{push})X_i+\sum_ikp_i^{push} \end{aligned}$

如果目标是最大化召回用户数，只需要将用户按照 $p_i^{sms}-kp_i^{push}$ 排序，给前 $N$ 个用户发送短信即可。如果目标是最大化 ROI，则可以求解一个简单的整数线性规划问题：

$max \frac{\sum_i(p_i^{sms}-kp_i^{push})X_i+\sum_ikp_i^{push}}{\sum_iX_i}\\ s.t. \quad\sum_iX_i\leq N$

• 使用策略 ② 时，平均召回的用户数为

$\begin{aligned} recall &= \sum_i\left[1-(1-p_i^{sms})(1-kp_i^{push})\right]X_i+\sum_ikp_i^{push}(1-X_i)\\ &=\sum_ip_i^{sms}(1-kp_i^{push})X_i+\sum_ikp_i^{push} \end{aligned}$

同样的，如果目标是最大化召回用户数，只需要将用户按照 $p_i^{sms}(1-kp_i^{push})$ 排序，给前 $N$ 个用户发送短信。如果目标是最大化 ROI，则只要求解：

$max \frac{\sum_ip_i^{sms}(1- kp_i^{push})X_i+\sum_ikp_i^{push}}{\sum_iX_i}\\ s.t. \quad\sum_iX_i\leq N$

尽管它是如此的简洁且优雅，但是由于我们并不知道短信和 Push 的点击概率，所以这个决策模型到目前为止并没有什么用。

等等，先别走，不知道没关系，我还可以预测啊，别忘了我可是算命工程师啊。下面以短信的点击概率为例，给大家算一卦。

预测模型

假设我们给一个用户发送过 $n$ 次短信，该用户点击了 $x$ 次，那么该用户点击短信的概率 $p$ 是多少呢？一个可能的做法是

$p\approx \frac{x}{n}$

这个方法看起来很自然，也有一定道理，因为根据频率学派对概率的定义，事件 A 在独立重复试验中发生的频率趋于极限 $p$，那么这个极限就是该事件的概率。

问题在于我们的数据非常稀疏，对大多数用户来说，$n$ 是一个很小的值。举例来说，有一个用户我们只给他发过 1 次短信，他点击了，我们能说这个用户点击短信的概率是 100% 吗？反之，如果他没有点击，我们能说这个用户点击短信的概率是 0 吗？答案是否定的。

让我们换一个思路，用贝叶斯学派的方法来解决这个问题。首先简单介绍一下贝叶斯推断。

我们想知道某个随机变量的取值。在观察到数据之前，我们根据经验，对该随机变量的取值为 $\theta$ 的可能性给出一个“信念” $P(\theta)$，称为先验概率（prior probability）。在观察到了一些数据 $data$ 之后，我们的“信念”更新为 $P(\theta|data)$，称为后验概率（posterior probability）。根据贝叶斯定理，有

$\begin{aligned} P(\theta|data) &= \frac{P(\theta)P(data|\theta)}{P(data)}\\ &=\frac{P(\theta)P(data|\theta)}{\int_0^1P(\theta)P(data|\theta)\mathrm d\theta} \end{aligned}$

其中 $P(data|\theta)$ 表示该随机变量的取值为 $\theta$ 的条件下，观察到数据 $data$ 的概率，称为似然（likelihood）。所谓贝叶斯推断，就是结合先验概率和观察到的数据来得到后验概率。而且贝叶斯推断可以迭代使用：在观察一些数据后得到的后验概率可以当作新的先验概率，再根据新的数据得到新的后验概率。

回到我们的问题。用户点击短信的概率本身也可以视作一个随机变量，我们想知道它的取值。为此，我们首先要给出它的取值为 $p$ 的先验概率 $P(p)$。这是一个概率的概率，是不是有点绕？我们假定它服从 Beta 分布，即

$P(p)=Beta(p|\alpha,\beta)=\frac{1}{\mathrm B(\alpha,\beta)}p^{\alpha-1}(1-p)^{\beta-1}$

其中归一化因子

$\mathrm B(\alpha, \beta)=\int_0^1p^{\alpha-1}(1-p)^{\beta-1}\mathrm dp$

为 $\mathrm B$ 函数。

已知用户点击短信的概率为 $p$ 的条件下，观察到“用户点击了 $n$ 条短信中的 $x$ 条”的概率可以用二项分布来刻画，即似然为

$P(x|p) = Binomial(x|n,p)= \frac{\Gamma(n+1)}{\Gamma(x+1)\Gamma(n-x+1)}p^x(1-p)^{n-x}$

有了先验概率和似然函数，我们可以得到后验概率

$\begin{aligned} P(p|x) &= \frac{P(p)P(x|p)}{P(x)}\\ &=\frac{Beta(p|\alpha, \beta)Binomial(x|n,p)}{\int_0^1Beta(p|\alpha, \beta)Binomial(x|n,p)\mathrm dp}\\ &= \frac{\frac{1}{\mathrm B(\alpha,\beta)}p^{\alpha-1}(1-p)^{\beta-1}\cdot\frac{\Gamma(n+1)}{\Gamma(x+1)\Gamma(n-x+1)}p^x(1-p)^{n-x}}{\int_0^1\frac{1}{\mathrm B(\alpha,\beta)}p^{\alpha-1}(1-p)^{\beta-1}\cdot\frac{\Gamma(n+1)}{\Gamma(x+1)\Gamma(n-x+1)}p^x(1-p)^{n-x}\mathrm dp}\\ &=\frac{p^{\alpha+x-1}(1-p)^{\beta+n-x-1}}{\int_0^1p^{\alpha+x-1}(1-p)^{\beta+n-x-1}\mathrm dp}\\ &=\frac{1}{\mathrm B(\alpha+x, \beta+n-x)}p^{\alpha+x-1}(1-p)^{\beta+n-x-1}\\ &\equiv Beta(p|\alpha+x, \beta+n-x) \end{aligned}$

有意思的是，后验分布和先验分布一样，都是 Beta 分布。这是因为 Beta 分布是二项分布的共轭先验。这一特性使得我们可以非常方便地计算后验概率。

我们可以计算所有用户历史平均点击短信次数 $\bar\alpha$ 和平均未点击短信次数 $\bar\beta$，据此确定用户短信点击概率的先验分布 $Beta(\bar\alpha,\bar\beta)$。第 $i$ 个用户历史点击短信次数为 $\alpha_i$，未点击短信次数为 $\beta_i$，故其短信点击概率的后验分布为 $Beta(\bar\alpha+\alpha_i,\bar\beta+\beta_i)$。我们可以使用后验分布的期望 $\dfrac{\bar\alpha+\alpha_i}{\bar\alpha+\alpha_i+\bar\beta+\beta_i}$ 作为第 $i$ 个用户短信点击概率的预测值。我们也可以从后验分布中随机采样出一个样本作为预测值，这样做的好处是可以让那些点击率没那么高的用户也有一定的可能性被选中发送短信。