阿里深度樹匹配召回體系演進(jìn)

模型能力的升級(jí)需要相應(yīng)的索引結(jié)構(gòu)升級(jí)來支持,我們需要設(shè)計(jì)一個(gè)通用的索引結(jié)構(gòu)，使得能夠支持任意復(fù)雜的模型來做召回。對(duì)于user和item之間復(fù)雜交互，如果不依賴雙塔這樣的模型結(jié)構(gòu)，我們需要什么樣的索引結(jié)構(gòu)?

首先，想到散列表，但是散列表同樣基于距離度量，融合先進(jìn)模型比較困難。加入選擇圖的話，對(duì)于模型結(jié)構(gòu)沒有任何要求，但是圖的一個(gè)問題就是它結(jié)構(gòu)非常復(fù)雜，并且在圖上做檢索很難有確定性的檢索次數(shù)的控制，會(huì)存在指數(shù)爆炸的問題，所以我們最后選擇了樹。樹的結(jié)構(gòu)相對(duì)簡(jiǎn)單，可以通過控制樹的層高來控制檢索次數(shù)。

1. 深度樹匹配的提出

我們提出了深度樹匹配這樣一套技術(shù)，它的基本想法就是我們把所有item商品庫聚合成為一個(gè)層次的興趣樹，把從商品庫里面的檢索轉(zhuǎn)換成一個(gè)在樹上做檢索的過程。
比如說是一個(gè)二叉樹，由于樹的特性，我們能把從十億商品庫里面挑商品的問題轉(zhuǎn)化成在樹上做30層的檢索問題，這樣的話計(jì)算次數(shù)就會(huì)大大減小。

雖然有這樣一個(gè)想法，但是我們后續(xù)需要解決非常多的問題:

• 如何基于樹實(shí)現(xiàn)高效檢索

• 如何做興趣建模保證樹檢索的有效性

• 如何學(xué)習(xí)興趣模型

• 如何構(gòu)建和優(yōu)化樹索引結(jié)構(gòu)

2. 基于樹的高效檢索方法—Beam Search

我們讓葉子節(jié)點(diǎn)表示全部商品，中間節(jié)點(diǎn)表示商品的粗力度的聚合，比如是對(duì)于興趣的聚合，這樣的話我們通過構(gòu)建一個(gè)完全平衡二叉樹就能夠保證這棵樹自頂而下的興趣劃分是從粗到細(xì)的。在這棵樹上就能夠通過Beam Search實(shí)現(xiàn)一個(gè)啟發(fā)式檢索的方法來找topK葉子節(jié)點(diǎn)，它的時(shí)間復(fù)雜度是logN, N是總的商品個(gè)數(shù)，計(jì)算性能是符合線上開銷的,那么一個(gè)很自然的問題就是怎么保證這樣的檢索出的就是全局最優(yōu)?

3. 最大堆樹：支持Beam Search檢索的興趣建模

我們提出了一套方案，要求模型保證用戶的興趣分布必須服從最大堆的性質(zhì)

• 最大堆樹下當(dāng)前層的最優(yōu)TopK孩子節(jié)點(diǎn)的父親必然屬于上層的父輩節(jié)點(diǎn)最優(yōu)TopK；

• 最大堆樹保證Beam Search檢索得到的TopK一定是全局最優(yōu)TopK：從根節(jié)點(diǎn)遞歸向下逐層挑選TopK和擴(kuò)展其子節(jié)點(diǎn)至葉子層。

4. 最大堆樹的模型學(xué)習(xí)

如何學(xué)習(xí)中間節(jié)點(diǎn)的興趣概率？

• 葉子層節(jié)點(diǎn)興趣：用戶對(duì)葉子節(jié)點(diǎn)的行為數(shù)據(jù)構(gòu)建序標(biāo)簽

• 中間層節(jié)點(diǎn)興趣：基于最大堆定義可推導(dǎo)每層的序標(biāo)簽

• 用深度學(xué)習(xí)模型擬合上述兩個(gè)序標(biāo)簽

采樣方案：

• 葉子節(jié)點(diǎn)：用戶行為的隱式反饋來建模葉子節(jié)點(diǎn)的興趣概率

• 中間節(jié)點(diǎn)：

傳遞性：葉子正樣本上溯祖先仍為正樣本

層次全局性：在每一祖先層隨機(jī)負(fù)采樣

5. TDM1.0：容納任意先進(jìn)模型

