首页课程笔记自动化系凸优化

# SVM 基础

支撑向量机（Support Vector Machine, SVM）的初始想法源自凸集分离特性的应用。SVM 是优化研究者接触机器学习的第一个重要范例，因为它可以表述为经典的凸二次规划问题。

# 凸集分离 (Separation of Convex Sets)

超平面的定义

  • 超平面（hyperplane）是形如 {x∣aTx=b}\{x \mid a^T x = b\} 的集合，其中 a∈Rn,a≠0a \in \mathbb{R}^n, a \neq 0，b∈Rb \in \mathbb{R}
  • 超平面将 Rn\mathbb{R}^n 分为两个半空间
  • 弱半空间（闭半空间）包含超平面；严格半空间（开半空间）不包含超平面

分离的定义

  • 严格分离（strict separation）：超平面严格分离集合 AA 和 BB，如果 AA 和 BB 位于不相交的开半空间中
  • 强分离（strong separation）：超平面强分离集合 AA 和 BB，如果 AA 和 BB 位于不相交的闭半空间中，即存在 ε>0\varepsilon > 0 使得

    A⊂{x∣aTx≥b+ε},B⊂{x∣aTx≤b}A \subset \{x \mid a^T x \geq b + \varepsilon\}, \quad B \subset \{x \mid a^T x \leq b\}

    或反之
  • 强分离的另一种表述：inf⁡x∈AaTx>sup⁡y∈BaTy\inf_{x \in A} a^T x > \sup_{y \in B} a^T y（或交换 AA 和 BB）

相关定理

  • 强分离定理（Strong separation theorem）
  • 适当分离定理（Proper separation theorem）
  • 支撑超平面定理（Support hyperplane theorem）
  • 点到有限维闭凸集的投影

# 线性判别 (Linear Discrimination)

问题设定

假设我们想要用超平面分离两组点（向量）{x1,…,xN}\{x_1, \ldots, x_N\} 和 {x1,…,xM}\{x_1, \ldots, x_M\}：

wTxi+b>0,i=1,…,N(6.1)w^T x_i + b > 0, \quad i = 1, \ldots, N \tag{6.1}

wTxj+b<0,j=1,…,M(6.2)w^T x_j + b < 0, \quad j = 1, \ldots, M \tag{6.2}

方程 (6.1)-(6.2) 等价于关于 w,bw, b 的齐次线性不等式组。

从线性可分到最大间距

我们希望进一步找到最优超平面，以最大间距（超平面与最近训练数据点之间的距离）分离不同类别。这个目标可以定义为最大化点与超平面之间的最小距离：

max⁡w,bmin⁡{∥x−xi∥:wTx+b=0,i=1,…,M+N}\max_{w, b} \min \left\{\|x - x_i\| : w^T x + b = 0, i = 1, \ldots, M+N\right\}

归一化与最大间距超平面

参数 ww 和 bb 可以重新缩放，使得最接近超平面 wTx+b=0w^T x + b = 0 的点位于两个超平面 wTxi+b=±1w^T x_i + b = \pm 1 上。因此，我们可以通过计算来分类：

wTxi+b≥1,i=1,…,NwTxj+b≤−1,j=1,…,M\begin{aligned} w^T x_i + b &\geq 1, \quad i = 1, \ldots, N \\ w^T x_j + b &\leq -1, \quad j = 1, \ldots, M \end{aligned}

间距的计算

给定满足 wTz1+b=1w^T z_1 + b = 1 和 wTz2+b=−1w^T z_2 + b = -1 的任意两点 z1z_1 和 z2z_2，有

wT(z1−z2)=2w^T(z_1 - z_2) = 2

最短距离为

wT∥w∥(z1−z2)=2∥w∥\frac{w^T}{\|w\|}(z_1 - z_2) = \frac{2}{\|w\|}

因此，两个超平面 H1={z∣wTz+b=1}H_1 = \{z \mid w^T z + b = 1\} 和 H2={z∣wTz+b=−1}H_2 = \{z \mid w^T z + b = -1\} 之间的欧几里得距离等于 2/∥w∥2/\|w\|。

最大间距优化问题

线性判别的思想是用最大间距分离两组点：

min⁡w,b12∥w∥2s.t.wTxi+b≥1,i=1,…,NwTxj+b≤−1,j=1,…,M\begin{align*} \min_{w, b} \quad & \frac{1}{2}\|w\|^2 \\ \text{s.t.} \quad & w^T x_i + b \geq 1, \quad i = 1, \ldots, N \\ & w^T x_j + b \leq -1, \quad j = 1, \ldots, M \end{align*}

这显然是一个关于 w,bw, b 的二次规划问题，具有线性约束。这是问题的原始形式（primal form）。

引入符号变量

可以引入符号变量 yiy_i 和 yjy_j：

yi=1 对于 wTxi+b≥1,i=1,…,Ny_i = 1 \text{ 对于 } w^T x_i + b \geq 1, \quad i = 1, \ldots, N

