Q-learning算法優化的SVDPP推薦算法

周運騰，張雪英，李鳳蓮，劉書昌，焦江麗，田 豆

（太原理工大學信息與計算機學院，太原 030600）

0 概述

隨著網絡和信息技術的不斷發展，現實社會中網絡信息的數據量呈指數級增長。面對種類繁多的信息，如何獲取個性化服務已成為人們的迫切需求。個性化推薦［1］通過各種推薦算法分析用戶的行為喜好，能夠有效過濾用戶不需要的信息，主動為用戶提供個性化的產品或服務。目前，個性化推薦已被廣泛應用于社交［2］、新聞、音樂、圖書和電影網站等應用［3］，如網易云音樂［4］、淘寶商品推薦［5］、Netflix和MovieLens電影推薦等。

協同過濾（Collaborative Filtering，CF）技術［6］可用于推薦算法，其主要包括基于內存和基于模型兩類算法。其中：基于內存的協同過濾推薦算法通過分析“用戶-項目”評分矩陣計算相似度，并根據相似度進行預測推薦；基于模型的協同過濾推薦算法通過用戶的歷史購買記錄、網絡操作等數據訓練一個預測模型，進而利用此模型對項目進行預測評分。許多研究通過改進協同過濾算法優化了推薦效果，如限制性玻爾茲曼機、K近鄰算法［7］、奇異值分解［（8］Singular Value Decomposition，SVD）算法及其改進模型（Singular Value Decomposition Plus Plus，SVDPP）。SVD不僅是一個數學問題，其在很多工程中也得到了成功應用。在推薦系統方面，利用SVD可以很容易地得到任意矩陣的滿秩分解，進而實現對數據的壓縮降維。SVDPP在SVD基礎上進一步融入了隱式反饋信息，采用隱式偏好對SVD模型進行優化，因此性能更優。但是SVDPP與SVD都沒有考慮時間戳對推薦性能的影響，而實際推薦效果與時間戳仍然有一定的關聯性，如十年前的用戶對某一部電影的評分與當前用戶的評分是有一定差異的，因此有必要對其進行改進，優化預測效果。

本文考慮時間戳對推薦性能的影響，通過馬爾科夫決策過程（Markov Decision Process，MDP）對用戶、評分、電影和時間進行建模，并利用強化學習Q-learning算法優化推薦算法，從而提升推薦效果，實現更準確的預測。

1 問題描述

在使用基于模型的推薦算法進行預測時，SVD和SVDPP模型都沒有考慮時間戳對于推薦準確性的影響，而用戶之前看過的電影會對他之后選擇觀看的電影類型及其對電影的評分產生影響。因此，本文利用馬爾科夫決策過程對這種時序決策問題建模，反映時間戳數據與評分的關系，并通過強化學習對推薦算法進行優化。

Q-learning算法是一種基于反饋和智能體的無模型的強化學習方法，本文提出一種基于Q-learning算法優化的SVDPP推薦算法RL-SVDPP，以解決SVDPP在電影推薦預測中未考慮時間戳影響的問題。

強化學習［9-10］作為一種機器學習方法，主要原理是智能體以試錯的方式進行學習，通過自身與環境交互獲得獎勵。目前，強化學習已經被成功應用到神經網絡和文本處理等領域，但將該方法直接應用于推薦算法的研究較少，現有研究主要通過結合深度神經網絡進行模型訓練并推薦預測［11］。筆者受啟發于Netflix Prize比賽中競賽選手將時間戳應用到矩陣分解模型［12］，以及文獻［13］將強化學習用于協同過濾的思路，考慮到用戶對一部未看過電影的評分可以通過他之前看過的電影評分來預測，即時間戳會影響用戶對未知電影的評分，將SVDPP推薦算法得到的預測評分進一步采用馬爾科夫決策過程中的獎懲函數進行優化，建立推薦預測評分與馬爾科夫決策過程之間的映射關系，并利用強化學習Q-learning算法［14］進行模型訓練，以優化預測過程。

