潘 偉，胡春安

(江西理工大學信息工程學院，贛州 341000)

在許多實際問題中，如信號處理[1-2]、多標簽分類[3-4]、推薦系統(tǒng)[5]等問題，數(shù)據(jù)是以矩陣的形式呈現(xiàn)的，由于各種原因，對于某個矩陣，無法得到整個矩陣的元素值，有很大一部分元素是缺失的，如何將這些缺失的值準確合理地填充，是矩陣填充要解決的問題。

在推薦系統(tǒng)中，評分矩陣的行和列通常是相互關(guān)聯(lián)的，而低秩矩陣假設(shè)可以很好地反映出行與列之間的相關(guān)性。然而，矩陣的秩函數(shù)是非凸的、不連續(xù)的，即最小化矩陣的秩是一個不確定能不能在多項式時間內(nèi)解決(NP-hard)的問題，為了解決這個問題，通常的方法是將矩陣Y∈Rm×n分解成兩個低秩矩陣U和V，其中U∈Rm×r，V∈Rn×r，秩r遠小于m和n，使得UVT和原矩陣Y在已知元素位置處盡量相等。通常使用梯度下降和交替最小化方法來優(yōu)化求解[6-7]。由于目標函數(shù)在U和V中不是聯(lián)合凸的，這種方法的收斂速度很慢。

另一種方法是用矩陣的奇異值的和，即矩陣的核范數(shù)，來替代矩陣的秩進行求解。Candès等[8]提出矩陣的核范數(shù)是矩陣秩的包絡(luò)，使用凸優(yōu)化模型來解決此問題，將最小化矩陣的秩問題轉(zhuǎn)化為核范數(shù)最小化模型來進行求解。針對該模型，有很多優(yōu)化算法被提出。半定規(guī)劃(semi-definite programming)[8]是早期提出來的一個方法，然而該方法的時間復雜度和空間復雜度較高且只適用于矩陣維數(shù)很小的情況下。為此，文獻[9]提出了一種適用于較大規(guī)模的矩陣填充的奇異值閾值算法(singular value thresholding，SVT)，該算法在交替迭代的過程中保持了矩陣填充時的低秩性，然而該算法涉及奇異值分解，計算量會隨著矩陣規(guī)模變大而增加。文獻[10]提出了APG(accelerated proximal gradient)算法，其收斂速度相比于SVT更有競爭力。另外，壓縮感知[11]領(lǐng)域的貝葉斯學習方法[12-13]也可以應用到矩陣填充問題上。在貝葉斯框架下，低秩矩陣填充問題的擬合誤差和低秩性可以自動地平衡。貝葉斯學習方法雖然可以提高重構(gòu)性能，但是它在學習過程中有著煩瑣的矩陣求逆運算。廣義近似消息傳遞(generalized approximate message passing，GAMP)[14]是近年來提出的消息傳遞框架下的貝葉斯迭代算法，其優(yōu)點是在迭代計算時不需要計算逆矩陣，在迭代過程中，各數(shù)值的計算與先驗分布參數(shù)的取值有關(guān)。

現(xiàn)針對推薦系統(tǒng)中的評分矩陣稀疏性問題，用矩陣填充來進行建模，提出一種新的矩陣填充方法，首先采用分層高斯先驗模型[15]促進矩陣的低秩性，然后通過GAMP迭代得到評分矩陣后驗分布的近似估計，規(guī)避貝葉斯學習算法中矩陣求逆的過程，同時加入阻尼步驟以促進算法收斂，得到填充后的評分矩陣，最后在真實數(shù)據(jù)集上進行實驗評估，以期在預測用戶實際評分時得到更好的預測精度。

1 低秩矩陣填充理論

矩陣填充技術(shù)是近年來提出的一類數(shù)據(jù)降維模型，主要研究了對于一個未知的矩陣，如何通過已知的部分矩陣元素來合理地將缺失的數(shù)據(jù)進行填充。如果不加其他的約束，僅由部分少量的矩陣元素來恢復出整個矩陣，則滿足要求的矩陣有無數(shù)多個，因此矩陣填充是一個非適定性問題。然而，若原始矩陣Y∈RM×N是一個受約束的低秩矩陣，則可以通過優(yōu)化方法，將原始矩陣Y分解成低秩矩陣X與稀疏的噪聲矩陣E之和，從而使得矩陣X與原矩陣Y之間的差異最小化。從數(shù)學上講，對矩陣Y進行恢復的優(yōu)化問題可表述為

(1)

