学习支持向量机。

函数间隔和几何间隔

给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

$$w^* \cdot x+b^* =0 $$

以及相应的分类决策函数

$$f(x) = sign (w^* \cdot x + b^*)$$

称为线性可分支持向量机。

对于给定训练集合T和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x _i,y_i)$的函数间隔为

$$\hat\gamma_i = y_i(w \cdot x_i + b)$$

定义超平面$(w,b)$关于训练数据集T的函数间隔为超平面$(w,b)$关于T中所有样本点$(x_i,y_i)$的函数间隔之最小值，

$$\hat\gamma = \min_{i=1,…,N}\hat\gamma_i$$

对于给定的训练数据集和超平面$(w,b)$，定义超平面$(w,b)关于$样本$(x_i,y_i)$的几何间隔为

$$\hat\gamma_i = y_i(\frac w{||w||} \cdot x_i + \frac b{||w||})$$

定义超平面$(w,b)$关于训练数据集T的几何间隔为超平面$(w,b)$关于T中所有样本点$(x_i,y_i)$的几何间隔之最小值

$$\gamma = \min_{i=1,…,N}\gamma_i$$

从而得到几何间隔和函数间隔的关系:

$$\gamma = \frac{\hat\gamma_i}{||w||}$$

间隔最大化

对数据集合找到几何间隔最大的超平面意味着以充分大的确信度来对训练数据进行分类。

最大化超平面可表示为：

$$\max_{w,b} \quad {\gamma}\\
s.t.\quad y_i(\frac w{||w||} \cdot x_i + \frac b{||w||}) \ge \gamma,\quad i=1,…,N$$

即最大化超平面$(w,b)$关于训练结合的间隔$\gamma$，约束条件表示的超平面$(w,b)$关于每个训练样本点的几何间隔至少为$\gamma$。

而函数间隔对于上述公式并没有影响，假设按比例改变为$\lambda w$和$\lambda b$，那么函数间隔改变为$\lambda \hat\gamma$

改变为相应的函数距离，如下

$$\max_{w,b} \quad \frac{\hat\gamma}{||w||} \\
s.t.\quad y_i(w \cdot x_i + b) \ge \hat\gamma,\quad i=1,…,N$$

由于分母和分子同时拥有$\lambda$，因此成比例改变并不会对函数间隔产生影响，从而对目标函数的优化也没有影响。

令$\hat\gamma$=1，代入上式，最大化$\frac1{||w||}$等价于最小化$\frac12||w||$，从而得到线性可分支持向量机学习的最优化问题

$$min_{w,b}\quad \frac12{||w||}^2 \\
s.t.\quad y_i(w\cdot x_i + b) - 1 \ge 0, \quad i=1,2,…,N$$

这是一个凸二次规划问题。

支持向量

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector），即

$$y_i(w\cdot x_i+b) =1$$

对于y=+1的正例来说，支持向量在超平面

$$H_1:w\cdot x + b= 1$$

对于y=-1的负例来说，支持向量在超平面

$$H_2:w\cdot x + b = -1$$

如图中， H1和H2平行，之间形成一条长带，其宽度为$\frac 2 {||w||}$。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用，如果移动支持向量改变所求的解，但是如果在间隔边界（H1和H2）以外移动其他实例点，解都不会发生改变。

对偶算法

为了求解线性可分支持向量机的最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到最优解。

定义拉格朗日函数：

$$L(w,b,\alpha) = \frac 1 2 {||w||}^2 - \sum_{i=0}^n \alpha_i y_i(w\cdot x_i + b) + \sum_{i=1}^N\alpha_i$$

其中，$\alpha = (\alpha_1, \alpha_2,…,\alpha_N)^T$为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题需要先求$L(w,b,\alpha)$对(w,b)求极小，再对$\alpha$求极大：

$$\max_\alpha \min_{w,b} L(w,b,\alpha)$$

• $\min_{w,b} L(w,b,\alpha)$

分别对$w,b,\alpha$求偏导数，并令其等于0，将结果带入原公式中即得

$$\min_{w,b} L(w,b,\alpha) = -\frac 1 2 \sum_{i-=1}^N \sum_{j-=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i$$

• 求$\min_{w,b} L(w, b, \alpha)$对$\alpha$的极大

$$\max_\alpha -\frac 1 2 \sum_{i-=1}^N \sum_{j-=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i \\
s.t.\quad \sum_{i=1}^N\alpha_i y_i=0, \quad \alpha_i > 0,i=1,2,…,N$$

等价于：

$$\min_\alpha \frac 1 2 \sum_{i-=1}^N \sum_{j-=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\
s.t.\quad \sum_{i=1}^N\alpha_i y_i=0, \quad \alpha_i > 0, i=1,2,…,N$$

线性可分支持向量机学习算法

(1)构造并求解约束最优化问题

$$\min_\alpha \frac 1 2 \sum_{i-=1}^N \sum_{j-=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i\\
s.t.\quad \sum_{i=1}^N\alpha_i y_i=0, \quad \alpha_i > 0, i=1,2,…,N$$

(2)计算

$$w^* = \sum_{i=1}^N \alpha_i^* y_i x_i$$

并选择$\alpha^*$的一个正分量$\alpha_j^*$，计算

$$b^* = y_i - \sum_{i=1}^N \alpha_i^*y_i(x_i \cdot x_j)$$

(3)求得分离超平面

$$w^* \cdot x + b^* = 0$$

分类决策函数

$$f(x) = sign(w^* \cdot x + b^*)$$