一. 背景

搜索、推薦和廣告看似業(yè)務(wù)形態(tài)不同，其實(shí)技術(shù)組成卻是非常相通的。從推薦的視角看，搜索可以認(rèn)為是一種帶query相關(guān)性約束的推薦，而廣告則是疊加了廣告主營銷意愿（價(jià)格）約束的推薦，所以推薦技術(shù)的創(chuàng)新對推動搜索、推薦和廣告業(yè)務(wù)技術(shù)的整體發(fā)展具有基礎(chǔ)性的作用。
從技術(shù)演進(jìn)的角度，推薦算法近年來也在不斷地更新?lián)Q代。從限定在一個(gè)有限的歷史興趣范疇內(nèi)推薦的第一代基于統(tǒng)計(jì)的啟發(fā)式規(guī)則方法(代表算法Item-based Collaborative Filtering, Item-CF)到第二代基于內(nèi)積模型的向量檢索方法，推薦技術(shù)打開了候選子集檢索范圍的天花板。然而，向量檢索方法限定了內(nèi)積模型這種用戶-商品偏好度量方式，無法容納更加先進(jìn)的打分模型(例如帶有Attention結(jié)構(gòu)的深度網(wǎng)絡(luò))。為了在全庫檢索和效率約束的基礎(chǔ)上進(jìn)一步打開推薦技術(shù)中模型能力的天花板，此前阿里媽媽精準(zhǔn)定向廣告業(yè)務(wù)團(tuán)隊(duì)自主提出了新一代任意深度學(xué)習(xí)+樹型全庫檢索推薦算法(Tree-based Deep Model，TDM)，在大規(guī)模推薦問題上取得了顯著的效果提升。最近，該團(tuán)隊(duì)針對大規(guī)模推薦問題的研究取得了最新的成果，介紹了如何通過數(shù)據(jù)驅(qū)動的方式，實(shí)現(xiàn)模型、索引、檢索算法的聯(lián)合優(yōu)化。基于這一最新研究成果整理的論文，已經(jīng)被NeurIPS 2019會議接收。

二. 現(xiàn)有體系存在的問題

如下圖所示，在大規(guī)模任務(wù)中，搜索，推薦和廣告的系統(tǒng)通常由模型，索引和檢索算法三大組件組成。模型計(jì)算單個(gè)用戶-商品的偏好概率，索引將所有商品有序地組織在一起，檢索算法根據(jù)模型的輸出在索引中召回最終的推薦結(jié)果。三者共同決定了召回質(zhì)量且存在內(nèi)在聯(lián)系。

然而，以推薦為例，現(xiàn)有的推薦體系對模型索引和檢索的相互聯(lián)系往往沒有做充分的考量。從聯(lián)合調(diào)優(yōu)這一視角出發(fā)，對現(xiàn)有的幾代推薦體系的代表算法存在問題分析如下：

1. 在Item-CF中，倒排索引根據(jù)Item之間某種自定義的相似度量建立，檢索過程則是根據(jù)用戶歷史行為在倒排索引中查詢候選集后排序截?cái)?，模型在排序過程中對候選集中的Item根據(jù)某種自定義的規(guī)則進(jìn)行打分。在系統(tǒng)中，模型和檢索被規(guī)則固化，沒有學(xué)習(xí)調(diào)優(yōu)。
2. 在向量檢索的模式中，系統(tǒng)會分別為用戶和商品學(xué)習(xí)一個(gè)向量表達(dá)，其內(nèi)積作為用戶對商品的偏好程度的預(yù)測。檢索等價(jià)于用戶向量在商品向量集合中的kNN最近鄰檢索，在大規(guī)模問題中，可以采用近似的最近鄰索引結(jié)構(gòu)來加速檢索。在建立向量檢索推薦系統(tǒng)的過程中，模型訓(xùn)練的目標(biāo)是準(zhǔn)確的預(yù)測單個(gè)用戶-商品的偏好概率，而kNN檢索索引建立的目標(biāo)則最小化近似誤差，二者的優(yōu)化方向并不一致。同時(shí)，內(nèi)積形式的偏好預(yù)測表達(dá)能力有限，無法容納更加先進(jìn)的打分模型。
3. 在TDM中，我們通過交替迭代優(yōu)化模型和樹結(jié)構(gòu)再加之無參數(shù)的逐層beam search檢索過程進(jìn)行了模型、索引和檢索聯(lián)合優(yōu)化上的實(shí)踐和創(chuàng)新。然而在TDM中，模型的優(yōu)化和樹結(jié)構(gòu)索引的學(xué)習(xí)二者的優(yōu)化目標(biāo)也不完全一致，這可能導(dǎo)致二者的優(yōu)化相互牽制而導(dǎo)致最終整體效果次優(yōu)。特別是對于樹結(jié)構(gòu)索引，模型訓(xùn)練樣本的構(gòu)造和檢索路徑的選擇與樹結(jié)構(gòu)具有更加緊密的聯(lián)系，因此其質(zhì)量好壞尤為重要。綜上分析，本文針對當(dāng)前大規(guī)模推薦方法中存在的問題，提出了一種統(tǒng)一目標(biāo)下的模型、索引、檢索聯(lián)合優(yōu)化的算法JTM（Joint Optimization of Tree-based Index and Deep Model），打破系統(tǒng)各模塊獨(dú)立優(yōu)化帶來的相互掣肘，使得整體推薦效能達(dá)到最優(yōu)。

