线性模型 - 支持向量机（参数学习）

支持向量机的主优化问题为凸优化问题，满足强对偶性，即主优化问题可以 通过最大化对偶函数来求解。对偶函数是一个凹函数，因此最大化对偶函数是一个凸优化问题，可以通过多种凸优化方法来进行求解，得到拉格朗日乘数的最优值 𝜆∗。但由于其约束条件的数量为训练样本数量，一般的优化方法代价比较高，因此在实践中通常采用比较高效的优化方法，比如序列最小优化(Sequential Minimal Optimization，SMO)算法 等。

一. 优化目标与约束

我们先回顾一下，上一篇博文中，关于支持向量机的优化目标。

对于线性可分的情况，SVM 的目标是找到一个超平面 w^T x + b = 0 将正负类数据分隔开，同时最大化“间隔”（margin）。在归一化条件下，我们要求所有训练样本满足：

其中 y_i​∈{+1,−1} 为样本标签。

在这种条件下，正类和负类之间的间隔为 。为了最大化间隔，我们实际上需要最小化 ||w||（或更常见地最小化  来便于求导）。因此，SVM 的原始优化问题可以写为：

二、拉格朗日对偶与参数学习

为了求解上述带有约束的优化问题，我们引入拉格朗日乘数，将其转化为无约束问题。构造拉格朗日函数：

其中 α_i ≥ 0 为拉格朗日乘数。

通过对 w 和 b 求偏导并令其为0，可以得到：

将 w 的表达式代入拉格朗日函数，就可以得到对偶问题：

这个对偶问题是一个凸二次规划问题，可以使用标准的优化算法（如 SMO 算法）求解，得到最优的 α^*。

一旦求得最优拉格朗日乘数 α^*，就可以通过

计算出最优的权重向量，同时利用支持向量上的约束 y_i (w^T x_i + b) = 1 来计算偏置 b^*。

三、理解：上面的优化问题，为什么可以转化为无约束问题，构造拉格朗日函数？

拉格朗日乘数法的核心思想是：在求解具有约束的优化问题时，最优解往往满足这样一个条件——目标函数的梯度与约束函数的梯度在最优点处是线性相关的，也就是说，它们在某个方向上是平行的。为了利用这一性质，我们引入拉格朗日乘数，将约束条件“融合”到目标函数中，构造一个新的无约束优化问题。

具体来说，对于一个带有等式约束的优化问题：

我们构造拉格朗日函数：

其中 λ是拉格朗日乘数。这个函数的意义在于：

• 当 g(x)=0 时，L(x,λ)=f(x)；
• 当 g(x)≠0 时，通过调整 λ 的值，可以“惩罚”那些不满足约束的 x 值。

求解原问题的最优解可以转化为寻找 L(x,λ) 关于 x 和 λ 的驻点，即求解下面的方程组：

为什么可以这样做？

• 梯度平行性原理：
  在最优点（假设满足某些正则条件），如果 x^* 是最优解，那么在满足 g(x^*)=0 的前提下，f(x) 在 x^* 处的变化必须受到约束的“制约”。也就是说，f(x) 的梯度 ∇f(x^*) 必须与 ∇g(x^*) 共线，这正是引入拉格朗日乘数 λ 的理由。通过构造 f(x)+λ g(x) 并求其驻点，我们就找到了满足这个“梯度平行”条件的 x^*。

• 转化为无约束问题：
  通过将约束项加权后加入目标函数，我们就将原来的约束问题转化为在 x 和 λ 上求无约束极值。只要找到这个联合问题的极值点，就能同时满足目标函数最优和约束条件。

例子：

假设我们要在约束 x^2 + y^2 = 1（单位圆）上寻找函数 f(x,y)=x+y 的最大值。

1. 构造拉格朗日函数： L(x,y,λ) = x + y + λ (x^2 + y^2 - 1).
2. 分别对 x、y 和 λ 求偏导并令其为0：

选择合适的符号后，可以求得 x 和 y 的值。

通过这种方式，我们就把原来的约束优化问题转化为了一个无约束问题，并利用拉格朗日乘数求得最优解。

四、理解支持向量机参数学习

• 最大间隔原理：
  优化目标 的最小化等价于最大化 的间隔，即让支持向量与决策超平面的距离最大化。这样得到的决策超平面对噪声和小样本扰动更鲁棒，具有更好的泛化能力。

• 支持向量的重要性：
  最终求得的 w^* 是由所有支持向量（即对应 α_i > 0 的样本）的线性组合形成的。这表明只有最靠近决策边界的样本对最终模型起关键作用，而其他样本对结果没有直接贡献。

