排序学习

引言信息流是目前大众点评除搜索之外的第二大用户获取信息的入口，以优质内容来辅助用户消费决策并引导发现品质生活。整个大众点评信息流（下文简称点评信息流）围绕个性化推荐去连接用户和信息，把更好的内容推荐给需要的用户。信息流推荐系统涉及内容挖掘、召回、精排、重排、创意等多层机制和排序。本文主要围绕创意部分的工作展开，并选取其中重要的文本创意优化做介绍，分为三个部分：第一部分阐述几个重点问题，包括创意优化是什么，为什么做，以及挑战在哪里；第二部分讲述领域内的应用及技术进展；第三部分介绍我们创意优化的实践，最后做个总结。什么是创意优化创意是一个宽泛的概念，它作为一种信息载体对受众展现，可以是文本、图像、视频等任何单一或多类间的组合，如新闻的标题就是经典的创意载体。而创意优化，作为一种方法，指在原有基础上进一步挖掘和激活资源组合方式进而提升资源的价值。在互联网领域产品中，往往表现为通过优化创意载体来提升技术指标、业务目标的过程，在信息流中落地重点包括三个方向：文本创意：在文本方面，既包括了面向内容的摘要标题、排版改写等，也包括面向商户的推荐文案及内容化聚合页。它们都广泛地应用了文本表示和文本生成等技术，也是本文的主要方向。图像创意：图像方面涉及到首图或首帧的优选、图像的动态裁剪，以及图像的二次生成等。其他创意：包括多类展示理由（如社交关系等）、元素创意在内的额外补充信息。核心目标与推荐问题相似，提升包括点击率、转化率在内的通用指标，同时需要兼顾考量产品的阅读体验包括内容的导向性等。关于“阅读体验”的部分，这里不作展开。为什么要做文本生成首先文本创意本身为重要的业务发展赋能。在互联网下半场，大众点评平台（下称点评平台）通过内容化去提升用户停留时长，各类分发内容类型在不停地增加，通过优化创意来提升内容的受众价值是必由之路。其次，目前很多内容类型还主要依赖运营维护，运营内容天然存在覆盖少、成本高的问题，无法完全承接需要内容化改造的场景。最后，近几年深度学习在NLP（Natural Language Processing，自然语言处理）的不同子领域均取得了重大突破。更重要的是，点评平台历经多年，积淀了大量可用的内容数据。从技术层面来说，我们也有能力提供系统化的文本创意生成的解决方案。对此，我们从文本创意面向对象的角度定义了两类应用形态，分别是面向内容的摘要标题，以及面向商户的推荐文案与内容化聚合页。前者主要应用信息流各主要内容场景，后者则主要应用在信息流广告等内容化场景。这里提前做下产品的简单介绍，帮助大家建立一个立体化的感知。摘要标题：顾名思义，就是针对某条分发内容生成摘要作标题展示。点评内容源非常多样，但超过95%内容并没有原生标题，同时原生标题质量和多样性等差异也极大。商户文案：生成有关单个商户核心卖点的描述，一般形式为一句话的短文案。内容聚合：生成完整的内容页包括标题及多条文案的短篇推荐理由，不同于单商户文案的是，既需要考虑商户的相关性，又要保证理由的多样性。最后需要明确的是，我们做文本创意优化最大的初心，是希望通过创意这个载体显式地连接用户、商户和内容。我们能够知道用户关注什么，知道哪些内容说什么，如何引导用户看，知道哪些商户好、好在哪里，将信息的推荐更进一步。而非为了生成而生成。面临的挑战文本创意优化，在业务和技术上分别面临着不同的挑战。首先业务侧，启动创意优化需要两个基础前提：第一，衔接好创意优化与业务目标，因为并不是所有的创意都能优化，也不是所有创意优化都能带来预期的业务价值，方向不对则易蹚坑。第二，创意优化转化为最优化问题，有一定的Gap。其不同于很多分类排序问题，本身相对主观，所谓“一千个人眼中有一千个哈姆雷特”，创意优化能不能达到预期的业务目标，这个转化非常关键。其次，在技术层面，业界不同的应用都面临不一样的挑战，并且尝试和实践对应的解决方案。对文本创意生成来说，我们面临的最大的挑战包括以下三点：带受限的生成 生成一段流畅的文本并非难事，关键在于根据不同的场景和目标能控制它说什么、怎么说。这是目前挑战相对较大的一类问题，在我们的应用场景中都面临这个挑战。业务导向 生成能够提升业务指标、贴合业务目标的内容。为此，对内容源、内容表示与建模上提出了更高的要求。高效稳定 这里有两层含义，第一层是高效，即模型训练预测的效果和效率；第二层是稳定，线上系统应用，需要具备很高的准确率和一套完善的质量提升方案。2. 文本生成问题综述我们整体的技术方案演进，可以视作近两年NLP领域在深度学习推动下发展的一个缩影。所以在展开之前，先谈一谈整个领域的应用及技术进展。2.1 相关领域应用在学界相关领域，文本生成被称为NLG，其相关任务目标是根据输入数据生成自然语言的文本。而我们在NLP领域使用更多的一般是NLU（Nature Language Understanding 自然语言理解）类任务，如文本分类、命名实体识别等，NLU的目标则是将自然语言文本转化成结构化数据。NLU和NLG两者表向上是一对相反的过程，但其实是紧密相连的，甚至目前很多NLU的任务都受到了生成式模型中表示方法的启发，它们更多只在最终任务上有所区别。文本生成也是一个较宽泛的概念，如下图所示，广义上只要输出是自然语言文本的各类任务都属于这个范畴。但从不同的输入端可以划分出多种领域应用，从应用相对成熟的连接人和语言的NMT（神经机器翻译），到2019年初，能续写短篇故事的GPT2都属于Text2Text任务。给定结构化数据比如某些信息事件，来生成文本比如赛事新闻的属于Data2Text类任务，我们的商户文案也属此类。另外还有Image2Text等，这块也逐渐在出现一些具有一定可用性又让人眼前一亮的应用，比如各种形式的看图说话。2.2 相关技术与进展文本生成包含文本表示和文本生成两个关键的部分，它们既可以独立建模，也可以通过框架完成端到端的训练。文本生成文本生成要解决的一个关键问题，是根据给定的信息如何生成一段文本句子。这是一个简单输入复杂输出的任务，问题的复杂度太大，至今在准确和泛化上都没有兼顾的非常好的方法。2014年提出的Seq2Seq Model，是解决这类问题一个非常通用的思路，本质是将输入句子或其中的词Token做Embedding后，输入循环神经网络中作为源句的表示，这一部分称为Encoder；另一部分生成端在每一个位置同样通过循环神经网络，循环输出对应的Token，这一部分称为Decoder。通过两个循环神经网络连接Encoder和Decoder，可以将两个平行表示连接起来。另外一个非常重要的，就是Attention机制，其本质思想是获取两端的某种权重关系，即在Decoder端生成的词和Encoder端的某些信息更相关。它也同样可以处理多模态的问题，比如Image2Text任务，通过CNN等将图片做一个关键特征的向量表示，将这个表示输出到类似的Decoder中去解码输出文本，视频语音等也使用同样的方式（如下图所示）。可见Encoder-Decoder是一个非常通用的框架，它同样深入应用到了文本生成的三种主流方法，分别是规划式、抽取式和生成式，下面看下这几类方法各自的优劣势：规划式：根据结构化的信息，通过语法规则、树形规则等方式规划生成进文本中，可以抽象为三个阶段。宏观规划解决“说什么内容”，微观规划解决“怎么说”，包括语法句子粒度的规划，以及最后的表层优化对结果进行微调。其优势是控制力极强、准确率较高，特别适合新闻播报等模版化场景。而劣势是很难做到端到端的优化，损失信息上限也不高。抽取式：顾名思义，在原文信息中抽取一部分作为输出。可以通过编码端的表征在解码端转化为多种不同的分类任务，来实现端到端的优化。其优势在于：能降低复杂度，较好控制与原文的相关性。而劣势在于：容易受原文的束缚，泛化能力不强。生成式：通过编码端的表征，在解码端完成序列生成的任务，可以实现完全的端到端优化，可以完成多模态的任务。其在泛化能力上具有压倒性优势，但劣势是控制难度极大，建模复杂度也很高。目前的主流的评估方法主要基于数据和人工评测。基于数据可以从不同角度衡量和训练目标文本的相近程度，如基于N-Gram匹配的BLUE和ROUGE等，基于字符编辑距离（Edit Distance）等，以及基于内容Coverage率的Jarcard距离等。基于数据的评测，在机器翻译等有明确标注的场景下具有很大的意义，这也是机器翻译领域最先有所突破的重要原因。但对于我们创意优化的场景来说，意义并不大，我们更重要的是优化业务目标，多以线上的实际效果为导向，并辅以人工评测。另外，值得一提的是，近两年也逐渐涌现了很多利用GAN（Generative Adversarial Networks，生成对抗网络）的相关方法，来解决文本生成泛化性多样性的问题。有不少思路非常有趣，也值得尝试，只是GAN对于NLP的文本生成这类离散输出任务在效果评测指标层面，与传统的Seq2Seq模型还存在一定的差距，可视为一类具有潜力的技术方向。文本表示前文提到，在Encoder端包括有些模型在Decoder端都需要对句子进行建模，那如何设计一个比较好的模型做表示，既可以让终端任务完成分类、序列生成，也可以做语义推理、相似度匹配等等，就是非常重要的一个部分。那在表示方面，整个2018年有两方面非常重要的工作进展：Contextual Embedding：该方向包括一系列工作，如最佳论文Elmo(Embeddings from Language Models)，OpenAI的GPT(Generative Pre-Training)，以及谷歌大力出奇迹的BERT(Bidirectional Encoder Representations from Transformers)。解决的核心问题，是如何利用大量的没标注的文本数据学到一个预训练的模型，并通过通过这个模型辅助在不同的有标注任务上更好地完成目标。传统NLP任务深度模型，往往并不能通过持续增加深度来获取效果的提升，但是在表示层面增加深度，却往往可以对句子做更好的表征，它的核心思想是利用Embedding来表征上下文的的信息。但是这个想法可以通过很多种方式来实现，比如ELMo，通过双向的LSTM拼接后，可以同时得到含上下文信息的Embedding。而Transformer则在Encoder和Decoder两端，都将Attention机制都应用到了极致，通过序列间全位置的直连，可以高效叠加多层（12层），来完成句子的表征。这类方法可以将不同的终端任务做一个统一的表示，大大简化了建模抽象的复杂度。我们的表示也经历了从RNN到拥抱Attention的过程。Tree-Based Embedding：另外一个流派则是通过树形结构进行建模，包括很多方式如传统的语法树，在语法结构上做Tree Base的RNN，用根结点的Embedding即可作为上下文的表征。Tree本身可以通过构造的方式，也可以通过学习的方式（比如强化学习）来进行构建。最终Task效果，既和树的结构（包括深度）有关，也受“表示”学习的能力影响，调优难度比较大。在我们的场景中，人工评测效果并不是很好，仍有很大继续探索的空间。3. 探索与实践该部分介绍从2017年底至今，我们基于文本生成来进行文本创意优化的一些探索和实践。3.1 内容源启动文本生成，首先要了解内容本身，数据的数量和质量对我们的任务重要性无须赘述，这是一切模型的基础。目前我们使用到的数据和大致方法包括：平台渠道：用户评价、用户笔记、Push、攻略、视频内容、榜单、团单等等。第三方渠道：合作获取了很多第三方平台的内容来补缺，同时运营侧辅助创意撰写和标注了大量内容，他们同样贡献了可观的数据量。标注数据：最稀缺的永远是标注数据，尤其是符合业务目标的标注。为此，我们在冷启动阶段设计了E&E（Explore and Exploit，探索与利用）机制，有意识地积累线上标注，同时尽量引入更多第三方的标注源。但这些内容的不同特点，也带来了不同的挑战：内容多样：前面提到的这些内容的结构化程度各不相同，长短差异也极大，对内容表示提出了很高的要求。质量不一：源内容非常丰富，但事实上质量、质感远远没有达到理想的标准。尤其是占绝对大头的UGC的内容，不做好两端的质控将极大影响业务目标的优化，甚至会造成体验问题。聚焦商户：平台99%以上的内容，都以商户作为核心载体，这个对商户的理解和表示同样提出了很高的要求，尤其是在内容化升级的场景下。场景差异：不同的场景、不同的应用，对模型能力的侧重和优化目标不一样。比如内容和商户，前者要求要有很高的准确率，同时保证优化线上效果；后者更多的是要求有较强的泛化性，并对质感进行优化。3.2 基础能力模块所以，文本创意优化要在业务侧落地产生效果，还需应用到NLP领域诸多方向的技术。下图是抽象的整个文本生成应用的基础能力模块，包括用于源和端质量控制的文本质量层，构建Context表示的文本表示层，以及面向业务优化的端到端模型层，其中很多技术应用了公司其他兄弟团队包括内容挖掘组、NLP中心、离线计算组的出色成果。如针对负面内容过滤的情感分析，多项针对性的文本分类，针对商户表示的标签挖掘等，在这里特别向他们表示感谢。3.3 信息流标题实践双平台的内容需要在信息流分发，在创意上最先优化的就是标题，这是用户仅能看到两个要素之一（另一个为首图），而我们超过95%的内容并没有原生标题，同时原生标题也存在诸如多样性差非场景导向等问题，还有二次优化的空间。但是，有两点比较大的挑战，在不同任务上具象可能不一样。它们的本质并没有改变，部分也是业界难点：1. 两个受限条件：第一，需要以线上点击率转化率为优化目标，线上没效果，写的再好意义都不大；第二，需要与原文强相关，并且容错空间极小，一出现就是Case。2. 优化评估困难：第一，模型目标和业务目标间存在天然Gap；第二，标注数据极度稀缺，离线训练和线上实际预测样本数量之间，往往差距百倍。对此，我们通过抽取式和生成式的相结合互补的方式，并在流程和模型结构上着手进行解决。抽取式标题抽取式方法在用户内容上有比较明显的优势：首先控制力极强，对源内容相关性好，改变用户行文较少，也不容易造成体验问题，可以直接在句子级别做端到端优化。对此，我们把整个标题建模转变为一个中短文本分类的问题，但也无法规避上文提到两个大挑战，具体表现在：在优化评估上，首先标题创意衡量的主观性很强，线上Feeds的标注数据也易受到其他因素的影响，比如推荐排序本身；其次，训练预测数据量差异造成OOV问题非常突出，分类任务叠加噪音效果提升非常困难。对此，我们重点在语义＋词级的方向上来对点击/转化率做建模，同时辅以线上E&E选优的机制来持续获取标注对，并提升在线自动纠错的能力。在受限上，抽取式虽然能直接在Seq级别对业务目标做优化，但有时候也须兼顾阅读体验，否则会形成一些“标题党”，亦或造成与原文相关性差的问题。对此，我们抽象了预处理和质量模型，来通用化处理文本创意内容的质控，独立了一个召回模块负责体验保障。并在模型结构上来对原文做独立表示，后又引入了Topic Feature Context来做针对性控制。整个抽取式的流程，可以抽象为四个环节+一个在线机制：源数据在内容中台完成可分发分析后，针对具体内容，进行系统化插件式的预处理，包括分句拼句、繁简转换、大小写归一等，并进行依存分析。而后将所有可选内容作质量评估，包括情感过滤、敏感过滤等通用过滤，以及规则判别等涉及表情、冗余字符处理与语法改写的二次基础优化。在召回模块中，通过实体识别+TF-IDF打分等方式来评估候选内容标题基础信息质量，并通过阈值召回来保证基础阅读体验，从而避免一些极端的Bad Case。最后，针对候选标题直接做句子级别的点击/转化率预估，负责质感、相关性及最终的业务目标的优化。为此，我们先后尝试了诸多模型结构来解决不同问题，下面重点在这方面做下介绍。我们第一版Bi-LSTM＋Attention整个结构并不复杂。我们的输入层是PreTrain的Word Embedding，经过双向LSTM给到Attention层，Dropout后全连接，套一个交叉熵的Sigmod，输出判别，但它的意义非常明显，既可以对整句序列做双向语义的建模，同时可以通过注意力矩阵来对词级进行加权。这个在线上来看，无论是对体感还是点击转化率都较召回打分的原始版本，有了巨大提升。而后，我们还在这个Base模型基础上，尝试添加过ELMo的Loss，在模型的第一层双向LSTM进行基于ELMo Loss的Pre Train作为初始化结果，在线上指标也有小幅的提升。但是上述这个结构，将中短文本脱离原文独立建模，显然无法更好地兼顾原文受限这个条件。一个表现，就是容易出现“标题党”、原文不相关等对体验造成影响的问题。对此，我们在原文与候选标题结合的表示建模方面，做了不少探索，其中以CNN+Bi-LSTM+Attention的基模型为代表，但其在相关性建模受原文本身长度的影响较大，而且训练效率也不理想。经过一段时间的探索分析，在原文受限问题上，最终既通过深度模型来表征深层的语义，也辅以更多的特征工程，如属性、Topic等挖掘特征我们统称为Context，来表征用户能感知到的浅层信息，“两条腿走路”才能被更好的学习，这个在文案生成和标题生成的探索中反过来为抽取式提供了借鉴。在效率上，我们整体替换了RNN-LSTM的循环结构，采用了谷歌那时新提出的自注意力的机制，来解决原文表征训练效率和长依赖问题。采用这个结构在效果和效率上又有了较大的提升。主要问题是，我们的Context信息如何更好地建模到Self-Attention的结构中。它与生成式模型结构非常类似，在下文生成式部分有所介绍。另外，需要说明的一点是，除非有两个点以上的巨大提升，一般我们并不会以离线评测指标来评价模型好坏。因为前面提到，我们的标注数据存在不同程度的扰动，而且只是线上预测很小的一个子集，无法避免的与线上存在一定的Gap，所以我们更关注的是模型影响的基础体验（人工检测通过率即非Bad Case率），效率表现（训练预测的时效）最重要的还是线上实际的业务效果。在我们这几个版本的迭代中，这三个方面都分别获得了不同程度的优化，尤其是包括点击率、总点击量等在内的业务指标，都累计获得了10%以上的提升。受限生成式标题抽取式标题在包括业务指标和基础体验上都获取了不错的效果，但仍有明显的瓶颈。第一，没有完全脱离原文，尤其在大量质量欠优内容下无法实现创意的二次优化；第二，更好的通过创意这个载体显式的连接用户、商户和内容，这个是生成式标题可以有能力实现的，也是必由之路。生成式标题，可以抽象描述为：在给定上文并在一定受限条件下，预估下个词的概率的问题。在信息流标题场景，抽取式会面临的问题生成式全部会继承，且在受限优化上面临更大的挑战：原文受限，首先只有表示并学习到原文的语义意图才能更好的控制标题生成，这个本身在NLU就是难点，在生成式中就更为突出；其次，标注数据稀缺，原文＋标题对的数据极少，而大部分又存在于长文章。为了保证控制和泛化性，我们初期将标题剥离原文独立建模，通过Context衔接，这样能引入更多的非标数据，并在逐步完成积累的情况下，才开始尝试做原文的深度语义表示。优化评估，受限生成式对训练语料的数量和质量要求高很多，首先要保证基础的语义学习也要保证生成端的质量；其次，生成式本质作为语言模型无法在句子层面对业务目标直接做优化，这中间还存在一道Gap。在表示上，前面已经提到，我们经历过目标单独建模和结合原文建模的过程，主要原因还是在于仅针对Target的理解去构建Context衔接，非常容易出现原文相关性问题。所以我们在描述的泛化性方向也做了不少的尝试，比如尽可能地描述广而泛主题。诸如“魔都是轻易俘获人心的聚餐胜地”，因为只面向上海的商户，内容符合聚餐主题，泛化能力很强，但仍然不能作为一个普适的方案解决问题。下图为我们一个有初步成效的RNN-Base的Seq2Seq模型的整体结构。Encoder端使用的是，包括前面提到的主题（包括商户信息）表示以及原文的双向语义表示，两部分的拼接构成的Context，输出给注意力层。Decoder端生成文本时，通过注意力机制学习主题和原文表示的权重关系，这个结构也完整应用到了文案生成，其中控制结构会在文案中展开介绍。在序列建模上，我们经历了一个从RNN到自注意力的过程。简单介绍下，序列建模一个核心要点是如何建模序列间的长依赖关系。影响它的重要因素是，信号在网络正向和反向计算中传递的长度（也就是计算次数），较长的依赖关系消失越严重。而在自注意力结构中，每一层都直接与前一层的所有位置直接连接，因此依赖长度均为O(1)，最大程度保留了序列间的依赖关系。可以看到，Encoder包括两部分，一部分是Source原文，一部分是基于原文和商户理解的主题Context，两者共同组成。为此，我们借鉴了NMT的一部分研究思想，调整了Transformer的结构，在原结构上额外引入了Context Encoder，并且在Encoder和Decoder端加入了Context的Attention层，来强化模型捕捉Context信息的能力。我们在生成式方向探索过程中，对低质内容的标题生成，在线上获得了接近10%的效果提升，但仍有很多值得进一步的尝试和深挖的空间。抽取与生成Combine在我们的场景中，有两种Combine的思路，一个是以业务效果为导向的偏工程化方法，另外一个是我们正在探索的一种Copy方法。工程化的思想非常简洁，在推荐问题上扩充候选，是提升效果的一个可行途径，那生成内容即作为新增的候选集之一，参与整体的预估排序。这个方法能保证最终线上效果不会是负向的，实际上也取得了一定的提升。另一种方法也是学业界研究的子方向之一，即Copy机制，我们也在做重点探索，这里仅作思路的介绍，不再进行展开。使用Copy机制的原始目的，是为了解决生成式的OOV（超出词表范围）问题。但对于我们的场景来说，大部分的“内容-标题”对数据是来自于抽取式，即我们很多标题数据，其实参考了原文。那如何继承这个参考机制，针对业务目标学习何时Copy以及Copy什么，来更优雅地发挥生成式的优势，就是我们探索Copy方法的初衷。我们的方向是对Copy和Generate概率做独立建模，其中重点解决在受限情况下的“Where To Point”问题。业务指标与生成式目标的Gap我们知道生成式模型其本质是一个Language Model，它的训练目标是最小化Word级别的交叉熵Loss，而最终我们的需要评价的其实是业务相关的句子级别点击率，这就导致了训练目标和业务指标不一致。解决这个问题，在我们的场景中有三个可行的方向，第一是在Context中显式地标注抽取式模型的Label，让模型学习到两者的差异；第二是在预测Decoder的Beam Search计算概率的同时，添加一个打分控制函数；第三则是在训练的Decoder中，建立一个全局损失函数参与训练，类似于NMT中增加的Coverage Loss。考虑到稳定性和实现成本，我们最终尝试了第一和第二种方式，其中第二种方式还是从商户文案迁移过来的，也会在下文进行介绍。在线上，这个尝试并没有在Combine的基础上取得更好的效果，但同样值得更加深入的探索。在线E&E机制最后，介绍一下前面提到过的标题E&E（Explore and Exploit，探索与利用）机制，用来持续获取标注数据，并提升在线自动纠错的能力。我们采用了一种贪心的Epsilon Greedy策略，并做了一点修改，类似经典的Epsilon算法，区别是引入创意状态，根据状态将Epsilon分成多级。目的是将比较好的创意可以分配给较大概率的流量，而不是均分，差的就淘汰，以此来提升效率。在初期优化阶段，这种方式发挥了很大的作用。具体我们根据标题和图片的历史表现和默认相比，将状态分成7档，从上到下效果表现依次递减，流量分配比例也依次降低，这样可以保证整个系统在样本有噪音的情况下实现线上纠偏。3.4 商户文案实践文案作为一个常见的创意形式，在O2O以商户为主要载体的场景下有三点需要：第一，赋予商户以内容调性，丰富创意；第二，通过内容化扩展投放的场景；最后，赋能平台的内容化升级，主要业务目标包括点击率、页面穿透率等等。文案生成和标题生成能够通用整体的生成模型框架，可以归为Data2Text类任务，最大区别是由文案的载体"商户"所决定。不同于内容，准确性的要求低很多，复杂度也大大降低，但同时为泛化能力提出了更高的要求，也带来了与内容生成不同的问题。首先在表示上，对商户的结构化理解变得尤其关键；其次在控制上，有D2T任务特有且非常重要的控制要求。前文也提到了生成一段文本从来不是难点，重要的是如何按照不同要求控制Seq生成的同时，保证很好的泛化性。下文也会分别介绍卖点控制、风格控制、多样性控制控制等几个控制方法。实现这样的控制，也有很多不同的思路。商户表示商户的表示抽象为Context，如下图中所示，主要分两部分。第一部分来源于商户的自身理解，一部分则来源于目标文本，两部分有一定交集。其中商户理解的数据为卖点或者Topic，在初期，为了挖掘商户卖点和Topic，我们主要使用成本较低、无需标注的LDA。但是它的准确性相对不可控，同时对产出的卖点主题仍需要进行人工的选择，以便作为新的标注，辅助后续扩展有监督的任务。我们通过Key和Value两个Field，来对卖点和主题进行共同表达（也存在很多只有Value的情况），比如下图这个商户“菜品”是个Key，“雪蟹”是Value，“约会”则仅是Value。随着时间的推移，后续我们逐渐利用平台商户标签和图谱信息，来扩展商户卖点的覆盖，以此丰富我们的输入信息。该部分在内容挖掘和NLP知识图谱的相关介绍中都有涉及，这里不再进行展开。第二部分目标文本来源，特意添加这部分进入Context，主要有三方面原因：第一，仅仅依靠商户理解的Context，在训练过程中Loss下降极慢，并且最终预测生成多样性不理想。本质原因是，目标文本内容与商户卖点、主题间的相关性远远不够。通过不同商户的集合来学习到这个表示关系，非常困难。第二，拓宽可用数据范围，不受商户评论这类有天然标注对的数据限制，从商户衔接扩展到卖点衔接，引入更多的泛化描述数据，比如各类运营文案等等。第三，这也是更为重要的一点，能够间接地实现卖点选择的能力，这个会在下文进行介绍。控制端实现控制，在解码端表现为两类，一类我们称之为Hard Constrained（强控制），即在数据端给定（或没有给定）的信息，一定要在解码端进行（或不进行）相应描述，这个适用于地域类目等不能出错的信息。比如这家商户在上海，生成时不能出现除上海以外的地域信息，否则容易造成歧义。另一类称之为Soft Constrained（弱控制），不同于NMT问题，在文案生成上即便是完全相同的输入，不同的输出都是允许的，比如同一商户，最终的文案可以选择不同的卖点去描述不同的内容。这类同属受限优化的问题，前文提到过有两个思路方向：第一，通过构建机制来让模型自己学习到目标；第二，在Decoder的Beam Search阶段动态地加入所需的控制目标。我们使用两者相结合的方法，来完成最终的不同控制的实现。两端机制设计：在具体机制实现上，主要依赖在Input Context和Output Decoder两端同时生效，让Context的Hard Constrained来源于Output，从而使Model能够自动学习到强受限关系；而Soft Constrained则通过贝叶斯采样的方法，动态添加进Context，从而帮助Model提升泛化能力。Decoder控制：简单介绍下Beam Search，前面提到过，文本生成的预测过程是按Word级进行的，每轮预测的候选是整个词汇空间，而往往一般的词表都是十万以上的量级。如果生成序列序列长度为N，最终候选序列就有十万的N次方种可能，这在计算和存储上绝不可行。这时候，就需要使用到Beam Search方法，每一步保留最优的前K（K一般为2）个最大概率序列，其他则被剪枝，本质上可以视作一个压缩版的维特比解码。我们在预测Beam Search阶段，除了计算模型概率外，额外增加下图中绿色部分的Fuction。输入为之前已生成的序列，具体计算逻辑取决于控制目标，可以自由实现。下面简单介绍两个重要的控制实现：卖点控制：这是最重要的一个控制机制，我们整理了涉及到Hard Constrained的卖点和实体，重要的如地域、品类等，在目标理解过程中直接加入Context。对于Soft Constrained，我们通过卖点的共现计算一个简单的条件概率，并将卖点依此条件概率随机添加进Context中，从而让模型通过注意力学习到受限关系。最后在Decoder fuction部分，我们新增了一个Hard&Soft Constrained的匹配打分项，参与最终的概率计算。最终的实际结果，也非常符合我们的预期。风格控制：实现方法和卖点控制非常相似，只是这里的风格，其实是通过不同内容之间的差异来间接进行实现。比如大众点评头条、PGC类的内容与UGC类的的写作风格，就存在极大的差异。那么在文案上，比如聚合页标题上可能更需要PGC的风格，而聚合页内容上则需要UGC的风格。这样的内容属性，即可作为一个Context的控制信号，让模型捕获。3.5 内容聚合多样性控制多样性，在文案生成上是一个比较重要和普遍的问题，尤其对于同一个店铺、同一个卖点或主题同时生成N条内容的聚合页来说，更为突出。本质原因是，在解码预测Beam Search时永远选择概率最大的序列，并不考虑多样性。但是如果预测时采用Decoder概率Random Search的方法，则在通顺度上会存在比较大的问题。对此，我们直接对全局结果进行优化，在预测时把一个聚合页Context放到同一个batch中，batch_size即为文案条数，对已经生成序列上进行实体重复检测和n-gram重复检测，将检测判重的加一个惩罚性打分，这个简单的思想已经能非常好的解决多样性问题。4. 动态创意目前，很多搜索推荐等排序优化场景，都会将创意信息作为特征工程一部分添加进精排或召回模型。那如果把创意优化近似为一个内容级创意排序问题，也可以无缝衔接常用的Wide&Deep、DNN、FNN等CTR预估模型。但是这之前，需要明确一点非常重要的问题，即它与推荐精排模型的差异，它们之间甚至可能会相互影响，对此，提供下我们的思考。与精排模型的差异第一，精排模型能否一并完成创意的排序，答案显然是肯定的。但它的复杂度决定了能Cover候选集的上限，性能上往往接受不了叉乘创意带来的倍数增长。但此非问题的关键。第二，创意层排序在精排层之前还是之后，直接影响了创意模型的复杂度，也间接决定了其效果的上限，以及它对精排模型可能的影响程度，从而可能带来全局的影响。此没有最佳实践，视场景权衡。第三，精排模型与创意排序业务目标一致，但实现方式不同。精排模型通过全局排序的最优化来提升业务指标，而创意优化则是通过动态提升内容受众价值来提升业务指标。最后，我们回到用户视角，当用户在浏览信息流时，其实看到的只有创意本身（标题、图片、作者等信息），但用户却能从中感知到背后的诸多隐含信息，也就是CTR预估中的重要内容/商户类特征，诸如类目、场景、商户属性等。这个现象背后的本质在于，创意可以表征很多高阶的结构化信息。基于这一点，在创意优化的特征工程上，方向就很明确了：强化User/Context，弱化Item/POI，通过创意表征，来间接学习到弱化的信息从而实现创意层面的最优排序。该部分工作不仅仅涉及到文本，在本文中不再展开。用户兴趣与文本生成结合的可能性动态创意为文本生成提供了全新的空间，也提出了更高的要求。动态创意提升受众价值，不仅仅只能通过排序来实现，在正篇介绍的最后部分，我们抛出一个可能性的问题，供各位同行和同学一起思考。也希望能看到更多业界的方案和实践，共同进步。5. 总结与展望整个2018年，大众点评信息流在核心指标上取得了显著的突破。创意优化作为其中的一部分，在一些方面进行了很多探索，也在效果指标上取得了较为显著的收益。不过，未来的突破，更加任重而道远。2018年至2019年初，NLP的各个子领域涌现了非常多令人惊喜的成果，并且这些成果已经落地到业界实践上。这是一个非常好的趋势，也预示着在应用层面会有越来越多的突破。比如2019年初，能够续写短篇小说的GPT2问世，虽然它真实的泛化能力还未可知，但让我们真切看到了在内容受限下高质量内容生成的可能性。最后，回到初心，我们希望通过创意的载体显式地连接用户、商户和内容。我们能了解用户关注什么，知道某些内容表达什么，获知哪些商户好，好在哪里，将信息的推荐更进一步。参考资料[1] Context-aware Natural Language Generation with Recurrent Neural Networks. arXiv preprint arXiv:1611.09900.[2] Attention Is All You Need. arXiv preprint arXiv:1706.03762.[3] Universal Transformers. arXiv preprint arXiv:1807.03819.[4] A Convolutional Encoder Model for Neural Machine Translation. arXiv preprint arXiv:1611.02344.[5] Don’t Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization. arXiv preprint arXiv:1808.08745.[6] Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805.[7] ELMO：Deep contextualized word representations. arXiv preprint arXiv:1802.05365.[8] openAI GPT：Improving Language Understanding by Generative Pre-Training.[9] Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473.[10] Tensor2Tensor for Neural Machine Translation. arXiv preprint arXiv:1803.07416.[11] A Convolutional Encoder Model for Neural Machine Translation. arXiv preprint arXiv:1611.02344.[12] Sequence-to-Sequence Learning as Beam-Search Optimization. arXiv preprint arXiv:1606.02960.[13] A Deep Reinforced Model For Abstractive Summarization. arXiv preprint arXiv:1705.04304.[14] SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient. arXiv preprint arXiv:1609.05473.[15] Generating sequences with recurrent neural networks. CoRR,abs/1308.0850.作者简介忆纯，2015年加入美团点评，算法专家，目前负责点评信息流内容创意工作。杨肖，博士，2016年加入美团点评，高级算法专家，点评推荐智能中心内容团队负责人。明海，2016年加入美团点评，美团点评研究员，点评推荐智能中心团队负责人。众一，2016年加入美团点评，算法研发工程师，目前主要负责点评信息流创意相关算法研发工作。扬威，2018年初加入美团点评，算法研发工程师，目前主要负责点评信息流动态创意相关算法研发工作。凤阳，2016年加入美团点评，算法研发工程师，目前主要负责点评信息流内容运营算法优化的工作。