2 建模過程

2.1 奇異值分解

現實生活中的“用戶-項目”矩陣規模很大，但是由于用戶的興趣和消費能力有限，單個用戶消費產生評分的物品是少量的，SVD的核心思想是將高維稀疏的矩陣分解為2個低維矩陣，相對于特征值分解只能用于對稱矩陣，SVD能對任意M×N矩陣進行滿秩分解，以實現數據壓縮。但是在采用SVD對矩陣進行分解之前，需要對矩陣中的空白項進行填充，以得到一個稠密矩陣。假設填充前的矩陣為R，填充后為R′，則計算公式為：

利用SVD算法獲取預測評分的計算公式如下：

其中：μ代表評分的平均值；bu、bi分別代表用戶u和電影i的偏置量；qi、pu分別對應電影和用戶在各個隱藏特質上的特征向量，上標T代表轉置。

如果用戶對某個電影進行了評分，則說明他看過這部電影，這樣的行為蘊含了一定的信息，從而可以推理出評分這種行為從側面反映了用戶的喜好，據此可將這種喜好通過隱式參數的形式體現在模型中，得到一個更為精準的模型SVDPP［15］。

利用SVDPP模型獲取預測評分的計算公式如下：

其中：N（u）為用戶u瀏覽和評價過的所有電影的集合；yj為隱藏的評價了電影j的個人喜好偏置；用戶u的偏好程度由顯式反饋pu和隱式反饋兩部分組成。

2.2 馬爾科夫決策過程

馬爾科夫決策過程是決策理論規劃、強化學習及隨機域中其他學習問題的一種直觀和基本的構造模型［16］。在這個模型中，環境通過一組狀態和動作進行建模，可用于執行控制系統的狀態。通過這種方式來控制系統的目的是最大化一個模型的性能標準。目前，很多問題（如多智能體問題［17］、機器人學習控制［18］和玩游戲的問題［19-20］）成功通過馬爾科夫決策過程進行建模，因此，馬爾科夫決策過程已成為解決時序決策問題的標準方法［21］。

一般的馬爾科夫決策過程由五元組＜S，A，P，γ，Rew＞表示，如圖1所示，其中，st表示狀態，at表示動作，rt表示回報函數。智能體感知當前環境中的狀態信息，根據當前狀態選擇執行某些動作，環境根據選擇的動作給智能體反饋一個獎懲信號，根據這個獎懲信號，智能體就從一個狀態轉移到了下一個狀態。

圖1 馬爾科夫決策過程Fig.1 Markov decision process

采用強化學習方法對SVDPP推薦模型進行優化，首先需要建立推薦預測模型與馬爾科夫決策過程的映射關系。由于本文采用MovieLens 1M數據集作為研究對象，因此需要將用戶在不同時間戳下對電影的評分轉換成五元組以構造馬爾科夫決策過程。下面給出本文設計的電影評分到馬爾科夫決策過程的映射關系。

2.3 狀態表生成

由上述馬爾科夫決策過程可知，一個狀態轉移到下一個狀態的動作對應下一個時間電影的評分，雖然這樣在表面上忽略了電影名及電影類型，但用戶對電影的喜好被隱式地反映在時間戳里，通過這個過程可將MovieLens 1M數據集處理為表1所示的形式。其中，括號中的第1個數字反映了對應行用戶給對應列電影的評分，第2個數字反映了對應行用戶觀看對應列電影的時間戳信息或者時間順序，如第1行第1列（4，3th）表示用戶1觀看電影1的時間順序是第3個，因此，時間戳t=3且用戶1對電影1打了4分，NaN表示對應用戶未觀看這部電影。

表1 MovieLens 1M數據集部分數據Table 1 Partial data of MovieLens 1M data set

將表1的數據按照時間戳排序，生成的狀態轉移路徑如下：