• 对偶求解与核技巧：
  对偶问题的形式允许我们使用核函数 替代内积 ，从而扩展到非线性分类。这使得 SVM 不仅适用于线性可分问题，也能处理非线性情况。

五、支持向量机的最终决策函数是什么？

支持向量机的最终决策函数用来将输入数据分类为正类或负类，其基本形式为：

其中：

• w 是权重向量，
• b 是偏置，
• sgn⁡(⋅) 表示符号函数，输出 +1 或 -1。

在SVM的训练过程中，通过求解优化问题得到最优的 w^* 和 b^*，并且可以证明最优权重向量可以用支持向量的线性组合表示，即（结合上面的参数学习）

其中 α_i^* 是对应支持向量的拉格朗日乘数，y_i 为支持向量的标签，x_i 为支持向量本身。

因此，对于一个新样本 x，SVM的最终决策函数可以写成：

如果使用核方法（Kernel SVM），决策函数则变为：

六、举例说明

例子：二维线性分类问题

例子：非线性分类问题

七、总结：

支持向量机的参数学习过程主要依赖于求解一个凸优化问题，通过最大化分类间隔来提高泛化能力。这个过程包括：

1. 建立线性决策模型 w^T x + b = 0 并设置归一化约束；
2. 利用拉格朗日乘数将约束问题转化为对偶形式；
3. 通过凸优化方法求解最优拉格朗日乘数，并计算最终的 w^* 和 b^*；
4. 得到的决策函数不仅基于支持向量，还可以利用核技巧扩展到非线性分类。

这种参数学习方式确保了 SVM 能够找到一个最大化间隔的决策超平面，从而提高模型在未知数据上的鲁棒性和准确性。

八、附加：对偶问题

对偶问题是指在数学优化中，对于一个给定的“原始问题”（primal problem），可以构造出一个与之相关联的“对偶问题”（dual problem）。对偶问题与原始问题在数学上密切相关，通常具有以下特点和优势：

1. 基本概念

• 原始问题：
  优化问题的最初形式，比如最小化目标函数 f(x) 受到一组约束条件的限制。

• 对偶问题：
  通过引入拉格朗日乘数，将原始问题的约束融入目标函数中，进而构造一个新的优化问题。对偶问题的目标通常是最大化（或最小化）一个关于拉格朗日乘数的函数，这个函数称为对偶函数。

• 弱对偶性：
  对偶问题的最优值总是对原始问题最优值的一个下界（对于最小化问题）或上界（对于最大化问题）。

• 强对偶性：
  在某些条件下（例如凸优化问题满足 Slater 条件时），原始问题和对偶问题的最优值相等。强对偶性使得我们可以通过求解对偶问题来获得原始问题的最优解。

2. 特点

• 转换思路：
  对偶问题将原始问题从变量 xx 的优化转换为对拉格朗日乘数（对偶变量）的优化。这种转换有时能使问题更容易求解或更具结构性。

• 凸性：
  对于许多非凸问题，构造出的对偶问题往往是凸的，这使得优化过程更为稳定和高效。

• 提供界限：
  即使原始问题求解困难，对偶问题也能提供一个理论上的界限（下界或上界），这在理论分析和算法设计中非常有用。

• 敏感性分析：
  对偶变量通常反映了约束条件对最优解的“影子价格”，可以帮助理解约束对目标函数影响的敏感度。

3. 优势

• 简化计算：
  在一些情况下，对偶问题的形式比原始问题更简单、更容易求解。比如在支持向量机（SVM）中，通过对偶问题可以利用核函数来高效处理非线性分类问题。

• 分解问题：
  对偶问题有时可以分解为多个小问题，从而利用分布式或并行计算加速求解过程。

• 理论指导：
  对偶性理论为验证最优性提供了工具。如果找到的解满足原始和对偶问题之间的对偶间隙为零，就说明该解是最优的。

4. 举例说明

例子1：线性规划问题

例子2：支持向量机（SVM）

对偶问题是原始优化问题的另一种表达方式，通过引入拉格朗日乘数将约束融入目标函数，构造出一个无约束（或更简单）的优化问题。其特点包括能够提供界限、简化计算、分解问题以及进行敏感性分析。优势在于，在某些情况下，对偶问题比原始问题更容易求解，且理论上可以保证最优性（在强对偶性条件下）。通过线性规划和SVM的例子，我们可以看到对偶问题在实际优化问题中具有广泛应用。