引言

我們正處在一個(gè)知識(shí)爆炸的時(shí)代，伴隨著信息量的劇增和人工智能的蓬勃發(fā)展，互聯(lián)網(wǎng)公司越發(fā)具有強(qiáng)烈的個(gè)性化、智能化信息展示的需求。而信息展示個(gè)性化的典型應(yīng)用主要包括搜索列表、推薦列表、廣告展示等等。

很多人不知道的是，看似簡(jiǎn)單的個(gè)性化信息展示背后，涉及大量的數(shù)據(jù)、算法以及工程架構(gòu)技術(shù)，這些足以讓大部分互聯(lián)網(wǎng)公司望而卻步。究其根本原因，個(gè)性化信息展示背后的技術(shù)是排序?qū)W習(xí)問題（Learning to Rank）。市面上大部分關(guān)于排序?qū)W習(xí)的文章，要么偏算法、要么偏工程。雖然算法方面有一些系統(tǒng)性的介紹文章，但往往對(duì)讀者的數(shù)學(xué)能力要求比較高，也比較偏學(xué)術(shù)，對(duì)于非算法同學(xué)來說門檻非常高。而大部分工程方面的文章又比較粗糙，基本上停留在Google的Two-Phase Scheme階段，從工程實(shí)施的角度來說，遠(yuǎn)遠(yuǎn)還不夠具體。

對(duì)于那些由系統(tǒng)開發(fā)工程師負(fù)責(zé)在線排序架構(gòu)的團(tuán)隊(duì)來說，本文會(huì)采用通俗的例子和類比方式來闡述算法部分，希望能夠幫助大家更好地理解和掌握排序?qū)W習(xí)的核心概念。如果是算法工程師團(tuán)隊(duì)的同學(xué)，可以忽略算法部分的內(nèi)容。本文的架構(gòu)部分闡述了美團(tuán)點(diǎn)評(píng)到店餐飲業(yè)務(wù)線上運(yùn)行的系統(tǒng)，可以作為在線排序系統(tǒng)架構(gòu)設(shè)計(jì)的參考原型直接使用。該架構(gòu)在服務(wù)治理、分層設(shè)計(jì)的理念，對(duì)于保障在線排序架構(gòu)的高性能、高可用性、易維護(hù)性也具有一定的參考價(jià)值。包括很多具體環(huán)節(jié)的實(shí)施方案也可以直接進(jìn)行借鑒，例如流量分桶、流量分級(jí)、特征模型、級(jí)聯(lián)模型等等。

總之，讓開發(fā)工程師能夠理解排序?qū)W習(xí)算法方面的核心概念，并為在線架構(gòu)實(shí)施提供細(xì)顆粒度的參考架構(gòu)，是本文的重要目標(biāo)。

算法部分

機(jī)器學(xué)習(xí)涉及優(yōu)化理論、統(tǒng)計(jì)學(xué)、數(shù)值計(jì)算等多個(gè)領(lǐng)域。這給那些希望學(xué)習(xí)機(jī)器學(xué)習(xí)核心概念的系統(tǒng)開發(fā)工程師帶來了很大的障礙。不過，復(fù)雜的概念背后往往蘊(yùn)藏著樸素的道理。本節(jié)將嘗試采用通俗的例子和類比方式，來對(duì)機(jī)器學(xué)習(xí)和排序?qū)W習(xí)的一些核心概念進(jìn)行揭秘。

機(jī)器學(xué)習(xí)

什么是機(jī)器學(xué)習(xí)？

典型的機(jī)器學(xué)習(xí)問題，如下圖所示：

機(jī)器學(xué)習(xí)模型或算法（Model/Algorithm）會(huì)根據(jù)觀察到的特征值（Feature）進(jìn)行預(yù)測(cè)，給出預(yù)測(cè)結(jié)果或者目標(biāo)（Prediction/Target）。這就像是一個(gè)函數(shù)計(jì)算過程，對(duì)于特定X值（Feature），算法模型就像是函數(shù)，最終的預(yù)測(cè)結(jié)果是Y值。不難理解，機(jī)器學(xué)習(xí)的核心問題就是如何得到預(yù)測(cè)函數(shù)。

Wikipedia的對(duì)機(jī)器學(xué)習(xí)定義如下：

“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.”

機(jī)器學(xué)習(xí)的最重要本質(zhì)是從數(shù)據(jù)中學(xué)習(xí)，得到預(yù)測(cè)函數(shù)。人類的思考過程以及判斷能力本質(zhì)上也是一種函數(shù)處理。從數(shù)據(jù)或者經(jīng)驗(yàn)中學(xué)習(xí)，對(duì)于人類來說是一件再平常不過的事情了。例如人們通過觀察太陽照射物體影子的長(zhǎng)短而發(fā)明了日晷，從而具備了計(jì)時(shí)和制定節(jié)氣的能力。古埃及人通過尼羅河水的漲落發(fā)明了古埃及歷法。

又比如人們通過觀察月亮形狀的變化而發(fā)明了陰歷。

如果機(jī)器能夠像人一樣具備從數(shù)據(jù)中學(xué)習(xí)的能力，從某種意義上講，就具備了一定的“智能”。現(xiàn)在需要回答的兩個(gè)問題就是：

