基于層次隱馬爾可夫模型和神經網絡的個性化推薦算法

郭 聃

(四川現代職業學院電子信息技術系 四川 成都 610207)

0 引 言

個性化推薦系統現已成為電子商務、電影娛樂業以及新聞媒體領域中一個必不可少的部分，推薦系統不僅能夠提高用戶的瀏覽效率，而且能夠為服務提供商帶來經濟效益[1]。協同過濾推薦系統是當前最為成功且應用最為廣泛的一種推薦系統模型，但目前的推薦系統領域主要關注于解決用戶評分的稀疏性問題和冷啟動問題[2]，將提高推薦的準確率作為首要目標，而忽略了用戶的多樣性和個性化特點[3]。

電子商務等領域中普遍存在長尾分布的現象[4]，推薦系統更傾向于將“熱門”項目推薦給用戶，這會影響用戶的滿意度，也不利于服務提供商擴大經濟收益。此外，對指定用戶的推薦結果常常集中于少數的一些候選項目，導致推薦結果的排序成為用戶滿意度的又一個關鍵因素[5]。因此提高推薦的多樣性和個性化是一個極有意義的研究方向，近期也得到了研究人員的廣泛關注。文獻[6]基于用戶瀏覽的歷史記錄和當前的上下文場景為用戶提供多樣化的推薦列表。文獻[7]設計了兩階段的推薦方法，第一階段預測并補充稀疏的用戶評分，第二階段對協同過濾推薦的結果進行排序處理。目前提高推薦多樣性的主流方法都是通過顯式評分信息產生推薦列表，然后通過排序算法產生個性化的項目排序，這種方法所產生項目列表的多樣性依然有提高的空間[8]。

用戶和項目的大多數交互均為隱式信息，例如：音樂應用的用戶極少對音樂給出顯式評價，但是聽同一首音樂的次數、聽音樂的時間點和播放時長等隱式信息的價值甚至高于顯式的評分信息[9]。本文充分考慮用戶和項目交互的隱式信息，設計了一種基于層次隱馬爾可夫模型的上下文預測算法，基于預測的上下文產生對應的推薦項目集。此外，設計了神經網絡來求解協同過濾的推薦問題，其滿足貝葉斯個性化排序[10]的條件，因此神經網絡輸出的推薦結果經過了個性化的排序處理。

1 推薦系統的問題模型

設U={1,2,…,N}為一個用戶集，I={1,2,…,M}為一個項目集，交互數據集為S?U×I，(u,i)∈S表示用戶u和項目i的交互，正反饋記為(u,i)∈S，負反饋記為(u,i)∈(U×I)-S，正反饋和負反饋包含的項目分別稱為正項目和負項目，設Iu+表示用戶u的正項目集，Iu-表示用戶u的負項目集。

Iu+={i∈I:(u,i)∈S}

(1)

Iu-={i∈I:(u,i)∈(U×I)-S}

(2)

xuij=xui-xuj

(3)

式中：xuij表示對xui和xuj喜好的程度差異。

本文對用戶進行個性化項目排序，目標是最大化用戶正負項目i∈Iu+和j∈Iu-的概率，采用ROC曲線的AUC作為度量方法：

(4)

式中：H(·)為Heaviside函數。AUC值越接近1，性能越好。

2 層次隱馬爾可夫模型

推薦系統考慮的上下文主要包括時間上下文、地理上下文、社交上下文和模式上下文，模式挖掘是最常見的上下文感知方式，但在項目數量多或者數據稀疏性高的情況下，推薦的準確率較低。本文設計了兩層隱馬爾可夫模型(Hidden Markov Modeling,HMM)[11]自動學習每個用戶的潛在上下文，將上下文作為狀態(隱變量)，用戶喜好的項目為觀測量，學習的目標包括估計狀態的轉移概率、每個觀測量的概率分布以及狀態變化所引起的用戶上下文變化，利用這些潛在狀態表示用戶的上下文。

2.1 總體結構

每個上下文建模為一個隱藏變量，檢測用戶喜好之間的相同上下文模式，根據這些模式預測用戶的下一個上下文。包含兩層隱藏變量，將用戶對項目的正反饋序列作為訓練第1層的觀測序列，第1層的隱藏變量作為訓練第2層的觀測序列。第1層隱藏變量表示了用戶關于時間的潛在上下文，第2層隱藏變量提取了不同上下文狀態之間的相同模式。圖1為本文HMM的結構圖。

