支持向量机,support vector machine,是一种二分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。因此这里需要一些凸优化的概念,可以参见我之前的博客**[REFERENCES 1]**。

SVM是干啥的

对于下面这个二分类问题可以有很多划分方式,如(b)(c),但是在这两个中最优的划分方式是(b),因为其泛化能力最优,而SVM就是要确定一个这样的划分线,使得两个类别之间距离最大。这两个虚线之间的面就是“决策面”,这两个虚线之间的距离就是“分类间隔”,因此SVM是要找到一个最大间隔的决策面,另外虚线穿过的点上的数据叫做“支持向量”。

DA623515-0B0D-4BB0-BB7C-672886F254F2

从表面上看,我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。

数学建模

一个优化问题通常有两大基本要素:

  1. 目标函数,也就是希望什么东西的什么指标达到最好。在SVM中目标函数是分类间隔。
  2. 优化对象,你期望通过改变哪些因素来使得你的目标函数达到最优。在SVM中优化对象是决策面。

决策面

对于22维数据,他的决策面通常是一个线,即11维的,对应到nn维空间中,决策面就变成了(n1)(n-1)维的一个超平面了。因此这里以22维数据做为例子,其决策面(线)公式如下:

(2.1)y=ax+by = ax + b \tag{2.1}

我们将xx轴变成x1x_1,将yy轴变成x2x_2,那么公式2.1就变为了:

\begin{align} x_2 = ax_1 + b \notag \\ ax_1 + (-1)x_2 + b=0 \tag{2.2} \\ \begin{bmatrix} a & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + b = 0 \tag{2.3} \end{align}

通过公式2.3我们就可以引入向量了,并且我们可以将其扩展到nn维向量中去,最终我们可以得到:

(2.4)wTx+b=0\boldsymbol{w}^T\boldsymbol{x} + b =0 \tag{2.4}

这里w\boldsymbol{w}决定了决策面的方向,bb为位移项,决定了决策面与原点之间的距离,因此决策面(超平面)的划分可以由w\boldsymbol{w}bb共同决定。

分类间隔(目标函数)

间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍,如下图所示:

image-20180819115600192

对应到二维坐标中,决策面就是上图的AA,分类间隔就是WW,根据点到直线的距离我们可以获得分类间隔的一半:

\begin{align} d = \frac{|\boldsymbol{w}^T\boldsymbol{x} + b|}{||\boldsymbol{w}||} \tag{2.5} \end{align}

其中x\boldsymbol{x}就是支持向量的坐标(虚线穿过的样本点),w||\boldsymbol{w}||是向量w\boldsymbol{w}的模,表示空间中向量的长度。因此追求WW的最大化,就是求dd的最大化,公式2.5就是目标函数的数学形式。

约束条件

上述公式虽然是目标函数,但是还是有几点非常麻烦的约束条件:

  • w\boldsymbol{w}:并不是所有w\boldsymbol{w}都能够实现正确分类。这个很好理解,w\boldsymbol{w}控制的是决策面的方向,可以理解为他改变就以为决策面在空间中旋转,因此对于样本来说并不是旋转到哪里都可以完全正确的分类的。
  • bb:如果实现了正确的分类,还需要确保决策面是否处于两个分类的支持向量的中间。而bb就是所谓的截距,因此bb也不能随意的优化。
  • x\boldsymbol{x}:即便取到了合适的方向和截距,公式2.5中的x\boldsymbol{x}是支持向量对应的样本点。

因此这里需要用到一些小技巧来将约束条件和目标函数融合到一个不等式之中。

因为SVM是解决二分类问题的,因此我们可以将样本分为正样本(positive samples)和负样本(negative samples),我们为每一个样本点xi\boldsymbol{x}_i加上一个类别标签yiy_i