由于式(1)所示的優(yōu)化問題是NP(nondeterminism polynomial)難問題，文獻[8]利用矩陣的秩與其非零奇異值的個數(shù)相等這個性質(zhì)將此優(yōu)化問題的秩函數(shù)進行凸松弛，即用矩陣的核范數(shù)替代矩陣的秩，因此問題可轉(zhuǎn)化為

(2)

2 基于低秩矩陣填充的推薦算法

2.1 分層高斯先驗

為了促進矩陣X的低秩性，采用了一種分層高斯先驗模型[15]。在模型的第一層，假設(shè)矩陣X的列xn相互獨立且服從均值為零、方差為Σ-1的高斯分布，公式為

(3)

式(3)中：Σ∈RM×M為精度矩陣。在模型的第二層，采用了Wishart分布作為超先驗來描述第一層概率模型的超參數(shù)Σ,表示為

(4)

式(4)中：∝為等價于某一乘法常數(shù)；det(·)為矩陣的行列式；tr(·)為矩陣的跡；v為Wishart分布的自由度；W∈RM×M為Wishart分布的尺度矩陣。

假設(shè)噪聲矩陣E的每一個元素是獨立同分布的隨機變量并且服從均值為零、方差為γ-1的高斯分布。為了學習γ，將Gamma超先驗添加到γ之上，因此有

p(γ)=Gamma(γ|a,b)=Γ(a)-1baγa-1e-bγ

(5)

2.2 變分貝葉斯方法

在概率模型中，令y為觀測數(shù)據(jù)，θ{X，Σ，γ}為所有的隱變量。變分貝葉斯的基本原理是通過最大化邊際似然下界來獲取p(θ|y)的近似后驗分布q(θ)。其中邊際似然下界定義為

(6)

根據(jù)文獻[16]，假設(shè)q(θ)可以按照其組成變量θ分解，即存在如式(7)的表示形式，即

q(X，Σ,γ)=qx(X)qΣ(Σ)qγ(γ)

(7)

通過這樣的分解形式，可以很方便地采用交替更新的方式來最大化邊際似然下界L(q)。因此有

(8)

式(8)中：c為歸一化常數(shù)，用來保證式(8)左邊的函數(shù)成為一個積分為1的概率密度函數(shù)。詳細的貝葉斯推理過程如下。

2.2.1 更新qx(X)

計算qx(X)的過程可以分解為計算矩陣X的每個列xn的近似后驗分布，即qx(xn)。而qx(xn)的近似后驗分布計算公式為

lnqx(xn)∝〈ln[p(yn|xn)p(xn|Σ)]〉qΣ(Σ)qγ(γ)∝

(9)

式(9)中：yn為矩陣Y的第n列；On為矩陣Ω的第n列；Ω為矩陣Y中非零元素的位置矩陣?？梢钥闯觯瑇n服從高斯分布，即

qx(xn)=N(xn|μn,Qn)

(10)

式(10)中：μn=〈γ〉QnOnyn，Qn=(〈γ〉On+〈Σ〉)-1。

2.2.2 更新qΣ(Σ)

qΣ(Σ)的近似后驗分布可以通過式(11)來獲得，即

〈XTX〉)Σ]

(11)

因此，Σ服從Wishart分布，即

(12)

(13)

(14)

(15)

2.2.3 更新qγ(γ)

通過對qγ(γ)變分優(yōu)化得到，即

lnqγ(γ)∝〈lnp(Y|X,γ)p(γ)〉qx(X)∝

(16)

式(16)中：ymn和xmn分別為矩陣Y和X的第m行第n列的元素；S為矩陣Y中元素值不為空的元素下標的集合；L為集合S中元素值不為空的元素數(shù)目。

因此，qγ(γ)服從Gamma分布，即

(17)

(18)

(19)

2.3 廣義近似消息傳遞

廣義近似消息傳遞是由循環(huán)信念傳播框架發(fā)展而來的一種低復雜度的算法，其通過中心極限定理來有效地計算后驗分布的近似估計，可以將信號的后驗概率密度函數(shù)分解為簡單的概率密度函數(shù)。因此廣義近似消息傳遞可以從觀測值y中得到xn的后驗分布近似估計。

根據(jù)文獻[14]，廣義近似消息傳遞主要存在兩個重要的近似：

近似一在輸入端通過式(20)來近似真實后驗分布p(xm|y)，即

(20)

近似二在輸出端通過式(21)近似真實后驗分布p(zi|y)。公式為

(21)

根據(jù)文獻[14]，廣義近似消息傳遞迭代的詳細步驟如下：

(1)對于任意的i∈{1,2,…,M}，計算

(22)

(23)

(24)