• 到底什么是“智能”？
• 如何讓機(jī)器具備智能？

什么是智能？

在回答這個(gè)問題之前，我們先看看傳統(tǒng)的編程模式為什么不能稱之為“智能”。傳統(tǒng)的編程模式如下圖所示，它一般要經(jīng)歷如下幾個(gè)階段：

• 人類通過觀察數(shù)據(jù)（Data）總結(jié)經(jīng)驗(yàn)，轉(zhuǎn)化成知識(shí)（Knowledge）。
• 人類將知識(shí)轉(zhuǎn)化成規(guī)則（Rule）。
• 工程師將規(guī)則轉(zhuǎn)化成計(jì)算機(jī)程序（Program）。

在這種編程模式下，如果一個(gè)問題被規(guī)則覆蓋，那么計(jì)算機(jī)程序就能處理。對(duì)于規(guī)則不能覆蓋的問題，只能由人類來重新思考，制定新規(guī)則來解決。所以在這里“智能”角色主要由人類來承擔(dān)。人類負(fù)責(zé)解決新問題，所以傳統(tǒng)的程序本身不能稱之為“智能”。

所以，“智能”的一個(gè)核心要素就是“舉一反三”。

如何讓機(jī)器具備智能？

在討論這個(gè)問題之前，可以先回顧一下人類是怎么掌握“舉一反三”的能力的？基本流程如下：

• 老師給學(xué)生一些題目，指導(dǎo)學(xué)生如何解題。學(xué)生努力掌握解題思路，盡可能讓自己的答案和老師給出的答案一致。
• 學(xué)生需要通過一些考試來證明自己具備“舉一反三”的能力。如果通過了這些考試，學(xué)生將獲得畢業(yè)證書或者資格從業(yè)證書。
• 學(xué)生變成一個(gè)從業(yè)者之后將會(huì)面臨并且處理很多之前沒有碰到過的新問題。

機(jī)器學(xué)習(xí)專家從人類的學(xué)習(xí)過程中獲得靈感，通過三個(gè)階段讓機(jī)器具備“舉一反三”的能力。這三個(gè)階段是：訓(xùn)練階段（Training）、測(cè)試階段（Testing）、推導(dǎo)階段（Inference）。下面逐一進(jìn)行介紹。

訓(xùn)練階段

訓(xùn)練階段如下圖所示：

• 人類給機(jī)器學(xué)習(xí)模型一些訓(xùn)練樣本（X，Y），X代表特征，Y代表目標(biāo)值。這就好比老師教學(xué)生解題，X代表題目，Y代表標(biāo)準(zhǔn)答案。
• 機(jī)器學(xué)習(xí)模型嘗試想出一種方法解題。
• 在訓(xùn)練階段，機(jī)器學(xué)習(xí)的目標(biāo)就是讓損失函數(shù)值最小。類比學(xué)生嘗試讓自己解題的答案和老師給的標(biāo)準(zhǔn)答案差別最小，思路如出一轍。

測(cè)試階段

測(cè)試階段如下圖所示：

• 人類給訓(xùn)練好的模型一批完全不同的測(cè)試樣本（X，Y）。這就好比學(xué)生拿到考試試卷。
• 模型進(jìn)行推導(dǎo)。這個(gè)過程就像學(xué)生正在考試答題。
• 人類要求測(cè)試樣本的總損失函數(shù)值低于設(shè)定的最低目標(biāo)值。這就像學(xué)校要求學(xué)生的考試成績(jī)必須及格一樣。

推導(dǎo)階段

推導(dǎo)階段如下圖所示：

• 在這個(gè)階段機(jī)器學(xué)習(xí)模型只能拿到特征值X，而沒有目標(biāo)值。這就像工作中，人們只是在解決一個(gè)個(gè)的問題，但不知道正確的結(jié)果到底是什么。
• 在推導(dǎo)階段，機(jī)器學(xué)習(xí)的目標(biāo)就是預(yù)測(cè)，給出目標(biāo)值。

排序?qū)W習(xí)

什么是排序?qū)W習(xí)？

Wikipedia的對(duì)排序?qū)W習(xí)的定義如下：

“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.”

排序?qū)W習(xí)是機(jī)器學(xué)習(xí)在信息檢索系統(tǒng)里的應(yīng)用，其目標(biāo)是構(gòu)建一個(gè)排序模型用于對(duì)列表進(jìn)行排序。排序?qū)W習(xí)的典型應(yīng)用包括搜索列表、推薦列表和廣告列表等等。

列表排序的目標(biāo)是對(duì)多個(gè)條目進(jìn)行排序，這就意味著它的目標(biāo)值是有結(jié)構(gòu)的。與單值回歸和單值分類相比，結(jié)構(gòu)化目標(biāo)要求解決兩個(gè)被廣泛提起的概念：

• 列表評(píng)價(jià)指標(biāo)
• 列表訓(xùn)練算法

列表評(píng)價(jià)指標(biāo)

以關(guān)鍵詞搜索返回文章列表為例，這里先分析一下列表評(píng)價(jià)指標(biāo)要解決什么挑戰(zhàn)。