(2.6){wTxi+b>0,yi=+1;wTxi+b<0,yi=1.\left \{ \begin{array}{lr} \boldsymbol{w}^T\boldsymbol{x}_i + b \gt 0, \quad y_i = +1; \\ \boldsymbol{w}^T\boldsymbol{x}_i + b \lt 0, \quad y_i = -1. \end{array} \right . \tag{2.6}

对于上式对应到上图的例子中

(2.7)yi={+1blue points1red pointsy_i = \left \{ \begin{array}{lr} +1 \quad blue\ points \\ -1 \quad red\ points \end{array} \right . \tag{2.7}

假设能正确分类,即决策面正好处于间隔区域的中轴上,并且对应分类的支持向量到决策面的距离为dd时,公式2.6可以写为

\begin{align} \left \{ \begin{array}{lr} \frac{\boldsymbol{w}^T\boldsymbol{x}_i + b}{||\boldsymbol{w}||} \ge d, \quad y_i = +1 \\ \frac{\boldsymbol{w}^T\boldsymbol{x}_i + b}{||\boldsymbol{w}||} \le -d, \quad y_i = -1 \end{array} \right . \tag{2.8} \end{align}

同时除以一个dd我们可以最终得到

\begin{align} \left \{ \begin{array}{lr} \boldsymbol{w}^T_d\boldsymbol{x}_i + b_d \ge 1, \quad y_i = +1 \\ \boldsymbol{w}^T_d\boldsymbol{x}_i + b_d \le -1, \quad y_i = -1 \end{array} \right . \tag{2.9} \end{align}

其中,$$\begin{align} \boldsymbol{w}_d = \frac{\boldsymbol{w}}{||\boldsymbol{w}||d} \end{align}$$,$$\begin{align} b_d = \frac{b}{||\boldsymbol{w}||d} \end{align}$$。在二维视角下,w\boldsymbol{w}就是斜率,bb就是截距,因此wdTx+bd=0\boldsymbol{w}^T_d\boldsymbol{x} + b_d = 0wTx+b=0\boldsymbol{w}^T\boldsymbol{x} + b = 0其实是一条直线,因此我们就可以把下角标去掉,变为

(2.10){wTxi+b1,yi=+1wTxi+b1,yi=1\left \{ \begin{array}{lr} \boldsymbol{w}^T\boldsymbol{x}_i + b \ge 1, \quad y_i = +1 \\ \boldsymbol{w}^T\boldsymbol{x}_i + b \le -1, \quad y_i = -1 \end{array} \right . \tag{2.10}

公式2.10可以认为是SVM优化条件的约束条件的基本描述。

线性SVM优化问题基本描述

公式2.10的等号条件是在当xi\boldsymbol{x}_i在为支持向量的时候成立的,因此对于公式2.5我们可以简化为$$\begin{align} d = \frac{|\boldsymbol{w}^T\boldsymbol{x} + b|}{||\boldsymbol{w}||} = \frac{1}{||\boldsymbol{w}||}\end{align}$$,因为dd也是恰好是支持向量到决策面的距离,因此$$\begin{align} W = 2d = \frac{2}{||\boldsymbol{w}||} \end{align}$$。我们最终的目标是最大化WW,也就是最大化w1||\boldsymbol{w}||^{-1},等效于最小化w2||\boldsymbol{w}||^2,数学公式描述为

\begin{align} \mathop{\min}_{\boldsymbol{w}, b} \ \ \frac{1}{2} \|\boldsymbol{w} \|^2 \\ \mathrm{s.t.} \ \ y_i(\boldsymbol{w}^T\boldsymbol{x} + b) \ge 1, \quad i = 1, 2, \dots, m. \end{align} \tag{2.11}

其中mm是样本总数,s.t.\mathrm{s.t.}表示subject to(服从某某条件),公式2.11是一个不等式约束条件下的二次型函数优化问题,也是支持向量机的基本数学模型。

(未完待续...)

REFERENCES

  1. 凸优化问题
  2. 零基础学SVM—Support Vector Machine(一)
  3. 支持向量机通俗导论(理解SVM的三层境界)
  4. 机器学习 周志强