支持向量机的原理和案例解析

一、支持向量机的核心目标：间隔最大化

支持向量机的核心思想是在两类数据中找到一个最优分离超平面，使得两类数据到超平面的“间隔”最大。我们从线性可分情况开始推导（非线性情况可通过核函数扩展）。

步骤1：定义分离超平面

在n维空间中，线性分离超平面的方程为：
$$\mathbf{w}\cdot \mathbf{x}+b=0\text{\hspace{1em}(1)}$$

• $\mathbf{w}=(w_1,w_2,...,w_n{)}^T$ 是超平面的法向量（决定超平面方向）；
• $b$ 是偏置项（决定超平面位置）；
• $\mathbf{x}=(x_1,x_2,...,x_n{)}^T$ 是样本点的特征向量。

对于二分类问题，假设样本标签为 y ∈ { + 1 , − 1 } y \in \{+1, -1\} y∈{+1,−1}（分别代表正、负类），则超平面需满足：

• 正类样本：$\mathbf{w}\cdot \mathbf{x}+b>0$（即 $y=+1$）；
• 负类样本：$\mathbf{w}\cdot \mathbf{x}+b<0$（即 $y=-1$）。

步骤2：定义样本到超平面的距离（间隔）

为衡量超平面的“分离能力”，需定义样本到超平面的距离。

• 函数间隔：对于样本 $({\mathbf{x}}_i,y_i)$，函数间隔为 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)$。

  • 意义：若值为正，说明分类正确（$y_i$ 与 $\mathbf{w}\cdot {\mathbf{x}}_i+b$ 同号）；绝对值越大，分类可信度越高。

• 几何间隔：函数间隔受 $\mathbf{w}$ 和 $b$ 缩放影响（例如 $\mathbf{w}\to 2\mathbf{w},b\to 2b$ 时超平面不变，但函数间隔翻倍），因此需归一化：
  $${\gamma }_i=\frac{y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)}{\Vert \mathbf{w}\Vert }\text{\hspace{1em}(2)}$$
  其中 $\Vert \mathbf{w}\Vert =\sqrt{\mathbf{w}\cdot \mathbf{w}}$ 是 $\mathbf{w}$ 的L2范数，几何间隔即样本到超平面的实际欧氏距离。

步骤3：间隔最大化的目标

最优超平面需满足：所有样本的几何间隔中最小的那个（即“最小间隔”）尽可能大。

设数据集的最小几何间隔为 $\gamma ={\min }_i{\gamma }_i$，目标是最大化 $\gamma$：
$$\underset{\mathbf{w},b}{\max }\gamma \text{s.t.}\frac{y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)}{\Vert \mathbf{w}\Vert }\ge \gamma (\forall i)\text{\hspace{1em}(3)}$$

步骤4：简化目标函数

由于超平面 $(\mathbf{w},b)$ 与 $(k\mathbf{w},kb)$（$k>0$）表示同一平面，可通过缩放将最小函数间隔归一化为1（即 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1$），此时最小几何间隔 $\gamma =\frac{1}{\Vert \mathbf{w}\Vert }$。

因此，最大化 $\gamma$ 等价于最小化 $\Vert \mathbf{w}\Vert$（或 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$，便于求导），目标函数简化为：
$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\text{s.t.}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1(\forall i)\text{\hspace{1em}(4)}$$

二、通过拉格朗日乘子法求解优化问题

式(4)是带不等式约束的凸优化问题，可通过拉格朗日乘子法转化为对偶问题求解。

步骤5：构建拉格朗日函数

引入拉格朗日乘子 ${\alpha }_i\ge 0$（对应每个约束条件），拉格朗日函数为：
$$\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^N{\alpha }_i\left[y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\right](5)$$

• 第一项是原目标函数；
• 第二项是约束条件的惩罚项（${\alpha }_i\ge 0$ 确保约束被满足）。

步骤6：求解对偶问题（KKT条件）

凸优化的对偶问题需满足KKT（Karush-Kuhn-Tucker）条件，即：

