支撑向量机(Support Vector Machines): 在19世纪末火爆十年分类模型

学习内容：目标函数，计算过程和算法步骤，线性SVM，增加软间隔达到线性可分的SVM（分类效果更好），核函数，参数的计算方法SMO。

各种概念

1. 线性可分SVM：数据集存在一条抽象的线可以完全将数据分成两类。
   
2. 线性SVM：允许一定错误率的前提下，才满足第1条。
   
3. 非线性SVM：核函数。线性可分SVM和线性SVM都可以通过增加核函数达到非线性的效果。

在中学数学知识中，下图中直线$L$函数的方差为$y=\frac{1}{2}x+1$

我们用线代的知识对函数做个变形：
$$y=\frac{1}{2}x+1$$
$$-x+2y+1=0$$
抽取参数后：
$$(-1,2)\left(\begin{array}{c}x\\ y\end{array}\right)+1=0$$
$(-1,2)$ 这个向量我们可以看出是直线$L$的一条法线（垂直于 $L$）将这个向量记为$\vec{w}$，将参数向量记为 $\vec{x}$ ，将截距项（常亮）记为b，于是有：
$$f(\vec{x})={\vec{w}}^T\cdot \vec{x}+b$$
如果参数 $\vec{x}$是n维的，则 $\vec{w}$也是n维的，b是一维的。
若将样本点$x_0$带入${\vec{w}}^T\cdot \overrightarrow{x_0}+b>0$，则表示此点在法线同方向，同理小于0在法线逆方向。

使用核解决线性不可分

涉及核函数内容后面讲；

线性分类问题

实际上我们的痛苦不是分不出来，而是分割方式太多如何选择？

回顾中学计算点到直线距离的方式：
直线方程为$Ax+By+C=0$求点$(x_0,y_0)$到直线的距离
直接套公式：$$d=\frac{|A{x}_0+B{y}_0+C|}{\sqrt{A^2+B^2}}$$
由上文可知符号表方向，所以我们在此不考虑绝对值。$$d=\frac{A{x}_0+B{y}_0+C}{\sqrt{A^2+B^2}}$$
变形：$$d=\frac{A}{\sqrt{A^2+B^2}}{x}_0+\frac{B}{\sqrt{A^2+B^2}}{y}_0+\frac{C}{\sqrt{A^2+B^2}}$$
简写一下，满足$A^{\prime }，B^{\prime }$平方和为1即可：$$A^{\prime }{x}_0+B^{\prime }{y}_0+C^{\prime }$$
如上文也可以视为：$\vec{w}\cdot \vec{x}+b$

对于$\sqrt{A^2+B^2}$，可以理解为$$\sqrt{(w_1,w_2,...)\left(\begin{array}{c}{w}_1\\ w_2\\ ...\end{array}\right)}=\sqrt{w_1^2+w_2^2+...}$$
定义二范式：$$||\vec{w}||=(w_1,w_2,...)\left(\begin{array}{c}{w}_1\\ w_2\\ ...\end{array}\right)$$
则二范式的平方为$$||\vec{w}|{|}^2={\vec{w}}^T\cdot \vec{w}$$
所以n维的点到直线的距离可以写成：
$$d(x_0,l)=\frac{\vec{w}\cdot \vec{x}+b}{||\vec{w}||}$$

在推导如何计算点到直线距离的时候我们忽略了绝对值（前面解释过是因为符号代表相对于法线的方向），但是样本中会有一个y值（定义负例为-1,正例为1）来标定这个样本的类别。那么我们可以将这个y值也放到公式中抵消符号：
$$d(x_0,l)=\frac{(\vec{w}\cdot \vec{x}+b)y^i}{||\vec{w}||}$$
接下来我们找到距离直线最近的样本点$i$。
$$\underset{i=1,2,...}{\min }(f(x^i;w,b))$$
再比较每一条直线$j$对应最近的点，找到距离最近点最远的直线。
$$\underset{j=1,2,...}{\max }(\underset{i=1,2,...}{\min }(f(x^i;w,b)))$$