• 第一個(gè)挑戰(zhàn)就是定義文章與關(guān)鍵詞之間的相關(guān)度，這決定了一篇文章在列表中的位置，相關(guān)度越高排序就應(yīng)該越靠前。
• 第二個(gè)挑戰(zhàn)是當(dāng)列表中某些文章沒有排在正確的位置時(shí)候，如何給整個(gè)列表打分。舉個(gè)例子來說，假如對(duì)于某個(gè)關(guān)鍵詞，按照相關(guān)性的高低正確排序，文檔1、2、3、4、5應(yīng)該依次排在前5位。現(xiàn)在的挑戰(zhàn)就是，如何評(píng)估“2，1，3，4，5”和“1，2，5，4，3”這兩個(gè)列表的優(yōu)劣呢？

列表排序的評(píng)價(jià)指標(biāo)體系總來的來說經(jīng)歷了三個(gè)階段，分別是Precision and Recall、Discounted Cumulative Gain(DCG)和Expected Reciprocal Rank(ERR)。我們逐一進(jìn)行講解。

Precision and Recall(P-R)

本評(píng)價(jià)體系通過準(zhǔn)確率（Precision）和召回率（Recall）兩個(gè)指標(biāo)來共同衡量列表的排序質(zhì)量。對(duì)于一個(gè)請(qǐng)求關(guān)鍵詞，所有的文檔被標(biāo)記為相關(guān)和不相關(guān)兩種。

Precision的定義如下：

Recall的定義如下：

舉個(gè)列子來說，對(duì)于某個(gè)請(qǐng)求關(guān)鍵詞，有200篇文章實(shí)際相關(guān)。某個(gè)排序算法只認(rèn)為100篇文章是相關(guān)的，而這100篇文章里面，真正相關(guān)的文章只有80篇。按照以上定義：

• 準(zhǔn)確率=⁸⁰?₁₀₀=0.8
• 召回率=⁸⁰?₂₀₀=0.4。

Discounted Cumulative Gain(DCG)

P-R的有兩個(gè)明顯缺點(diǎn)：

• 所有文章只被分為相關(guān)和不相關(guān)兩檔，分類顯然太粗糙。
• 沒有考慮位置因素。

DCG解決了這兩個(gè)問題。對(duì)于一個(gè)關(guān)鍵詞，所有的文檔可以分為多個(gè)相關(guān)性級(jí)別，這里以rel1，rel2…來表示。文章相關(guān)性對(duì)整個(gè)列表評(píng)價(jià)指標(biāo)的貢獻(xiàn)隨著位置的增加而對(duì)數(shù)衰減，位置越靠后，衰減越嚴(yán)重。基于DCG評(píng)價(jià)指標(biāo)，列表前p個(gè)文檔的評(píng)價(jià)指標(biāo)定義如下：

對(duì)于排序引擎而言，不同請(qǐng)求的結(jié)果列表長(zhǎng)度往往不相同。當(dāng)比較不同排序引擎的綜合排序性能時(shí)，不同長(zhǎng)度請(qǐng)求之間的DCG指標(biāo)的可比性不高。目前在工業(yè)界常用的是Normalized DCG(nDCG)，它假定能夠獲取到某個(gè)請(qǐng)求的前p個(gè)位置的完美排序列表，這個(gè)完美列表的分值稱為Ideal DCG(IDCG)，nDCG等于DCG與IDCG比值。所以nDCG是一個(gè)在0到1之間的值。

nDCG的定義如下：

IDCG的定義如下：

|REL|代表按照相關(guān)性排序好的最多到位置p的結(jié)果列表。

Expected Reciprocal Rank(ERR)

與DCG相比，除了考慮位置衰減和允許多種相關(guān)級(jí)別（以R1，R2，R3…來表示）以外，ERR更進(jìn)了一步，還考慮了排在文檔之前所有文檔的相關(guān)性。舉個(gè)例子來說，文檔A非常相關(guān)，排在第5位。如果排在前面的4個(gè)文檔相關(guān)度都不高，那么文檔A對(duì)列表的貢獻(xiàn)就很大。反過來，如果前面4個(gè)文檔相關(guān)度很大，已經(jīng)完全解決了用戶的搜索需求，用戶根本就不會(huì)點(diǎn)擊第5個(gè)位置的文檔，那么文檔A對(duì)列表的貢獻(xiàn)就不大。

ERR的定義如下：

列表訓(xùn)練算法

做列表排序的工程師們經(jīng)常聽到諸如Pointwise、Pairwise和Listwise的概念。這些是什么東西呢，背后的原理又是什么呢？這里將逐一解密。

仍然以關(guān)鍵詞搜索文章為例，排序?qū)W習(xí)算法的目標(biāo)是為給定的關(guān)鍵詞對(duì)文章列表進(jìn)行排序。做為類比，假定有一個(gè)學(xué)者想要對(duì)各科學(xué)生排名進(jìn)行預(yù)測(cè)。各種角色的對(duì)應(yīng)關(guān)系如下：

