笔记（六）机器学习（周志华）第6章 支持向量机SVM_考虑一个在两维特征空间的二分类问题。训练集包括8个样本

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 = { w T x i + b > 0 , y i = + 1 ; w T x i + b < 0 , y i = − 1 (6.1) a =

$$\begin{cases} w^Tx_i+b>0, y_i=+1;\\ w^Tx_i+b<0, y_i=-1 \end{cases}$$ \tag{6.1} a={wTxi​+b>0,yi​=+1;wTxi​+b<0,yi​=−1​(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$最大，即：
max ⁡ w , b    2 ∣ ∣ w ∣ ∣ s . t .      y i ( w T x i + b ) ≥ 1 ,    i = 1 , 2 , . . . , m . (6.5)

$$\begin{aligned} &\max_{w,b} \;\frac{2}{||w||} \\ &s.t.\;\;y_i(w^Tx_i+b)\ge1, \;i=1,2,...,m. \tag{6.5} \end{aligned}$$ ​w,bmax​∣∣w∣∣2​s.t.yi​(wTxi​+b)≥1,i=1,2,...,m.​(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=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i\text{\hspace{1em}(6.9)}$$
  $$0=\sum _{i=1}^m{\alpha }_i{y}_i\text{\hspace{1em}(6.10)}$$
  目标函数：${\min }_{w,b}L(w,b,\alpha )$，因为$y_i(w^T{x}_i+b)\ge 1$，所以，$1-y_i(w^T{x}_i+b)\le 0，{\alpha }_i\ge 0$，所以，${\alpha }_i$增大，$L(w,b,\alpha )$变小。
  目标函数变为：$$\underset{w,b}{\min }\underset{{\alpha }_i\ge 0}{\max }L(w,b,\alpha )$$
  由于这个不好求解，一般我们将最小和最大的位置交换一下（需满足KKT条件） ，变成原问题的对偶问题：
  $$\underset{{\alpha }_i\ge 0}{\max }\underset{w,b}{\min }L(w,b,\alpha )$$
• 3、将上面的偏导结果带入(6.8)得到(6.6)的对偶问题：
  将(6.9)带入(6.8)，即可消去$L(w,,b,\alpha )$中的w和b，再考虑(6.10)的约束，得到(6.6)的对偶问题：
  $$\begin{array}{rl}& \underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )，即\\ & \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & {\alpha }_i\ge 0,i=1,2,...,m.\end{array}\text{\hspace{1em}(6.11)}$$
  解出$\alpha$后，求出w和b即可得到模型：
  $$\begin{array}{rl}f(x)& =w^{T}x+b\\ & =\sum _{i=1}^m{\alpha }_i{y}_i{x}_i^{T}x+b\end{array}\text{\hspace{1em}(6.12)}$$

2.2 KKT

从对偶问题(6.11)解出的${\alpha }_i$是(6.8)中的拉格朗日乘子，它恰对应着训练样本$(x_i,y_i)$。注意(6.6)中有不等式约束，因此上述过程需满足KKT条件，即要求：
{ α i ≥ 0 ; y i f ( x i ) − 1 ≥ 0 ; α i ( y i f ( x i ) − 1 ) = 0 \left\{

$$\begin{aligned} &\alpha_i\ge0;\\ &y_if(x_i)-1 \ge 0;\\ &\alpha_i(y_if(x_i)-1)=0 \end{aligned}$$ \right. ⎩⎪⎨⎪⎧​​αi​≥0;yi​f(xi​)−1≥0;αi​(yi​f(xi​)−1)=0​
于是，对任意训练样本$(x_i,y_i)$总有${\alpha }_i=0或y_{i}f(x_i)=1$。

• 若${\alpha }_i=0$，则该样本不会出现在(6.12)的求和中出现，也不会对f(x)有任何影响
• 若${\alpha }_i>0$，则必有$y_{i}f(x_i)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。
  由此得到支持向量的重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
  支持向量机：强调了此类学习器的关键是如何从支持向量构建出解；同时也暗示着其复杂度只要与支持向量的数目有关。

2.3 SMO（序列最小优化算法）

  可以发现对偶问题式（6.11）是一个二次规划问题，可以使用通用的二次规划算法求解，但问题规模正比于样本数，会造成很大的开销。为了避免这个障碍，可以使用高效的SMO（Sequential Minimal Optimization）算法。
  SMO算法的中心思想：每次选出两个$\alpha$进行优化（之所以是两个是因为$\alpha$的约束条件决定了其与标签乘积的累加等于0，因此必须一次同时优化两个，否则就会破坏约束条件），然后固定其他的$\alpha$值。重复此过程，直到达到某个终止条件程序退出并得到我们需要的优化结果。
在参数初始化后，SMO不断执行如下两个步骤直至收敛：

• 选取一对需要更新的变量${\alpha }_i$和${\alpha }_j$；
• 固定${\alpha }_i$和${\alpha }_j$以外的参数，求解(6.11)获得更新后的${\alpha }_i$和${\alpha }_j$。

SMO具体过程：
强推：Python3《机器学习实战》学习笔记（八）：支持向量机原理篇之手撕线性SVM

如何选取${\alpha }_i$和${\alpha }_j$：

  注意到只要选取的 ${\alpha }_i$和${\alpha }_j$中有一个不满足KKT条件，目标函数迭代后会增大。而且KKT条件违背的程度越大，则变量更新后导致目标函数增幅就越大。
  因此，SMO算法先选取一个违背KKT条件程度最大的变量${\alpha }_i$，然后再选一个使目标函数增长最快的变量${\alpha }_j$，但由于找出${\alpha }_j$的开销较大，所以SMO算法采用了一个启发式：使选取的两变量对应的样本之间间隔最大。这样两个变量有很大的差别，与选取两个相似变量相比，这种方法能为目标函数带来更大的变化，从而更快搜索到全局最大值。
  SMO算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑${\alpha }_i$和${\alpha }_j$时，(6.11)的约束可以重写为：
$${\alpha }_i{y}_i+{\alpha }_j{y}_j=c,{\alpha }_i\ge 0,{\alpha }_j\ge 0$$
其中
$$c=-\sum _{k\ne i,j}{\alpha }_k{y}_k$$
c是使${\sum }_{i=1}^m{\alpha }_i{y}_i=0$成立的常数，用${\alpha }_i{y}_i+{\alpha }_j{y}_j=c$，消去（6.11）中的变量${\alpha }_j$，（${\alpha }_j=(c-{\alpha }_i{y}_i)÷y_j$）则得到一个关于${\alpha }_i$的单变量二次规划问题，仅有的约束是${\alpha }_i\ge 0$。这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的${\alpha }_i$和${\alpha }_j$。

如何求出w和b？

w：根据公式(6.9)
b：对于任意支持向量$(x_s,y_s)$都有$y_{s}f(x_s)=1$，即
$$y_s(\sum _{i\in S}{\alpha }_i{y}_i{x}_i^T{x}_s+b)=1\text{\hspace{1em}(6.17)}$$
得到：$$b=\frac{1}{y_s}-\sum _{i\in S}{\alpha }_i{y}_i{x}_i^T{x}_s$$
其中 S = { i ∣ α i ≥ 0 ,    i = 1 , 2 , . . . , m } S=\{i|\alpha_i\ge0,\;i=1,2,...,m\} S={i∣αi​≥0,i=1,2,...,m}为所有支持向量的下标集。理论上，可选取任意支持向量并通过求解(6.17)获得b，但现实任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值
$$b=\frac{1}{|S|}\sum _{s\in S}(\frac{1}{y_s}-\sum _{i\in S}{\alpha }_i{y}_i{x}_i^T{x}_s)$$

3. 核函数

  前面的讨论我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。
  解决方法：将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。幸运的是，如果原始空间是有限维，即属性数有限，那就一定存在一个高维特征空间使样本线性可分。
  令$\varphi (x)$表示将$x$映射后的特征向量，于是，在特征空间中划分超平面对应的模型可表示为：
$$f(x)=w^T\varphi (x)+b$$
和之前一样，先写出目标函数的拉格朗日函数，接着写出其对偶问题，最后运用SOM求解α。
w和b是模型参数，类似(6.6)，有：
min ⁡ w , b    1 2 ∣ ∣ w ∣ ∣ 2 s . t .      y i ( w T ϕ ( x ) + b ) ≥ 1 , i = 1 , 2 , . . . , m

$$\begin{aligned} &\min_{w,b} \;\frac{1}{2}||w||^2 \\ &s.t.\;\;y_i(w^T\phi(x)+b)\ge1, i=1,2,...,m \end{aligned}$$ ​w,bmin​21​∣∣w∣∣2s.t.yi​(wTϕ(x)+b)≥1,i=1,2,...,m​
其对偶问题：
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_i{y}_i{y}_j\varphi (x_i{)}^T\varphi (x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & {\alpha }_i\ge 0,i=1,2,...,m.\end{array}\text{\hspace{1em}(6.21)}$$
求解(6.21)涉及到计算$\varphi (x_i{)}^T\varphi (x_j)$，这是样本$x_i与x_j$映射到特征空间之后的内积。特征空间位数可能很高，甚至是无穷维，因此直接计算$\varphi (x_i{)}^T\varphi (x_j)$通常是困难的。便引出了核函数（Kernel）的概念所以我们设想这样一个函数：
$$k(x_i,x_j)=⟨\varphi (x_i),\varphi (x_j)⟩=\varphi (x_i{)}^T\varphi (x_j)$$
即$x_i与x_j$在特征空间的内积等于它们在原始空间中通过函数$k(\cdot ,\cdot )$计算的结果。可以用它来替换高维或者无穷维特征空间中的内积，于是(6.21)可重写为：
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_i{y}_i{y}_{j}k(x_i,x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & {\alpha }_i\ge 0,i=1,2,...,m.\end{array}$$
求解后得到：
$$\begin{array}{rl}f(x)& =w^T\varphi (x)+b\\ & =\sum _{i=1}^m{\alpha }_i{y}_i\varphi (x_i{)}^T\varphi (x)+b\\ & =\sum _{i=1}^m{\alpha }_i{y}_{i}k(x,x_i)+b\end{array}\text{\hspace{1em}(6.24)}$$
这里的函数$k(\cdot ,\cdot )$就是核函数(kernel function)，可以不必直接计算高维甚至无穷维特征空间中的内积。(6.24)显出模型最优解可通过训练样本的核函数展开，这一展示亦称“支持向量展式”。
现实任务中通常不知道映射$\varphi (\cdot )$的具体形式，也就不知道核函数$k(\cdot ,\cdot )$是否存在，或者是什么样的。

几种常用核函数：特别地，文本数据一般用线性核，情况不明可尝试高斯核。
除了这些常用的核函数，要产生核函数还可以使用组合的方式：
若${\kappa }_1和{\kappa }_2$都是核函数，则$a{\kappa }_1+b{\kappa }_2$ 也是核函数，其中 a>0,b>0。
若${\kappa }_1和{\kappa }_2$都是核函数，则其直积${\kappa }_1\otimes {\kappa }_2(x,z)={\kappa }_1(x,z){\kappa }_2(x,z)$也是核函数。
若 ${\kappa }_1$是核函数，则对于任意函数 $g(x)，\kappa (x,z)=g(x){\kappa }_1(x,z)g(z)$也是核函数。

核函数举例：
每个样本有两个属性x和y，两个样本点$v_1=(x_1,y_1),v_2=(x_2,y_2)$，其映射后的特征向量$\varphi (x,y)=(x^2,\sqrt{2}xy，y^2)$，对应核函数$k(v_1,v_2)=⟨v_1,v_2{⟩}^2$
证明：$v_1,v_2$在特征空间的内积为
⟨ ϕ ( v 1 ) , ϕ ( v 2 ) ⟩ = ϕ ( v 1 ) T ϕ ( v 2 ) = ( x 1 2 , 2 x 1 y 1 , y 1 2 ) T ( x 2 2 , 2 x 2 y 2 , y 2 2 ) = x 1 2 x 2 2 + 2 x 1 x 2 y 1 y 2 + y 1 2 y 2 2 = ( x 1 x 2 + y 1 y 2 ) 2 = ⟨ v 1 , v 2 ⟩ 2 = k ( v 1 , v 2 )

$$\begin{aligned} \langle\phi(v_1),\phi(v_2)\rangle&=\phi(v_1)^T\phi(v_2)\\ &=(x_1^2,\sqrt2x_1y_1,y_1^2)^T(x_2^2,\sqrt2x_2y_2,y_2^2)\\ &=x_1^2x_2^2+2x_1x_2y_1y_2+y_1^2y_2^2\\ &=(x_1x_2+y_1y_2)^2\\ &=\langle v_1,v_2\rangle^2\\ &=k(v_1,v_2) \end{aligned}$$ ⟨ϕ(v1​),ϕ(v2​)⟩​=ϕ(v1​)Tϕ(v2​)=(x12​,2 ​x1​y1​,y12​)T(x22​,2 ​x2​y2​,y22​)=x12​x22​+2x1​x2​y1​y2​+y12​y22​=(x1​x2​+y1​y2​)2=⟨v1​,v2​⟩2=k(v1​,v2​)​

4. 软间隔与正则化

  前面讨论的都是假定训练样本在样本空间或特征空间是线性可分的，即存在一个超平面能将不同类的样本完全划分开。但是，现实任务很难找到合适的核函数，即使找到，也难说这不是过拟合造成的结果。
  解决办法：软间隔——允许支持向量机在一些样本上出错
前面介绍的是硬间隔——所有样本都必须划分正确。

硬间隔：必须满足约束
$$y_i(w^T{x}_i+b)\ge 1\text{\hspace{1em}(6.28)}$$
软间隔：允许某些样本不满足约束(6.28)。

当然，在最大化间隔的同时，不满足约束的样本应该尽可能少。于是，优化目标为：

含义：如果分类正确，那么函数间隔必定大于等于1，此时损失为0；如果分类错误，那么函数间隔必定小于0，此时损失为1。
当 C 为无穷大时，(6.29)迫使所有样本均满足约束(6.28)，因为此时对误分类的惩罚无限大，也即要求全部样本分类正确。当 C 取有限值时，(6.29)允许一些样本不满足约束。
0/1损失函数非凸、非连，所以式(6.29)不易直接求解。于是在实际任务中，我们采用一些凸的连续函数来取替它，这样的函数就称为替代损失函数。
三种常用的替代损失函数：

若用hinge损失，则(6.29)变成：
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^{m}max(0,1-y_i(w^T{x}_i+b))\text{\hspace{1em}(6.34)}$$
引入“松弛变量”${\xi }_i\ge 0$，可将(6.34)重写为：
$$\begin{gathered} \underset{w,b,{\xi }_i}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i \\ s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i, \\ {\xi }_i\ge 0,i=1,2,...,m.\text{\hspace{1em}(6.35)} \end{gathered}$$
这就是常用的“软间隔支持向量机”
显然，(6.35)中每个样本都有一个对应的松弛变量，用以表示该样本不满足约束(6.28)的程度。这也是一个二次规划问题。

• 1、通过拉格朗日乘子法把 m 个约束转换 m 个拉格朗日乘子，得到该问题的拉格朗日函数：
  $$\begin{array}{rl}L(w,b,\alpha ,\xi ,\mu )=& \frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i\\ & +\sum _{i=1}^m{\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i+b))-\sum _{i=1}^m{\mu }_i{\xi }_i\end{array}\text{\hspace{1em}(6.36)}$$
  其中，${\alpha }_i\ge 0，{\mu }_i\ge 0$是拉格朗日乘子。
• 2、分别对$w,b,{\xi }_i$求偏导为零，得：
  $$\begin{gathered} w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i \\ 0=\sum _{i=1}^m{\alpha }_i{y}_i \\ C={\alpha }_i+{\mu }_i \end{gathered}$$
• 3、带入(6.36)得到(6.35)的对偶问题：
  $$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0,\\ & 0\le {\alpha }_i\le C,i=1,2,...m.\end{array}\text{\hspace{1em}(6.40)}$$
  软间隔与硬间隔的对偶问题唯一的差别：对偶变量的约束条件不一样。
  软间隔：$0\le {\alpha }_i\le C$；
  硬间隔：$0\le {\alpha }_i$
• 4、和之前一样，使用SMO算法求解对偶问题，解出所有样本对应的拉格朗日乘子。

软间隔支持向量机，KKT条件要求：
{ α i ≥ 0 ,    μ i ≥ 0 , y i f ( x i ) − 1 + ξ i ≥ 0 , α i ( y i f ( x i ) − 1 + ξ i ) = 0 , ξ i ≥ 0 ,    μ i ξ i = 0 \left\{

$$\begin{aligned} &\alpha_i\ge0,\;\mu_i\ge0,\\ &y_if(x_i)-1+\xi_i\ge0,\\ &\alpha_i(y_if(x_i)-1+\xi_i)=0,\\ &\xi_i\ge0,\;\mu_i\xi_i=0 \end{aligned}$$ \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​αi​≥0,μi​≥0,yi​f(xi​)−1+ξi​≥0,αi​(yi​f(xi​)−1+ξi​)=0,ξi​≥0,μi​ξi​=0​
KKT条件理解：

• 对于任意训练样本$(x_i,y_i)$，总有${\alpha }_i=0或y_{i}f(x_i)=1-{\xi }_i$
  • 若${\alpha }_i=0$，则该样本不会对f(x)有任何影响；
  • 若${\alpha }_i>0$，则必有$y_{i}f(x_i)=1-{\xi }_i$，即该样本是支持向量：
    根据$C={\alpha }_i+{\mu }_i$可知：
    • 若${\alpha }_i<C$，则${\mu }_i>0$，进而有${\xi }_i=0$，则该样本恰在最大间隔边界上；
    • 若${\alpha }_i=C$，则${\mu }_i=0$（因为${\mu }_i{\xi }_i=0$，所以${\xi }_i$可以为大于等于0的任意数）：
      • 若${\xi }_i\le 1$，则该样本落在最大间隔内部；
      • 若${\xi }_i>1$，则该样本被错误分类。

特别地，在 R. Collobert. 的论文Large Scale Machine Learning 中提到，常数 C 一般取训练集大小的倒数（$C=\frac{1}{m}$）。

上面是采用hinge损失函数。若果使用对率损失函数${\ell }_{log}$来代替0/1损失，则几乎就得到了对率回归模型(3.27)。
支持向量机与对率回归的优化目标相近，通常情况下它们的性能也相当。

• 对率回归：具有自然的概率意义，即在给出预测标记的同时也给出了概率；可直接用于多分类任务
• 支持向量机：不具有概率意义，欲得到概率输出需进行特殊处理，不可直接用于多分类任务

无论使用何种损失函数，SVM的目标函数都可以描述为以下形式(6.42)：

结构风险（structural risk）：用于描述模型$f$的某些性质。用来描述划分超平面“间隔”大小。
经验风险（empirical risk）：用于描述模型与训练数据的契合程度。用来表述训练集上的误差。
参数 C 用于权衡这两种风险。
从最小化经验风险的角度来看，$\Omega (f)$表述了我们希望得到具有何种性质的模型（例如复杂度较小的模型），这为引入领域知识和用户意图提供了途径；另一方面，Ω(f) 还有助于削减假设空间，从而降低了最小化训练误差的过拟合风险。
从这个角度来说，(6.42)称为“正则化”（regularization）问题，$\Omega (f)$为正则化项，C 为正则化常数。$L_p$范数是常用的正则化项，其中$L_2$范数$||w|{|}_2$倾向于w的分量取值尽量均衡，即非零分量个数尽量稠密，而$L_0$范数$||w|{|}_0$和$L_1$范数$||w|{|}_1$则倾向于w的分量尽量稀疏，即非零分量个数尽量少。
正则化可理解为一种“罚函数法”，即对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标。
前面学习的模型大多都是在最小化经验风险的基础上，再考虑结构风险（避免过拟合）。
而SVM是从最小化结构风险来展开的。

5. 支持向量回归(SVR)

同样是希望学得线性模型$f(x)=w^{T}x+b$来做预测，使得$f(x)与y$尽可能接近。

• 传统回归模型：基于模型输出$f(x)$与真实值$y$之间的差别来计算损失，当且仅当$f(x)$与$y$完全相同时，损失才为零。
• 支持向量回归(SVR)：假设我们能容忍f(x)与y之间最多有$ϵ$的偏差，即仅当$f(x)$与$y$之间的误差绝对值大于$ϵ$时，才计算损失。
  如上图，这相当于以$f(x)$为中心，构建一个宽度为2$ϵ$的间隔带，若训练样本落在次间隔带，则认为是被预测正确的。

SVR问题的目标函数可形式化为：
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\ell }_{ϵ}(f(x_i)-y_i)\text{\hspace{1em}(6.43)}$$
其中$C$为正则化常数，${\ell }_{ϵ}$是ϵ−不敏感损失（ϵ−insensitive loss）函数。
ℓ ϵ ( z ) = { 0 , i f    ∣ z ∣ ≤ ϵ ; ∣ z ∣ − ϵ , o t h e r s i z e . (6.44) \ell_\epsilon(z)=

$$\begin{cases} 0,& \mathrm{if}\;|z|\leq\epsilon;\\ |z|-\epsilon,&\mathrm{othersize.} \end{cases}$$ \tag{6.44} ℓϵ​(z)={0,∣z∣−ϵ,​if∣z∣≤ϵ;othersize.​(6.44)
引入松弛变量${\xi }_i、{\hat{\xi }}_i$，分别表示间隔带两侧的松弛程度，它们可有所不同。将(6.43)重写为：
$$\begin{array}{rl}& \underset{w,b,{\xi }_i,{\hat{\xi }}_i}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m({\xi }_i+{\hat{\xi }}_i)\\ & s.t.f(x_i)-y_i\le ϵ+{\xi }_i,\\ & y_i-f(x_i)\le ϵ+{\hat{\xi }}_i,\\ & {\xi }_i\ge 0,{\hat{\xi }}_i\ge 0,i=1,2,...,m.\end{array}$$
引入拉格朗日乘子${\mu }_i\ge 0,{\hat{\mu }}_i\ge 0,{\alpha }_i\ge 0,{\hat{\alpha }}_i\ge 0$，得到拉格朗日函数：

讲求得的偏导带入(6.46)，得到SVR得对偶问题：

KKT条件：

然后使用SMO算法求解拉格朗日乘子，最后得到SVR的解：

6. 核方法

补充：为什么要使用对偶问题（SVM）
 1.对偶问题将原始问题中的约束转为了对偶问题中的等式约束
 2.方便核函数的引入
 3.改变了问题的复杂度。由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。
(对偶问题的理解)

参考：
序列最小优化算法（SMO）浅析
支持向量机
SVM与LR的比较