引言挑战与思路搜索是大众点评App上用户进行信息查找的最大入口，是连接用户和信息的重要纽带。而用户搜索的方式和场景非常多样，并且由于对接业务种类多，流量差异大，为大众点评搜索（下文简称点评搜索）带来了巨大的挑战，具体体现在如下几个方面：意图多样：用户查找的信息类型和方式多样。信息类型包括POI、榜单、UGC、攻略、达人等。以找店为例，查找方式包括按距离、按热度、按菜品和按地理位置等多种方式。例如用户按照品牌进行搜索时，大概率是需要寻找距离最近或者常去的某家分店；但用户搜索菜品时，会对菜品推荐人数更加敏感，而距离因素会弱化。业务多样：不同业务之间，用户的使用频率、选择难度以及业务诉求均不一样。例如家装场景用户使用频次很低，行为非常稀疏，距离因素弱，并且选择周期可能会很长；而美食多为即时消费场景，用户行为数据多，距离敏感。用户类型多样：不同的用户对价格、距离、口味以及偏好的类目之间差异很大；搜索需要能深度挖掘到用户的各种偏好，实现定制化的“千人千面”的搜索。LBS的搜索：相比电商和通用搜索，LBS的升维效应极大地增加了搜索场景的复杂性。例如对于旅游用户和常驻地用户来说，前者在搜索美食的时候可能会更加关心当地的知名特色商户，而对于距离相对不敏感。上述的各项特性，叠加上时间、空间、场景等维度，使得点评搜索面临比通用搜索引擎更加独特的挑战。而解决这些挑战的方法，就需要升级NLP（Natural Language Processing，自然语言处理）技术，进行深度查询理解以及深度评价分析，并依赖知识图谱技术和深度学习技术对搜索架构进行整体升级。在美团NLP中心以及大众点评搜索智能中心两个团队的紧密合作之下，经过短短半年时间，点评搜索核心KPI在高位基础上仍然大幅提升，是过去一年半涨幅的六倍之多，提前半年完成全年目标。基于知识图谱的搜索架构重塑美团NLP中心正在构建全世界最大的餐饮娱乐知识图谱——美团大脑（相关信息请参见《美团大脑：知识图谱的建模方法及其应用》）。它充分挖掘关联各个场景数据，用NLP技术让机器“阅读”用户公开评论，理解用户在菜品、价格、服务、环境等方面的喜好，构建人、店、商品、场景之间的知识关联，从而形成一个“知识大脑”[1]。通过将知识图谱信息加入到搜索各个流程中，我们对点评搜索的整体架构进行了升级重塑，图1为点评搜索基于知识图谱搭建的5层搜索架构。本篇文章是“美团大脑”系列文章第二篇（系列首篇文章请参见《美团餐饮娱乐知识图谱——美团大脑揭秘》)，主要介绍点评搜索5层架构中核心排序层的演变过程，文章主要分为如下3个部分：核心排序从传统机器学习模型到大规模深度学习模型的演进。搜索场景深度学习排序模型的特征工程实践。适用于搜索场景的深度学习Listwise排序算法——LambdaDNN。2. 排序模型探索与实践搜索排序问题在机器学习领域有一个单独的分支，Learning to Rank（L2R）。主要分类如下:根据样本生成方法和Loss Function的不同，L2R可以分为Pointwise、Pairwise、Listwise。按照模型结构划分，可以分为线性排序模型、树模型、深度学习模型，他们之间的组合（GBDT+LR，Deep&Wide等）。在排序模型方面，点评搜索也经历了业界比较普遍的迭代过程：从早期的线性模型LR，到引入自动二阶交叉特征的FM和FFM，到非线性树模型GBDT和GBDT+LR，到最近全面迁移至大规模深度学习排序模型。下面先简单介绍下传统机器学习模型（LR、FM、GBDT）的应用和优缺点，然后详细介绍深度模型的探索实践过程。传统机器学习模型LR可以视作单层单节点的线性网络结构。模型优点是可解释性强。通常而言，良好的解释性是工业界应用实践比较注重的一个指标，它意味着更好的可控性，同时也能指导工程师去分析问题优化模型。但是LR需要依赖大量的人工特征挖掘投入，有限的特征组合自然无法提供较强的表达能力。FM可以看做是在LR的基础上增加了一部分二阶交叉项。引入自动的交叉特征有助于减少人工挖掘的投入，同时增加模型的非线性，捕捉更多信息。FM能够自动学习两两特征间的关系，但更高量级的特征交叉仍然无法满足。GBDT是一个Boosting的模型，通过组合多个弱模型逐步拟合残差得到一个强模型。树模型具有天然的优势，能够很好的挖掘组合高阶统计特征，兼具较优的可解释性。GBDT的主要缺陷是依赖连续型的统计特征，对于高维度稀疏特征、时间序列特征不能很好的处理。深度神经网络模型随着业务的发展，在传统模型上取得指标收益变得愈发困难。同时业务的复杂性要求我们引入海量用户历史数据，超大规模知识图谱特征等多维度信息源，以实现精准个性化的排序。因此我们从2018年下半年开始，全力推进L2核心排序层的主模型迁移至深度学习排序模型。深度模型优势体现在如下几个方面：强大的模型拟合能力：深度学习网络包含多个隐藏层和隐藏结点，配合上非线性的激活函数，理论上可以拟合任何函数，因此十分适用于点评搜索这种复杂的场景。强大的特征表征和泛化能力：深度学习模型可以处理很多传统模型无法处理的特征。例如深度网络可以直接中从海量训练样本中学习到高维稀疏ID的隐含信息，并通过Embedding的方式去表征；另外对于文本、序列特征以及图像特征，深度网络均有对应的结构或者单元去处理。自动组合和发现特征的能力：华为提出的DeepFM，以及Google提出的DeepCrossNetwork可以自动进行特征组合，代替大量人工组合特征的工作。下图是我们基于Google提出的Wide&Deep模型搭建的网络结构[2]。其中Wide部分输入的是LR、GBDT阶段常用的一些细粒度统计特征。通过较长周期统计的高频行为特征，能够提供很好的记忆能力。Deep部分通过深层的神经网络学习Low-Order、高纬度稀疏的Categorical型特征，拟合样本中的长尾部分，发现新的特征组合，提高模型的泛化能力。同时对于文本、头图等传统机器学习模型难以刻画的特征，我们可以通过End-to-End的方式，利用相应的子网络模型进行预处理表示，然后进行融合学习。3. 搜索深度排序模型的特征工程实践深度学习的横空出世，将算法工程师从很多人工挖掘和组合特征的事情中解放出来。甚至有一种论调，专做特征工程的算法工程师可能面临着失业的风险。但是深度学习的自动特征学习目前主要集中体现在CV领域，CV领域的特征数据是图片的像素点——稠密的低阶特征，深度学习通过卷积层这个强力工具，可以自动对低阶特征进行组合和变换，相比之前人工定义的图像特征从效果上来说确实更加显著。在NLP领域因为Transformer的出现，在自动特征挖掘上也有了长足的进步，BERT利用Transformer在多个NLP Task中取得了State-of-The-Art的效果。但是对于CTR预估和排序学习的领域，目前深度学习尚未在自动特征挖掘上对人工特征工程形成碾压之势，因此人工特征工程依然很重要。当然，深度学习在特征工程上与传统模型的特征工程也存在着一些区别，我们的工作主要集中在如下几个方面。3.1 特征预处理特征归一化：深度网络的学习几乎都是基于反向传播，而此类梯度优化的方法对于特征的尺度非常敏感。因此，需要对特征进行归一化或者标准化以促使模型更好的收敛。特征离散化：工业界一般很少直接使用连续值作为特征，而是将特征离散化后再输入到模型中。一方面因为离散化特征对于异常值具有更好的鲁棒性，其次可以为特征引入非线性的能力。并且，离散化可以更好的进行Embedding，我们主要使用如下两种离散化方法：等频分桶：按样本频率进行等频切分，缺失值可以选择给一个默认桶值或者单独设置分桶。树模型分桶：等频离散化的方式在特征分布特别不均匀的时候效果往往不好。此时可以利用单特征结合Label训练树模型，以树的分叉点做为切分值，相应的叶子节点作为桶号。特征组合：基于业务场景对基础特征进行组合，形成更丰富的行为表征，为模型提供先验信息，可加速模型的收敛速度。典型示例如下：用户性别与类目之间的交叉特征，能够刻画出不同性别的用户在类目上的偏好差异，比如男性用户可能会较少关注“丽人”相关的商户。时间与类目之间的交叉特征，能够刻画出不同类目商户在时间上的差异，例如，酒吧在夜间会更容易被点击。3.2 万物皆可Embedding深度学习最大的魅力在于其强大的特征表征能力，在点评搜索场景下，我们有海量的用户行为数据，有丰富的商户UGC信息以及美团大脑提供的多维度细粒度标签数据。我们利用深度学习将这些信息Embedding到多个向量空间中，通过Embedding去表征用户的个性化偏好和商户的精准画像。同时向量化的Embedding也便于深度模型进一步的泛化、组合以及进行相似度的计算。3.2.1 用户行为序列的Embedding用户行为序列（搜索词序列、点击商户序列、筛选行为序列）包含了用户丰富的偏好信息。例如用户筛选了“距离优先”时，我们能够知道当前用户很有可能是一个即时消费的场景，并且对距离较为敏感。行为序列特征一般有如下图所示的三种接入方式:Pooling：序列Embedding后接入Sum/Average Pooling层。此方式接入成本低，但忽略了行为的时序关系。RNN：LSTM/GRU接入，利用循环网络进行聚合。此方式能够考虑行为序列的时序关系；代价是增大了模型复杂度，影响线上预测性能。Attention：序列Embedding后引入Attention机制，表现为加权的Sum Pooling；相比LSTM/GRU计算开销更低[4]。同时，为了突显用户长期偏好和短期偏好对于排序的不同影响，我们按照时间维度对行为序列进行了划分：Session、半小时、一天、一周等粒度，也在线上取得了收益。3.2.2 用户ID的Embedding一种更常见的刻画用户偏好的方式，是直接将用户ID经过Embedding后作为特征接入到模型中，但是最后上线的效果却不尽如人意。通过分析用户的行为数据，我们发现相当一部分用户ID的行为数据较为稀疏，导致用户ID的Embedding没有充分收敛，未能充分刻画用户的偏好信息。Airbnb发表在KDD 2018上的文章为这种问题提供了一种解决思路[9]——利用用户基础画像和行为数据对用户ID进行聚类。Airbnb的主要场景是为旅游用户提供民宿短租服务，一般用户一年旅游的次数在1-2次之间，因此Airbnb的用户行为数据相比点评搜索会更为稀疏一些。如上图所示，将用户画像特征和行为特征进行离散分桶，拼接特征名和所属桶号，得到的聚类ID为：US_lt1_pn3_pg3_r3_5s4_c2_b1_bd2_bt2_nu3。我们也采取了类似Airbnb的方案，稀疏性的问题得到了很好的解决，并且这样做还获得了一些额外的收益。点评搜索作为一个本地化的生活信息服务平台，大部分用户的行为都集中自己的常驻地，导致用户到达一个新地方时，排序个性化明显不足。通过这种聚类的方式，将异地有相同行为的用户聚集在一起，也能解决一部分跨站的个性化问题。3.2.3 商户信息Embedding商户Embedding除了可以直接将商户ID加入模型中之外，美团大脑也利用深度学习技术对UGC进行大量挖掘，对商家的口味、特色等细粒度情感进行充分刻画，例如下图所示的“好停车”、“菜品精致”、“愿意再次光顾”等标签。这些信息与单纯的商户星级、点评数相比，刻画的角度更多，粒度也更细。我们将这些标签也进行Embedding并输入到模型中：直连：将标签特征做Pooling后直接输入模型。这种接入方式适合端到端的学习方式；但受输入层大小限制，只能取Top的标签，容易损失抽象实体信息。分组直连：类似于直连接入的方式，但是先对标签进行分类，如菜品/风格/口味等类别；每个分类取Top N的实体后进行Pooling生成不同维度的语义向量。与不分组的直连相比，能够保留更多抽象信息。子模型接入：可以利用DSSM模型，以标签作为商户输入学习商户的Embedding表达。此种方式能够最大化保留标签的抽象信息，但是线上实现和计算成本较高。3.2.4 加速Embedding特征的收敛在我们的深度学习排序模型中，除了Embedding特征，也存在大量Query、Shop和用户维度的强记忆特征，能够很快收敛。而Embedding特征是更为稀疏的弱特征，收敛速度较慢，为了加速Embedding特征的收敛，我们尝试了如下几种方案：低频过滤：针对出现频率较低的特征进行过滤，可以很大程度上减少参数量，避免过拟合。预训练：利用多类模型对稀疏Embedding特征进行预训练，然后进入模型进行微调：通过无监督模型如Word2vec、Fasttext对用户-商户点击关系建模，生成共现关系下的商户Embedding。利用DSSM等监督模型对Query-商户点击行为建模得到Query和商户的Embedding。Multi-Task：针对稀疏的Embedding特征，单独设置一个子损失函数，如下图所示。此时Embedding特征的更新依赖两个损失函数的梯度，而子损失函数脱离了对强特征的依赖，可以加快Embedding特征的收敛。3.3 图片特征图片在搜索结果页中占据了很大的展示面积，图片质量的好坏会直接影响用户的体验和点击，而点评商户首图来自于商户和用户上传的图片，质量参差不齐。因此，图片特征也是排序模型中较为重要的一类。目前点评搜索主要用了以下几类图片特征：基础特征：提取图片的亮度、色度饱和度等基础信息，进行特征离散化后得到图片基础特征。泛化特征：使用ResNet50进行图片特征提取[3]，通过聚类得到图片的泛化特征。质量特征：使用自研的图片质量模型，提取中间层输出，作为图片质量的Embedding特征。标签特征：提取图片是否是食物、环境、价目表、Logo等作为图片分类和标签特征。4. 适用于搜索场景的深度学习Listwise排序算法—LambdaDNN4.1 搜索业务指标与模型优化目标的Gap通常模型的预测目标与业务指标总会存在一些Gap。如果模型的预测目标越贴近业务目标，越能保证模型优化的同时业务指标也能够有相应的提升；反之则会出现模型离线指标提升，但线上关键业务指标提升不明显，甚至出现负向的问题。工业届大部分深度学习排序采用Pointwise的Log Loss作为损失函数，与搜索业务指标有较大的Gap。体现在如下两个方面：搜索业务常用的指标有QV_CTR或者SSR(Session Success Rate)，更关心的是用户搜索的成功率（有没有发生点击行为）；而Pointwise的Log Loss更多是关注单个Item的点击率。搜索业务更关心排在页面头部结果的好坏，而Pointwise的方法则对于所有位置的样本一视同仁。基于上述理由，我们对于深度学习模型的损失函数进行了优化。4.2 优化目标改进-从Log Loss到NDCG为了让排序模型的优化目标尽量贴近搜索业务指标，需要按照Query计算损失，且不同位置的样本具有不同的权重。搜索系统常用的指标NDCG(Normalized Discounted Cumulative Gain)相较于Log Loss显然更贴近搜索业务的要求，NDCG计算公式如下：累加部分为DCG(Discounted Cumulative Gain)表示按照位置折损的收益，对于Query下的结果列表l，函数G表示对应Doc的相关度分值，通常取指数函数，即G(lj)=2lj-1（lj表示的是相关度水平，如{0，1，2}）；函数 即位置折损，一般采用 (j)=1/log(j+1)，Doc与Query的相关度越高且位置越靠前则DCG值会越大。另外，通常我们仅关注排序列表页前k位的效果，Zk 表示 DCG@k 的可能最大值，以此进行归一化处理后得到的就是NDCG@k。问题在于NDCG是一个处处非平滑的函数，直接以它为目标函数进行优化是不可行的。LambdaRank提供了一种思路：绕过目标函数本身，直接构造一个特殊的梯度，按照梯度的方向修正模型参数，最终能达到拟合NDCG的方法[6]。因此，如果我们能将该梯度通过深度网络进行反向传播，则能训练一个优化NDCG的深度网络，该梯度我们称之为Lambda梯度，通过该梯度构造出的深度学习网络称之为LambdaDNN。要了解Lambda梯度需要引入LambdaRank。LambdaRank模型是通过Pairwise来构造的，通常将同Query下有点击样本和无点击样本构造成一个样本Pair。模型的基本假设如下式所示，令Pij为同一个Query下Doci相比Docj更相关的概率，其中si和sj分别为Doci和Docj的模型得分：使用交叉熵为损失函数，令Sij表示样本Pair的真实标记，当Doci比Docj更相关时（即Doci有被用户点击，而Docj没有被点击），有Sij=1，否则为-1；则损失函数可以表示为：在构造样本Pair时，我们可以始终令i为更相关的文档，此时始终有Sij≡1，代入上式并进行求导，则损失函数的梯度为：到目前为止，损失函数的计算过程中并未考虑样本所在的位置信息。因此进一步对梯度进行改造，考虑Doci和Docj交换位置时的NDCG值变化，下式即为前述的Lambda梯度。可以证明，通过此种方式构造出来的梯度经过迭代更新，最终可以达到优化NDCG的目的。Lambda梯度的物理意义如下图所示。其中蓝色表示更相关（用户点击过）的文档，则Lambda梯度更倾向于位置靠上的Doc得到的提升更大（如红色箭头所示）。有了Lambda梯度的计算方法，训练中我们利用深度网络预测同Query下的Doc得分，根据用户实际点击Doc的情况计算Lambda梯度并反向传播回深度网络，则可以得到一个直接预测NDCG的深度网络。4.3 LambdaDNN的工程实施我们利用TensorFlow分布式框架训练LambdaDNN模型。如前文所述，Lambda梯度需要对同Query下的样本进行计算，但是正常情况下所有的样本是随机Shuffle到各个Worker的。因此我们需要对样本进行预处理：通过QueryId进行Shuffle，将同一个Query的样本聚合在一起，同一个Query的样本打包进一个TFRecord。由于每次请求Query召回的Doc数不一样，对于可变Size的Query样本在拉取数据进行训练时需要注意，TF会自动补齐Mini-Batch内每个样本大小一致，导致输入数据中存在大量无意义的默认值样本。这里我们提供两点处理方式：MR过程中对Key进行处理，使得多个Query的样本聚合在一起，然后在训练的时候进行动态切分。读取到补齐的样本，根据设定的补齐标记获取索引位，去除补齐数据。为了提升训练效率，我们与基础研发平台数据平台中心紧密协同，一起探索并验证了多项优化操作：将ID类特征的映射等操作一并在预处理中完成，减少多轮Training过程中的重复计算。将样本转TfRecord，利用RecordDataSet方式读取数据并计算处理，Worker的计算性能大概提升了10倍。Concat多个Categorical特征，组合成Multi-Hot的Tensor进行一次Embedding_Lookup操作，减少Map操作的同时有助于参数做分片存储计算。稀疏Tensor在计算梯度以及正则化处理时保留索引值，仅对有数值的部分进行更新操作。多个PS服务器间进行分片存储大规模Tensor变量，减少Worker同步更新的通讯压力，减少更新阻塞，达到更平滑的梯度更新效果。整体下来，对于30亿左右的样本量、上亿级别的特征维度，一轮迭代大概在半小时内完成。适当的增加并行计算的资源，可以达到分钟级的训练任务。4.4 进一步改进优化目标NDCG的计算公式中，折损的权重是随着位置呈指数变化的。然而实际曝光点击率随位置变化的曲线与NDCG的理论折损值存在着较大的差异。对于移动端的场景来说，用户在下拉滑动列表进行浏览时，视觉的焦点会随着滑屏、翻页而发生变动。例如用户翻到第二页时，往往会重新聚焦，因此，会发现第二页头部的曝光点击率实际上是高于第一页尾部位置的。我们尝试了两种方案去微调NDCG中的指数位置折损：根据实际曝光点击率拟合折损曲线：根据实际统计到的曝光点击率数据，拟合公式替代NDCG中的指数折损公式，绘制的曲线如图12所示。计算Position Bias作为位置折损：Position Bias在业界有较多的讨论，其中7将用户点击商户的过程分为观察和点击两个步骤：a.用户需要首先看到该商户，而看到商户的概率取决于所在的位置；b.看到商户后点击商户的概率只与商户的相关性有关。步骤a计算的概率即为Position Bias，这块内容可以讨论的东西很多，这里不再详述。经过上述对NDCG计算改造训练出的LambdaDNN模型，相较Base树模型和Pointwise DNN模型，在业务指标上有了非常显著的提升。4.5 Lambda深度排序框架Lambda梯度除了与DNN网络相结合外，事实上可以与绝大部分常见的网络结构相结合。为了进一步学习到更多交叉特征，我们在LambdaDNN的基础上分别尝试了LambdaDeepFM和LambdaDCN网络；其中DCN网络是一种加入Cross的并行网络结构，交叉的网络每一层的输出特征与第一层的原始输入特征进行显性的两两交叉，相当于每一层学习特征交叉的映射去拟合层之间的残差。离线的对比实验表明，Lambda梯度与DCN网络结合之后充分发挥了DCN网络的特点，简洁的多项式交叉设计有效地提升模型的训练效果。NDCG指标对比效果如下图所示：5. 深度学习排序诊断系统深度学习排序模型虽然给业务指标带来了大幅度的提升，但由于深度学习模型的“黑盒属性”导致了巨大的解释性成本，也给搜索业务带来了一些问题：日常搜索Bad Case无法快速响应：搜索业务日常需要应对大量来自于用户、业务和老板们的“灵魂拷问”，“为何这个排序是这样的”，“为什么这家商户质量跟我差不多，但是会排在我的前面”。刚切换到深度学习排序模型的时候，我们对于这样的问题显得手足无措，需要花费大量的时间去定位问题。无法从Bad Case中学习总结规律持续优化：如果不明白为什么排序模型会得出一个很坏的排序结果，自然也无法定位模型到底出了什么问题，也就无法根据Bad Case总结规律，从而确定模型和特征将来的优化方向。模型和特征是否充分学习无从得知：新挖掘一些特征之后，通常我们会根据离线评测指标是否有提升决定特征是否上线。但是，即使一个有提升的特征，我们也无法知道这个特征是否性能足够好。例如，模型拟合的距离特征，会不会在特定的距离段出现距离越远反而打分越高的情况。这些问题都会潜在带来一些用户无法理解的排序结果。我们需要对深度排序模型清晰地诊断并解释。关于机器学习模型的可解释性研究，业界已经有了一些探索。Lime(Local Interpretable Model-Agnostic Explanations)是其中的一种，如下图所示：通过对单个样本的特征生成扰动产生近邻样本，观察模型的预测行为。根据这些扰动的数据点距离原始数据的距离分配权重，基于它们学习得到一个可解释的模型和预测结果[5]。举个例子，如果需要解释一个情感分类模型是如何预测“我讨厌这部电影”为负面情感的，我们通过丢掉部分词或者乱序构造一些样本预测情感，最终会发现，决定“我讨厌这部电影”为负面情感的是因为“讨厌”这个词。基于Lime解释器的思想，我们开发了一套深度模型解释器工具——雅典娜系统。目前雅典娜系统支持两种工作模式，Pairwise和Listwise模式：Pairwise模式用来解释同一个列表中两个结果之间的相对排序。通过对样本的特征进行重新赋值或者替换等操作，观察样本打分和排序位次的变化趋势，诊断出当前样本排序是否符合预期。如下图所示，通过右侧的特征位次面板可以快速诊断出为什么“南京大牌档”的排序比“金时代顺风港湾”要更靠前。第一行的特征位次信息显示，若将“金时代顺风港湾”的1.3km的距离特征用“南京大牌档”的0.2km的距离特征进行替换，排序位次将上升10位；由此得出，“南京大牌档”排在前面的决定性因素是因为距离近。Listwise模式与Lime的工作模式基本类似，通过整个列表的样本生成扰动样本，训练线性分类器模型输出特征重要度，从而达到对模型进行解释的目的。6. 总结与展望2018年下半年，点评搜索完成了从树模型到大规模深度学习排序模型的全面升级。团队在深度学习特征工程、模型结构、优化目标以及工程实践上都进行了一些探索，在核心指标上取得了较为显著的收益。当然，未来依然有不少可以探索的点。在特征层面，大量知识图谱提供的标签信息尚未充分挖掘。从使用方式上看，简单以文本标签的形式接入，损失了知识图谱的结构信息，因此，Graph Embedding也是未来需要尝试的方向。同时团队也会利用BERT在Query和商户文本的深层语义表达上做一些工作。模型结构层面，目前线上依然以全连接的DNN网络结构为主，但DNN网络结构在低秩数据的学习上不如DeepFM和DCN。目前LambdaDeepFM和LambdaDCN在离线上已经取得了收益，未来会在网络结构上做进一步优化。在模型优化目标上，Lambda Loss计算损失的时候，只会考虑Query内部有点击和无点击的样本对，大量无点击的Query被丢弃，同时，同一个用户短时间内在不同Query下的行为也包含着一些信息可以利用。因此，目前团队正在探索综合考虑Log Loss和Lambda Loss的模型，通过Multi-Task和按照不同维度Shuffle样本让模型充分学习，目前我们已经在线下取得了一些收益。最后，近期Google开源的TF Ranking提出的Groupwise模型也对我们有一些启发。目前绝大部分的Listwise方法只是体现在模型训练阶段，在打分预测阶段依然是Pointwise的，即只会考虑当前商户相关的特征，而不会考虑列表上下文的结果，未来我们也会在这个方向上进行一些探索。参考资料美团大脑：知识图谱的建模方法及其应用Wide & Deep Learning for Recommender SystemsDeep Residual Learning for Image RecognitionAttention Is All You NeedLocal Interpretable Model-Agnostic Explanations: LIMEFrom RankNet to LambdaRank to LambdaMART: An OverviewA Novel Algorithm for Unbiased Learning to RankUnbiased Learning-to-Rank with Biased FeedbackReal-time Personalization using Embeddings for Search Ranking at Airbnb作者简介非易，2016年加入美团点评，高级算法工程师，目前主要负责点评搜索核心排序层的研发工作。祝升，2016年加入美团点评，高级算法工程师，目前负责点评搜索核心排序层的研发工作。汤彪，2013年加入美团点评，高级算法专家，点评平台搜索技术负责人，致力于深层次查询理解和大规模深度学习排序的技术落地。张弓，2012年加入美团点评，美团点评研究员。目前主要负责点评搜索业务演进，及集团搜索公共服务平台建设。仲远，博士，美团AI平台部NLP中心负责人，点评搜索智能中心负责人。在国际顶级学术会议发表论文30余篇，获得ICDE 2015最佳论文奖，并是ACL 2016 Tutorial “Understanding Short Texts”主讲人，出版学术专著3部，获得美国专利5项。此前，博士曾担任微软亚洲研究院主管研究员，以及美国Facebook公司Research Scientist。曾负责微软研究院知识图谱、对话机器人项目和Facebook产品级NLP Service。

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是NlogN。归并排序的2个步骤先拆分，一直拆分到只有一个数拆分完成后，开始递归合并拆分过程从上图可以看出，归并排序会将一个数组进行两两拆分，一直拆分到只有一个数的时候停止拆分。那么拆分的代码就很简单了，就是得到一个指向中间的指针q，将数组拆分成(start,p)和（p，end）两个部分。p表示数组的开始下标r表示数组的结束下标 function divide(p, r){ return Math.floor( (p + r) / 2 ); }合并过程合并的过程就如上图所示遍历两组数据进行对比大小较小的那个值取出来放在第一个位置举个例子：假设现在数组A的数据是[2,5,1,3]经过我们的拆分后会是(0,2),(2,4);我们通过A.slice(0,2)和A.slice(2,4)=>得到两个数组A1[2,5]和A2[1,3]然后我们对数组[2,5,1,3]进行遍历，第一次会得到两边较小的数1，第二次2，第三次3，第四次是5 function merge(A, p, q, r){ const A1 = A.slice(p, q); const A2 = A.slice(q, r); // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值 A1.push(Number.MAX_SAFE_INTEGER); A2.push(Number.MAX_SAFE_INTEGER); // 循环做比较，每次取出较小的那个值 for (let i = p, j = 0, k = 0; i < r; i++) { if (A1[j] < A2[k]) { A[i] = A1[j]; j++; } else { A[i] = A2[k]; k++; } } }主程序主程序就是做递归重复上面的操作了 function merge_sort(A, p = 0, r) { r = r || A.length; if (r - p === 1) { return; } const q = divide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }完整代码 function divide(p, r) { return Math.floor((p + r) / 2); } function merge(A, p, q, r) { const A1 = A.slice(p, q); const A2 = A.slice(q, r); A1.push(Number.MAX_SAFE_INTEGER); A2.push(Number.MAX_SAFE_INTEGER); for (let i = p, j = 0, k = 0; i < r; i++) { if (A1[j] < A2[k]) { A[i] = A1[j]; j++; } else { A[i] = A2[k]; k++; } } } function merge_sort(A, p = 0, r) { r = r || A.length; if (r - p === 1) { return; } const q = divide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }推荐阅读数据结构系列：js数据结构-栈js数据结构-链表js数据结构-队列js数据结构-二叉树（二叉堆）js数据结构-二叉树（二叉搜索树）js数据结构-散列表(哈希表) ...

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nLogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nLogn)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成快速排序可能大家都学过，在面试中也经常会遇到，哪怕你是做前端的也需要会写，这里会列举两种不同的快排代码进行分析快速排序的3个基本步骤：从数组中选择一个元素作为基准点排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。为了更深入的理解，可以看下面这张图我们根据上面这张图，来用文字描述一下选择左右边的元素为基准数，7将小于7的放在左边，大于7的放在右边，然后将基准数放到中间然后再重复操作从左边的数组选择一个基准点23比2大则放到基准树的右边右边的数组也是一样选择12作为基准数，15比12大所以放到了12的右边最后出来的结果就是从左到右 2 ，3，7，12，15了以上就是快速排序基本的一个实现思想。快速排序实现方式一这是我最近看到的一种快排代码var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));};以上代码的实现方式是，选择一个中间的数字为基准点，用两个数组分别去保存比基准数小的值，和比基准数大的值，最后递归左边的数组和右边的数组，用concat去做一个数组的合并。对于这段代码的分析：缺点：获取基准点使用了一个splice操作，在js中splice会对数组进行一次拷贝的操作，而它最坏的情况下复杂度为O(n)，而O(n)代表着针对数组规模的大小进行了一次循环操作。首先我们每次执行都会使用到两个数组空间，产生空间复杂度。concat操作会对数组进行一次拷贝，而它的复杂度也会是O(n)对大量数据的排序来说相对会比较慢优点：代码简单明了，可读性强，易于理解非常适合用于面试笔试题那么我们接下来用另外一种方式去实现快速排序快速排序的实现方式二从上面这张图，我们用一个指针i去做了一个分割初始化i = -1循环数组，找到比支点小的数就将i向右移动一个位置，同时与下标i交换位置循环结束后，最后将支点与i+1位置的元素进行交换位置最后我们会得到一个由i指针作为分界点，分割成从下标0-i，和 i+1到最后一个元素。下面我们来看一下代码的实现，整个代码分成三部分，数组交换，拆分，qsort（主函数）三个部分先写最简单的数组交换吧，这个大家应该都懂 function swap(A, i ,j){ const t = A[i]; A[i] = A[j]; A[j] = t; }下面是拆分的过程，其实就是对指针进行移动，找到最后指针所指向的位置/** * * @param {} A 数组 * @param {} p 起始下标 * @param {} r 结束下标 + 1 / function dvide(A, p, r){ // 基准点 const pivot = A[r-1]; // i初始化是-1，也就是起始下标的前一个 let i = p - 1; // 循环 for(let j = p; j < r-1; j++){ // 如果比基准点小就i++，然后交换元素位置 if(A[j] < pivot){ i++; swap(A, i, j); } } // 最后将基准点插入到i+1的位置 swap(A, i+1, r-1); // 返回最终指针i的位置 return i+1; }主程序主要是通过递归去重复的调用进行拆分，一直拆分到只有一个数字。 /* * * @param {} A 数组 * @param {} p 起始下标 * @param {} r 结束下标 + 1 */ function qsort(A, p, r){ r = r || A.length; if(p < r - 1){ const q = divide(A, p, r); qsort(A, p, q); qsort(A, q + 1, r); } return A; }总结第二段的排序算法我们减少了两个O(n)的操作，得到了一定的性能上的提升，而第一种方法数据规模足够大的情况下会相对来说比较慢一些，快速排序在面试中也常常出现，为了笔试更好写一些可能会有更多的前端会选择第一种方式，但也会有一些为难人的面试官提出一些算法中的问题。而在实际的项目中，我觉得第一种方式可以少用。推荐本人最近写的关于数据结构系列如下，欢迎大家看看点个赞哈：js数据结构-栈js数据结构-链表js数据结构-队列js数据结构-二叉树（二叉堆）js数据结构-二叉树（二叉搜索树） ...

