CS267 · 第 12 课

机器学习（监督学习）

从线性代数到深度网络：机器学习中的并行化策略

---

机器学习分类

机器学习包含多种学习范式，每种有其独特的并行化需求：

类型	定义	示例
监督学习	从标注数据学习输入→输出映射	分类、回归
无监督学习	从未标注数据发现结构	聚类、降维
半监督学习	结合少量标注与大量未标注数据	自训练、图方法
强化学习	通过与环境交互学习策略	游戏、机器人控制

---

机器学习依赖线性代数

几乎所有机器学习方法的核心计算都可以归结为线性代数运算。BLAS（Basic Linear Algebra Subprograms）层次结构是理解这一点的关键：

级别	操作类型	复杂度	示例
Level 1 BLAS	向量-向量	O(n)	点积、向量加法
Level 2 BLAS	矩阵-向量	O(n²)	GEMV（矩阵乘向量）
Level 3 BLAS	矩阵-矩阵	O(n³)	GEMM（矩阵乘法）

---

并行类型：隐式与显式

机器学习中的并行可以分为两类：

• 隐式并行：由 BLAS 库、编译器或框架自动实现。程序员无需显式管理线程或进程。例如 OpenBLAS、MKL 自动使用多线程执行矩阵乘法。
• 显式并行：程序员显式设计数据分布、通信和任务调度。适用于跨节点的大规模训练。

---

扩展定律

理解并行系统的扩展行为对 ML 至关重要：

• 强扩展（Strong Scaling）：问题规模固定，增加处理器数量。目标是减少求解时间。受限于 Amdahl 定律。
• 弱扩展（Weak Scaling）：问题规模与处理器数量成比例增加。目标是处理更大问题。受限于 Gustafson 定律。

// 强扩展：固定 N=100万样本，从 1 核到 1024 核
// 理想：1024 核应快 1024 倍（实际因通信开销达不到）

// 弱扩展：每核 1000 样本，1024 核处理 102.4 万样本
// 理想：时间保持不变（实际因通信开销会增加）

---

神经网络训练：反向传播与 SGD

深度神经网络（DNN）的训练基于两个核心算法：

• 反向传播（Backpropagation）：通过链式法则高效计算损失函数对每个参数的梯度
• 随机梯度下降（SGD）：使用梯度更新参数以最小化损失

# 简化的 SGD 训练循环
for epoch in range(num_epochs):
    for batch in data_loader:  # mini-batch
        # 前向传播
        predictions = model(batch.inputs)
        loss = loss_fn(predictions, batch.targets)

        # 反向传播
        gradients = backward(loss, model.parameters())

        # 参数更新
        for param, grad in zip(model.parameters(), gradients):
            param -= learning_rate * grad

Mini-batch SGD 是实践中的标准做法：每个更新步骤使用一小批样本（而非单个样本或全部样本）计算梯度，兼顾梯度估计质量和计算效率。

---

并行化技术

大规模 DNN 训练有多种并行化策略：

并行类型	划分对象	通信模式
数据并行	训练样本（batch）	梯度聚合（allreduce）
模型并行	模型层/参数	激活/梯度传递
张量并行	单个张量（如权重矩阵）	矩阵乘法中间结果
流水线并行	网络层（阶段）	阶段间激活传递
专家并行	MoE 中的专家	门控路由

---

批量与数据并行

数据并行是最常用的并行策略：每个 worker 持有模型完整副本，处理不同的数据子集，然后聚合梯度。

# 数据并行伪代码
# 每个 rank 执行
for batch in local_data_split:
    grad = compute_gradient(model, batch)
    all_gradients = allreduce(grad, op="sum")  # 全局聚合
    model.update(all_gradients / world_size)

批量并行（Batch Parallelism）将大 batch 拆分到多个设备上。当 batch 很大时（如 GPT-3 使用 1024+ GPUs），全局 batch 可以非常大。

---

参数服务器架构

参数服务器（Parameter Server）是另一种经典架构：

• Server 节点：存储和更新全局参数
• Worker 节点：计算梯度，从 server 拉取参数，推送梯度

// 参数服务器工作流程
// Worker:
params = server.pull(key)           // 拉取最新参数
grad = compute_gradient(params, data)  // 计算梯度
server.push(key, grad)              // 推送梯度

// Server:
grads = collect_from_workers(params)
params -= lr * average(grads)       // 更新参数

---

DNN 训练的矩阵形式

DNN 训练可以完全用矩阵运算表示。考虑一个全连接层：

Y = XW + b

其中：
  X: [batch_size, input_dim]  输入矩阵
  W: [input_dim, output_dim]  权重矩阵
  b: [output_dim]             偏置向量
  Y: [batch_size, output_dim] 输出矩阵

反向传播也可以写成矩阵形式：

dX = dY · W^T          # 对输入的梯度
dW = X^T · dY          # 对权重的梯度
db = sum(dY, axis=0)   # 对偏置的梯度

这种矩阵形式使得我们可以直接利用高度优化的 BLAS 库（cuBLAS、MKL）进行计算。

---

批量+模型混合并行

实际大规模训练通常组合多种并行策略。例如，Megatron-LM 使用张量并行（机内）+ 流水线并行（机间）：

// Megatron-LM 风格的混合并行
// 同一节点内：张量并行（矩阵按列/行切分）
// 跨节点：流水线并行（不同层在不同节点）
// 全局：数据并行（不同节点组处理不同数据）

// 矩阵乘法的张量并行示例（列切分）
// W = [W1 | W2]  （按列切分到两个 GPU）
// Y = XW = [XW1 | XW2] = [Y1 | Y2]
// 每个 GPU 计算部分结果，最后 allgather

---

卷积神经网络与域并行

