基于二叉樹結構采樣預估的召回模型框架

靳甲廣?

摘要：在廣告或者推薦系統(tǒng)的召回階段，通常會包含百萬到億級別的候選集，采樣和預估就成為很重要的問題；傳統(tǒng)的召回模型會做隨機負采樣，這種方法采樣的數(shù)據(jù)分布和整體樣本分布可能存在不一致，影響模型訓練效果，在預估服務時線上infer性能也是嚴峻的考驗；針對這兩個問題，我們提出了基于樹結構的采樣預估服務，把全量候選集通過層次聚類構建到一顆二叉樹中，所有物料掛在的樹的葉子結點，通過二叉樹采樣可能無偏的來到所有物料，并且線上infer時間復雜度從O（n）降低到O（log（n）），整體提升了模型訓練效果和預估時間開銷。

關鍵詞：召回模型，廣告系統(tǒng)，推薦系統(tǒng)，二叉樹

一、背景介紹

在多階段廣告系統(tǒng)中，召回技術的任務是從百萬-億量級的全庫候選廣告集合中挑選千級別的優(yōu)質廣告，供給粗排和精排進行更高精度的廣告候選集挑選。

當前人們普遍認同召回技術已經(jīng)發(fā)展了兩代，并正向第三代新技術的發(fā)展進程中：

第一代：啟發(fā)式規(guī)則召回技術，例如基于ItemCF的U2I2I召回，召回用戶訪問過的廣告的相類似廣告。

優(yōu)點是實現(xiàn)簡單，推斷高效。實現(xiàn)為兩階段：

1.用戶的歷史行為（點擊、購買等）獲得觸發(fā)廣告（Trigger Item）。

2.在候選廣告集中檢索與觸發(fā)廣告最相似的廣告。相似度可以離線預先計算好。

缺點是：

1.不是全庫，而是針對歷史行為相關的相似廣告集合被召回，新穎性不夠，對冷啟動不友好。

2.模型過于簡單，精度有限，泛化能力不夠。

3. 兩階段實現(xiàn)，無法實現(xiàn)聯(lián)合優(yōu)化，影響效果。

第二代：基于Embedding的向量內(nèi)積召回模型。廣告的檢索變成了用戶embedding向量和廣告embedding向量的內(nèi)置。它的優(yōu)點是實現(xiàn)為雙塔結構，借助ANN可以實現(xiàn)全庫近似計算，或者使用GPU實現(xiàn)全庫暴力算。

1.一階段端到端模型訓練，把用戶和item的各種輔助學習表示成統(tǒng)一空間的向量表示，精度提高，泛化性更好。

2.用戶和item的向量可以準實時計算和更新，實時性更好

雖然以全量暴力算為代表的雙塔模型在廣告業(yè)務中取得了很多收益，但是它的缺點也是很明顯：雙塔建模中用戶和item特征沒有價差，向量內(nèi)置的計算score的方式導致模型表達能力有限。雖然使用MLP能獲取的進一步收益，但它比更多的attention或者復雜模型表達能力要差不少。

未來的先進模型召回技術必須滿足以下核心訴求：

1.檢索效率高：在線推斷能夠針對全庫召回：能對候選廣告集合進行全量檢索，提高召回技術的效果天花板。

2.模型表達能力強：能夠克服雙塔模型結構的缺陷，提高召回的泛化性。

3.一致性：選出的廣告能被后端的粗排和精排也認為優(yōu)質。

在現(xiàn)有算力約束下，模型表達能力可能制約和限制召回模型的檢索效率。如果模型復雜度增加，表達能力變強了，可能使得能夠檢索的物料范圍受到限制。因此，只有改進檢索效率，才能有提高模型表達能力的先決條件。

二、召回樹模型框架

（一）什么是召回樹模型

顧名思義，召回樹模型是采用樹作為提高檢索效率的索引結構，同時使用一般深度學習模型取代常用的雙塔模型結構提高模型的表達能力。

樹模型把全庫的廣告候選集自底向上構建一顆二叉樹，葉子節(jié)點代表全庫的廣告候選集，中間節(jié)點是虛擬節(jié)點，代表了滿足一定特性的廣告子集的聚類。

使用二叉樹后，數(shù)模型的檢索效率由O（N）提高到O（logN）。檢索包含1億個候選廣告的集合只需要27步計算。

（二）類最大堆樹 Max-heap like tree

類最大堆樹是召回數(shù)模型的一個發(fā)明，它保證了樹的檢索是可以通過采樣beam search的方法獲得top-k的最優(yōu)候選廣告集。

類最大堆樹脂的是一棵樹，它的第j層的中間節(jié)點 nj 被給定用戶 u 感興趣概率 P（nj |u ）由它的子節(jié)點（即第 j+1層的節(jié)點）的最大值確定。

檢索時，只需要從根節(jié)點開始，找出p（n|u）的所有子節(jié)點進行概率計算，排序后選取top-k個節(jié)點繼續(xù)檢索，直到找到top-k個葉子節(jié)點，作為最后的召回結果。

