基于層次隱馬爾可夫模型和神經(jīng)網(wǎng)絡(luò)的個(gè)性化推薦算法

郭 聃

(四川現(xiàn)代職業(yè)學(xué)院電子信息技術(shù)系 四川 成都 610207)

0 引 言

個(gè)性化推薦系統(tǒng)現(xiàn)已成為電子商務(wù)、電影娛樂業(yè)以及新聞媒體領(lǐng)域中一個(gè)必不可少的部分，推薦系統(tǒng)不僅能夠提高用戶的瀏覽效率，而且能夠?yàn)榉?wù)提供商帶來經(jīng)濟(jì)效益[1]。協(xié)同過濾推薦系統(tǒng)是當(dāng)前最為成功且應(yīng)用最為廣泛的一種推薦系統(tǒng)模型，但目前的推薦系統(tǒng)領(lǐng)域主要關(guān)注于解決用戶評分的稀疏性問題和冷啟動(dòng)問題[2]，將提高推薦的準(zhǔn)確率作為首要目標(biāo)，而忽略了用戶的多樣性和個(gè)性化特點(diǎn)[3]。

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

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

1 推薦系統(tǒng)的問題模型

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

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

(1)

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

(2)

xuij=xui-xuj

(3)

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

本文對用戶進(jìn)行個(gè)性化項(xiàng)目排序，目標(biāo)是最大化用戶正負(fù)項(xiàng)目i∈Iu+和j∈Iu-的概率，采用ROC曲線的AUC作為度量方法：

(4)

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

2 層次隱馬爾可夫模型

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

2.1 總體結(jié)構(gòu)

每個(gè)上下文建模為一個(gè)隱藏變量，檢測用戶喜好之間的相同上下文模式，根據(jù)這些模式預(yù)測用戶的下一個(gè)上下文。包含兩層隱藏變量，將用戶對項(xiàng)目的正反饋序列作為訓(xùn)練第1層的觀測序列，第1層的隱藏變量作為訓(xùn)練第2層的觀測序列。第1層隱藏變量表示了用戶關(guān)于時(shí)間的潛在上下文，第2層隱藏變量提取了不同上下文狀態(tài)之間的相同模式。圖1為本文HMM的結(jié)構(gòu)圖。

圖1 層次隱馬爾可夫模型的兩層結(jié)構(gòu)

2.2 推斷過程

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

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

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

(5)

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

(6)

采用前向算法需要約L×N2次乘法運(yùn)算，小于直接計(jì)算的運(yùn)算量。

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

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

(7)

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

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

(8)

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

(9)

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

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

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

(10)

(11)

(12)

2.3 基于HMM產(chǎn)生推薦列表

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

算法1基于HMM的推薦算法

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

2.for each 用戶udo

3. for each用戶反饋信息

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

5. 基于觀測序列計(jì)算第1層的狀態(tài)序列；

6. 基于第1層狀態(tài)序列重新估計(jì)參數(shù)λ(C,D,π)；

7. 基于第1層序列計(jì)算第2層的狀態(tài)序列；

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

9. 基于λ(A,B,C,D,π)預(yù)測下一個(gè)項(xiàng)目；

10. end for

11.end for

HMM第1層：收集每個(gè)用戶的反饋序列，首先更新矩陣A和B，更新每個(gè)序列第1層的轉(zhuǎn)移概率矩陣和觀測概率矩陣。然后尋找第1層中似然最大的狀態(tài)序列，該序列等價(jià)于該用戶上下文狀態(tài)最相似的轉(zhuǎn)移概率序列，使用Viterbi算法[12]尋找最優(yōu)的隱狀態(tài)序列。根據(jù)第1層發(fā)現(xiàn)的序列更新矩陣C和D，再根據(jù)觀測的項(xiàng)目序列重新估計(jì)參數(shù)A和B。

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

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

圖2 層次隱馬爾可夫模型的上下文學(xué)習(xí)流程圖

3 基于神經(jīng)網(wǎng)絡(luò)的個(gè)性化排序模型

3.1 網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