根據表1得到該狀態轉移路徑的規則，以第1行為例進行說明。第1行狀態轉移路徑5→3→4 →3反映了用戶1在時間戳t=1時看電影3，對電影3的評分為5，t=2時看電影2，對電影2的評分為3，t=3時看電影1，對電影1的評分為4，t=4時看電影5，對電影5的評分為3。其余4個轉移路徑采用類似方式得到。

此狀態轉移路徑表示馬爾科夫決策過程中狀態的轉移，指引了Q表更新的方向。

3 RL-SVDPP算法

本文提出的RL-SVDPP算法包括訓練與預測兩部分。訓練時，首先采用SVDPP算法對訓練集進行模型訓練，得到SVDPP推薦模型，如式（3）所示，然后對強化學習模型進行訓練，利用式（5）所示的獎懲函數計算狀態轉移的獎懲值Rew，完成強化學習Q表的更新，用于SVDPP推薦評分的優化模型。預測時，首先根據SVDPP推薦模型得到預測評分值，再用本文設計的優化模型對預測評分進行優化，得到最終的預測評分。本文設計的優化模型表示如下：

3.1 訓練過程

首先通過式（3）對訓練集進行訓練，得到SVDPP推薦模型；然后對強化學習模型進行訓練，利用式（5）計算獎懲值Rew，進而將Rew用于Q-learning算法中Q值的更新過程。Q表更新公式如下：

RL-SVDPP算法訓練過程的偽代碼如下：

算法RL-SVDPP算法訓練過程

3.2 預測過程

預測過程根據SVDPP推薦模型得到的預測評分，結合訓練的Q表來預測用戶u對電影i的評分，同時可預測用戶u未觀看但是其他用戶觀看過的電影。

3.3 數據稀疏性及邊界點問題的處理

本文所采用的MovieLens 1M數據集存在缺省值，即存在沒有評分的電影信息。根據本文優化模型的構建思路，后續優化過程中需要利用未評分電影評分信息，這將導致中可能缺少s或者a的值，從而使優化模型失效。為避免出現這一情況，本文采用SVDPP模型對缺失值進行預測再取整填充，以解決數據稀疏的問題。

此外，當t=1，2時，邊界的會超出下標范圍，出現沒有對應取值的情況。因此，本文采用最后兩列的預測評分作為第－1列和第0列的預測評分數據，以保證數據的完整性。

4 實驗

4.1 實驗數據

本文實驗采用MovieLens 1M數據集，其中包含6 040個用戶對3 952個影片的近1億條評分，評分范圍為1分～5分。本文將數據的80%作為訓練集來訓練RL-SVDPP模型，其他的20%作為測試集，通過均方根誤差（Root-Mean-Square Error，RMSE）來評價推薦算法的準確性。

4.2 評價指標

評分預測的準確度一般通過均方根誤差來決定，定義如下：

其中：rui表示測試集中用戶u對電影i的真實評分；為采用本文算法得到的預測評分；T為電影集合；N表示該用戶看過的電影總數。

4.3 實驗結果與分析

為驗證本文算法的有效性，除了對SVDPP模型進行優化得到RL-SVDPP模型外，同時也對SVD模型進行訓練，建立優化模型RL-SVD。實驗分別建立SVD及SVDPP模型，并求出預測評分，以得到獎懲函數Rew，根據獎懲函數可得到對應的獎懲表，如表2和表3所示。獎懲函數作為馬爾科夫決策過程中最重要的部分，能夠隱式地反映學習目標，指出馬爾科夫決策過程的前進方向。在表2和表3中，行表示狀態，列表示動作，如－1.137 11表示在狀態1時，進行動作1得到的獎勵值為－1.137 11，其他以此類推，其中獎勵值為正表明對正確行為給予獎勵，獎勵值為負表明對錯誤動作給予懲罰。

表2 由SVD預測評分得到的獎懲表Table 2 Reward and punishment table by SVD prediction scores

表3 由SVDPP預測評分得到的獎懲表Table 3 Reward and punishment table based by SVDPP prediction scores

