在推荐系统中，多目标优化一直是热门话题，阿里巴巴的Xiao Lin、Hongjie Chen等人针对推荐中的多目标优化问题提出了一种基于帕累托效率的优化算法框架，并应用在电商推荐场景中，对GMV和CTR多个目标同时优化，线上实验效果好于LambdaMART以及基于强化学习的CXR-RL等算法。该论文已经被RecSys 2019 会议录用，本文是AI前线第94篇论文导读，我们将对这项研究工作进行详细解读。

介绍

推荐系统在电商平台中扮演着至关重要的角色，推荐算法（例如，Learning To Rank ）会为用户生成个性化的推荐列表，可以防止用户信息过载。通常，算法需要精心设计来满足多个目标。然而，同时优化多个目标非常困难，其核心难点在于不同目标之间经常存在冲突。在电商推荐中，点击率（CTR）和成交总额（GMV）是两个并不完全一致但都很重要的目标。为了验证这种不一致性，我们从一个真实的电商平台收集了一周的在线数据，并绘制了当CTR上升时GMV的变化趋势图。根据图1，CTR与GMV的趋势变化不完全一致，当CTR最优或GMV最优时，另一个目标可能是次优的，甚至是不好的。

因此，如果一个解被认为是两个目标的最优解，那么意味着其中一个目标在不伤害另一个目标的情况下很难进一步改进。这种最优性在多目标优化中得到了广泛的认可，被称为帕累托效率或帕累托最优性。在帕累托效率的情况下，只有当解A在所有目标上都优于解B时，解A才被认为优于解B。帕累托效率的目标是在不受其他目标支配的情况下找到最优解。

现有的帕累托优化方法分两类：启发式搜索和标量化。演化算法是启发式搜索方法中最热门的。然而，启发式搜索并不能保证帕累托有效性，它只能保证得到的解不被对方支配（但仍然可以被帕累托有效解支配）。与启发式搜索方法不同，标量化方法是通过目标函数的加权和将多目标问题转化为单目标问题。然后通过合适的标量，优化重构的目标函数来获得帕累托有效解。目标函数的标量化权重通常是手动确定的，因此帕累托有效性仍然无法保证。总而言之，现有的演化算法和标量化算法难以保证帕累托有效解。最近，Karush Kuhn Tucker（KKT）条件被证明可用于指导标量化。我们尝试在KKT条件下构建算法，并提出了一种新的算法框架，在理论保证的前提下，生产标量化的权重。

具体地说，我们提出了一个帕累托有效的算法框架“PE-LTR”，它用LTR过程优化多个目标。为了给每个用户生成候选的item，考虑到多目标，PE -LTR对候选item进行排序，使得这种排序是帕累托有效的。假设每一个目标都存在相应的可微公式，我们采用标量化技术将不同的目标协同成一个单目标函数。如前所述，除非仔细选择权重，否则标量化技术不能保证帕累托有效性。因此，我们提出了一个标量化权值的条件，保证该解是帕累托有效的。该条件等价于一个约束优化问题，并且我们提出了一个算法，它可以通过两步解决该问题。首先通过放宽约束来简化问题，从而得到解析解，然后通过实施投影过程（projection procedure）得到可行解。以PE-LTR为基础，依据服务提供者的需求，我们提供方法来生成帕累托边界（Pareto Frontier）和特定的推荐。为了生成帕累托边界，通过均匀设置目标标量权重的边界来运行“PE-LTR”算法框架。为了生成特定的推荐，可以使用适当的边界运行一次PE-LTR，或者首先生成帕累托边界，然后在特定的公平性度量下选择一个“合适”的解。

在本文中，应用该框架来优化电商推荐的两个重要目标，即GMV和CTR。对于电商平台，主要目标是提升GMV，但CTR需要做出很大的牺牲很大，从长远来看，会使平台的活跃用户（DAU）减少。因此，我们的目标是在同时考虑这两个目标的前提下，找到帕累托有效解。我们分别为GMV和CTR提出了两个可微分公式，并应用PE-LTR框架来生成帕累托最优解。我们在一个真实的电商推荐系统上进行了大量的实验，并将结果与最新的最佳的方法进行了比较。在线和离线实验结果都表明，我们的解优于其他基线，并且我们的解几乎是帕累托有效的。