最大堆樹的訓(xùn)練模式和檢索模式為容納任意先進(jìn)模型提供了堅(jiān)實(shí)的理論基礎(chǔ)和強(qiáng)大的效率保證。我們主要做的工作是在最大堆樹這樣一個(gè)約束之下，我們引入了一些更加先進(jìn)的模型,它跟雙塔模型最大的區(qū)別在于我們模型里面考慮了用戶的特征以及Item特征的交叉，它不是一個(gè)雙塔結(jié)構(gòu)，這里面用戶特征簡(jiǎn)單來說就是用戶歷史的Item行為序列商品特征。商品特征比如商品的ID，如果是在樹里面非葉子層的話，它就是node的ID，在這種模型結(jié)構(gòu)里面，我們把用戶的歷史行為拆分成一系列時(shí)間窗，然后我們?cè)诿總€(gè)時(shí)間窗里面做一個(gè)基于Item embedding的attention，然后得到最終的attention向量。在這種模型結(jié)構(gòu)之下，我們利用到了用戶以及item之間的交叉信息，所以它的模型能力是比雙塔結(jié)構(gòu)強(qiáng)的。

然后在這種情況下，我們?cè)谟?xùn)練的時(shí)候就用之前所說的最大堆樹學(xué)習(xí)的方法，把它拆分成H層的分類問題，在檢索階段的話，直接用Beam search，然后對(duì)這棵樹檢索，得到我們最終想要的結(jié)果。大概在兩年前，我們已經(jīng)到線上后取得了大概兩位數(shù)的一個(gè)性能的提升。

6. TDM2.0：模型&索引聯(lián)合學(xué)習(xí)

在1.0的時(shí)候，我們是在給定的一個(gè)樹的范式之下，只考慮模型的學(xué)習(xí)，但其實(shí)樹的結(jié)構(gòu)本身對(duì)于我們召回結(jié)果有非常大的影響，比如說考慮左下角這樣一個(gè)例子，在一些女裝女鞋男裝拿些這樣個(gè)商品集合里面去構(gòu)造一棵樹，那么在這種情況下，樹構(gòu)造有兩種辦法，一種是把女裝和男鞋做一個(gè)聚合，然后把女鞋和男裝聚合，但這種方法可以看到它得到的聚合其實(shí)是沒有什么意義的。一個(gè)更加合理的劃分方法是把女裝和女鞋、男裝和男鞋劃分到相同的樹節(jié)點(diǎn)，這樣的話對(duì)于高層的非葉子節(jié)點(diǎn)我們就有一些抽象的含義。
所以我們?cè)?.0想要解決的問題就是如何對(duì)模型以及索引做聯(lián)合的學(xué)習(xí)，這個(gè)問題抽象出來，其實(shí)就像右上角所示。所以在這種情況下，我們整個(gè)樹模型的學(xué)習(xí)過程就可以看成是對(duì)兩項(xiàng)的優(yōu)化問題。一項(xiàng)是模型的參數(shù)，也就是對(duì)帶權(quán)二部圖的最大匹配問題，我們用了貪心的算法，最終得到一個(gè)分段式樹學(xué)習(xí)算法。這就是我們?cè)?.0所做的一些基本事情。

7. TDM3.0：模型&索引&檢索聯(lián)合學(xué)習(xí)

不論是1.0還是2.0都有一個(gè)問題就是訓(xùn)練和檢索的目標(biāo)偏差。訓(xùn)練的目標(biāo)：擬合每層興趣多分類的概率。正樣本上溯路徑節(jié)點(diǎn)+同層隨機(jī)負(fù)采樣。檢索目標(biāo)：召回率最大，自頂而下的Beam Search集合,每層只集中在頭部打分節(jié)點(diǎn)部分。

一個(gè)最典型的例子就是我們?cè)谟?xùn)練的時(shí)候，所用到的樣本是一部分上述的正樣本以及一部分隨機(jī)采樣的。沒有考慮到在線上檢索的時(shí)候，實(shí)際上是自頂而下的一個(gè)擴(kuò)展的方式，每層用到的Item其實(shí)是相對(duì)打分比較高的那一部分，這就會(huì)導(dǎo)致我們?cè)跈z索中可能檢索到的某些Item在訓(xùn)練的時(shí)候沒有得到充分的訓(xùn)練。我們希望把線上檢索的目標(biāo)以及過程完全考慮到訓(xùn)練中，保證我們離線訓(xùn)練以及線上使用的一致性。這樣的話，實(shí)際上我們又從興趣分類建模這件事情重新回到對(duì)于集合召回建模這個(gè)事情上。
為了達(dá)到這一點(diǎn)，我們做了以下兩件事情。

對(duì)檢索過程建模：對(duì)齊數(shù)據(jù)分布

首先第一是我們對(duì)采樣方式做了一個(gè)升級(jí)，就是我們不再通過正樣本加負(fù)樣本采樣這套方式來構(gòu)造我們的訓(xùn)練樣本，我們直接對(duì)我們這棵樹做一個(gè)BeamSearch檢索，然后以檢索出來的這些topK集合作為我們的訓(xùn)練樣本。這樣我們?cè)陔x線訓(xùn)練時(shí)和在線Serviceing的樣本產(chǎn)生邏輯以及樣本分布是完全保持一致的。

