阿里深度樹匹配召回體系演進

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

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

1. 深度樹匹配的提出

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

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

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

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

• 如何學習興趣模型

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

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

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

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

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

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

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

4. 最大堆樹的模型學習

如何學習中間節(jié)點的興趣概率？

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

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

• 用深度學習模型擬合上述兩個序標簽

采樣方案：

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

• 中間節(jié)點：

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

層次全局性：在每一祖先層隨機負采樣

5. TDM1.0：容納任意先進模型

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

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

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

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

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

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

一個最典型的例子就是我們在訓練的時候，所用到的樣本是一部分上述的正樣本以及一部分隨機采樣的。沒有考慮到在線上檢索的時候，實際上是自頂而下的一個擴展的方式，每層用到的Item其實是相對打分比較高的那一部分，這就會導致我們在檢索中可能檢索到的某些Item在訓練的時候沒有得到充分的訓練。我們希望把線上檢索的目標以及過程完全考慮到訓練中，保證我們離線訓練以及線上使用的一致性。這樣的話，實際上我們又從興趣分類建模這件事情重新回到對于集合召回建模這個事情上。
為了達到這一點，我們做了以下兩件事情。

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

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

對檢索過程建模：對齊訓練目標

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

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

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

9. TDM顯著性效果

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

我們在每個階段的思考也有一些論文產(chǎn)出，如果大家對具體的細節(jié)感興趣的話，可以參考我們的論文。

10. TDM在定向廣告場景落地實踐

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