【论文阅读】MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS

本文主要是介绍【论文阅读】MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

论文

背景

1.RECOMMENDER SYSTEM STRATEGIES（推荐系统策略）

1.1内容过滤

1.2协同过滤（Collaborative filtering）

2.MATRIX FACTORIZATION METHODS（矩阵分解方法）

3.A BASIC MATRIX FACTORZATION MODEL（一个基本的矩阵分解模型）

4.LEARNING ALGORITHMS（学习算法）

4.1stochastic gradient descent随机梯度下降

4.2Alternating least squares交替最小二乘法

5.ADDING BIASES（消除打分偏差）

6.ADDITIONAL INPUT SOURCES(附加输出源)-加入隐式反馈

7.TEMPORAL DYNAMICS(时序动态)

8.INPUTS WITH VARYING CONFIDENCE LEVELS（不同置信水平的输入）

论文

MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS
推荐系统中的矩阵分解技术

背景

正如Netflix竞赛所证明的那样，矩阵分解模型在产生产品推荐时优于经典的最近邻技术，并且允许合并辅助信息，如隐性反馈（implicit feedback）、时间效应(temporal effects)和置信水平(confidence levels)。

1.RECOMMENDER SYSTEM STRATEGIES（推荐系统策略）

一般来说，推荐系统分为两种策略。内容过滤和协同过滤

1.1内容过滤

内容过滤（CBF）方法为每个用户或产品创建一个配置文件，以描述其特性。例如，一部电影的配置文件可以包括对其类型、参与演员、票房（受欢迎程度）等方面。用户配置文件可能包括人口统计信息或填写适当的问卷。

配置文件将用户与匹配的产品相关联。但是也会存在一个问题就是：这些信息往往是很难获得的。

原文：Collaborative filtering analyzes relationships between users and interdependencies among products to identify new user-item associations.

内容过滤的替代方案是依赖于过去的用户行为，例如，以前的交易或产品评级，而不需要创建明确的配置文件，这种方法被称为协同过滤。

1.2协同过滤（Collaborative filtering）

分析用户和用户之间的关系和产品之间的相关性，以识别新的用户-项目关联。

CF最大的吸引力在于它是无域的，但是它可以处理使用内容过滤时难以捉摸且难以分析的数据方面。

虽然比基于内容的技术更准确，但协同过滤也面临冷启动（cold start）的问题，因为它无法解决系统的新产品和新用户的问题（当一个新用户来的时候，我们无法获取历史信息），而在这方面内容过滤表现更好。

协同过滤主要分为两个领域：邻域算法（neighborhood methods）、隐语义模型（latent factor models）。

1.2.1邻域算法：

邻域算法的基本思想是计算项目（item）之间的关系，或用户之间的关系。

面向用户的邻域算法（The user-oriented neighborhood method）。如图1，Joe喜欢左边的三部电影，为了给他进行预测，系统会找到也喜欢这些电影的相似用户，然后确定他们喜欢哪些其他的电影。在这种情况下，这三个人都喜欢Saving Private Ryan，所以这是推荐首选，第二是……

图一

面向item的方法：评估用户user对项目item的偏好是基于同一用户对该item的“相邻”项目的评分。当同一用户打分时，相邻项目往往会获得相似的得分。例如，考虑电影拯救大兵瑞恩。它的邻居可能包括战争电影、斯皮尔伯格电影和汤姆汉克斯电影等。为了预测特定用户对拯救大兵瑞恩的评分，我们将查找该用户实际评分的电影最近的邻居。

1.2.2隐语义模型（latent factor models）

LFM是一种另一种的方法，基于用户购买记录，使用20-100个左右的因子（使用向量矩阵的方法）来衡量或者表征用户或者商品信息，来解释评分。比如在电影场景中，这个因子可能用来衡量「comedy」、「drama」、「action」或者「children」的程度，或者更泛化的讲述主人公的「development」或者「quirkiness」(比较难翻译，保留原文含义)，更或者，该因子完全无法解释。对于用户来说，每个因素衡量的是用户对相应电影因素中得分较高的电影的喜爱程度。

