线性可分支持向量机

线性可分支持向量机 (Hard Margin SVM)

1. 最大间隔算法 (Maximum Margin Algorithm)

最大间隔算法是线性可分支持向量机的基础，它旨在找到一个超平面，不仅能将两类数据完全分开，而且使分类间隔最大化。

1.1 输入与输出

• 输入： 训练数据集 $T=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),\dots ,({\mathbf{x}}_N,y_N)\}$。 其中：
  • ${\mathbf{x}}_i\in {\mathbb{R}}^n$ 是第 $i$ 个训练样本的 $n$ 维特征向量。
  • $y_i\in \{+1,-1\}$ 是第 $i$ 个训练样本的类别标签。
  • $N$ 是训练样本的总数量。
• 输出：
  • 能够实现最大几何间隔的分离超平面 $H^{\ast }:{\mathbf{w}}^{\ast }\cdot \mathbf{x}+b^{\ast }=0$。
  • 相应的分类决策函数 $f(\mathbf{x})=\text{sign}({\mathbf{w}}^{\ast }\cdot \mathbf{x}+b^{\ast })$。

1.2 优化问题构建 (原始问题 Primal Problem)

为了实现最大间隔，我们构建一个优化问题。其核心思想是最大化几何间隔，同时确保所有样本都被正确分类且满足函数间隔的约束。

• 回顾几何间隔： 对于样本 $({\mathbf{x}}_i,y_i)$，其几何间隔为 ${\gamma }_i=y_i\frac{\mathbf{w}\cdot {\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }$。 整个数据集的几何间隔为 $\gamma ={\min }_{i=1,\dots ,N}{\gamma }_i$。

• 标准化函数间隔： 如初识SVM所述，由于几何间隔具有尺度不变性，我们可以通过缩放 $\mathbf{w}$ 和 $b$ 来标准化函数间隔。我们选择固定最小函数间隔为 1： ${\min }_{i=1,\dots ,N}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$ 这意味着，对于所有样本 $i$： $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1$ （对于距离超平面最近的点，即支持向量，等号成立）。 在这种标准化下，最大化几何间隔 $\gamma =\frac{1}{\Vert \mathbf{w}\Vert }$ 等价于最小化 $\Vert \mathbf{w}\Vert$。

• 最终的原始优化问题 (Primal Problem)： 为了方便数学处理（特别是求导），我们通常最小化 $\Vert \mathbf{w}{\Vert }^2$ 或 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$。 ${\min }_{\mathbf{w},b}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$ $\text{s.t.}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1\text{对于所有 }i=1,\dots ,N$ 这个优化问题是一个凸二次规划 (Convex Quadratic Programming) 问题。它的目标函数是严格凸函数，约束是线性不等式，定义了凸可行域。因此，存在唯一的全局最优解 $({\mathbf{w}}^{\ast },b^{\ast })$。

2. 对偶问题与参数获得 (Dual Problem and Parameter Acquisition)

直接求解原始问题可能比较复杂，特别是当数据维度很高时。而将问题转化为其对偶问题 (Dual Problem) 常常能带来巨大的优势，包括：

1. 更高效的求解算法：对偶问题通常更容易求解。
2. 引入核函数 (Kernel Trick)：对偶问题中的内积形式 ${\mathbf{x}}_i\cdot {\mathbf{x}}_j$ 可以自然地替换为核函数，从而将线性模型扩展到非线性分类。
3. 稀疏性 (Sparsity)：对偶问题的解能自然地识别出支持向量。

2.1 广义拉格朗日函数 (Generalized Lagrangian Function)

我们将原始优化问题转化为无约束的优化问题，引入拉格朗日乘子 ${\alpha }_i\ge 0$ (对应每个约束)。 原始问题中的约束形式是 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\ge 0$。为了符合标准广义拉格朗日函数的 $g_i(\mathbf{x})\le 0$ 形式，我们将其改写为 $1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\le 0$。

广义拉格朗日函数 $L(\mathbf{w},b,\mathbf{\alpha })$ 定义为： $L(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\sum }_{i=1}^N{\alpha }_i[1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)]$ 其中 $\mathbf{\alpha }=({\alpha }_1,\dots ,{\alpha }_N{)}^T$ 是拉格朗日乘子向量，且 ${\alpha }_i\ge 0$。

2.2 原始问题的对偶形式

对偶问题是通过以下两步构建的：

步骤 1：内部极小化 (Primal Variable Minimization) 首先，我们对 $L(\mathbf{w},b,\mathbf{\alpha })$ 关于原始变量 $\mathbf{w}$ 和 $b$ 求偏导，并令其为零。这对应于求解 ${\min }_{\mathbf{w},b}L(\mathbf{w},b,\mathbf{\alpha })$。

