基于加權Schatten-p范數的矩陣填充及其應用

潘 偉 胡春安

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

0 引 言

隨著互聯網的快速發展,網上用戶規模與內容服務呈幾何數量級增長,社會信息超過了個人能接受的范圍,海量的信息導致了信息過載問題[1],推薦系統成為解決這一問題的重要工具,并在許多領域得到了應用,如電子商務[2]、新聞推薦[3]、音樂推薦[4]以及電影視頻推薦[5-6]等。

推薦系統中使用最廣泛的方法是基于協同過濾的推薦算法。協同過濾方法包括基于記憶的協同過濾和基于模型的協同過濾。基于記憶的協同過濾利用物品被評分的記錄或用戶過去的行為計算物品之間的相似度或用戶之間的相似度構成最近鄰集合,從而對目標用戶的興趣進行預測,產生推薦結果?；谀Ｐ偷膮f同過濾利用已知評分矩陣訓練預測模型,訓練好的模型為用戶生成推薦。雖然協同過濾方法被廣泛研究和應用,但依然存在一些問題,例如評分矩陣的稀疏性導致用戶之間或物品之間的相似度計算不穩定,矩陣的高維度導致相似度計算量非常大。為了解決評分矩陣的稀疏性問題,文獻[7]利用矩陣填充技術,將矩陣中空缺的元素合理準確地填充,提出了一種加權的核范數最小化模型,該模型提高了核函數的靈活性,提升了矩陣填充時的精度和速度,但在矩陣規模大的情況下優勢不明顯。文獻[8]提出基于加權核范數正則化項的最小化方法模型(Weighted Nuclear Norm Minimization,WNNM),通過構造與奇異值大小相反的權值來更好地逼近原矩陣。

本文提出一種基于加權Schatten-p范數最小化模型。該模型利用Schatten-p范數來替代核范數對評分矩陣進行低秩約束,同時采用對奇異值加權的方式以更好地逼近原始秩函數,此外,近端交替線性化最小化(Proximal Alternating Linearized Minimization,PALM)方法被用來求解非凸最小化問題,通過在MovieLens數據集上實驗驗證了所提出模型在推薦結果精準度上得到了提升。

1 相關理論

在推薦系統中,用戶-項目的關系一般用矩陣表示,矩陣的元素值代表了某用戶對某項目的評分,要實現評分的預測,可以通過填充用戶-項目評分矩陣來完成。

對于一個部分矩陣元素未知的矩陣M∈Rm×n,矩陣填充問題可以定義為以下的秩最小化問題:

s.t.PΩ(X)=PΩ(M)

(1)

式中:X∈Rm×n是填充所得矩陣;rank(X)表示矩陣X的秩;Ω是矩陣M中已知元素的下標的集合;PΩ(·):Rm×n→Rm×n表示正交投影算子。當元素的下標(i,j)∈Ω時,(PΩ(X))ij=Xij;當元素的下標(i,j)∈Ω時,(PΩ(X))ij=0。

由于秩函數的非凸性和不連續性,式(1)所示的秩最小化問題是個NP問題,并且問題的復雜度隨著矩陣維數的增長呈指數關系增長。因此現有的很多矩陣填充方法用核范數,即矩陣的奇異值的和,來代替矩陣的秩[9],從而將式(1)轉化為如下形式:

s.t.PΩ(X)=PΩ(M)

(2)

式中:‖·‖*表示矩陣的核范數。矩陣X∈Rm×n的核范數定義成:

(3)

式中:σi(X)表示矩陣X的第i個最大的奇異值。

通過使用內點法,可以將式(2)所示的核范數最小化問題轉化為半定規劃(Semi-Definite Programming,SDP)[9]問題。在許多的實際應用中,所需填充矩陣的維數都非常高,而SDP只適用于矩陣維數較低的情況。

為了有效地解決核范數最小化問題,特別是在矩陣維數較高的情況下,文獻[10]提出了奇異值閾值(Singular Value Thresholding,SVT)方法。該方法用如下形式表示:

s.t.PΩ(X)=PΩ(M)

(4)

式中:參數τ大于0,‖·‖F表示矩陣的Frobenius范數,該優化問題可以通過迭代的奇異值收縮算子[10]來求解。對于一個秩為r的矩陣X,奇異值分解為:

X=UΣVT,Σ=diag({σi},1≤i≤r)

(5)

在該奇異值分解中,U∈Rm×r,V∈Rn×r均由正交的奇異向量構成。

