Support Vector Machine(SVM)

对下图中的数据点进行分类：

要解决的问题：

• 什么样的决策边界最好？
• 特征数据本身若很难分应怎么处理？
• 计算复杂度如何？

决策边界

若将数据点比喻为地雷，则决策边界为选出的离雷区最远的（雷区就是边界上的点，要large margin）

距离的计算

数据标签定义

数据集：/((X_{1},Y_{1})(X_{2},Y_{2})…(X_{n},Y_{n})/)
Y为样本的类别：当X为正例时Y=+1，当X为负例时Y=-1
决策方程：

/[y(x)=w^{T}/phi(x)+b => /begin{cases}y(x_{i})>0=>y_{i}=+1//y(x_{i})<0=>y_{i}=-1/end{cases}=>y_{i}·y(x_{i})>0
/]

其中/(/phi(x)/)为数据点由低维到高维的变换函数

优化的目标

通俗的解释就是找到一条线使得离该线最近的点（雷区）能够最远
将点到直线的距离化简得：

/[y_{i}·(w^{T}·/phi(x_{i})+b)/over||w||
/]

由于/(y_{i}·y(x_{i})>0/)所以去掉绝对值后原式依然成立

目标函数

放缩变换：对于决策方程（w,b）可以通过放缩使/(|Y|/geq1=>y_{i}·(w^{T}·/phi(x_{i})+b)/geq1/)
(为使其易于化简，认为其恒大于1）
优化目标：
由于/(y_{i}·(w^{T}·/phi(x_{i})+b)/geq1/)，只需要考虑/({/underset {w,b} { /operatorname {arg/,max} } /, /left(1/over||w||/right)}/)
当前目标：/({/underset {w,b} { /operatorname {max} } /, /left(1/over||w||/right)}/)，约束条件：/(y_{i}·(w^{T}·/phi(x_{i})+b)/geq1/)
常规套路：将求解极大值问题转换成求解极小值问题/(=>{/underset {w,b} { /operatorname {min} } /, /left(w^{2}/over2/right)}/)（w为向量）
求解方法：拉格朗日乘子法

拉格朗日乘子法

带约束的优化问题：

原式转换：

我们的式子：
（设法用a表示w和b）

SVM求解

• 分别对w和b求偏导，分别得到两个条件（由于对偶性质）
• 对w求偏导：
• 对b求偏导：
• 带入原始：
  
  *继续对a求极大值：
  条件：
  *极大值转换成求极小值：
  条件：

SVM求解实例

数据：三个点，其中正例X1(3,3),X2(4,3),负例X3(1,1)
求解：
约束条件：/(/alpha_{1}+/alpha_{2}-/alpha_{3}=0///alpha_{i}/geq0,i=1,2,3/)

将数据代入原式：
由于：/(/alpha_{1}+/alpha_{2}=/alpha_{3}
化简可得：
分别对/)/alpha_{1}/(和/)/alpha_{2}$求偏导（约束条件 /(/alpha_{i}/geq0,i=1,2,3/))，偏导等于0可得：
/(/alpha_{1}=1.5///alpha_{2}=-1/) 不满足约束条件
/(/alpha_{1}=0///alpha_{2}=-2/13/) 不满足约束条件
/(/alpha_{1}=0.25///alpha_{2}=0/) 满足约束条件
最小值在（0.25，0，0.25）处取得
将/(/alpha/)结果带入求解：

/[w=/sum/limits_{i=1}^n/alpha_{i}y_{i}/phi(x_{n})//
w=/frac{1}{4}*1*(3,3)+0*1*(4,3)+/frac{1}{4}*-1*(1,1)=(/frac{1}{2},/frac{1}{2})//
b=y_{i}-/sum/limits_{i=1}^{n}/alpha_{i}y_{i}(x_{i}x_{j}=1-(/frac{1}{4}*1*18+/frac{1}{4}*(-1)*6)=-2
/]

平面方程为：/(0.5x_{1}+0.5x_{2}-2=0/)

支持向量

即真正发挥作用的数据点，即/(/alpha/)不为0的点（处于雷区的点）

soft-margin

软间隔：有时候数据中会有一些噪音点（干扰点），如果考虑的话决策边界的效果会变差

为了解决该问题，引入松弛因子/(xi_{i}/):

/[y_{i}(w·x_{i}+b)/geq1-/xi_{i}
/]

新的目标函数：

/[min/frac{1}{2}||w||^{2}+C/sum/limits_{i=1}^{n}/xi_{i}
/]

C是一个需指定的参数
当C趋近于很大时：意味着分类严格不能有误
当C趋近于很小时：意味着可以有更大的错误容纳
因为要求极小值，当C趋于很大时，只有/(/xi_{i}/)很小时才能满足需要；当C趋于很小时，即使/(/xi_{i}/)较大也可容易地找到极小值

拉格朗日乘子法

引入松弛因子后公式为：

/[L(w,b,/xi,/alpha,/mu)=/frac{1}{2}||w||^{2}+C/sum/limits_{i}^{n}/xi_{i}-/sum/limits_{i}^{n}/alpha_{i}(y_{i}(w·x_{i}+b)-1+/xi_{i})-/sum/limits_{i}^{n}/mu_{i}/xi_{i}//
w=/sum/limits_{i}^{n}/alpha_{i}y_{i}/phi(x_{n})
/]

约束：

/[0=/sum/limits_{i}^{n}/alpha_{i}y_{i}//
C-/alpha_{i}-/mu_{i}=0//
/alpha_{i}/geq0 /mu_{i}/geq0
/]

解法与先前相同

低维不可分问题

核变换

当低维不可分的时候，映射至高维后是否可分？

目标：找到一种变换函数/(/phi(x)/)，从而实现将数据由低维向高维映射

高斯核函数

公式：


尽量不要尝试自己开发新的核函数:-(

reference

https://www.bilibili.com/video/BV1dZ4y1b7in?p=129&share_source=copy_web&vd_source=bc572b96767067a4ac4c1a2d53fc8d39