2.2 矩阵分解
矩阵分解类算法因其在Netflix大奖赛打分预测任务上的优秀表现[144]，逐渐受到了学术界的广泛关注和深入研究。由于矩阵分解算法使用隐变量（latent factor）来描述用户偏好和物品属性，因此也常常被归为隐变量模型[145]。矩阵分解算法在为用户和物品计算偏好与属性向量时，本质上用到了其他用户和其他物品的历史记录，因此相关算法也属于基于协同过滤的推荐范畴。
严格数学意义上的矩阵分解是指将原始矩阵分为两个（或多个）子矩阵的乘积，使子矩阵的乘积严格等于原始矩阵。上下三角矩阵分解（LU decomposition）将原始矩阵分解为一个上三角矩阵和一个下三角矩阵的乘积[146]；正交矩阵分解（QR decomposition）将原始矩阵分解为一个半正交矩阵和一个上三角矩阵的乘积[147]；SVD则将原始矩阵分解为两个酉矩阵与一个奇异值对角阵的乘积[148]。它们构成了许多重要数学问题的计算基础，如离散优化、线性方程组求解、偏微分方程求解、信号处理、谱分析等。
而在个性化推荐问题中，我们所处理的用户-物品打分矩阵往往极其稀疏，矩阵中只有少数的观测值（用户对物品的打分），而大部分值是空缺的（相应的用户没有对物品打分）。为了对用户潜在兴趣进行预测，我们并不关心原始矩阵的精确恢复，而更加关心利用矩阵分解实现对原始矩阵中空缺值的预测，因此近似矩阵分解应运而生。在个性化推荐背景下，矩阵分解一般指基于近似矩阵分解的矩阵补全（matrix completion）算法。
常见的矩阵分解算法是基于“低秩近似”假设的[13]，[149]，该类算法认为虽然一个矩阵的维度可以大至上千万乃至上亿级别，但是描述矩阵性质的内在因素其实只是少数有限的几个——虽然我们并不知道它们是什么（隐变量）。例如在一个包含上亿用户和上亿物品的购物网站用户评分矩阵中，决定用户打分偏好的可能只有价格、颜色、款式、流行度等几十或者数百个因素。因此，庞大的原始矩阵可以分解为两个低秩（几十或上百维）子矩阵的乘积，而两个矩阵分别描述了用户和物品在这些隐变量上的偏好。
以SVD为理论基础的PCA首先得到了应用。Sarwar等利用主成分分析方法研究了购物网站中用户打分行为特征[31]；Goldberg等则进一步直接将其用于协同过滤的推荐问题当中[53]；与此同时，与PCA同源的截断式奇异值分解（truncated SVD）算法被正式应用于协同过滤预测当中[31]，截断式矩阵分解通过舍弃较小的特征值来对原始矩阵进行近似，它具有较为直观的理论基础，即通过滤除原始矩阵中的噪声来达到降噪预测的目的；由于严格SVD算法具有较高的计算复杂度，为了适应线上推荐的需求，Sarwar提出了增量式SVD算法[150]、Brand提出了线上SVD算法[151]。
SVD算法本身不对分解矩阵的值做额外要求，但是在很多实际应用场景中，我们经常认为用户和物品在隐变量上的打分是正的，因此原本应用于图像处理的非负矩阵分解[60]，[61]开始在推荐系统中得到关注。Zhang等利用非负矩阵分解恢复评分矩阵中的缺失值[152]；Langville等讨论了分解矩阵的初始化对非负矩阵分解效果的影响[153]；Chen等提出了正交非负矩阵分解方法，用以改进预测效果[154]；Arora等[155]对非负矩阵分解的性质进行了算法理论分析；Liu等提出了分布式非负矩阵分解算法，用以提高计算效率[156]。
Salakhutdinov和Mnih研究了矩阵分解的概率意义，发现常见的奇异值分解和非负矩阵分解都可以等价地概率化，并表达为最大似然估计的形式，由此提出了贝叶斯概率矩阵分解框架[67]，[68]。由于本质上的低秩近似假设，以上矩阵分解算法都面临同一个难题，即在实际应用中难以准确确定应该使用多少维的分解矩阵进行近似，在实际应用中，往往需要手动调试以确定效果最优的维度选择。为了避免该问题，Srebro等避开了低秩近似假设，采用低范数假设提出了最大间隔矩阵分解（MMMF）算法[62]，通过最小化预测矩阵的核范数实现矩阵分解，在理论上允许无穷维的分解子矩阵；Rennie和Srebro在此技术上分析了核范数的数学性质，提出了快速最大间隔矩阵分解（fast MMMF）算法[63]；Xu等研究了最大间隔矩阵分解算法的非参数化[157]；Weimer等[64]，[66]和De Coste[65]研究了最大间隔矩阵分解在协同过滤和推荐系统中的应用。
Koren[158]和Bell等[159]将矩阵分解作为主要算法之一应用于Netflix大奖赛，并取得了重要成功，通过去掉SVD中的奇异值矩阵给出了SVD矩阵分解的双子矩阵形式，使其更适合实际应用中对效率和迭代更新的要求[58]；Koren进一步研究了矩阵分解与基于近邻方法的结合，提出了著名的SVD++算法[57]，[160]，并研究了基于矩阵分解的系统过滤对用户动态临时兴趣的建模[161]，进而将其应用于雅虎音乐推荐系统[162]，[163]；Wu系统性地研究了多矩阵分解算法的集成[164]；Takács等也研究了多种矩阵分解算法在大规模协同过滤系统中的效果[165]。
矩阵分解适用于数值化打分的显示反馈矩阵，而对于用户隐式行为反馈矩阵（如0-1矩阵）效果并不显著[166]。为了对隐式反馈进行更好地处理，Rendle等将贝叶斯排序方法与矩阵分解相结合，提出了基于贝叶斯个性化排序的矩阵分解（Bayesian personalized ranking matrix factorization，BPRMF）算法[167]，取得了较好的效果。
近年来，随着互联网用户生成内容的不断丰富，为多种类异质信息的处理带来了新的要求，矩阵分解的高维形式——张量分解（tensor factorization）算法[168]在推荐系统中的应用也逐渐受到了关注。Karatzoglou等用张量描述不同的上下文信息，从而将张量分解用于上下文相关的推荐系统中，提出了一种上下文相关推荐的统一形式[169]；Rendle等将张量的维度进行两两组合式的分解，并用于标签预测和推荐任务中[170]，[171]；Xiong等将用户临时和动态兴趣引入张量分解中，提出了动态张量分解模型[172]；Hidasi和Tikk研究了张量分解对用户隐式反馈的处理[173]；Zheng等将张量分解应用于Flickr图片分享网站中的小组推荐实际系统中，取得了理想的效果[174]。
同样为了处理大量的异质用户行为信息，Rendle等进一步将两两维度组合的张量分解推广为任意维度组合的张量分解，并提出了分解机（factorization machines，FM）模型[175]，[176]，分解机模型理论上具有更强的拟合能力，并且可以在一个统一的算法框架下进行模型求解，为实际系统中异质信息的处理提供了便利。目前，张量分解已经广泛用于谷歌的商业系统中，并提供LibFM[177]和MyMedialite[178]等多种开源实现。
在实际系统中，矩阵分解问题常用的求解算法有交替最小二乘法（alternate least square，ALS）[58]、坐标下降法（coordinate descent，CD）[179]，[180]和随机梯度下降算法（stochastic gradient descent，SGD）[181]等。由于较好的收敛效果和计算效率上的优势，随机梯度下降算法在实际中得到了较为广泛的应用，为了适应产业级大规模数据的处理，Gemulla等提出了分布式随机梯度下降算法[182]，Zhuang等提出了并行化随机梯度下降算法[183]。