阿裡妹導讀：搜尋，推薦和廣告是網際網路内容提供商進行價值創造的核心業務，在阿裡巴巴的電子商務交易平台上，搜尋，推薦和廣告業務同樣具有舉足輕重的意義和價值。現在，阿裡推薦技術又雙叒優化了，新的推薦技術，新的體驗，一起來看。
一. 背景
搜尋、推薦和廣告看似業務形态不同，其實技術組成卻是非常相通的。從推薦的視角看，搜尋可以認為是一種帶query相關性限制的推薦，而廣告則是疊加了廣告主營銷意願（價格）限制的推薦，是以推薦技術的創新對推動搜尋、推薦和廣告業務技術的整體發展具有基礎性的作用。
從技術演進的角度，推薦算法近年來也在不斷地更新換代。從限定在一個有限的曆史興趣範疇内推薦的第一代基于統計的啟發式規則方法(代表算法Item-based Collaborative Filtering, Item-CF)到第二代基于内積模型的向量檢索方法，推薦技術打開了候選子集檢索範圍的天花闆。然而，向量檢索方法限定了内積模型這種使用者-商品偏好度量方式，無法容納更加先進的打分模型(例如帶有Attention結構的深度網絡)。
為了在全庫檢索和效率限制的基礎上進一步打開推薦技術中模型能力的天花闆，此前阿裡媽媽精準定向廣告業務團隊自主提出了新一代任意深度學習+樹型全庫檢索推薦算法(Tree-based Deep Model，TDM)，在大規模推薦問題上取得了顯著的效果提升。最近，該團隊針對大規模推薦問題的研究取得了最新的成果，介紹了如何通過資料驅動的方式，實作模型、索引、檢索算法的聯合優化。基于這一最新研究成果整理的論文，已經被NeurIPS 2019會議接收。
二. 現有體系存在的問題
如下圖所示，在大規模任務中，搜尋，推薦和廣告的系統通常由模型，索引和檢索算法三大元件組成。模型計算單個使用者-商品的偏好機率，索引将所有商品有序地組織在一起，檢索算法根據模型的輸出在索引中召回最終的推薦結果。三者共同決定了召回品質且存在内在聯系。
然而，以推薦為例，現有的推薦體系對模型索引和檢索的互相聯系往往沒有做充分的考量。從聯合調優這一視角出發，對現有的幾代推薦體系的代表算法存在問題分析如下：
1.在Item-CF中，反向索引根據Item之間某種自定義的相似度量建立，檢索過程則是根據使用者曆史行為在反向索引中查詢候選集後排序截斷，模型在排序過程中對候選集中的Item根據某種自定義的規則進行打分。在系統中，模型和檢索被規則固化，沒有學習調優。
2.在向量檢索的模式中，系統會分别為使用者和商品學習一個向量表達，其内積作為使用者對商品的偏好程度的預測。檢索等價于使用者向量在商品向量集合中的kNN最近鄰檢索，在大規模問題中，可以采用近似的最近鄰索引結構來加速檢索。在建立向量檢索推薦系統的過程中，模型訓練的目标是準确的預測單個使用者-商品的偏好機率，而kNN檢索索引建立的目标則最小化近似誤差，二者的優化方向并不一緻。同時，内積形式的偏好預測表達能力有限，無法容納更加先進的打分模型。
3.在TDM中，我們通過交替疊代優化模型和樹結構再加之無參數的逐層beam search檢索過程進行了模型、索引和檢索聯合優化上的實踐和創新。然而在TDM中，模型的優化和樹結構索引的學習二者的優化目标也不完全一緻，這可能導緻二者的優化互相牽制而導緻最終整體效果次優。特别是對于樹結構索引，模型訓練樣本的構造和檢索路徑的選擇與樹結構具有更加緊密的聯系，是以其品質好壞尤為重要。
綜上分析，本文針對目前大規模推薦方法中存在的問題，提出了一種統一目标下的模型、索引、檢索聯合優化的算法JTM（Joint Optimization of Tree-based Index and Deep Model），打破系統各子產品獨立優化帶來的互相掣肘，使得整體推薦效能達到最優。
三. 端到端聯合學習的深度樹比對推薦技術
JTM繼承了TDM樹結構索引+任意深度使用者-商品偏好打分模型的系統架構，通過聯合優化和階層化特征模組化取得了大幅超越TDM的推薦精度。為了更好地了解JTM，我們首先簡單了解一下TDM的原理。
3.1 深度樹推薦模型TDM
推薦系統的任務是從候選集(例如，商品庫)中選出使用者目前偏好的一個子集。當候選集的規模很大時，如何快速有效地從全庫中做推薦是一個具有挑戰性的問題。TDM創造性地采用樹結構作為索引結構并進一步地令使用者對樹上節點的偏好滿足下面的近似最大堆性質：
其中 p(l)(n|u) 是使用者 u 對節點 n 偏好機率的真值，α(l)是第 l 層内偏好機率分布的歸一化項。這樣的模組化保證了第 l 層節點中偏好機率最大的 k個節點一定包含在第 l−1 層的top-k節點的子節點中。基于這一模組化，TDM将推薦問題轉換為樹結構中自上而下的階層化的檢索問題。下圖給出了TDM候選子集的生成過程。
首先，候選集中的每個商品都被配置設定到樹的一個不同葉子節點上，如圖(b)所示。樹上的非葉子節點可以看做是它的子節點集合的一個抽象。圖(a)給出了使用者對節點的偏好機率的計算過程，使用者資訊和待打分的節點首先被向量化為深度打分網絡(例如，全連接配接網絡，attention網絡等等)的輸入，網絡的輸出作為使用者對該節點的偏好機率。在檢索top-k的候選子集即top-k葉子節點的過程中，我們采用自頂向下的逐層beam search方法。在第l層中，我們隻對第l−1層被選中的k個節點的子節點進行打分和排序來選擇第l層的k個候選。圖(b)給出了檢索過程的示意。
通過采用樹結構作為索引，對一個使用者的偏好子集進行top1檢索的時間複雜度為O(log(N))，其中 N 為全部候選集的大小。這一複雜度也與使用者偏好打分模型的結構無關。同時，近似最大堆的假設将模型學習的目标轉化為使用者-節點偏好分布的學習，這使得TDM能夠打破最近鄰檢索模式帶來的内積形式的使用者偏好打分的限制，賦能任意複雜打分模型，進而極大的提升了推薦的準确率。
3.2 JTM中的聯合優化架構
從檢索過程中可以看到，TDM的推薦準确率由使用者偏好打分模型 M 和樹索引結構 T 共同決定，且二者是互相耦合的關系。具體地，給定 n 對正樣本 ，即使用者 u(i)對商品c(i)感興趣，樹結構 T 決定了模型 M 需要選擇哪些非葉子節點來對使用者 u(i)傳回商品c(i) 。在統一目标下聯合優化 M 和 T 能夠避免二者優化方向的沖突造成的整體結果次優。為此，在JTM中，我們在一個共同的損失函數下聯合優化 M 和 T 。我們首先構造聯合優化的目标函數。
記 p(π(c)|u;π)為使用者u對葉子節點 π(c) 的偏好機率，其中 π(⋅) 是把候選集中的商品投射到樹的葉子節點上的投影函數。π(c) 決定了候選集中的商品在樹結構上的索引順序。如果 (u,c) 是一個正樣本，我們有 p(π(c)|u;π)=1。同時在近似最大堆的假設下，對 π(c) 的所有祖先節點，其偏好機率也為1，即。其中 bj(⋅) 是把一個節點投影到其在第 j 層的祖先節點的投影函數，lmax 為樹 T 的層數。記 為模型 M 傳回的使用者 u 對節點 π(c) 的偏好機率的估計值，其中 θ 為模型的參數。給定 n 對正樣本，我們希望聯合優化 π 和 θ 來拟合上述的使用者對樹上節點的偏好分布。為此，我們希望 π 和 θ 最小化如下的全局經驗損失函數：
在求解中，由于優化 π 是一個組合優化問題，很難和 θ 用基于梯度的優化算法同時優化。是以，我們提出交替優化 θ 和 π 的聯合優化架構，如下圖所示。優化 θ 和 π 的目标一緻性促進了整個算法的收斂。事實上，如果模型學習和樹學習能夠同時使得損失函數下降，那麼整個算法一定會收斂，因為 {L(θt,πt)} 是下界為0的單調下降序列。
在模型訓練中，minθL(θ,π) 是為了求解得到每層的使用者-節點偏好打分模型。得益于樹結構和近似最大堆的性質，我們隻需要在模型訓練中拟合訓練集中的使用者-節點偏好分布，這使得我們可以使用任意複雜的神經網絡模型，同時 minθL(θ,π) 可以用流行的算法例如SGD、Adam求解。采樣政策如Noise-contrastive estimation (NCE)可以用來加速計算中的歸一化項。
樹結構學習是在給定模型參數的情況下求解 maxπ−L(θ,π) ，這是一個組合優化問題。事實上，給定樹的形狀時(為了便于表達，我們假定樹的形狀是完整二叉樹。我們提出的優化算法可以友善地推廣到多叉樹的情況)，maxπ−L(θ,π) 等價于尋找候選集和所有葉子節點之間的一個最優比對，這進一步等價于一個帶權二部圖的最大比對。分析過程如下：
若第k個商品ck被配置設定到第m個葉子節點 nm 上，即 π(ck)=nm，我們可以計算如下的權重：
其中
為目标商品為 ck 的訓練樣本集合。把樹的葉子節點和候選集作為頂點，葉子節點和候選集之間的全連接配接作為邊，把 Lck,nm 作為 ck 和 nm 之間邊的權重，我們可以構造一個帶權二部圖V ，如2.1節的流程圖(b)所示。在這種情況下，每個可能的 π(⋅) 都是 V 的一個比對，同時我們有
C 為所有ck的集合。是以，maxπ−L(θ,π) 等價于求解 V 的最大權比對。
對于大規模的候選集，傳統的求解最大權比對的算法例如匈牙利算法由于複雜度太高而難以使用。即使是最簡單的貪婪算法，計算和存儲所有的權重的成本也是無法接受的。為解決這一問題，我們利用樹結構提出了一種分段式樹學習算法。相比于直接将所有商品配置設定到葉子節點中，我們在樹中自上而下地一步步實作商品到節點的配置設定。記：
為目标商品為 ck 的訓練樣本集合，s 和 e 分别為一個起始和終止層。我們的分段算法，首先通過找到一個最優映射 π∗ 來最大化
，等價于将候選集配置設定到第d層的所有節點上。對于一個完整二叉樹來說，每個第d層的節點應該包含不超過 2lmax−d個商品。這也是一個最大權比對問題，但由于每個商品可能的配置設定位置大大減少了，是以可以通過貪婪算法有效求解。然後，在保持每個商品在第 d 層的祖先節點不變的前提下，即保證∀c∈C,bd(π(c))=bd(π∗(c)) 的前提下，繼續将候選集在接下來的d層中進行配置設定，即優化
。不斷重複這一過程，直至每個商品被配置設定到葉子節點上為止。整個算法的流程如下圖所示：
3.3 階層化使用者興趣表達
本質上，JTM（和TDM）是對推薦系統中索引結構和檢索方式的一種深度改造。樹結構的每一層可以看做是商品不同粒度上的聚合表示，JTM通過樹上自頂向下的逐層相關性檢索，從粗到細地找到使用者資訊比對的最佳候選子集，這也與人類視角選擇偏好商品的過程相契合。通過聯合考慮模型和索引結構，JTM和TDM将一個複雜的大規模推薦任務分解為若幹個級聯的子檢索任務，在上層的檢索任務中，隻需要在一個更粗的粒度上做圈選，且每層圈選的候選集遠小于候選集全集，其訓練難度将大大縮小。可以預見，當子檢索任務的解足夠理想時，其級聯後的檢索結果将超越直接在候選集中圈選候選集的效果。
事實上，樹結構本身提供了候選集的一個層次結構，因為每個非葉子節點都是其所有子節點的一個學習到的抽象，這啟發我們在訓練模型 M 做每層的子檢索任務時對使用者行為特征做最利于模型學習的精準層次模組化。
具體而言，使用者曆史行為的每個商品都是一個ID類離散特征，在模型訓練中，每個商品和樹上的節點都被嵌入到一個連續特征空間并與模型同時優化。從每個非葉子節點是其子節點的抽象這一點出發，給定使用者行為序列c={c1,c2,⋯,cm} ，我們提出用 cl={bl(π(c1)),bl(π(c2)),⋯,bl(π(cm))}聯合目标節點以及使用者的其他特征來生成模型 M 在第 l 層檢索的輸入。通過這種方式，使用者行為過的商品在第 l 層的祖先節點被用作了使用者抽象化的行為序列。這主要帶來了兩方面的好處：
1.層間的獨立性。
傳統的在每層檢索中共用使用者行為序列的embedding會在訓練 M 作為每層的使用者偏好打分模型時引入噪聲，這是因為 M 在每層的訓練目标是不同的。一個直接的解決辦法是在每層賦予每個商品一個單獨的embedding來聯合訓練。但是這會極大的增加參數量。我們提出的階層化使用者行為特征使用對應層節點的embedding生成 M 的輸入，進而在沒有增加參數總量的同時實作了層間embedding學習的獨立。
2.使用者的精準模組化。
M 在檢索過程中逐層選擇最終候選子集的從粗到細的抽象。我們提出的階層化使用者行為特征表達抓住了這一檢索過程的本質，用目前層的節點對使用者行為進行了适當的抽象，進而增加了使用者偏好的可預測性，減少了過粗或者過細的特征表達帶來的混淆。
四. 實驗效果
4.1 實驗設定
我們使用了Amazon Books和UserBehavior兩個大型公開資料集來進行方法的效果評估。Amazon Books是使用者在Amazon上的行為記錄，我們選擇了其中最大的Books這一子類目。UserBehavior為阿裡開源的淘寶使用者行為資料集。資料集的規模如下：
在實驗中，我們比較了下面幾種方法：
- Item-CF: 基本的協同濾波算法，被廣泛應用于個性化推薦任務中。
- YouTube product-DNN: 應用于Youtube視訊推薦的向量内積檢索模型。
- HSM: 層次Softmax模型，被廣泛應用于NLP領域，作為歸一化機率計算的一種替代.
- TDM： 我們此前的工作深度樹比對推薦技術。
- DNN: TDM模型去掉樹結構後的版本。該方法不使用索引結構，在預測時會對全量候選集進行打分，再挑選topk。由于對全量候選集打分的計算複雜度非常高，是以無法實際應用，但可以作為強baseline來進行比較。
- JTM: 本文中提出的聯合優化方法。同時，我們對比了JTM的兩個變種版本，分别為JTM-J和JTM-H。其中，JTM-J為使用了樹結構聯合優化但沒有采用階層化使用者興趣表達的版本；JTM-H相反，其使用了階層化使用者興趣表達，但會使用固定的初始樹結構而不進行聯合學習。
在所有神經網絡模型中，均使用相同的三層全連接配接網絡作為打分模型。評測方面，我們使用Precision, Recall和F-measure作為性能評測名額，定義如下：
Pu 是對使用者 u召回的商品集合，Gu 是使用者 u感興趣集合的真集。
4.2 比較結果
下表給出了各個方法在兩個資料集上的比較結果。相比于效果最佳的baseline方法DNN（計算量太高無法應用于實際），JTM在Amazon Books和UserBehavior上的recall分别取得了45.3%和8.1%的相對提升。
DNN的性能要優于YouTube product-DNN，這反應了内積模型的局限性，隻通過内積的形式構造使用者對商品的偏好機率無法充分拟合使用者-商品偏好分布。此外，TDM的性能不如DNN，這說明了樹結構優化的必要性。
欠佳的樹結構可能導緻模型學習收斂到次優的結果。特别是對于Amazon Books這種稀疏的資料，樹上節點的embedding無法充分學習而不具有顯著的區分性導緻TDM效果不顯著。與之對應的是，通過應用本文提出的階層化使用者興趣表征方法，JTM-J方案在一定程度上解決了粗粒度上的資料稀疏性問題，是以對比TDM在Amazon Books資料集上取得了十分顯著的提升，通過聯合優化，JTM在所有資料集和評測名額上顯著優于DNN全量打分的結果，且檢索複雜度也要低得多。
這些結果說明，通過統一目标下聯合優化的方式，JTM能夠學習到更優的樹結構和興趣模型。從JTM、JTM-J、JTM-H三者的互相對比來看，可以發現不管是同一目标下的聯合學習，還是階層化的使用者興趣表示，都能提升最終的推薦精準度。另外，在JTM的聯合架構下，樹結構學習和階層化興趣表示疊加，起到了1+1>2的效果。
4.3 樹結構學習收斂性
在基于樹的推薦方法中，樹結構直接影響了訓練時的樣本生成和預測時的檢索路徑。一個好的樹結構，不管是對模型訓練還是興趣檢索，都能發揮重要的正面作用。下圖中，我們對比了JTM提出的基于統一目标的樹聯合學習方案，和TDM工作中使用到的基于商品embedding聚類的方案。其中，前三個圖為Amazon Books資料集上的效果，後三個圖為UserBehavior資料集上的效果
從實驗結果中可以發現，本文提出的JTM方案，在樹結構學習的逐漸疊代過程中，能夠穩定地收斂到一個更優的樹結構。與之對比的是，基于聚類的方案，在疊代最後都會出現類似于過拟合的情況。
五. 總結
JTM給出了一種統一目标下聯合優化深度樹比對模型的打分模型和樹索引結構的算法架構。在樹結構優化中，我們基于樹型結構的特點提出了一種可用于大規模任務的分層重建算法。在模型優化和打分中，基于樹上檢索逐層細化候選集合的本質，我們相應的提出了對使用者行為特征階層化的模組化方法。
JTM繼承了TDM打破内積模型的限制，可容納任意深度打分模型的優勢。此外，通過聯合調優，JTM帶來了顯著的效果提升。JTM徹底解決了曆史推薦系統架構的非最優聯合問題，建立了完全資料驅動下端到端索引，模型和檢索聯合最優化的系統組成。進一步的，JTM的提出，是對以user-tag-doc兩段式檢索為基礎的搜尋，推薦和廣告現有架構的一次重大技術革新。
之前的TDM解決方案已經基于阿裡巴巴自研的深度學習平台X-DeepLearning在 Github 開源，點選獲得
Github下載下傳連結，了解更多詳情。
阿裡媽媽資訊流廣告算法團隊常年誠招大資料處理和機器學習算法方向的能人志士！有意者可發履歷聯系：[email protected]。
原文釋出時間為：2019-10-10
作者：阿裡媽媽技術團隊
本文來自雲栖社群合作夥伴“
阿裡技術”，了解相關資訊可以關注“
”。