首先我們要告訴學(xué)者每個(gè)學(xué)生的各種屬性，這就像我們要告訴排序算法文檔特征。對(duì)于目標(biāo)值，我們卻有三種方式來告訴學(xué)者：

• 對(duì)于每個(gè)學(xué)科，我們可以告訴學(xué)者每個(gè)學(xué)生的成績(jī)。比較每個(gè)學(xué)生的成績(jī)，學(xué)者當(dāng)然可以算出每個(gè)學(xué)生的最終排名。這種訓(xùn)練方法被稱為Pointwise。對(duì)于Pointwise算法，如果最終預(yù)測(cè)目標(biāo)是一個(gè)實(shí)數(shù)值，就是一個(gè)回歸問題。如果目標(biāo)是概率預(yù)測(cè)，這就是一個(gè)分類問題，例如CTR預(yù)估。
• 對(duì)于每個(gè)學(xué)科，我們可以告訴學(xué)者任意兩個(gè)學(xué)生的相互排名。根據(jù)學(xué)生之間排名的情況，學(xué)者也可以算出每個(gè)學(xué)生的最終排名。這種訓(xùn)練方法被稱為Pairwise。Pairwise算法的目標(biāo)是減少逆序的數(shù)量，所以是個(gè)二分類問題。
• 對(duì)于每個(gè)學(xué)科，我們可以直接告訴學(xué)者所有學(xué)生的整體排名。這種訓(xùn)練方法被稱為L(zhǎng)istwise。Listwise算法的目標(biāo)往往是直接優(yōu)化nDCG、ERR等評(píng)價(jià)指標(biāo)。

這三種方法表面看上去有點(diǎn)像玩文字游戲，但是背后卻是工程師和科學(xué)家們不斷探索的結(jié)果。最直觀的方案是Pointwise算法，例如對(duì)于廣告CTR預(yù)估，在訓(xùn)練階段需要標(biāo)注某個(gè)文檔的點(diǎn)擊概率，這相對(duì)來說容易。Pairwise算法一個(gè)重要分支是Lambda系列，包括LambdaRank、LambdaMart等，它的核心思想是：很多時(shí)候我們很難直接計(jì)算損失函數(shù)的值，但卻很容易計(jì)算損失函數(shù)梯度（Gradient）。這意味著我們很難計(jì)算整個(gè)列表的nDCG和ERR等指標(biāo)，但卻很容易知道某個(gè)文檔應(yīng)該排的更靠前還是靠后。Listwise算法往往效果最好，但是如何為每個(gè)請(qǐng)求對(duì)所有文檔進(jìn)行標(biāo)注是一個(gè)巨大的挑戰(zhàn)。

在線排序架構(gòu)

典型的信息檢索包含兩個(gè)階段：索引階段和查詢階段。這兩個(gè)階段的流程以及相互關(guān)系可以用下圖來表示：

索引階段的工作是由索引器（Indexer）讀取文檔（Documents）構(gòu)建索引（Index）。

查詢階段讀取索引做為召回，然后交給Topn Retriever進(jìn)行粗排，在粗排后的結(jié)果里面將前n個(gè)文檔傳給Reranker進(jìn)行精排。這樣一個(gè)召回、粗排、精排的架構(gòu)最初是由Google提出來的，也被稱為“Two-Phase Scheme”。

索引部分屬于離線階段，這里重點(diǎn)講述在線排序階段，即查詢階段。

三大挑戰(zhàn)

在線排序架構(gòu)主要面臨三方面的挑戰(zhàn)：特征、模型和召回。

• 特征挑戰(zhàn)包括特征添加、特征算子、特征歸一化、特征離散化、特征獲取、特征服務(wù)治理等。
• 模型挑戰(zhàn)包括基礎(chǔ)模型完備性、級(jí)聯(lián)模型、復(fù)合目標(biāo)、A/B實(shí)驗(yàn)支持、模型熱加載等。
• 召回挑戰(zhàn)包括關(guān)鍵詞召回、LBS召回、推薦召回、粗排召回等。

三大挑戰(zhàn)內(nèi)部包含了非常多更細(xì)粒度的挑戰(zhàn)，孤立地解決每個(gè)挑戰(zhàn)顯然不是好思路。在線排序作為一個(gè)被廣泛使用的架構(gòu)值得采用領(lǐng)域模型進(jìn)行統(tǒng)一解決。Domain-driven design(DDD)的三個(gè)原則分別是：領(lǐng)域聚焦、邊界清晰、持續(xù)集成。

基于以上分析，我們構(gòu)建了三個(gè)在線排序領(lǐng)域模型：召回治理、特征服務(wù)治理和在線排序分層模型。

召回治理

經(jīng)典的Two-Phase Scheme架構(gòu)如下圖所示，查詢階段應(yīng)該包含：召回、粗排和精排。但從領(lǐng)域架構(gòu)設(shè)計(jì)的角度來講，粗排對(duì)于精排而言也是一種召回。和基于傳統(tǒng)的文本搜索不同，美團(tuán)點(diǎn)評(píng)這樣的O2O公司需要考慮地理位置和距離等因素，所以基于LBS的召回也是一種召回。與搜索不同，推薦召回往往基于協(xié)同過濾來完成的，例如User-Based CF和Item-Based CF。

