发表在 Operations Research, 2022. DOI: https://doi.org/10.1287/opre.2021.2158.
Subject Classifications: Buyer behavior, Choice models, Computational complexity
Area of Review: OR Practice
Keywords: choice models; product assortment; machine learning; field experiment; retail operations
这篇文章记录了阿里巴巴算法团队在 2018 年针对商品推荐的两种方法 machine learning VS customer choice models 的过程和结果。
Product-Display Problem
天猫的一次活动中，店铺会给予新人顾客一个红包，然后指定六件商品，红包只能用在这六件商品中。天猫当然希望用户有更高的购买率和购买金额，所以算法团队的任务就是找出六件商品推荐给用户。
用 $\mathcal{N} = \{1, 2, \dots, n\}$ 表示商品集，一般一家电商店铺的 SKU 在 $100-2000$ 之间。
推荐算法的核心可以看成是一个优化问题（assortment optimization）： $$ \max _{S \subseteq \mathcal{N}:|S|=6} \sum_{j \in S} r_{j} \cdot P_{j t} $$ $P_{jt}$ 是顾客 $t$ 购买商品 $j$ 的概率，$r_j$ 是商品的利润。$\mathcal{N}$ 表示全体商品，优化的目标是找到一个子集 $S$，使得期望利润最大。
这个问题最重要的一步就是计算 $P_{jt}$ （estimation）。
阿里巴巴团队在过去一直使用的是一套复杂的机器学习算法来估计 $P_{jt}$，在 2018 年 3 月的为期两周的实验中，阿里团队比较了机器学习方法和 multinomial logit (MNL) model 的效果，并发现 MNL 方法能给平台带来显著更高的收益。
Our field experiments revealed that the MNL-based approach generated 5.17 renminbi (RMB) per customer visit, compared with the 4.04 RMB per customer visit generated by the machine-learning-based approach when both approaches were given access to the same set of the 25 most important features.
The Estimation Problem
在机器学习方法中，预测 $P_{jt}$ 主要用的是产品特征（价格、评价、浏览次数）、顾客特征（历史消费行为、人口统计信息）。团队提取出了其中最重要的 25 个特征。
阿里团队使用历史数据来训练机器学习模型和MNL模型。数据由历史的顾客对于六个商品的点击和购买行为组成，顾客数量为 $\tau$，$c_{jt}, z_{jt} \in \{0, 1\}$ 分别表示是否点击和购买。数据可以表示为 $\mathcal{PH}_{ML} = \{ (\mathbf{X_{jt}}, c_{jt}, z_{jt}): 1 \leq t \leq T, T=6\tau,\; j \in S_t \}$，$S_t$ 是当时展示的商品，$\mathbf{X_{jt}}$ 是商品的特征。
由于模型保密原因，文章没有过多透露机器学习方法是怎样实践的。它一共分为两步，第一步是训练模型 $f(\mathbf{X_{jt}})$ 预测 $\mathbb{P}(c_{jt} = 1)$，第二部是训练模型 $g(\mathbf{X_{jt}})$ 预测 $\mathbb{P}\left(z_{i t}=1 \mid c_{i t}=1\right)$，最后顾客的购买概率就是 $\mathbb{P}_{jt} (\mathbf{X_{jt}}) = f(\mathbf{X_{jt}}) \cdot g(\mathbf{X_{jt}})$ .这样的模型可以通过逻辑回归、梯度提升树等方法来得到。
MNL Choice Model 更加简单，它就是一个参数模型： $$ P_{j t}\left(S_{t}, X_{t}\right)=\mathbb{P}\left[U_{j t}=\max _{i \in S_{t}} U_{i t}\right]=\frac{e^{\beta^{T} X_{j t}}}{1+\sum_{i \in S_{t}} e^{\beta^{T} X_{j t}}} $$ 这里，训练数据是 $\mathcal{PH}_{MNL} = \{(S_t, \mathbf{X_{jt}}, z_t): t = 1, \dots, \tau\}$ 。文章用极大似然法来估计 $\mathbf{\beta}$： $$ \max _{\beta}\; \mathcal{L} \mathcal{L}\left(\boldsymbol{\beta} ; \mathcal{P} \mathcal{H}_{M N L}\right)=\sum_{t=1}^{\tau}\left(\boldsymbol{\beta}^{T} X_{z_{t} t}-\log \left(1+\sum_{j \in S_{t}} e^{\boldsymbol{\beta}^{T} \mathbf{X}_{\mathbf{j t}}}\right)\right) $$ 目标函数是凹的，因此是一个凸优化问题。$\tau$ 在两千万到三千万之间，阿里团队选择使用 TensorFlow 用随机梯度下降法来解。
The Assortment Problem
机器学习方法的 assortment 非常简单，挑选使得 $r_j \cdot P(\mathbf{X_{jt}})$ 最大的六种商品即可。
MNL 的 assortment 是： $$ Z_{O P T}=\max _{\mathbf{y} \in \mathcal{F}} R(\mathbf{y}) =\sum_{j \in N} P_{j}(\mathbf{y}) \cdot r_{j}=\frac{\sum_{j \in \mathcal{N}} r_{j} v_{j} \mathbf{y}_{j}}{1+\sum_{i \in \mathcal{N}} v_{i} \mathbf{y}_{i}} $$ 其中 $\mathcal{F}=\left\{\mathbf{y} \in\{0,1\}^{n}: \sum_{j=1}^{n} \mathbf{y}_{j}=6\right\}$ .
文章在前文的基础上给出了一个 $O(n^2)$ 的算法。
Extension
Joint pricing and assortment
如果价格有 $m$ 种选择，那么可行集是 $$ \begin{gathered} \mathcal{F}_{1}=\left\{\mathbf{y} \in\{0,1\}^{m \times n}: \sum_{j=1}^{m} \mathbf{y}_{i j} \leq 1 \;\;\forall i \in N\right\} \\ \cap \left\{\mathbf{y} \in\{0,1\}^{m \times n}: \sum_{i=1}^{n} \sum_{j=1}^{m} \mathbf{y}_{i j}=6\right\} \end{gathered} $$ 问题变成了： $$ \max _{\mathbf{y} \in \mathcal{F}_{1}} R(\mathbf{y})=\max _{\mathbf{y} \in \mathcal{F}_{1}} \frac{\sum_{i=1}^{n} \sum_{j=1}^{m} r_{i} v_{i j} \mathbf{y}_{i j}}{1+\sum_{i=1}^{n} \sum_{j=1}^{m} v_{i j} \mathbf{y}_{i j}} $$ 文章还给出了一种转变为线性规划求解上述问题的方法。
Icon display size
如果商品图标的大小是可变的。假定一定大小的 icon 对顾客的购买行为有影响。
Experiment Design and Data & Main Results
这一部分文章叙述了实验的设计过程并从统计学的角度说明了实验的有效性。
在第一周的实验里，团队对比了一下三种方法：
- The MNL-based approach (MNL approach) 使用 top25 特征的MNL
- The same-feature-ML-based approach (SF-ML approach) 使用 top25 特征的机器学习
- The all-feature-ML-based approach (AF-ML approach) 使用全部特征的机器学习
实验的数据量在百万量级。三组的人数分别是：1,879,903、1,879,598、1,876,940。
实验结果的统计数据如下图示：
Panel A 显示了三组顾客的统计信息，t-test 显示两组顾客并没有显著的差异。
Panel B 显示了三种方法的效果
Financial Performance
总的来说，MNL比SF-ML表现好，跟AF-ML方法不分伯仲。
Purchase-Probability Accuracy
就用户购买的准确率来说，MNL方法显著差于机器学习方法。
We ascribe the superior financial performance of the MNL approach to its ability to produce six-product displays that ultimately lead to higher revenue products being purchased.
Average Purchase Price
上表展示了 MNL 方法能产生更高的利润和购买率。
Hence, although the SF-ML approach produces more accurate estimates of the purchase probabilities, it is not able to offer assortments that are as desirable or as profitable as those offered by the MNL approach.
Weakness of the MNL-Based Approach
- MNL 只假定了顾客购买一件商品，但实际上顾客可能购买多件商品。
- 不能通过顾客的点击来推断顾客的偏好。
附：
GMV（全称Gross Merchandise Volume），即商品交易总额，是成交总额（一定时间段内）的意思。
电商平台给出的计算指标是：GMV=销售额+取消订单金额+拒收订单金额+退货订单金额。
GMV不是实际的购买交易数据，但是可以用GMV来研究顾客的购买意向，顾客买了之后发生退单的比率，GMV与实际成交额的比率等等。
Appendix C. 说明了实验没有带来长期的负面效应
Appendix D. 用全部的特征比较了 MNL 和 ML，这是一个在2018年9月的实验。
实验显示全量特征的 MNL 方法比全量特征的 ML 方法能带来更高的顾客购买额。