• 对 $\mathbf{w}$ 求偏导： $\frac{\partial L}{\partial \mathbf{w}}=\frac{\partial }{\partial \mathbf{w}}\left(\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+{\sum }_{i=1}^N{\alpha }_i[1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)]\right)$ $=\frac{\partial }{\partial \mathbf{w}}\left(\frac{1}{2}{\mathbf{w}}^T\mathbf{w}-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i\right)$ 解释：

  • $\frac{\partial }{\partial \mathbf{w}}(\frac{1}{2}{\mathbf{w}}^T\mathbf{w})=\mathbf{w}$ （向量二次型的导数）。
  • $\frac{\partial }{\partial \mathbf{w}}({\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i)={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$ （线性项 ${\mathbf{c}}^T\mathbf{w}$ 对 $\mathbf{w}$ 的导数是 $\mathbf{c}$）。 令偏导数等于零向量： $\mathbf{w}-{\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i=0$ 由此得到 $\mathbf{w}$ 的表达式： ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$ 这个结果表明，==最优权重向量 ${\mathbf{w}}^{\ast }$ 可以表示为训练样本的线性组合，其中每个样本的系数是 ${\alpha }_i{y}_i$。==

• 对 $b$ 求偏导： $\frac{\partial L}{\partial b}=\frac{\partial }{\partial b}\left({\sum }_{i=1}^N{\alpha }_i[1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)]\right)$ $={\sum }_{i=1}^N{\alpha }_i(-y_i)$ 令偏导数等于零： $-{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 由此得到一个重要约束： ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 解释：这个条件表明，来自正类和负类的拉格朗日乘子加权和必须平衡，这是分类超平面能够存在的一个必要条件。

步骤 2：外部极大化 (Dual Problem Maximization) 将步骤 1 中得到的 ${\mathbf{w}}^{\ast }$ 表达式和 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 约束代入广义拉格朗日函数 $L(\mathbf{w},b,\mathbf{\alpha })$。 我们的目标是得到一个只依赖于 $\mathbf{\alpha }$ 的函数，然后对其进行最大化。

代入 ${\mathbf{w}}^{\ast }={\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j$： $L(\mathbf{\alpha })=\frac{1}{2}{\left({\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i\right)}^T\left({\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j\right)+{\sum }_{i=1}^N{\alpha }_i\left[1-y_i\left(\left({\sum }_{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j\right)\cdot {\mathbf{x}}_i+b\right)\right]$ 展开并简化： $L(\mathbf{\alpha })=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\alpha }_i{y}_i\left({\sum }_{j=1}^N{\alpha }_j{y}_j({\mathbf{x}}_j\cdot {\mathbf{x}}_i)+b\right)$ $=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)-b{\sum }_{i=1}^N{\alpha }_i{y}_i$ 根据 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 这一约束，最后一项 $b{\sum }_{i=1}^N{\alpha }_i{y}_i$ 变为 0。 合并第一项和第三项： $L(\mathbf{\alpha })=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i$

这就是对偶目标函数。因此，对偶优化问题 (Dual Problem) 为： ${\max }_{\mathbf{\alpha }}-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ ${\alpha }_i\ge 0\text{对于所有 }i=1,\dots ,N$ 这是一个凸二次规划问题，因为目标函数是关于 $\mathbf{\alpha }$ 的凹函数（或等价地，将其取负号，变为最小化一个凸函数），且约束是线性等式和线性不等式。存在成熟的算法可以求解它。

2.3 从对偶解获得原始参数 ${\mathbf{w}}^{\ast }$ 和 $b^{\ast }$

一旦我们通过求解对偶问题获得了最优的拉格朗日乘子 ${\mathbf{\alpha }}^{\ast }=({\alpha }_1^{\ast },\dots ,{\alpha }_N^{\ast }{)}^T$，我们就可以回溯来确定原始问题的最优参数 ${\mathbf{w}}^{\ast }$ 和 $b^{\ast }$。

• 获得 ${\mathbf{w}}^{\ast }$： 直接利用我们之前从 $\frac{\partial L}{\partial \mathbf{w}}=0$ 推导出的关系： ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$ 关键特性：支持向量 (Support Vectors) 根据KKT (Karush-Kuhn-Tucker) 条件，对于原始问题中的每个约束 $1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\le 0$，有互补松弛条件 (Complementary Slackness)： ${\alpha }_i^{\ast }[1-y_i({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_i+b^{\ast })]=0$ 这意味着：

  • 如果 ${\alpha }_i^{\ast }>0$，那么 $1-y_i({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_i+b^{\ast })=0$，即 $y_i({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_i+b^{\ast })=1$。这些样本点恰好位于间隔边界上，它们就是支持向量。
  • 如果 ${\alpha }_i^{\ast }=0$，那么 $1-y_i({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_i+b^{\ast })>0$，即 $y_i({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_i+b^{\ast })>1$。这些样本点位于间隔边界之外，它们不影响 ${\mathbf{w}}^{\ast }$ 的计算（因为对应的 ${\alpha }_i^{\ast }=0$）。 因此，${\mathbf{w}}^{\ast }$ 实际上是只由支持向量决定的，这使得模型具有稀疏性。

• 获得 $b^{\ast }$： 根据 KKT 条件，对于任何一个支持向量 $({\mathbf{x}}_j,y_j)$（即 ${\alpha }_j^{\ast }>0$ 的样本），我们有： $y_j({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_j+b^{\ast })=1$ 由此，我们可以解出 $b^{\ast }$： ${\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_j+b^{\ast }=y_j$ $b^{\ast }=y_j-{\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_j$ 将 ${\mathbf{w}}^{\ast }$ 的表达式代入： $b^{\ast }=y_j-{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i({\mathbf{x}}_i\cdot {\mathbf{x}}_j)$ 在实践中，为了提高数值稳定性，通常会取所有支持向量计算出的 $b^{\ast }$ 的平均值。

3. 对偶算法 (Dual Algorithm)

对偶算法是求解线性可分支持向量机的具体步骤。

3.1 算法流程

1. 构建对偶问题： 根据给定的训练数据集 $T=\{({\mathbf{x}}_i,y_i){\}}_{i=1}^N$，构建上述的凸二次规划对偶问题： ${\max }_{\mathbf{\alpha }}-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ ${\alpha }_i\ge 0\text{对于所有 }i=1,\dots ,N$

2. 求解对偶问题： 使用二次规划优化算法（例如，专门的二次规划求解器，或者更常用的 SMO (Sequential Minimal Optimization) 算法）来求解 $\mathbf{\alpha }$，得到最优解 ${\mathbf{\alpha }}^{\ast }$。

3. 计算最优参数 ${\mathbf{w}}^{\ast }$： 利用 ${\mathbf{\alpha }}^{\ast }$ 计算 ${\mathbf{w}}^{\ast }$: ${\mathbf{w}}^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i$

4. 计算最优偏置项 $b^{\ast }$： 选择任意一个满足 ${\alpha }_j^{\ast }>0$ 的支持向量 $({\mathbf{x}}_j,y_j)$，计算 $b^{\ast }$: $b^{\ast }=y_j-{\mathbf{w}}^{\ast }\cdot {\mathbf{x}}_j$ （实践中，通常选择多个支持向量的平均值，或通过更稳定的数值方法计算）。

5. 构建决策函数： 得到最终的分类决策函数： $f(\mathbf{x})=\text{sign}({\mathbf{w}}^{\ast }\cdot \mathbf{x}+b^{\ast })$ 分类超平面为 ${\mathbf{w}}^{\ast }\cdot \mathbf{x}+b^{\ast }=0$。

3.2 对偶算法的优势

1. 核技巧的自然引入 (The Kernel Trick)： 对偶问题中所有涉及到输入特征 ${\mathbf{x}}_i$ 的地方都以内积的形式 ${\mathbf{x}}_i\cdot {\mathbf{x}}_j$ 出现。 $\text{目标函数：}-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+{\sum }_{i=1}^N{\alpha }_i$ $\text{决策函数中的 }{\mathbf{w}}^{\ast }\cdot \mathbf{x}\text{项：}\left({\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i\right)\cdot \mathbf{x}={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i({\mathbf{x}}_i\cdot \mathbf{x})$ 这意味着我们可以用一个核函数 (Kernel Function) $K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 来替代内积 ${\mathbf{x}}_i\cdot {\mathbf{x}}_j$，而无需显式地将数据映射到高维特征空间。 $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i)\cdot \varphi ({\mathbf{x}}_j)$ 其中 $\varphi$ 是从原始空间到高维特征空间的映射。核技巧使得 SVM 能够高效地处理非线性分类问题，这是其最强大的特性之一。

2. 解的稀疏性： 如前所述，在最优解 ${\mathbf{\alpha }}^{\ast }$ 中，只有支持向量对应的 ${\alpha }_i^{\ast }$ 大于 0，其他非支持向量的 ${\alpha }_i^{\ast }$ 均为 0。 这意味着在计算 ${\mathbf{w}}^{\ast }$ 和决策函数时，我们只需要考虑那些 ${\alpha }_i^{\ast }>0$ 的支持向量。这大大减少了计算量，尤其是在大规模数据集上，因为支持向量通常只占训练数据的一小部分。

3. 计算复杂度： 对偶问题通常比原始问题更容易求解，特别是当样本数量 $N$ 不太大，但特征维度 $n$ 很高时。对偶问题的复杂度与 $N^2$ 相关（因为需要计算所有样本对的内积），而原始问题则与 $n$ 和 $N$ 都相关。当使用核函数时，原始特征空间维度 $n$ 可能无穷大，但对偶问题仍然可解，因为我们只依赖于核函数的计算。

通过将原始问题转化为对偶问题，支持向量机实现了从线性分类到非线性分类的强大扩展，并获得了高效和稀疏的求解能力。