这项工作的主要贡献是：

（1）我们提出了一个通用的帕累托有效性算法框架（PE-LTR）用于多目标推荐。该框架既不依赖于模型，也不依赖于目标，显示了其强大的可伸缩性。

（2）我们提出了一个two-step算法，它理论上保证了帕累托有效性。尽管该算法是建立在标量化技术之上的，但与其他的标量化方法相比，它的不同之处是有理论保证并且标量化权重是自动学习，而不是手动分配。

（3）以PE-LTR为基础，提出了如何生成帕累托边界和特定的推荐。具体地说，我们建议在使用适当的公平度量下从帕累托边界中选择一个合适的推荐。

（4）我们使用电商推荐作为PE-LTR的一个特例，并在一个真实的推荐系统上进行了广泛的在线和离线实验。结果表明，我们的算法优于其他最先进的方法，所产生的解是帕累托有效的。

（5）我们开源了一个大规模的电商推荐数据集EC-REC，其中包含展现、点击和购买的真实记录。据我们所知，没有一个公共数据集同时包含三个标签和足够多的特征，这个数据集可以用于进一步的研究。

提出的框架

在这一部分中，我们首先简要介绍帕累托有效性的概念，然后具体介绍所提出框架的细节，即帕累托有效学习排序（PE-LTR）。假定多个目标对应有不同的损失函数，首先我们提出一个能保证帕累托有效解的条件，证明了该条件等价于约束二次规划问题。然后，我们又提出了一个两步算法来解决该问题。此外，我们还提供了用PE-LTR生成帕累托边界和特定推荐的方法。

预备知识

首先，简要介绍帕累托有效性的相关概念。帕累托有效性是多目标优化的一个重要概念，即给定一个系统，该系统的目标是最小化一系列目标函数f1,…,fK，帕累托有效性是一种状态，在不损害其他多个目标的情况下，不可能再改善其中一个目标。

定义 3.1 两个解的结果表示为si=(fi1,…,fiK)和sj=(fj1,…,fjK)，仅在fi1≤fj1,fi2≤fj2,…fiK≤fjK（对于最小化目标）情况下，si支配sj。

帕累托效率的概念建立在支配的定义之上：

**定义3.2 ** 如果没有其他的解sj=(fj1,…,fjK)支配si，解si=(fi1,…,fiK)就是帕累托有效解。

因此，在不损害其他目标的情况下，一个解是非帕累托有效性解，它仍可以至少在一个目标上提升，并且在多目标优化中总是可以得到帕累托有效解。值得一提的是，帕累托有效解并不是唯一的，所有这些解的集合都被称为“帕累托边界”。

基于帕累托有效的学习排序算法

为了实现帕累托最优解，我们提出了一种利用标量化技术优化多目标的学习排序方案。假设在给定的推荐系统中存在k个目标，模型F(θ)需要同时优化这些目标，其中θ表示模型参数。在不失一般性的情况下，我们假设对于K个目标存在K个不同的损失函数。

给定公式，优化第i个目标等价于最小化Li(θ)。然而，同时优化这K目标是非常复杂的，因为对于一个目标的最优解通常对于另一个目标是次优的。因此，我们使用标量化技术将多个目标合并成单个目标。确切地说，我们利用ωi聚合损失函数：

其中，w1+w2+…+wK=1，wi≥0。在真实的场景下，目标可能有不同的优先级。在我们的案例中，我们假定约束被添加到目标中是预先定义的约束边界。例如，wi≥ci，其中ci是一个在0-1之间的常量，c1+c2+…ci+…+cK≤1。

尽管只有一个目标公式，除非分配适当的权重，否则不能保证问题的解是帕累托有效的。但是，我们得到的标量化权重的条件，可以确保解是帕累托有效的。

3.2.1 帕累托有效条件

为了得到多目标的帕累托有效解，我们试图最小化聚合损失函数。模型参数的KKT条件(Karush-Kuhn-Tucher条件)：

满足此条件的解称为帕累托平稳解。该条件可转化为以下优化问题：

