【Abee】吃掉西瓜——西瓜书学习笔记（五）

本文主要是介绍【Abee】吃掉西瓜——西瓜书学习笔记（五），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

支持向量机（Support Vector Machine，SVM）

【内容包含第六章】

间隔与支持向量

核函数

软间隔（soft margin）

正则化(regularization)

支持向量回归（Support Vector Regrassion,SVR）

核方法

间隔与支持向量

分类学习的主要思想是在样本空间中找到一个划分超平面，将不同样本分开。

超平面可以定义为

$w^{T}x+b=0$

其中w是法向量，决定超平面的方向，b是位移项，决定超平面到原点的距离。

样本空间中任意点到超平面（w，b）的距离为（根据点到平面的距离公式，这里是超平面，应该是广义的）

$r=\frac{\left |w^{T}x+b \right |}{\left \| w \right \|}$

令

$\left\{\begin{matrix} w^{T}x+b\geq +1,y_{i}=+1 \\ w^{T}x+b\geq +1,y_{i}=-1 \end{matrix}\right.$

离超平面最近的几个样本点（可能不止正反两个）使上式成立，被称为支持向量（support vector），异类支持向量的距离和为

$r=\frac{2}{\left \| w \right \|}$

即 间隔（margin）

支持向量机即使间隔最大化

$\begin{matrix} min_{w,b}\frac{1}{2}\left \|w \right \|^{2}\\ s.t. y_{i}(w^{T}x+b)\geq 1 \end{matrix}$

对偶问题(引入拉格朗日乘子 $\alpha _{i}$ )

$\begin{matrix} max_{\alpha }\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 , a_{i}\geq 0\end{matrix}$

解出 $\alpha _{i}$ 后即可得到模型的w，b

求解的方法主要是二次规划算法，比如SMO（Sequential Minimal Optimization），每次更新两个参数，把其他的变量固定，不断迭代直至收敛（每次选取的两个变量对应的样本之间的间隔最大，可以尽快的收敛）

核函数

并非所有问题都是线性可分的，需要把样本从原始空间映射至高维空间，则模型可以表示为

$f(x)=w^{T}\phi (x)+b$

$\begin{matrix} min_{w,b}\frac{1}{2}\left \|w \right \|^{2}\\ s.t. y_{i}(w^{T}\phi (x)+b)\geq 1 \end{matrix}$

相应的对偶问题

$\begin{matrix} max_{\alpha }\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}\phi(x_{i})^{T}\phi(x_{j})\\ s.t. \sum_{i=1}^{m}\alpha _{i}y _{i}=0 , a_{i}\geq 0\end{matrix}$

假设存在核函数 $\kappa (x_{i},x_{j})$ (kernel function)

$\kappa (x_{i},x_{j})=\phi(x_{i})^{T}\phi(x_{j})$

此时模型为

$f(x)=\sum_{i=1}^{m}\alpha _{i}y_{i}\kappa (x,x_{i})+b$

只要一个对称函数所对应的核矩阵半正定，就能作为核函数使用，，一个半正定核矩阵总是能找到一个与之对应的映射 $\phi$ ,隐式的定义了一个 再生核希尔伯特空间（Reproducing Kernel Hilbert Space，RKHS）

常用的核函数：线性核、多项式核、高斯核、拉普拉斯核、Sigmoid核

软间隔（soft margin）

虽然可以通过升维来实现线性可分，不过仍然是很困难的，引入软间隔的概念，即允许SVM在一些样本上出错

$min_{w,b }\frac {1}{2} \left \| w \right \|^{2} +C\sum_{i=1}^{m}\iota _{\frac {0}{1}}(y_{i}(w^{T}x_{i}+b)+1)$

$\iota _{\frac {0}{1}}(z)=\left\{\begin{matrix} 1,if z<0\\ 0,otherwise \end{matrix}\right.$

由于 $\iota _{\frac {0}{1}}$ 数学性质不好，常用的替代损失函数：

hinge损失： $\iota _{hinge}(z)=max(0,1-z)$

指数损失: $\iota _{exp}(z)=exp(-z)$

对率损失： $\iota _{log}(z)=log(1+exp(-z))$

引入松弛变量 $\xi _{i}\geq 0$ ,软间隔支持向量机为

$\begin{matrix} max_{w,b,\xi _{i} }\frac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{m}\xi _{i} \\ s.t. y_{i}(w^{T}x^{i}+b)\geq 1-\xi _{i}\\ \xi _{i}\geq 0,i=1,2,3,\cdots ,m\end{matrix}$

正则化(regularization)

$min_{f}\Omega (f)+C\sum_{i=1}^{m}l(f(x_{i},y_{i}))$

其中 $\Omega (f)$ 是正则化项，也称为 结构风险（structural risk），C为正则化常数， $L_{p}$ 为常用的正则化项， $L_{2}$ 范数 $\left \| w \right \|_{2}$ 倾向于w的分量取值均衡， $L_{0},L_{1}$ 范数则倾向于w分量尽量稀疏。

支持向量回归（Support Vector Regrassion,SVR）

SVR的损失计算允许f(x)和y之间有最小 $\epsilon$ 的偏差，若样本落入2 $\epsilon$ 的间隔带中，被认为是正确预测，不计损失。

$\begin{matrix} min_{f}\Omega (f)+C\sum_{i=1}^{m}(\xi _{i}+\hat \xi _{i})\\ s.t. f(x_{i})-y_{i}\leq \epsilon +\xi _{i} \\ y_{i}-f(x_{i})\leq \epsilon +\hat \xi _{i} \\ \xi _{i}\geq 0,\hat \xi _{i}\geq 0,i=1,2,\cdots ,m \end{matrix}$