綜上所述，召回總體而言分成四大類：

• 關(guān)鍵詞召回，我們采用Elasticsearch解決方案。
• 距離召回，我們采用K-D tree的解決方案。
• 粗排召回。
• 推薦類召回。

特征服務(wù)治理

傳統(tǒng)的視角認(rèn)為特征服務(wù)應(yīng)該分為用戶特征（User）、查詢特征（Query）和文檔特征（Doc），如下圖：

這是比較純粹的業(yè)務(wù)視角，并不滿足DDD的領(lǐng)域架構(gòu)設(shè)計(jì)思路。由于特征數(shù)量巨大，我們沒有辦法為每個(gè)特征設(shè)計(jì)一套方案，但是我們可以把特征進(jìn)行歸類，為幾類特征分別設(shè)計(jì)解決方案。每類技術(shù)方案需要統(tǒng)一考慮性能、可用性、存儲(chǔ)等因素。從領(lǐng)域視角，特征服務(wù)包含四大類：

• 列表類特征。一次請(qǐng)求要求返回實(shí)體列表特征，即多個(gè)實(shí)體，每個(gè)實(shí)體多個(gè)特征。這種特征建議采用內(nèi)存列表服務(wù)，一次性返回所有請(qǐng)求實(shí)體的所有特征。避免多次請(qǐng)求，從而導(dǎo)致數(shù)量暴增，造成系統(tǒng)雪崩。
• 實(shí)體特征。一次請(qǐng)求返回單實(shí)體的多個(gè)特征。建議采用Redis、Tair等支持多級(jí)的Key-Value服務(wù)中間件提供服務(wù)。
• 上下文特征。包括召回靜態(tài)分、城市、Query特征等。這些特征直接放在請(qǐng)求內(nèi)存里面。
• 相似性特征。有些特征是通過計(jì)算個(gè)體和列表、列表和列表的相似度而得到的。建議提供單獨(dú)的內(nèi)存計(jì)算服務(wù)，避免這類特征的計(jì)算影響在線排序性能。本質(zhì)上這是一種計(jì)算轉(zhuǎn)移的設(shè)計(jì)。

在線排序分層模型

如下圖所示，典型的排序流程包含六個(gè)步驟：場(chǎng)景分發(fā)（Scene Dispatch）、流量分配（Traffic Distribution）、召回（Recall）、特征抽取（Feature Retrieval）、預(yù)測(cè)（Prediction）、排序（Ranking）等等。

按照DDD的設(shè)計(jì)原則，我們?cè)O(shè)計(jì)了如下在線排序分層模型，包括：場(chǎng)景分發(fā)（Scene Dispatch）、模型分發(fā)（Model Distribution）、排序（Ranking）、特征管道（Feature Pipeline）、預(yù)測(cè)管道（Prediction Pipeline）。我們將逐一進(jìn)行介紹。

場(chǎng)景分發(fā)（Scene Dispatch）

場(chǎng)景分發(fā)一般是指業(yè)務(wù)類型的分發(fā)。對(duì)于美團(tuán)點(diǎn)評(píng)而言包括：分平臺(tái)、分列表、分使用場(chǎng)景等。如下圖所示：

模型分發(fā)（Model Distribution）

模型分發(fā)的目標(biāo)是把在線流量分配給不同的實(shí)驗(yàn)?zāi)Ｐ?#xff0c;具體而言要實(shí)現(xiàn)三個(gè)功能：

• 為模型迭代提供在線流量，負(fù)責(zé)線上效果收集、驗(yàn)證等。
• A/B測(cè)試，確保不同模型之間流量的穩(wěn)定、獨(dú)立和互斥、確保效果歸屬唯一。
• 確保與其他層的實(shí)驗(yàn)流量的正交性。

流量的定義是模型分發(fā)的一個(gè)基礎(chǔ)問題。典型的流量包括：訪問、用戶和設(shè)備。

如何讓一個(gè)流量穩(wěn)定地映射到特定模型上面，流量之間是否有級(jí)別？這些是模型分發(fā)需要重點(diǎn)解決的問題。

流量分桶原理

采用如下步驟將流量分配到具體模型上面去：

• 把所有流量分成N個(gè)桶。
• 每個(gè)具體的流量Hash到某個(gè)桶里面去。
• 給每個(gè)模型一定的配額，也就是每個(gè)策略模型占據(jù)對(duì)應(yīng)比例的流量桶。
• 所有策略模型流量配額總和為100%。
• 當(dāng)流量和模型落到同一個(gè)桶的時(shí)候，該模型擁有該流量。

舉個(gè)例子來說，如上圖所示，所有流量分為32個(gè)桶，A、B、C三個(gè)模型分別擁有37.5%、25%和37.5%的配額。對(duì)應(yīng)的，A、B、C應(yīng)該占據(jù)12、8和12個(gè)桶。

為了確保模型和流量的正交性，模型和流量的Hash Key采用不同的前綴。

流量分級(jí)

每個(gè)團(tuán)隊(duì)的模型分級(jí)策略并不相同，這里只給出一個(gè)建議模型流量分級(jí)：

