本文主要介紹發表在SIGIR2018上的論文

From Greedy Selection to Exploratory Decision-Making: Diverse Ranking with Policy-Value Networks?

www.bigdatalab.ac.cn

這篇論文利用強化學習來解決多樣性排序問題，整體思路和AlphaGo類似。

  1. Motivation

在信息檢索領域一個重要的目標是提供可以覆蓋很多topic的檢索結果，也就是檢索結果的多樣性。簡單來說就是選擇候選文檔的一個最小子集，這個子集能夠儘可能多的包含subtopic。因為文檔是否新穎取決於已經選擇的文檔，因此這是個NP-hard的問題。一些傳統的方法都是把檢索多樣性看成是基於相關性和新穎性的一個排序問題，這些方法的核心是利用貪心來選擇文檔，每一次從候選集合中選擇一個文檔。貪心方法雖然可以加速在線排序，但是可想而知這種方法不可避免的會陷入次優解，因為它每次選擇只考慮局部信息，而文檔的「貢獻"(utility)並不是獨立的，是與其他文檔相關聯的，每次選擇一個文檔後都會改變候選集合中的剩餘文檔的utility，理想的解決方法是探索所有文檔的排序，但在實際應用中這顯然無法實現。得益於AlphaGo的成功，作者提出利用蒙特卡洛樹搜索(Monte Carlo tree search-MCTS)來改善MDP模型。新的模型 M^2Div(MCTS enhanced MDP for Diverse ranking)利用一個MDP來對序列文檔的選擇進行建模，在每次進行選擇時，將query和已有文檔送給RNN來產生policy和value，policy用來進行文檔的選擇而value用來估計整體文檔排序的質量，比如 alpha-NDCG@M 。為了防止次優解，作者使用MCTS來探索每個位置的可能的文檔排序，由此產生一個對於當前選擇的更好的policy。因為MCTS探索了更多未來可能的文檔，它給出的policy有更大的概率產生全局最優解。當有了更好的policy後，模型通過最小化loss function來進行調整。

2. MDP和MCTS

馬爾可夫決策過程(MDP)是建模序列決策的一個框架，關鍵部分為States，Action， Policy， Transition和Value。具體的，States S 是狀態的集合，在文章中作者定義狀態為query、已有文檔排序和候選文檔的三元組；Action A 是agent可以執行的離散動作集合，可選的動作會依賴於狀態s，記為 A(s) ; Policy p 描述agent的行為，它是所有可能動作的一個概率分布，通過最大化長期回報進行優化；Transition T 是狀態轉移函數 s_{t+1}=T(s_t, a_t) ，也就是根據動作 a_t 將狀態 s_t 映射為 s_{t+1} ；Value 是狀態值函數 V:S ightarrow R ,用來預測當前基於policy p下狀態s的長期回報。MDP模型中agent和環境在每個時刻 t=0,1,2,... 進行交互，在每個時間步 t agent接收環境的狀態 s_t ，然後選擇一個動作 a_tin A(s_t) ,之後 agent進入一個新的狀態 s_{t+1}=T(s_t, a_t)，強化學習的目標是最大化長期回報，也就是最大化Value V(s_0) 。

通過MDP做的決策(根據policy選擇置信度最大的動作)可能會陷入次優解，理論上我們應該探索所有的決策空間來得到全局最優解，但是這是不現實的。MCTS就是在決策空間中進行啟發式的搜索，這樣更容易產生比貪心更好的決策序列。給定時刻 t ,policy p 以及值函數 V ，MCTS的目標是找到一個「加強版」的策略來進行更好的決策。MCTS包含四個過程，分別是Selection，Expansion，Simulation/Evaluation 和 Back-propagation。Selection是從根節點開始，遞歸的選擇一個最優子節點直到到達葉子節點；Expansion 指如果 L 不是一個終止節點，那麼為 L 創建子節點並且根據policy選擇一個子節點 C ；Simulation/Evaluation 是從 C 進行一次模擬直到結束。在AlphaGo Zero中使用值函數代替模擬來加速樹的搜索。Back-propagation來更新當前序列中的每個節點裡的數值。MCTS最終輸出一個policy pi ,這個策略用來在 t 時刻選擇動作。MCTS會持續的進行，直到完整的episode生成為止。

