机器学习第六章：支持向量机

机器学习第六章：支持向量机

算法原理：从几何角度，对于线性可分数据集，支持向量机就是找距离正负样本都最远的超平面，相比于感知机，其解是唯一的，且不偏不倚，泛化性能更好。

n维空间的超平面（$w^{T}x+b=0$,其中$w,x\in R^n$）

• 超平面方程不唯一
• 法向量$w$和位移项$b$确定一个唯一超平面
• 法向量$w$垂直于超平面（缩放$w,b$时，若缩放倍数为负数会改变法向量方向）
• 法向量$w$指向的那一半空间为正空间，另一半为负空间
• 任意一点到超平面的距离为：$r=\frac{|w^{T}x+b|}{||w||}$

几何间隔：对于给定的数据集X和超平面$w^{T}x+b=0$,定义数据集X中任意一个样本点 ( x i , y i ) , y i = { − 1 , 1 } , i = 1 , 2 , . . . , m (x_{i},y_{i}),y_{i}=\{-1,1\},i=1,2,...,m (xi​,yi​),yi​={−1,1},i=1,2,...,m,关于超平面的几何间隔为：
$${\gamma }_i=\frac{y_i(w^T{x}_i+b)}{||w||}$$
正确分类时：${\gamma }_i>0$,几何间隔也就等价于点到超平面的距离;
没有正确分类时：${\gamma }_i<0$;

对于给定的数据集X和超平面$w^{T}x+b=0$,定义数据集X关于超平面的几何间隔为数据集X中所有样本点的几何间隔最小值$\gamma =mi{n}_{i=1,2,...,m}{\gamma }_i$

支持向量机

