第 273 题：实现协同过滤的矩阵分解，SGD与ALS的并行化。
题目
实现协同过滤的矩阵分解，SGD与ALS的并行化。
完整讲解
一、矩阵分解形式
- 协同过滤的矩阵分解：评分矩阵 $R \approx U V^\top$，$U \in \mathbb{R}^{m \times r}$（用户隐向量），$V \in \mathbb{R}^{n \times r}$（物品隐向量），$r$ 为隐因子数。目标最小化 $\sum_{(i,j) \in \Omega} (R_{ij} - u_i^\top v_j)^2 + \lambda(|U|^2 + |V|^2)$，$\Omega$ 为已观测位置。
二、SGD（随机梯度下降）
- 对每个观测 $(i,j)$ 采样，更新 $u_i$ 与 $v_j$：梯度为 $(r_{ij} - u_i^\top v_j) \cdot (-v_j)$ 与 $(r_{ij} - u_i^\top v_j) \cdot (-u_i)$，对应 $u_i \leftarrow u_i + \eta \cdot (r_{ij} - u_i^\top v_j) v_j$，$v_j \leftarrow v_j + \eta \cdot (r_{ij} - u_i^\top v_j) u_i$。
- 并行化：按样本或按用户/物品分片；异步 SGD（各 worker 独立更新，定期同步或延迟同步）或同步 SGD（每轮汇总梯度）；注意冲突与收敛性，可加锁或用 Hogwild! 风格无锁更新不同维度。
三、ALS（交替最小二乘）
- 固定 $V$ 时，对每个用户 $i$ 的目标为关于 $u_i$ 的二次型，有闭式解：$u_i = (V_i^\top V_i + \lambda I)^{-1} V_i^\top r_i$，其中 $V_i$ 为 $i$ 评过分的物品对应的 $V$ 行。同理固定 $U$ 更新 $V$。交替迭代直至收敛。
- 并行化：每轮固定一侧，另一侧各用户（或各物品）的更新互不依赖，可完全并行；仅需广播当前 $U$ 或 $V$，适合分布式（如 Spark ALS）。每子问题为小规模线性方程组，可 Cholesky 或 CG 求解。
四、对比
- SGD：实现简单、适合在线与稀疏更新；并行时需处理冲突。ALS：每轮可大规模并行、适合批处理；实现稍复杂、需解线性系统。
面试要点
- 能写出矩阵分解的目标与 SGD 对单样本的更新公式；能写出 ALS 单步闭式解（$u_i = (V_i^\top V_i + \lambda I)^{-1} V_i^\top r_i$）及交替流程。
- 能说明 SGD 与 ALS 的并行方式（按样本/按用户物品、同步/异步；ALS 按用户/物品并行）。
记忆要点
- 矩阵分解：$R \approx UV^\top$；SGD 逐样本更新 $u_i,v_j$；ALS 固定一侧解二次型，闭式解，交替更新。
- 并行：SGD 按样本分片或异步；ALS 按用户/物品并行解小线性系统。