引言我们正处在一个知识爆炸的时代，伴随着信息量的剧增和人工智能的蓬勃发展，互联网公司越发具有强烈的个性化、智能化信息展示的需求。而信息展示个性化的典型应用主要包括搜索列表、推荐列表、广告展示等等。很多人不知道的是，看似简单的个性化信息展示背后，涉及大量的数据、算法以及工程架构技术，这些足以让大部分互联网公司望而却步。究其根本原因，个性化信息展示背后的技术是排序学习问题（Learning to Rank）。显然，市面上大部分关于排序学习的文章，要么偏算法、要么偏工程。虽然算法方面有一些系统性的介绍文章，但往往对读者的数学能力要求比较高，也偏学术论文，对于非算法同学来说门槛非常高。而大部分工程方面的文章也比较粗糙，基本上停留在Google的Two-Phase Scheme阶段，从工程实施的角度来说，远远还不够具体。对于那些由系统开发工程师负责在线排序架构的团队来说，本文会采用通俗的例子和类比方式来阐述算法部分，希望能够帮助大家更好地理解和掌握排序学习的核心概念。如果是算法工程师团队的同学，可以忽略算法部分的内容。本文的架构部分阐述了美团点评到店餐饮业务线上运行的系统，可以作为在线排序系统架构设计的参考原型直接使用。该架构在服务治理、分层设计的理念，对于保障在线排序架构的高性能、高可用性、易维护性也具有一定的参考价值。包括很多具体环节的实施方案也可以直接进行借鉴，例如流量分桶、流量分级、特征模型、级联模型等等。总之，让开发工程师能够理解排序学习算法方面的核心概念，并为在线架构实施提供细颗粒度的参考架构，是本文的重要目标。算法部分机器学习涉及优化理论、统计学、数值计算等多个领域。这给那些希望学习机器学习核心概念的系统开发工程师带来了很大的障碍。不过，复杂的概念背后往往蕴藏着朴素的道理。本节将尝试采用通俗的例子和类比方式，来对机器学习和排序学习的一些核心概念进行揭秘。机器学习什么是机器学习？典型的机器学习问题，如下图所示：机器学习模型或算法（Model/Algorithm）会根据观察到的特征值（Feature）进行预测，给出预测结果或者目标（Prediction/Target）。这就像是一个函数计算过程，对于特定X值（Feature），算法模型就像是函数，最终的预测结果是Y值。不难理解，机器学习的核心问题就是如何得到预测函数。Wikipedia的对机器学习定义如下：“Machine learning is a subset of artificial intelligence in the field of computer science that often uses statistical techniques to give computers the ability to learn with data, without being explicitly programmed.” 机器学习的最重要本质是从数据中学习，得到预测函数。人类的思考过程以及判断能力本质上也是一种函数处理。从数据或者经验中学习，对于人类来说是一件再平常不过的事情了。例如人们通过观察太阳照射物体影子的长短而发明了日晷，从而具备了计时和制定节气的能力。古埃及人通过尼罗河水的涨落发明了古埃及历法。又比如人们通过观察月亮形状的变化而发明了阴历。如果机器能够像人一样具备从数据中学习的能力，从某种意义上讲，就具备了一定的“智能”。现在需要回答的两个问题就是：到底什么是“智能”？如何让机器具备智能？什么是智能？在回答这个问题之前，我们先看看传统的编程模式为什么不能称之为“智能”。传统的编程模式如下图所示，它一般要经历如下几个阶段：人类通过观察数据（Data）总结经验，转化成知识（Knowledge）。人类将知识转化成规则（Rule）。工程师将规则转化成计算机程序（Program）。在这种编程模式下，如果一个问题被规则覆盖，那么计算机程序就能处理。对于规则不能覆盖的问题，只能由人类来重新思考，制定新规则来解决。所以在这里“智能”角色主要由人类来承担。人类负责解决新问题，所以传统的程序本身不能称之为“智能”。所以，“智能”的一个核心要素就是“举一反三”。如何让机器具备智能？在讨论这个问题之前，可以先回顾一下人类是怎么掌握“举一反三”的能力的？基本流程如下：老师给学生一些题目，指导学生如何解题。学生努力掌握解题思路，尽可能让自己的答案和老师给出的答案一致。学生需要通过一些考试来证明自己具备“举一反三”的能力。如果通过了这些考试，学生将获得毕业证书或者资格从业证书。学生变成一个从业者之后将会面临并且处理很多之前没有碰到过的新问题。机器学习专家从人类的学习过程中获得灵感，通过三个阶段让机器具备“举一反三”的能力。这三个阶段是：训练阶段（Training）、测试阶段（Testing）、推导阶段（Inference）。下面逐一进行介绍：训练阶段训练阶段如下图所示：人类给机器学习模型一些训练样本（X，Y），X代表特征，Y代表目标值。这就好比老师教学生解题，X代表题目，Y代表标准答案。机器学习模型尝试想出一种方法解题。在训练阶段，机器学习的目标就是让损失函数值最小。类比学生尝试让自己解题的答案和老师给的标准答案差别最小，思路如出一辙。测试阶段测试阶段如下图所示：人类给训练好的模型一批完全不同的测试样本（X，Y）。这就好比学生拿到考试试卷。模型进行推导。这个过程就像学生正在考试答题。人类要求测试样本的总损失函数值低于设定的最低目标值。这就像学校要求学生的考试成绩必须及格一样。推导阶段推导阶段如下图所示：在这个阶段机器学习模型只能拿到特征值X，而没有目标值。这就像工作中，人们只是在解决一个个的问题，但不知道正确的结果到底是什么。在推导阶段，机器学习的目标就是预测，给出目标值。排序学习什么是排序学习？Wikipedia的对排序学习的定义如下：“Learning to rank is the application of machine learning, typically supervised, semi-supervised or reinforcement learning, in the construction of ranking models for information retrieval systems. Training data consists of lists of items with some partial order specified between items in each list. This order is typically induced by giving a numerical or ordinal score or a binary judgment (e.g. “relevant” or “not relevant”) for each item. The ranking model’s purpose is to rank, i.e. produce a permutation of items in new, unseen lists in a way which is “similar” to rankings in the training data in some sense.”排序学习是机器学习在信息检索系统里的应用，其目标是构建一个排序模型用于对列表进行排序。排序学习的典型应用包括搜索列表、推荐列表和广告列表等等。列表排序的目标是对多个条目进行排序，这就意味着它的目标值是有结构的。与单值回归和单值分类相比，结构化目标要求解决两个被广泛提起的概念：列表评价指标列表训练算法列表评价指标以关键词搜索返回文章列表为例，这里先分析一下列表评价指标要解决什么挑战。第一个挑战就是定义文章与关键词之间的相关度，这决定了一篇文章在列表中的位置，相关度越高排序就应该越靠前。第二个挑战是当列表中某些文章没有排在正确的位置时候，如何给整个列表打分。举个例子来说，假如对于某个关键词，按照相关性的高低正确排序，文档1、2、3、4、5应该依次排在前5位。现在的挑战就是，如何评估“2，1，3，4，5”和“1，2，5，4，3”这两个列表的优劣呢？列表排序的评价指标体系总来的来说经历了三个阶段，分别是Precision and Recall、Discounted Cumulative Gain(DCG)和Expected Reciprocal Rank(ERR)。我们逐一进行讲解。Precision and Recall(P-R)本评价体系通过准确率（Precision）和召回率（Recall）两个指标来共同衡量列表的排序质量。对于一个请求关键词，所有的文档被标记为相关和不相关两种。Precision的定义如下：Recall的定义如下：举个列子来说，对于某个请求关键词，有200篇文章实际相关。某个排序算法只认为100篇文章是相关的，而这100篇文章里面，真正相关的文章只有80篇。按照以上定义：准确率=80/100=0.8召回率=80/200=0.4。Discounted Cumulative Gain(DCG)P-R的有两个明显缺点：所有文章只被分为相关和不相关两档，分类显然太粗糙。没有考虑位置因素。DCG解决了这两个问题。对于一个关键词，所有的文档可以分为多个相关性级别，这里以rel1，rel2…来表示。文章相关性对整个列表评价指标的贡献随着位置的增加而对数衰减，位置越靠后，衰减越严重。基于DCG评价指标，列表前p个文档的评价指标定义如下：对于排序引擎而言，不同请求的结果列表长度往往不相同。当比较不同排序引擎的综合排序性能时，不同长度请求之间的DCG指标的可比性不高。目前在工业界常用的是Normalized DCG(nDCG)，它假定能够获取到某个请求的前p个位置的完美排序列表，这个完美列表的分值称为Ideal DCG(IDCG)，nDCG等于DCG与IDCG比值。所以nDCG是一个在0到1之间的值。nDCG的定义如下：IDCG的定义如下：|REL|代表按照相关性排序好的最多到位置p的结果列表。Expected Reciprocal Rank(ERR)与DCG相比，除了考虑位置衰减和允许多种相关级别（以R1，R2，R3…来表示）以外，ERR更进了一步，还考虑了排在文档之前所有文档的相关性。举个例子来说，文档A非常相关，排在第5位。如果排在前面的4个文档相关度都不高，那么文档A对列表的贡献就很大。反过来，如果前面4个文档相关度很大，已经完全解决了用户的搜索需求，用户根本就不会点击第5个位置的文档，那么文档A对列表的贡献就不大。ERR的定义如下：列表训练算法做列表排序的工程师们经常听到诸如Pointwise、Pairwise和Listwise的概念。这些是什么东西呢，背后的原理又是什么呢？这里将逐一解密。仍然以关键词搜索文章为例，排序学习算法的目标是为给定的关键词对文章列表进行排序。做为类比，假定有一个学者想要对各科学生排名进行预测。各种角色的对应关系如下：首先我们要告诉学者每个学生的各种属性，这就像我们要告诉排序算法文档特征。对于目标值，我们却有三种方式来告诉学者：对于每个学科，我们可以告诉学者每个学生的成绩。比较每个学生的成绩，学者当然可以算出每个学生的最终排名。这种训练方法被称为Pointwise。对于Pointwise算法，如果最终预测目标是一个实数值，就是一个回归问题。如果目标是概率预测，这就是一个分类问题，例如CTR预估。对于每个学科，我们可以告诉学者任意两个学生的相互排名。根据学生之间排名的情况，学者也可以算出每个学生的最终排名。这种训练方法被称为Pairwise。Pairwise算法的目标是减少逆序的数量，所以是个二分类问题。对于每个学科，我们可以直接告诉学者所有学生的整体排名。这种训练方法被称为Listwise。Listwise算法的目标往往是直接优化nDCG、ERR等评价指标。这三种方法表面看上去有点像玩文字游戏，但是背后却是工程师和科学家们不断探索的结果。最直观的方案是Pointwise算法，例如对于广告CTR预估，在训练阶段需要标注某个文档的点击概率，这相对来说容易。Pairwise算法一个重要分支是Lambda系列，包括LambdaRank、LambdaMart等，它的核心思想是：很多时候我们很难直接计算损失函数的值，但却很容易计算损失函数梯度（Gradient）。这意味着我们很难计算整个列表的nDCG和ERR等指标，但却很容易知道某个文档应该排的更靠前还是靠后。Listwise算法往往效果最好，但是如何为每个请求对所有文档进行标注是一个巨大的挑战。在线排序架构典型的信息检索包含两个阶段：索引阶段和查询阶段。这两个阶段的流程以及相互关系可以用下图来表示：索引阶段的工作是由索引器（Indexer）读取文档（Documents）构建索引（Index）。查询阶段读取索引做为召回，然后交给Topn Retriever进行粗排，在粗排后的结果里面将前n个文档传给Reranker进行精排。这样一个召回、粗排、精排的架构最初是由Google提出来的，也被称为“Two-Phase Scheme”。索引部分属于离线阶段，这里重点讲述在线排序阶段，即查询阶段。三大挑战在线排序架构主要面临三方面的挑战：特征、模型和召回。特征挑战包括特征添加、特征算子、特征归一化、特征离散化、特征获取、特征服务治理等。模型挑战包括基础模型完备性、级联模型、复合目标、A/B实验支持、模型热加载等。召回挑战包括关键词召回、LBS召回、推荐召回、粗排召回等。三大挑战内部包含了非常多更细粒度的挑战，孤立地解决每个挑战显然不是好思路。在线排序作为一个被广泛使用的架构值得采用领域模型进行统一解决。Domain-driven design(DDD)的三个原则分别是：领域聚焦、边界清晰、持续集成。基于以上分析，我们构建了三个在线排序领域模型：召回治理、特征服务治理和在线排序分层模型。召回治理经典的Two-Phase Scheme架构如下图所示，查询阶段应该包含：召回、粗排和精排。但从领域架构设计的角度来讲，粗排对于精排而言也是一种召回。和基于传统的文本搜索不同，美团点评这样的O2O公司需要考虑地理位置和距离等因素，所以基于LBS的召回也是一种召回。与搜索不同，推荐召回往往基于协同过滤来完成的，例如User-Based CF和Item-Based CF。综上所述，召回总体而言分成四大类：关键词召回，我们采用Elasticsearch解决方案。距离召回，我们采用K-D tree的解决方案。粗排召回。推荐类召回。特征服务治理传统的视角认为特征服务应该分为用户特征（User）、查询特征（Query）和文档特征（Doc），如下图：这是比较纯粹的业务视角，并不满足DDD的领域架构设计思路。由于特征数量巨大，我们没有办法为每个特征设计一套方案，但是我们可以把特征进行归类，为几类特征分别设计解决方案。每类技术方案需要统一考虑性能、可用性、存储等因素。从领域视角，特征服务包含四大类：列表类特征。一次请求要求返回实体列表特征，即多个实体，每个实体多个特征。这种特征建议采用内存列表服务，一次性返回所有请求实体的所有特征。避免多次请求，从而导致数量暴增，造成系统雪崩。实体特征。一次请求返回单实体的多个特征。建议采用Redis、Tair等支持多级的Key-Value服务中间键提供服务。上下文特征。包括召回静态分、城市、Query特征等。这些特征直接放在请求内存里面。相似性特征。有些特征是通过计算个体和列表、列表和列表的相似度而得到的。建议提供单独的内存计算服务，避免这类特征的计算影响在线排序性能。本质上这是一种计算转移的设计。在线排序分层模型如下图所示，典型的排序流程包含六个步骤：场景分发（Scene Dispatch）、流量分配（Traffic Distribution）、召回（Recall）、特征抽取（Feature Retrieval）、预测（Prediction）、排序（Ranking）等等。按照DDD的设计原则，我们设计了如下在线排序分层模型，包括：场景分发（Scene Dispatch）、模型分发（Model Distribution）、排序（Ranking）、特征管道（Feature Pipeline）、预测管道（Prediction Pipeline）。我们将逐一进行介绍。场景分发（Scene Dispatch）场景分发一般是指业务类型的分发。对于美团点评而言包括：分平台、分列表、分使用场景等。如下图所示：模型分发（Model Distribution）模型分发的目标是把在线流量分配给不同的实验模型，具体而言要实现三个功能：为模型迭代提供在线流量，负责线上效果收集、验证等。A/B测试，确保不同模型之间流量的稳定、独立和互斥、确保效果归属唯一。确保与其他层的实验流量的正交性。流量的定义是模型分发的一个基础问题。典型的流量包括：访问、用户和设备。如何让一个流量稳定地映射到特定模型上面，流量之间是否有级别？这些是模型分发需要重点解决的问题。流量分桶原理采用如下步骤将流量分配到具体模型上面去：把所有流量分成N个桶。每个具体的流量Hash到某个桶里面去。给每个模型一定的配额，也就是每个策略模型占据对应比例的流量桶。所有策略模型流量配额总和为100%。当流量和模型落到同一个桶的时候，该模型拥有该流量。举个例子来说，如上图所示，所有流量分为32个桶，A、B、C三个模型分别拥有37.5%、25%和37.5%的配额。对应的，A、B、C应该占据12、8和12个桶。为了确保模型和流量的正交性，模型和流量的Hash Key采用不同的前缀。流量分级每个团队的模型分级策略并不相同，这里只给出一个建议模型流量分级：基线流量。本流量用于与其他流量进行对比，以确定新模型的效果是否高于基准线，低于基准线的模型要快速下线。另外，主力流量相对基线流量的效果提升也是衡量算法团队贡献的重要指标。实验流量。该流量主要用于新实验模型。该流量大小设计要注意两点：第一不能太大而伤害线上效果；第二不能太小，流量太小会导致方差太大，不利于做正确的效果判断。潜力流量。如果实验流量在一定周期内效果比较好，可以升级到潜力流量。潜力流量主要是要解决实验流量方差大带来的问题。主力流量。主力流量只有一个，即稳定运行效果最好的流量。如果某个潜力流量长期好于其他潜力流量和主力流量，就可以考虑把这个潜力流量升级为主力流量。做实验的过程中，需要避免新实验流量对老模型流量的冲击。流量群体对于新模型会有一定的适应期，而适应期相对于稳定期的效果一般会差一点。如果因为新实验的上线而导致整个流量群体的模型都更改了，从统计学的角度讲，模型之间的对比关系没有变化。但这可能会影响整个大盘的效果，成本很高。为了解决这个问题，我们的流量分桶模型优先为模型列表前面的模型分配流量，实验模型尽量放在列表尾端。这样实验模型的频繁上下线不影响主力和潜力流量的用户群体。当然当发生模型流量升级的时候，很多流量用户的服务模型都会更改。这种情况并不是问题，因为一方面我们在尝试让更多用户使用更好的模型，另一方面固定让一部分用户长期使用实验流量也是不公平的事情。排序（Ranking）排序模块是特征模块和预测模块的容器，它的主要职责如下：获取所有列表实体进行预测所需特征。将特征交给预测模块进行预测。对所有列表实体按照预测值进行排序。特征管道（Feature Pipeline）特征管道包含特征模型（Feature Model）、表达式（Expression）、原子特征（Atomic Feature）、 特征服务代理（Feature Proxy）、特征服务（Feature Service）。如下图所示：特征管道要解决两个核心问题：给定特征名获取对应特征值。这个过程很复杂，要完成特征名->特征服务->特征类->特征值的转化过程。特征算子问题。模型使用的特征往往是对多个原子特征进行复合运算后的结果。另外，特征离散化、归一化也是特征算子需要解决的问题。完整的特征获取流程如下图所示，具体的流程如下：Ranking模块从FeatureModel里面读取所有的原始特征名。Ranking将所有的原始特征名交给Feature Proxy。Feature Proxy根据特征名的标识去调用对应的Feature Service，并将原始特征值返回给Ranking模块。Ranking模块通过Expression将原始特征转化成复合特征。Ranking模块将所有特征交给级联模型做进一步的转换。特征模型（Feature Model）我们把所有与特征获取和特征算子的相关信息都放在一个类里面，这个类就是FeatureModel，定义如下： //包含特征获取和特征算子计算所需的meta信息 public class FeatureModel { //这是真正用在Prediction里面的特征名 private String featureName; //通过表达式将多种原子特征组合成复合特征。 private IExpression expression; //这些特征名是真正交给特征服务代理(Feature Proxy)去从服务端获取特征值的特征名集合。 private Set<String> originalFeatureNames; //用于指示特征是否需要被级联模型转换 private boolean isTransformedFeature; //是否为one-hot特征 private boolean isOneHotIdFeature; //不同one-hot特征之间往往共享相同的原始特征，这个变量>用于标识原始特征名。 private String oneHotIdKey; //表明本特征是否需要归一化 private boolean isNormalized; }表达式（Expression）表达式的目的是为了将多种原始特征转换成一个新特征，或者对单个原始特征进行运算符转换。我们采用前缀法表达式（Polish Notation）来表示特征算子运算。例如表达式(5-6)7的前缀表达式为 - 5 6 7。复合特征需要指定如下分隔符：复合特征前缀。区别于其他类型特征，我们以“$”表示该特征为复合特征。表达式各元素之间的分隔符，采用“_”来标识。用“O”表示运算符前缀。用“C”表示常数前缀。用“V”表示变量前缀。例如：表达式v1 + 14.2 + (2*(v2+v3)) 将被表示为 $O+_O+_Vv1_C14.2_O*_C2_O+_Vv2_Vv3原子特征（Atomic Feature）原子特征（或者说原始特征）包含特征名和特征值两个部分。原子特征的读取需要由4种实体类共同完成：POJO用于存储特征原始值。例如DealInfo保存了所有与Deal实体相关的特征值，包括Price、maxMealPerson、minMealPerson等等。ScoringValue用于存储从POJO中返回的特征值。特征值包含三种基本类型，即数量型（Quantity）、序数型（Ordinal）、类别型（Categorical）。ScoreEnum实现特征名到特征值的映射。每类原子特征对应于一个ScoreEnum类，特征名通过反射（Reflection）的方式来构建对应的ScoreEnum类。ScoreEnum类和POJO一起共同实现特征值的读取。FeatureScoreEnumContainer用于保存一个算法模型所需所有特征的ScoreEnum。一个典型的例子如下图所示：DealInfo是POJO类。DealInfoScoreEnum是一个ScoreEnum基类。对应于平均用餐人数特征、价格等特征，我们定义了DIAveMealPerson和DIPrice的具体ScoreEnum类。FeatureScoreEnumContainer用于存储某个模型的所有特征的ScoreEnum。复杂系统设计需要充分的利用语言特性和设计模式。建议的优化点有三个：为每个原子特征定义一个ScoreEnum类会导致类数量暴增。优化方式是ScoreEnum基类定义为Enum类型，每个具体特征类为一个枚举值，枚举值继承并实现枚举类的方法。FeatureScoreEnumContainer采用Build设计模式将一个算法模型的所需特征转换成ScoreEnum集合。ScoreEnum从POJO类中读取具体特征值采用的是Command模式。这里稍微介绍一下Command设计模式。Command模式的核心思想是需求方只要求拿到相关信息，不关心谁提供以及怎么提供。具体的提供方接受需求方的需求，负责将结果交给需求方。在特征读取里面，需求方是模型，模型仅仅提供一个特征名（FeatureName），不关心怎么读取对应的特征值。具体的ScoreEnum类是具体的提供方，具体的ScoreEnum从POJO里面读取特定的特征值，并转换成ScoringValue交给模型。特征服务代理（Feature Proxy）特征服务代理负责远程特征获取实施，具体的过程包括：每一大类特征或者一种特征服务有一个FeatureProxy，具体的FeatureProxy负责向特征服务发起请求并获取POJO类。所有的FeatureProxy注册到FeatureServiceContainer类。在具体的一次特征获取中，FeatureServiceContainer根据FeatureName的前缀负责将特征获取分配到不同的FeatureProxy类里面。FeatureProxy根据指定的实体ID列表和特征名从特征服务中读取POJO列表。只有对应ID的指定特征名（keys）的特征值才会被赋值给POJO。这就最大限度地降低了网络读取的成本。预测管道（Prediction Pipeline）预测管道包含：预测（Prediction）、级联模型（Cascade Model）、表达式（Expression）、特征转换（Transform）、计分（Scoring）和原子模型（Atomic Model）。预测（Prediction）预测本质上是对模型的封装。它负责将每个列表实体的特征转化成模型需要的输入格式，让模型进行预测。级联模型（Cascade Model）我们构建级联模型主要是基于两方面的观察：基于Facebook的《Practical Lessons from Predicting Clicks on Ads at Facebook》的Xgboost+LR以及最近很热门的Wide&Deep表明，对一些特征，特别是ID类特征通过树模型或者NN模型进行转化，把转化后的值做为特征值交给预测模型进行预测，往往会能实现更好的效果。有些训练目标是复合目标，每个子目标需要通过不同的模型进行预测。这些子目标之间通过一个简单的表达式计算出最终的预测结果。举例如下图所示，我们自上而下进行讲解：该模型有UserId、CityId、UserFeature、POI等特征。UserId和CityId特征分别通过GBDT和NN模型进行转换（Transform）。转换后的特征和UserFeature、POI等原始特征一起交给NN和LR模型进行算分（Scoring）。最终的预测分值通过表达式Prediction Score = NNScore + LRScore/(1+)来完成。表达式中的 、和是事先设置好的值。原子模型（Atomic Model）在这里原子模型指的是一种原子计算拓扑结构，比如线性模型、树模型和网络模型。常用的模型像Logistic Regression和Linear Regression都是线性模型。GBDT、Random Forest都是树模型。MLP、CNN、RNN都是网络模型。这里定义的原子模型主要的目的是为了工程实施的便利。一个模型被认定为原子模型有如下两个原因：该模型经常做为独立预测模型被使用。该模型有比较完整的实现代码。总结本文总结了作者在美团点评解决到店餐饮个性化信息展示的相关经验，从算法和架构两方面进行阐述。在算法部分，文章采用通俗的例子和类比方式进行讲解，希望非算法工程师能够理解关键的算法概念。架构部分比较详细地阐述了到店餐饮的排序架构。根据我们所掌握的知识，特征治理和召回治理的思路是一种全新的视角，这对于架构排序系统设计有很大的帮助。这种思考方式同样也适用于其他领域模型的构建。与Google提供的经典Two-Phase Scheme架构相比，在线排序分层模型提供了更细颗粒度的抽象原型。该原型细致的阐述了包括分流、A/B测试、特征获取、特征算子、级联模型等一系列经典排序架构问题。同时该原型模型由于采用了分层和层内功能聚焦的思路，所以它比较完美地体现了DDD的三大设计原则，即领域聚焦、边界清晰、持续集成。作者简介刘丁，曾就职于Amazon、TripAdvisor。2014年加入美团，先后负责美团推荐系统、智能筛选系统架构、美团广告系统的架构和上线、完成美团广告运营平台的搭建。目前负责到店餐饮算法策略方向，推进AI在到店餐饮各领域的应用。参考文章：[1]Gamma E, Helm R, Johnson R, et al. Design Patterns-Elements of Reusable Object-Oriented Software. Machinery Industry, 2003.[2]Wikipedia,Learning to rank.[3]Wikipedia,Machine learning.[4]Wikipedia,Precision and recall.[5]Wikipedia,Discounted cumulative gain.[6]Wikipedia,Domain-driven design.[7]Wikipedia,Elasticsearch.[8]Wikipedia,k-d tree.[9]百度百科,太阳历.[10]百度百科,阴历.[11]Xinran H, Junfeng P, Ou J, et al. Practical Lessons from Predicting Clicks on Ads at Facebook[12]Olivier C, Donald M, Ya Z, Pierre G. Expected Reciprocal Rank for Graded Relevance[13]Heng-Tze C, Levent K, et al. Wide & Deep Learning for Recommender Systems ...