您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > ALS-WR算法原稿译文(一)
算法原文译文经过3个晚上的翻译,终于把ALS-WR算法的介绍论文翻译完成。此次翻译目的是加强对ALS-WR算法的理解和练习自己对专业性英文的能力,由于本人英文水平有限并且该算法使用到了多个高数甚至超越高数和线性代数的一些知识,所以如哪里翻译不对或理解有误,望英语强人,数学高人,算法牛人给个纠正,先于此谢过。原文见:=true#page-1,最好是看英文版的,因为该算法的主要精髓是在那几个数学公式上。译文如下:大规模并行协同过滤算法(NetflixPrize)作者:YunhongZhou(),DennisWilkinson,RobertSchreiberandRongPan()很多的推荐系统使用协同过滤技术向用户推荐相关事物,该技术是基于用户之前已经查阅,购买或评论过的事物所做出的推荐。该技术需要解决的两个主要问题是可扩展性和用户信息的稀疏程度带来的问题。在此论文中,我们将会描述ALS-WR,它是我们为NetflixPrize设计的并行算法。我们在linux集群中使用并行Matlab作为实验平台,根据经验,ALS-WR的性能会伴随着特征值数量和ALS迭代的增加而增加。ALS-WR使用1000个从RMSE中获得的特征值作为Netflix数据集进行实验最后获得的得分是0.8985,这个得分是基于单纯(串行)方法获得的最好的得分。结合其他并行版本的方法,我们获得了比Netflix自身的CineMatch推荐系统高出5.91%的性能。ALS-WR是很简单的并且对于大数据集也有很好的扩展性的一种解决方法。1.介绍推荐系统尝试基于可用的信息向潜在的客户推荐如电影,音乐,网页,产品等事物。可想而知,一个成功的推荐系统能够明显的提升电子商务公司的收入或促进社交网站上用户的交互。在众多的推荐系统中,基于内容的方法当然是要去分析对应的内容(如文本,元数据,特征)来决定相似的事物,然而协同过滤对大量用户的行为/爱好向指定用户推荐相似事物。协同过滤在如Amazon,Netflix,GoogleNews等很多公司中都有使用。NetflixPrize这个项目(据说有大量的奖金给参赛者)是由Netflix主持的大型的数据挖掘竞争项目,主要目的是为了寻找最好的推荐系统算法来预测用户对电影的评分,当然这是在一个多于1亿得分(根据480000个用户和将近18000部电影得出的得分)的训练集的情况下完成的。每个训练数据有用户,电影,日期,评分四个元素组成,评分是一个介于1到5的值。测试数据集是由2800000个数据节点和评分组成,目标是在预测评分时将RMSE(均方根误差,)的值最小化。Netflix自身的推荐系统在测试数据集上的得分是0.9514,NetflixPrize这个项目的目标是获得比该得分高出10%的解决方案。该问题展示了一系列的挑战,(所以到目前为止,奖金还未被参赛者赢取)第一个挑战是数据集比之前的基准数据集还要大100倍,这会消耗大量的模型训练时间和系统内存要求。第二个挑战是只有1%的用户-电影矩阵是在观察中的,大部分潜在的评分都是不可见的。第三个挑战是由于用户行为训练数据集和测试数据集都会存在脏数据,我们不能期望用户是完全可预测的。第四个挑战是分配给每个训练和测试数据集中用户的评分是不同的,由于训练数据集是由1995-2005年之间的数据组成而测试数据集是由2006年的评分组成。特别的,评分越少的用户在测试集中是更为有效的。直观来讲,预测一个在训练集中表示较为稀疏(该用户对事物的评分较少)的用户的评分是一件很困难的事情。在此论文中,我们将会详细讨论该问题,接着会描述一个并行算法:ALSWR。2.问题结构(配方)使R={rij}nu×nm(数学公式请参看原文)表示一个用户-电影矩阵,其中rij表示i用户对j电影的评分,这个分数可以是一个真实的数字或是无值的。nu指定了用户数量,nm指定了电影数量。在许多的推荐系统中,其任务就是根据已知的评分值去估算那些未知的评分。我们从矩阵R的一个低秩近似值开始讲起。通过赋予用户和电影一个小尺寸的特征空间我们可以接近用户和电影的数据模型。每个用户电影都存在一个特征,并且每个用户对电影作出的评分(已知和未知的)对应着用户和电影特征向量值的一个模型。更为特别的是,U=[ui]代表用户的特征矩阵,ui属于Rnf,其中i=1…nu,M=[mj]表示电影特征矩阵,mj属于Rnf其中j=1…nm,这里的nf是特征空间的尺寸,也就是模型中隐藏变量的数量。如果用户评分是完全可以预测的并且nf也足够的大,我们可能会期望rij=ui,mj,8i,j。然后在实验当中,我们最小化U和M的一个损失函数()来获得矩阵U和M。在本文中,我们将会学习mean-square()这个损失函数,该损失是由于一个单一评分是被squarederror()定义的:L2(r,u,m)=(r−u,m)2.。接下来我们有以下的经验,将所有的损失作为已知评分的损失的和:Lemp(R,U,M)=1/nX(i,j)2IL2(rij,ui,mj),其中i代表已知评分集合的索引,n代表I的大小。最后可以将低秩近似值问题定义为:(U,M)=argmin(U,M)Lemp(R,U,M)。其中U和M是真实的矩阵,并有nf列。在这个问题中,等式3中有(nu+nm)*nf个参数将被决定,另一方面,已知的评分集合I的元素个数远远少于nu*nm,因为对于很少的用户来对18000个电影进行评分是不可能的。为了解决此问题,对一个很稀疏的数据集使用等式3经常会过于庞大,为了避免这个问题,一个简单的方法就是使用一下方式:Lreg_(R,U,M)=Lemp(R,U,M)+_(kUUk2+kMMk2)。对于一系列的已选的Tikhonov()矩阵。3.解决方法在此节中,我们描述了一个迭代算法(ALSWR)来解决低秩近似值问题,接着会实现基于并行Matlab平台的并行实现。3.1ALSWR由于评分矩阵同时包含信号和脏数据,重要的是移除脏数据和使用恢复的信号来预测失去的评分。奇异值分解(SVD,)是一种估算原生用户-电影评分矩阵R的方法,它使用两个k排名的矩阵˜R=UT×M的结果作为估算标准。由SVD给出的解决方案最小化Frobeniousnorm(),该方案与在R的所有元素上最小化RMSE是等效的。然而,由于在矩阵R中有很多的空值,标准的SVD算法不能找到U和M矩阵。在本文中,我们使用ALS来解决低秩近似矩阵分解问题的步骤如下:1.使用指定电影的平均得分作为矩阵M的第一行,余下的行值使用小的随机值来填充。2.使用squarederrors和的最小值来填充U矩阵。3.相似的使用squarederrors和的最小值来填充M矩阵。4.重复2,3步直到满足了停止标准(stoppingcriterion())。这里使用的停止标准是基于在探测数据集上观测的RMSE,修改U和M的第一次循环之后,如果探测数据集上的观测的RMSE之间的差异小于1个基点,那么该循环就会停止并且会使用获得的U,M来作为测试数据集上的最后预测根据。该探测数据集是由Netflix提供的,它与那些隐藏的测试数据集有相同的结构。之前的第二节中,存在许多的自由参数,在没有正交化的情况下,ALS可能会导致过度拟合(),一种常见的解决方法是使用吉洪诺夫正交化(Tikhonovregularization()),该方法会使大量的参数尽量影响最小化。我们尝试了很多的正交化矩阵,发现下面的WR正交矩阵的效率最高,因为根据经验当我们增加特征值的数量或循环次数的时候它从不会导致测试数据过度拟合:f(U,M)=X(i,j)2I(rij−uTimj)2+_0@Xinuikuik2+Xjnmjkmjk21A(公式看原文!!!),其中nui和nmj分别表示用户i和电影j的评分数量,如果使Ii代表用户i评论过的电影j的集合,那么nui就是Ii的基数,相似的如果Ij表示对电影j评论过的用户集合,那么nmj就是Ij的基数。这个和吉洪诺夫正交化中的U=diag(nui)和M=diag(nmj)是一样的。现在我们将演示如何在M给定的情况下填充(solve)矩阵U。U的列数(ui)是在已知用户i的评分和用户i评论过的电影特征向量关系下解决正规化的线性最小二乘问题时给定的。(公式省略见原文)。相似的,当M被修改时,我们会通过正规化线性最小二乘解来计算mj的值,方法是使用用户对电影j评分特征向量和对电影j的评分,如下:mj=A−1jVj,8j。3.2使用加权正规化来并行计算ALS我们通过并行修改U和M来并行计算ALS,我们使用的是最新版本的Matlab,该版本的Matlab允许在分开的Matlab上进行并行计算并互相通信(如分布式数据库),这些分开的Matlab拥有自己的空间和硬件环境。每个这样的Matlab被称为一个单独的实验室,所以我们就会通过识别码(labindex)和一个静态变量(numlabs)得知当前共有多少个labs。这些矩阵可以是私有(拥有自己的一个拷贝并且值都是不同的)的,也可以是复制过来的(私有但是所有的labs的值都是相同的)或是分布式(只有一个矩阵但在所有的labs当中是分区存储的)的。分布式的矩阵是存储和使用大容量数据集的简单方式,因为数据集过大的话,在一个存储器上存储是非常耗内存的。在我们的问题上,我们会使用评分矩阵R的拷贝作为分布式来存储,一份只存储行(例如只有用户)另一份只存储列(只有电影)。我们将会计算分布式的值并修改U和M,在计算U时我们会使用一份M的拷贝,反之亦然。为了修改M,我们需要U的一份拷贝,我们会使用电影的评分数据来修改。这是由相同数量的电影分配的。存储电影j评分的lab自然地会成为M的列值,这些列值也被称为影片j的特征向量。每个lab并行地在对应的影片组中为所有的电影计算mj值,这些计算出来的值接着会被收集起来以保证在一个复制的数组当中每个节点都有M的所有数据。相同的要修改U,所有的用户会被分成相同数量的用户组,接下来每个lab用以行分开的评分值来在对应用户组中修改用户向量。下面的Matlab代码片段实现了给定U情况下修改M的实现:functionM=updateM(lAcols,U)lamI=lambda*eye(Nf);lM=zeros(Nf,Nlm);lM=
本文标题:ALS-WR算法原稿译文(一)
链接地址:https://www.777doc.com/doc-2896914 .html