奇异值分解(SVD)时间复杂度分析与优化
奇异值分解(SVD)时间复杂度分析与优化
奇异值分解（SVD）是一种重要的矩阵分解方法，在数据科学和机器学习领域有着广泛的应用。本文将深入探讨SVD的时间复杂度分析及其优化方法，并介绍几种基于SVD的推荐系统算法变种，包括改进的SVD算法、SVD++算法和timeSVD算法。
1. SVD 时间复杂度分析
给定一个m × n的矩阵A，按照下面公式做分解：
$$
A = U \Sigma V^T
$$
其中Σ是一个m × n的矩阵，除对角线以外其他元素都是0，对角线上的值就是所谓的奇异值。U是m × m的酉矩阵，V是n × n的酉矩阵，即满足$U^T * U = I$。
分解过程如下：
- 将A的转置和A做矩阵乘法，得到一个n × n的方阵$A^T * A$，然后运用方阵特征分解，得到特征值和特征向量。
- 得到矩阵$A^T * A$的n个特征值和对应的n个特征向量v，将所有特征向量v张成一个n × n的矩阵V，就是前面公式里的V矩阵，一般叫其中V中的每个特征向量是A的右奇异向量。
- 同样的对A和A的转置做乘法，就得到m × m的方阵$A * A^T$，运用方阵特征分解，得到特征值和特征向量。
- 得到矩阵$A * A^T$的m个特征值和对应的m个特征向量u，将所有特征向量u张成一个m × m的矩阵U，就是前面公式里的U矩阵，一般叫U中的每个特征向量是A的左奇异向量。
- 计算奇异矩阵Σ。
这是标准的按照线性代数理论进行分解的方法。由于矩阵乘法的实时间复杂度是$O(n^3)$，那么不难得知，按照线性代数理论进行奇异值分解的时间复杂度是$O(\max(m, n)^3)$。在工业应用中，如推荐系统，物料数和用户数通常最少也是千万级别，三次方下来就10000亿，是一个很恐怖的时间复杂度。
2. SVD 分解算法优化
2.1 奇异值分解性质
对于奇异值分解结果的中间矩阵，它对角线上的值称为奇异值，按照从大到小排序，并且奇异值下降特别快，正常情况下前10%的奇异值占有了全部奇异值的99%，那么可以用前k个奇异值近似表示原始矩阵。
$$
A_{m \times N} \approx U_{m \times k} * \Sigma_{k \times k} * V_{k \times n}^T
$$
一般来说，这里$k << \min(m, n)$，可以达到数据压缩或者降维的作用。
2.2 截断奇异值分解
利用上面提到的奇异值分解的性质，可以借助截断奇异值分解来优化奇异值分解。首先不直接分解矩阵，而是用机器学习的方法，直接去求第二个矩阵。定义损失函数：
$$
C = \sum_{(i, j) \in R} [a_{ij} - u_i * v_j^T)^2 + \lambda (u_i^2 + v_j^2)]
$$
第一项使用平方差定义分解后和原始矩阵的RMSE，其中$a_{ij}$是原始矩阵的第i行第j列，$u_i$是推荐系统场景中的用户特征向量，$v_j$是物品特征向量，后面一项是正则化项。有了损失函数就可以用ALS或者梯度下降法求解了。这里的时间复杂度是$O(mnk)$，而k是个很小的数，那么复杂度就是相当于是$O(m * n)$，这样在千万的数据上计算复杂度瞬间变成100亿了。
3. 变种 SVD 算法
3.1 改进的 SVD 算法
前面说到，奇异值分解常用在推荐系统中，最简单的方法就是直接把评分矩阵分解去做推荐，但是实际中发现不管是用户还是物品都存在一定偏差，比如有些用户给的评分就是比其他人高0.5，或者有些电影用户倾向于给高分，但是建模的时候没有考虑进去这种情况。那么把用户和物品的偏差考虑进来，那么就可以对SVD算法进行改进，评分 = 兴趣 + 偏见。
$$
a_{u, i} = u + b_u + b_i + U_u * V_i^T
$$
其中$b_u$表示用户偏见，$b_i$表示物品偏见，$u$表示全局均值，损失函数为：
$$
C = \sum_{(u, i) \in R} \left( a_{u, i} - b_i - b_u - U_u * V_i^T \right) ^2 + \lambda \left( ||U_u|| ^2 + ||V_i|| ^2 + b_u^2 b_i^2 \right)
$$
3.2 SVD++ 算法
实际使用中，除了用户或者物品偏见，还有一个问题就是行为数据中的评分数据很少，但是隐式行为数据有很多，把隐式行为数据建模进去从而缓解评分稀疏提高推荐效果，这就是SVD++算法。SVD++在SVD中加入了用户对物品的隐式行为，SVD++的假设条件是评分 = 显式兴趣 + 隐式兴趣 + 偏见：
$$
a_{u, i} = u + b_u + b_i + V_i^T * \left( U_u + |I_u| ^{-\frac{1}{2}} * \sum_{j \in I_u} y_j \right)
$$
其中$I_u$是该用户有隐式行为的所有物品集合，而$y_j$是隐式评分电影j反应出的喜好值，其中对$I_u$取根号是一个经验值，这样就把系统中大量的隐式行为也建模到SVD算法中，虽然这么做对计算复杂度提高了不少，但是能够缓解评分稀疏提高推荐效果。同样的，损失函数为：
$$
C = \sum_{(u, i) \in R} \left( a_{u, i} - b_i - b_u - V_i^T * \left( U_u + \min(|I_u| ^{-\frac{1}{2}} * \sum_{j \in I_u} y_j) \right) \right) ^2 + \lambda \left( \sum_u (b_{i, u}^2 + ||U_u||^2) + \sum_i (b_i^2 + ||V_i|| ^2 + ||y_i||^2) \right)
$$
3.3 timeSVD 算法
2010年，Koren发现在Netflix的数据中，个体用户的兴趣会随着时间转移，论文中称作concepte drift(观念转移)。比如大家都知道的《大话西游》，刚上映票房很低，大家都给出的评分也不高，但是随着时间流逝，大家给出的评分越来越高。另外可能有些电影在某些特定的节日或者某天会获得高分，作者希望建立模型能捕捉到这些。timeSVD在SVD中加入了时间因素，也可以叫做有时序的SVD。timeSVD的假设条件是评分 = 显式兴趣 + 时序兴趣 + 热点 + 偏见。
按照原始论文的介绍来说，这个模型是为了对观念转移建模。从三个角度出发，首先是时间窗口概念，另外是实例权重，采用时间衰减，最后是集成学习的概念，引入多个基础预估方法。
static predictor是最基础的预估方法：
$$
b_{u,i}(t) = u + b_u + b_i
$$
mov predictor：
$$
b_{u,i}(t) = u + b_u + b_i + b_{i, Bin(t)}
$$
这里对$b_i$是$b_i(t) = b_i + b_{i, Bin(t)}$，分为Static和time changing两部分，引入物品的时间变化因素，对时间片进行划分。论文中是以10周为一片，共划分了30片，赋予一个$Bin(t)$，即1-30之间。时间片划分也可以是其他的，小的时间片可以有更好的性能，大的时间片能够让每片有更多的数据。
linear predictor，引入用户兴趣的变化，首先定义：
$$
dev_u(t) = sign(t - t_u) * |t - t_u|^{\beta}
$$
表示当前用户当前评分时间和平均评分时间的距离，论文中$\beta = 0.4$
然后对$b_u$引入时间变化到线性模型，多了一个需要训练的参数$\alpha$：
$$
b_u^{(1)} = b_u + \alpha_u * dev_u(t)
$$
引入到公式中得到：
$$
b_{u, i}(t) = u + b_u + \alpha_u * dev_u(t) + b_i + b_{i, Bin(t)}
$$
spline predictor通过另一种方法引入用户兴趣变化的模型，区别于前面的线性模型，这是一个曲线式模型：
$$
b_{u, i}(t) = u + b_u + \frac{\sum_{l=1}^{k_u} e^{-r|t-t^u|} * b_{t, l}^{u}}{\sum_{l=1}^{k_u} e^{-r|t-t^u|}} + b_i + b_{i, Bin(t)}
$$
linear+ predictor引入实时特定，比如用户某天心情，或者生日等，引入一个参数$b_{u, t}$，表示每日的特定偏差：
$$
b_{u, i}(t) = u + b_u + \alpha_u * dev_u(t) + b_i + b_{u, t} + b_{i, Bin(t)}
$$
spline+ predictor曲线模型也引入：
$$
b_{u, i}(t) = u + b_u + \frac{\sum_{l=1}^{k_u} e^{-r|t-t^u|} * b_{t, l}^{u}}{\sum_{l=1}^{k_u} e^{-r|t-t^u|}} + b_i + b_{u, t} + b_{i, Bin(t)}
$$
通过梯度下降法进行训练，损失函数为：
$$
C = \sum_{u, i, t \in K} \left( r_{u, i}(t) - u - b_u - \alpha_u * dev_u(t) - b_i - b_{u, t} - b_{i, Bin(t)} \right) ^2 + \lambda * \left(b_u^2 + \alpha_u^2 + b_{u, t}^2 + b_i^2 + b_{i, Bin{t}}^2 \right)
$$
原论文中对各个predictor用RMSE作为指标的结果：
这里通过时序建模，用户矩阵的参数表示为：
$$
u_u(t)[k] = p_{u, k} + \alpha_{u, k} * dev_u(t) + p_{u, k} * k = 1, \cdots, f
$$
这里k代表第k个predictor，每一个predictor单独训练，最终得到如下公式：
$$
a_{u, i} = u + b_i(t) + b_u(t) + V_i^T * (u_u(t) + |I_u|^{-\frac{1}{2}} * \sum_{j \in I_u} y_j)
$$
通过在Netflix数据集测试，对比三种算法，可以得到：