CodeGoRound
0%

矩阵分解 （一）SVD及其的几种变体

Posted on Edited on

矩阵分解 （一）SVD及其的几种变体

背景

在矩阵分解算法出现之前，基于协同过滤实现的推荐算法，一般是依靠近邻模型，即存在一个「user-item」的评分矩阵，类似于：

这个矩阵的每一行都表示一个用户（和物品关系）的向量，每一列都表示一个物品（和用户关系）的向量，在推荐时只需要根据向量相似度推荐相似度最高的n个物品（用户）即可，但是这种模型也存在一些问题：

  • 向量的维度一般较大，计算复杂度特别高。例如 用户向量的维度是物品总数，物品向量的维度则是用户总数，但是物品之间存在相关性，信息量并不随着向量维度增加而线性增加
  • 没有关系的维度上，一般使用0作为缺省值，数据量达到一定大小时，多数情况下一个系统里任意两个user-item对是没有关系的，即一个向量中多数值都是0，对相似度计算的结果影响较大

上述问题都可以在矩阵分解中解决，那矩阵分解具体是怎么做的呢？

实现原理

直观地说，矩阵分解就是在原本的大矩阵中分解出两个小矩阵，在推荐时，不用原先的大矩阵，而使用分解出的两个小矩阵计算

具体做法是，假设原本的user-item矩阵是m维n维的矩阵，即有m个用户，n个物品。选取一个k，这个k比m，n都小很多，可能是若干个数量级。通过一套算法 得到两个矩阵U和V，矩阵U的维度是m k ，矩阵V的维度是n * k。这两个矩阵需要能够通过矩阵乘法复原本来的矩阵，即：

​ \[ U_{m\times{k}}V_{n\times{k}}^{T} \approx A_{m\times{n}}\]

类似这样的计算方法就是矩阵分解，或者说叫做SVD（奇异值分解），但是SVD不能和矩阵分解（MF，下同）画等号，除了SVD还有很多矩阵分解的方法

SVD及其变体

SVD

从物理意义上解释，矩阵分解就是把用户和物品都映射到一个k维的空间中，这个k维空间不是显式的 每一个维度的值也没有一个很好的解释，每一个维度也没有名字，所以通常称其为“隐因子”，代表藏在直观矩阵下面的隐藏关联。

经过计算，得出两个小矩阵后，每一个用户有一个向量p，p的每个维度上的元素有正有负，代表用户和物品“不可说”的隐藏关联，每一个物品也有一个向量q，同样代表了对用户的隐藏关联，他们的数量和意义是一致的，数量即我们在计算时人为指定的k。

例如，用户u的向量是pu，物品i的向量是qi，那么在计算时，推荐分数直接计算两个向量的点积即可：

​ \[ \hat{r}_{ui} = p_{u}q_{i}^{T}\]

那么 两个矩阵是如何得到的呢？这是一个机器学习问题，按照机器学习框架，一般考虑两个核心要素：

  • 目标函数
  • 优化算法
目标函数

\[ \min_{q^{* },p^{* } } \sum_{(u,i) \in \kappa }{(r_{ui} - p_{u}q_{i}^{T})^{2} + \lambda (||q_{i}||^{2} + ||p_{u}||^{2})} \]

\(\sum_{(u,i) \in \kappa }\) 是对所有已知用户-物品评分对的求和

加号左边是误差平方和 用于控制模型偏差导致的欠拟合 \(r_{ui}\)是用户u对物品i的实际评分； \(p_{u}q_{i}^{T}\) 是通过用户向量和物品特征向量的内积得到的预测评分

加号右边是分解后参数的平方 是正则化项 用于控制模型方差导致的过拟合 确保找到的特征向量\(p_{u}\) \(q_{i}\)不会变得过大 常数 \(\lambda\)是正则化参数 用于平衡预测误差与正则化项的权重

在这个目标函数的基础上 需要使用优化算法找到能使它最小的参数 常用的有两个 交替最小二乘法 随机梯度下降。

交替最小二乘法

核心是 找到两个矩阵P和Q 让他们相乘后等于原矩阵

\[ R_{m \times n} = P_{m \times k} \times Q^{T}_{n \times k} \]

难点在于 P Q都是未知的 如果知道一个话 可以用线性代数解法求出另一个

\[ P_{m \times k} = R_{m \times n} \times Q^{-1}_{n \times k}\]

所以 最小二乘法的原理就是

  1. 初始化随机矩阵Q里面的元素值；
  2. 把Q矩阵当做已知的，直接用线性代数的方法求得矩阵P；
  3. 得到了矩阵P后，把P当做已知的，故技重施，回去求解矩阵Q；
  4. 上面两个过程交替进行，一直到误差可以接受为止。

以下是一个python实现 使用交替最小二乘法实现这个优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import numpy as np

