SVDALS算法文档

以使用者为基础（User-based）的协同过滤和以项目为基础（Item-based）的协同过滤统称为以记忆为基础（Memorybased）的协同过滤技术，他们共有的缺点是资料稀疏，难以处理大数据量下的即时结果，因此发展出以模型为基础的协同过滤技术。以模型为基础的协同过滤(Model-basedCollaborativeFiltering)是先用历史资料得到一个模型，再用此模型进行预测。以模型为基础的协同过滤广泛使用的技术包括LatentSemanticIndexing、BayesianNetworks…等，根据对一个样本的分析得到模型。这里说说svd分解。svd是将一个任意实矩阵分解为三个矩阵U,S,V，其中，U,V是两个正交矩阵，称为左右奇异矩阵，S是个对角阵，称为奇异值矩阵。其实svd分解的问题可以化解为特征值分解的问题。评分矩阵A(m*n)=U(m*k)*S(k*k)*V'(k*n)令B(m*m)=A(m*n)*A'(n*m)B矩阵就是一个方阵，可以利用各种简单的方法将B进行特征值分解：Bv=av，v是方阵B的特征向量，a是特征向量v对应的特征值。所以奇异值s=sqrt(a)，左奇异向量u=A*v/s同样的方法可以求得右奇异向量。这样我们就得到了svd分解后的三个矩阵。（你可以自己写个c程序计算，当然也可以用matlab算算得到）分解后的三个矩阵都有着各自的意义，U：每一行表示一个user的特征。V：每一列表示一个item的特征。S：表示对应的user和item的相关性。所以可以考虑用U和V将S吸收进来，形成两个矩阵分别表示user的矩阵和item的矩阵。这种方法有着矩阵分解算法的表，却可以非常简单地完成矩阵的分解，然后填充稀疏的评分矩阵。但它考虑的因素太少了，不过对于简单的推荐系统，这种方法还是非常有意义的，容易实现，而且结果也不会太差。矩阵分解算法的数学理论基础是矩阵的行列变换。在《线性代数》中，我们知道矩阵A进行行变换相当于A左乘一个矩阵，矩阵A进行列变换等价于矩阵A右乘一个矩阵，因此矩阵A可以表示为A=PEQ=PQ（E是标准阵）。矩阵分解目标就是把用户-项目评分矩阵R分解成用户因子矩阵和项目因子矩阵乘的形式，即R=UV，这里R是n×m，n=6，m=7，U是n×k，V是k×m。直观地表示如下：.首先,依据历史数据矩阵初始化用户因子矩阵和项目因子矩阵;其次,迭代更新因子矩阵,将迭代结果置于内存中作为下次迭代的输入;最后,迭代结束时得到矩阵推荐模型.ALS是交替最小二乘（alternatingleastsquares）的简称。在机器学习的上下文中，ALS特指使用交替最小二乘求解的一个协同推荐算法。它通过观察到的所有用户给产品的打分，来推断每个用户的喜好并向用户推荐适合的产品。举个例子，我们考虑下面这个包含用户打分的打分矩阵：这个矩阵的每一行代表一个用户(u1,u2,...,u9)、每一列代表一个产品(v1,v2,…,v9)。用户的打分在1-9之间。我们只显示观察到的打分。那么问题来了：用户u5给产品v4的打分大概会是多少？粗略地观察一下……这不是数独么？是的，而且如果按照数独来做的话（比较耗时、不推荐），用户u5一定会给产品v4打9分。为什么看上去选择很多，答案却是唯一的？因为数独的规则很强，每添加一条规则，就让整个系统的自由度下降一个量级。当我们要满足所有的规则时，整个系统的自由度已然降为一了。现在请努力地把上面的数独题想成一个打分矩阵。如果我们不添加任何条件的话，打分之间是相互独立的，我们没有任何依据来推断u5给v4的打分。所以在这个打分矩阵的基础上，我们需要提出一个限制其自由度的合理假设，使得我们可以通过观察已有打分猜测未知打分。ALS的核心就是下面这个假设：打分矩阵是近似低秩的。换句话说，一个的打分矩阵A可以用两个小矩阵和的乘积来近似：。这样我们就把整个系统的自由度从一下降到了。当然，我们也可以随便提一个假设把自由度直接降到一。我们接下来就聊聊为什么ALS的低秩假设是合理的。世上万千事物，人们的喜好各不相同。但描述一个人的喜好经常是在一个抽象的低维空间上进行的，并不需要把其喜欢的事物一一列出。举个例子，我喜欢看略带黑色幽默的警匪电影，那么大家根据这个描述就知道我大概会喜欢昆汀的《低俗小说》、《落水狗》和韦家辉的《一个字头的诞生》。这些电影都符合我对自己喜好的描述，也就是说他们在这个抽象的低维空间的投影和我的喜好相似。再抽象一些，把人们的喜好和电影的特征都投到这个低维空间，一个人的喜好映射到了一个低维向量，一个电影的特征变成了纬度相同的向量，那么这个人和这个电影的相似度就可以表述成这两个向量之间的内积。我们把打分理解成相似度，那么打分矩阵A就可以由用户喜好矩阵和产品特征矩阵的乘积来近似了。我们大致解释了ALS低秩假设的合理性，接下来的问题是怎么选这个抽象的低维空间。这个低维空间要能够有效的区分事物，如果我说我喜欢看16:9宽屏的彩色立体声电影，那一定是我真心不想透露我的喜好。但ALS是很难从实质上理解“黑色幽默”和“彩色”的区别是什么的，它需要一个更明确的可以量化的目标，这就是重构误差。既然我们的假设是打分矩阵A可以通过来近似，那么一个最直接的可以量化的目标就是通过U,V重构A所产生的误差。在ALS里，我们使用Frobenius范数，，来量化重构误差，就是每个元素的重构误差的平方和。这里存在一个问题，我们只观察到部分打分，A中的大量未知元正是我们想推断的，所以这个重构误差是包含未知数的。解决方案很简单很暴力：就只看对已知打分的重构误差吧。所以ALS的优化目标是：。这里R指观察到的（用户，产品）集。我们把一个协同推荐的问题通过低秩假设成功转变成了一个优化问题。下面要讨论的内容很显然：这个优化问题怎么解？其实答案已经在ALS的名字里给出——交替最小二乘。ALS的目标函数不是凸的，而且变量互相耦合在一起，所以它并不算好解。但如果我们把用户特征矩阵U和产品特征矩阵V固定其一，这个问题立刻变成了一个凸的而且可拆分的问题。比如我们固定U，那么目标函数就可以写成。其中关于每个产品特征的部分是独立的，也就是说固定U求我们只需要最小化就好了，这个问题就是经典的最小二乘问题。所谓“交替”，就是指我们先随机生成然后固定它求解，再固定求解，这样交替进行下去。因为每步迭代都会降低重构误差，并且误差是有下界的，所以ALS一定会收敛。但由于问题是非凸的，ALS并不保证会收敛到全局最优解。但在实际应用中，ALS对初始点不是很敏感，是不是全局最优解造成的影响并不大。ALS在MLlib中的实现ALS的算法介绍完了，但我们距离一个好的分布式实现还有一段距离。因为ALS每步迭代中优化问题的目标函数可以拆分成互相独立的最小二乘子问题，所以从计算的角度来看ALS是适合分布式求解的。但通过观察一个子问题，我们会发现求解vj是需要知道上一步得到的每个已知打分对应的的值。如果分布式求解，我们可能会需要从其它节点获取这些数据，从而产生通信费用。和很多机器学习算法的分布实现类似，ALS的分布式实现主要关心的是计算复杂度和通信复杂度。计算复杂度比较容易估算，所以我们先讲。求解一个的最小二乘问题的复杂度是。当固定U求V时，我们一共有n个最小二乘子问题，所以总的复杂度是，其中nnz指观察到的打分数量。再加上固定V求U的复杂度，一步完整的迭代需要的计算量就是。MLlib中的ALS实现通过法方程(normalequation)求解最小二乘子问题，需要的空间复杂度是。2、均方根误差，它是观测值与真值偏差的平方和观测次数n比值的平方根，在实际测量中，观测次数n总是有限的，真值只能用最可信赖（最佳）值来代替.方根误差对一组测量中的特大或特小误差反映非常敏感，所以，均方根误差能够很好地反映出测量的精密度。均方根误差，当对某一量进行甚多次的测量时，取这一测量列真误差的均方根差(真误差平方的算术平均值再开方)，称为标准偏差，以σ表示。σ反映了测量数据偏离真实值的程度，σ越小，表示测量精度越高，因此可用σ作为评定这一测量过程精度的标准。