將獎懲函數Rew用于Q表更新過程，更新后的Q表如表4和表5所示?？梢钥闯?，通過Q-learning算法訓練生成的Q表中的值有正有負。為更形象地進行描述，將表中數據繪制成三維空間圖，如圖2和圖3所示，其中，凸起和凹陷部分表示在某狀態下采取動作獲得的期望收益有好有壞。可以看出：RL-SVD算法Q表三維圖中Q值動態變化范圍較大，變化范圍為－0.979 930～1.000 000，25個Q值中有14個為負值；RL-SVDPP算法得到的Q表三維圖中Q值動態變化范圍較小，變化范圍為－0.145 190～0.175 280，25個Q值中有10個為負值。這表明RL-SVDPP選擇正確動作得到獎勵的情況多于選擇錯誤動作進行懲罰的情況，因此，其優化性能優于RL-SVD。下文將通過RMSE性能對比進一步驗證該結論。

表4 由SVD預測評分得到的Q表Table 4 Q table by SVD prediction scores

表5 由SVDPP預測評分得到的Q表Table 5 Q table by SVDPP prediction scores

圖2 RL-SVD算法Q表三維圖Fig.2 3D diagram of Q table for RL-SVD algorithm

圖3 RL-SVDPP算法Q表三維圖Fig.3 3D diagram of Q table for RL-SVDPP algorithm

對20%的測試集采用本文提出的優化模型RL-SVD和RL-SVDPP計算預測評分，并通過式（8）求解其與實際評分的均方根誤差，驗證本文優化方法的有效性。RMSE比較結果如表6所示。

表6 本文算法與已有SVD/SVDPP的RMSE對比Table 6 Comparison of RMSE by the proposed algorithm and the existing SVD/SVDPP

可以看出：相對SVD算法，采用RL-SVD算法得到的預測結果比優化前SVD算法預測結果的RMSE降低了0.004 3；相對SVDPP算法，采用本文提出的RL-SVDPP算法得到的預測結果比優化前SVDPP的RMSE降低了0.005 6，驗證了本文融合時間戳信息建立的強化學習優化的推薦模型的有效性，也說明用戶對電影的評分與時間戳確實有一定的關系。

由于學習率α和折扣因子γ是可以動態調整的，因此進一步研究RL-SVDPP算法中α和γ的變化對預測性能的影響，實驗結果如圖4和圖5所示。由圖4可知，當γ一定時，α從0.000 003增大到0.3，10倍遞增，RMSE的值會增大，并且當α比較大時，RMSE變化很小，因此，α應盡可能取較小的值。由圖5可知，當α一定時，γ從0.4增大到0.6，RL-SVDPP算法的RMSE不斷減小，實驗中最好的效果是當α=0.000 003和γ=0.6時，此時RMSE能達到0.819 48，相比之前降低了0.008 6，由此證明了RL-SVDPP算法的可行性。

圖4 γ 一定時α 變化對RMSE的影響Fig.4 Effect of α change on RMSE with constant γ

圖5 α 一定時γ 變化對RMSE的影響Fig.5 Effect of γ change on RMSE with constant α

5 結束語

本文提出一種強化學習Q-learning算法優化的SVDPP推薦算法RL-SVDPP。將用戶在不同時間戳下對電影的評分動作轉化為馬爾科夫決策過程，結合協同過濾算法與強化學習獎懲過程進行建模，對SVDPP推薦預測評分進行優化，并通過調整影響因子來改善預測效果。實驗結果表明，用戶過去的評分數據對當前的評分有顯著影響，將用戶對電影的喜好隱式地反映在時間戳中，有助于得到更精確的結果。本文僅采用強化學習方法中的Q-Learning對SVDPP進行優化，如何能通過融入時間戳對算法直接進行優化，或者將強化學習與其他推薦方法（如深度學習網絡）相結合進行優化，將是下一步的研究方向。