本文網(wǎng)絡(luò)模型是多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，共有四層：用戶層L1、隱藏層L2、項(xiàng)目層L3和排序?qū)覮4，如圖3所示。L1層神經(jīng)元數(shù)量和用戶數(shù)量相等，L3層神經(jīng)元數(shù)量和項(xiàng)目數(shù)量相等，L2層神經(jīng)元數(shù)量K決定了用戶和項(xiàng)目的規(guī)模。

圖3 本文的多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

3.2 前向傳播

設(shè)R={(u,i,j)|u∈U,i∈Iu+,j∈Iu-}為訓(xùn)練樣本集。網(wǎng)絡(luò)采用二進(jìn)制形式表示每個(gè)用戶：a1∈{0,1}N，表示為指示向量形式(z0,z1,…,zN), 如果j=u，則zj=1，否則zj=0。隱層L2的輸出a2相應(yīng)變?yōu)椋?/p>

(13)

(14)

式中：k=1,2,…,K表示隱層的神經(jīng)元；函數(shù)f:RR為隱層的激活函數(shù)。a2和f之間存在以下的關(guān)系：

(15)

(16)

(17)

采用Sigmoid函數(shù)σ作為排序?qū)拥募せ詈瘮?shù)，比較用戶u對于項(xiàng)目i和項(xiàng)目j的喜好程度。

3.3 后向傳播

采用交叉熵C作為網(wǎng)絡(luò)的代價(jià)函數(shù)：

(18)

(19)

激活權(quán)重W的更新規(guī)則定義為：

W←W+αΔW

(20)

企業(yè)價(jià)值共創(chuàng)體系的涌現(xiàn)指由價(jià)值情報(bào)探測及分析系統(tǒng)、協(xié)調(diào)控制系統(tǒng)、協(xié)同生產(chǎn)系統(tǒng)等構(gòu)成的企業(yè)價(jià)值共創(chuàng)體系整體所具有的超越各組成系統(tǒng)的能力。借鑒穆勒提出的判斷涌現(xiàn)存在與否的三個(gè)判據(jù)［21］：可加性判據(jù)、新奇性判據(jù)和可演繹性判據(jù)［22-23］，將企業(yè)價(jià)值共創(chuàng)體系的涌現(xiàn)分為兩個(gè)層次：第一個(gè)層次是價(jià)值共創(chuàng)體系繼承與各組成系統(tǒng)的能力，但其能力指標(biāo)不是系統(tǒng)級(jí)能力指標(biāo)的簡單線性疊加，而是非線性的整體價(jià)值創(chuàng)造能力的改變值。第二個(gè)層次是價(jià)值共創(chuàng)體系具備的而單個(gè)體系組成系統(tǒng)并不具備的價(jià)值創(chuàng)造能力，表現(xiàn)在體系的整體價(jià)值創(chuàng)造能力指標(biāo)上。

(21)

(22)

(23)

后向傳播引起如下的權(quán)重變化：

(24)

(25)

(26)

最終更新用戶層u的激活神經(jīng)元，因?yàn)榫W(wǎng)絡(luò)的輸入為1u，所以用戶u的權(quán)重增量為：

(27)

3.4 Mini batch處理

本文神經(jīng)網(wǎng)絡(luò)同時(shí)處理一批樣本，設(shè)一個(gè)Mini batch的樣本量為p，從U中隨機(jī)選擇p個(gè)用戶，隨機(jī)選擇每個(gè)用戶的正項(xiàng)目和負(fù)項(xiàng)目，訓(xùn)練程序每次迭代中處理一個(gè)Mini patch。

3.5 偏置層

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

本文增加一個(gè)偏置層，該層聚集所有的偏置項(xiàng)，偏置層位于項(xiàng)目層和排序?qū)又g，根據(jù)相關(guān)的偏置項(xiàng)修改項(xiàng)目層的激活值。修改式(16)可獲得偏置層的輸出：

(28)

(29)

式中：bg表示全局偏置；bU為用戶偏置；bI為項(xiàng)目偏置。排序?qū)拥妮敵鲎優(yōu)椋?/p>

(30)

4 神經(jīng)網(wǎng)絡(luò)和貝葉斯個(gè)性化排序的關(guān)系分析