3. Algorithm

這一部分介紹 M^2Div模型，模型整體如圖

可以看出在每個時間步模型選擇一個文檔，首先模型通過LSTM來產生 p(a|s_t) 和 V(s_t) ，然後進行搜索，產生加強版的策略，之後根據策略選擇動作並進入下一個狀態。

3.1定義文檔排序的MDP

定義候選文檔全集為 X={x_1,x_2,...,x_M} ，每個文檔通過doc2vec模型轉化為向量，在時刻 t ，狀態為 s_t=[q, Z_t, X_t] ，其中 q 為query， Z_t={x_{(n)}}_{n=1}^t 是已選擇的文檔， X_t 是候選文檔，在初始狀態( t=0 ), s_t=[q,phi,X] , phi 為空集；動作 A(s_t) 是可以選擇的動作集合，也就是對應每一個候選文檔；狀態轉移 T 為 s_{t+1}=T(s_t, a_t)=T([q,Z_t,X_t],a_t)=[q,Z_toplus{x_{m(a_t)}},X_tackslash {x_{m(a_t)}}] 其中 oplus 為將 x_{m(a_t)} 添加到 Z_t 中， ackslash 為將 x_{m(a_t)} 從X_t 去除。每次選擇新的文檔query是保持不變的，新文檔添加到 Z_t 的末尾；值函數 V 用來估計整體排序的質量，通過學習 V 來近似評價指標，比如 alpha-NDCG@M 。具體的，值函數 V 的計算如下 V(s)=sigma(langle w, LSTM(s) angle+b_v) LSTM 的輸入為query和已有文檔的向量表示，輸出為cell state向量與output vector的concatenate，也就是 LSTM(s)=[h_t^T,c_t^T]^T ；有了值函數，可以計算policy p ，計算方法如下 p(a|s)=frac{exp{x_{m(a)}^T U_ ho LSTM(s)}}{sum_{ain A(s)}exp{x_{m(a)}^T U_ ho LSTM(s)}} 其中 U_ ho 為參數，最終的策略函數 p(s) 為 p(s)=langle p(a_1|s),...,p(a_{|A(s)}|s) angle 。

3.2 MCTS

有了值函數和策略函數後，作者提出使用MCTS來進行改進，也就是在每個時刻 t ，根據值函數 V 和策略函數 p 進行MCTS搜索得到更好的策略 pi 。因為MCTS探索整體的排序空間，所以 pi 比上式得到的 p 會選擇更好的動作。具體演算法為

在Selection階段( line 3 - line 7)，每次搜索都從根節點 s_R 開始選擇最大化upper confidence bound的文檔。注意這個根節點並不是樹的根節點，而是t 時刻的狀態。最大化upper confidence bound的標準為 a_t = argmax_{a}(Q(s_t,a)+lambda U(s_t,a))

由 a_t 的定義可以看出，Q(s_t,a) 是動作值函數，可以看做選擇某個動作的回報，考慮的是「利用」，而 U 更傾向於「探索」，也就是更喜歡訪問次數少的節點， lambdageq0 ，是平衡因子，U(s_t,a) 定義為 U(s_t,a)=p(a|s_t)frac{sqrt{sum_{ain A(s_t)}N(s_t,a)}}{1+N(s_t,a)}

p(a|st) 是策略函數 p(s_t) 的預測概率， N(s_t,a) 是節點的被訪問次數。上式是PUCT演算法的一個變體。

