SVM 的推导

本文最后更新于：2024年1月14日晚上

SVM（Support Vector Machine，支持向量机）是一个线性分类器，是最经典的分类算法，其核心目标就是找到最大间隔超平面。本文记录SVM的推导过程。

概述

SVM就是一个分类器，只是相对于传统的线性分类器，它添加了一个支持向量的概念。

考虑一个分类任务

从图片上解释，对于一组数据，SVM在使用直线的同时要求数据点距离这条直线的最小距离最大，也就是说分类器和数据之间要有足够大的“间隔”。这样做的好处是很明显的，越大的“间隔”代表了更大的转圜空间，在得到新的数据之后更容易将其正确分类。

而SVM的工作就是求解这个最大间隔，也就是最优化问题。对于线性可分的数据，可以直接套用线性规划的知识进行推导，但如果数据线性不可分，就需要核函数进行数据升维，进行超平面分类。

目标函数

SVM是一个线性分类器，SVM的目标就是找到最大间隔超平面。

定义任意的超平面函数为：

$$
\bf{w}^{T} \bf{x}+b=0
$$

二维空间点$(x,y)$到直线$Ax+By+C=0$的距离为：

$$ \frac{|A x+B y+C|}{\sqrt{A^{2}+B^{2}}} $$

扩展到$k$维空间后，点$X=(x_1,x_2,\dots,x_k)$到超平面$w^{T} x+b=0$距离为：

$$
\frac{\left|\bf{w}^{T} \bf{x}+b\right|}{|\bf{w}|}
$$

其中：

$$
|\bf{w}|=\sqrt{w_{1}^{2}+\ldots w_{n}^{2}}
$$

我们希望这个超平面可以区分不同两类数据特征，这个分类决策函数就是：

$$
f(x)=\operatorname{sign}\left(\bf{w}^T\bf{x}+b\right)
$$

我们的数据为$({{\bf{x}}_i},{y_i}),i \in \{ 1,2, \ldots ,n\},y_i \in \{1,-1\} $，定义点$({{\bf{x}}_i},{y_i}) $到超平面的函数距离$\hat{\gamma}_{i}$：

$$ \hat{\gamma}_{i}=y_{i}\left(\bf{w} \cdot \bf{x}_{i}+b\right) $$

而我们的目标是找到可以最大化数据到点几何距离的超平面，将几何距离用${\gamma}_{i}$表示，为：

$$ \gamma_{i}=|\frac{\bf{w}}{\|\bf{w}\|} \cdot \bf{x}_{i}+\frac{b}{\|\bf{w}\|}|=\frac{|\bf{w}^T\bf{x}_i+b|}{\|\bf{w}\|}=\frac{y_{i}\left(\bf{w} \cdot \bf{x}_{i}+b\right)}{\|\bf{w}\|}=\frac{\hat{\gamma}_{i}}{\|\bf{w}\|} $$

因此优化函数为：

$$ \begin{array}{*{20}{l}} {\mathop {\max }\limits_{{\bf{w}},b} }&\gamma \\ {{\rm{ s}}{\rm{.t}}{\rm{. }}}&{{y_i}\left( {\frac{{\bf{w}}}{{{||\bf{w}||}}} \cdot {x_i} + \frac{b}{{{||\bf{w}||}}}} \right) \ge \gamma ,\quad i = 1,2, \cdots ,n} \end{array} $$

根据已有结论可以将优化函数转化为：

$$ \begin{array}{*{20}{l}} {\mathop {\max }\limits_{{\bf{w}},b} }&{\frac{{{{\hat \gamma }_i}}}{{{||\bf{w}||}}}}\\ {{\rm{s}}.{\rm{t}}.}&{{y_i}\left( {{\bf{w}} \cdot {x_i} + b} \right) \ge {{\hat \gamma }_i},\quad i = 1,2, \cdots ,n} \end{array} $$ - 事实上函数间隔${\hat \gamma }$并不影响最优化问题的解，假设将$\bf{w}$和$b$成倍的改变为$a\bf{w}，ab$，那么函数间隔也会相应变成$a{\hat \gamma }$，因此为简便，我们取 ${\hat \gamma }=1$，因此优化函数为最大化$1/||\bf{w}||$，这等价于最小化$||\bf{w}||$，考虑到求导方便，我们最小化$1/2||\bf{w}||^2$ - 优化函数最终为： $$ \begin{array}{*{20}{l}} {\mathop {\min }\limits_{{\bf{w}},b} }&{\frac{1}{2}||{\bf{w}}|{|^2}}\\ {{\rm{s}}.{\rm{t}}.}&{{y_i}\left( {{\bf{w}} \cdot {{\bf{x}}_i} + b} \right) - 1 \ge 0,\quad i = 1,2, \cdots ,n} \end{array} $$