(31)

(32)

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

(33)

式中：Θ表示所有的模型參數(shù)。推導(dǎo)矩陣分解模型的所有權(quán)重，可獲得：

(34)

(35)

式中：p為用戶權(quán)重；q為項(xiàng)目權(quán)重。

根據(jù)文獻(xiàn)[13]的分析和結(jié)論，本文的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了貝葉斯個(gè)性化排序的效果。

5 實(shí) 驗(yàn)

5.1 網(wǎng)絡(luò)模型的實(shí)現(xiàn)方式和參數(shù)設(shè)定

本文實(shí)驗(yàn)的操作系統(tǒng)為Ubuntu 16.04，基于Pytorch verson 0.4.1實(shí)現(xiàn)本文的神經(jīng)網(wǎng)絡(luò)模型，Pytorch能夠完全占用GPU來加速模型的訓(xùn)練過程，實(shí)驗(yàn)采用Nvidia Quadro M6000的GPU，GPU訓(xùn)練一個(gè)epoch的速度大約是32核CPU的5倍。采用Pytorch缺省的L2正則化和Adam優(yōu)化器實(shí)時(shí)更新神經(jīng)網(wǎng)絡(luò)的權(quán)重。

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

5.2 實(shí)驗(yàn)數(shù)據(jù)集和對比方法

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

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

5.3 性能評價(jià)指標(biāo)

采用了推薦系統(tǒng)領(lǐng)域常用的3個(gè)性能指標(biāo)評價(jià)推薦結(jié)果的準(zhǔn)確性，分別為精度(P)、召回率(R)和F1-measure(Fm)。分別統(tǒng)計(jì)了top-5和top-10推薦結(jié)果的準(zhǔn)確性。

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

5.4 推薦準(zhǔn)確率實(shí)驗(yàn)

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

圖4 top-5推薦的準(zhǔn)確率結(jié)果

圖5 top-10推薦的準(zhǔn)確率結(jié)果

5.5 多樣性實(shí)驗(yàn)

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

圖6 推薦多樣性結(jié)果比較

5.6 個(gè)性化實(shí)驗(yàn)

因?yàn)镻attern Mining和KNN兩個(gè)算法并未考慮推薦結(jié)果的排序處理，所以僅將本文算法和HMM、BPRMFL兩個(gè)包含個(gè)性化排序的算法比較，結(jié)果如圖7所示。HMM系統(tǒng)將推薦準(zhǔn)確率作為主優(yōu)化目標(biāo)，將AUC作為次優(yōu)化目標(biāo)，其AUC結(jié)果低于BPRMFL算法。BPRMFL則采用矩陣分解實(shí)現(xiàn)了個(gè)性化排序，其結(jié)果優(yōu)于HMM系統(tǒng)。本文方法采用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了個(gè)性化排序的目標(biāo)，取得了最佳的個(gè)性化結(jié)果，其原因在于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)能力強(qiáng)于一般的矩陣分解技術(shù)。

圖7 推薦系統(tǒng)的個(gè)性化排序結(jié)果

6 結(jié) 語

本文采用兩層的隱馬爾可夫模型對推薦系統(tǒng)的上下文建模，設(shè)計(jì)了上下文的預(yù)測和推薦方法，再利用神經(jīng)網(wǎng)絡(luò)較強(qiáng)的學(xué)習(xí)能力，實(shí)現(xiàn)對推薦結(jié)果的個(gè)性化排序。基于層次隱馬爾可夫模型建模用戶在不同上下文的喜好變化，學(xué)習(xí)每個(gè)用戶狀態(tài)轉(zhuǎn)移的最大似然，根據(jù)概率分布預(yù)測用戶的下一個(gè)上下文，并產(chǎn)生預(yù)測上下文的推薦列表。此外，基于神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了個(gè)性化排序，其結(jié)果優(yōu)于矩陣分解的個(gè)性化排序方法。實(shí)驗(yàn)結(jié)果證明，本文在保持較高推薦準(zhǔn)確性的前提下，實(shí)現(xiàn)了較高的推薦多樣性和個(gè)性化。