Matrix Factorization Techniques for Recommender Systems
现代消费者被淹没了选择。电子零售商和内容提供商提供大量产品，具有满足各种特殊需求和口味的前所未有的机会。将消费者与最合适的产品相匹配是提高用户满意度和忠诚度的关键。
因此，更多零售商已经对推荐系统感兴趣，推荐系统分析用户对产品感兴趣的模式以提供适合用户口味的个性化推荐。由于良好的个性化推荐可以为用户体验增加另一个维度，因此Amazon.com和Netflix等电子商务领导者已将推荐系统作为其网站的重要组成部分。
这种系统对于诸如电影，音乐和电视节目之类的娱乐产品特别有用。许多客户将观看同一部电影，每个客户都可能会看到许多不同的电影。客户已经证明愿意表明他们对特定电影的满意度，因此有大量数据可供哪些电影吸引哪些客户。公司可以分析此数据以向特定客户推荐电影
Recommender system strategies
从广义上讲，推荐系统基于两种策略之一。内容过滤方法为每个用户或产品创建一个配置文件，以表征其性质。例如，电影简档可以包括关于其类型，参与演员，其票房受欢迎程度等的属性。用户个人资料可能包括适当问卷上提供的人口统计信息或答案。配置文件允许程序将用户与匹配的产品相关联。当然，基于内容的策略需要收集可能不可用或不易收集的外部信息。
一个已知的成功的内容过滤实现是音乐基因组计划，它被用于互联网广播服务Pandora.com。一位训练有素的音乐分析师根据数百种不同的音乐特征为音乐基因组计划中的每首歌曲打分。这些属性，或者说基因，不仅能捕捉一首歌的音乐特征，还能捕捉到许多与理解听众的音乐偏好相关的重要品质。
内容过滤的另一种选择仅依赖于过去的用户行为——例如，以前的事务或产品评级——而不需要创建显式的配置文件。这种方法被称为协同过滤，这是第一个推荐系统Tapestry的开发人员发明的术语。协同过滤分析用户之间的关系和产品之间的相互依赖关系，以识别新的用户项关联。
协同过滤的一个主要优点是它是无域(domain free)的，但是它可以处理数据方面的问题，这些问题通常很难用内容过滤来描述。尽管协同过滤通常比基于内容的技术更准确，但由于它无法处理系统的新产品和用户，因此存在所谓的冷启动问题。在这方面，内容过滤是优越的。
协同过滤的两个主要领域是邻域方法和潜在因素模型。邻域方法集中于计算项目之间或用户之间的关系。面向项目的方法根据同一用户对“相邻”项的评级来评估用户对某个项的偏好。一个产品的邻居是其他产品，当同一用户对其进行评级时，这些产品往往会得到类似的评级。以电影《拯救大兵瑞恩》为例。它的邻居可能包括战争片、斯皮尔伯格的电影、汤姆汉克斯的电影等等。为了预测某一特定用户对《拯救大兵瑞恩》的评分，我们将查找该用户实际评分的电影最近的邻居。如图1所示，面向用户的方法识别志同道合的用户，这些用户可以互补彼此的评分。
潜在因素模型是另一种方法，它试图通过描述项目和用户的特征来解释评级，例如，从评级模式中推断出20到100个因素。从某种意义上说，这些因素构成了上述人类创造的歌曲基因的计算替代品。对于电影来说，所发现的因素可能衡量明显的维度，如喜剧与戏剧，动作的数量，或对儿童的定位;定义不太明确的维度，如性格发展的深度或怪癖;或者完全不可解释的维度。对于用户来说，每个因素衡量的是用户有多喜欢在相应电影因素上得分高的电影。
图2展示了一个二维简化示例的这种思想。考虑两个假设的维度，分别是面向女性和面向男性，以及严肃(serious)和逃避现实(escapist)。该图显示了几个著名的电影和一些虚构的用户可能属于这两个维度。在这个模型中，用户对一部电影的预测评级，相对于这部电影的平均评级，等于这部电影和用户在图上的位置的点积。例如，我们希望Gus喜欢《Dumb and Dumber》，讨厌紫色，对《Braveheart》的评价一般。请注意，有些电影——例如《ocean’s 11》——和用户——例如Dave——在这两个维度上的特征是相当中立的。
Matrix factorization methods
一些最成功的潜在因素模型的实现是基于矩阵分解。矩阵分解的基本形式是通过从项目评级模式中推断出的因素向量来表征项目和用户。项目和用户因素之间的高度对应导致推荐。这些方法结合了良好的可扩展性和预测精度，近年来越来越受欢迎。此外，它们为建模各种真实场景提供了很大的灵活性。
推荐系统依赖于不同类型的输入数据，这些数据通常放在一个矩阵中，一个维度表示用户，另一个维度表示感兴趣的项目。最方便的数据是高质量的显性反馈，包括用户对产品兴趣的显性输入。例如，Netflix收集电影的明星评分，TiVo用户通过按拇指向上和拇指向下的按钮来显示他们对电视节目的偏好。我们将明确的用户反馈称为评分。通常，显式反馈包含一个稀疏矩阵，因为任何单个用户可能只对可能的项进行了很小的百分比的评级。
矩阵分解的一个优点是它允许合并额外的信息。当没有显式反馈时，推荐系统可以使用隐式反馈来推断用户的偏好，隐式反馈通过观察用户的购买历史、浏览历史、搜索模式甚至鼠标移动等行为来间接反映用户的意见。隐式反馈通常表示事件的存在或不存在，因此它通常用一个填充密集的矩阵来表示。
A BASIC MATRIX FACTORIZATION MODEL
矩阵分解模型将用户和项目映射到维度f的联合潜在因子空间，从而将用户-项目交互建模为该空间的内积。于是,每个项目i与一个向量$q_i∈R^f$关联,每个用户u与一个向量$p_u∈R^f$关联.对于给定项目i,$q_i$的元素表示了该项目拥有这些因素的程度,正的或负的.对于给定用户u，$p_u$的元素表示u用户对相应因素高的项目的兴趣程度,同样是正的或负的.点积的结果$q_i^Tp_u$,捕捉了用户u和项目i之间的交互(interactuon)———该用户对项目特征的总体兴趣.这近似于用户u对第项目i打分记为$r_{ui}$,这引出了估计:
这主要的挑战是计算每一项目和用户的因素向量$q_i,p_u∈R^f$的映射.在推荐系统完成映射之后,就可以很容易的估计得到一个用户对任意项目的评分用上式.
这种模型与奇异值分解(SVD)密切相关，奇异值分解是一种用于识别信息检索中潜在语义因素的成熟技术。在协同过滤领域中应用SVD需要分解用户项评级矩阵。这通常会带来困难，因为用户项评级矩阵中的稀疏性会导致很大一部分缺失值。当矩阵知识不完备时，传统的支持向量机没有定义。此外，不小心仅对相对较少的已知条目进行寻址很容易导致过拟合。
早期的系统依靠归一化来填充缺失的评级，使得评级矩阵变得稠密。然而，由于注入极大地增加了数据量，因此它可能非常昂贵。此外，不准确的估算可能会对数据造成相当大的失真。因此，最近的研究建议只对观测到的评级进行直接建模，同时通过正则化模型进行避免过拟合。为了学习因子向量$(p_u和q_i)$，系统最小化了已知评级集上的正则化平方误差:
这里k是已知$r_{ui}的$(u,i)对的集合(训练集)。
系统通过拟合之前观察到的评级来学习模型。然而，我们的目标是以一种预测未来未知评级的方式来概括那些之前的评级。因此，系统应通过正则化学习参数来避免对观测数据的过拟合，使学习参数的大小受到惩罚。常数λ控制正则化的程度,通常是由交叉验证。Ruslan Salakhutdinov和Andriy Mnih的“概率矩阵因子分解”为正则化提供了概率基础。
LEARNING ALGORITHMS
最小化等式2的两种方法是随机梯度下降法和交替最小二乘法。
Stochastic gradient descent
Simon Funk推广了公式2的随机梯度下降优化(http://sifter.org/~Simon/journal/20061211.html)，算法循环遍历训练集中的所有评级。对于每个给定的训练案例，系统预测$r_{ui}$并计算相关的预测误差
然后在梯度的相反方向上，对参数进行与$\gamma$成比例的幅度修正，得到:
- $q_i\leftarrow q_i+\gamma(e_{ui}·p_u-\lambda·q_i)$
- $p_u \leftarrow p_u+\gamma·(e_{ui}·q_i-\lambda·p_u)$
这种流行的方法结合了易于实现和相对较快的运行时间。然而，在某些情况下，使用ALS优化是有益的。
Alternating least squares
因为$q_i$和$p_u$都是未知数，所以方程2不是凸的。然而，如果我们修正了其中一个未知数，优化问题就变成了二次方程，可以得到最优解。因此，ALS技术在固定$q_i$和固定$p_u$之间轮换。当所有的$p_u$都固定时，系统通过解最小二乘问题重新计算$q_i$，反之亦然。这保证了每一步都减小方程2直到收敛
虽然一般来说，随机梯度下降比ALS更容易和更快，但ALS在至少两种情况下是有利的。首先是当系统可以使用并行化。在ALS中，系统独立于其他项目因子计算每个$q_i$，独立于其他用户因子计算每个$p_u$。这可能会导致算法的大量并行化。第二种情况是以隐式数据为中心的系统。因为训练集不能被认为是稀疏的，所以像梯度下降那样遍历每个训练案例是不实际的。ALS可以有效地处理这种情况.
ADDING BIASES
协同过滤的矩阵分解方法的一个好处是它在处理各种数据方面和其他特定于应用程序的需求时具有灵活性。这要求在保持相同的学习框架的同时，对等式1进行调整。方程1试图捕捉产生不同评级值的用户和项目之间的交互。然而，许多观察到的评分值的变化是由于与用户或项目相关的影响，即偏差或截取，独立于任何交互。例如，典型的协同过滤数据显示出较大的系统性趋势，有些用户给出的评分比其他用户高，有些项目得到的评分比其他项目高。毕竟，有些产品被普遍认为比其他产品更好(或更差)。
因此，通过$q_i^Tp_u$形式的交互来解释完整的评级值是不明智的。相反，系统试图识别这些值中个别用户或项目偏差可以解释的部分，只对数据的真实交互部分进行因子建模。一阶近似的偏差涉及评级r_{ui}如下:
评价r_{ui}所涉及的偏差用b_{ui}表示，并考虑了用户和项目的影响。总体平均评级用μ;参数b_u和b_i分别表示观察到的用户u和项目i与平均值的偏差。例如，假设您想要用户Joe对电影泰坦尼克号的评级的一阶估计。现在,说平均评级所有电影,μ是3.7星。此外，《泰坦尼克号》比一般电影要好，所以它的星级往往比一般电影高0.5星。另一方面，Joe是一个重要的用户，他的评分往往比平均水平低0.3星。因此，乔对泰坦尼克号的评级估计是3.9颗星(3.7 + 0.5 - 0.3)。bias将方程1推广如下:
在这里，观察到的评级被分解为四个组成部分:全局平均值$\mu$、项目偏差$b_i$、用户偏差$b_u$和用户项交互q_i^Tp_u。这允许每个组件只解释与它相关的信号的一部分。系统通过最小化平方误差函数来学习
由于bias往往会捕获观测到的大部分信号，因此精确建模至关重要。因此，其他作品提供了更复杂的bias模型。
ADDITIONAL INPUT SOURCES
通常情况下，系统必须处理冷启动问题，其中许多用户提供的评级非常少，因此很难对他们的口味得出一般性结论。缓解这个问题的一种方法是加入关于用户的额外信息来源。推荐系统可以使用隐式反馈来洞察用户的偏好。事实上，他们可以收集行为信息，而不管用户是否愿意提供明确的评级。零售商可以利用顾客的购物记录或浏览历史来了解他们的购物倾向，以及这些顾客可能提供的评级。
为了简单起见，考虑一个布尔隐式反馈的情况。N(u)表示用户u表示隐式偏好的项集。这样，系统通过用户隐式首选的项来配置用户。这里,一组新的项因素是必要的,项目i与$x_i∈R^f$关联。因此,一个在N(u)中对项目展示偏好的用户可以用下述向量表示:
例如，对求和进行规范化通常是有益的
另一个信息源是已知的用户属性，例如人口统计信息。同样，为了简单起见，考虑布尔属性，其中用户u对应于一组属性A(u)，这些属性可以描述性别、年龄组、邮政编码、收入水平等。一个不同因素向量$y_a ∈ R^f$ 对应于每个属性来描述一个用户通过用户相关特征集合(user-associated attributes):
矩阵分解模型应集成所有信号源，增强用户表示:
虽然前面的示例处理的是增强用户代表性(缺少数据是更常见的情况)，但是项目在必要时也可以得到类似的处理。
TEMPORAL DYNAMICS
到目前为止，所提出的模型都是静态的。在现实中，随着新的选择的出现，产品的认知和受欢迎程度也在不断变化。同样的，顾客的喜好也在不断变化，这导致他们重新定义自己的品味。因此，系统应该考虑反映用户-项目交互的动态、时间漂移性质的时间效应。
矩阵分解方法可以很好地对时间效应进行建模，极大地提高了建模的精度。将评级分解成不同的术语允许系统分别处理不同的时间方面。具体来说，以下术语随时间而变化:项目偏差，$b_i(t)$;用户偏差,$b_u(t)$;用户偏好，$p_u(t)$
第一个时间效应是指物品的受欢迎程度可能会随着时间的推移而改变。例如，电影可以随着外部事件(如演员在新电影中的出现)的触发而流行或不流行。因此，这些模型将项目偏差b_i视为时间的函数。第二个时间效应允许用户随着时间改变他们的基线评级。例如，一个用户倾向于给一部平均的电影打分“4星”，现在可能会给这样一部电影打分“3星”。“这可能反映了几个因素，包括用户评分等级的自然变化、用户相对于最近的其他评分进行评分的事实，以及评分者在家庭中的身份会随着时间的推移而改变。”因此，在这些模型中，参数$b_u$是时间的函数。
时间的动态不止于此;它们还影响用户首选项，从而影响用户和项之间的交互。用户会随着时间改变他们的首选项。例如，心理惊悚片的粉丝一年后可能会成为犯罪片的粉丝。同样，人类也会改变对某些演员和导演的看法。该模型通过将用户因素(向量$p_u$)作为时间的函数来解释这种影响。另一方面，它指定静态项的特征$q_i$，因为与人类不同，项目在本质上是静态的。
对时变参数的精确参数化导致将式4替换为t时刻某一额定值的动态预测规则:
INPUTS WITH VARYING CONFIDENCE LEVELS
在几个设置中，并不是所有观察到的评级都有相同的权重或confidence。例如，大量的广告可能会影响某些项目的投票，而这些项目并不恰当地反映长期的特征。类似地，系统可能会面对试图倾斜某些项目的评级的敌对用户。
另一个例子是围绕内隐反馈构建的系统。在这种解释用户行为的系统中，很难量化用户的确切偏好水平。因此，系统使用一种更粗糙的二进制表示，表示“可能喜欢该产品”或“可能对该产品不感兴趣”。在这种情况下，将confidence得分与估计的偏好联系起来是很有价值的。confidence可以来自于可用的数值，这些数值描述了动作的频率，例如，用户观看某个节目的时间或购买某个商品的频率。这些数值表明了每个观察的可信度。与用户首选项无关的各种因素可能导致一次性事件;然而，重复发生的事件更可能反映用户的意见。
矩阵因子分解模型可以很容易地接受不同的置信水平，这使得它对不太有意义的观测给予较少的权重。若将观测$r_{ui}$的置信度表示为$c_{ui}$，则模型对代价函数(公式5)进行改进，得到置信度为: