出处：美团技术团队
作者： 瑞玉、文斌、杨林、懋地(美团外卖技术团队)
本文从技术层面介绍外卖套餐搭配的技术方案，包括离线、实时的套餐搭配的迭代，套餐质量评估方案，同时会介绍套餐搭配的业务应用.
因与服装搭配、推荐等相关，这里学习、记录备忘.
1. 背景
让用户更方便快捷地选购到满意的外卖商品，是美团外卖一直在努力的方向.
本文主要介绍了针对美食类商家的套餐搭配技术以及应用实践.
在外卖点餐的选择过程中，用户一般会考虑单品偏好、组合搭配等因素，挑选商家和商品的过程耗时较长. 我们通过套餐搭配技术，基于商家的候选商品，自动搭配优质套餐，轻松解决用户“选择困难症”，能够提升用户的决策效率.
2. 业务目标和挑战
2.1. 业务目标
目前，美团外卖App的套餐搭配应用有很多，有“今日套餐推荐”、“满减神器”、“套餐搭配推荐”等. 由于目前外卖商家自行搭配套餐的能力较弱而且意愿不强，导致外卖套餐底层供给对业务场景和商家的覆盖率偏低，不能满足套餐相关推荐排序应用的需求. 因此，外卖套餐搭配的业务目标是对于美食类商家搭配出候选的套餐组合，给套餐相关应用方提供更丰富的套餐供给.
图：“套餐推荐” 、“满减神器套餐推荐”、“菜品详情页套餐搭配”应用示例
对于套餐相关应用方，我们进行了业务分析：“今日推荐”、“满减神器”等业务的搭配条件相对较弱且可以离线获取搭配条件，归类为推荐型相关业务，此类业务需要保证商家的套餐覆盖率提升，从而保证商家的推荐露出. 详情页、满减加购等业务的搭配条件较强，而且偏实时.
例如，详情页是用户指定一个菜品后进行搭配，满减加购场景是用户选择一个菜品和特定的价格区间作为条件. 这些属于搭配型业务，此类业务需要保证套餐对实时场景的覆盖，从而保证套餐搭配Tab的露出. 套餐搭配算法的目标有：①提升套餐组合的覆盖度，从而给下游的套餐相关应用提供场景覆盖率高、多样性充足的套餐组合. ②保证搭配套餐的质量.
2.2. 业务挑战
商品搭配在电商场景下也存在较多的应用，例如淘宝的购物车搭配、服装搭配，化妆品搭配.
购物车搭配是基于用户购物车、已购买商品的打包推荐，例如，用户在加购牙刷后，可以给出牙膏的推荐. 这类方法主要基于商品的购买行为进行相关性的推荐，目标不是形成一个完成的搭配组合. 但是，外卖美食商品搭配则需要考虑整个组合的合理性，而不单纯基于商品是否相关. 比如：大量订单中有“小炒肉+番茄鸡蛋汤+米饭”、“鱼香肉丝+番茄鸡蛋汤+米饭”等组合方式，但是“番茄鸡蛋汤+米饭”并不构成一个好的套餐搭配.
服装搭配和化妆品搭配为面向组合的搭配推荐，对此类搭配问题的解决方案大体分成两类，一类是：搭配模式用于模型挑选商品过程的剪枝，搭配模式可以是人工或者模型的方式先验给出，参考文献中的论文4、5采用此思路，该方法的特点是搭配效果靠剪枝策略+质量评估模型共同保证. 另一类是通过端到端的网络参数学习搭配模式思路，论文6和我们的离线套餐搭配采用此思路，该方案的特点是搭配效果更依赖于端到端模型保证，但同时搭配模型更复杂.
相比电商场景的商品搭配，美食搭配面临独特的业务挑战：
[1] - 套餐搭配的业务场景和搭配条件比较多样，因此套餐搭配方案需要满足各类业务、各种搭配条件下的需求.
[2] - 美食商品属于非标品，且不同商家销售的商品各不相同，导致套餐搭配模式因商家而异. 例如，不同商家销售的宫保鸡丁，在份量、口味、食材、价格上都不相同，因此对于宫保鸡丁这道菜也会有不同的套餐搭配方式.
[3] - 算法搭配不可避免会产生低质量的搭配结果，而商品的非标品属性，导致我们更难衡量美食搭配的质量. 低质量的搭配可能包括：a.包含不适宜单独销售、非美食品类的搭配，例如包含赠品、锅具、餐具的搭配. b.搭配结果不符合常规搭配模式，例如两份饮料，饮料+馒头等.
为此，我们的解决方案是：
[1] - 为了解决业务场景和搭配条件多样的问题，我们形成了离线、实时结合的算法搭配框架. 对于推荐型相关业务，我们采用离线搭配方法预先搭配出套餐候选，再在业务场景中做个性化排序. 离线搭配本着规则到模型的迭代思路，规则搭配依赖知识图谱的商品表示，通过高频聚合+规则搭配泛化，产出相对高质量套餐以确保头部商家覆盖. 模型搭配可以在保证搭配质量的同时，通过模型泛化提高套餐的场景覆盖率. 对于实时搭配型的业务，算法会依据业务的搭配条件实时搭配套餐，进一步提升各个实时场景下的套餐的覆盖率.
[2] - 为了解决美食商品非标品的问题，我们引入外卖美食图谱对菜品进行了多方位的刻画. 我们基于外卖知识图谱提取了菜品丰富的信息表征，例如菜品的标准菜品、菜品品类、口味、食材、做法等，减弱非标品带来的影响.
[3] - 为了保证搭配套餐的质量，我们开发了套餐质量评估的模型.
总体来说，我们在非标品的商品表示、商家表示、套餐搭配模型、套餐搭配质量评估上都进行了相关的探索和迭代，形成了如图2所示的套餐搭配框架.
图. 套餐搭配框架
3. 套餐搭配模型
3.1. 基于图谱标签归纳的套餐搭配模型
我们面临的一个问题是外卖商品为非标品，菜品数据质量较差、属性缺失. 为此，我们基于商家菜单、菜谱、商品描述等多种信息源，通过信息抽取、关系识别、知识融合等多种方法，构建了以美食为核心的知识图谱，对菜品建立了品类、口味、做法、功效等多个维度的表示.
图: 外卖美食知识图谱
商家的历史高销量套餐一般可认为是优质的套餐，但是，中低销量商家的高销量套餐数量较少，难以支持套餐的个性化推荐等应用. 依赖美食图谱对菜品的语义表达，我们首先尝试了基于知识图谱的直接归纳演绎进行套餐搭配的方案. 例如，通过高频订单可以归纳得出，{热菜}+{米饭}+{汤}是一个常见的套餐搭配方式，进而对于商家演绎出“番茄炒鸡蛋+番茄鸡蛋汤+米饭”的套餐搭配.
图谱归纳演绎的过程是高频聚合和基于搭配模板的泛化过程，我们通过订单聚合、同品牌、同标签、同菜品模板泛化，来产生高质量的套餐搭配，同时套餐的商家覆盖率有了显著的提升. 但是搭配模板的问题在于较难对搭配质量和泛化程度取得折中. 约束性较强的搭配模板可以确保搭配质量，但泛化能力不足，套餐覆盖度较低. 如果用单一或少量标签描述搭配项，会导致模式过度泛化，准确率不能保证. 为此，我们引入了基于模型的套餐搭配方法.
3.2. 基于Encoder-Decoder的套餐搭配模型
用户搭配套餐也是一个信息编码到信息输出的过程：用户浏览商家菜单即是编码过程，得到该商家和商品信息的一个整体概况，再基于这个概况去进行套餐的搭配. 贴合该过程的一个思路是采用Encoder-Decoder框架进行套餐搭配模型的建设，Encoder类比用户浏览菜单的过程，学习菜单的语义信息，Decoder负责搭配出套餐. Encoder-Decoder是一种深度学习网络框架，已经被广泛应用于文本摘要、机器翻译、对话生成等应用中，其建模的方式是通过编码（特征提取）和解码（目标拟合），学习从Encoder输入数据到Decoder输出数据的映射. 常见的编码方式有CNN、RNN、Transformer等结构，解码方式也类似.
3.2.1. 基于LSTM的套餐搭配模型
套餐生成问题是要从一个商家的所有候选商品集合中提取出多个商品子集，形成方便用户筛选、可直接下单的套餐. 套餐生成的数据源主要是该商家的候选商品信息（如商品的名称、标签、价格、销量等），再结合用餐价格区间、用餐人数等约束条件，以及用户偏好等信息.
最初我们采用了LSTM作为Encoder和Decoder的神经网络进行套餐搭配. 我们基于图谱语义抽取商品语义表示，并输入Encoder的RNN模型. Encoder编码过程类似于用户翻阅商家候选商品的过程，Encoder端输入菜品名称、菜品标签、菜品的业务属性（价格、销量等），通过LSTM对非标品菜品进行特征抽取. 如下图4所示，每个商品的名称经过Embedding层、CNN+Pooling层提取特征，并同菜品标签、类别的Embedding以及价格和销量等连续特征进行拼接，最终作为Encoder RNN中每步的输入.
图. Encoder网络结构
Decoder在解码过程中一般依赖一个固定的字典或词典作为候选集，每一步输出候选集中的字、词被选中的概率分布. 对于套餐搭配网络来说，Decoder解码的候选集来源于Encoder输入端商家内的商品列表，而非固定维度的外部菜品词表，Pointer Network是建模这一问题的有效架构. Pointer Network是基于Seq2seq的扩展，主要解决的是候选集不固定的问题，这一模型架构已被成功应用于抽取式文本摘要，以及旅行商问题、凸包问题等组合优化问题的解决方案中.
套餐搭配解码的具体过程为，Decoder每一步预估目标菜品来自菜品列表的概率分布. 在第n（n>=1）步时，这个概率分布向量表达了在已经选择了n-1个商品的情况下，某个商品或者终止位被选中的概率. 若终止位对应的概率较大，则模型倾向以前n-1个已选商品形成一个完整的套餐搭配. 解码过程中，我们结合BeamSearch算法产生TopN个结果，保证搭配的多样性.
图. Encoder-Decoder网络结构
3.2.2. 套餐搭配模型的优化
[1] - 套餐搭配模型的学习目标
为了解决菜品搭配模式因商家而异的问题，模型通过拟合该商家的历史订单来学习商家的搭配特性. 一种较为主流的训练形式是基于商家真实订单，采用Teacher Forcing的形式进行训练，使得模型预测的菜品逐位匹配上真实订单内的菜品. Teacher Forcing式的训练方法使得预测菜品的概率倾向于0-1分布，但是现实的菜品搭配通常是个性化、多样性的，例如在Decoder已经输出“宫保鸡丁”菜品的基础上，下一步选择的主食为“米饭”或者“炒饭”皆可.
为此，我们对商家历史成单的套餐搭配模式进行统计，计算出商品选择的概率分布，Decoder以此商品选择的概率分布作为训练目标，同预估的分布计算MSE Loss，并最小化该值指导模型的训练. Teacher Forcing的另一个问题是较难引入搭配质量、套餐的点击购买行为等外部知识来指导模型训练，为此我们尝试了采用强化学习的思路进行改进. 在解码过程的时刻T，我们通过蒙特卡洛算法采样（Monte Carlo Sampling）出完整的套餐候选，并计算套餐候选的搭配质量分作为Reward，结合MSE Loss和搭配质量分进行模型训练.
[2] - 套餐搭配的约束
套餐搭配过程会面临多种业务约束，例如，对于“满减神器”来说，搭配的套餐需要满足给定的满减价格档位. “智能助手”的套餐搭配过程需要考虑用户选定的筛选条件，例如条件可能为“主食为米饭”且“价格为30元以下”. 我们通过剪枝策略保证搭配过程满足约束，以“满减神器”的价格区间约束为例，Decoder端在单步产生候选菜品时，会基于剩余的价格过滤掉超出剩余价格范围的菜品.
如下图6所示，对于商家的A、B、C、D、E菜品，Decoder会利用剩余价格的区间“15元以内”对后一轮菜品A、B、C、D、E进行剪枝，并删除超过价格区间的C、D两个菜品.
图. 套餐搭配价格约束
[3] - 基于Attention网络的套餐搭配模型
基于LSTM网络的商家内菜品特征提取面临的问题有：第一，商家菜单的菜品本身无序，而RNN网络依赖序列进行建模. 第二，菜品之间可能存在长距离的语义依赖，例如，菜单内是否有“米饭”、“馒头”等菜品会影响对于“宫保鸡丁”菜品的搭配.
为了更好的对无序菜单和菜品之间依赖信息进行表征，我们尝试了基于Attention结构的Encoder-Decoder模型. Encoder部分采用层次化Attention结构提取菜品的语义信息，包含底层单菜品级的Attention和菜品之间的Attention两部分. 对于单菜品级的Attention，我们在字维度采用Multi-Head Attention结构得到菜品名称的语义向量，菜品标签同样采用Multi-Head Attention 得到菜品标签语义向量，对于菜品的交易属性，我们采用多层全连接网络提取交易特征的语义向量.
最后，菜品名称语义向量、菜品标签语义向量、交易特征语义向量拼接后经过全连接层+层归一化得到菜品语义向量. 对于菜品之间的Attention层，我们对该店的菜品语义向量列表采用多层Multi-Head Attention得到该店的菜单级别语义向量. 模型Decoder部分同样采用Multi-Head Attention进行解码，输入信息包括用户偏好信息、历史时刻的解码输入、价格约束等上下文信息，模型在每步输出商家菜单中的菜品被选择的概率分布. Decoder过程中我们对用户偏好信息同商家菜单级别的语义向量进行Multi-Head Attention，在套餐搭配过程中考虑用户的用餐偏好.
图. 基于Attention的套餐搭配网络
3.2.3. 套餐搭配模型分析
我们认为商家高质量的搭配可以从订单的销量体现，一种评估方法即是评估模型输出的套餐对商家真实高销量套餐的覆盖. 通过离线和在线评估，我们发现该模型可以拟合出商家高销量套餐. 在人工评估部分，我们把算法搭配的套餐和真实成单订单进行混合并让人工进行区分，发现人工无法分辨模型搭配的订单和真实成单订单的差异. 同时，该模型具备良好的泛化能力，显著提升了套餐对商家和特定业务场景的覆盖度.
我们对模型输出的菜品表征向量进行了分析，以了解模型的套餐搭配模式. 利用TSNE对向量进行降维和聚类，通过聚类图观察发现“主食”、“主菜”、“小食”类的菜品各自聚集在一起，可以看出模型识别了菜品的“主食”、“菜品”、"小食"等品类语义属性，并参考此语义进行套餐搭配.
3.3. 实时套餐搭配模型
利用离线搭配产生套餐候选的方案可以满足推荐型业务的需求，但对于一些搭配型的业务场景仍然覆盖不足，例如，目前离线套餐对菜品的覆盖度较低，即对于菜品详情页等应用只保证部分PV的搭配模块露出.
一种解决方案是通过离线搭配提升套餐对美食商品的覆盖，但该方案的存储成本较高，为此我们采用实时套餐搭配方案. 实时生成方案的难点在于既要保证套餐质量，又要满足各种搭配条件，最重要的还要保证实时性. 最初我们把离线搭配模型应用于线上实时搭配，发现在性能方面存在瓶颈. 因此，我们对离线模型进行了精简，精简的思路是将选菜的过程精简为选择菜品类目的过程，将菜品维度的搭配关系精简为菜品类目的搭配关系，实现整个解空间的缩小. 如下图8所示，具体流程如下：
[1] - 搭配模板挖掘：通过商家历史订单挖掘出商家高销的类目层面的搭配关系，即搭配模板，例如“热菜+主食”.
[2] - 搜索剪枝：在搭配选菜时，依据搭配模板中的菜品类目，进行菜品的选择. 例如上述的例子，首先进行“热菜”的选择，然后进行“主食”的选择. 在选择的过程中，根据用户的实时需求，例如指定必选菜、指定价格、指定主食类型等约束条件，对整体的选择过程进行剪枝.
[3] - 筛选评估：在搭配完成后，对得到的候选搭配结果进行质量评估，这里基于性能考虑，使用树模型进行质量评估，筛选出Top N的搭配结果.
图. 实时套餐搭配和离线套餐搭配
4. 套餐质量评估
高销量的订单中也存在搭配质量稍低的套餐，加上模型泛化的精度问题，搭配模型很容易生成质量较差的搭配组合. 如下图9右侧，模型生成的后两个套餐搭配相对不是特别合理. 为进一步保证用户体验，我们建立了套餐搭配质量模型，对套餐的质量进行统一评估. 套餐质量分类模型将套餐搭配质量转化为一个分类问题. 因为套餐组合是有多个菜品组成的，所以我们基于菜品名称、标签等信息构造菜品的表示，然后通过Global-Attention来实现菜品间重要程度的考量，同时添加总商品个数、总份数等全局特征来表示整体搭配的信息，模型结构具体见下图9所示：
图. 套餐质量分类
我们对套餐的搭配质量进行了细粒度的分档：极差、差、中、好 ，且四种类别存在有序关系（极差<差<中<好），对应模型有四个输出值，每一个表示该位为1的概率，例如“极差”表示为“1,0,0,0”, “差”表示为“1,1,0,0”，“中”表示为“1,1,1,0”，“好”表示为“1,1,1,1”. 模型的损失采用Pair Hinge Loss函数，避免前面节点为0后面节点为1的情况，保证模型的准确度. 套餐的搭配质量分值为四个输出节点的求和平均值，使得预测值更加可信. 模型结构同一般的分类模型大体一致，目标函数如下：
套餐质量模型的建设过程中，负例样本主要来自用户反馈的Bad Case，和通过人工构造不合理搭配模式版筛出的套餐. 这种方式存在的问题是：Bad Case和人工构造的搭配负样本有偏、多样性较差，且负样本同正样本的配比不容易调节.
为此，我们引入一个预训练任务学习历史订单的搭配模式，为套餐搭配质量模型引入更多的搭配先验知识. 预训练过程如下图11所示，我们随机Mask已成单搭配组合中的一个菜品，然后训练Transformer模型还原被Mask掉的菜品.
图. 套餐质量分类
在这个过程中，考虑一些次优套餐的合理性（例如："宫保鸡丁+米饭+可乐"，Mask掉"宫爆鸡丁"，生成器生成出来的是“鱼香肉丝”，“鱼香肉丝+米饭+可乐”就可理解为一个次优套餐），我们在最后的损失函数添加预测菜品与目标菜品类别相似性的判别器来解决这类情况. 预训练得到的参数最终用来初始化套餐搭配质量分档模型，并基于少量的人工标注语料进行模型的调优.
5. 套餐搭配的应用和未来展望
目前，外卖已打造了多款以套餐为核心供给的产品，“今日套餐推荐”帮助用户解决不知道吃什么、选购慢的问题，店铺页内的“满减神器”、“单品搭配推荐”解决用户凑单难、搭配难的问题. 为了解决了各业务场景下套餐搭配难题，套餐搭配算法针对覆盖度、搭配质量、搭配多样性进行了持续优化，为业务提供了重要的技术和数据支撑. 离线套餐搭配用于”满减神器“、”今日套餐推荐“等业务，显著提高了套餐商家的覆盖率，实时套餐搭配用于“菜品详情页套餐搭配”等业务，并取得较好的业务收益.
后续工作，一方面我们会继续优化菜品知识图谱的构建，完善对非标品菜品的刻画，通过引入图像等多模态数据进一步提升数据准确度和覆盖度，通过构建场景知识图谱更好地刻画用户需求和供给.
另一方面我们会探索场景化的套餐搭配：目前我们在场景化套餐搭配方面的工作较少，而且用户在不同场景下会有不同的套餐需求，例如天气寒冷偏爱吃火锅类套餐、腊八节吃粥类套餐，在异地希望吃当地特色类套餐. 接下来，我们会在场景化套餐搭配方面进行探索，针对节气、节日、人群等场景搭配套餐，更好的满足用户个性化、场景化的用餐需求.
图：套餐搭配相关应用
参考文献
[1] Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. "Pointer networks." Advances in neural information processing systems. 2015.
[2] See, Abigail, Peter J. Liu, and Christopher D. Manning. "Get to the point: Summarization with pointer-generator networks." arXiv preprint arXiv:1704.04368 (2017).
[3] Gong, Jingjing, et al. "End-to-end neural sentence ordering using pointer network." arXiv preprint arXiv:1611.04953 (2016).
[4] Han, Xintong, et al. "Learning fashion compatibility with bidirectional lstms." Proceedings of the 25th ACM international conference on Multimedia. 2017.
[5] Alashkar, Taleb, et al. "Examples-Rules Guided Deep Neural Network for Makeup Recommendation." AAAI. 2017.
[6] Chen, Wen, et al. "Pog: Personalized outfit generation for fashion recommendation at alibaba ifashion." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.
[7] Rush, Alexander M., Sumit Chopra, and Jason Weston. "A neural attention model for abstractive sentence summarization." arXiv preprint arXiv:1509.00685 (2015).
[8] Paulus, Romain, Caiming Xiong, and Richard Socher. "A deep reinforced model for abstractive summarization." arXiv preprint arXiv:1705.04304 (2017).
[9] See, Abigail, Peter J. Liu, and Christopher D. Manning. "Get to the point: Summarization with pointer-generator networks." arXiv preprint arXiv:1704.04368 (2017).