yj=−1 对于 wTxj+b≤−1,j=1,…,My_j = -1 \text{ 对于 } w^T x_j + b \leq -1, \quad j = 1, \ldots, M

则约束可以统一写为：

yk(wTxk+b)≥1,k=1,…,N+My_k(w^T x_k + b) \geq 1, \quad k = 1, \ldots, N+M

其中 yk∈{+1,−1}y_k \in \{+1, -1\} 是类别标签。

# 鲁棒线性判别 (Robust Linear Discrimination)

在实际应用中，数据可能不完全线性可分，或者我们希望找到对噪声更鲁棒的超平面。这引出了软间隔（soft margin）SVM 的概念。

# 转导 SVM (Transductive SVM)

转导 SVM 是一种半监督学习方法，利用未标记数据来改进分类性能。

# SVM 的更深入讨论

# 可分离问题与核方法 (Separable Problems and Kernels)

软间隔 SVM（Soft Margin SVM）

当数据不完全线性可分时，引入松弛变量（slack variables）ξi≥0\xi_i \geq 0：

min⁡w,b,ξ12∥w∥2+C∑i=1Nξis.t.yi(wTxi+b)≥1−ξi,i=1,…,Nξi≥0,i=1,…,N\begin{align*} \min_{w, b, \xi} \quad & \frac{1}{2}\|w\|^2 + C \sum_{i=1}^N \xi_i \\ \text{s.t.} \quad & y_i(w^T x_i + b) \geq 1 - \xi_i, \quad i = 1, \ldots, N \\ & \xi_i \geq 0, \quad i = 1, \ldots, N \end{align*}

其中 C>0C > 0 是惩罚参数，控制对误分类的惩罚程度。

对偶问题

通过拉格朗日对偶，软间隔 SVM 的对偶问题为：

max⁡α∑i=1Nαi−12∑i,j=1NαiαjyiyjxiTxjs.t.∑i=1Nαiyi=00≤αi≤C,i=1,…,N\begin{align*} \max_{\alpha} \quad & \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j \\ \text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, \quad i = 1, \ldots, N \end{align*}

核方法 (Kernel Methods)

为了处理非线性可分问题，可以通过核函数将数据映射到高维特征空间：

  • 核函数：K(xi,xj)=ϕ(xi)Tϕ(xj)K(x_i, x_j) = \phi(x_i)^T \phi(x_j)，其中 ϕ\phi 是特征映射
  • 常用核函数：
    • 线性核：K(xi,xj)=xiTxjK(x_i, x_j) = x_i^T x_j
    • 多项式核：K(xi,xj)=(xiTxj+1)dK(x_i, x_j) = (x_i^T x_j + 1)^d
    • 径向基函数（RBF）核：K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)
    • Sigmoid 核：K(xi,xj)=tanh⁡(κxiTxj+θ)K(x_i, x_j) = \tanh(\kappa x_i^T x_j + \theta)

核技巧 (Kernel Trick)

在对偶问题中，只需要计算 xiTxjx_i^T x_j，可以替换为 K(xi,xj)K(x_i, x_j)：

max⁡α∑i=1Nαi−12∑i,j=1NαiαjyiyjK(xi,xj)\max_{\alpha} \quad \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j)

决策函数变为：

f(x)=∑i=1Nαi∗yiK(xi,x)+b∗f(x) = \sum_{i=1}^N \alpha_i^* y_i K(x_i, x) + b^*

其中 αi∗\alpha_i^* 是对偶问题的最优解，只有支持向量（αi∗>0\alpha_i^* > 0）参与决策。

# 训练问题：直接方法 (Training Issues: Direct Approach)

直接求解原始问题

  • 对于线性 SVM，可以直接求解原始二次规划问题
  • 使用标准的 QP 求解器（如 CPLEX、Gurobi）
  • 适用于小到中等规模的问题
  • 优点：直观、易于理解
  • 缺点：对于大规模问题计算效率较低

# 训练问题：分解方法 (Training Issues: Decomposition)

分解方法的基本思想

  • 将大规模优化问题分解为一系列子问题
  • 每次只优化一部分变量（工作集），固定其他变量
  • 迭代求解，直到收敛
  • 适用于大规模 SVM 训练问题

工作集选择策略

  • 选择违反 KKT 条件最严重的样本
  • 选择对目标函数改进最大的样本
  • 各种启发式方法

# 训练问题：序列最小优化 (Training Issues: Sequential Minimal Optimization, SMO)

SMO 算法

  • SMO 是分解方法的特例，每次只优化两个变量
  • 对于 SVM 对偶问题，由于约束 ∑i=1Nαiyi=0\sum_{i=1}^N \alpha_i y_i = 0，至少需要同时优化两个变量
  • 算法步骤：
    1. 选择两个违反 KKT 条件的变量 αi,αj\alpha_i, \alpha_j
    2. 固定其他变量，优化这两个变量（有解析解）
    3. 更新 bb 和误差缓存
    4. 重复直到收敛

