机器学习之支持向量机算法（五）

支持向量机（Support Vector Machine）

要解决的问题：什么样的决策边界才是最好的？
特征数据本身如果很难分，怎么办？
计算的复杂度怎么样？能实际应用吗？
目标：基于上述问题对SVM进行推导

三条线都能够做分类，但是那一条线最好呢？

决策边界：选出来离雷区最远的（雷区就是边界上的点，要large margin）

数学推导过程：

机器学习之支持向量机算法（五）

这里我们假设 $x^1$ 、 $x^2$ 为所求平面（ $w^Tx=-b$ ）上的两个点 ,满足上面的（1）式，其中w为垂直于平面的法向量，由于w垂直于平面，所以w垂直于平面的任意一条直线，所以有（2）式， $x$ 为平面外面的一点，到平面的距离等于 $\vec{xx^1}$ 在法向量上的投影。

基于以上的式子，这里给出距离的方程：
机器学习之支持向量机算法（五）
而对于我们的数据集标签有如下的定义：

数据集：（x1,y1） (x2,y2) (x3,y3)
Y 为样本的类别：当X 为正例的时候，Y =+1 当X 为负例的时候 Y=-1
决策方程： $y(x) = w^T\Phi(x) + b$ (其中 $\Phi (x)$ 是对数据做了变换)
$=> y(x_i)>0 \Leftrightarrow y_i =+1 \\ y(x_i) < 0 \Leftrightarrow y_i =-1$

$=> y_iy(x_i)>0$

优化目标

通俗的解释：找到一条线（w,b），使得离该线最近的点能够最远

将点到直线的距离化简得： $\frac{y_i \cdot \big(w^T \cdot \Phi(x_i)+b \big)}{ \lVert w \lVert}$ ,这里是由（3）式推导。

目标函数：
- 放缩变换：对于决策方程（3），可以通过放缩使得其结果值>=1,
  
  即 $y_i \cdot \big(w^T \cdot \Phi(x_i)+b \big) >= 1$
- 优化的目标： $argmax_{w,b} \langle {\frac{1}{ \lVert w \lVert }min_i \big(y_i \cdot \big(w^T \cdot \Phi(x_i)+b \big)\big)}$ ,由于 $y_i \cdot \big(w^T \cdot \Phi(x_i)+b \big) \geqslant 1$ ，只需要考虑 $arg max_{w,b}\frac{1}{ w}$ , 这就是我们的目标函数
目标函数的求解：
- 当前目标： $max_{w,b} \frac{1}{ \lVert w \lVert}$ ，约束条件为： $y_i\cdot \big(w^T \cdot \Phi(x_i)+b \big) \geqslant 1$
- 将上面的求极大值问题转换为求极小值问题 => $min_{w,b} \frac{1}{2}w^2$
- 如何求解：应用拉格朗日乘子法求解
拉格朗日乘子法

拉格朗日乘子法是经典的求解最小值的数学方法，更多原理可以进入上面的链接

根据上述原理，我们的目标函数可以转化成：
$L(w,b,\alpha ) = \frac{1}{2}w^2 - \sum_{i=1}^{n} \alpha_i\big(y_i(w^T\cdot \Phi(x_i)+b )-1\big)$
对于上式的约束条件为： $y_i \cdot \big(w^T \cdot \Phi(x_i)+b \big) \geqslant 1$

函数的对偶性和凸优化可以查找一下资料

对w求偏导： $\frac{\varphi L}{\varphi w}=0 \Rightarrow w=\sum_{i=1}^{n} \alpha_iy_i \Phi(x_n)$

对b求偏导： $\frac{\varphi L}{\varphi b}=0 \Rightarrow 0=\sum_{i=1}^{n} \alpha_iy_i$

将上面两个式子代入原函数中：
$=\sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j(\Phi(x_i)\cdot \Phi(x_j))$
继续对 $\alpha$ 求极大值： $max_{\alpha}(上式)$ ，条件为： $\alpha_i >0$ 且 $0=\sum_{i=1}^{n} \alpha_iy_i$