已经证明该优化问题的解是0，使得满足KKT条件，或者解能指导梯度方向来最小化所有损失函数。如果满足KKT条件，则解是帕累托平稳的，并且在现实和温和条件下也能做到帕累托有效性。在此条件上，我们提出了一个算法框架PE-LTR，其细节在算法1中给出了说明。

该框架以均匀的标量加权开始，然后交替地更新模型参数和标量权重。PE-LTR的核心部分是PECsolver，它通过求解问题（1）中的条件来产生标量化权值。注意，该条件是一个复杂的二次规划问题，我们给出了在算法2中PECsolver的详细过程。

值得一提的是，算法框架不依赖于损失函数或模型结构的特定公式。任何带有梯度的模型和公式都可以很容易地应用到框架中。尽管算法在批处理中采用随机梯度下降法，但该算法为梯度下降的收敛提供了理论保证。

3.2.2 二次规划算法

将ωi^表示为ωi-ci，帕累托有效条件变为：

帕累托有效条件等价于问题1，然而，由于它的二次规划形式，解决这个问题并不是一个轻而易举的任务。因此，我们提出了一个两步算法，作为帕累托有效条件求解的工具。该算法在算法2中有详细说明。我们首先通过只考虑等式约束来松散问题，然后用解析解来解决松弛问题。然后，我们引入一个投影过程，从在所有约束下的可行解的集合中生成一个有效解。

当除了等式约束，忽略所有其他约束时：

松弛问题的解由定理3.3给出。

然而，因为省略了非负性约束，问题3的解ω*^可能是无效的。因此，我们执行以下投影步骤以获得有效的解。

这个问题是一个非负最小二乘问题，并且可以很容易地用有效集方法求解。由于篇幅的限制，我们省略了问题3算法的细节。算法2的复杂度主要由伪逆(pseudo-inverse)运算决定，它与目标数目有关。通常目标的数量是有限的，因此算法2的运行时间是可忽略不计的，在线实验也证实了这一点。

帕累托边界生成与解的选择

多目标优化可以用于寻找一个特定的帕累托解，或者被用来生成一组解来构造帕累托边界。在本节中，我们将介绍用算法1生成解的细节。

帕累托边界生成

在算法1中，给定不同目标的边界，我们可以得到帕累托最优解。然而，存在一些场景，我们期望有一系列的帕累托最优解存在，即帕累托边界。这对于算法框架来说很简单，我们将不同的值设置到各个目标的不同边界上执行算法1就可以得到。

为了得到帕累托边界，我们执行多次算法1，并且在每个运行中用适当的边界生成的解产生帕累托最优解。我们适当地选择边界，以便均匀分布的帕累托点可以生成一个好的均价分布近似的帕累托边界。

解的选择

在期望单个推荐的情况下，我们需要选择一个特定的帕累托最优解。当不同目标的优先级可用时，我们可以通过为目标设置适当的边界来获得适当的帕累托有效推荐并执行一次算法1。

当优先级不可用时，我们可以首先生成帕累托边界并选择一个对目标公平的解。无论是在经济学理论还是在推荐系统背景下，公平都有几种不同的定义。最直观的度量之一是 Least Misery，它集中在最“悲惨”的目标上，在我们的例子中，一个“Least Misery”的推荐是最小化目标损失函数的最大值：

另一个常用的度量是公平边际效用，即选择一个解，其中优化一个目标的成本几乎等于其他目标的收益：

给定一个生成的帕累托边界，方程5或者6的最小值的解，被选择作为最后的推荐，这取决于公平性的选择。

电商推荐的特殊性

在PE-LTR算法框架的基础上，我们详细介绍了其在电商推荐中的具体应用。电商推荐中最重要的两个目标是GMV和CTR。对于电商平台，GMV通常是首要目标。然而，CTR是评估用户体验的一个重要指标，长远来看影响平台的扩大。因此，我们的目标是考虑两个目标的前提下，找到一个推荐是帕累托最优的。

考虑到在现实环境中，LTR模型以流数据为输入，在线更新其参数。因此，在线的LTR模型通常遵循point-wise的排序方案。我们将问题描述为二元分类问题，并针对这两个目标分别设计两个不同的损失函数。