對于每個τ,有軟閾值操作:Sτ(Σ)=diag({σi-τ}+),其中{σi-τ}+=max(σi-τ,0)。

使用奇異值收縮算子Dτ:Dτ(X)=USτ(Σ)VT,從而生成新的矩陣。

為了改變不同奇異值對秩函數的影響,提高核范數在實際應用中的靈活度,文獻[7]提出了用于矩陣填充的加權核范數最小化模型:

(6)

核函數雖能很好地逼近秩函數,但在實際應用中其效果還沒有達到最優。為了更好地逼近秩函數,文獻[11]提出了使用Schatten-p范數來逼近秩函數,Schatten-p范數表示為:

(7)

式中:參數p的取值范圍是0

2 加權Schatten-p范數最小化模型

結合WNNM的加權性和Schatten-p范數最小化,本節提出了一種基于加權Schatten-p范數的矩陣填充模型WSNM-PALM,該方法利用評分矩陣奇異值的稀疏性,即矩陣的低秩性,同時考慮了不同秩的重要性,采用比核范數具有更佳低秩逼近的加權Schatten-p范數來對矩陣作低秩約束,使用近端交替線性化最小化方法來求解模型中的非凸最小化問題。

2.1 模型的建立

對于一個已知的評分矩陣Y∈Rm×n,m和n分別表示用戶數量和項目數量,本文所提模型的目的就是要通過填充得到一個近似Y的低秩矩陣X∈Rm×n。矩陣X的加權Schatten-p范數的定義如下:

(8)

式中:wi為σi(X)對應的權重,所有的權重構成了一個向量w=(w1,w2,…,wmin(m,n))。因此可以得到加權Schatten-p范數的p次方為:

(9)

于是可以得到如下優化問題:

s.t.PΩ(X)=PΩ(Y)

(10)

權重參數wi的取值為:

(11)

式中:C和ε為均常數。

2.2 模型的求解

針對式(10)所示的優化問題,本文采用近端交替線性化最小化[12-13](PALM)方法來進行求解。根據文獻[14],對于一個矩陣X∈Rm×n,可以將其分解為兩個子矩陣的乘積,并且存在以下等式:

(12)

式中:A∈Rm×d,B∈Rd×n,d≥rank(X)。

受核范數和雙線性譜正則化之間的關系啟發,文獻[15]定義了兩種范數:Frobenius/核混合范數和雙核范數,分別用‖X‖F/N和‖X‖BiN表示。這兩種范數與Schatten-p范數之間的關系滿足下式:

‖X‖F/N=‖X‖S2/3

(13)

‖X‖BiN=‖X‖S1/2

(14)

式中:‖X‖S2/3表示X的Schatten-2/3范數;‖X‖S1/2表示X的Schatten-1/2范數。因此有:

(15)

(16)

于是,式(10)可以轉化為如下相等的問題:

(17)

(18)

式中:λ是正則化項的系數。

(19)

因此對于問題(17),在第k+1次迭代時,A和B的更新求解步驟如下:

(20)

(21)

(22)

(23)

式中:‖B‖2表示矩陣B的最大奇異值。

同樣地,對于問題(18),在第k+1次迭代時,A和B的更新求解步驟為:

(24)

(25)

式(17)和式(18)分別是p=2/3和p=1/2時要求解的優化問題。所提出模型的求解算法描述如算法1所示。

算法1WSNM-PALM算法

輸入:矩陣Y∈Rm×n, 參數λ,ε,d。

輸出:補全矩陣X*∈Rm×n。

初始化:對矩陣Y中的未知元素用已知元素的平均值填充,k=0

1) 對矩陣Y進行奇異值分解,計算權重wi,A0和B0

2) Repeatk=0, 1, 2, …

4) 若p=1/2,則通過式(24)更新變量Ak+1;

5) 若p=2/3,則通過式(20)更新變量Ak+1;

7) 若p=1/2,則通過式(25)更新變量Bk+1;

8) 若p=2/3,則通過式(21)更新變量Bk+1;

9)Xk+1←Ak+1Bk+1;

10) Until 達到預設的停止條件

3 實驗與結果分析

3.1 實驗設置

實驗采用推薦系統研究中常用的MovieLens 1M數據集[16],該數據集包含了100萬條整型評分數據,這些評分數據是6 400名用戶對3 900部電影的評分記錄。實驗在配置為Intel Core i5 2.40 GHz CPU、6 GB內存的Windows 10 PC機上進行,運行環境為MATLAB R2014a。

