雷鋒網(wǎng) AI 科技評論按：推薦系統(tǒng)是現(xiàn)代互聯(lián)網(wǎng)服務的重要組成部分之一，不管是 YouTube 和亞馬遜，還是優(yōu)酷和淘寶，都通過推薦系統(tǒng)向用戶推薦他們可能感興趣的內(nèi)容，用戶得以看到更多自己關(guān)心的內(nèi)容、在頁面上逗留更多時間，服務提供商和網(wǎng)購平臺的商戶們也由此獲得更多的收入。

蓋坤博士領(lǐng)導的阿里媽媽精準定向技術(shù)團隊就在推薦系統(tǒng)方面有諸多研究成果。之前我們就介紹過一篇來自他們的論文，他們設計的深度興趣網(wǎng)絡（Deep Interest Network，DIN）能更好地利用用戶歷史行為數(shù)據(jù)，提升廣告點擊預測的準確率。

最近蓋坤團隊的一篇新論文《Learning Tree-based Model for Recommender Systems》也介紹了他們在推薦系統(tǒng)算法設計方面的新進展。雷鋒網(wǎng) AI 科技評論把論文內(nèi)容介紹如下。

背景

對于生產(chǎn)級別的推薦系統(tǒng)來說，語料庫的大小其實是算法選擇的一大限制。直觀地來說，推薦系統(tǒng)需要從各項語料（商品或者視頻）中挑出和用戶最為匹配的條目作為推薦結(jié)果。當語料庫較小時，各種方法都可以選用；但當語料庫很大時，那些計算復雜度隨語料數(shù)量線性增加的算法就是難以接受的了。

研究人員們早期提出的協(xié)同過濾推薦算法（collaborative filtering）就是一類能以相對小的計算能力處理大規(guī)模語料的算法，其中典型的基于物品的協(xié)同過濾算法 ItemCF 可以預先計算物品對之間的相似度，然后根據(jù)用戶的歷史行為選出最相似的物品。這種方法簡單有效，而且已經(jīng)可以為不同的用戶提供個性化的推薦結(jié)果，但它最好情況下也只能推薦與用戶看過的商品相似的其它商品，無法真正挖掘用戶的興趣，而且推薦結(jié)果也沒有新穎性（對用戶來說沒有驚喜度）。

隨著機器學習的興起，「學出一個推薦系統(tǒng)模型」的想法被證明不僅可行，而且推薦結(jié)果也有明顯的進步。理論上，學到的模型應當為每一對「用戶 - 商品」對計算匹配度，然后把算出的匹配度排序，推薦排在前列的商品。學到的模型固然可以帶來優(yōu)秀的推薦質(zhì)量，但這樣的做法同時也會帶來線性增加的計算復雜度，用戶和商品數(shù)量大到一定程度就無法使用了。所以研究人員們也提出了一些替代方法，比如建立矩陣分解（matrix factorization）模型，把用戶 - 商品對分解為用戶向量和商品向量，然后把兩個向量的內(nèi)積或者距離作為匹配度。這樣形式的推薦問題在有限時間內(nèi)可以近似求解，比如用哈?；蛘吡炕椒ń茖ふ?k-最近鄰，所以也在工業(yè)界得到了廣泛應用。YouTube 介紹自己的推薦系統(tǒng)的論文《Deep Neural Networks for YouTube Recommendations》中就探索了使用兩路多層網(wǎng)絡分別產(chǎn)生用戶向量和商品向量最后做內(nèi)積計算的方法。

不過向量內(nèi)積方法也仍然極大地限制了模型的能力。比如點擊通過率（click through rate）預估中需要使用用戶歷史行為和商品的交叉特征，但大部分特征無法用內(nèi)積的形式表示。甚至于，即便只是把固定的內(nèi)積計算步驟換成一個多層前饋神經(jīng)網(wǎng)絡都能改善推薦結(jié)果。更強大、更自由的模型仍然大有可為。

基于樹搜索的深度推薦模型

在這樣的背景下，蓋坤團隊希望通過新的匹配和推薦技術(shù)解開計算復雜度的枷鎖，允許在大規(guī)模語料庫上自由地使用各種模型。在論文中他們提出了新的基于樹搜索的深度推薦模型（tree-based deep recommendation model，TDM）。

實際上，樹形的層級化信息結(jié)構(gòu)在各種領(lǐng)域都天然地存在，比如 iPhone 這個細分商品品類就可以歸在“智能手機”這個粗粒度商品品類下面。文中提出的 TDM 就利用了這種層級化的信息結(jié)構(gòu)，把推薦問題轉(zhuǎn)化為一系列層級化分類問題。利用從粗到細的逐步分類過程，TDM 不僅提高了推薦準確率，而且可以把計算復雜度從關(guān)于語料數(shù)量線性增加降低到對數(shù)增加。

TDM 的關(guān)鍵設計可以分為新型樹結(jié)構(gòu)的設計、深度神經(jīng)網(wǎng)絡設計、樹結(jié)構(gòu)的學習三部分。

新型樹結(jié)構(gòu)降低計算復雜度、降低搜索難度