图2用一个简单的例子，在二维空间说明了这一思想。考虑两个假设的维度，横坐标表示女性导向和男性导向，纵坐标表示严肃和轻松（serious vs escapist）。该图展示了电影和用户都会落在这两个维度的位置上，也就是任一电影和用户都可以被这两个维度的隐向量所表示。在这一模型中，一个用户对电影的预测评分，相对于用户的平均评分，是等同于这一电影和该用户在该图上坐标的点乘积（the dot product）。举个例子，我们预计Gus会喜欢Dumb and Dumber，讨厌The Color Purple，给Braveheart中等评分。注意，有些电影——例如Ocean’s 11和用户——例如Dave在这两个维度中表现的相当中立。

2.MATRIX FACTORIZATION METHODS（矩阵分解方法）

最成功的隐因子模型的实现是基于矩阵分解。它的基本形式：矩阵分解从用户-项目评分矩阵中推断出的隐因子向量来表征item和user。user和item之间的相关性，使得矩阵分解大放异彩。这种方式由于他的好的可扩展性和预测的精准性，在这些年变得很受欢迎。另外，还为现实中各种状况的建模提供了灵活性。

推荐系统依靠各种类型的输入数据，这些数据往往被放置在一个维度表示用户，另一维度表示感兴趣的item的矩阵中。最方便的数据是高质量的显式反馈，包括用用户根据她们对产品的兴趣的显式输入。例如，Netflix收集电影的星级评分和TiVo用户通过👍赞（thumbs-up）和👎踩（thumbs-down）来表明她们的偏好。我们会参考显式的用户反馈，例如评分。通常来说，显式反馈会构成一个稀疏矩阵，因为单个用户可能只会对很小部分的项目进行打分。

矩阵分解的一个强大点在于它允许合并辅助信息来填充矩阵。当显式反馈不可用时，推荐系统可以使用隐式反馈来推断用户的喜好，这是间接反映意见，通过观察用户行为包括购买记录，浏览记录，搜索模式甚至是鼠标的移动。隐式反馈通常表示事件的存在或不存在，因此它通常由一个密集填充的矩阵表示（隐式反馈的优点在于补充了缺失的元素，更容易得到一个稠密矩阵）。

3.A BASIC MATRIX FACTORZATION MODEL（一个基本的矩阵分解模型）

矩阵分解模型会将用户和项目信息映射到一个共同的f维的隐因子空间，使用用户项目评分交互矩阵|通过这个空间维度向量的内积形式|进行建模。因此，每一个项目i都会对应一个f维的向量qi，而每一个用户u也会对应一个f维的向量Pu。对于一个给定的项目i，qi中的元素衡量该项目在多大程度上拥有的这些因子的程度。对于一个给定的用户u，pu中的元素衡量的是用户对相应因子较高的项目的兴趣程度。由此产生的点积：

$q_i^Tp_u$

捕获了用户u和项目i之间的交互——用户对项目特征的总体兴趣。用户u对项目i的预测评分用以下公式表示：

公式1：
$\widehat r_{ui} =q_i^Tp_u$

最主要的挑战是处理每个项目和用户的在f维向量的映射（如何计算用户-项目向量矩阵）。当推荐系统完成了映射后，就能很容易地使用公式1评估出一个用户对任意项目的评分。

SVD（singular value decomposition）奇异值分解，是经典的技术，用于信息检索的识别潜在语义特征。在协同过滤中运用SVD，需要将user-item评分矩阵分解。这通常很困难，因为评分矩阵是稀疏的，大部分的值都是缺失的。当关于矩阵的知识不完整时，传统的SVD是没有明确定义的。此外，只处理相对较少的已知项目很大困难会造成过拟合。