在Evaluation and expansion階段( line8 - line 19)，當到達一個葉節點 s_{L} 時，如果是episode的結尾，那麼可以用已有的評價指標進行評估，比如 alpha-NDCG@M ，否則可以用值函數來評估 V(s_L) 。如果 s_L 可以展開，那麼對每個動作構建新的節點並且初始化，也就是 line 11- line 16。

在Back-propagation and update( line 20 - line 28)中，我們更新 Q 和 N Q(s,a)leftarrow frac{Q(s,a) imes N(s,a)+V(s_t)}{N(s,a)+1} N(s,a)leftarrow N(s,a)+1

本質上 Q(s,a) 是每次從狀態 s 選擇動作 a 的對應的值函數的相加再求平均，也就是 Q(s,a) = frac{1}{N(s,a)}sum_{l} V(s_l) ,文中的公式是增量更新的形式。在Algorithm 1的 line 29 - line 32，根據已有的 N(s_R, a) 來計算 pi pi(a|s_R)=frac{N(s_R,a)}{sum_{ain A(s_R)}N(s_R,a)}

3.3 利用強化學習訓練網路

有了更好的策略 pi 後，在每個時刻 t 都使用 pi_t 進行文檔選擇。當候選集合為空或者已經滿足挑選文檔個數時不再進行文檔的排序，此時利用已有的文檔排序，可以和真實的文檔計算評價指標，用 r 表示。所有時刻的狀態和MCTS的策略組成 E={(s_t, pi_t)}_{t=1}^T ，我們要優化的目標為 l(E,r)=sum_{t=1}^{|E|}((V(s_t)-r)^2+sum_{ain A(s_t)}pi_t(a|s_t)logfrac{1}{p(a|s_t)}) 第一項為平方誤差，希望值函數在每個狀態的值都和 r 接近；而第二項是為了讓LSTM輸出的策略與MCTS得到的策略更接近。loss function形象化表示如下圖

整體演算法如下

可以看出針對每個query，在每個時刻選擇文檔時，利用MCTS來進行選擇。當結束排序後，根據排序結果以及每個時刻的策略 pi 和 p 進行模型的更新，最終得到一個訓練好的LSTM模型。

3.4 Online ranking

MCTS是比較耗時的，在線上進行排序的時候可能會對服務有不小的壓力。作者提出了Online ranking的方法，就是在排序時不再進行MCTS，直接用LSTM輸出的策略。作者用實驗驗證了不使用MCTS的時候模型仍然會高於baseline。這得益於訓練時MCTS的貢獻，MCTS使模型能夠輸出更精確的策略。

3.4 與AlphaGo Zero的不同

雖然受到了AlphaGo Zeor的啟發，但 M^2Div 與之還是有不同的。作者總結了三點，第一使任務的形式化不同。圍棋是兩人進行博弈，狀態是棋盤以及落子位置，而多樣性排序只需要每次挑選一個文檔。第二是監督信息不同，在圍棋中監督信息是最後的輸贏，而在多樣性排序中監督信息是各種多樣性的評價指標。第三是網路模型不同，AlphaGo Zero使用了殘差網路而排序使用了LSTM，這也是由於任務不同而有不同的選擇。

4. Experiment

作者與其他演算法進行了對比，實驗結果如下

可以看出在測試階段使用MCTS的效果最好。除此之外，作者還對比了在沒有MCTS的排序中使用策略還是使用值函數，隨著訓練迭代的增多，使用策略效果會更好

一個可能的原因是 alpha-NDCG@M 的優化相對困難，尤其是在訓練的初期。

5. 結束語

這篇文章利用強化學習來進行多樣性排序，與已有方法相比效果由明顯的提升。用AlphaGo演算法的整體框架來解決序列排序問題確實也比較自然，尤其是文檔之間還會互相的影響。這種方法也可以應用到其他序列生成的任務中，最直接的比如導航時路線生成，理想狀況下是可以根據路況來選擇道路的。強化學習應用很廣，期待能在更多的場景下發揮作用。


推薦閱讀：
相关文章