對于樹結(jié)構(gòu)，我們很容易想到熟悉的 hierarchical softmax 樹，其中每次分支都是一次二分類。這一面導致從上向下搜索時不能保證一次就找到最優(yōu)的葉子，仍然需要遍歷整個樹；另一面，在推薦系統(tǒng)的場景下其實我們希望找到多個相似的葉子，hierarchical softmax 就不是那么適合。

（雷鋒網(wǎng) AI 科技評論注：softmax 模型里每類的概率正比于類別自己的指數(shù)項，但具體計算一類的概率時需要用自己的指數(shù)項除以一個歸一化項，這個歸一化項是所有類別的指數(shù)項的加和。所以導致了對多類問題中，即使計算其中一個類別的概率，softmax 的計算復雜度也很高。Hierachical softmax 的動機和貢獻是用樹狀連乘概率形式避免掉了歸一化項的計算，節(jié)省了計算某一類的計算量。但對于尋優(yōu)檢索問題，它的連乘概率形式不保證每層進行貪婪搜索能找到全局最優(yōu)，所以對大商品庫下推薦最好商品這個尋優(yōu)問題仍需要遍歷全部商品進行計算。）

TDM 的關(guān)鍵是使用了一種新的類似最大堆（max-heap like）的樹結(jié)構(gòu)，如上圖（圖中示例是一個完全二叉樹，實際中也可以不是）。設用戶 u （包含用戶身份、歷史行為等）對第 j 層的節(jié)點 n 代表的商品品類感興趣的概率為 P^(j)(n|u) ，那么每個非葉子節(jié)點都滿足： P^(j)(n|u) 的真實值 = n 節(jié)點的所有子節(jié)點 ｛n_c｝中最大的 P^(j+1)(n_c|u) 除以正則化項 α^(j)；正則化項 α^(j) 的作用是讓第 j 層所有節(jié)點的概率的和為 1。

對于推薦系統(tǒng)而言，對這個樹做搜索的目標是找到 k 個偏好概率最大的葉子。那么搜索時可以在每層中找到 k 個概率值最大的節(jié)點，然后只有這 k 個節(jié)點的子節(jié)點會繼續(xù)向下搜索；最終找到概率值最高的 k 個葉子。根據(jù)這樣的設計，搜索過程中可以不知道每個節(jié)點的概率的確切值，只需知道同一層節(jié)點之間的大小順序就可以完成搜索。據(jù)此，作者們也根據(jù)用戶的隱式反饋數(shù)據(jù)和神經(jīng)網(wǎng)絡來訓練每個節(jié)點的辨別器，讓它們可以對偏好概率排序。

在訓練時，用戶實際沒有進行互動的節(jié)點也就可以隨機選擇一部分作為訓練中的負例。這種隨機選擇作為負例的做法還有一個好處，相比 hierarchical softmax 樹中訓練模型分辨最優(yōu)和次優(yōu)節(jié)點，隨機選擇的負例會讓每個節(jié)點的辨別器都成為當前層中的全局辨別器，即便當上一層的辨別器出了問題、選擇了一些不好的子節(jié)點時，下一層的辨別器也有能力把所有這些子節(jié)點中好的那一部分挑出來。

通過這樣的樹結(jié)構(gòu)設計，尋找節(jié)點的過程是從高向低、層層遞進的。對于大小為 M 的語料庫，最多只需要 2*k*log M 次分支就可以在完全二叉樹中找到最終需要的 k 個推薦結(jié)果?？s減到對數(shù)級別的計算復雜度也意味著可以在其上使用更高級的概率二分類模型。層層遞進中每一次只需要做一個簡單分類問題的設計也比傳統(tǒng)逐個搜索葉子節(jié)點的難度大大降低。

另外，樹結(jié)構(gòu)作為一種索引也是可以學習的，從而讓其中的商品和概念可以被更快地提取到；這同時也有助于模型的訓練。作者們也提出了一種樹結(jié)構(gòu)的學習方法，可以合并訓練神經(jīng)網(wǎng)絡和樹結(jié)構(gòu)，見下文。

時間分片輸入、帶有注意力模塊的深度神經(jīng)網(wǎng)絡

受到之前在點擊通過率 CTR 模型方面研究的啟發(fā)，作者們設計的深度神經(jīng)網(wǎng)絡模型（上圖）可以從樹中學到低維的嵌入，然后結(jié)合注意力模塊尋找相關(guān)的用戶行為，以便更好地表征用戶。網(wǎng)絡的輸入也可以接收多個塊，每個塊中包含用戶在不同時間窗口內(nèi)的行為。借助注意力模塊和后部的多層神經(jīng)網(wǎng)絡，這個模型的表現(xiàn)和容量得以大幅提高，同時也不再受到前文提到過的表示為向量和向量內(nèi)積的限制。

樹結(jié)構(gòu)學習

根據(jù)前面的設計，學到一個好的樹對整個推薦模型發(fā)揮出良好表現(xiàn)起著重要作用。直接參照現(xiàn)有數(shù)據(jù)庫的一致性或者相似性構(gòu)建樹結(jié)構(gòu)很可能導致不平衡，這對訓練和節(jié)點檢索都有負面影響。所以作者們也新設計了合理、可行的樹構(gòu)建和學習方法。