早期的系统依靠去插补（imputation）填补缺失的评分，让评分矩阵变得稠密。然而，插补是非常昂贵的，因为它会在很大程度上增加数据量。此外，不准确的插补会使数据在很大程度上失真。因此，很多近期的工作研究建议直接在观测到的评分矩阵上建模，同时通过正则化来避免过拟合。为了得到因子向量，系统将已知的评分集的平方误差最小化：

公式2：

$\min_{q*,p*} \sum_{(u,i)\in\kappa}{(r_{ui}-q_i^Tp_u)^2+\lambda(\|q_i\|^2+\|p_u\|^2)}$

κ 表示（u，i）对的集合 ,r_{ui}表示训练集（the training set）

系统通过拟合先前观察到的评级来学习模型。无论如何，目的是通过这种方法归纳这些原有的评分来预测未知的评分。因此，系统应该通过正则化（调整那些参数）来避免对观测数据的过拟合。常数λ控制正则化的范围并且通常通过交叉验证得到。

关于正则化的lambda，特别的提了一嘴，Ruslan Salakhutdinov and Andriy Mnih提出了 “Probabilistic Matrix Factorization ，PMF这种概率的方式建模来添加正则化

4.LEARNING ALGORITHMS（学习算法）

两种方法：stochastic gradient descent随机梯度下降和alternating least squares（ALS）交替最小二乘法

4.1stochastic gradient descent随机梯度下降

Simon Funk推广了随机梯度下降法（Funk-SVD）的优化(Netflix Update: Try This at Home)，该算法变量了训练集中所有的评分。对于每个给定的训练案例，系统预测rui，并计算相关的预测误差：

$e_{ui}\overset{def}= r_{ui}-q_i^Tp_u.$

然后它在梯度的相反方向将参数修改维与γ成比例的幅度，也就是对目标函数求偏导，产生：
$\\q_i\leftarrow q_i+\gamma \cdot(e_{ui}\cdot p_u-\lambda\cdot q_i) \\p_u\leftarrow p_u+\gamma \cdot(e_{ui}\cdot q_i-\lambda\cdot p_u)$

整个SGD的函数代码如下所示：

def sgd(data_matrix, user, item, alpha, lam, iter_num):
for j in range(iter_num):for u in range(data_matrix.shape[0]):for i in range(data_matrix.shape[1]):if data_matrix[u][i] != 0:e_ui = data_matrix[u][i] - sum(user[u,:] * item[i,:])user[u,:] += alpha * (e_ui * item[i,:] - lam * user[u,:])item[i,:] += alpha * (e_ui * user[u,:] - lam * item[i,:])return user, item

这种流行的方法 4-6 结合了实现的简易性和相对较快的运行时间,然而，在某些方面，ALS更有效。

4.2Alternating least squares交替最小二乘法

因为qi和pu都是未知的，目标函数（公式2）非凸。然而，如果我们固定其中一个未知数，该目标函数就会变成二次方程，并且可以得到最优解。因此，ALS技术反复分别固定其中一个变量，并计算迭代另一个变量，直至最终模型收敛。

虽然SGD要比ALS更容易更快，但ALS至少在两种情况下是有利的。第一个是并行计算qi。在ALS，系统独立于其他向量因子来计算每个qi，同时独立于其他用户因子来计算每个pu。这会导致算法存在潜在的大规模并行化。第二种情况是针对一隐式数据为中心的系统。矩阵不再稀疏，循环遍历每个单独的训练案例——使用梯度下降是不切实际的。ALS可以高效的处理这种情况。

5.ADDING BIASES（消除打分偏差）

对协同过滤来说，矩阵分解的一个优点是它处理各种数据方面的灵活性和其他专用的需求。这需要在相同的学习框架中调整评分函数（公式1）。公式1尽力获取用户和物品之间的交互，并产生不同评分值（rating）。然而，大部分观测到的评分值不同是与用户或是项目有关，即偏差（biases）和intercepts，独立于任何交互行为。例如，传统的协同过滤数据表现出较大的系统性倾向，一些用户给予比其他其他用户更高的评分，一些项目获得比其他项目更高的评分。毕竟，有些产品被普遍认为比其他产品更好(或更差)。

