靳甲廣?

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

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

一、背景介紹

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

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

第一代：?jiǎn)l(fā)式規(guī)則召回技術(shù)，例如基于ItemCF的U2I2I召回，召回用戶訪問(wèn)過(guò)的廣告的相類似廣告。

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

1.用戶的歷史行為（點(diǎn)擊、購(gòu)買(mǎi)等）獲得觸發(fā)廣告（Trigger Item）。

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

缺點(diǎn)是：

1.不是全庫(kù)，而是針對(duì)歷史行為相關(guān)的相似廣告集合被召回，新穎性不夠，對(duì)冷啟動(dòng)不友好。

2.模型過(guò)于簡(jiǎn)單，精度有限，泛化能力不夠。

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

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

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

2.用戶和item的向量可以準(zhǔn)實(shí)時(shí)計(jì)算和更新，實(shí)時(shí)性更好

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

未來(lái)的先進(jìn)模型召回技術(shù)必須滿足以下核心訴求：

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

2.模型表達(dá)能力強(qiáng)：能夠克服雙塔模型結(jié)構(gòu)的缺陷，提高召回的泛化性。

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

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

二、召回樹(shù)模型框架

（一）什么是召回樹(shù)模型

顧名思義，召回樹(shù)模型是采用樹(shù)作為提高檢索效率的索引結(jié)構(gòu)，同時(shí)使用一般深度學(xué)習(xí)模型取代常用的雙塔模型結(jié)構(gòu)提高模型的表達(dá)能力。

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

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

（二）類最大堆樹(shù) Max-heap like tree

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

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

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

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

（三）召回樹(shù)模型的初始化和模型訓(xùn)練

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

召回樹(shù)模型的訓(xùn)練是一個(gè)類似EM的算法：

1.構(gòu)建一個(gè)初始二叉樹(shù)，在樹(shù)上訓(xùn)練模型直到收斂。

2.通過(guò)葉子節(jié)點(diǎn)的embedding重新構(gòu)建一顆新樹(shù)。

3.使用新構(gòu)建的樹(shù)訓(xùn)練收斂的模型。

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

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

（一） 系統(tǒng)結(jié)構(gòu)

主要部分：

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

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

3.Offline Tree Server：服務(wù)模型訓(xùn)練負(fù)采樣的Tree Server。

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

5. Embedding Server：存儲(chǔ)User/Item的Embedding。

6.離線模型訓(xùn)練/Dragon負(fù)采樣。

（二） 召回樹(shù)的構(gòu)建

在實(shí)踐過(guò)程中，召回樹(shù)的構(gòu)建與論文實(shí)現(xiàn)不同，而是結(jié)合快手主站、特別是商業(yè)化的業(yè)務(wù)特點(diǎn)進(jìn)行改造。

1.建樹(shù)過(guò)程

在召回樹(shù)的構(gòu)建上，建樹(shù)的過(guò)程如下：

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

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

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

（4）通過(guò)BTQ，Offline Tree Server和Online Tree Server獲得最新的召回樹(shù)，并分別進(jìn)行離線和在線的模型訓(xùn)練與推斷。

2. K-means建樹(shù)

在構(gòu)建樹(shù)的過(guò)程中，使用K-means算法對(duì)Embedding進(jìn)行完全二叉樹(shù)的構(gòu)建。大致流程如下：

（1）使用K-means算法對(duì)所有的Embedding進(jìn)行聚類，得到兩個(gè)類，分別對(duì)應(yīng)left tree和right tree。

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

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

（4）重復(fù)步驟（3），直到每棵子樹(shù)只包含一個(gè)或兩個(gè)節(jié)點(diǎn)停止。

k-means建樹(shù)之后，還需要進(jìn)行兩步處理：

（1）把物料對(duì)應(yīng)的都節(jié)點(diǎn)都下發(fā)到葉子節(jié)點(diǎn)；

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

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

3. 樹(shù)的采樣

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

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

（2）使用負(fù)采樣Processor把樣本通過(guò)gRPC服務(wù)調(diào)用offline Tree Server接口對(duì)樣本進(jìn)行采樣。

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

（4）抽取后的特征發(fā)送給訓(xùn)練平臺(tái)進(jìn)行在線模型訓(xùn)練。

四、結(jié)束語(yǔ)

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

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

參? 考? 文? 獻(xiàn)

[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