def train_als(ratings, num_features, lambda_reg, num_iterations):
    num_users, num_items = ratings.shape

    # 初始化用户和物品特征矩阵
    user_features = np.random.rand(num_users, num_features)
    item_features = np.random.rand(num_items, num_features)

    # 交替执行用户和物品特征矩阵的最小二乘优化
    for iteration in range(num_iterations):
        # 优化用户特征矩阵
        for u in range(num_users):
            user_ratings = ratings[u, :]
            nonzero_indices = user_ratings > 0  # 得到用户评分过的物品索引
            # 构建A和b以求解Au = b
            A = (item_features[nonzero_indices].T @ item_features[nonzero_indices]) + \
                lambda_reg * np.eye(num_features)
            b = item_features[nonzero_indices].T @ user_ratings[nonzero_indices].T
            user_features[u] = np.linalg.solve(A, b)

        # 优化物品特征矩阵
        for i in range(num_items):
            item_ratings = ratings[:, i]
            nonzero_indices = item_ratings > 0  # 得到评分过该物品的用户索引
            # 构建A和b以求解Av = b
            A = (user_features[nonzero_indices].T @ user_features[nonzero_indices]) + \
                lambda_reg * np.eye(num_features)
            b = user_features[nonzero_indices].T @ item_ratings[nonzero_indices]
            item_features[i] = np.linalg.solve(A, b)

    return user_features, item_features

# 配置参数
num_features = 10  # 特征向量的维度
lambda_reg = 0.1  # 正则化系数
num_iterations = 20  # 迭代次数

# 假设有一个已知的评分矩阵ratings，其中未知评分用0表示
ratings = np.random.randint(1, 6, (100, 50))  # 示例：100个用户，50个项目

# 训练模型并输出特征矩阵
user_features, item_features = train_als(ratings, num_features, lambda_reg, num_iterations)
梯度下降方法

梯度下降是一个用于寻找函数最小值的迭代优化算法。在机器学习中，它通常用于最小化损失函数，即试图找到能够使损失函数达到最小值的参数。原理如下：

  1. 初始化：选择一个起始点作为参数的初始估计。
  2. 计算梯度：在当前点计算目标函数的梯度，梯度指向的是函数上升最快的方向。
  3. 反向移动：为了最小化函数，需要向梯度的反方向（下降最快的方向）移动一步。步长通常由学习率决定。
  4. 更新参数：将当前点更新为新点，再次执行梯度计算和更新步骤。
  5. 迭代：重复步骤2-4直到满足收敛条件，比如迭代次数、梯度大小小于阈值或者损失函数的变化小于某个阈值。

以下是一个python实现实例 使用随机梯度下降方法来实现这个优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import numpy as np

# 参数初始化
num_users, num_items = 100, 50  # 假设有100个用户和50个物品
num_features = 10  # 特征向量的维度
lambda_reg = 0.1  # λ正则化系数
alpha = 0.01  # 学习率(步长)
epochs = 10  # 训练迭代轮次

# 随机初始化用户和物品的特征矩阵
user_features = np.random.normal(0.0, 1.0, (num_users, num_features))
item_features = np.random.normal(0.0, 1.0, (num_items, num_features))

# 假设r_ui代表一个已经填充好的用户评分矩阵，κ是已知评分的(u,i)索引对集合
ratings = np.random.uniform(1, 5, (num_users, num_items))  # 随机生成示例评分
known_ratings = [(u, i) for u in range(num_users) for i in range(num_items) if np.random.rand() < 0.1]  # ~10%的已知评分

# 训练过程: 随机梯度下降
for epoch in range(epochs):
    np.random.shuffle(known_ratings)  # 打乱已知评分对
    for u, i in known_ratings:
        prediction = np.dot(user_features[u], item_features[i].T)
        error = ratings[u, i] - prediction
        # 更新特征向量
        user_features[u] += alpha * (error * item_features[i] - lambda_reg * user_features[u])
        item_features[i] += alpha * (error * user_features[u] - lambda_reg * item_features[i])

# 用户和物品的特征向量现在应该已经调整为最小化公式中的目标函数

带偏置项的SVD (BiasSVD)

​ 基础的SVD看起来很美好，但事实上，真实世界里充满了复杂，举个例子：在一个电影评分平台上，有一些用户会给出偏高的评分，比如标准宽松的用户，另一些用户可能对艺术的要求较为苛刻，那么ta对于所有的电影的评分就会相对更低，对于item（电影），则会由于明星效应，或者迎合了一些社会热点等原因造成评分整体偏高或偏低，所以为了尽量减少这类偏置情况对于整体模型的影响，SVD就有了一个变种：把偏置信息抽出来的SVD

​ 这种算法下一个用户对一个物品的评分会由四部分相加：