有了類最大堆的性質，可以保證這種檢索方法得到的top-k結果必定是全局最優(yōu)的top-k結果，即使用更少的檢索代價達到了全庫檢索的效果。

（三）召回樹模型的初始化和模型訓練

召回樹的初始化過程是使用類目信息完成的：時候選集的物料的類目排序，相同的類目放在同一桶里隨機排序，然后把這些分桶的物料進行二分。此過程循環(huán)，直到每個二分里只剩下一個物料。最終結果是一顆自頂向下構建的近似或完全的二叉樹。

召回樹模型的訓練是一個類似EM的算法：

1.構建一個初始二叉樹，在樹上訓練模型直到收斂。

2.通過葉子節(jié)點的embedding重新構建一顆新樹。

3.使用新構建的樹訓練收斂的模型。

重復2、3步驟，不斷dump出模型放到線上推斷，具體算法入Algorithm 1。

三、How：實現(xiàn)與實踐

（一） 系統(tǒng)結構

主要部分：

1. Embedding Producer （Photo Emb Server）：產(chǎn)生Photo Embedding。

2.Tree Calc Server：? 根據(jù)Embedding Producer構建全量和增量的召回樹。

3.Offline Tree Server：服務模型訓練負采樣的Tree Server。

4. Online Tree server/Predict Server：用于召回服務的在線推斷。

5. Embedding Server：存儲User/Item的Embedding。

6.離線模型訓練/Dragon負采樣。

（二） 召回樹的構建

在實踐過程中，召回樹的構建與論文實現(xiàn)不同，而是結合快手主站、特別是商業(yè)化的業(yè)務特點進行改造。

1.建樹過程

在召回樹的構建上，建樹的過程如下：

（1）Embedding Producer使用已有的線上雙塔模型，加載DSP的物料庫，每個一定周期（例如15分鐘）產(chǎn)生全庫物料的Embedding，并聚合層photo粒度。

（2）Calc Tree server通過BTQ監(jiān)聽Embedding Producer產(chǎn)生的Embedding變化，并通過gRPC向Item Service獲取creative_id對應的Photo Service。

（3） Calc Tree Server 每天構建一個全量的召回樹，并在一定周期（1小時或者15分鐘）內(nèi)增量更新樹。

（4）通過BTQ，Offline Tree Server和Online Tree Server獲得最新的召回樹，并分別進行離線和在線的模型訓練與推斷。

2. K-means建樹

在構建樹的過程中，使用K-means算法對Embedding進行完全二叉樹的構建。大致流程如下：

（1）使用K-means算法對所有的Embedding進行聚類，得到兩個類，分別對應left tree和right tree。

（2）使用平衡算法，使得左右兩棵樹的物料一樣多。

（3）分別對left tree和right tree進一步進行聚類并執(zhí)行平衡算法，每棵樹得到left子樹和right子樹。

（4）重復步驟（3），直到每棵子樹只包含一個或兩個節(jié)點停止。

k-means建樹之后，還需要進行兩步處理：

（1）把物料對應的都節(jié)點都下發(fā)到葉子節(jié)點；

（2）根據(jù)葉子節(jié)點更新中間節(jié)點的信息，例如生成中間節(jié)點的虛擬ID特征，虛擬統(tǒng)計信息（例如子節(jié)點的click數(shù)的平均值作為中間節(jié)點的click樹）。

對于增量建樹，廣告動態(tài)插入到樹中，并從根節(jié)點開始依次尋找最相似的中間節(jié)點插入，直到倒數(shù)第一層，作為葉子節(jié)點插入到召回樹中

3. 樹的采樣

在離線的模型訓練中，召回樹模型與一般模型訓練的差別在于樹的采樣：從在線數(shù)據(jù)流中讀取到訓練樣本依次經(jīng)過以下過程：

（1）從樣本得到樣本的label。當前采用多標簽Label，例如 未下發(fā)、下發(fā)未曝光、下發(fā)并曝光、曝光并點擊的樣本的label

（2）使用負采樣Processor把樣本通過gRPC服務調用offline Tree Server接口對樣本進行采樣。

（3）使用特征抽取的Processor對負采樣processor返回的數(shù)據(jù)進行特征抽取。

（4）抽取后的特征發(fā)送給訓練平臺進行在線模型訓練。

四、結束語

綜上，召回樹模型可以有效的提升訓練采樣樣本和真實分布一致性，引入更多的真實和虛擬節(jié)點樣本訓練模型，使得模型學習更充分無偏，并在在線預估時提升整體性能。

作者單位：靳甲廣? ? 北京快手科技有限公司

參? 考? 文? 獻

[1] Jui-Ting Huang. Embedding-based Retrieval in Facebook Search， KDD 2020，F(xiàn)acebook

[2] Han Zhu. Learning Tree-based Deep Model for Recommender Systems，Alibaba