矩阵分解介绍

作者: 老喵呜_1 | 来源:发表于2020-03-31 18:28 被阅读0次

之前的文章中提到关于推荐算法中矩阵分解的部分算法,但是十分粗略。在这篇文章中想具体讨论一下矩阵分解的相关内容。

模型构造

定义矩阵R \in R^{m\times n}表示m个用户对n个物品的评分,我们的目标是将R分解成两个矩阵U \in U^{m \times k}P \in P^{n \times k}使得R \approx U \times P^T,如下图所示。

矩阵分解

在这里,我们引入了一个新的变量k,表示两个新矩阵的列数。因此对于R中的每个元素R_{i, j},我们希望它会约等于两个向量u_i, p_j \in R^k的点乘的结果。从直观上看,这个模型假设每个R中的每个评分结果都由k个因素所影响,而UP则表示有每个用户和物品对k个因素的倾向。

这里假设R表示用户对电影的打分,那么显然,每个电影都会关联到一个或多个分类上,那么每个用户也会对一些分类感兴趣或者不感兴趣。因此用户对电影的打分取决于用户喜好和电影类型的相似程度。那么问题来了,我们如何高效地搭建分类体系?对电影来说,包括演员、导演、语言、类型等等好多分类维度,这给手动搭建分类体系带来了极大的难度。

但是好在我们对协同过滤的直观解释是,如果用户A给电影C打了高分,用户B给电影C和D打了高分,那么用户A也有可能会给电影D打高分。他不需要进一步解释说电影C和D有什么可解释的相似性。这就让矩阵分解解决协同过滤有了用武之地,因为我们不需要让算法解释那k个因素到底是啥。

扯远了,回到矩阵分解这个话题上。我们的目标是想最优化矩阵RU\times P^T的相似程度,所以,自然,目标函数为
J=||R-U\times P^T||_2 + \lambda(||U||_2 + ||P||_2)
其中,第一项是矩阵RU\times P^T之间的均方差,用来描述分解的两个矩阵与原矩阵的近似程度。第二项成为“正则项”,主要为了防止模型过拟合,减小模型的规模用。

在这里注意目标函数存在两个参数:k\lambda。因此在你打算优化目标函数之前,需要确定这两个参数(超参数)的值,可以用交叉验证法等一些方法去优化这两个参数,但是这些内容不在本文讨论的范畴内,接下来的算法都假定这两个参数已经确定下来了。

梯度下降

梯度下降是机器学习领域最优化问题的首选解决方法。这个方法原理很简单,随机赋给待学习的参数初始值并计算此时的目标函数,然后每一次迭代计算目标函数关于参数的梯度,并用其更新参数,直到目标函数收敛到最小值。当然,该算法只能保证收敛到局部最优,不能保证一定能收敛到全局最优。

但是一般不太会用梯度下降做矩阵分解,虽然他的优化效果挺好,但是,如果原始矩阵R的维度特别大的话,需要优化的参数过多(n \cdot k + m \cdot k)。在实际的问题中,这个数量通常非常大,所以需要找到一个既能并行计算又能通过矩阵相关性质来提高算法效率的办法

交替最小二乘法(Alternating Least Squares, ALS)

再来看看矩阵分解的目标函数,其中,||R-U\times P^T||_2=\sum_{i,j}(R_{i,j}-u_i \times p_j),如果我们给定P求最优的U,那么这个问题就变得简单了。

回忆线性回归里我们最优化\omega使得||y-X\omega||_2最小,那么得到的\omega的值为\omega=(X^TX)^{-1}X^Ty

ALS用的就是这种思想,它的一次迭代包含两步。在每次迭代,首先固定P去求最优的U,然后再固定U去求最优的P。由于每次固定一个矩阵后,求的另一个矩阵都是最优的,因此每一步迭代目标函数必定不会增加,直到收敛。和梯度下降法一样的是,该算法也只能保证收敛到局部最优。

由于每一次迭代包含两个步骤,所以在固定其中一个矩阵求另一个矩阵最优解的目标函数如下:
\forall u_i: J(u_i) = ||R_{i} - u_i \times P^T||_2 + \lambda \cdot || u_i ||_2 \forall p_j: J(p_j) = || R_{,j} - U \times p_j^T||_2 + \lambda \cdot ||p_j||_2
因此每次迭代求得的最优解为:
u_i=(P^T \times P + \lambda I)^{-1}\times P^T \times R_{i} p_j=(U^T \times U + \lambda I)^{-1}\times U^T \times R_{,j}

由于求每个u_i时与u_{j\neq i}无关,因此在这里可以并行计算。

SVD和矩阵分解

严格来说,SVD和之前提到的矩阵分解问题并不一样,它是将目标矩阵分为三个矩阵的乘积:U \in R^{m \times k}, \Sigma \in R^{k \times k}, V \in R^{m \times k},使得A = U \times \Sigma \times V^T

