线性支持向量机与软间隔最大化
支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器 ，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化 ，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（ linear support vector machine in linearly separable case )、线性支持向量机（ linear support vector machine)及非线性支持向量机（non-linear support vector machine)。简单模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化（ hard margin maximization)，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（ soft margin maximization)，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧（kemel trick）及软间隔最大化，学习非线性支持向量机。
当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机 。这样的方法称为核技巧。核方法（ kernel method)是比支持向量机更为一般的机器学习方法。
Cortes与Vapnik提出线性支持向童机，Boser、Guyon与Vapnik又引入核技巧，提出非线性支持向量机。
本章按照上述思路介绍3类支持向量机、核函数及一种快速学习算法——序列最小最优化算法（SMO)。
线性支持向量机
线性可分子问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束并不能成立。怎么才能将它扩展到线性不可分问题呢？这就需要修改硬间隔最大化，使其成为软间隔最大化。
假设给定一个特征空间上的训练数据集
这里，C>0称为惩罚函数，一般由应用问题决定，C值大时对误分类的惩罚更大，C值小时对误分类的惩罚减小。最小化目标函数（上式）包含了两层含义 ：
同时使误分类点的个数尽可能小，
而C是调和两者的系数 。
有了上面的思路，可以和训练数据集线性可分时一样来考虑训练数据集不可分时的线性支持向量机学习问题。相应于硬间隔最大化，它称为软间隔最大化 。
线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题（原始问题 ）：
下面给出线性支持向量机的定义 ：
对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大问题（上述原始问题），得到的分离超平面为
以及相应的分类决策函数
称为线性支持向量机。
线性支持向量机学习的对偶算法
原始问题的对偶问题是
下面我们来具体说明上述对偶问题是怎么得出的：
原始最优化问题的拉格朗日函数 是
其中，
对偶问题是拉格朗日函数的极大极小问题。
得
将上式代入上面的拉格朗日函数，得
拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题 。
下面具体来说明上式不等式是怎么得到的：
再通过取负，将对目标函数求极大转换为求极小，于是得到对偶问题
设
证明：
原始问题是凸二次规划问题，满足强对偶问题（凸函数+Slater条件），所以原函数问题和对偶问题等价，则解满足KKT条件。即得
解释下上式所述的KKT条件：前三项是一阶偏导等于零，第四五项是互补松弛条件（强对偶性决定的） ，第六七项是原始问题的约束条件，最后两项是对偶问题的约束条件。
由上式KKT条件中的第一项可知，原始问题的解中的第一项成立，即
。这里具体是怎么得到的呢？
。由此定理可知，分离超平面可以写成
分类决策函数可以写成
上式为线性支持向量机的对偶形式 。
综合前面的结果，有下面的算法。
线性支持向量机学习算法
输出：分离超平面和分类决策函数。
（1）选择惩罚参数C>0，构造并求解凸二次规划问题（对偶问题 ）
求得最优解
（3）求得分离超平面和分类决策函数
分离超平面：
分类决策函数：
支持向量
在线性不可分的情况下，将对偶问题的解
这里解释下为什么，由上一节我们知道
合页损失函数
线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：
目标函数的第一项是经验损失是或经验风险，函数
称为合页损失函数（hinge loss function）。下标“+”表示以下取正值的函数。
定理：线性支持向量机原始最优化问题 等价于 合页损失+正则化的最优化问题
线性支持向量机原始最优化问题
等价于合页损失+正则化的最优化问题
证明：令
由上式，
故原始最优化问题约束条件的第一项成立。
所以合页损失+正则化最优化问题可写成
与原始最优化问题等价。
反之，也可将原始最优化问题表示成合页损失+正则化的最优化问题。
图中还画出0-1损失函数，可以认为它是二类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向量机是优化由0-1损失函数的上界（合页损失函数）构成的目标函数 。这时的上界损失函数又称为代理损失函数。
上图中虚线显示的是感知机的损失函数
参考资料
本章的结构和大部分内容均参考此书对应章节。
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T = {( x 1 , y 1 ) , ( x 2 , y 2 ) , ... , ( x N , y N )} 其中，x i ∈ X = R n x_i\in X=R^n x i ∈ X = R n y i ∈ Y = { − 1 , + 1 } y_i\in Y=\{-1,+1\} y i ∈ Y = { − 1 , + 1 } i = 1 , 2 , . . . , N i=1,2,...,N i = 1 , 2 , ... , N x i x_i x i y i y_i y i x i x_i x i
线性不可分意味着某些样本点是不能满足线性可分中的函数间隔大于等于1的约束条件的。为了解决这个问题，可以对每个样本点( x i , y i ) (x_i,y_i) ( x i , y i ) ξ i ⩾ 0 \xi_i\geqslant 0 ξ i ⩾ 0
y i ( w ⋅ x i + b ) ⩾ 1 − ξ i y_i(w\cdot x_i+b)\geqslant1-\xi_i y i ( w ⋅ x i + b ) ⩾ 1 − ξ i 上式可以这么理解： ξ i \xi_i ξ i 是数据点到其分隔边界的函数距离，而 1 − ξ i 1-\xi_i 1 − ξ i 则就是数据点到分界面的函数距离了。原来要求的是数据点到分界面的函数距离要大于等于1，现在就放宽到了数据点到分界面函数距离大于等于1- ξ i \xi_i ξ i 。这其实是对异常离群点的一种容忍。
同时，对每一个松弛变量ξ i \xi_i ξ i ξ i \xi_i ξ i
1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 2 1 ∣∣ w ∣ ∣ 2 min w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i s.t. y i ( w ⋅ x i + b ) ⩾ 1 − ξ i , i = 1 , 2 , . . . , N ξ i ⩾ 0 , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{min}}_{w,b,\xi}\quad \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i\\
&\text{s.t.}\ \ \quad y_i(w\cdot x_i+b)\geqslant 1-\xi_i,\ i=1,2,...,N\\
&\ \ \ \quad \quad \xi_i\geqslant 0,\ i=1,2,...,N\\
\end{aligned} min w , b , ξ 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i s.t. y i ( w ⋅ x i + b ) ⩾ 1 − ξ i , i = 1 , 2 , ... , N ξ i ⩾ 0 , i = 1 , 2 , ... , N 原始问题是一个凸二次规划问题，因而关于( w , b , ξ ) (w,b,\xi) ( w , b , ξ )
设原始问题的解是w ∗ , b ∗ w^*,b^* w ∗ , b ∗ w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 w ∗ ⋅ x + b ∗ = 0 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^*\cdot x+b^*) f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) 线性支持向量机 。显然，线性支持向量机包含线性可分支持向量机。由于现实中训练数据集往往是不可分的，线性支持向量机具有更广泛的适用性。
w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 w ∗ ⋅ x + b ∗ = 0 f ( x ) = sign ( w ∗ ⋅ x + b ∗ ) f(x)=\text{sign}(w^*\cdot x+b^*) f ( x ) = sign ( w ∗ ⋅ x + b ∗ ) min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s.t. ∑ i = 1 N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{min}}_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\
&\text{s.t.}\ \quad \sum_{i=1}^N\alpha_iy_i=0\\
&\ \ \ \quad \quad 0\leqslant\alpha_i\leqslant C,\ i=1,2,...,N\\
\end{aligned} min α 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ⋅ x j ) − i = 1 ∑ N α i s.t. i = 1 ∑ N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , ... , N L ( w , b , ξ , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i − ∑ i = 1 N α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i = 1 N μ i ξ i L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i L ( w , b , ξ , α , μ ) = 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i − i = 1 ∑ N α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − i = 1 ∑ N μ i ξ i α i ⩾ 0 , μ i ⩾ 0 \alpha_i\geqslant0,\quad \mu_i\geqslant0 α i ⩾ 0 , μ i ⩾ 0 首先求L ( w , b , ξ , α , μ ) L(w,b,\xi,\alpha,\mu) L ( w , b , ξ , α , μ ) 对 w , b , ξ w,b,\xi w , b , ξ 的极小 ，由
▽ w L ( w , b , ξ , α , μ ) = w − ∑ i = 1 N α i y i x i = 0 ▽ b L ( w , b , ξ , α , μ ) = − ∑ i = 1 N α i y i = 0 ▽ ξ i L ( w , b , ξ , α , μ ) = C − α i − μ i = 0 \begin{aligned}
&\bigtriangledown_wL(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\
&\bigtriangledown_bL(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N\alpha_iy_i=0\\
&\bigtriangledown_{\xi_i}L(w,b,\xi,\alpha,\mu)=C-\alpha_i-\mu_i=0
\end{aligned} ▽ w L ( w , b , ξ , α , μ ) = w − i = 1 ∑ N α i y i x i = 0 ▽ b L ( w , b , ξ , α , μ ) = − i = 1 ∑ N α i y i = 0 ▽ ξ i L ( w , b , ξ , α , μ ) = C − α i − μ i = 0 w = ∑ i = 1 N α i y i x i ∑ i = 1 N α i y i = 0 C − α i − μ i = 0 \begin{aligned}
&w=\sum_{i=1}^N\alpha_iy_ix_i\\
&\sum_{i=1}^N\alpha_iy_i=0\\
&C-\alpha_i-\mu_i=0\\
\end{aligned} w = i = 1 ∑ N α i y i x i i = 1 ∑ N α i y i = 0 C − α i − μ i = 0 min w , b , ξ L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i \mathop{\text{min}}_{w,b,\xi}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i min w , b , ξ L ( w , b , ξ , α , μ ) = − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ⋅ x j ) + i = 1 ∑ N α i 再对极小（上式）求α \alpha α 的极大 ，即得对偶问题 ：
max α − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i s.t. ∑ i = 1 N α i y i = 0 C − α i − μ i = 0 α i ⩾ 0 μ i ⩾ 0 , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{max}}_{\alpha}\quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\\
&\text{s.t.}\ \quad \sum_{i=1}^N\alpha_iy_i=0\\
&\ \ \ \quad \quad C-\alpha_i-\mu_i=0\\
&\ \ \ \quad \quad \alpha_i\geqslant0\\
&\ \ \ \quad \quad \mu_i\geqslant0,\ i=1,2,...,N\\
\end{aligned} max α − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ⋅ x j ) + i = 1 ∑ N α i s.t. i = 1 ∑ N α i y i = 0 C − α i − μ i = 0 α i ⩾ 0 μ i ⩾ 0 , i = 1 , 2 , ... , N 将对偶最优化问题（上式）进行变换：利用等式约束（上式第二项约束）消去μ i \mu_i μ i α i \alpha_i α i
0 ⩽ α i ⩽ C 0\leqslant\alpha_i\leqslant C 0 ⩽ α i ⩽ C C − α i − μ i = 0 ⇒ μ i = C − α i u i ⩾ 0 ⇒ C − α i ⩾ 0 ⇒ α i ⩽ C α i ⩾ 0 ⇒ 0 ⩽ α i ⩽ C \begin{aligned}
&C-\alpha_i-\mu_i=0 \Rightarrow \mu_i=C-\alpha_i\\
&u_i\geqslant0 \Rightarrow C-\alpha_i\geqslant0 \Rightarrow \alpha_i\leqslant C\\
&\alpha_i\geqslant0 \Rightarrow 0\leqslant \alpha_i\leqslant C
\end{aligned} C − α i − μ i = 0 ⇒ μ i = C − α i u i ⩾ 0 ⇒ C − α i ⩾ 0 ⇒ α i ⩽ C α i ⩾ 0 ⇒ 0 ⩽ α i ⩽ C min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s.t. ∑ i = 1 N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{min}}_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\
&\text{s.t.}\ \quad \sum_{i=1}^N\alpha_iy_i=0\\
&\ \ \ \quad \quad 0\leqslant\alpha_i\leqslant C,\ i=1,2,...,N\\
\end{aligned} min α 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ⋅ x j ) − i = 1 ∑ N α i s.t. i = 1 ∑ N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , ... , N 可以通过求解对偶问题而得到原始问题的解 ( w ∗ , b ∗ ) (w^*,b^*) ( w ∗ , b ∗ ) ，进而确定分离超平面和决策函数 。为此，我们以定理的形式叙述原始问题的最优解( w ∗ , b ∗ ) (w^*,b^*) ( w ∗ , b ∗ ) α ∗ \alpha^* α ∗
定理：原始问题的最优解 ( w ∗ , b ∗ ) (w^*,b^*) ( w ∗ , b ∗ ) 和对偶问题的最优解的 α ∗ \alpha^* α ∗ 关系：
α ∗ = { α 1 ∗ , α 2 ∗ , . . . , α N ∗ } \alpha^*=\{\alpha_1^*, \alpha_2^*, ..., \alpha_N^*\} α ∗ = { α 1 ∗ , α 2 ∗ , ... , α N ∗ } 是上述对偶问题的一个解，若存在α ∗ \alpha^* α ∗ α j ∗ \alpha_j^* α j ∗ 0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C ( w ∗ , b ∗ ) (w^*,b^*) ( w ∗ , b ∗ )
w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y j − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) \begin{aligned}
&w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\\
&b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)\\
\end{aligned} w ∗ = i = 1 ∑ N α i ∗ y i x i b ∗ = y j − i = 1 ∑ N y i α i ∗ ( x i ⋅ x j ) ▽ w L ( w , b , ξ , α , μ ) = w − ∑ i = 1 N α i y i x i = 0 ▽ b L ( w , b , ξ , α , μ ) = − ∑ i = 1 N α i y i = 0 ▽ ξ i L ( w , b , ξ , α , μ ) = C − α i − μ = 0 α i ∗ ( y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ) = 0 μ i ∗ ξ i ∗ = 0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ ⩾ 0 ξ i ∗ ⩾ 0 α i ∗ ⩾ 0 μ i ∗ ⩾ 0 , i = 1 , 2 , . . . , N \begin{aligned}
&\bigtriangledown_wL(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\
&\bigtriangledown_bL(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N\alpha_iy_i=0\\
&\bigtriangledown_{\xi_i}L(w,b,\xi,\alpha,\mu)=C-\alpha_i-\mu=0\\
&\alpha_i^*(y_i(w^*\cdot x_i+b^*)-1+\xi_i)=0\\
&\mu_i^*\xi_i^*=0\\
&y_i(w^*\cdot x_i+b^*)-1+\xi_i^*\geqslant 0\\
&\xi_i^*\geqslant0\\
&\alpha_i^*\geqslant0\\
&\mu_i^*\geqslant 0,\quad i=1,2,...,N\\
\end{aligned} ▽ w L ( w , b , ξ , α , μ ) = w − i = 1 ∑ N α i y i x i = 0 ▽ b L ( w , b , ξ , α , μ ) = − i = 1 ∑ N α i y i = 0 ▽ ξ i L ( w , b , ξ , α , μ ) = C − α i − μ = 0 α i ∗ ( y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ) = 0 μ i ∗ ξ i ∗ = 0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ ⩾ 0 ξ i ∗ ⩾ 0 α i ∗ ⩾ 0 μ i ∗ ⩾ 0 , i = 1 , 2 , ... , N w ∗ = ∑ i = 1 N α i ∗ y i x i w^*=\sum_{i=1}^N\alpha_i^*y_ix_i w ∗ = i = 1 ∑ N α i ∗ y i x i 再由KKT的互补松弛条件（第四五项）得，若存在α j ∗ \alpha_j^* α j ∗ 0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C
y i ( w ∗ ⋅ x i + b ∗ ) − 1 = 0 y_i(w^*\cdot x_i+b^*)-1=0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 = 0 由互补松弛条件的第一项可知，当 α j ∗ > 0 \alpha_j^*>0 α j ∗ > 0 时，该项括号内才等于零，即
y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ = 0 y_i(w^*\cdot x_i+b^*)-1+\xi_i^*=0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ = 0 里面还有个 ξ i ∗ \xi_i^* ξ i ∗ 未知，那怎么消去这个 ξ i ∗ \xi_i^* ξ i ∗ 呢？由互补松弛条件的第二项可知，当 μ i ∗ > 0 \mu_i^*>0 μ i ∗ > 0 时， ξ i ∗ = 0 \xi_i^*=0 ξ i ∗ = 0 ，这时候就能消去 ξ i ∗ \xi_i^* ξ i ∗ 了。那么当 μ i ∗ > 0 \mu_i^*>0 μ i ∗ > 0 时， α j ∗ \alpha_j^* α j ∗ 必须满足什么条件呢？或者说，当 α j ∗ \alpha_j^* α j ∗ 满足什么条件时，才能保证 μ i ∗ > 0 \mu_i^*>0 μ i ∗ > 0 ？我们知道，对偶问题的条件中有一个 C − α i − μ i = 0 C-\alpha_i-\mu_i=0 C − α i − μ i = 0 ，即 μ i = C − α i > 0 \mu_i=C-\alpha_i>0 μ i = C − α i > 0 ，则 α i < C \alpha_i<C α i < C ，这时，上式中的 ξ i ∗ = 0 \xi_i^*=0 ξ i ∗ = 0 。也就是说，当 0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C 时， ξ i ∗ = 0 \xi_i^*=0 ξ i ∗ = 0 ，则有
y i ( w ∗ ⋅ x i + b ∗ ) − 1 = 0 y_i(w^*\cdot x_i+b^*)-1=0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 = 0 即由此即得原始问题的解中的第二项（注意上式中1可以写成y i 2 y_i^2 y i 2 y i y_i y i b ∗ b^* b ∗
b ∗ = y j − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j) b ∗ = y j − i = 1 ∑ N y i α i ∗ ( x i ⋅ x j ) ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ = 0 \sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0 i = 1 ∑ N α i ∗ y i ( x ⋅ x i ) + b ∗ = 0 f ( x ) = sign ( ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ ) f(x)=\text{sign}\left( \sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^* \right) f ( x ) = sign ( i = 1 ∑ N α i ∗ y i ( x ⋅ x i ) + b ∗ ) 输入：训练数据集T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T = {( x 1 , y 1 ) , ( x 2 , y 2 ) , ... , ( x N , y N )} x i ∈ X = R n x_i\in X=R^n x i ∈ X = R n y i ∈ Y = { − 1 , + 1 } y_i\in Y=\{-1,+1\} y i ∈ Y = { − 1 , + 1 } i = 1 , 2 , . . . , N i=1,2,...,N i = 1 , 2 , ... , N
min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s.t. ∑ i = 1 N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{min}}_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\
&\text{s.t.}\ \quad \sum_{i=1}^N\alpha_iy_i=0\\
&\ \ \ \quad \quad 0\leqslant\alpha_i\leqslant C,\ i=1,2,...,N\\
\end{aligned} min α 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ⋅ x j ) − i = 1 ∑ N α i s.t. i = 1 ∑ N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , ... , N α ∗ = { α 1 ∗ , α 2 ∗ , . . . , α N ∗ } \alpha^*=\{\alpha_1^*, \alpha_2^*, ..., \alpha_N^*\} α ∗ = { α 1 ∗ , α 2 ∗ , ... , α N ∗ } （2）计算原问题的最优解的参数w ∗ w^* w ∗ b ∗ b^* b ∗
w ∗ = ∑ i = 1 N α i ∗ y i x i w^*=\sum_{i=1}^N\alpha_i^*y_ix_i w ∗ = i = 1 ∑ N α i ∗ y i x i 选择α ∗ \alpha^* α ∗ 0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C α j ∗ \alpha_j^* α j ∗
b ∗ = y j − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j) b ∗ = y j − i = 1 ∑ N y i α i ∗ ( x i ⋅ x j ) w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 w ∗ ⋅ x + b ∗ = 0 f ( x ) = sign ( w ∗ ⋅ x + b ∗ ) f(x)=\text{sign}(w^*\cdot x+b^*) f ( x ) = sign ( w ∗ ⋅ x + b ∗ ) 上述步骤（2）中，对任一符合条件0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C α j ∗ \alpha_j^* α j ∗ b ∗ b^* b ∗ b ∗ b^* b ∗
α ∗ = ( a 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^*=(a_1^*,\alpha_2^*,...,\alpha_N^*)^T α ∗ = ( a 1 ∗ , α 2 ∗ , ... , α N ∗ ) T 中对应于α i ∗ > 0 \alpha_i^*>0 α i ∗ > 0 ( x i , y i ) (x_i,y_i) ( x i , y i ) x i x_i x i
ξ i ∣ ∣ w ∣ ∣ \frac{\xi_i}{||w||} ∣∣ w ∣∣ ξ i 软间隔的支持向量 x i x_i x i 或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。
若α i ∗ < C \alpha_i^*<C α i ∗ < C ξ i = 0 \xi_i=0 ξ i = 0
若α i ∗ = C \alpha_i^*=C α i ∗ = C
0 < ξ i < 1 0<\xi_i<1 0 < ξ i < 1 x i x_i x i
ξ i = 1 \xi_i=1 ξ i = 1 x i x_i x i
ξ i > 1 \xi_i>1 ξ i > 1 x i x_i x i
C − α i ∗ − μ i ∗ = 0 μ i ∗ ξ i ∗ = 0 \begin{aligned}
&C-\alpha_i^*-\mu_i^*=0\\
&\mu_i^*\xi_i^*=0
\end{aligned} C − α i ∗ − μ i ∗ = 0 μ i ∗ ξ i ∗ = 0 所以，当 α i ∗ < C \alpha_i^*<C α i ∗ < C ，则 μ i ∗ > 0 \mu_i^*>0 μ i ∗ > 0 ，所以 ξ i = 0 \xi_i=0 ξ i = 0 ，即支持向量恰好落在间隔边界上；而当 α i ∗ = C \alpha_i^*=C α i ∗ = C 时， μ i ∗ = 0 \mu_i^*=0 μ i ∗ = 0 ，所以 ξ i > 0 \xi_i>0 ξ i > 0 。
对于线性支持向量机学习来说，其模型为分离超平面w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 w ∗ ⋅ x + b ∗ = 0 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^*\cdot x+b^*) f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ )
∑ i = 1 N [ 1 − y i ( w ⋅ x i + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 \sum_{i=1}^N\left[ 1-y_i(w\cdot x_i+b) \right]_++\lambda||w||^2 i = 1 ∑ N [ 1 − y i ( w ⋅ x i + b ) ] + + λ ∣∣ w ∣ ∣ 2 L ( y ( w ⋅ x + b ) ) = [ 1 − y ( w ⋅ x + b ) ] + L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+ L ( y ( w ⋅ x + b )) = [ 1 − y ( w ⋅ x + b ) ] + [ z ] + = { z , z > 0 0 , z ⩽ 0 \begin{aligned}
\ [z]_+=
\left\{\begin{matrix}
z,\quad z>0\\
0,\quad z\leqslant0
\end{matrix}\right.
\end{aligned} [ z ] + = { z , z > 0 0 , z ⩽ 0 这就是说，当样本点( x i , y i ) (x_i,y_i) ( x i , y i ) y i ( w ⋅ x i + b ) > 1 y_i(w\cdot x_i+b)>1 y i ( w ⋅ x i + b ) > 1 1 − y i ( w ⋅ x i + b ) 1-y_i(w\cdot x_i+b) 1 − y i ( w ⋅ x i + b ) x 4 x_4 x 4 λ \lambda λ L 2 L_2 L 2
min w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i s.t. y i ( w ⋅ x i + b ) ⩾ 1 − ξ i , i = 1 , 2 , . . . , N ξ i ⩾ 0 , i = 1 , 2 , . . . , N \begin{aligned}
&\mathop{\text{min}}_{w,b,\xi}\quad \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i\\
&\text{s.t.}\ \ \quad y_i(w\cdot x_i+b)\geqslant 1-\xi_i,\ i=1,2,...,N\\
&\ \ \ \quad \quad \xi_i\geqslant 0,\ i=1,2,...,N\\
\end{aligned} min w , b , ξ 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i s.t. y i ( w ⋅ x i + b ) ⩾ 1 − ξ i , i = 1 , 2 , ... , N ξ i ⩾ 0 , i = 1 , 2 , ... , N min w , b ∑ i = 1 N [ 1 − y i ( w ⋅ x i + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 \mathop{\text{min}}_{w,b}\ \sum_{i=1}^N\left[ 1-y_i(w\cdot x_i+b) \right]_++\lambda||w||^2 min w , b i = 1 ∑ N [ 1 − y i ( w ⋅ x i + b ) ] + + λ ∣∣ w ∣ ∣ 2 [ 1 − y i ( w ⋅ x i + b ) ] + = ξ i \left[ 1-y_i(w\cdot x_i+b) \right]_+=\xi_i [ 1 − y i ( w ⋅ x i + b ) ] + = ξ i ，则ξ i ⩾ 0 \xi_i\geqslant 0 ξ i ⩾ 0
当1 − y i ( w ⋅ x i + b ) > 0 1-y_i(w\cdot x_i+b)>0 1 − y i ( w ⋅ x i + b ) > 0 y i ( w ⋅ x i + b ) = 1 − ξ i y_i(w\cdot x_i+b)=1-\xi_i y i ( w ⋅ x i + b ) = 1 − ξ i
当1 − y i ( w ⋅ x i + b ) ⩽ 0 1-y_i(w\cdot x_i+b)\leqslant 0 1 − y i ( w ⋅ x i + b ) ⩽ 0 ξ i = 0 \xi_i=0 ξ i = 0 y i ( w ⋅ x i + b ) ⩾ 1 − ξ i y_i(w\cdot x_i+b)\geqslant 1-\xi_i y i ( w ⋅ x i + b ) ⩾ 1 − ξ i
于是w , b , ξ i w,b,\xi_i w , b , ξ i
min w , b ∑ i = 1 N ξ i + λ ∣ ∣ w ∣ ∣ 2 \mathop{\text{min}}_{w,b}\sum_{i=1}^N\xi_i+\lambda||w||^2 min w , b i = 1 ∑ N ξ i + λ ∣∣ w ∣ ∣ 2 若取λ = 1 2 C \lambda=\frac{1}{2C} λ = 2 C 1
min w , b 1 C ( 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i ) \mathop{\text{min}}_{w,b} \frac{1}{C}\left( \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i \right) min w , b C 1 ( 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i ) 合页损失函数的图形如上图所示，横轴是函数间隔y ( w ⋅ x + b ) y(w\cdot x+b) y ( w ⋅ x + b )
[ − y i ( w ⋅ x i + b ) ] + \left[ -y_i(w\cdot x_i+b) \right]_+ [ − y i ( w ⋅ x i + b ) ] + 。这时，当样本点 ( x i , y i ) (x_i,y_i) ( x i , y i ) 被正确分类时，损失是0，否则损失是 − y i ( w ⋅ x i + b ) -y_i(w\cdot x_i+b) − y i ( w ⋅ x i + b ) 。相比之下，合页损失函数不仅要分类正确，而且确信度要足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。这就是SVM和感知机分本质区别！
support-vector-of-soft-interval 
