科学地花钱：基于端智能的在线红包分配方案

一、前言

本文是作者在1688进行新人红包发放的技术方案总结，基于该技术方案的论文《Spending Money Wisely: Online Electronic Coupon Allocation based on Real-Time User Intent Detection》已经被CIKM2020接收，欢迎交流指正！

关于作者

李良伟：阿里巴巴算法工程师，邮箱 leon.llw@alibaba-inc.com 孙刘诚: 阿里巴巴高级算法工程师，邮箱 liucheng.slc@alibaba-inc.com

二、背景介绍

用户权益（包括现金红包、优惠券、店铺券、元宝等，图-1）是电商平台常用的用户运营手段，能够帮助平台促活促转化。 围绕着权益的技术优化也层出不穷[1,2,3,4,5]。

图-1: 1688新人红包

红包发放作为一种营销手段，其ROI是我们非常关心的一个指标，因为它直接反映了在有限的预算内红包为整个平台促活促成交的能力。优化红包发放的ROI要求我们把红包发到最合适的用户手上。而判断哪些用户适合领到红包需要我们在真正发红包之前判断当前用户的意图。举例来讲，一个购买意图非常明确、无论是否有红包都会下单的用户显然不适合领到红包；相反，红包对一个犹豫不决、货比三家的用户很有可能起到“临门一脚”的作用。

随着1688业务的快速发展，每天都会有大量的平台新用户涌入，其中有很多用户在整个阿里经济体的数据都十分稀疏，基于常规手段，我们很难对这种“陌生”的用户进行精准刻画。然而，只要一个用户进入了APP，或多或少都会和平台产生相互作用（滑动，点击等），这种在端上实时产生的数据能够帮助我们对用户尤其是新用户的实时意图进行精准捕捉，进而完成红包发放的决策。

本文将介绍我们基于端智能的用户意图识别和智能权益发放方案。

三、技术方案

从数学的角度，权益发放是一个带约束的优化问题。优化目标是关心的业务指标（GMV，买家数，转化率等），约束一般是预算约束，有时也会有其他约束比如发放疲劳度约束、单个用户领取红包金额约束等。

按照之前提到的先识别用户意图再进行权益发放这一思路，我们提出了一个two-stage的求解方案。在第一阶段，我们基于端智能技术[6]，根据用户实时行为数据，通过瞬时意图识别网络(Instantaneous Intent Detection Network, IIDN) 识别出用户当前意图；在第二阶段，我们将优化问题建模成一个多选项背包问题(Multiple-Choice Knapsack Problem, MCKP),并运用[7]提到的primal-dual框架求解。在这里，我们强调我们关于IIDN的两个创新点：

1.IIDN最主要检测的用户意图是下单意图，但是实践发现在新人当中，用户下单的比例是比较小的，这样我们在进行下单意图识别的时候会面临一个类别不均衡的问题(下单:不下单 = 1:10甚至更低)，这样的类别偏差会降低常见的分类器的分类效果[8]。为了解决这一问题，受到ESMM[11]和seq2seq[10]启发，我们引入了一个辅助任务：停留意图识别。我们随后会从理论上验证这一做法

2.我们采用encoder-decoder的结构，灵活地处理序列化的输入和输出

第一阶段：瞬时意图识别

图-2: IIDN结构

图-2是IIDN的整体结构,它由Embedding Layer, LSTM layer, Attention Layer, Encoder和Decoder五部分组成。接下来分别介绍。

Embedding Layer

模型的输入主要是实时用户特征和红包特征，用户特征包括实时特征（端上收集到的：点击、加购等）、历史特征（用户核身、年龄等），红包特征现在只加入了面额。这些特征是高度异质的，需要进行一步处理把它们映射到相同的向量空间中。我们采用[9]提到的嵌套技术，把原始的异质特征映射为长度固定的向量，并把该向量作为后续结构的输入。

LSTM Layer

我们红包发放的业务逻辑是：用户在详情页产生浏览行为并返回landing page的时候触发决策模型，判断给该用户发放红包的面额（0元代表不发放）。由于用户通常会产生一系列的详情页浏览行为，因此我们收集到的数据也是高度序列化的。为了更好地描述序列化数据当中的时间依赖关系，我们在特征抽取环节采用了Long Short Term Memory (LSTM) 来捕捉这种序列化信息。