它比一般的矩阵分解问题来说约束更多:

  • \Sigma是一个对角矩阵,值为A的奇异值。一般来说这k个奇异值在\Sigma中按降序排列
  • UV均为正交矩阵
  • 它的解是唯一的

所以如果我们假设矩阵A是用户和物品的打分矩阵(用户表示行,物品表示列),这意味着:

  • UV中的每行代表一个用户/物品的特征,例如,U_{i,k}表示用户i在第k个分类上的喜好程度,V_{j,k}表示物品在同样第k个分类上的程度。
  • 对于每个评分(A_{i,j}的值),都可以用一组互相独立的分类解释。对于某个用户i和物品j,分值A_{ij}的值等于\sum_{k=1}^{K}[ u_{i,k} * \Sigma_{k,k} * v_{j,k}^T],其中:
    • u_{i,k}表示第i个用户的第k个特征
    • v_{j,k}^T表示第j个物品的第k个特征
    • \Sigma_{k,k}表示第k个特征对评分的影响力
      也就是说,每个评分代表着用户i和物品j,不同分类带不同权重的相似程度。
  • 由于\Sigma中的值是矩阵A的奇异值按降序排列,所以可以很好的估计我们需要对用户和物品设置特征(k)的值

当然这种方法有两个问题

  1. 计算复杂度略高
  2. 原始矩阵不能有任何缺失值,但是在协同过滤中矩阵有大量数据缺失

缺失值处理

因为我们在矩阵分解之前和之后,只比较有值的元素,因此可以稍微修改一下目标函数:
J = \sum_{i,j}w_{i,j}\cdot (R_{i,j}-u_i \times p_j^T)^2 + \lambda (||U||_2 + ||P||_2)其中
w_{i,j}=\left\{ \begin{aligned} 1 & & R_{i,j} \text{is known}\\ 0 & & R_{i,j} \text{unknown} \end{aligned} \right.

矩阵分解的应用

推荐物品

做矩阵分解其实我们并不只是想得到物品和用户的向量化表示,而是希望用它来给用户推荐最适合的商品。因此我们可以把用户矩阵和物品矩阵相乘得到填满所有未知元素的矩阵R^*,它包含了所有用户对所有商品的评分。所以,可以根据R^*矩阵,寻找用户还没见过的,且对其评分高的物品推荐给用户。而且,我们也可以利用R^*的结果进行推荐的排序。

降维

有时候,矩阵分解并不是用于推荐,而是用于预处理高维的数据,降低数据的维度,之后再喂给其他训练模型中。它可以将高维稀疏的数据转化为低维的稠密数据,例如我们通过矩阵分解得到了用户和物品的向量化表示。另外,通过用户的向量化表示,我们可以用一些距离计算方法去求不同用户之间的相似程度。

参考资料

[1] How do you build a “People who bought this also bought that” style recommendation engine

相关文章

  • 矩阵分解介绍

    在之前的文章中提到关于推荐算法中矩阵分解的部分算法,但是十分粗略。在这篇文章中想具体讨论一下矩阵分解的相关内容。 ...

  • 第30课 奇异值分解

    奇异值分解:简称,是矩阵最终和最好的分解,分解的因子是正交矩阵,对角矩阵,正交矩阵,任意矩阵都有这种奇异值分解 对...

  • 线代--矩阵的分解-LU分解n阶方阵

    矩阵分解的概念:初中我们接触过数的分解,如:;推广到矩阵,一个矩阵也可以分解为几个矩阵乘积的形式,矩阵分解具有不同...

  • 非方正矩阵的LU分解_线性代数_day42

    矩阵的LU分解就是将矩阵分解成一个上三角矩阵,和一个下三角矩阵 矩阵的LU分解可以用于非方阵的分解 矩阵的LU分解...

  • 机器学习矩阵分解解析Recommender.Matrix.Fac

    目录: 1.为什么要矩阵分解 2.矩阵分解怎么分解 3.什么样的情况考虑矩阵分解 4.矩阵分解有哪些分类 5.各种...

  • 矩阵的LU分解2_线性代数_day41

    将矩阵A分解为 分解成了LU矩阵 LU分解大概有:

  • 2018-12-23 MF Basic

    【矩阵分解】 矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。常见的矩阵分解有可逆方阵的三角...

  • SVD奇异值分解(1)-预备知识

    引入 SVD奇异值分解属于矩阵分解的知识,矩阵分解用白话解释就是将一个复杂的矩阵分解成一些特殊形式的矩阵,这些特殊...

  • 推荐系统11:交替最小二乘 (ALS)及其改进Weighted-

    回顾矩阵分解 矩阵分解要将用户物品评分矩阵分解成两个小矩阵,一个矩阵是代表用户偏好的用户隐因子向量组成,另一个矩阵...

  • 矩阵分解的一点总结

    1.为什么要矩阵分解 2.矩阵分解的算法 3.矩阵分解算法的应用场景 4.评价指标 ---------------...

网友评论

    本文标题:矩阵分解介绍

    本文链接:https://www.haomeiwen.com/subject/nxwvuhtx.html