三. 端到端聯(lián)合學(xué)習(xí)的深度樹匹配推薦技術(shù)

JTM繼承了TDM樹結(jié)構(gòu)索引+任意深度用戶-商品偏好打分模型的系統(tǒng)框架，通過聯(lián)合優(yōu)化和層次化特征建模取得了大幅超越TDM的推薦精度。為了更好地理解JTM，我們首先簡單了解一下TDM的原理。3.1 深度樹推薦模型TDM推薦系統(tǒng)的任務(wù)是從候選集(例如，商品庫)中選出用戶當(dāng)前偏好的一個(gè)子集。
當(dāng)候選集的規(guī)模很大時(shí)，如何快速有效地從全庫中做推薦是一個(gè)具有挑戰(zhàn)性的問題。TDM創(chuàng)造性地采用樹結(jié)構(gòu)作為索引結(jié)構(gòu)并進(jìn)一步地令用戶對樹上節(jié)點(diǎn)的偏好滿足下面的近似最大堆性質(zhì)：

其中 p(l)(n|u) 是用戶 u 對節(jié)點(diǎn) n 偏好概率的真值，α(l)是第 l 層內(nèi)偏好概率分布的歸一化項(xiàng)。這樣的建模保證了第 l 層節(jié)點(diǎn)中偏好概率最大的 k個(gè)節(jié)點(diǎn)一定包含在第 l?1 層的top-k節(jié)點(diǎn)的子節(jié)點(diǎn)中?；谶@一建模，TDM將推薦問題轉(zhuǎn)換為樹結(jié)構(gòu)中自上而下的層次化的檢索問題。下圖給出了TDM候選子集的生成過程。

首先，候選集中的每個(gè)商品都被分配到樹的一個(gè)不同葉子節(jié)點(diǎn)上，如圖(b)所示。樹上的非葉子節(jié)點(diǎn)可以看做是它的子節(jié)點(diǎn)集合的一個(gè)抽象。圖(a)給出了用戶對節(jié)點(diǎn)的偏好概率的計(jì)算過程，用戶信息和待打分的節(jié)點(diǎn)首先被向量化為深度打分網(wǎng)絡(luò)(例如，全連接網(wǎng)絡(luò)，attention網(wǎng)絡(luò)等等)的輸入，網(wǎng)絡(luò)的輸出作為用戶對該節(jié)點(diǎn)的偏好概率。在檢索top-k的候選子集即top-k葉子節(jié)點(diǎn)的過程中，我們采用自頂向下的逐層beam search方法。在第l層中，我們只對第l?1層被選中的k個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行打分和排序來選擇第l層的k個(gè)候選。圖(b)給出了檢索過程的示意。通過采用樹結(jié)構(gòu)作為索引，對一個(gè)用戶的偏好子集進(jìn)行top1檢索的時(shí)間復(fù)雜度為O(log(N))，其中 N 為全部候選集的大小。這一復(fù)雜度也與用戶偏好打分模型的結(jié)構(gòu)無關(guān)。同時(shí)，近似最大堆的假設(shè)將模型學(xué)習(xí)的目標(biāo)轉(zhuǎn)化為用戶-節(jié)點(diǎn)偏好分布的學(xué)習(xí)，這使得TDM能夠打破最近鄰檢索模式帶來的內(nèi)積形式的用戶偏好打分的限制，賦能任意復(fù)雜打分模型，從而極大的提升了推薦的準(zhǔn)確率。

3.2 JTM中的聯(lián)合優(yōu)化框架

image

，我們希望聯(lián)合優(yōu)化 π 和 θ 來擬合上述的用戶對樹上節(jié)點(diǎn)的偏好分布。為此，我們希望 π 和 θ 最小化如下的全局經(jīng)驗(yàn)損失函數(shù)：