• 基線流量。本流量用于與其他流量進(jìn)行對(duì)比，以確定新模型的效果是否高于基準(zhǔn)線，低于基準(zhǔn)線的模型要快速下線。另外，主力流量相對(duì)基線流量的效果提升也是衡量算法團(tuán)隊(duì)貢獻(xiàn)的重要指標(biāo)。
• 實(shí)驗(yàn)流量。該流量主要用于新實(shí)驗(yàn)?zāi)Ｐ汀Ｔ摿髁看笮≡O(shè)計(jì)要注意兩點(diǎn)：第一不能太大而傷害線上效果；第二不能太小，流量太小會(huì)導(dǎo)致方差太大，不利于做正確的效果判斷。
• 潛力流量。如果實(shí)驗(yàn)流量在一定周期內(nèi)效果比較好，可以升級(jí)到潛力流量。潛力流量主要是要解決實(shí)驗(yàn)流量方差大帶來的問題。
• 主力流量。主力流量只有一個(gè)，即穩(wěn)定運(yùn)行效果最好的流量。如果某個(gè)潛力流量長(zhǎng)期好于其他潛力流量和主力流量，就可以考慮把這個(gè)潛力流量升級(jí)為主力流量。

做實(shí)驗(yàn)的過程中，需要避免新實(shí)驗(yàn)流量對(duì)老模型流量的沖擊。流量群體對(duì)于新模型會(huì)有一定的適應(yīng)期，而適應(yīng)期相對(duì)于穩(wěn)定期的效果一般會(huì)差一點(diǎn)。如果因?yàn)樾聦?shí)驗(yàn)的上線而導(dǎo)致整個(gè)流量群體的模型都更改了，從統(tǒng)計(jì)學(xué)的角度講，模型之間的對(duì)比關(guān)系沒有變化。但這可能會(huì)影響整個(gè)大盤的效果，成本很高。

為了解決這個(gè)問題，我們的流量分桶模型優(yōu)先為模型列表前面的模型分配流量，實(shí)驗(yàn)?zāi)Ｐ捅M量放在列表尾端。這樣實(shí)驗(yàn)?zāi)Ｐ偷念l繁上下線不影響主力和潛力流量的用戶群體。當(dāng)然當(dāng)發(fā)生模型流量升級(jí)的時(shí)候，很多流量用戶的服務(wù)模型都會(huì)更改。這種情況并不是問題，因?yàn)橐环矫嫖覀冊(cè)趪L試讓更多用戶使用更好的模型，另一方面固定讓一部分用戶長(zhǎng)期使用實(shí)驗(yàn)流量也是不公平的事情。

排序（Ranking）

排序模塊是特征模塊和預(yù)測(cè)模塊的容器，它的主要職責(zé)如下：

• 獲取所有列表實(shí)體進(jìn)行預(yù)測(cè)所需特征。
• 將特征交給預(yù)測(cè)模塊進(jìn)行預(yù)測(cè)。
• 對(duì)所有列表實(shí)體按照預(yù)測(cè)值進(jìn)行排序。

特征管道（Feature Pipeline）

特征管道包含特征模型（Feature Model）、表達(dá)式（Expression）、原子特征（Atomic Feature）、 特征服務(wù)代理（Feature Proxy）、特征服務(wù)（Feature Service）。如下圖所示：

特征管道要解決兩個(gè)核心問題：

• 給定特征名獲取對(duì)應(yīng)特征值。這個(gè)過程很復(fù)雜，要完成特征名->特征服務(wù)->特征類->特征值的轉(zhuǎn)化過程。
• 特征算子問題。模型使用的特征往往是對(duì)多個(gè)原子特征進(jìn)行復(fù)合運(yùn)算后的結(jié)果。另外，特征離散化、歸一化也是特征算子需要解決的問題。

完整的特征獲取流程如下圖所示，具體的流程如下：

• Ranking模塊從FeatureModel里面讀取所有的原始特征名。
• Ranking將所有的原始特征名交給Feature Proxy。
• Feature Proxy根據(jù)特征名的標(biāo)識(shí)去調(diào)用對(duì)應(yīng)的Feature Service，并將原始特征值返回給Ranking模塊。
• Ranking模塊通過Expression將原始特征轉(zhuǎn)化成復(fù)合特征。
• Ranking模塊將所有特征交給級(jí)聯(lián)模型做進(jìn)一步的轉(zhuǎn)換。

特征模型（Feature Model）

我們把所有與特征獲取和特征算子的相關(guān)信息都放在一個(gè)類里面，這個(gè)類就是FeatureModel，定義如下：

//包含特征獲取和特征算子計(jì)算所需的meta信息 public class FeatureModel { //這是真正用在Prediction里面的特征名 private String featureName; //通過表達(dá)式將多種原子特征組合成復(fù)合特征。private IExpression expression; //這些特征名是真正交給特征服務(wù)代理(Feature Proxy)去從服務(wù)端獲取特征值的特征名集合。private Set<String> originalFeatureNames;//用于指示特征是否需要被級(jí)聯(lián)模型轉(zhuǎn)換 private boolean isTransformedFeature; //是否為one-hot特征 private boolean isOneHotIdFeature;//不同one-hot特征之間往往共享相同的原始特征，這個(gè)變量>用于標(biāo)識(shí)原始特征名。 private String oneHotIdKey; //表明本特征是否需要?dú)w一化private boolean isNormalized; }