---

一不小心就推到了目标函数
我们总是想要找到使得$w_j,b_j$在这个目标函数取最大。最小距离取最大
$$w^{\ast },b^{\ast }⟹\underset{j=1,2,...}{\mathrm{argmax}}(\underset{i=1,2,...}{\min }(\frac{(w\cdot x^{(i)}+b)\cdot y^{(i)}}{||w||}))$$

---

arg max ⁡ w , b { 1 ∣ ∣ w ∣ ∣ min ⁡ i [ y i ⋅ ( w T ⋅ Φ ( x i ) + b ) ] } \argmax_{w,b}\{\frac{1}{||w||}\min_i[y_i \cdot (w^T \cdot \Phi(x_i)+b)]\} w,bargmax​{∣∣w∣∣1​imin​[yi​⋅(wT⋅Φ(xi​)+b)]}

这个目标函数太复杂了，还能不能简化呢？
函数中有很大一部分是表示距离的，假设我们让他除以一个系数（这个系数就是最近点到直线的距离，也就是将最小距离视为单位1），这样表示距离的公式部分就可以知己省略。

• 新目标函数：
  $$\underset{w,b}{\mathrm{argmax}}\frac{1}{||w||}$$

建立目标函数

$$\underset{w,b}{\max }\frac{1}{||w||}\Rightarrow \underset{w,b}{\min }||w||\Rightarrow \underset{w,b}{\min }\frac{1}{2}||w|{|}^2$$
$$s.t.y_i(w^T\cdot \Phi (x_i)+b)\ge 1，i=1,2,\cdot \cdot \cdot ,n(n样本个数，n个约束条件)$$

插入知识点，凸优化可以将最大最小问题转化为最小最大问题
拉格朗日乘子法
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T\cdot \Phi (x_i)+b)-1)$$
注：实际上还包含不等式约束。

• 分别对w，b求偏导并令其为0：
  $$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum _{i=1}^n{\alpha }_i{y}_i\Phi (x_n)$$
  $$\frac{\partial L}{\partial b}=0\Rightarrow 0=\sum _{i=1}^n{\alpha }_i{y}_i$$
  
  
  
  

举例

线性支持向量机

为了得到最宽的分隔带，未必完全正确的分隔所以样本。

---

接下来求解线性SVM目标函数：
$$\begin{gathered} \underset{w,b,\xi }{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i \\ s.t.y_i(w\cdot x_i+b)\ge 1-{\xi }_i,i=1,2,\cdot \cdot \cdot ,n \\ {\xi }_i\ge 0,i=1,2,\cdot \cdot \cdot ,n \end{gathered}$$

$$\begin{gathered} 条件项：y_i(w\cdot x_i+b)-1+{\xi }_i\ge 0 \\ 每项乘{\alpha }_i(1,2,...,n){\alpha }_i(y_i(w\cdot x_i+b)-1+{\xi }_i) \\ 每项乘{\mu }_i(1,2,...,n){\mu }_i{\xi }_i \end{gathered}$$

拉格朗日函数:
$$L(w,b,\xi ,\alpha ,\mu )\equiv \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$$

对$w,b,\xi$求偏导:
$$\begin{gathered} \frac{\partial L}{\partial w}=0\Rightarrow w=\sum _{i=1}^n{a}_i{y}_i\varphi (x_n) \\ \frac{\partial L}{\partial b}=0\Rightarrow 0=\sum _{i=1}^n{a}_i{y}_i \\ \frac{\partial L}{\partial {\xi }_i}=0\Rightarrow C-a_i-{\mu }_i=0 \end{gathered}$$
回带这三个式子：

损失函数

就是所有样本的损失（点到支撑线的距离）之和：$$C\sum _{i=1}^n{\xi }_i$$

核函数

数据不总是线性可分的，对于非线性的数据处理的一种手段。

核技巧(kernel trick)：

1. 使用一个变换，将原空间的数据映射到新空间
2. 在新空间例用线性分类学习方法训练数据中学习分类模型。