怎麼給海量商品設計推薦系統？阿里蓋坤團隊提出深層樹結構檢索模型

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

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

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

背景

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

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

隨著機器學習的興起，「學出一個推薦系統模型」的想法被證明不僅可行，而且推薦結果也有明顯的進步。理論上，學到的模型應當為每一對「用戶 - 商品」對計算匹配度，然後把算出的匹配度排序，推薦排在前列的商品。學到的模型固然可以帶來優秀的推薦質量，但這樣的做法同時也會帶來線性增加的計算複雜度，用戶和商品數量大到一定程度就無法使用了。所以研究人員們也提出了一些替代方法，比如建立矩陣分解（matrix factorization）模型，把用戶 - 商品對分解為用戶向量和商品向量，然後把兩個向量的內積或者距離作為匹配度。這樣形式的推薦問題在有限時間內可以近似求解，比如用哈希或者量化方法近似尋找 k-最近鄰，所以也在工業界得到了廣泛應用。YouTube 介紹自己的推薦系統的論文中就探索了使用兩路多層網路分別產生用戶向量和商品向量最後做內積計算的方法。

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

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

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

實際上，樹形的層級化信息結構在各種領域都天然地存在，比如 iPhone 這個細分商品品類就可以歸在「智能手機」這個粗粒度商品品類下面。文中提出的 TDM 就利用了這種層級化的信息結構，把推薦問題轉化為一系列層級化分類問題。利用從粗到細的逐步分類過程，TDM 不僅提高了推薦準確率，而且可以把計算複雜度從關於語料數量線性增加降低到對數增加。

TDM 的關鍵設計可以分為新型樹結構的設計、深度神經網路設計、樹結構的學習三部分。

新型樹結構降低計算複雜度、降低搜索難度

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

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

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

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

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

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

另外，樹結構作為一種索引也是可以學習的，從而讓其中的商品和概念可以被更快地提取到；這同時也有助於模型的訓練。作者們也提出了一種樹結構的學習方法，可以合併訓練神經網路和樹結構，見下文。

時間分片輸入、帶有注意力模塊的深度神經網路

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

樹結構學習

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

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

然後，深度神經網路在訓練後可以為樹中的每個葉子節點生成一個嵌入，那麼這些嵌入向量也就可以用來聚類為一個新的樹。K-means 聚類對於大規模語料庫就是不錯的選擇。在實驗中，單台伺服器只花一個小時時間就可以完成大小為四百萬的語料庫的聚類成樹。

最後，新生成的樹還可以用來繼續訓練神經網路。通過交替生成新的樹以及訓練神經網路，兩者得以合併訓練，樹結構和網路表現都得以繼續優化。

模型表現

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

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

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

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

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

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

最後，作者們也關注了模型的運行速度。對於淘寶的廣告展示系統，TDM 的神經網路平均只需要 6 毫秒就可以完成一次推薦，不僅不構成整個推薦系統的性能瓶頸，甚至還比後續的點擊通過率預測模型運行還快。

結論

這篇論文中作者們首先探究了基於模型的系統應用於大規模語料推薦場景存在的問題，並提出了基於樹結構的新的匹配與推薦演算法範式，希望藉此在推薦系統中應用任意的模型。作者們提出的樹學習方法和 TDM 模型也在測試中獲得了良好表現，召回率和新穎性都有大幅提高。蓋坤博士表示：「雖然初期很令人興奮，但我們深知這個技術並不完美，還有很多工作要做。並且解決匹配問題也不意味著解決推薦中的所有問題。歡迎更多人來探討交流。」

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

雷鋒網 AI 科技評論編譯，感謝蓋坤博士的審閱指正

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！