在电商推荐系统中，用户反馈可以大致分为三种类型：展现、点击和购买。假定表示一个实例为(xj,yj,zj),j∈ [1,…,N]，给定point-wise的排序模型F(θ)，我们提出优化这两个目标，即CTR和GMV。对于CTR优化，我们的目标是最小化：

对于GMV优化，我们的目标是最小化：

其中h（price(j)）是关于price(j)的凹单调非递减函数，price(j)表示xj中item的价格。在我们的公式中，我们选择h（price(j)）=log（price(j)）。我们假设p（zj＝1，yj＝1）与模型F(θ)参数无关。因此，给定一个模型F(θ)和Lctr（θ，x，y，z）和Lgmv（θ，x，y，z）的表达式，电商推荐问题变成：

注意，提出的框架不依赖于特定的模型结构或损失公式，只要模型有梯度，它就可以工作。因此，CTR和GMV损失的计算公式不是本文的重点，而更为精心设计的计算公式可以应用到这个框架中。

此外，我们没有关注特定的LTR模型，而是使用三种不同的典型模型进行比较，即LR、DNN和WDL。DNN模型是一个三层MLP，在wide&deep模型中具有与深部结构相同的结构。对于所有的神经网络组件，我们选择tanh作为每个隐藏层的激活函数，而最后一层采用线性函数作为输出。在实验5中对三种不同模型进行了比较。

实验

在本节中，我们将介绍实验的详细细节，旨在回答以下研究问题：

（1）与目前最先进的以CTR/GMV导向的方法和多目标推荐算法相比，该框架的性能如何？

（2）就单一推荐和帕累托边界而言，提出框架的帕累托效率如何？

（3）从模型选择的角度来看，提出框架的可伸缩性如何？

为了回答这些研究问题，我们在一个流行的电商网站上对真实世界的数据集进行了广泛的实验，包括在线和离线实验。

数据集

据我们所知，没有一个公开的电商数据集包含这些重要的特征，例如同一时间的价格、标签的展现、点击和购买。因此，我们从一个流行的电商平台收集了一个真实的数据集EC-REC 。由于在线数据量巨大，我们收集了一周的数据，并为离线实验采集了超过700万个展现样本，数据集将公开，以支持未来的研究。同时，利用PE-LTR为用户服务，我们对在线实验进行了A/B测试。这些特性来自于用户画像和item画像，例如用户的购买力和item的平均购买次数。

实验设置

我们进行了离线和在线实验来验证所提框架的有效性，并以最先进的方法作为比较的基准。

6.2.1 基线

我们选择最新的推荐方法进行比较，基线可以分为三类：典型方法（CF、LambdaMART）、以GMV导向的方法（LETORIF、MTL-REC）和优化两个目标的方法（CXR-RL、PO-EA）。

ItemCF 基于item的协同过滤。
LambdaMART 是最先进的学习排序方法。一个MART模型用于优化NDCG的loss。然而，LambdaMART只关注点击相关性，而购买不考虑。
LETORIF 是最大化GMV的学习排序方法，并采用price*CTR*CVR进行排序，其中CTR和CVR是两个单独的模型进行预测。
MTL-REC 采用多任务学习技术对CTR和CVR模型进行训练。两个模型共享相同的用户和item嵌入和类似的神经网络结构。排序模型也是price*CTR*CVR。
CXR-RL 是一种最近基于值感知的推荐算法，它同时优化了CTR和CVR。CXR设计为CTR和CVR的组合。CXR-RL使用强化学习技术来优化CXR，从而实现CTR和CVR之间的平衡。
PO-EA 是一种最先进的多目标推荐方法，旨在寻找帕累托有效的解。PO-EA假定不同的基础算法在目标上具有不同的优势。它用多个初等算法给出的分数，用演化算法生成权重。基础算法包括LETORIF-CTR、LETORIF、CXR-RL、PE-LTR-CTR和PE-LTR-GMV。LETORIF-CTR是指LETORIF中的CTR模型。PE-LTR-CTR和PE-LTR-GMV都是PE-LTR模型，在模型中加入边界约束，对CTR和GMV进行相应的优化。两个LTR模型被用作基础算法，以便与PE-LTR进行公平比较。
PO-EA-CTR ，PO-EA-GMV 由PO-EA生成的两个解决方案，分别针对CTR和GMV。
PE-LTR-CTR，PE-LTR-GMV 由PE-LTR生成的两个解决方案，分别针对CTR和GMV。