模型：给定线性可分的数据集X，支持向量机模型希望求得数据集X关于超平面的几何间隔$\gamma$达到最大的那个超平面，然后套上一个sign函数实现分类功能：
y = s i g n ( w T x + b ) = { 1 , w T x + b > 0 − 1 , w T x + b < 0 y=sign(w^{T}x+b)={1,wTx+b>0−1,wTx+b<0

y=sign(wTx+b)={1,wTx+b>0−1,wTx+b<0​
几何间隔最大的超平面一定就是那个距离正负样本都最远的超平面；
因为：

• 当超平面没有正确划分正负样本时，几何间隔最小的为误分类点，因此$\gamma <0$
• 当超平面正确划分超平面时，$\gamma \ge 0$,且越靠近*$\gamma$越大

策略：给定线性可分数据集X,设X中几何间隔最小的样本为（$x_{min},y_{min}$）,那么支持向量机找超平面的过程可以转化为以下带约束条件的优化问题：
$$\begin{gathered} \max \gamma \\ s.t.{\gamma }_i\ge \gamma ,i=1,2,...,m \end{gathered}$$
$$\begin{gathered} \underset{w,b}{\max }\frac{y_{min(w^T{x}_{min}+b)}}{||w||} \\ s.t.\frac{y_i(w^{T}x+b)}{||w||}\ge \frac{y_{min}(w^T{x}_{min}+b)}{||w||},i=1,2,...,m \end{gathered}$$
$$\begin{gathered} \underset{w,b}{\max }\frac{y_{min(w^T{x}_{min}+b)}}{||w||} \\ s.t.y_i(w^{T}x+b)\ge y_{min}(w^T{x}_{min}+b),i=1,2,...,m \end{gathered}$$
假设该问题的最优解为（$w^{\ast },b^{\ast }$）,那么（$\alpha w^{\ast },\alpha b^{\ast }$）,$\alpha \in R^{+}$也是最优解，且超平面也不变；
所以还需要对$w,b$做一定的限制才能使上述问题有可解的唯一解；
不妨令$y_{min}(w^T{x}_{min}+b)=1$,因此对于特定的$(x_{min},y_{min})$来说，能使$y_{min}(w^T{x}_{min}+b)=1$的$\alpha$有且仅有一个；
上述问题进一步转化为：
$$\begin{gathered} \underset{w,b}{\max }\frac{1}{||w||} \\ s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2...,m \end{gathered}$$

为方便计算，再次转换为：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.1-y_i(w^T{x}_i+b)\le 0,i=1,2...,m \end{gathered}$$
支持向量机通常采用拉格朗日对偶来求解。

定义上述函数的拉格朗日对偶函数$\Gamma (\mu ,\lambda )$为$L(x,\mu ,\lambda )$关于x的下确界，即：
$$\Gamma (\mu ,\lambda )=\underset{x\in D}{\inf }(f(x)+\sum _{i=1}^m{\mu }_i{g}_i(x))+\sum _{j=1}^n{\lambda }_j{h}_j(x)$$
对偶函数$\Gamma (\mu ,\lambda )$具有的性质：

• 无论上述优化问题是否为凸优化问题，其对偶函数恒为以凹函数；
• 当$\mu \ge 0$时，$\Gamma (\mu ,\lambda )$构成了上述优化问题最优值$p^{\ast }$的下界，即$\Gamma (\mu ,\lambda )\le p^{\ast }$

定义在满足$\mu \ge 0$这个约束条件下求对偶函数最大值的优化问题为拉格朗日对偶问题
$$\begin{gathered} \max \Gamma (\mu ,\lambda ) \\ s.t.\mu \ge 0 \end{gathered}$$
设该优化问题的最优值为$d^{\ast }$,显然$d^{\ast }\le p^{\ast }$,此时称为“弱对偶性“成立；
若$d^{\ast }=p^{\ast }$，则称为”强对偶性“成立；

主问题：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.1-y_i(w^T{x}_i+b)\le 0,i=1,2...,m \end{gathered}$$
拉格朗日函数：
$$\begin{gathered} L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b)) \\ =\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m{\alpha }_i{y}_i{w}^T{x}_i-b\sum _{i=1}^m{\alpha }_i{y}_i \end{gathered}$$
若将$w,b$合并为$\hat{w}=(w;b)$,显然上式是关于$\hat{w}$的凸函数，求一阶导令其等于0.然后带回即可得到最小值。

软间隔算法原理：
在现实任务中，线性不可分的情形才是最常见的，因此需要允许支持向量机犯错；
从数学角度，软间隔就是允许部分样本不满足下式的约束条件
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.1-y_i(w^T{x}_i+b)\le 0,i=1,2...,m \end{gathered}$$
所以，可以将必须严格执行的约束条件转化为具有一定灵活性的损失；
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\ell }_{0/1}(y_i(w^T{x}_i+b)-1)$$
其中${\ell }_{0/1}$是“0/1损失函数”
ℓ 0 / 1 ( z ) = { 1 , i f   z < 0 0 , i f   z ≥ 0 ℓ_{0/1}(z)={1,if z<00,if z≥0

ℓ0/1​(z)={1,if z<00,if z≥0​
$C>0$是一个常数，用来调节损失的权重；
当$C\to +\infty$,会迫使所有样本的损失为0，进而退化为严格执行的约束条件，退化为硬间隔；

由于${\ell }_{0/1}$非凸，非连续，数学性质不好，所以常用一些数学性质较好的“替代损失函数”来替代它，软间隔支持向量机通常采用hinge损失来替代它
$$hinge损失：{\ell }_{hinge}(z)=max(0,1-z)$$
替换上式可得
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^{m}max(0,1-y_i(w^T{x}_i+b))$$
引入松弛变量${\xi }_i$,上述优化问题等价于
$$\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=0,1,...,m \end{gathered}$$

支持向量回归：
相比于线性回归用一条线来拟合训练样本，支持向量回归采用一个以$f(x)=w^{T}x+b$为中心，宽度为$2\epsilon$的间隔带来拟合训练样本。
因此支持向量回归优化问题可写成：
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\ell }_{\epsilon }(f(x_i)-y_i)$$
其中${\ell }_{\epsilon }(z)$为$\epsilon$不敏感损失函数
ℓ ε ( z ) = { 0 , i f   ∣ z ∣ ≤ ε ∣ z ∣ − ε , i f   ∣ z ∣ > ε ℓ_{\varepsilon}(z)={0,if |z|≤ε|z|−ε,if |z|>ε

ℓε​(z)={0,if ∣z∣≤ε∣z∣−ε,if ∣z∣>ε​
同软间隔支持向量机，引入松弛变量${\xi }_i$,令
$${\ell }_{\epsilon }(f(x_i)-y_i)={\xi }_i$$
当$|f(x_i)-y_i|\le \epsilon \Rightarrow {\xi }_i=0$
当$|f(x_i)-y_i|>\epsilon \Rightarrow {\xi }_i=|f(x_i)-y_i|-\epsilon$
所以$$-\epsilon -{\xi }_i\le f(x_i)-y_i-\epsilon \le \epsilon +{\xi }_i$$
进而优化问题改写为
$$\begin{gathered} \underset{w,b,{\xi }_i}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i \\ s.t.-\epsilon -{\xi }_i\le f(x_i)-y_i-\epsilon \le \epsilon +{\xi }_i \\ {\xi }_i\ge 0,i=0,1,...,m \end{gathered}$$