1. 原始可行性：$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1$；
2. 对偶可行性：${\alpha }_i\ge 0$；
3. 互补松弛：${\alpha }_i\left[y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\right]=0$（若 ${\alpha }_i>0$，则约束取等号，即 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$）；
4. 梯度为零：${\nabla }_{\mathbf{w}}\mathcal{L}=0$，${\nabla }_b\mathcal{L}=0$。

步骤7：求导化简（核心推导）

对 $\mathbf{w}$ 和 $b$ 求偏导并令其为0：

• 对 $\mathbf{w}$ 求导：
  $${\nabla }_{\mathbf{w}}\mathcal{L}=\mathbf{w}-\sum _{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i=0⟹\mathbf{w}=\sum _{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i(6)$$
  （$\mathbf{w}$ 可由样本的线性组合表示，系数为 ${\alpha }_i{y}_i$）

• 对 $b$ 求导：
  $${\nabla }_b\mathcal{L}=-\sum _{i=1}^N{\alpha }_i{y}_i=0⟹\sum _{i=1}^N{\alpha }_i{y}_i=0(7)$$

步骤8：对偶问题的目标函数

将式(6)代入拉格朗日函数(5)，化简对偶问题：

1. 展开 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$：
   $$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2=\frac{1}{2}\left(\sum _{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i\right)\cdot \left(\sum _{j=1}^N{\alpha }_j{y}_j{\mathbf{x}}_j\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)$$

2. 展开惩罚项：
   $$\sum _{i=1}^N{\alpha }_i\left[y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\right]=\sum _{i=1}^N{\alpha }_i{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i)+\sum _{i=1}^N{\alpha }_i{y}_{i}b-\sum _{i=1}^N{\alpha }_i$$
   由式(6)和(7)，第二项 $\sum {\alpha }_i{y}_{i}b=b\cdot 0=0$，第一项：
   $$\sum _{i=1}^N{\alpha }_i{y}_i(\mathbf{w}\cdot {\mathbf{x}}_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\right)=\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)$$

3. 合并化简拉格朗日函数：
   $$\mathcal{L}=\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)-\left[\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)-\sum _i{\alpha }_i\right]$$
   $$=-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+\sum _i{\alpha }_i$$

因此，对偶问题转化为最大化以下函数（ subject to 约束 ${\alpha }_i\ge 0$ 和 $\sum {\alpha }_i{y}_i=0$）：
$$\underset{\mathbf{\alpha }}{\max }\left(\sum _{i=1}^N{\alpha }_i-\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)\right)\text{\hspace{1em}(8)}$$

步骤9：求解超平面参数

通过对偶问题求出 $\mathbf{\alpha }$ 后，可计算：

• $\mathbf{w}$：由式(6)，$\mathbf{w}=\sum {\alpha }_i{y}_i{\mathbf{x}}_i$；
• $b$：由互补松弛条件，对 ${\alpha }_i>0$ 的样本（即支持向量），$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$，解得：
  $$b=y_i-\mathbf{w}\cdot {\mathbf{x}}_i=y_i-\sum _{j=1}^N{\alpha }_j{y}_j({\mathbf{x}}_j\cdot {\mathbf{x}}_i)\text{\hspace{1em}(9)}$$

步骤10：分类决策函数

对新样本 $\mathbf{x}$，分类结果由超平面的符号决定：
$$f(\mathbf{x})=\text{sign}(\mathbf{w}\cdot \mathbf{x}+b)=\text{sign}\left(\sum _{i=1}^N{\alpha }_i{y}_i({\mathbf{x}}_i\cdot \mathbf{x})+b\right)(10)$$

三、数学案例：线性可分数据的SVM求解

设二维数据集如下（线性可分）：

• 正类（$y=+1$）：${\mathbf{x}}_1=(3,3{)}^T$，${\mathbf{x}}_2=(4,3{)}^T$；
• 负类（$y=-1$）：${\mathbf{x}}_3=(1,1{)}^T$，${\mathbf{x}}_4=(2,1{)}^T$。