表達(dá)式（Expression）

表達(dá)式的目的是為了將多種原始特征轉(zhuǎn)換成一個(gè)新特征，或者對(duì)單個(gè)原始特征進(jìn)行運(yùn)算符轉(zhuǎn)換。我們采用前綴法表達(dá)式（Polish Notation）來表示特征算子運(yùn)算。例如表達(dá)式(5-6)*7的前綴表達(dá)式為* - 5 6 7。

復(fù)合特征需要指定如下分隔符：

• 復(fù)合特征前綴。區(qū)別于其他類型特征，我們以“$”表示該特征為復(fù)合特征。
• 表達(dá)式各元素之間的分隔符，采用“_”來標(biāo)識(shí)。
• 用“O”表示運(yùn)算符前綴。
• 用“C”表示常數(shù)前綴。
• 用“V”表示變量前綴。

例如：表達(dá)式v1 + 14.2 + (2*(v2+v3)) 將被表示為 $O+_O+_Vv1_C14.2_O*_C2_O+_Vv2_Vv3

原子特征（Atomic Feature）

原子特征（或者說原始特征）包含特征名和特征值兩個(gè)部分。原子特征的讀取需要由4種實(shí)體類共同完成：

• POJO用于存儲(chǔ)特征原始值。例如DealInfo保存了所有與Deal實(shí)體相關(guān)的特征值，包括Price、maxMealPerson、minMealPerson等等。
• ScoringValue用于存儲(chǔ)從POJO中返回的特征值。特征值包含三種基本類型，即數(shù)量型（Quantity）、序數(shù)型（Ordinal）、類別型（Categorical）。
• ScoreEnum實(shí)現(xiàn)特征名到特征值的映射。每類原子特征對(duì)應(yīng)于一個(gè)ScoreEnum類，特征名通過反射（Reflection）的方式來構(gòu)建對(duì)應(yīng)的ScoreEnum類。ScoreEnum類和POJO一起共同實(shí)現(xiàn)特征值的讀取。
• FeatureScoreEnumContainer用于保存一個(gè)算法模型所需所有特征的ScoreEnum。

一個(gè)典型的例子如下圖所示：

• DealInfo是POJO類。
• DealInfoScoreEnum是一個(gè)ScoreEnum基類。對(duì)應(yīng)于平均用餐人數(shù)特征、價(jià)格等特征，我們定義了DIAveMealPerson和DIPrice的具體ScoreEnum類。
• FeatureScoreEnumContainer用于存儲(chǔ)某個(gè)模型的所有特征的ScoreEnum。

復(fù)雜系統(tǒng)設(shè)計(jì)需要充分的利用語言特性和設(shè)計(jì)模式。建議的優(yōu)化點(diǎn)有三個(gè)：

• 為每個(gè)原子特征定義一個(gè)ScoreEnum類會(huì)導(dǎo)致類數(shù)量暴增。優(yōu)化方式是ScoreEnum基類定義為Enum類型，每個(gè)具體特征類為一個(gè)枚舉值，枚舉值繼承并實(shí)現(xiàn)枚舉類的方法。
• FeatureScoreEnumContainer采用Build設(shè)計(jì)模式將一個(gè)算法模型的所需特征轉(zhuǎn)換成ScoreEnum集合。
• ScoreEnum從POJO類中讀取具體特征值采用的是Command模式。

這里稍微介紹一下Command設(shè)計(jì)模式。Command模式的核心思想是需求方只要求拿到相關(guān)信息，不關(guān)心誰提供以及怎么提供。具體的提供方接受需求方的需求，負(fù)責(zé)將結(jié)果交給需求方。

在特征讀取里面，需求方是模型，模型僅僅提供一個(gè)特征名（FeatureName），不關(guān)心怎么讀取對(duì)應(yīng)的特征值。具體的ScoreEnum類是具體的提供方，具體的ScoreEnum從POJO里面讀取特定的特征值，并轉(zhuǎn)換成ScoringValue交給模型。

特征服務(wù)代理（Feature Proxy）

特征服務(wù)代理負(fù)責(zé)遠(yuǎn)程特征獲取實(shí)施，具體的過程包括：

• 每一大類特征或者一種特征服務(wù)有一個(gè)FeatureProxy，具體的FeatureProxy負(fù)責(zé)向特征服務(wù)發(fā)起請(qǐng)求并獲取POJO類。
• 所有的FeatureProxy注冊(cè)到FeatureServiceContainer類。
• 在具體的一次特征獲取中，FeatureServiceContainer根據(jù)FeatureName的前綴負(fù)責(zé)將特征獲取分配到不同的FeatureProxy類里面。
• FeatureProxy根據(jù)指定的實(shí)體ID列表和特征名從特征服務(wù)中讀取POJO列表。只有對(duì)應(yīng)ID的指定特征名（keys）的特征值才會(huì)被賦值給POJO。這就最大限度地降低了網(wǎng)絡(luò)讀取的成本。