6.2.2 实验设置

我们采用了两种典型的IR测量方法来评估CTR，即NDCG和MAP。同时，我们为这两个指标提出了两种GMV变体：

其中Q®表示item购买集合，pay(i)=0/1表示在第i次rank中item是否被购买，price’(i)表示第i次rank中item的价格，G-IDCG@K表示G-DCG@K中最大的可能值。G-NDCG@K考虑了在排序列表中位置偏差的GMV，偏好高ranking的item被购买，而G-MAP考虑在推荐列表中购买数量。对于用户没有购买记录的，两个度量指标的值都是0。

离线实验结果

6.3.1 对比基准线

为了回答最初的研究问题，我们在表2中对NDCG、MAP和GMV相关度量进行了比较。

PE-LTR是从具有公平边际效用的帕累托边界选择模型，PO-EA是具有在CTR指标方面跟PE-LTR可比的模型。如表所示，PE-LTR在所有GMV相关指标上都优于其他方法，在CTR相关指标上也优于LambdaMART。与Item-CF和LambdaMART相比，PE-LTR可以获得更高的G-NDCG和G-MAP。这是合理的，因为PE-LTR联合优化了GMV和CTR，而GMV在Item-CF和LambdaMART中没有优化。同时，PE-LTR实现了与LambdaMART相当的NDCG和MAP。在对Web搜索基准中，LambdaMART通常是性能非常好的方法。这说明了我们的框架的有效性，它不仅优化了GMV，而且保证了高CTR。

与LETORIF、MTL-REC、CXR-RL和PO-EA相比，PE-LTR可以实现更高的G-NDCG和G-MAP，并且成本更低。这背后有几个原因：

首先，与LETORIF和MTL-REC相比，PE-LTR使用一个模型来联合学习两个目标，这允许模型同时学习点击和购买；而在LETORIF和MTL-REC中，两个单独的模型或组件被设计用于点击和购买，这可能导致一些不一致性。
其次，与CXR-RL和PO-EA相比，PE-LTR以帕累托有效的方式协调两个目标。CXR-RL优化了两个目标，但以非帕累托有效的方式。同时，虽然PO-EA试图用寻找帕累托有效解，但它只能保证最终解是从一系列互不支配的解中选择出来的。

在图2中，我们进一步绘制了PO-EA和PE-LTR的NDCG与G-NDCG曲线（由于篇幅限制，我们只在本文的图中绘制了G-NDCG和NDCG，结果与MAP和G-MAP相似）。如图表所示，PO-EA所产生的任何解都不受PO-EA中的另一个支配，并且情况与PE-LTR相同。然而，我们观察到PE-LTR的曲线高于PO-EA的曲线，这意味着PO-EA的解主要是由PE-LTR生成的解。注意两个PE-LTR算法已经被用作PO-EA的基本组成部分，比较表明，所提出的框架更能生成帕累托有效解。

此外，电商平台中的真实数据可能不遵循典型的假设。在PE-LTR中，标量权重在每个批次中调整，能够在训练过程中动态地调整训练数据。同时，PO-EA需要几个经过训练的算法来聚合，这使得它更难满足在线学习环境的要求。

我们进一步比较了排名第一的推荐的质量。由于用户通常更关注排名靠前的item，因此排名靠前的指标在推荐中更为重要，结果如图3所示。如图所示，PE-LTR在GMV相关指标上优于其他基线，且损失CTR较少。这说明了帕累托效率在现实推荐系统中的重要性。单独优化一个目标可能会严重损害其他目标。因此，有必要同时考虑多个目标，帕累托效率推荐使得以较低的损失CTR下实现高GMV成为可能。

6.3.2 PE-LTR的帕累托效率