拉格朗日对偶求极值

写成拉格朗日优化的格式：

$$ \begin{array}{*{20}{l}} {\mathop {\min }\limits_{{\bf{w}},b} }&{\frac{1}{2}||{\bf{w}}|{|^2}}\\ {{\rm{s}}.{\rm{t}}.}&1-{{y_i}\left( {{\bf{w}} \cdot {{\bf{x}}_i} + b} \right) \le 0,\quad i = 1,2, \cdots ,n} \end{array} $$

拉格朗日方程：

$$ L({\bf{w}},b,{\bf{\alpha }}) = \frac{1}{2}||{\bf{w}}|{|^2} + \sum\limits_{i = 1}^n {{\alpha _i}(1 - {y_i}\left( {{\bf{w}} \cdot {{\bf{x}}_i} + b} \right)} ) $$

原始问题为凸优化问题，我们按照KKT条件求解该问题的对偶问题，即可根据强对偶条件获得原始问题的解
对偶问题为：

$$ \mathop {max}\limits_{\bf{\alpha }} D({\bf{\alpha }}) = \mathop {max}\limits_{\bf{\alpha }} \mathop {\min }\limits_{{\bf{w}},b} L({\bf{w}},b,{\bf{\alpha }}) $$

先求最小化极值问题 $\mathop {\min }\limits_{{\bf{w}},b} L({\bf{w}},b,{\bf{\alpha }})$：

$$ \left\{ {\begin{array}{*{20}{c}} {\frac{{\partial {\rm{L}}}}{{\partial {\bf{w}}}} = 0}\\ {\frac{{\partial {\rm{L}}}}{{\partial b}} = 0} \end{array}} \right. $$

解得：

$$ \left\{ {\begin{array}{*{20}{c}} {{\bf{w}} = \sum\limits_{i = 1}^n {{\alpha _i}{y_i}{{\bf{x}}_i}} }\\ {\sum\limits_{i = 1}^n {{\alpha _i}{y_i} = 0} } \end{array}} \right. $$

带入$L({\bf{w}},b,{\bf{\alpha }})$得：

$$ \begin{aligned} L(\bf{w}, b, \bf{\alpha}) &=\frac{1}{2}\|\bf{w}\|^{2}+\sum_{i=1}^{n} \alpha_{i}\left[1-y_{i}\left(\bf{w}^{T} x_{i}+b\right)\right] \\ &=\frac{1}{2} \bf{w}^{T} \bf{w}-\bf{w}^{T} \sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}-b \sum_{i=1}^{n} \alpha_{i} y_{i}+\sum_{i=1}^{n} \alpha_{i} \\ &=\frac{1}{2} \bf{w}^{T} \sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}-\bf{w}^{T^{\prime}} \sum_{i=1}^{n} \alpha_{i} x_{i} y_{i}-b * 0+\sum_{i=1}^{n} \alpha_{i} \\ &=\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2}\left(\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}\right)^{T} \sum_{i=1}^{n} \alpha_{i} y_{i} x_{i} \\ &=\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} \end{aligned} $$

此时我们需要解决的优化问题是：

$$ \begin{array}{*{20}{c}} {\mathop {\max }\limits_{\bf{\alpha }} \sum\limits_{i = 1}^n {{\alpha _i}} - \frac{1}{2}\sum\limits_{i,j = 1}^n {{\alpha _i}} {\alpha _j}{y_i}{y_j}{\bf{x}}_i^T{{\bf{x}}_j}}\\ {\qquad \begin{array}{*{20}{c}} {{\rm{ s}}{\rm{.t}}{\rm{. }}{\alpha _i} \ge 0,\quad i = 1,2, \ldots ,n}\\ {\sum\limits_{i = 1}^n {{\alpha _i}} {y_i} = 0} \end{array}} \end{array} $$

可以看到通过拉格朗日对偶，我们将原始拉格朗日方程$k+1+n$个未知数、$n$个复杂不等式约束条件的优化问题转换为了$n$个未知数，1个等式约束的问题，当然满足KKT条件是前提
对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到$\bf{α}$，再根据$\bf{α}$，我们就可以求解出$\bf{w}$和$b$，进而求得我们最初的目的：找到超平面，即"决策平面"。