因此，用qi^Tpu来解释完整的评分是不充分的。系统试图确定这些中个体用户或项目偏差可以解释的部分，只将数据的真实交互部分用于因子建模。rui偏差的一阶近似如下：

公式3： $b_{ui} = \mu+b_i+b_u$

bui表示rui的偏置，包含了用户和项目对rating的影响。μ表示全部评分的平均值，参数bu和bi分别表示用户u和项目i的观测偏差。例如，假设你希望对用户Joe对电影Titanic的评分进行估计。现在，假设所有电影的平均分μ是3.7星，此外，《泰坦尼克号》比一般电影好，所以它的评分往往比平均水平高0.5颗星。但是，Joe是一个挑剔的用户，他的评分往往比平均水平低0.3颗星。因此Joe对泰坦尼克号的评价是3.9颗星(3.7 + 0.5 - 0.3)。在公式1 的基础上添加偏置参数，预测评分的公式如下：

公式4： $\widehat r_{ui}=\mu+b_i+b_u+q_i^Tp_u$

因此，这个预测评分由四个部分构成：总体的平均分，项目偏差，用户偏差，用户-项目的交互。这允许每个部分只解释与它相关的部分。系统通过最小化平方误差函数进行学习：

公式5： $\min_{q*,p*} \sum_{(u,i)\in\kappa}{(r_{ui}-\mu-b_u-b_i-q_i^Tp_u)^2+\lambda(\|q_i\|^2+\|p_u\|^2+b_u^2+b_i^2)}$

整个SGD变为：

def sgd_bias(data_matrix, user, item, alpha, lam, iter_num, miu):
b_u = [1] * rating_matrix.shape[0]b_i = [1] * rating_matrix.shape[1]for j in range(iter_num):for u in range(data_matrix.shape[0]):for i in range(data_matrix.shape[1]):if data_matrix[u][i] != 0:b_ui = b_u[u] + b_i[i] + miue_ui = data_matrix[u][i] - b_ui - sum(user[u,:] * item[i,:])user[u,:] += alpha * (e_ui * item[i,:] - lam * user[u,:])item[i,:] += alpha * (e_ui * user[u,:] - lam * item[i,:])b_u[u] += alpha * (e_ui - lam * b_u[u])b_i[i] += alpha * (e_ui - lam * b_i[i])return user, item, b_u, b_i

通过观测数据捕捉bias，对精确建模比较重要。因此，其他工作提供了更精细的偏见模型(11)

6.ADDITIONAL INPUT SOURCES(附加输出源)-加入隐式反馈

通常，一个系统需要处理冷启动问题，其中部分用户提供很少的评分，使对她们的品味得出大致结论变得困难。缓解这个问题的一种方法的合并关于用户的附加信息源推荐系统可以使用隐式反馈捞了解用户的偏好。事实上，他们可以收集行为信息，而不管用户是否愿意提供明确的评级。除了用户可能提供的评级外，零售商还可以通过顾客的购买或浏览历史来了解他们的倾向。

为简单起见，考虑一个带有布尔隐式反馈的情况。N(u)表示用户u隐式偏好的项目集。这样，系统就可以通过用户隐式偏爱的项目来分析用户。在这里，需要一组新的项目因子，其中项目i与属于R^f的x_i相对应。相应的，一个对N(u)中的项目表现出偏好的用户用向量表征：

简而言之：用一个Boolean值表示隐式反馈，N(u):用户u有过隐式反馈行为的item集合。

$\sum_{i\in N(u)}x_i$

添加正则化：

$|N(u)|^{-0.5}\sum_{i\in N(u)}{x_i.^{4.5}}$

另一个信息源是已知的用户属性，例如人口统计数据。同样，为了简单起见，考虑布尔属性，其中用户u对应于属性集A(u)，他可以描述性别，年龄，邮政编码，收入水平等等。每个属性对应一个不同的因子向量ya，通过一组与用户相关的属性来描述用户。隐因子ya描述用户：