CNN 通过卷积核提取局部特征，其并行化策略包括：

• 数据并行：不同设备处理不同图像
• 模型并行：不同通道/滤波器分配到不同设备
• 域并行（Domain Parallelism）：将输入图像空间域切分到多个设备

// 域并行：将图像切分到 4 个设备
// 设备 1: 左上区域
// 设备 2: 右上区域
// 设备 3: 左下区域
// 设备 4: 右下区域
// 需要 halo 交换处理边界（类似 MPI 域分解）

---

Transformer 的序列与上下文并行

Transformer 是 NLP 和视觉领域的主流架构。长序列训练面临显存和计算瓶颈：

• 序列并行（Sequence Parallelism）：将序列维度切分到多个设备，与张量并行互补
• 上下文并行（Context Parallelism）：将长序列分段，各设备处理不同段，通过 attention 通信

---

注意力机制

自注意力（Self-Attention）是 Transformer 的核心：

Attention(Q, K, V) = softmax(QK^T / √d_k) · V

其中：
  Q: Query 矩阵 [seq_len, d_k]
  K: Key 矩阵 [seq_len, d_k]
  V: Value 矩阵 [seq_len, d_v]
  d_k: 注意力维度

注意力的计算复杂度为 O(n²d)，其中 n 是序列长度。这是长序列的主要瓶颈。

---

Ring Attention

Ring Attention 是一种处理超长序列的并行策略。设备排成环状，每个设备持有一部分 KV 和完整的 Q：

// Ring Attention 工作流程
// 设备 i 持有 Q_i, K_i, V_i
// 步骤 1: 设备 i 计算 Q_i 与 K_i 的本地 attention
// 步骤 2: 将 K_i, V_i 传递给设备 i+1（环状）
// 步骤 3: 收到 K_{i-1}, V_{i-1} 后继续计算
// 重复直到所有 KV 被处理

---

流水线并行

流水线并行将网络层分配到不同设备，像流水线一样处理不同 micro-batch：

方法	特点	代表
GPipe	同步更新，等待所有 micro-batch 完成	Google, 2019
PipeDream	异步更新，不同 micro-batch 可能在不同版本	Microsoft, 2019
1F1B	一进一出调度，减少显存	PipeDream-Flush

// GPipe 流水线示意（4 个 stage）
// Stage 1: layers 1-3    ← micro-batch 1, 2, 3, 4
// Stage 2: layers 4-6    ← micro-batch 1, 2, 3, 4
// Stage 3: layers 7-9    ← micro-batch 1, 2, 3, 4
// Stage 4: layers 10-12  ← micro-batch 1, 2, 3, 4
//
// 时间线：
// t1: [mb1] [  ] [  ] [  ]
// t2: [mb2] [mb1] [  ] [  ]
// t3: [mb3] [mb2] [mb1] [  ]
// t4: [mb4] [mb3] [mb2] [mb1]
// t5: [  ] [mb4] [mb3] [mb2]
// t6: [  ] [  ] [mb4] [mb3]
// t7: [  ] [  ] [  ] [mb4]

---

Mixture of Experts 专家并行

MoE（Mixture of Experts）模型包含多个"专家"子网络和门控网络。每个输入只激活少数专家，从而在不增加计算量的情况下增大模型容量。

// MoE 工作流程
// 1. 门控网络决定每个 token 发送给哪些专家
// 2. 将 token 路由到对应专家（跨设备通信）
// 3. 专家处理 token
// 4. 将结果路由回原设备，加权求和

// 专家并行：不同专家放在不同设备
// 设备 1: Expert 1, Expert 2
// 设备 2: Expert 3, Expert 4
// ...

---

支持向量机

支持向量机（SVM）是经典的监督学习方法，目标是找到最大化分类间隔的超平面。

线性 SVM

// 原始优化问题
minimize:  (1/2)||w||^2 + C * Σ ξ_i
subject to: y_i(w·x_i + b) ≥ 1 - ξ_i,  ξ_i ≥ 0

// 对偶问题（更常用）
maximize: Σ α_i - (1/2) Σ Σ α_i α_j y_i y_j K(x_i, x_j)
subject to: 0 ≤ α_i ≤ C,  Σ α_i y_i = 0

核技巧（Kernel Trick）

当数据线性不可分时，通过核函数将数据映射到高维空间：

核函数	公式
线性核	K(x,y) = x·y
多项式核	K(x,y) = (γ x·y + r)^d
RBF（高斯）核	K(x,y) = exp(-γ||x-y||²)
Sigmoid 核	K(x,y) = tanh(γ x·y + r)

SMO 算法

Sequential Minimal Optimization（SMO）是求解 SVM 对偶问题的高效算法，每次只优化两个 Lagrange 乘子。

// SMO 算法概要
repeat:
    选择违反 KKT 条件最严重的 α_i
    选择使目标函数下降最大的 α_j
    在约束下优化 (α_i, α_j)
until convergence

---

并行 SVM

有多种并行 SVM 方法，各有不同的并行策略和适用场景：

方法	策略	特点
Cascade SVM	层次化训练	将数据分块训练子 SVM，再合并训练上层
DC-SVM	分解协调	将大问题分解为子问题，协调器整合
CP-SVM	约束优化	基于约束优化的分布式求解
CA-SVM	通信避免	减少通信次数，以计算换通信

// Cascade SVM 示意
// Level 1: 数据分为 4 块，分别训练 SVM_1, SVM_2, SVM_3, SVM_4
// Level 2: 收集各子 SVM 的支持向量，合并后训练 SVM_12, SVM_34
// Level 3: 合并 SVM_12 和 SVM_34 的支持向量，训练最终 SVM

---

本课要点

---

知识检查