預(yù)測(cè)管道（Prediction Pipeline）

預(yù)測(cè)管道包含：預(yù)測(cè)（Prediction）、級(jí)聯(lián)模型（Cascade Model）、表達(dá)式（Expression）、特征轉(zhuǎn)換（Transform）、計(jì)分（Scoring）和原子模型（Atomic Model）。

預(yù)測(cè)（Prediction）

預(yù)測(cè)本質(zhì)上是對(duì)模型的封裝。它負(fù)責(zé)將每個(gè)列表實(shí)體的特征轉(zhuǎn)化成模型需要的輸入格式，讓模型進(jìn)行預(yù)測(cè)。

級(jí)聯(lián)模型（Cascade Model）

我們構(gòu)建級(jí)聯(lián)模型主要是基于兩方面的觀察：

• 基于Facebook的《Practical Lessons from Predicting Clicks on Ads at Facebook》的Xgboost+LR以及最近很熱門的Wide&Deep表明，對(duì)一些特征，特別是ID類特征通過樹模型或者NN模型進(jìn)行轉(zhuǎn)化，把轉(zhuǎn)化后的值做為特征值交給預(yù)測(cè)模型進(jìn)行預(yù)測(cè)，往往會(huì)能實(shí)現(xiàn)更好的效果。
• 有些訓(xùn)練目標(biāo)是復(fù)合目標(biāo)，每個(gè)子目標(biāo)需要通過不同的模型進(jìn)行預(yù)測(cè)。這些子目標(biāo)之間通過一個(gè)簡(jiǎn)單的表達(dá)式計(jì)算出最終的預(yù)測(cè)結(jié)果。

舉例如下圖所示，我們自上而下進(jìn)行講解：

• 該模型有UserId、CityId、UserFeature、POI等特征。
• UserId和CityId特征分別通過GBDT和NN模型進(jìn)行轉(zhuǎn)換（Transform）。
• 轉(zhuǎn)換后的特征和UserFeature、POI等原始特征一起交給NN和LR模型進(jìn)行算分（Scoring）。
• 最終的預(yù)測(cè)分值通過表達(dá)式Prediction Score = α*NNScore + β*LRScore/(1+γ)來完成。表達(dá)式中的 α 、β和γ是事先設(shè)置好的值。

原子模型（Atomic Model）

在這里原子模型指的是一種原子計(jì)算拓?fù)浣Y(jié)構(gòu)，比如線性模型、樹模型和網(wǎng)絡(luò)模型。

常用的模型像Logistic Regression和Linear Regression都是線性模型。GBDT、Random Forest都是樹模型。MLP、CNN、RNN都是網(wǎng)絡(luò)模型。

這里定義的原子模型主要的目的是為了工程實(shí)施的便利。一個(gè)模型被認(rèn)定為原子模型有如下兩個(gè)原因：

• 該模型經(jīng)常做為獨(dú)立預(yù)測(cè)模型被使用。
• 該模型有比較完整的實(shí)現(xiàn)代碼。

總結(jié)

本文總結(jié)了作者在美團(tuán)點(diǎn)評(píng)解決到店餐飲個(gè)性化信息展示的相關(guān)經(jīng)驗(yàn)，從算法和架構(gòu)兩方面進(jìn)行闡述。在算法部分，文章采用通俗的例子和類比方式進(jìn)行講解，希望非算法工程師能夠理解關(guān)鍵的算法概念。架構(gòu)部分比較詳細(xì)地闡述了到店餐飲的排序架構(gòu)。

根據(jù)我們所掌握的知識(shí)，特征治理和召回治理的思路是一種全新的視角，這對(duì)于架構(gòu)排序系統(tǒng)設(shè)計(jì)有很大的幫助。這種思考方式同樣也適用于其他領(lǐng)域模型的構(gòu)建。與Google提供的經(jīng)典Two-Phase Scheme架構(gòu)相比，在線排序分層模型提供了更細(xì)顆粒度的抽象原型。該原型細(xì)致的闡述了包括分流、A/B測(cè)試、特征獲取、特征算子、級(jí)聯(lián)模型等一系列經(jīng)典排序架構(gòu)問題。同時(shí)該原型模型由于采用了分層和層內(nèi)功能聚焦的思路，所以它比較完美地體現(xiàn)了DDD的三大設(shè)計(jì)原則，即領(lǐng)域聚焦、邊界清晰、持續(xù)集成。

作者簡(jiǎn)介

• 劉丁，目前負(fù)責(zé)到店餐飲算法策略方向，推進(jìn)AI在到店餐飲各領(lǐng)域的應(yīng)用。2014年加入美團(tuán)，先后負(fù)責(zé)美團(tuán)推薦系統(tǒng)、智能篩選系統(tǒng)架構(gòu)、美團(tuán)廣告系統(tǒng)的架構(gòu)和上線、完成美團(tuán)廣告運(yùn)營平臺(tái)的搭建。曾就職于Amazon、TripAdvisor等公司。

參考文章：

• [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

總結(jié)

以上是生活随笔為你收集整理的深入浅出排序学习：写给程序员的算法系统开发实践的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。