​ \[\hat{r}_{ui} = \mu + b_{i} + b_{u} + p_{u}q_{i}^{T} \]

从左到右分别代表：

  • 全局平均分\(\mu\),表现了训练数据的总体评分情况，对于固定的数据集，它是一个常数
  • 物品的评分偏置\(b_{i}\)，即独立于用户兴趣的因素，大致表示一个物品的总体评分
  • 用户的评分偏置\(b_i\)，即独立于物品特征的因素，大致表示一个用户的评分习惯
  • 用户和物品之间的兴趣偏好$ p_{u}q_{i}^{T}$，即前文提到的预测评分
目标函数

增加了偏置信息的SVD 目标函数稍有改变

​ \[\min_{q^{* },p^{* } }\sum_{(u, i) \in K} (r_{ui} - \mu - b_u - b_i - q_i^T p_u)^2 + \lambda (\|p_u\|^2 + \|q_i\|^2 + b_u^2 + b_i^2)\]

即在SVD目标函数的基础上，在加号左边的误差平方和中减去偏置项，在加号右边的正则化项中引入偏置项，保持模型的稳定性

SVD++

增加完偏置信息后，SVD在一定程度上可以适应了现实世界的参差，但现实世界的残酷远不止如此（笑。

更贴合现实的情况是，相比起沉默的大多数，主动点评电影或者美食的用户是少数，这就导致了有的用户评分相对较少，也就是说，用户对于物品的隐式反馈要多于显式反馈，那么 该如何利用隐式反馈来弥补缺失的评分数据呢？另外，对于用户的个人属性，比如性别、年龄、地域等属性，是否也可以加入到模型中来弥补冷启动的不足呢？

对于这些需求，有一套专门的模型给出了方案，即在基础的SVD模型中结合用户的隐式反馈和属性变形来的：SVD++

SVD++模型的损失函数与传统的SVD类似，但是它加入了额外的项来表示用户的隐式反馈。用户 \(u\) 的特征向量 \(p_u\) 在 SVD++ 中被调整为基于其显式特征加权和所有其交互过的隐式特征的总和。

先说隐式反馈怎么加入，方法是：除了假设评分矩阵中的物品有一个隐因子向量外，用户有过行为的物品集合也都有一个隐因子向量，维度是一样的。把用户操作过的物品隐因子向量加起来，用来表达用户的兴趣偏好。

类似的，用户属性，全都转换成0-1型的特征后，对每一个特征也假设都存在一个同样维度的隐因子向量，一个用户的所有属性对应的隐因子向量相加，也代表了他的一些偏好。

具体来说，模型定义如下： \[ \hat{r}_{ui} = \mu + b_u + b_i + q_i^T \left(p_u + |N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_j \right) \] 其中：

  • $ _{ui} $ 是模型预测用户 $ u $ 对物品 $ i $ 的评分。
  • $ $ 是所有评分的全局平均值。
  • $ b_u $, $ b_i $ 分别是用户偏置和物品偏置。
  • $ q_i $, $ p_u $ 分别是物品 $ i $ 和用户 $ u $ 的特征向量。
  • $ y_j $ 是与物品 $ j $ 相关的隐式反馈特征向量。
  • $ N(u) $ 是用户 $ u $ 有过隐式反馈的物品集合。
  • $ |N(u)| $ 是集合 $ N(u) $ 中元素的个数，用于归一化。
目标函数

SVD++ 的目标函数增加了对隐式反馈特征的正则化，以避免过拟合： \[ \min_{b_u, b_i, p_u, q_i, y_j} \sum_{(u, i) \in K} (r_{ui} - \hat{r}_{ui})^2 + \lambda (\|p_u\|^2 + \|q_i\|^2 + b_u^2 + b_i^2 + \sum_{j \in N(u)} \|y_j\|^2) \]

TimeSVD

人，总是善变的；人对于事物的兴趣也是会随着时间变化的。所以，对于将过去时间内的行为和现在时间的行为用相同的权重计算，显然是不合理的，因为这个计算结果很可能无法代表用户当前的兴趣。所以，在SVD中考虑时间因素，也就成了顺理成章的事情。

具体的，有以下几种做法：

  1. 对评分按照时间加权，让久远的评分更趋近平均值；
  2. 对评分时间划分区间，不同的时间区间内分别学习出隐因子向量，使用时按照区间使用对应的隐因子向量来计算；
  3. 对特殊的期间，如节日、周末等训练对应的隐因子向量。

小结

本篇描述了经典的矩阵分解算法SVD及其的一些变体，那么经过分解后得到的稠密向量该如何使用，如何在庞大的数据中计算推荐项？

除了SVD，还有什么别的方法可以完成矩阵分解呢？他们和SVD有哪些不同？在不同的业务场景下孰优孰劣？请关注接下来的矩阵分解系列文章