在求解中，由于優(yōu)化 π 是一個(gè)組合優(yōu)化問題，很難和 θ 用基于梯度的優(yōu)化算法同時(shí)優(yōu)化。因此，我們提出交替優(yōu)化 θ 和 π 的聯(lián)合優(yōu)化框架，如下圖所示。優(yōu)化 θ 和 π 的目標(biāo)一致性促進(jìn)了整個(gè)算法的收斂。事實(shí)上，如果模型學(xué)習(xí)和樹學(xué)習(xí)能夠同時(shí)使得損失函數(shù)下降，那么整個(gè)算法一定會收斂，因?yàn)?{L(θt,πt)} 是下界為0的單調(diào)下降序列。

image

中的歸一化項(xiàng)。樹結(jié)構(gòu)學(xué)習(xí)是在給定模型參數(shù)的情況下求解 maxπ?L(θ,π) ，這是一個(gè)組合優(yōu)化問題。事實(shí)上，給定樹的形狀時(shí)(為了便于表達(dá)，我們假定樹的形狀是完整二叉樹。我們提出的優(yōu)化算法可以方便地推廣到多叉樹的情況)，maxπ?L(θ,π) ****等價(jià)于尋找候選集和所有葉子節(jié)點(diǎn)之間的一個(gè)最優(yōu)匹配，這進(jìn)一步等價(jià)于一個(gè)帶權(quán)二部圖的最大匹配。分析過程如下：若第k個(gè)商品ck被分配到第m個(gè)葉子節(jié)點(diǎn) nm 上，即 π(ck)=nm，我們可以計(jì)算如下的權(quán)重：

為目標(biāo)商品為 ck 的訓(xùn)練樣本集合。把樹的葉子節(jié)點(diǎn)和候選集作為頂點(diǎn)，葉子節(jié)點(diǎn)和候選集之間的全連接作為邊，把 Lck,nm 作為 ck 和 nm 之間邊的權(quán)重，我們可以構(gòu)造一個(gè)帶權(quán)二部圖V ，如2.1節(jié)的流程圖(b)所示。在這種情況下，每個(gè)可能的 π(?) 都是 V 的一個(gè)匹配，同時(shí)我們有

C 為所有ck的集合。因此，maxπ?L(θ,π) 等價(jià)于求解 V 的最大權(quán)匹配。對于大規(guī)模的候選集，傳統(tǒng)的求解最大權(quán)匹配的算法例如匈牙利算法由于復(fù)雜度太高而難以使用。即使是最簡單的貪婪算法，計(jì)算和存儲所有的權(quán)重的成本也是無法接受的。為解決這一問題，我們利用樹結(jié)構(gòu)提出了一種分段式樹學(xué)習(xí)算法。相比于直接將所有商品分配到葉子節(jié)點(diǎn)中，我們在樹中自上而下地一步步實(shí)現(xiàn)商品到節(jié)點(diǎn)的分配。記：

image

。不斷重復(fù)這一過程，直至每個(gè)商品被分配到葉子節(jié)點(diǎn)上為止。整個(gè)算法的流程如下圖所示：

3.3 層次化用戶興趣表達(dá)

