笔记（六）机器学习（周志华）第6章 支持向量机SVM

1. 间隔与支持向量

训练样本集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . ( x m , y m ) } ， y i ∈ { − 1 , + 1 } D=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}，y_i\in\{-1,+1\} D={ (x1​,y1​),(x2​,y2​),...(xm​,ym​)}，yi​∈{ −1,+1}
分类学习的最基本想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。

能将训练样本划分开的平面可能有很多个，应该选择位于两类训练样本“正中间”的划分超平面，因为这个超平面的所产生的分类结果是最鲁棒的，泛化能力最强。
分离超平面对应于方程：
$$w^{T}x+b=0$$
其中$w=(w_1;w_2;...w_d)$为法向量，指向正类，决定了超平面的方向；b为位移项（截距），决定了超平面与原点的距离。可用(w,b)表示。
样本空间中任意一点到超平面(w,b)的距离可写为：
$$r=\frac{|w^{T}x+b|}{||w||}$$
复习：点$p(x_0,y_0)$到直线$ax+by+c=0$的距离：$$d=\frac{|a{x}_0+b{y}_0+c|}{\sqrt{a^2+b^2}}$$
假设超平面(w,b)能将训练样本正确分类，则有：
$$a=\{\begin{array}{l}{w}^T{x}_i+b>0,y_i=+1;\\ w^T{x}_i+b<0,y_i=-1\end{array}\text{\hspace{1em}(6.1)}$$
距离超平面最近的几个训练样本，被称为“支持向量”。
假设支持向量到超平面的距离为r（其他样本点肯定大于r），所以有：
$$\frac{|w^{T}x+b|}{||w||}\ge r$$
根据(6.1)对正负两类去绝对值得：
$$\{\begin{array}{r}\frac{w^T{x}_i+b}{||w||}\ge r,y_i=+1;\\ \frac{w^T{x}_i+b}{||w||}\le r,y_i=-1\end{array}$$
两边同时除以r得：
$$\begin{gathered} \{\begin{array}{r}{w}_r^T{x}_i+b_r\ge +1,y_i=+1;\\ w_r^T{x}_i+b_r\le -1,y_i=-1\end{array} \\ 其中w_r=\frac{w}{||w||r},b_r=\frac{b}{||w||r} \end{gathered}$$
线性缩放，例如2x+2y=0与x+y=0是同一条直线。
$w_r和b_r$仍是直线的法向量和截距，用w表示$w_r$,b表示$br$
所以得到：
$$\{\begin{array}{r}{w}^T{x}_i+b\ge +1,y_i=+1;\\ w^T{x}_i+b\le -1,y_i=-1\end{array}\text{\hspace{1em}(6.3)}$$
合并：$y_i(w^{T}x+b)\ge 1$
支持向量使等号成立。即 $|w^{T}x+b|=1$

所以，间隔为两个异类支持向量到超平面的距离之和为：
$$\gamma =2\ast \frac{|w^{T}x+b|}{||w||}=\frac{2}{||w||}\text{\hspace{1em}(6.4)}$$

想要找到“最大间隔”的划分超平面，就是要找满足(6.3)中约束的参数w和b，使得$\gamma$最大，即：
$$\begin{array}{rl}& \underset{w,b}{\max }\frac{2}{||w||}\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m.\end{array}\text{\hspace{1em}(6.5)}$$
最大化间隔就是使$||w||$最小化，转换为求解凸二次规划问题，即最小化$||w|{|}^2$，乘以$\frac{1}{2}$为了求导方便，于是重写(6.5)式：
$$\begin{array}{rl}& \underset{w,b}{\min }\frac{1}{2}||w|{|}^2\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m.\end{array}\text{\hspace{1em}(6.6)}$$
这就是支持向量机（SVM）的基本型。

2. 对偶问题

2.1 对偶问题

我们希望求解(6.6)得到大间隔划分超平面所对应的模型
$$f(x)=w^{T}x+b\text{\hspace{1em}(6.7)}$$
其中w和b是模型参数,。（6.6）是一个凸二次规划问题，可以直接用现成的优化计算包求解，这里是使用拉格朗日乘子法得到其对偶问题。具体来说，

• 1、对(6.6)的每条约束添加拉格朗日乘子${\alpha }_i\ge 0$，该问题的拉格朗日函数可写为：
  $$L(w,,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))\text{\hspace{1em}(6.8)}$$
  其中$\alpha =({\alpha }_1;{\alpha }_2;...;{\alpha }_m)$。
• 2、令$L(w,b,\alpha )$对w和b的偏导为0，得：
  w = ∑ i = 1 m α i y