對(duì)檢索過程建模：對(duì)齊訓(xùn)練目標(biāo)

我們做的第二件事情就是說我們對(duì)于本身模型學(xué)習(xí)的目標(biāo)做了一次改造，確保我們能夠滿足最大堆約束，也就是保證我們的BeamSearch的局部最優(yōu)一定是全局最優(yōu)。我們與之前的方法做一個(gè)對(duì)比，在之前的方法，我們對(duì)于節(jié)點(diǎn)的標(biāo)簽的設(shè)定就是它本身以及它的上溯路徑全部標(biāo)為1，然后剩下的節(jié)點(diǎn)全部標(biāo)為0作為負(fù)樣本，從里面隨機(jī)采樣作為它的訓(xùn)練樣本。我們后來發(fā)現(xiàn)這樣一個(gè)設(shè)定方式，其實(shí)并不符合最大堆的需求，我們對(duì)它做BeamSearch得到的topK也不是全局的最優(yōu)。所以我們換了一個(gè)樣本構(gòu)建的方式，就如右圖所示，比如說這里面藍(lán)色節(jié)點(diǎn)都是我們檢索到的集合，那么我們對(duì)于每個(gè)節(jié)點(diǎn)的標(biāo)簽，我們不只依賴于本身item用戶是否點(diǎn)擊了這個(gè)行為，每個(gè)節(jié)點(diǎn)的標(biāo)簽還依賴于從它的子節(jié)點(diǎn)上溯的標(biāo)簽，以及模型對(duì)于它的子節(jié)點(diǎn)的一個(gè)預(yù)估分?jǐn)?shù)。

8. Beam Search下理論最優(yōu)的訓(xùn)練范式

我們做了上述兩版升級(jí)，就得到了一個(gè)在BeamSearch下理論最優(yōu)的一個(gè)訓(xùn)練方式，具體來說就是我們以BeamSearch來構(gòu)造我們的樣本集合，我們通過基于打分上溯的方式去設(shè)計(jì)每一層樣本的擬合目標(biāo)，還是一個(gè)H層的但是存在上下層依賴的這樣一個(gè)分類問題來做我們的模型的訓(xùn)練。他的訓(xùn)練方法也是一個(gè)循環(huán)迭代的方式，就是我們輸入原始樣本的minibatch，使用當(dāng)前的模型做一遍采樣就是做一BeamSearch檢索，得到每層的樣本，然后采用目標(biāo)構(gòu)建的方式，對(duì)于這個(gè)樣本里面的每一個(gè)節(jié)點(diǎn)得到它的一個(gè)模型的標(biāo)簽，得到標(biāo)簽之后類似一個(gè)二分類問題設(shè)計(jì)一個(gè)loss，然后去對(duì)參數(shù)更新，然后如此反復(fù)迭代，直到收斂。

9. TDM顯著性效果

離線的話我們也做了一些公開數(shù)據(jù)集的測(cè)試，可以看到不管是從1.0、2.0以及3.0，它的召回率都有一個(gè)顯著的漲幅，跟現(xiàn)有的方法，比如說ITemCF以及YoutubeDNN這兩個(gè)經(jīng)典的方法來比，有個(gè)非常大的提升。

我們?cè)诿總€(gè)階段的思考也有一些論文產(chǎn)出，如果大家對(duì)具體的細(xì)節(jié)感興趣的話，可以參考我們的論文。

10. TDM在定向廣告場(chǎng)景落地實(shí)踐

最后，講一下我們?cè)诙ㄏ驈V告場(chǎng)景的一些落地使用，廣告業(yè)務(wù)本身它有非常顯著的一個(gè)特點(diǎn)，就是我們商品召回的有效性其實(shí)比較低的，因?yàn)榇嬖趶V告主的預(yù)算是否花光，商品的上下架以及投放的時(shí)間的影響。所以這導(dǎo)致了在廣告里面，我們候選廣告集合它的動(dòng)態(tài)性非常強(qiáng)，但是TDM這樣的樹結(jié)構(gòu)，是一個(gè)相對(duì)比較靜態(tài)的結(jié)構(gòu)。
所以在實(shí)際中我們采用了靜態(tài)樹結(jié)構(gòu)加動(dòng)態(tài)的正排倒排表這樣一個(gè)實(shí)現(xiàn)方式。具體來說就是我們本身這個(gè)樹的結(jié)構(gòu)是以正常的商品作為葉子，我們?cè)谶@樣的結(jié)構(gòu)之上做了一個(gè)實(shí)時(shí)的商品以及廣告的倒排表，以及廣告本身的信息做正排表。我們?cè)诰€上Servicing的時(shí)候，樹結(jié)構(gòu)是保持不變的，我們根據(jù)實(shí)時(shí)的變化去實(shí)時(shí)更新廣告正排倒排表的順序結(jié)構(gòu)，這樣使得整體能夠保持一個(gè)比較高的召回有效性。