为了回答第二个研究问题，我们首先通过运行算法1生成CTR和GMV损失的帕累托边界，并在图2中绘制帕累托边界。可以看出，在不同的约束条件下，损失基本上遵循帕累托效率，即没有一个点比其他点同时达到更低的CTR和GMV损失。当模型更关注CTR时，CTR损失较低，GMV损失较高，反之亦然。这与该框架的帕累托有效标量方案相吻合。

然后比较了不同选择策略下PE-LTR的解。我们预先定义了CTR和GMV的两组边界：（ω(ctr)≥0，omega(gmv)≥0.8）和（ω(ctr)≥0.8，omega(gmv)≥0.0），得到了两个分别聚焦于GMV和CTR的PE-LTR（PE-LTR-GMV和PE-LTR-CTR）。然后从帕累托边界选择两个具有LM公平和MU公平的PE-LTR(PE-LTR-LM和PE-LTR-MU)。我们在图4中绘制了这些PE-LTR之间的比较。

PE-LTR-CTR和PE-LTR-GMV与被添加到目标的约束性能是一致的。因此，当GMV和CTR的优先级可用时（即GMV或CTR优先），可以通过相应地设置边界来实现推荐。当优先级不可用时，可以通过从具有最高公平性的帕累托边界中进行选择来实现公平解决。尽管所选择的PE-LTR（PE-LTR-LM和PE-LTR-MU）在所有指标上都不是最好的，但它在两个目标之间实现了相对良好的权衡。将PE-LTR-LM与PE-LTR-MU进行比较，我们认为LM和MU公平性选择的两个推荐是相对平衡的。在GMV中，PE-LTR-MU优于PE-LTR-LM，而在CTR中，PE-LTR-LM稍好。

6.3.3 PE-LTR的可扩展性

为了回答第三个研究问题，我们进行了实验，从模型选择方面展示了可伸缩性。我们使用LR、DNN和WDL作为PE-LTR框架中的模型，模型的详细内容见第5节。我们为模型设置了相同的边界，结果如图5所示。

从结果来看，模型选择对PE-LTR的性能有重要影响。在三个PE-LTR变体中，PE-LTR-WDL优于其余的，PE-LTR-DNN优于PE-LTR-LR。这是因为神经网络能捕获比线性模型更复杂的特征之间的关系。Wide&Deep的模型将神经网络和线性模型结合到一个模型中，使推荐更好地泛化和记忆。因此，PE-LTR能够适应不同的模型，更强的模型可以带来更好的性能。这也说明了PE-LTR的潜力，其性能可以通过更精心设计的模型进一步提高。

在线实验结果

我们在真实的电商平台上进行了3天在线实验。在线实验中，仅考虑CTR的方法会严重伤害GMV。因此，只考虑CTR的方法不包括在在线实验中。

在线实验中我们关注四个度量指标，即CTR（点击率）、IPV（单个页面查看）、PAY（购买量）和GMV（成交总额）。我们计算了三天的平均性能，结果见表3。由于用户数量众多，结果具有统计上的显著性。我们使用LETORIF作为基线，并在表中给出比较方法在LETORIF上的提升。

从结果观察到，我们的方法在四个度量上优于其他基线。这与离线实验的结果基本吻合。请注意，PE-LTR在较高的CTR下实现了GMV的显著提升，这说明帕累托有效推荐的优势。同时，PO-EA要求离线模型来聚合需要，不能在线学习权重，使实验效果不好。

结论

本文研究的是推荐中多目标优化的问题。我们提出了一个通用的算法框架，在理论保证下生成帕累托有效解。同时，我们提出了一个保证帕累托有效性的理论条件和一个两步算法，它可以进一步适应目标约束。我们将该框架应用在电商推荐上同时优化GMV和CTR，并在一个真实的电商推荐系统上进行了大量的实验，实验结果验证了该框架的有效性。同时，该框架不依赖于模型和目标，显示了强大的可伸缩性。

论文原文链接：

https://dl.acm.org/citation.cfm?id=3346998

创作场景

阿里提出针对多目标优化的全新算法框架，同时提升电商推荐场景 GMV 和 CTR