SMO 的优势

  • 每次子问题有解析解，计算快速
  • 内存需求小，适合大规模问题
  • 实现简单，收敛速度快

SMO 的变种

  • 广义 SMO 算法
  • 改进的工作集选择策略
  • 针对非 PSD 核的 SMO 类型方法

# 多类问题 (Multiclass Problems)

一对多方法 (One-vs-All, OVA)

  • 对于 KK 类问题，训练 KK 个二分类器
  • 第 kk 个分类器将第 kk 类与其他所有类分开
  • 预测时选择得分最高的类别

一对一方法 (One-vs-One, OVO)

  • 对于 KK 类问题，训练 (K2)=K(K−1)/2\binom{K}{2} = K(K-1)/2 个二分类器
  • 每对类别训练一个分类器
  • 预测时使用投票机制

多类 SVM 的直接方法

  • 直接构造多类 SVM 优化问题
  • 同时考虑所有类别，优化一个统一的目标函数
  • 例如 Crammer-Singer 方法

方法比较

  • 一对多方法：简单，但可能不平衡
  • 一对一方法：更平衡，但需要更多分类器
  • 直接方法：理论上更优，但实现复杂

# 最小二乘 SVM 和 ν\nu-SVM (LS-SVM and ν\nu-SVM)

最小二乘 SVM (Least Squares SVM, LS-SVM)

  • 将 SVM 的不等式约束改为等式约束
  • 优化问题变为：

    min⁡w,b,e12∥w∥2+γ2∑i=1Nei2s.t.yi(wTϕ(xi)+b)=1−ei,i=1,…,N\begin{align*} \min_{w, b, e} \quad & \frac{1}{2}\|w\|^2 + \frac{\gamma}{2} \sum_{i=1}^N e_i^2 \\ \text{s.t.} \quad & y_i(w^T \phi(x_i) + b) = 1 - e_i, \quad i = 1, \ldots, N \end{align*}

  • 优点：转化为线性方程组求解，计算简单
  • 缺点：失去稀疏性（所有样本都是支持向量）

ν\nu-SVM

  • 引入参数 ν∈(0,1]\nu \in (0, 1] 控制支持向量的比例和误分类率的上界
  • 优化问题：

    min⁡w,b,ξ,ρ12∥w∥2−νρ+1N∑i=1Nξis.t.yi(wTϕ(xi)+b)≥ρ−ξiξi≥0,ρ≥0\begin{align*} \min_{w, b, \xi, \rho} \quad & \frac{1}{2}\|w\|^2 - \nu \rho + \frac{1}{N} \sum_{i=1}^N \xi_i \\ \text{s.t.} \quad & y_i(w^T \phi(x_i) + b) \geq \rho - \xi_i \\ & \xi_i \geq 0, \quad \rho \geq 0 \end{align*}

  • ν\nu 可以解释为支持向量的下界和误分类率的上界

# 支持向量回归 (Support Vector Regression, SVR)

ϵ\epsilon-不敏感损失函数

对于回归问题，SVM 的推广是支持向量回归（SVR）。使用 ϵ\epsilon-不敏感损失函数：

Lϵ(y,f(x))={0如果 ∣y−f(x)∣≤ϵ∣y−f(x)∣−ϵ否则L_\epsilon(y, f(x)) = \begin{cases} 0 & \text{如果 } |y - f(x)| \leq \epsilon \\ |y - f(x)| - \epsilon & \text{否则} \end{cases}

SVR 优化问题

min⁡w,b,ξ,ξ∗12∥w∥2+C∑i=1N(ξi+ξi∗)s.t.yi−(wTϕ(xi)+b)≤ϵ+ξi(wTϕ(xi)+b)−yi≤ϵ+ξi∗ξi,ξi∗≥0\begin{align*} \min_{w, b, \xi, \xi^*} \quad & \frac{1}{2}\|w\|^2 + C \sum_{i=1}^N (\xi_i + \xi_i^*) \\ \text{s.t.} \quad & y_i - (w^T \phi(x_i) + b) \leq \epsilon + \xi_i \\ & (w^T \phi(x_i) + b) - y_i \leq \epsilon + \xi_i^* \\ & \xi_i, \xi_i^* \geq 0 \end{align*}

其中 ξi,ξi∗\xi_i, \xi_i^* 是松弛变量，允许样本在 ϵ\epsilon-管道外。

# 其他主题 (Other Topics)

多核学习 (Multiple Kernel Learning, MKL)

  • 学习多个核函数的组合
  • 通过半正定规划等方法优化核函数权重
  • 可以自动选择最适合数据的核函数

结构化数据的核

  • 针对图、树、序列等结构化数据的核函数
  • 扩展 SVM 到非向量数据

大规模 SVM 训练

  • 针对大规模数据集的专门算法
  • 并行和分布式实现
  • 在线学习算法

SVM 软件库

SVM 的理论基础

  • 统计学习理论
  • VC 维理论
  • 结构风险最小化原理
  • 正则化理论