Attention Layer

对于LSTM产出的序列化的feature map，我们使用注意力机制抽取当中的局部和全局依赖关系。我们将LSTM每层的输出都通过Attention计算权重并参与最终的结果计算。这样的好处是模型不仅关注LSTM最终层输出，还会关注逐层的输出结果，从而增加模型对于输入信息的感知能力。

Encoder

由于用户实时特征的序列长度不固定，而红包特征和用户历史特征是静态的固定特征，我们需要一种机制来进行有效的特征融合。受到Natural Language Generation (NLG) 当中语句生成的启发，我们采用一种seq2seq的结构：包括encoder和decoder，我们将在下一小节介绍decoder。这里encoder将之前产生的所有feature map作为输入，通过全连接层产生一个固定长度的向量，这个向量囊括了进行用户意图识别的一切信息，并作为之后decoder进行意图识别的依据。

Decoder

Decoder被用来输出最终的意图识别结果。在最开始，我们的模型只输出用户下单的概率，但是随着业务的深入，我们发现类别不均衡这一问题给结果预测造成了不小的干扰。在提高预测精度的实践当中，我们发现了一个有趣的现象：如果在进行下单率预估的时候在特征中加入用户在这次浏览之后是否离开这一信息，预测精度会有很大的提升。这引发了我们的思考：用户离开和用户下单之间存在什么样的关系。随后我们又做了一个实验：进行用户离开意图识别，并在特征中加入了用户两小时内是否下单这一特征。实验结果表明加入是否下单这一特征并不能给离开率预估的任务带来增益。这样的实验结果其实是符合逻辑的：用户能够下单的前提是用户一定要留在APP内不离开，前者的发生在逻辑上需要依赖后者的发生，因此在进行下单率预估的时候加入是否离开能够为模型提供一定的信息增益；相反，用户是否离开更多取决于用户当前的心态以及APP能否很好地承接他，用户是否下单并不能影响用户是否离开。我们可以认为：

由上式可以很自然地推导出下式：

可以看到，在进行下单率预估的时候（P的计算），用户停留意图识别（S的计算，或者说离开意图，二者等价）将可以用来作为辅助任务提升预测效果。我们的实验也验证了这点。

尽管在我们这一任务当中，我们只需要预测停留意图和下单意图，但是在之后扩展的场景中，更多意图也可以被识别：比如用户去往搜索的意图，用户去往新人专区的意图等。所有意图其实都像下单意图和停留意图一样存在一个逻辑上的先后关系（至少所有意图的产生都依赖于用户不离开），这样的关系使得我们想到了机器翻译当中语句生成：后一个单词的生成依赖于前一个单词的预测，这启发了我们在encoder-decoder的基础上采用seq2seq的思想：decoder会先生成S，并在此之上生成P。这样做有两个好处：

1.在一定程度上缓解了我们一开始提到类别不均衡问题：尽管不是所有用户都下单，但是所有用户一定会离开APP，离开意图识别并不存在类别不均衡的问题

2.我们这一套意图识别框架可以扩展到无限多的意图识别当中，只要提供先验的逻辑先后关系

我们使用普通的RNN完成每一个意图的识别。

loss设计

全局的loss是由停留意图识别和下单意图识别两个任务的loss相加得到：

其中CE表示交叉熵：

第二阶段：求解MCKP

根据第一阶段得到的实时意图$P$和$S$，我们在这一阶段完成红包的最终发放。我们将这一问题建模成一个多选项背包问题，我们作以下定义：

1.j用来索引红包，表示第j个红包，i用来索引用户，表示第i个用户
2.c_j表示第$j$个红包的面额
3.x_{ij} = 1当且仅当第i个用户被发到了j红包
4.\gamma 表示用户停留兴趣阈值，我们只给那些停留意图足够低的用户发红包，停留意图如果不够低我们认为他还会继续浏览，因此这次先不发放红包
5.P_{ij}、S_{ij}分别表示第$i$个用户领取到第$j$个红包以后的下单率和停留率
6.B表示全局预算约束

运用以上的定义，红包发放问题可以被写作：对于任意的用户，满足S_{ij}