基于加权Schatten-p范数的矩阵填充及其应用

潘 伟 胡春安

(江西理工大学信息工程学院 江西 赣州 341000)

0 引 言

随着互联网的快速发展,网上用户规模与内容服务呈几何数量级增长,社会信息超过了个人能接受的范围,海量的信息导致了信息过载问题[1],推荐系统成为解决这一问题的重要工具,并在许多领域得到了应用,如电子商务[2]、新闻推荐[3]、音乐推荐[4]以及电影视频推荐[5-6]等。

推荐系统中使用最广泛的方法是基于协同过滤的推荐算法。协同过滤方法包括基于记忆的协同过滤和基于模型的协同过滤。基于记忆的协同过滤利用物品被评分的记录或用户过去的行为计算物品之间的相似度或用户之间的相似度构成最近邻集合,从而对目标用户的兴趣进行预测,产生推荐结果。基于模型的协同过滤利用已知评分矩阵训练预测模型,训练好的模型为用户生成推荐。虽然协同过滤方法被广泛研究和应用,但依然存在一些问题,例如评分矩阵的稀疏性导致用户之间或物品之间的相似度计算不稳定,矩阵的高维度导致相似度计算量非常大。为了解决评分矩阵的稀疏性问题,文献[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数据集上的实验,验证了该模型在评分预测的准确性上优于对比模型。