(2)對于任意的m∈{1,2,…,M}，計算

(25)

(26)

Rangan等[17]研究了在GAMP算法中加入阻尼的步驟保證算法的收斂性，因此在本文算法中也加入阻尼運算，公式為

(27)

(28)

(29)

(30)

式中：阻尼系數(shù)β的取值范圍是0<β<1。

2.4 算法總結(jié)

現(xiàn)將提出的基于低秩矩陣填充的推薦算法步驟總結(jié)如下：

算法:基于低秩矩陣填充的推薦算法Input: rating matrix Y∈RM×N, relative error ε, maximum iterations KOutput: the predicted rating matrix X∈RM×N1: Initialize parameter a,b,β,v,W and γ;2: Σ←(Y YT)/N+I;3: for k=1 to K do4: compute qx(X) by using the damped GAMP;5: update Σ using Eq.(12);6: update γ using Eq.(17);7: if x(k)-x(k-1)F/x(k)F<ε8: then stop9: end for10: return X

3 實驗

3.1 實驗數(shù)據(jù)集與評估方法

為保證實驗結(jié)果的可比性，實驗采用推薦系統(tǒng)研究中常用的MovieLens 100k數(shù)據(jù)集[18]，該數(shù)據(jù)集包含了10萬條取值范圍在1～5的整型評分數(shù)據(jù)，這些評分數(shù)據(jù)是943名用戶對1 682部電影的評分記錄。因此這些評分數(shù)據(jù)可以組成一個943行 1 682列的評分矩陣。

平均絕對誤差(mean absolute error，MAE)和均方根誤差(root mean squared error，RMSE)是推薦領(lǐng)域常用的檢驗算法性能的評估方法。本文實驗采用MAE和RMSE作為評價標準。

MAE的定義為

(31)

RMSE的定義為

(32)

從定義來看，這兩種指標都是通過計算預測的評分值和實際的評分值之間的誤差來度量推薦算法的性能。MAE和RMSE小，意味著該算法的預測精度高，推薦性能好。

3.2 實驗結(jié)果及分析

算法中參數(shù)設(shè)定為：a=b=10-6，β=0.9，v=γ=1，W=10-10I，I為單位矩陣，ε=10-5。

第一個實驗考慮迭代次數(shù)對實驗結(jié)果的影響。圖1所示為本算法在迭代學習過程中評價標準MAE和RMSE隨著迭代次數(shù)的增大而逐漸下降的變化趨勢。實驗結(jié)果表明，在迭代次數(shù)多于1 400后，MAE為0.725左右，RMSE為0.925左右，MAE和RMSE開始收斂并逐漸趨于穩(wěn)定，即評分預測的準確性趨于穩(wěn)定。

圖1 迭代求解RMSE收斂走勢圖Fig.1 Convergence tends of RMSE over iterations

第二個實驗是為了比較本文算法的性能，選擇了近年來提出的層次矩陣分解(hierarchical matrix factorization，HMF)算法[19]、多重圖正則化矩陣填充(multiple graphs regularized matrix completion，MGRMC)算法[20]作為對比算法。HMF算法使用非負矩陣分解作為基本模型，同時利用了用戶和項目的顯式反饋和隱式反饋構(gòu)成一種分層結(jié)構(gòu)，解決了單一使用隱式反饋方法的不足。MGRMC算法建立矩陣的行和列的多圖關(guān)系，將單一圖正則化矩陣填充技術(shù)擴展到多重圖正則化矩陣填充，使得算法效果優(yōu)于單一圖正則化矩陣填充。實驗的結(jié)果如表1所示。

表1 三種算法的實驗結(jié)果對比Table 1 Comparison of experimental results of three algorithms

由表1中三種算法的實驗結(jié)果對比可以看出，本文提出的算法在MovieLens 100 k數(shù)據(jù)集上的MAE和RMSE都是最低的，說明本文算法效果優(yōu)于其他兩種對比算法。相較于HMF算法，本文算法的MAE和RMSE分別降低了3.33%和3.85%；相較于MGRMC算法，本文算法的MAE和RMSE分別降低了1.36%和1.07%。

4 結(jié)論

提出了一種基于低秩矩陣填充技術(shù)的推薦算法，通過采用分層高斯先驗模型，促進矩陣的低秩性，基于這一模型使用變分貝葉斯方法完成矩陣填充，并在廣義近似消息傳遞中加入阻尼步驟。通過實驗證明該算法在預測用戶評分的精度上勝于基于圖正則化矩陣填充的方法和層次矩陣分解方法，能夠進一步提高推薦算法性能。