$\sum_{a\in A(u)}y_a$

矩阵分解模型中聚合各种信息后，预测结果表示为：

公式6： $\widehat r_{ui}=\mu+b_i+b_u+q_i^T[p_u+|N(u)|^{-0.5}\sum_{i\in N(u)}x_i+\sum_{a\in A(u)}y_a]$

这个例子增强了用户的表示(数据缺乏更常见)，但在必要时项目也可以得到类似的处理。（缺少了item的信息）

7.TEMPORAL DYNAMICS(时序动态)

到目前为止，所提出的模型都是静态的，在现实中，随着新产品的出现，产品的认知和受欢迎程度不断变化。同样，顾客的偏好也在变化，导致他们重新定义自己的品味。因此系统应该考虑反映用户-项目交互的动态、时间漂移性质的时间效应。矩阵分解方法很好地用于建模时间效应，可以显著提高精度。将评级分解为不同的术语terms，允许系统分别处理不同的时序方面。具体来说，以下的术语terms随时间而变化：项目偏置bi(t);用户偏置bu(t);还有用户偏好，pu(t)。

第一个时序影响是项目的受欢迎程度会随着时间流逝而改变。例如，电影的受欢迎程度可能被外部事件触发。比如演员出演新的电影。因此，这些模型将项目偏差bi视为时间的函数。第二个时间效应允许用户随时间改变他们的基线评分。例如，一个平均打分为4星的用户现在可能给一部电影打3分。这可能包括很多因素，用户打分标准的改变，用户分配评分相对于其他近期评分的事实，以及评分者在家庭中的身份可能随着时间而变化的事实。因此，在这些模型中，参数bu是时间的函数。

时序动态会影响更甚；他们也会影响用户偏好，从而引起用户和项目之间的交互。随着时间流逝，用户会改变他们的偏好。例如，心理惊悚片的粉丝一年后可能会成为犯罪剧的粉丝，同样，人们也会改变对某些演员和导演的看法。该模型通过将用户因子向量pu作为时间函数来解释这种影响。另一方面，它列举了静态物品的特性，qi，因为，和人类不同的是，项目本质上是静态的。对时变参数进行精确的参数化，可将公式4替换为时刻t时额定值的动态预测规则:

在item的bias - bi(t)和user的bias-bu(t)，以及user的偏好pu(t).为什么没有q(t)呢？item相对变换更缓慢一些，可以认为是静态的，不会在短时间内发生变化。

公式7： $\widehat r_{ui}=\mu+b_i(t)+b_u(t)+q_i^Tp_u(t)$

8.INPUTS WITH VARYING CONFIDENCE LEVELS（不同置信水平的输入）

不是所有观测到的评分数据都有相同的权重或置信度（confidence）。例如，大规模的广告可能会影响某些item的rui，而这些项目并不能没有长期特征。类似地，系统可能会面临想要改变对某些物品评分的用户。

另一个例子是围绕隐性反馈构建的系统。在会解释用户行为的系统中，用户的确切偏好水平是很难量化的。因此，系统使用原始的二进制表示，表示“可能喜欢产品”或“可能对产品不感兴趣”。在这种情况下，将置信度分数与估计的偏好联系起来是有价值的。置信度是可以来自描述行为频率的可用数值，例如，用户看某个节目的时间有多长，或者用户购买某种商品的频率有多高。这些数值表示每个观测值的置信度。各种与用户偏好无关的因素可能会导致一次性事件；然而，一个重复出现的事件可能用户的想法。

矩阵分解模型可以很容易地接受不同的置信水平，这使得它可以给不太有意义的观测值更少的权重。若将观察rui的置信度记为cui，则模型对代价函数(式5)进行增强，使其对置信度的解释如下:

公式8： $\min_{q*,p*} \sum_{(u,i)\in\kappa}{c_{ui}(r_{ui}-\mu-b_u-b_i-p_u^Tq_i)^2+\lambda(\|q_i\|^2+\|p_u\|^2+b_u^2+b_i^2)}$