圖1 層次隱馬爾可夫模型的兩層結構

2.2 推斷過程

將HMM模型的參數表示為λ(A,B,C,D,π)，N為第1層的狀態量，M為項目(觀測變量)的數量，A為第1層的狀態轉移概率，B為隱藏狀態和項目之間在第1層的觀測概率矩陣，C為第2層的狀態轉移概率，D為第2層和第1層之間的觀測概率矩陣，π為初始化狀態分布，設O=(O0,O1,…,OL-1)表示長度為L的觀測序列，Oi表示從用戶收到反饋的第i個項目。基于HMM的推薦系統需要解決以下3個核心問題：1) 計算觀測序列的似然；2) 計算概率最大的狀態序列；3) 估計HMM模型的參數。

直接計算問題1)需要約2L×NL次乘法運算，所以采用前向算法來減少問題的復雜度：

αl(i)=P(O0,O1,…,Ol,xl=si|λ)

(5)

式中：l為時間戳；αl(i)為在l的觀測序列概率；si為馬爾可夫過程的狀態。

(6)

采用前向算法需要約L×N2次乘法運算，小于直接計算的運算量。

采用后向算法解決問題2)：

βl(i)=P(Ol+1,Ol+2,…,OL-1|xl=si,λ)

(7)

式中：遞歸計算αl(i)和βl(i)。對于所有的觀測變量和狀態，定義以下的關系：

γl(i)=P(xl=si|O,λ)

(8)

αl(i)度量了時間l之前的相關概率，βl(i)度量了時間l之后的相關概率。狀態序列的概率定義為：

(9)

根據γl(i)的定義，時間戳l可能性最高的狀態是最大化γl(i)的狀態si。

問題3)的解決方法是將矩陣的大小固定，然后確定合適的矩陣元素：

γl(i,j)=P(xl=si,xl+1=sj|O,λ)

(10)

(11)

(12)

2.3 基于HMM產生推薦列表

算法1是基于兩層隱馬爾可夫模型的上下文感知推薦算法。

算法1基于HMM的推薦算法

1.隨機初始化HMM的模型參數λ(A,B,C,D,π)；

2.for each 用戶udo

3. for each用戶反饋信息

4. 基于給定的觀測序列重新估計參數λ(A,B,π)；

5. 基于觀測序列計算第1層的狀態序列；

6. 基于第1層狀態序列重新估計參數λ(C,D,π)；

7. 基于第1層序列計算第2層的狀態序列；

8. 基于λ(C,D,π)預測下一個上下文；

9. 基于λ(A,B,C,D,π)預測下一個項目；

10. end for

11.end for

HMM第1層：收集每個用戶的反饋序列，首先更新矩陣A和B，更新每個序列第1層的轉移概率矩陣和觀測概率矩陣。然后尋找第1層中似然最大的狀態序列，該序列等價于該用戶上下文狀態最相似的轉移概率序列，使用Viterbi算法[12]尋找最優的隱狀態序列。根據第1層發現的序列更新矩陣C和D，再根據觀測的項目序列重新估計參數A和B。

HMM第2層：通過最大似然決定第2層的狀態序列，該序列是第2層隱藏變量中最可能發生轉移的序列，所以該序列反映了上下文的變化。基于訓練的上下文轉移概率(參數C和D)，預測用戶的下一個上下文。給定預測的上下文和觀測概率矩陣B，推導出和預測上下文匹配的推薦列表。

在模型訓練完成之后，將矩陣C和D相乘，預測用戶的下一個上下文。然后，將矩陣A和B相乘，計算每個項目被推薦的概率。最終，基于計算的概率和預測的上下文，生成上下文對應的top-N推薦項目。層次隱馬爾可夫模型的總體程序流程如圖2所示。

圖2 層次隱馬爾可夫模型的上下文學習流程圖

3 基于神經網絡的個性化排序模型

3.1 網絡結構設計

本文網絡模型是多層前饋神經網絡結構，共有四層：用戶層L1、隱藏層L2、項目層L3和排序層L4，如圖3所示。L1層神經元數量和用戶數量相等，L3層神經元數量和項目數量相等，L2層神經元數量K決定了用戶和項目的規模。

