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