步骤1：直观分析

最优超平面应位于两类数据中间，假设支持向量为 ${\mathbf{x}}_1$（正类）和 ${\mathbf{x}}_3$（负类），即 ${\alpha }_1>0,{\alpha }_3>0$，${\alpha }_2={\alpha }_4=0$（非支持向量）。

步骤2：代入对偶问题约束

由 $\sum {\alpha }_i{y}_i=0$：
$${\alpha }_1\cdot 1+{\alpha }_3\cdot (-1)=0⟹{\alpha }_1={\alpha }_3\text{\hspace{1em}(11)}$$

步骤3：计算对偶目标函数

目标函数式(8)简化为（仅保留 ${\alpha }_1,{\alpha }_3$）：
$$W(\alpha )={\alpha }_1+{\alpha }_3-\frac{1}{2}\left[{\alpha }_1^2(x_1\cdot x_1)+{\alpha }_3^2(x_3\cdot x_3)+2{\alpha }_1{\alpha }_3{y}_1{y}_3(x_1\cdot x_3)\right]$$

代入数据：

• $x_1\cdot x_1=3^2+3^2=18$，$x_3\cdot x_3=1^2+1^2=2$；
• $x_1\cdot x_3=3\cdot 1+3\cdot 1=6$，$y_1{y}_3=1\cdot (-1)=-1$；
• 由 ${\alpha }_1={\alpha }_3=\alpha$，得：
  $$W(\alpha )=2\alpha -\frac{1}{2}\left[{\alpha }^2\cdot 18+{\alpha }^2\cdot 2+2{\alpha }^2\cdot (-1)\cdot 6\right]$$
  $$=2\alpha -\frac{1}{2}\left[20{\alpha }^2-12{\alpha }^2\right]=2\alpha -4{\alpha }^2$$

步骤4：最大化对偶函数

对 $W(\alpha )$ 求导并令其为0：
$$\frac{dW}{d\alpha }=2-8\alpha =0⟹\alpha =\frac{1}{4}$$
因此，${\alpha }_1={\alpha }_3=\frac{1}{4}$，${\alpha }_2={\alpha }_4=0$。

步骤5：计算 $\mathbf{w}$ 和 $b$

• $\mathbf{w}={\alpha }_1{y}_1{\mathbf{x}}_1+{\alpha }_3{y}_3{\mathbf{x}}_3=\frac{1}{4}\cdot 1\cdot (3,3)+\frac{1}{4}\cdot (-1)\cdot (1,1)=\left(\frac{3-1}{4},\frac{3-1}{4}\right)=(0.5,0.5)$；
• 由支持向量 ${\mathbf{x}}_1$ 求 $b$：$y_1(\mathbf{w}\cdot {\mathbf{x}}_1+b)=1$
  $$1\cdot (0.5\cdot 3+0.5\cdot 3+b)=1⟹3+b=1⟹b=-2$$

步骤6：验证超平面

超平面方程：$0.5x_1+0.5x_2-2=0$（即 $x_1+x_2=4$）。

• 正类样本 ${\mathbf{x}}_1$ 到超平面的距离：$\frac{|3+3-4|}{\sqrt{0.5^2+0.5^2}}=\sqrt{2}$；
• 负类样本 ${\mathbf{x}}_3$ 到超平面的距离：$\frac{|1+1-4|}{\sqrt{0.5^2+0.5^2}}=\sqrt{2}$，满足间隔最大化。

总结

SVM通过间隔最大化确定最优超平面，利用拉格朗日乘子法将原始问题转化为对偶问题，最终仅通过支持向量（${\alpha }_i>0$ 的样本）即可求解超平面参数。这一特性使其在高维空间中仍具高效性，且可通过核函数扩展到非线性分类场景。以下将对支持向量机（SVM）的核心公式原理进行逐步骤详细推导，并结合数学案例说明，确保每一步的逻辑和计算过程清晰可追溯。