關注“阿裡機器智能”官方公衆号，并在對話框内回複“K”，即可檢視原版論文。
1.背景
在許多推薦場景中，我們都需要一次性推薦一屏的物品給使用者，如下圖所示兩個例子（Taobao和YouTube）：
在論文中我們将這種場景稱之為exact-K recommendation問題，這個問題的目标是優化提高這一屏物品被點選或者滿足目标使用者需求的機率。于此同時，為了保障推薦的體驗，同一屏中的物品往往要滿足一定的限制，比如推薦物品之間需要具有一定的多樣性。Exact-K推薦問題可以看做是帶限制的組合優化問題，Top-K的方法則看做是一種啟發式的貪心解法。下面我們介紹論文中如果對該問題進行端到端的求解，并重點介紹論文中提出來的“Graph Attention Networks (GAttN)”模型和“Reinforcementfrom Demonstrations (RLfD)”訓練方法。
2.問題定義
**2.1Exact-K Recommendation問題
**
對于給定的包含N個物品的候選集合，我們的目标是從中選擇K個物品的集合，并将這K個物品作為一屏推薦給使用者，使得使用者對這一屏的點選率最高。在這裡，我們把A會被使用者u點選或者滿足使用者u需求的機率定義為，同時，A中的物品兩兩之間有時需要滿足一定的條件限制，定義為：
可以了解為兩個物品之間的某種限制，如果滿足限制，則，如果不滿足限制，則。當然，物品之間有時也不需要條件限制，此時。根據上面的定義，我們可以把Exact-K Recommendation問題形式化表示為下面的組合優化問題：
論文中從圖論的角度，可以重新了解我們剛才定義的問題。首先，把S中包含的N個物品作為圖中的N個節點，其中節點代表物品。如果物品之間的限制條件為空也就是時，那麼圖中兩兩節點之間的都有邊相連，如果C不為時，隻有滿足了條件的物品之間在圖中相應節點才有邊相連。既然要求推薦的K個物品兩兩之間都要滿足條件，是以問題變為了圖論中一個非常經典的問題，即在圖中找到一個K個節點的完全子圖，也就是K團。同時問題是最優化問題，相應的我們需要求解“最大”的K團，這裡“最大”是一個泛化的概念。舉個例子如下：
2.2節點權重估計方法
論文中首先介紹了一種基礎的方法，過程如下：
- 對于給定的使用者u和候選集合S，首先構造一張無向圖；
- 計算圖中每個節點的點選率CTR；
- 基于貪心算法，從目前的候選集合中選擇點選率最高的一個節點，加入到推薦結果集A中，并把至少與A中一個物品不相連的物品從目前的候選集中去掉；
- 重複第3步直到得到包含K個物品的推薦結果集合A。
這個方法非常類似Top-K推薦的思路，計算每個物品的點選率，然後從大到小進行展示，但這個方法的缺點也非常明顯：
- 點選率預估是單獨針對一個物品來計算的，而且K個物品之間的組合關系也沒有很好的考慮；
- 該方法啟發式地将“最大”K團問題轉化成了預估每個節點的權重然後求“最大權重和”的K團，并沒有直接地對目标進行優化，可能得不到最優解。
3.方法
3.1Graph Attention Networks
文章提出的方法稱為Graph Attention Networks，簡稱為GAttN，整體的架構采用Encoder-Decoder的方法，如下圖所示：
- 3.1.1 Input
對于給定的圖，圖中每個節點對應的物品的特征記作，使用者u的特征記作。是以Encoder的每個階段的輸入計算如下：
- 3.1.2 Encoder
傳統的Encoder一般選擇循環神經網絡如LSTM或GRU，但在這個問題裡順序是沒有意義的，因為輸入的各個物品之間是無序的。盡管各個物品之間無序，但它們之間的互相影響還是需要考慮的。是以，這裡的Encoder選擇的是Transformer裡面Multi-head Self-Attention機制。其中，Encoder具體包含三個sub-layers，如下所示：
- 3.1.3 Decoder
對于Decoder來說，要輸出K個物品集合A，代表圖中的一個包含K個節點的完全子圖。這裡使用的是循環神經網絡，輸出的集合是A的機率計算方式如下：
其中，這裡代表的是encoder的輸出（圖中每個節點的embedding），代表的是decoder的參數。得到輸出是集合A的機率可以表示為得到A中所有物品的聯合機率分布。這裡使用循環神經網絡來模組化聯合機率分布，在得到時，輸入包含兩部分，一個是上一個階段的隐藏層狀态，另一個是上一階段的輸出，是以可以得到下面的式子：
其中，
這樣可以得到Decoder每個階段的隐藏層狀态，那麼如何得到目前選擇的物品呢？參考下面的網絡結構圖：
這裡采用pointer-network的做法，首先使用一個attention機制，先讓decoder回顧（glimpse）一遍所有的encoder輸出，作為目前輸出的上下文：
接下來，我們要計算選擇每個物品的機率分布，首先這裡需要注意的一點是，Decoder每個階段的輸出組合起來，應該是圖中的一個團，是以，要確定目前選擇的物品能夠與之前選擇的物品在同一個完全子圖中，如果不能滿足這個條件，需要通過添加mask的方式，確定其不會被選擇到：
3.2 Reinforcement Learning from Demonstrations
回顧我們的優化目标是整個一屏的推薦結果集合A的點選機率最高，按照監督學習的思路，Decoder階段使用的是RNN的結構，我們隻能計算每個階段的交叉熵損失，是以網絡的優化目标和實際想要的目标是存在一定的gap的。是以，可以考慮通過強化學習中policy-gradient的思路直接優化目标。但是直接使用policy-gradient的方法，其訓練是比較低效的，前面的探索效率可能無法得到有效的保證。是以，可以認為監督學習方法是“有效率的（efficient）”，而強化學習的方法是“有效充分的（sufficient）”。
綜上所述，我們采取的思路是，結合了監督學習和強化學習，通過監督學習的方式對網絡參數進行一定的預訓練，再通過政策梯度的方式進一步修正網絡參數。我們将使用監督學習的方法稱作Learning from Demonstrations，使用強化學習的方法稱作Learningfrom Rewards。
- 3.2.1 Learning from Demonstrations
我們将從曆史日志中收集的一批真實的訓練資料稱作，通過定義通過交叉熵損失訓練模型：
上面的公式存在的一個問題就是，訓練階段時，Decoder輸入的是真實的物品，而在預測時，Decoder輸入的是上一階段輸出的物品，這就容易導緻錯誤積累的問題，這個問題在很多NLP的生成任務上都有讨論。是以我們設定在訓練階段時，Decoder輸入也直接使用上一階段輸出的物品，則損失函數變為：
- 3.2.2 Learning from Rewards
這裡複用強化學習的基本概念，把作為狀态state的話，decoder階段輸出的組合A可以看作動作action，而policy則是聯合機率分布。強化學習可以通過定義reward來直接優化問題的目标，是以我們定義了一個simulator來計算state和action對應的reward，直接使用曆史資料作為reward的話顯然是不夠的，因為大量的(state, action)組合沒有出現過。是以我們借鑒了逆強化學習（InverseReinforcement Learning）的思路，來訓練一個獎勵估計器（Reward Estimator）。這個估計器也比較簡單，即基于曆史資料來訓練一個給定物品集合A和使用者u的二分類模型，然後定義損失函數是logloss：
有了這個獎勵估計器，就可以通過政策梯度的方法訓練網絡：
其中，獎勵函數歸一化到-1到1之間。
由于通過REINFORCE方法訓練policy時獎勵函數是delayed，并且“正回報”也很稀疏（一般來說使用者點的少看得多），這樣也會導緻訓練時很難收到正向的reward，使得訓練變得很不穩定，并且收斂很慢。是以，我們借鑒了“爬山法”的思想，每次儲存5個結果，并從這5個結果中選擇能獲得最大獎勵的一個結果進行模型訓練。
- 3.2.3 Combination
結合上文說的兩種訓練方式，模型的最終loss為：
這裡有一個非常重要的參數來調節監督學習訓練和強化學習訓練的相對比重，而且可以根據訓練過程做相應的調整（如初期設定較大的監督學習比重，随後慢慢變小，逐漸向強化學習方式偏移）。整個Reinforcement learning from Demonstrations方法可以總結為下面算法流程：
4.實驗
4.1 實驗評估方法
首先我們不能使用傳統的排序方法的評價名額，如NDCG或MAP等，這些方法依賴對每個物品進行打分或者假設一個“好”的物品應該排在靠前的位置，是以并不适用于Exact-K推薦的問題。這裡我們定義了兩種離線實驗的評估名額，分别定義為Precision@K和Hit Ratio@K：
其中，Hit Ratio是一個基于覆寫率的名額，解釋為生成的物品集合A裡面有多少是覆寫到使用者真實偏好的物品集合的；Precision是一個基于準确度的名額，解釋為生成的物品集合A中是否包含了使用者點選的物品。
4.2 Baseline比較方法
在文章中我們比較了三種典型的排序學習方法：Pointwise、Pairwise和Listwise的方法。其中，Listwise方法最符合我們的問題，因為同樣考慮了排序物品之間的上下文資訊。其中代表性的工作是發表在SIGIR 2018的DLCM方法，該方法使用了GRU的循環神經網絡對排序物品進行模組化，同樣地我們任務将GRU替換成Transformer效果會有進一步的提升。但是上述方法隻是使用了監督學習的方法對問題進行求解。
4.3 實驗資料集
首先，我們使用了公開的MovieLens資料構造了我們問題的資料集，其中分别構造了MovieLens(K=4, N=20) 和MovieLens(K=10, N=50) 兩種資料集設定。于此同時，我們也使用了淘寶線上真實的資料集Taobao(K=4, N=50)，這個資料集的使用場景可以參考我們另一篇論文（已被CIKM2019接受）：
https://arxiv.org/pdf/1907.01639。
4.4 實驗結論
整體的實驗結果如下表所示：
可以看到我們的方法在所有資料集上都達到了最優的表現，于此同時可以看出Listwise的效果要遠好于Pairwise和Pointwise方法，證明了論文中所說的上下文模組化的重要性，同時基于Transformer的Listwise方法要優于基于GRU的方法，也驗證了引入Multi-head Self-Attention對上下文模組化的優勢。
在論文中，我們也做了多組的ablation tests，優于篇幅的原因這裡就不一一介紹。這裡隻強調一下一個相對來說最重要的超參數，用于調節訓練時監督學習loss和強化學習loss的比重。如下圖所示：
在圖中可以看出，在時效果最好。進一步看，當隻使用監督學習loss（也就是）時，我們可以初步得到一個較好的“次優解”，後面當逐漸加入強化學習方法時（減小），效果會進一步提升達到更優的解。這也驗證了我們在論文中提出的“Reinforcement Learning from Demonstrations”的訓練方法，可以達到兼顧sufficiency-and-efficiency的效果。
關于我們
在猜你喜歡團隊工作，你将要解決的問題域涉及對上億使用者在幾十億商品池中的推薦問題，不僅僅要考慮CTR、成交金額等業務名額，還需要系統化的解決上千萬賣家流量博弈的機制設計，以及推薦系統與使用者的互動體驗。團隊内的算法工程師和科學家将與你一起解決世界上規模最大電商平台上最困難的業務技術難題。在過去的幾年間，猜你喜歡團隊所負責的場景核心使用者名額一直保持非常高的增長速度，目前組内成員多來自國内外知名院校和研究所，近年在SIGKDD、AAAI、CIKM、WWW等學術會議上發表多篇論文。歡迎加入我們！郵箱：[email protected]
論文已被接收在SIGKDD 2019 research track oral。