平均絕對誤差(Mean Absolute Error,MAE)和均方根誤差(Root Mean Squared Error,RMSE)是常用的度量推薦算法性能的評估方法。本文實驗采用MAE和RMSE作為評價指標。其定義分別為:

(26)

(27)

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

為了驗證提出模型的有效性,對比方法選取加權核范數模型WNNM[8],并選取矩陣分解類算法ConvMF[17]、MFMSR[18]作為參照。加權核范數模型WNNM使用加權核范數作為正則化項,構造和奇異值大小相反的權值,使得近似矩陣能很好地逼近原矩陣;ConvMF算法利用評分和項目描述文檔,以概率的角度將卷積神經網絡集成到概率矩陣分解中,有效解決了評分數據的稀疏性問題;MFMSR算法通過提取項目內容的多維語義特征,并以正則化方式融入概率矩陣分解模型,緩解了用戶-項目交互行為數據的稀疏性。

3.2 性能對比

文獻[8]中的實驗將MovieLens 1M數據集上49.86%的評分數據作為訓練集,50.14%的評分數據作為測試集,因此所提出模型與WNNM模型對比實驗時也按照0.498 6:0.501 4劃分訓練集和測試集。實驗的結果如表1所示。

表1 WSNM-PALM與WNNM的性能對比結果

可以看出,WSNM-PALM模型的推薦性能優于WNNM模型,MAE值和RMSE值分別降低了1.04%和2.53%。

所提出模型與ConvMF和MFMSR進行性能對比實驗時,將MovieLens 1M數據集按照0.8∶0.2劃分訓練集和測試集。實驗的結果如表2所示。

表2 WSNM-PALM與ConvMF和MFMSR的性能對比結果

可以看出,所提出的算法的性能優于ConvMF和MFMSR。相較于ConvMF,所提出算法的MAE值和RMSE值分別降低了1.92%和1.67%;相較于MFMSR,所提出算法的MAE值和RMSE值分別降低了0.63%和0.85%。

3.3 相關參數分析

為了研究參數p對WSNM-PALM性能的影響,分別取p=2/3和p=1/2,保持其他參數不變,觀察在MovieLens 1M數據集上MAE和RMSE的實驗結果,結果如圖1和圖2所示。

圖1 不同p值下MAE收斂走勢圖

圖2 不同p值下RMSE收斂走勢圖

可以看出,迭代開始時收斂速度較快,當迭代次數達到1 000時,收斂變緩,MAE和RMSE的值逐漸趨于穩定,當p=1/2時,MAE值達到0.660 0,RMSE值達到0.841 8;當p=2/3時,MAE值達到0.666 8,RMSE值達到0.848 9。p取1/2時算法的性能優于p取2/3時算法的性能。

為了研究參數λ對算法性能的影響,實驗設置λ的值從0.005～0.009以0.001的間隔遞增,p取值為1/2,其他的參數不變,觀察在MovieLens 1M數據集上MAE和RMSE的實驗結果,如圖3和圖4所示。

圖3 參數λ對MAE的影響

圖4 參數λ對RMSE的影響

可以看出,當λ的值為0.005時,MAE和RMSE的值最大,此時預測精度最低,隨著λ的值增大,預測精度逐步提高,而當λ值到達0.007后,隨著λ的值增大,預測精度開始降低。在λ=0.007時MAE和RMSE的值最小,此時推薦效果最佳。

最后,本文研究了參數d對算法性能的影響,當d的值為30、80、130(λ=0.007,p=1/2)時,在MovieLens 1M數據集上MAE和RMSE的實驗結果,如圖5和圖6所示。

圖5 不同d值下MAE收斂走勢圖

圖6 不同d值下RMSE收斂走勢圖

圖5和圖6顯示了初始秩d取不同值時MAE和RMSE的變化過程?？梢钥闯?d取的值越大,初始循環時MAE和RMSE的值越大,但收斂狀態最快。

4 結 語

傳統基于核范數的矩陣填充模型中,對所有奇異值的懲罰力度一樣,容易損失矩陣的性質,并且在實際應用中核范數對秩函數的逼近效果不佳,導致評分矩陣填充時準確性不高。因此,本文提出了一種基于加權Schatten-p范數的矩陣填充模型WSNM-PALM,該方法利用評分矩陣奇異值的稀疏性,并對奇異值加權,采用加權Schatten-p范數來逼近低秩假設,使用近端交替線性化最小化方法來求解矩陣填充模型中的非凸最小化問題。通過MovieLens 1M數據集上的實驗,驗證了該模型在評分預測的準確性上優于對比模型。