246
技術社區[雲棲]
『幹貨』深度強化學習與自適應在線學習的阿裏實踐
1.1背景
淘寶的搜索引擎涉及對上億商品的毫秒級處理響應，而淘寶的用戶不僅數量巨大，其行為特點以及對商品的偏好也具有豐富性和多樣性。因此，要讓搜索引擎對不同特點的用戶作出針對性的排序，並以此帶動搜索引導的成交提升，是一個極具挑戰性的問題。傳統的Learning to Rank（LTR）方法主要是在商品維度進行學習，根據商品的點擊、成交數據構造學習樣本，回歸出排序權重。LTR學習的是當前線上已經展示出來商品排序的現象，對已出現的結果集合最好的排序效果，受到了本身排序策略的影響，我們有大量的樣本是不可見的，所以LTR模型從某種意義上說是解釋了過去現象，並不一定真正全局最優的。針對這個問題，有兩類的方法，其中一類嚐試在離線訓練中解決online和offline不一致的問題，衍生出Counterfactural Machine Learning的領域。另外一類就是在線trial-and-error進行學習，如Bandit Learning和Reinforcement Learning。
在之前我們嚐試了用多臂老虎機模型（Multi-Armed Bandit，MAB）來根據用戶反饋學習排序策略，結合exploration與exploitation，收到了較好的效果。
後來更進一步，在原來的基礎上引入狀態的概念，用馬爾可夫決策過程對商品搜索排序問題進行建模，並嚐試用深度強化學習的方法來對搜索引擎的排序策略進行實時調控。
實際上，如果把搜索引擎看作智能體（Agent）、把用戶看做環境（Environment），則商品的搜索問題可以被視為典型的順序決策問題。Agent每一次排序策略的選擇可以看成一次試錯（Trial-and-Error），把用戶的反饋，點擊成交等作為從環境獲得的獎賞。在這種反複不斷地試錯過程中，Agent將逐步學習到最優的排序策略，最大化累計獎賞。而這種在與環境交互的過程中進行試錯的學習，正是強化學習（Reinforcement Learning，RL）的根本思想。
本文接下來的內容將對具體的方案進行詳細介紹。
1.2 問題建模
馬爾可夫決策過程（Markov Decision Process，MDP）是強化學習的最基本理論模型。一般地，MDP可以由一個四元組表示：（1）S為狀態空間（State Space）；（2）A為動作空間（Action Space）；（3）為獎賞函數；（4）為環境狀態轉移函數（State Transition Function）
我們的最終目標是用強化學習進行商品搜索排序策略的學習，在實現的過程中，我們一步一步完成了從簡單問題到複雜問題的過渡，包括：
1. 基於值表（Tabular）強化學習方法的商品價格檔T變換控製（離散狀態、離散動作問題）；
2. 基於值表（Tabular）強化學習方法的商品展示比例控製（離散狀態、離散動作問題）；
3. 基於強化學習值函數估計（Value Function Approximation）的商品排序策略調控（連續狀態、離散動作問題）；
4. 基於強化學習策略估計（Policy Approximation）的商品排序策略調控（連續狀態、連續動作問題）。
1.2.1狀態定義
假設用戶在搜索的過程中傾向於點擊他感興趣的商品，並且較少點擊他不感興趣的商品。基於這個假設，我們將用戶的曆史點擊行為作為抽取狀態特征的數據來源。具體地，在每一個PV請求發生時，我們把用戶在最近一段時間內點擊的商品的特征作為當前Agent感知到的狀態。當然，在不同的問題中，狀態的表示方法會有所不同。例如，在值表強化學習方法中，狀態為可枚舉的離散變量；在值函數估計和策略估計方法中，狀態則表示為特征向量。
1.2.2 獎賞函數定義
Agent給出商品排序，用戶根據排序的結果進行的瀏覽、商品點擊或購買等行為都可以看成對Agent的排序策略的直接反饋。在第四章中，我們將利用獎賞塑形（Reward Shaping）方法對獎賞函數的表達進行豐富，提高不同排序策略在反饋信號上的區分度。
1.3算法設計
由於篇幅有限，我們僅對強化學習在搜索中的使用給出2個實例。
1. Tabular方法
我們在排序中要引入價格的因素來影響最終展示的價格，若以GMV為目標，則簡單可以表示為cvr*price，同時我們又想控製價格的作用程度，所以目標稍作修改：，加入一個變量t來控製價格的影響。這個t值的範圍很有限，可以用MAB或CMAB來找到最優解。
我們用強化學習的視角來對這個問題進行抽象，把用戶前2次點擊的商品價格檔位（0~7，從低到高）作為狀態。這個狀態表示的是用戶之前點擊商品的價格偏好，如果兩次都點擊1檔商品，說明用戶偏好低價商品，很有可能接下來用戶隻對低價商品感興趣，如果這個狀態轉移分布是穩定的（stationary），那麼一個統計模型可以就可以描述這種規律。而實際上，用戶的行為是受我們排序模型的影響的，用戶點擊1檔商品也可能是因為當前的排序策略隻給用戶展示了1檔商品，並不一定是用戶的本質需求。在接下來用戶的搜索過程中，我們可以有的選擇1是隻出1檔商品讓用戶的需求快速收斂，選擇2是投放一些附近檔位的商品供用戶選擇，如果用戶選擇了其他檔位的商品，進行了狀態的轉移，就可能找到一個更好的路徑，最終的收益和我們所有的過程中的投放策略都相關。從每個時間點上看，策略可能不是最優的，但全局上可能是最優的。
具體地，當用戶進行了搜索後，根據用戶的狀態s，和Q表（下圖）進行一個epsilon-greedy的投放，選擇一個動作a（上文中的價格指數t），執行這個a的排序結果展示給用戶，並記錄下這次的狀態s與動作a，以及用戶對這次搜索結果的反饋r，從用戶的點擊與否的反饋，再對Q表進行更新。
根據Q-Learning公式進行權重更新。
接下來，由於用戶點擊了某商品，他的狀態發生了轉移，就找到對應的狀態繼續進行epsilon-greedy的投放。再繼續進行學習，直到收斂。
2. DDPG方法
例如一個線性排序模型，
x是m維的特征向量，我們學習每個用戶狀態的最優參數w，即
這種假設需要使用策略估計的方法。策略估計（Policy Approximation）方法是解決連續狀態/動作空間問題的有效方法之一。其主要思想是用參數化的函數對策略進行表達，通過優化參數來完成策略的學習。通常，這種參數化的策略函數被稱為Actor。假設我們一共調控（）個維度的排序權重，對於任意狀態，Actor對應的輸出為
其中，為Actor的參數，對於任意（），是關於狀態的一個函數，代表第維的排序權重分，其形式可根據實際情況而定，我們的方案采用深度神經網絡作為Actor函數。這種方式在不同的狀態之間可以通過神經網絡來共享一些參數權重。
強化學習的目標是最大化任意狀態上的長期累積獎賞，根據策略梯度定理， Actor函數的參數的更新公式可以寫為
其中，為Actor神經網絡在狀態上關於的梯度，為狀態動作對（State-Action Pair）的長期累積獎賞。因為和都是連續的數值，我們采用深度神經網絡作為估計器對進行學習，具體的學習算法可參考深度Q學習算法DQN [1]。
1.4 獎賞塑型
我們最初采用的獎賞函數僅基於用戶在每一個PV中的點擊、成交行為反饋來構建。然而，在淘寶主搜這種大規模應用的場景中，我們較難在短時間內觀察到不同的排序策略在點擊和成交這樣的宏觀指標上的差別。因此，長期累積獎賞關於不同學習參數的梯度並無明顯區別，導致學習算法收斂緩慢。因此，我們有必要在獎賞函數中引入更多的信息，增大不同動作的區分度。
在進行強化學習方案的同時，我們用Pointwise LTR進行了一些對比實驗，發現Pointwise LTR這種直接在商品特征上進行學習的方式在求取策略梯度的時候，能夠將不同排序策略更為顯著地區分開。參照這個思路，我們將商品的一些屬性特征加入到獎賞函數的定義中，通過獎賞塑形（Reward Shaping）的方法[2, 3]豐富其包含的信息量。
獎賞塑形的思想是在原有的獎賞函數中引入一些先驗的知識，加速強化學習算法的收斂。簡單地，我們可以將“在狀態上選擇動作，並轉移到狀態”的獎賞值定義為
其中，為原始定義的獎賞函數，為包含先驗知識的函數，也被稱為勢函數（Potential Function）。我們可以把勢函數理解學習過程中的子目標（Local Objective）。根據上麵的討論，我們把每個狀態對應PV的商品信息納入Reward的定義中，將勢函數定義為
其中，為狀態對應PV中商品的個數，表示的第個商品，為Agent在狀態執行的動作，表示排序策略為時商品的點擊（或成交）的似然（Likelihood）。因此，也就表示在狀態上執行動作時，PV中所有商品能夠被點擊（或購買）的似然概率之和。
1.5 實驗效果
在雙11期間，我們在無線搜索排序的21和22號桶對強化學習方案進行了測試。下圖展示了我們的算法在學習的過程中的誤差（RNEU）變化情況，截取的時間範圍為11月10日18:00到11月11日8:00。
可以看到，從11月10日18:00啟動開始，每個桶上的RNEU開始逐漸下降。到當天20:00之後，下降趨勢變得比較緩和，說明學習算法在逐步往最優策略進行逼近。但過了11月11日0點之後，每個桶對應的RNEU指標都出現了陡然上升的情況，這是因為0點前後用戶的行為發生了急劇變化，導致線上數據分布在0點以後與0點之前產生較大差別。相應地，學習算法獲取到新的reward信號之後，也會做出適應性地調整。
2.1背景介紹
雙11主會場是一個很複雜的推薦場景。從推薦的業務形式上看，雙11主會場分為三層：分別是樓層、坑位以及具體素材圖的推薦。2016年的雙11主會場在整體的組織形式上與去年的雙11主會場類似，但具體業務的構成及組織有較大的不同。
首先，可推薦的樓層多於十層，我們需從中挑選數層進行展示，並有可能根據時間段和業務的需求進行調整。因此，展現形式的多變對模型的日誌特征學習造成了一定的幹擾。其次，坑位的構成分為三種會場入口：第一行是行業會場，第二行對應店鋪會場，第三行對應是標簽會場。最後，在樓層以及坑位都確定之後，我們需要每個的坑位入口上選擇具體的素材。2016年雙11主會場的素材有兩種不同的展現形式，分別是雙素材圖以及單素材圖。雙素材圖模式能提升用戶的點擊欲望，增強視覺感官衝擊力，但也會對用戶的真實點擊行為數據造成一定程度的幹擾或噪聲，甚至對排序的模型產生比較大的偏置。
由於2016年雙11首圖寶貝素材總量在百萬張且坑位數上百，我們會根據樓層的次序對參與打分的候選集進行配額，根據樓層的實時點擊率分配樓層的打分量。在各類業務以及填坑邏輯及調控流量的限製下，推薦結果並不一定能按照原有的打分高低進行展示。因此，我們需要考慮打分寶貝數與工程實現上的平衡關係。由於主會場的QPS高達數萬，一味地增大打分量是不可取的。為了解決這一問題，我們在初選的match召回方式上做了大量的努力，如提升用戶的多重興趣覆蓋、增大有效的候選寶貝。
根據在2015雙11的一些經驗並結合2016年雙11前期的係統壓測情況，在2016年雙11主會場我們采用了素材模型驅動的模式。從個性化推薦算法的角度來說，我們在2016年雙11主會場嚐試了多種新穎的排序模型，並做了嚴格的效果對比。具體的排序模型涉及LR、FTRL、GBDT+FTRL融合模型以及WIDE&DEEP模型，同時為了克服data drift的波動在日常的首圖場景還嚐試了Adaptive-Online-Learning的算法，以及嚐試了強化學習的思路。在後麵的章節，會從算法層麵逐一闡釋。
2.2算法模型
2.2.1 GBDT+FTRL模型
采用非線性模型學習intermediate feature，作為ID feature和cross feature的補充，最終輸入到線性model來做CTR預估，最早是由Facebook提出的，思路大致如下：采用raw features（一般是統計類特征）訓練出GBDT模型，獲得的所有樹的所有葉子節點就是它能夠generate出來的特征空間，當每個樣本點經過GBDT模型的每一個樹時，會落到一個葉子節點，即產生了一個中間特征，所有這些中間特征會配合其他ID類特征以及人肉交叉的特征一起輸入到LR模型來做CTR預估。顯然，GBDT模型很擅長發掘有區分度的特征，而從根到葉子節點的每一條路徑體現了特征組合。對比手工的離散化和特征交叉，模型顯然更擅長挖掘出複雜模式，獲得更好的效果。我們通過GBDT來做特征挖掘，並最終與FTRL模型融合的方案如下圖：
輸入到GBDT的特征非常關鍵，這些特征決定了最終產出的中間特征是否有效。我們有一套靈活的特征生成流程，可以方便做各種維度的特征提取以及交叉統計。GBDT+FTRL中主要用到的特征包含兩部分：第一部分是用戶/寶貝ID與對方泛化維度交叉統計的特征，包含各種基礎行為的次數以及CTR等。
第二部分是來自於match階段的一些連續類特征。推薦的match階段負責粗選出一部分跟用戶相關的content，該過程中會有多個模型分出現，例如做trigger selection的model分， content的最終match score等，這些分數來自於不同離線model，最終作為feature在online rank model中，能獲得非常好的ensemble效果。
2.2.2 Wide & Deep Learning模型
借鑒Google今年在深度學習領域的論文《Wide & Deep Learning for Recommender Systems》中所提到的Wide & Deep Learning框架（以下簡稱為WDL），並將其結合基於搜索事業部自研的機器學習平台的在線學習技術，我們研發了一套適用於推薦業務的WDL模型算法。下文將會對這一技術進行詳述。
WDL模型的原理框架如上圖所示：它將深度神經網絡(DNN)網絡和邏輯回歸(Logistic Regression)模型並置在同一個網絡中，並且將離散型特征(Categorical Feature)和連續型特征(Continuous Feature)有機地結合在一起。WDL模型主要由wide側和deep側組成。Wide側通過特征交叉來學習特征間的共現，而deep側通過將具有泛化能力的離散型特征進行特征嵌入(embedding)，和連續型特征一起作為深度神經網絡的輸入（可以認為是一種特殊的深度神經網絡，在網絡的最後一層加入了大量的0/1節點），從理論上來說，我們可以把deep側看作傳統矩陣分解(matrix factorization)的一種泛化實現，值得注意的是特征嵌入的函數是和網絡中其他參數通過梯度反向傳播共同學習得到。模型的預測值采用如下公式進行計算：
其中，wide側和deep側合並在一起計算後驗概率P(Y=1|x)；在誤差反向傳播(Backpropagation)的計算過程中時，我們對兩個方向同時進行計算。
2.2.3 Adaptive-Online-Learning（自適應在線學習）
傳統的在線學習模型沒有一種機製很好的判斷模型應該采用的多長時間的日誌進行訓練，目前業界的在線學習模型也都是通過經驗值的方式來進行數據截斷，自適應學習(adaptive learning)的最大優勢就在於能夠通過自我學習的方法適應業務的多變性。其實現原理在於保留下來每一個時刻開始到現在的數據學習到的模型，然後根據有效的評測指標，計算出各個模型的權重信息，並同時捕捉到數據分布快速變化波動的情況下的用戶實時興趣的細微差別，從而融合出一個最優的模型結果。
2.2.4 Reinforcement Learning（強化學習）
相比對每個推薦場景單獨進行個性化推薦的策略，基於強化學習框架（Reinforcement Learning）的推薦係統根據全鏈路的數據進行整合，同時響應多個異構場景的推薦請求。下圖中我們對手機淘寶（天貓）客戶端的數據/流量通路進行抽象：每個圓圈代表一個獨立的手淘場景，E代表用戶在該場景隨時離開，箭頭代表流量可能地流動方向。
基於以上的數據通路圖，我們可以很自然地將全鏈路多場景的推薦任務理解為一個連續的決策問題：作為一個智能決策者（agent），推薦係統需要持續不斷地決定應該為用戶推薦怎樣的內容（比如，商品、店鋪、品牌以及活動）。強化學習正是一種對智能決策者進行建模的最佳方式：通過對智能決策者短期狀態的變化進行遞歸式建模，最終引導其漸進式地優化長期目標。
手淘上的推薦場景相當豐富，最具代表性的是一個頁麵以列表的形式同時推薦多個商品的場景。為了便於讀者理解，我們首先介紹單個商品的推薦場景，之後再過渡到多商品的推薦場景。在單商品的推薦場景，a對應的是單個商品。我們的目標是學習在狀態s下采取動作a所能獲得的累積獎勵（的期望值）。我們用Q(s,a)來表示這一期望值。在這種情況下，我們隻需要選擇一種函數映射關係（如線性函數或神經網絡）將s和a所代表的向量映射到標量上對目標函數Q(s,a)進行擬合。
我們把這一定義延伸到典型的多商品推薦場景。由於文章長度有限，我們下麵介紹一種最簡單的思路，即假設用戶是否會點擊單商品的決策是獨立的。也就是說，假設用戶如果喜歡商品A，用戶不會因為在同一推薦列表中見到了他更喜歡的商品B而放棄點擊商品A。在這一假設下，我們對展示每個商品所獲得的累積獎勵的計算也是獨立的。通過一係列的推導，我們可以得到一個對狀態s下商品i能得到的分數f(s,i)的遞歸定義。
通過等式(7)，我們可以迭代計算對無偏估計值進行求解。實際情況中用戶必然會因為推薦商品的組合問題產生更複雜的行為，這樣一來必然導致累積獎勵獨立計算的假設不成立。但以此為本，我們可以推導出基於更複雜假設下的計算累積獎勵估計量的遞歸公式。
最後更新：2017-06-22 11:03:32