本質(zhì)上，JTM（和TDM）是對推薦系統(tǒng)中索引結(jié)構(gòu)和檢索方式的一種深度改造。樹結(jié)構(gòu)的每一層可以看做是商品不同粒度上的聚合表示，JTM通過樹上自頂向下的逐層相關(guān)性檢索，從粗到細(xì)地找到用戶信息匹配的最佳候選子集，這也與人類視角選擇偏好商品的過程相契合。通過聯(lián)合考慮模型和索引結(jié)構(gòu)，JTM和TDM將一個(gè)復(fù)雜的大規(guī)模推薦任務(wù)分解為若干個(gè)級聯(lián)的子檢索任務(wù)，在上層的檢索任務(wù)中，只需要在一個(gè)更粗的粒度上做圈選，且每層圈選的候選集遠(yuǎn)小于候選集全集，其訓(xùn)練難度將大大縮小。
可以預(yù)見，當(dāng)子檢索任務(wù)的解足夠理想時(shí)，其級聯(lián)后的檢索結(jié)果將超越直接在候選集中圈選候選集的效果。事實(shí)上，樹結(jié)構(gòu)本身提供了候選集的一個(gè)層次結(jié)構(gòu)，因?yàn)槊總€(gè)非葉子節(jié)點(diǎn)都是其所有子節(jié)點(diǎn)的一個(gè)學(xué)習(xí)到的抽象，這啟發(fā)我們在訓(xùn)練模型 M 做每層的子檢索任務(wù)時(shí)對用戶行為特征做最利于模型學(xué)習(xí)的精準(zhǔn)層次建模。具體而言，用戶歷史行為的每個(gè)商品都是一個(gè)ID類離散特征，在模型訓(xùn)練中，每個(gè)商品和樹上的節(jié)點(diǎn)都被嵌入到一個(gè)連續(xù)特征空間并與模型同時(shí)優(yōu)化。
從每個(gè)非葉子節(jié)點(diǎn)是其子節(jié)點(diǎn)的抽象這一點(diǎn)出發(fā)，給定用戶行為序列c={c1,c2,?,cm} ，我們提出用 cl={bl(π(c1)),bl(π(c2)),?,bl(π(cm))}聯(lián)合目標(biāo)節(jié)點(diǎn)以及用戶的其他特征來生成模型 M 在第 l 層檢索的輸入。通過這種方式，用戶行為過的商品在第 l 層的祖先節(jié)點(diǎn)被用作了用戶抽象化的行為序列。這主要帶來了兩方面的好處：
★ 1. 層間的獨(dú)立性。
傳統(tǒng)的在每層檢索中共用用戶行為序列的embedding會在訓(xùn)練 M 作為每層的用戶偏好打分模型時(shí)引入噪聲，這是因?yàn)?M 在每層的訓(xùn)練目標(biāo)是不同的。一個(gè)直接的解決辦法是在每層賦予每個(gè)商品一個(gè)單獨(dú)的embedding來聯(lián)合訓(xùn)練。
但是這會極大的增加參數(shù)量。我們提出的層次化用戶行為特征使用對應(yīng)層節(jié)點(diǎn)的embedding生成 M 的輸入，從而在沒有增加參數(shù)總量的同時(shí)實(shí)現(xiàn)了層間embedding學(xué)習(xí)的獨(dú)立。
★ 2. 用戶的精準(zhǔn)建模。M 在檢索過程中逐層選擇最終候選子集的從粗到細(xì)的抽象。我們提出的層次化用戶行為特征表達(dá)抓住了這一檢索過程的本質(zhì)，用當(dāng)前層的節(jié)點(diǎn)對用戶行為進(jìn)行了適當(dāng)?shù)某橄?，從而增加了用戶偏好的可預(yù)測性，減少了過粗或者過細(xì)的特征表達(dá)帶來的混淆。

四. 實(shí)驗(yàn)效果

4.1 實(shí)驗(yàn)設(shè)置

我們使用了Amazon Books和UserBehavior兩個(gè)大型公開數(shù)據(jù)集來進(jìn)行方法的效果評估。Amazon Books是用戶在Amazon上的行為記錄，我們選擇了其中最大的Books這一子類目。UserBehavior為阿里開源的淘寶用戶行為數(shù)據(jù)集。數(shù)據(jù)集的規(guī)模如下：

在實(shí)驗(yàn)中，我們比較了下面幾種方法：

• Item-CF: 基本的協(xié)同濾波算法，被廣泛應(yīng)用于個(gè)性化推薦任務(wù)中。
• YouTube product-DNN: 應(yīng)用于Youtube視頻推薦的向量內(nèi)積檢索模型。
• HSM: 層次Softmax模型，被廣泛應(yīng)用于NLP領(lǐng)域，作為歸一化概率計(jì)算的一種替代.
• TDM： 我們此前的工作深度樹匹配推薦技術(shù)。
• DNN: TDM模型去掉樹結(jié)構(gòu)后的版本。該方法不使用索引結(jié)構(gòu)，在預(yù)測時(shí)會對全量候選集進(jìn)行打分，再挑選topk。由于對全量候選集打分的計(jì)算復(fù)雜度非常高，因此無法實(shí)際應(yīng)用，但可以作為強(qiáng)baseline來進(jìn)行比較。
• JTM: 本文中提出的聯(lián)合優(yōu)化方法。同時(shí)，我們對比了JTM的兩個(gè)變種版本，分別為JTM-J和JTM-H。其中，JTM-J為使用了樹結(jié)構(gòu)聯(lián)合優(yōu)化但沒有采用層次化用戶興趣表達(dá)的版本；JTM-H相反，其使用了層次化用戶興趣表達(dá)，但會使用固定的初始樹結(jié)構(gòu)而不進(jìn)行聯(lián)合學(xué)習(xí)。

在所有神經(jīng)網(wǎng)絡(luò)模型中，均使用相同的三層全連接網(wǎng)絡(luò)作為打分模型。評測方面，我們使用Precision, Recall和F-measure作為性能評測指標(biāo)，定義如下：