首先依據(jù)「相似的商品應當具有相近的位置」的思路對樹結(jié)構(gòu)進行初始化。初始樹的構(gòu)建利用了商品的類別分類信息，隨機排序所有的類別后，以隨機順序把同一類的商品安排在一起；同時屬于多個品類的商品會唯一地歸為其中某一個類，從而得到一個商品的有序列表。然后反復對有序列表做二分割，直到讓每個集中都只含有一個商品，這樣就得到了接近完全的二叉樹。這樣基于品類的初始化方法比完全隨機的初始化方法具有更好的層次性。

然后，深度神經(jīng)網(wǎng)絡在訓練后可以為樹中的每個葉子節(jié)點生成一個嵌入，那么這些嵌入向量也就可以用來聚類為一個新的樹。K-means 聚類對于大規(guī)模語料庫就是不錯的選擇。在實驗中，單臺服務器只花一個小時時間就可以完成大小為四百萬的語料庫的聚類成樹。

最后，新生成的樹還可以用來繼續(xù)訓練神經(jīng)網(wǎng)絡。通過交替生成新的樹以及訓練神經(jīng)網(wǎng)絡，兩者得以合并訓練，樹結(jié)構(gòu)和網(wǎng)絡表現(xiàn)都得以繼續(xù)優(yōu)化。

模型表現(xiàn)

作者們在 MovieLens-20M 數(shù)據(jù)集上，以及根據(jù)部分真實淘寶用戶進行了測試。數(shù)據(jù)規(guī)模如下圖。

參與對比的基準模型包括 FM 矩陣分解、BPR-MF 隱式反饋推薦矩陣分解、 ItemCF 基于物品的協(xié)同過濾算法、YouTube product-DNN。TDM 的變種則包括去掉注意力模塊、使用和 YouTube product-DNN 同樣的內(nèi)積方法的 TDM product-DNN，僅去掉激活模塊的 TDM DNN，以及使用 hierarchical softmax 樹的 TDM attention-DNN-HS。

上圖測試結(jié)果不僅反映出了所提的 TDM 模型的有效性，幾個變體之間的對比也分別體現(xiàn)了注意力模塊帶來的 10% 的召回率提升和去掉內(nèi)積限制的巨大作用。使用 hierarchical softmax 樹的 TDM attention-DNN-HS 則帶來的最差了表現(xiàn)，也表明了它不適合推薦任務。

前面我們也提到了推薦結(jié)果需要有一定的新穎性。上圖的測試中限定了推薦結(jié)果必須來自用戶沒有行為過的類目下的商品，作為推薦準確率和新穎性的結(jié)合度量。TDM 的表現(xiàn)自然一騎絕塵。

針對樹學習的單項測試也表明了它帶來的可見提升。

作者們也在淘寶 app 的真實訪問流量上進行了測試。對比的基準方法是通過邏輯回歸挑選出用戶有過互動的商品聚類，這是一個表現(xiàn)很好的基準線，而 TDM 模型的點擊通過率及廣告收入仍然有顯著提升。這還僅僅是 TDM 的首個版本實現(xiàn)，后續(xù)相信還有不小提升空間。

最后，作者們也關(guān)注了模型的運行速度。對于淘寶的廣告展示系統(tǒng)，TDM 的神經(jīng)網(wǎng)絡平均只需要 6 毫秒就可以完成一次推薦，不僅不構(gòu)成整個推薦系統(tǒng)的性能瓶頸，甚至還比后續(xù)的點擊通過率預測模型運行還快。

結(jié)論

這篇論文中作者們首先探究了基于模型的系統(tǒng)應用于大規(guī)模語料推薦場景存在的問題，并提出了基于樹結(jié)構(gòu)的新的匹配與推薦算法范式，希望借此在推薦系統(tǒng)中應用任意的模型。作者們提出的樹學習方法和 TDM 模型也在測試中獲得了良好表現(xiàn)，召回率和新穎性都有大幅提高。蓋坤博士表示：「雖然初期很令人興奮，但我們深知這個技術(shù)并不完美，還有很多工作要做。并且解決匹配問題也不意味著解決推薦中的所有問題。歡迎更多人來探討交流?！?/p>

論文地址：https://arxiv.org/abs/1801.02294 

雷鋒網(wǎng) AI 科技評論編譯，感謝蓋坤博士的審閱指正。更多人工智能、機器學習前沿技術(shù)及應用，請繼續(xù)關(guān)注雷鋒網(wǎng) AI 科技評論。

相關(guān)文章：

AI能看懂英文，阿里巴巴奪實體發(fā)現(xiàn)測評全球第一

阿里巴巴年度技術(shù)總結(jié)：人工智能在搜索的應用和實踐

阿里巴巴WSDM Cup 2018奪得第二名，獲獎論文全解讀

阿里巴巴人工智能進入時尚界 發(fā)起全球首個時尚AI算法大賽

阿里蓋坤團隊提出深度興趣網(wǎng)絡，更懂用戶什么時候會剁手

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。