在现代推荐系统中，用户行为数据以流的形式不断产生，系统需要实时响应并更新推荐结果。传统的批处理矩阵分解方法已无法满足毫秒级延迟的需求。本章深入探讨如何设计高效的增量算法，在保证推荐质量的同时实现快速更新。我们将分析在线学习的理论保证、数值稳定性挑战，以及工程实现的最佳实践。
在实时推荐场景中，用户兴趣随时间演化，旧数据的重要性逐渐降低。我们需要设计合理的遗忘机制来平衡历史信息与新鲜度。遗忘机制的设计直接影响模型对趋势变化的敏感度和稳定性。
指数遗忘模型
考虑矩阵分解的目标函数： \(\mathcal{L}_t = \sum_{(i,j) \in \Omega_t} w_{ij}^{(t)} (r_{ij} - \mathbf{u}_i^T \mathbf{v}_j)^2 + \lambda (\|\mathbf{U}\|_F^2 + \|\mathbf{V}\|_F^2)\)
其中时间权重 $w_{ij}^{(t)} = \exp(-\beta(t - t_{ij}))$，$t_{ij}$ 是观测时间，$\beta$ 控制遗忘速率。
指数遗忘的优势在于：
数学性质分析
指数遗忘的有效样本量（Effective Sample Size, ESS）： \(\text{ESS}_t = \frac{\left(\sum_{s=1}^t e^{-\beta(t-s)}\right)^2}{\sum_{s=1}^t e^{-2\beta(t-s)}} \approx \frac{1}{2\beta}\)
这提供了选择 $\beta$ 的理论指导：若希望有效利用约 $N$ 个时间单位的历史数据，应设置 $\beta \approx 1/(2N)$。
滑动窗口方法
另一种方法是只考虑最近 $W$ 个时间单位的数据： \(w_{ij}^{(t)} = \begin{cases} 1 & \text{if } t - t_{ij} \leq W \\ 0 & \text{otherwise} \end{cases}\)
这种硬截断虽然简单，但可能导致信息突变。实践中常用软窗口变体： \(w_{ij}^{(t)} = \sigma\left(\frac{W - (t - t_{ij})}{\tau}\right)\) 其中 $\sigma$ 是sigmoid函数，$\tau$ 控制过渡的平滑度。
分段线性遗忘
介于指数和窗口之间的折中方案： \(w_{ij}^{(t)} = \begin{cases} 1 & \text{if } t - t_{ij} \leq W_1 \\ 1 - \alpha(t - t_{ij} - W_1)/(W_2 - W_1) & \text{if } W_1 < t - t_{ij} \leq W_2 \\ 1 - \alpha & \text{if } t - t_{ij} > W_2 \end{cases}\)
这种方法保留近期数据的完整权重，对中期数据线性衰减，对远期数据保持最小权重。
自适应遗忘模型
更高级的方法是让遗忘率随数据特性动态调整： \(\beta_{ij}(t) = \beta_0 \cdot f(\text{volatility}_i, \text{popularity}_j, \text{sparsity}_{ij})\)
其中：
波动性估计
用户兴趣波动性可通过滑动窗口内的评分方差估计： \(\text{volatility}_i(t) = \sqrt{\frac{1}{|\mathcal{W}_i|} \sum_{(j,s) \in \mathcal{W}_i} (r_{ij}^{(s)} - \bar{r}_i^{(t)})^2}\)
其中 $\mathcal{W}_i$ 是用户 $i$ 在时间窗口内的交互集合。
多尺度遗忘
实际系统中，不同时间尺度的模式共存： \(w_{ij}^{(t)} = \sum_{k=1}^K \alpha_k \exp(-\beta_k(t - t_{ij}))\)
其中 $\sum_k \alpha_k = 1$，不同的 $\beta_k$ 对应不同时间尺度（小时、天、周、月）。
对于流式数据 $(i_t, j_t, r_t)$，标准SGD更新为： \(\mathbf{u}_{i_t} \leftarrow \mathbf{u}_{i_t} - \eta_t \nabla_{\mathbf{u}_{i_t}} \ell_t\) \(\mathbf{v}_{j_t} \leftarrow \mathbf{v}_{j_t} - \eta_t \nabla_{\mathbf{v}_{j_t}} \ell_t\)
其中 $\ell_t = (r_t - \mathbf{u}{i_t}^T \mathbf{v}{j_t})^2 + \lambda(|\mathbf{u}{i_t}|^2 + |\mathbf{v}{j_t}|^2)$。
收敛性定理（非凸情况）
在以下条件下：
则增量SGD收敛到稳定点的速率为： \(\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^T \|\nabla \mathcal{L}_t\|^2\right] = O\left(\frac{1}{\sqrt{T}}\right)\)
改进的收敛性分析
考虑矩阵分解的特殊结构，可以得到更紧的界。定义 Lyapunov 函数： \(V_t = \|\mathbf{U}_t - \mathbf{U}^*\|_F^2 + \|\mathbf{V}_t - \mathbf{V}^*\|_F^2\)
在适当的步长条件下： \(\mathbb{E}[V_T] \leq \frac{V_0}{T^\alpha} + O\left(\frac{\sigma^2}{T^{1-\alpha}}\right)\)
其中 $\alpha \in (0.5, 1)$ 取决于问题的强凸性程度，$\sigma^2$ 是噪声方差。
带遗忘的SGD分析
考虑指数遗忘权重，修正的更新规则变为： \(\mathbf{u}_{i_t} \leftarrow (1-\gamma)\mathbf{u}_{i_t} - \eta_t e^{-\beta(t-t_{ij})} \nabla_{\mathbf{u}_{i_t}} \ell_t\)
其中 $\gamma$ 是衰减因子，防止历史信息完全主导。
追踪误差分析
在非平稳环境下，定义追踪误差： \(\text{TE}_T = \frac{1}{T}\sum_{t=1}^T \|\mathbf{U}_t\mathbf{V}_t^T - \mathbf{M}_t^*\|_F^2\)
其中 $\mathbf{M}_t^*$ 是时刻 $t$ 的真实矩阵。可以证明： \(\mathbb{E}[\text{TE}_T] \leq O\left(\frac{1}{\sqrt{T}}\right) + O(\beta) + O(\Delta_T)\)
其中 $\Delta_T$ 衡量环境变化速度。这表明遗忘率 $\beta$ 需要在适应性和稳定性之间权衡。
方差减少技术
为了加速收敛，可以使用方差减少的SGD变体：
SVRG-style更新： \(\mathbf{g}_t = \nabla \ell_t(\mathbf{u}_t) - \nabla \ell_t(\tilde{\mathbf{u}}) + \tilde{\mathbf{g}}\) 其中 $\tilde{\mathbf{u}}$ 是快照点，$\tilde{\mathbf{g}}$ 是在快照点的完整梯度。
动量方法： \(\mathbf{m}_t = \beta_1 \mathbf{m}_{t-1} + (1-\beta_1)\nabla \ell_t\) \(\mathbf{u}_t = \mathbf{u}_{t-1} - \eta_t \mathbf{m}_t\)
关键研究方向：
随着数据累积，不同用户/物品的样本数差异巨大。动态正则化可以解决这个问题：
\[\lambda_i^{(t)} = \lambda_0 / \sqrt{n_i^{(t)} + 1}\]其中 $n_i^{(t)}$ 是用户 $i$ 到时刻 $t$ 的交互次数。
理论基础
这种设计基于贝叶斯观点：
更精确地，后验分布为： \(p(\mathbf{u}_i | \mathcal{D}_i) \propto \exp\left(-\frac{1}{2\sigma^2}\|\mathbf{u}_i\|^2 - \frac{1}{2\sigma_r^2}\sum_{j \in \mathcal{D}_i}(r_{ij} - \mathbf{u}_i^T\mathbf{v}_j)^2\right)\)
泛化误差界
动态正则化的泛化性能可以通过PAC-Bayes理论分析： \(\mathbb{E}[\mathcal{L}_{\text{test}}] \leq \mathcal{L}_{\text{train}} + O\left(\sqrt{\frac{\text{KL}(q\|p) + \log(1/\delta)}{n}}\right)\)
其中 KL 散度项受正则化控制。
多尺度正则化
考虑不同时间尺度的行为： \(\lambda_i^{(t)} = \lambda_{\text{long}} / \sqrt{n_i^{\text{all}}} + \lambda_{\text{short}} / \sqrt{n_i^{\text{recent}}}\)
其中：
信息论视角
从最小描述长度（MDL）原理，最优正则化应平衡模型复杂度和数据拟合： \(\text{MDL} = -\log p(\mathcal{D}|\mathbf{u}_i) + \text{KL}(\mathbf{u}_i \| \mathbf{u}_{\text{prior}})\)
这导出自适应正则化： \(\lambda_i^{(t)} = \frac{\sigma_r^2}{\sigma^2} \cdot \frac{1}{n_i^{(t)}}\)
稀疏感知正则化
对于极稀疏用户，标准正则化可能过强。一种改进是： \(\lambda_i^{(t)} = \lambda_0 \cdot \left(\frac{n_{\text{median}}}{n_i^{(t)} + n_{\text{median}}}\right)^\alpha\)
其中 $n_{\text{median}}$ 是中位数交互次数，$\alpha \in [0.5, 1]$ 控制调整强度。
数值稳定性考虑：
实践中，单一遗忘机制往往不够灵活。混合策略结合多种方法的优势：
分层遗忘模型 \(w_{ij}^{(t)} = \alpha \cdot w_{\text{exp}}^{(t)} + (1-\alpha) \cdot w_{\text{window}}^{(t)}\)
其中 $\alpha$ 可以自适应调整： \(\alpha(t) = \sigma\left(\frac{\text{MSE}_{\text{exp}} - \text{MSE}_{\text{window}}}{\tau}\right)\)
在线模型选择
使用专家算法（Multiplicative Weights）动态选择最佳遗忘策略： \(p_k^{(t+1)} = \frac{p_k^{(t)} \exp(-\eta L_k^{(t)})}{\sum_{k'} p_{k'}^{(t)} \exp(-\eta L_{k'}^{(t)})}\)
其中 $L_k^{(t)}$ 是策略 $k$ 的累积损失，$p_k^{(t)}$ 是选择概率。
事件驱动遗忘
某些事件（如节假日、促销）会导致用户行为突变： \(\beta(t) = \begin{cases} \beta_{\text{normal}} & \text{常规时期} \\ \beta_{\text{fast}} & \text{事件期间} \\ \beta_{\text{recovery}} & \text{事件后恢复期} \end{cases}\)
变点检测算法
使用贝叶斯在线变点检测（BOCD）： \(p(r_t | r_{1:t-1}) = \sum_{\tau} p(r_t | r_{\tau:t-1}) p(\tau | r_{1:t-1})\)
其中 $\tau$ 是最近变点的位置。
研究挑战：
竞争比分析
定义在线算法的竞争比： \(\rho = \sup_{\text{sequence}} \frac{\text{ALG}_{\text{online}}}{\text{OPT}_{\text{offline}}}\)
对于指数遗忘的在线矩阵分解： \(\rho \leq 1 + O(\sqrt{\beta T})\)
这表明遗忘率 $\beta$ 不能太大。
Regret界
考虑与最佳固定遗忘率的比较： \(R_T = \sum_{t=1}^T \ell_t^{\beta_t} - \min_{\beta^*} \sum_{t=1}^T \ell_t^{\beta^*}\)
使用在线镜像下降可得： \(R_T \leq O(\sqrt{T \log K})\)
其中 $K$ 是候选遗忘率的数量。
样本复杂度
达到 $\epsilon$-近似解需要的样本数： \(m = O\left(\frac{r(n_1 + n_2)\log(1/\epsilon)}{\epsilon^2} \cdot \frac{1}{1-e^{-\beta T}}\right)\)
遗忘机制增加了有效样本复杂度。
计算-统计权衡
定义计算预算约束下的近似误差： \(\text{Error}(T, B) = \underbrace{O(1/\sqrt{T})}_{\text{统计误差}} + \underbrace{O(B^{-\gamma})}_{\text{计算误差}}\)
其中 $B$ 是计算预算，$\gamma$ 取决于算法效率。
当新增一个评分时，可以利用秩一更新避免完全重新计算。这在实时系统中至关重要，将更新复杂度从 $O(r^3)$ 降至 $O(r^2)$。
给定 $\mathbf{A} = \mathbf{X}^T\mathbf{X} + \lambda\mathbf{I}$，新增样本 $(\mathbf{x}, y)$ 后： \(\mathbf{A}' = \mathbf{A} + \mathbf{x}\mathbf{x}^T\)
利用Sherman-Morrison公式： \((\mathbf{A}')^{-1} = \mathbf{A}^{-1} - \frac{\mathbf{A}^{-1}\mathbf{x}\mathbf{x}^T\mathbf{A}^{-1}}{1 + \mathbf{x}^T\mathbf{A}^{-1}\mathbf{x}}\)
数值稳定性增强
标准Sherman-Morrison公式在 $1 + \mathbf{x}^T\mathbf{A}^{-1}\mathbf{x} \approx 0$ 时不稳定。稳定版本：
\((\mathbf{A}')^{-1} = \mathbf{A}^{-1} - \frac{\mathbf{u}\mathbf{u}^T}{1 + \|\mathbf{u}\|^2}\) 其中 $\mathbf{u} = \mathbf{A}^{-1/2}\mathbf{x}$
基于Cholesky分解的稳定实现
维护Cholesky分解 $\mathbf{A} = \mathbf{L}\mathbf{L}^T$，更新过程：
这种方法数值稳定且保持正定性。
删除操作的处理
当需要删除旧数据（遗忘）时，使用减法版本： \((\mathbf{A} - \mathbf{x}\mathbf{x}^T)^{-1} = \mathbf{A}^{-1} + \frac{\mathbf{A}^{-1}\mathbf{x}\mathbf{x}^T\mathbf{A}^{-1}}{1 - \mathbf{x}^T\mathbf{A}^{-1}\mathbf{x}}\)
注意：需要检查 $\mathbf{x}^T\mathbf{A}^{-1}\mathbf{x} < 1$ 以保证正定性。
加权更新扩展
对于带时间权重的更新： \(\mathbf{A}' = \mathbf{A} + w_t \mathbf{x}\mathbf{x}^T\)
修正的Sherman-Morrison公式： \((\mathbf{A}')^{-1} = \mathbf{A}^{-1} - \frac{w_t \mathbf{A}^{-1}\mathbf{x}\mathbf{x}^T\mathbf{A}^{-1}}{1 + w_t \mathbf{x}^T\mathbf{A}^{-1}\mathbf{x}}\)
应用于矩阵分解
对于用户嵌入更新： \(\mathbf{u}_i = (\mathbf{V}_{\Omega_i}^T\mathbf{V}_{\Omega_i} + \lambda\mathbf{I})^{-1}\mathbf{V}_{\Omega_i}^T\mathbf{r}_i\)
新增评分 $(i,j,r_{ij})$ 后，只需更新：
误差累积分析
经过 $k$ 次更新后的误差界： \(\|(\mathbf{A}_k)^{-1} - (\mathbf{A}_k)^{-1}_{\text{exact}}\|_F \leq k \epsilon_{\text{machine}} \kappa(\mathbf{A}_0)^2\)
建议每 $O(1/\epsilon_{\text{machine}})$ 次更新后重新计算精确逆。
缓存友好的实现
为了优化缓存性能，使用分块更新：
BlockSize = 32 // L1 cache line
for block in blocks:
prefetch(A_inv[block])
update(A_inv[block])
对于批量更新，Woodbury矩阵恒等式提供了高效方案： \((\mathbf{A} + \mathbf{U}\mathbf{C}\mathbf{V}^T)^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1} + \mathbf{V}^T\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}^T\mathbf{A}^{-1}\)
批量评分更新
当同时到达 $k$ 个新评分时：
复杂度：$O(r^2k + k^3)$，当 $k \ll r$ 时高效。
优化的Woodbury实现
为避免数值不稳定，使用QR分解：
并行化策略
parallel for each user i:
update A_i and u_i
gemm, syrk细粒度并行优化
使用原子操作避免锁：
atomic_add(A[i,j], delta)
memory_fence()
atomic_add(b[i], r * v[j])
NUMA感知的数据布局
在多处理器系统中：
UserData {
A_inv: aligned to NUMA node
embeddings: interleaved across nodes
update_queue: per-node queue
}
批大小的自适应调整
根据系统负载动态调整： \(k_{\text{opt}} = \arg\min_k \left(\frac{T_{\text{collect}}(k)}{k} + T_{\text{compute}}(k)\right)\)
其中：
实现要点：
不是所有嵌入都需要实时更新。懒惰求值策略大幅减少计算量：
三级更新策略
智能缓存管理
CacheEntry {
embedding: Vector
last_update: Timestamp
pending_updates: Queue<Update>
access_count: int
update_cost: float
}
更新决策函数： \(\text{should\_update} = \frac{\text{staleness} \times \text{importance}}{\text{update\_cost}} > \theta\)
其中：
成本模型
更精确的更新成本估计： \(\text{cost}(i) = c_{\text{compute}} \cdot |\Omega_i| + c_{\text{memory}} \cdot r^2 + c_{\text{sync}}\)
其中：
LRU-K缓存策略
考虑访问模式的时间局部性：
access_score(i) = Σ_{k=1}^K w_k * time_since_kth_access(i)
evict_score(i) = staleness(i) / access_score(i)
版本化缓存
支持多版本读取，避免更新阻塞查询：
VersionedEmbedding {
versions: RingBuffer<(Version, Embedding)>
current_version: AtomicInt
}
近似更新理论
定义近似因子 $\alpha$： \(\mathbf{u}_{\text{approx}} = \alpha \mathbf{u}_{\text{old}} + (1-\alpha) \mathbf{u}_{\text{increment}}\)
误差界： \(\|\mathbf{u}_{\text{approx}} - \mathbf{u}_{\text{exact}}\| \leq \frac{\alpha}{1-\alpha} \cdot \|\Delta \mathbf{u}\|\)
分层缓存架构
缓存提升决策： \(\text{promote}(i) = \frac{\text{access\_rate}(i) \times \text{value}(i)}{\text{size}(i)} > \tau_{\text{level}}\)
研究线索：
Lock-Free更新算法
避免锁竞争的无锁更新：
AtomicUpdate(user_id, item_id, rating):
loop:
old_A = load(A[user_id])
new_A = old_A + v[item_id] * v[item_id]'
if CAS(A[user_id], old_A, new_A):
break
Compare-And-Swap优化
使用双重检查减少CAS失败：
FastUpdate(user_id, item_id, rating):
expected = load(version[user_id])
new_A = compute_update(...)
if load(version[user_id]) == expected:
if CAS(A[user_id], old_A, new_A):
increment(version[user_id])
异步SGD的理论保证
在延迟 $\tau$ 有界的情况下： \(\mathbb{E}[\|\mathbf{u}_T - \mathbf{u}^*\|^2] \leq O\left(\frac{1}{\sqrt{T}} + \frac{\tau}{T}\right)\)
这表明适度的异步不会显著影响收敛性。
Hogwild!算法分析
对于稀疏数据，无锁并行SGD的收敛速率： \(\mathbb{E}[\mathcal{L}_T] - \mathcal{L}^* \leq O\left(\frac{L\sigma^2}{T} + \frac{L^2\tau^2\sigma^2}{T^2}\right)\)
其中 $L$ 是Lipschitz常数，$\sigma^2$ 是梯度方差。
延迟补偿机制
考虑梯度延迟的影响： \(\mathbf{g}_{\text{comp}} = \mathbf{g}_t + \sum_{s=t-\tau}^{t-1} \mathbf{H}_s (\mathbf{w}_s - \mathbf{w}_{t-\tau-1})\)
其中 $\mathbf{H}_s$ 是Hessian近似。
分布式快照
使用Chandy-Lamport算法实现一致性快照：
这允许在不停止系统的情况下进行checkpoint和恢复。
向量时钟同步
维护因果一致性：
VectorClock {
clocks: Map<NodeId, LogicalTime>
update(node_id):
clocks[node_id] += 1
merge(other: VectorClock):
for (id, time) in other.clocks:
clocks[id] = max(clocks[id], time)
}
最终一致性模型
定义收敛条件： \(\lim_{t \to \infty} \mathbb{E}[\|\mathbf{U}_i^{(t)} - \mathbf{U}_j^{(t)}\|_F] = 0\)
对所有节点 $i, j$。
参数服务器架构
| 有界陈旧性：$ | \text{version}_i - \text{version}_j | \leq B$ |
冲突解决策略
当多个节点同时更新同一嵌入：
通信优化
async_push(gradient):
compressed = compress(gradient)
future = send_async(compressed)
error_buffer += gradient - decompress(compressed)
理论保证
分布式SGD的收敛速率： \(\mathbb{E}[\|\nabla \mathcal{L}_T\|^2] \leq O\left(\frac{1}{\sqrt{nT}} + \frac{\sigma^2}{nT} + \frac{G^2\tau^2}{T^2}\right)\)
其中 $n$ 是节点数，展示了线性加速直到通信瓶颈。
将冷启动视为少样本矩阵补全问题，利用已有用户/物品的知识构建有效的先验。这种方法将冷启动从”无中生有”转变为”知识迁移”。
共享隐空间模型
基本假设：新用户的隐向量可以从其特征预测： \(\mathbf{u}_{\text{new}} = \mathbf{W}_u \mathbf{f}_u + \boldsymbol{\epsilon}_u\)
其中：
分层贝叶斯模型
更精细的建模考虑不确定性： \(\begin{aligned} \mathbf{u}_i &\sim \mathcal{N}(\mathbf{W}_u \mathbf{f}_i, \boldsymbol{\Sigma}_u) \\ \mathbf{W}_u &\sim \mathcal{MN}(\mathbf{M}_0, \boldsymbol{\Sigma}_u, \boldsymbol{\Omega}) \\ r_{ij} &\sim \mathcal{N}(\mathbf{u}_i^T \mathbf{v}_j, \sigma^2) \end{aligned}\)
这提供了预测的不确定性估计，对主动学习至关重要。
元学习视角
将冷启动视为few-shot learning问题：
使用MAML（Model-Agnostic Meta-Learning）框架： \(\mathbf{W}^* = \arg\min_{\mathbf{W}} \sum_{i \in \mathcal{T}_{\text{train}}} \mathcal{L}(\mathbf{W} - \alpha\nabla_{\mathbf{W}}\mathcal{L}_i(\mathbf{W}))\)
多任务学习
不同用户群体共享部分结构： \(\mathbf{U} = \mathbf{U}_{\text{shared}} + \sum_{k=1}^K \mathbf{U}_k \odot \mathbf{Z}_k\)
其中 $\mathbf{Z}_k$ 是群体指示矩阵。
选择最优的初始交互来快速学习新用户偏好。关键是平衡探索（减少不确定性）与利用（提供好的推荐）。
不确定性采样
基于后验方差选择物品： \(j^* = \arg\max_j \text{Var}[\hat{r}_{ij} | \mathcal{D}]\)
对于线性模型，方差可解析计算： \(\text{Var}[\hat{r}_{ij}] = \mathbf{v}_j^T (\mathbf{V}_{\mathcal{D}}^T\mathbf{V}_{\mathcal{D}} + \lambda\mathbf{I})^{-1} \mathbf{v}_j\)
信息增益最大化
选择最大化互信息的物品： \(j^* = \arg\max_j I(\mathbf{u}_i; r_{ij} | \mathcal{D})\)
对于高斯分布： \(I(\mathbf{u}_i; r_{ij}) = \frac{1}{2}\log\left(1 + \frac{\mathbf{v}_j^T\boldsymbol{\Sigma}_{\mathbf{u}|i}\mathbf{v}_j}{\sigma^2}\right)\)
Thompson采样
平衡探索与利用的贝叶斯方法：
| 从后验采样：$\tilde{\mathbf{u}}_i \sim p(\mathbf{u}_i | \mathcal{D})$ |
批量主动学习
同时选择 $k$ 个物品的次模优化问题： \(\mathcal{S}^* = \arg\max_{|\mathcal{S}|=k} f(\mathcal{S})\)
其中 $f(\mathcal{S})$ 是次模函数（如信息增益）。贪心算法提供 $(1-1/e)$ 近似保证。
上下文相关的主动学习
考虑时间、位置等上下文： \(j^* = \arg\max_j g(\text{uncertainty}_j, \text{context}_t, \text{diversity}(\mathcal{S} \cup \{j\}))\)
样本复杂度界
给定秩-$r$ 矩阵，达到 $\epsilon$-精度需要的样本数：
均匀采样情况： \(m = O(r(n_1 + n_2)\log(1/\epsilon))\)
非均匀采样的改进界： \(m = O(\mu r \log(n_1 + n_2) \log(1/\epsilon))\) 其中 $\mu$ 是相干性参数。
在线学习的regret界
对于冷启动用户的累积regret： \(R_T = \sum_{t=1}^T (r^* - r_t) = O(\sqrt{rT\log T})\)
其中 $r^*$ 是最优推荐的回报。
主动学习的加速
相比随机选择，主动学习可以指数级减少样本需求：
矩阵补全的信息论下界
任何算法至少需要： \(m \geq c \cdot r(n_1 + n_2 - r)\) 个观测才能精确恢复秩-$r$ 矩阵。
关键挑战：
混合方法
结合多种信息源：
渐进式个性化
随着数据积累逐步过渡： \(\mathbf{u}_i(t) = \alpha(t) \cdot \mathbf{u}_{\text{prior}} + (1-\alpha(t)) \cdot \mathbf{u}_{\text{learned}}\)
其中 $\alpha(t) = \exp(-\gamma \cdot n_i(t))$。
群体先验
利用相似用户群体： \(\mathbf{u}_{\text{prior}} = \frac{1}{|\mathcal{N}_i|}\sum_{k \in \mathcal{N}_i} \mathbf{u}_k\)
其中 $\mathcal{N}_i$ 是基于特征的最近邻。
在线更新的数值技巧
用户和物品的隐因子随时间演化： \(\mathbf{u}_i(t) = \mathbf{u}_i(t-1) + \mathbf{w}_i(t)\) \(\mathbf{v}_j(t) = \mathbf{v}_j(t-1) + \mathbf{z}_j(t)\)
其中 $\mathbf{w}_i(t), \mathbf{z}_j(t)$ 是演化噪声。
将隐因子演化建模为状态空间模型：
状态方程： \(\mathbf{x}_t = \mathbf{F}\mathbf{x}_t + \mathbf{w}_t\)
观测方程： \(r_t = \mathbf{h}_t^T \mathbf{x}_t + v_t\)
Kalman滤波提供了最优的在线估计。
许多推荐场景存在周期性（日、周、季节）：
傅里叶基展开： \(\mathbf{u}_i(t) = \mathbf{u}_i^{(0)} + \sum_{k=1}^K (\mathbf{a}_{ik} \cos(\omega_k t) + \mathbf{b}_{ik} \sin(\omega_k t))\)
研究方向：
用户兴趣的突变需要及时检测：
CUSUM算法的矩阵版本： \(S_t = \max(0, S_{t-1} + \|\mathbf{r}_t - \mathbf{U}_t\mathbf{V}_t^T\|_F - \delta)\)
当 $S_t > h$ 时触发变点警报。
高级主题：
本章深入探讨了实时推荐系统中的增量矩阵方法，主要贡献包括：
理论框架：建立了在线矩阵分解的统一分析框架，包括遗忘机制、收敛性保证和regret界。
关键公式汇总：
未来研究方向：
练习15.1 证明指数遗忘权重下的SGD更新等价于求解一个加权最小二乘问题。
提示：考虑累积损失函数 $\sum_{s=1}^t \beta^{t-s} \ell_s$。
练习15.2 给定秩为 $r$ 的 $m \times n$ 矩阵，使用Sherman-Morrison公式计算添加一个新行后的SVD更新复杂度。
提示：考虑增量SVD的计算步骤。
练习15.3 设计一个自适应遗忘率算法，使得稀疏用户的数据保留更久。
提示：遗忘率应该与用户活跃度成反比。
练习15.4 推导在线矩阵分解的regret界，考虑数据流是对抗性选择的情况。
提示：使用在线凸优化的分析框架，注意矩阵分解的非凸性。
练习15.5 设计一个分布式增量矩阵分解算法，支持异步更新且保证最终一致性。
提示：考虑参数服务器架构和延迟补偿。
练习15.6 分析Kalman滤波在隐因子演化中的计算瓶颈，提出一个近似算法将复杂度从 $O(r^3)$ 降到 $O(r)$。
提示：利用协方差矩阵的特殊结构。
练习15.7 推导多任务学习框架下的增量矩阵分解，其中不同任务共享部分隐空间。
提示：使用分块矩阵表示共享和特定结构。
练习15.8 设计一个在线算法同时处理显式评分和隐式反馈，考虑两种数据的不同噪声特性和到达频率。
提示：使用多目标优化框架。