Pu 是對用戶 u召回的商品集合，Gu 是用戶 u感興趣集合的真集。

4.2 比較結(jié)果

DNN的性能要優(yōu)于YouTube product-DNN，這反應(yīng)了內(nèi)積模型的局限性，只通過內(nèi)積的形式構(gòu)造用戶對商品的偏好概率無法充分?jǐn)M合用戶-商品偏好分布。此外，TDM的性能不如DNN，這說明了樹結(jié)構(gòu)優(yōu)化的必要性。欠佳的樹結(jié)構(gòu)可能導(dǎo)致模型學(xué)習(xí)收斂到次優(yōu)的結(jié)果。特別是對于Amazon Books這種稀疏的數(shù)據(jù)，樹上節(jié)點(diǎn)的embedding無法充分學(xué)習(xí)而不具有顯著的區(qū)分性導(dǎo)致TDM效果不顯著。
與之對應(yīng)的是，通過應(yīng)用本文提出的層次化用戶興趣表征方法，JTM-J方案在一定程度上解決了粗粒度上的數(shù)據(jù)稀疏性問題，所以對比TDM在Amazon Books數(shù)據(jù)集上取得了十分顯著的提升，通過聯(lián)合優(yōu)化，JTM在所有數(shù)據(jù)集和評測指標(biāo)上顯著優(yōu)于DNN全量打分的結(jié)果，且檢索復(fù)雜度也要低得多。這些結(jié)果說明，通過統(tǒng)一目標(biāo)下聯(lián)合優(yōu)化的方式，JTM能夠?qū)W習(xí)到更優(yōu)的樹結(jié)構(gòu)和興趣模型。從JTM、JTM-J、JTM-H三者的相互對比來看，可以發(fā)現(xiàn)不管是同一目標(biāo)下的聯(lián)合學(xué)習(xí)，還是層次化的用戶興趣表示，都能提升最終的推薦精準(zhǔn)度。另外，在JTM的聯(lián)合框架下，樹結(jié)構(gòu)學(xué)習(xí)和層次化興趣表示疊加，起到了1+1>2的效果。

4.3 樹結(jié)構(gòu)學(xué)習(xí)收斂性

在基于樹的推薦方法中，樹結(jié)構(gòu)直接影響了訓(xùn)練時(shí)的樣本生成和預(yù)測時(shí)的檢索路徑。一個(gè)好的樹結(jié)構(gòu)，不管是對模型訓(xùn)練還是興趣檢索，都能發(fā)揮重要的正面作用。下圖中，我們對比了JTM提出的基于統(tǒng)一目標(biāo)的樹聯(lián)合學(xué)習(xí)方案，和TDM工作中使用到的基于商品embedding聚類的方案。其中，前三個(gè)圖為Amazon Books數(shù)據(jù)集上的效果，后三個(gè)圖為UserBehavior數(shù)據(jù)集上的效果

從實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，本文提出的JTM方案，在樹結(jié)構(gòu)學(xué)習(xí)的逐步迭代過程中，能夠穩(wěn)定地收斂到一個(gè)更優(yōu)的樹結(jié)構(gòu)。與之對比的是，基于聚類的方案，在迭代最后都會出現(xiàn)類似于過擬合的情況。

五. 總結(jié)

JTM給出了一種統(tǒng)一目標(biāo)下聯(lián)合優(yōu)化深度樹匹配模型的打分模型和樹索引結(jié)構(gòu)的算法框架。在樹結(jié)構(gòu)優(yōu)化中，我們基于樹型結(jié)構(gòu)的特點(diǎn)提出了一種可用于大規(guī)模任務(wù)的分層重建算法。在模型優(yōu)化和打分中，基于樹上檢索逐層細(xì)化候選集合的本質(zhì)，我們相應(yīng)的提出了對用戶行為特征層次化的建模方法。
JTM繼承了TDM打破內(nèi)積模型的約束，可容納任意深度打分模型的優(yōu)勢。此外，通過聯(lián)合調(diào)優(yōu)，JTM帶來了顯著的效果提升。JTM徹底解決了歷史推薦系統(tǒng)架構(gòu)的非最優(yōu)聯(lián)合問題，建立了完全數(shù)據(jù)驅(qū)動下端到端索引，模型和檢索聯(lián)合最優(yōu)化的系統(tǒng)組成。
進(jìn)一步的，JTM的提出，是對以user-tag-doc兩段式檢索為基礎(chǔ)的搜索，推薦和廣告現(xiàn)有架構(gòu)的一次重大技術(shù)革新。