圖3 本文的多層前饋神經網絡結構

3.2 前向傳播

設R={(u,i,j)|u∈U,i∈Iu+,j∈Iu-}為訓練樣本集。網絡采用二進制形式表示每個用戶：a1∈{0,1}N，表示為指示向量形式(z0,z1,…,zN), 如果j=u，則zj=1，否則zj=0。隱層L2的輸出a2相應變為：

(13)

(14)

式中：k=1,2,…,K表示隱層的神經元；函數f:RR為隱層的激活函數。a2和f之間存在以下的關系：

(15)

(16)

(17)

采用Sigmoid函數σ作為排序層的激活函數，比較用戶u對于項目i和項目j的喜好程度。

3.3 后向傳播

采用交叉熵C作為網絡的代價函數：

(18)

(19)

激活權重W的更新規則定義為：

W←W+αΔW

(20)

企業價值共創體系的涌現指由價值情報探測及分析系統、協調控制系統、協同生產系統等構成的企業價值共創體系整體所具有的超越各組成系統的能力。借鑒穆勒提出的判斷涌現存在與否的三個判據［21］：可加性判據、新奇性判據和可演繹性判據［22-23］，將企業價值共創體系的涌現分為兩個層次：第一個層次是價值共創體系繼承與各組成系統的能力，但其能力指標不是系統級能力指標的簡單線性疊加，而是非線性的整體價值創造能力的改變值。第二個層次是價值共創體系具備的而單個體系組成系統并不具備的價值創造能力，表現在體系的整體價值創造能力指標上。

(21)

(22)

(23)

后向傳播引起如下的權重變化：

(24)

(25)

(26)

最終更新用戶層u的激活神經元，因為網絡的輸入為1u，所以用戶u的權重增量為：

(27)

3.4 Mini batch處理

本文神經網絡同時處理一批樣本，設一個Mini batch的樣本量為p，從U中隨機選擇p個用戶，隨機選擇每個用戶的正項目和負項目，訓練程序每次迭代中處理一個Mini patch。

3.5 偏置層

協同過濾的矩陣分解模型在預測評分的程序中引入偏置項，有助于提高預測的準確性，并且能夠加快訓練的速度。偏置項將評分預測劃分為多個元素：用戶-項目-交互項、用戶偏置、項目偏置和全局偏置，用戶偏置和項目偏置可理解為全局偏置的平均偏差。

本文增加一個偏置層，該層聚集所有的偏置項，偏置層位于項目層和排序層之間，根據相關的偏置項修改項目層的激活值。修改式(16)可獲得偏置層的輸出：

(28)

(29)

式中：bg表示全局偏置；bU為用戶偏置；bI為項目偏置。排序層的輸出變為：

(30)

4 神經網絡和貝葉斯個性化排序的關系分析

(31)

(32)

貝葉斯個性化排序(Bayesian Personalized Ranking,BPR)表示為：

(33)

式中：Θ表示所有的模型參數。推導矩陣分解模型的所有權重，可獲得：

(34)

(35)

式中：p為用戶權重；q為項目權重。

根據文獻[13]的分析和結論，本文的神經網絡實現了貝葉斯個性化排序的效果。

5 實 驗

5.1 網絡模型的實現方式和參數設定

本文實驗的操作系統為Ubuntu 16.04，基于Pytorch verson 0.4.1實現本文的神經網絡模型，Pytorch能夠完全占用GPU來加速模型的訓練過程，實驗采用Nvidia Quadro M6000的GPU，GPU訓練一個epoch的速度大約是32核CPU的5倍。采用Pytorch缺省的L2正則化和Adam優化器實時更新神經網絡的權重。

實驗中對Aadm優化器的學習率、隱層神經元數量和批大小3個超參數進行專門的調節，其他超參數采用Pytorch的缺省值。超參數的優化步驟為：人工設置初始化的超參數；設計局部搜索算法進行優化處理。局部搜索算法的具體過程為：選擇一個參數，隨機將該參數增大或者減小10%，如果網絡的AUC性能得以提升，則持續該參數的變化方式；如果性能下降，則進行相反的變化方式，重復10次，選擇其中性能最好的兩個參數值。實驗發現參數值的差異較小，最終學習率設為0.01，隱藏層的神經元數量設為K=100，批大小為500。

5.2 實驗數據集和對比方法

采用Netflix數據集作為benchmark數據集，該數據集共包含100 480 507個評分、17 770部電影和480 189名用戶。數據集也含有用戶對電影評分的時間戳。

選擇4個與本文接近的推薦系統作為對比，分別為：(1) 基于隱馬爾可夫模型的推薦系統[14]，簡稱為HMM。本文也采用隱馬爾可夫模型對上下文進行建模和預測，以驗證本文方法的上下文預測效果。(2) 基于模式挖掘的推薦系統[15]，簡稱為Pattern Mining。模式挖掘是一種常用的多樣性推薦系統，該方法用來驗證本文方法的多樣性效果。(3) 基于貝葉斯個性化排序和矩陣分解的推薦系統[16]，簡稱為BPRMF。貝葉斯個性化排序是一種經典的個性化排序模型，本文的神經網絡也滿足貝葉斯個性化排序的條件，用來驗證本文方法的個性化推薦效果。(4) 基于k近鄰的推薦系統[17]，簡稱為KNN。KNN是一種以推薦準確率為首要目標的推薦系統，是目前最常見的推薦系統類型。

5.3 性能評價指標

采用了推薦系統領域常用的3個性能指標評價推薦結果的準確性，分別為精度(P)、召回率(R)和F1-measure(Fm)。分別統計了top-5和top-10推薦結果的準確性。

采用流形偏置方法[18]評價推薦結果的多樣性，該方法將項目集按照頻率排序，然后均勻分為10個bin，同一個bin內項目的流形度相似。

5.4 推薦準確率實驗

圖4和圖5分別為各算法top-5和top-10的推薦結果。HMM、Pattern Mining、BPRMF系統的推薦準確率均高于KNN算法，KNN算法僅考慮了用戶評分的相似性，而本文benchmark數據集的評分數據稀疏性較大，所以KNN的準確率較低。HMM、Pattern Mining、BPRMF系統均考慮了數據的潛在信息和上下文信息，因此其推薦精度、召回率和F1-measure略優于KNN算法。本文方法設計了上下文預測機制，充分利用了benchmark數據集的時間戳信息，并且對推薦列表進行了個性化的排序，所以取得了較好的推薦準確性。

圖4 top-5推薦的準確率結果

圖5 top-10推薦的準確率結果

5.5 多樣性實驗

圖6比較了本文方法和其他推薦系統的多樣性。可以看出，KNN的推薦項目全部為最流行的10%項目，多樣性較差；HMM考慮了數據的隱式反饋信息和上下文環境，其推薦多樣性好于Pattern Mining和BPRMF。而本文方法的推薦多樣性好于HMM算法，并且明顯考慮了長尾分布的項目，實現了較好的推薦多樣性。

圖6 推薦多樣性結果比較

5.6 個性化實驗

因為Pattern Mining和KNN兩個算法并未考慮推薦結果的排序處理，所以僅將本文算法和HMM、BPRMFL兩個包含個性化排序的算法比較，結果如圖7所示。HMM系統將推薦準確率作為主優化目標，將AUC作為次優化目標，其AUC結果低于BPRMFL算法。BPRMFL則采用矩陣分解實現了個性化排序，其結果優于HMM系統。本文方法采用神經網絡實現了個性化排序的目標，取得了最佳的個性化結果，其原因在于神經網絡的學習能力強于一般的矩陣分解技術。

圖7 推薦系統的個性化排序結果

6 結 語

本文采用兩層的隱馬爾可夫模型對推薦系統的上下文建模，設計了上下文的預測和推薦方法，再利用神經網絡較強的學習能力，實現對推薦結果的個性化排序。基于層次隱馬爾可夫模型建模用戶在不同上下文的喜好變化，學習每個用戶狀態轉移的最大似然，根據概率分布預測用戶的下一個上下文，并產生預測上下文的推薦列表。此外，基于神經網絡實現了個性化排序，其結果優于矩陣分解的個性化排序方法。實驗結果證明，本文在保持較高推薦準確性的前提下，實現了較高的推薦多樣性和個性化。