浙江大学《机器学习》 支持向量机SVM（一）

线性可分定义

• 线性：二维中的直线，三维中的平面……
• $$二分类问题\{\begin{array}{rlr}& 线性可分& \\ & 线性不可分& \end{array}$$

问题描述

• 支持向量机算法
  1.解决线性可分问题
  2.结论推广到线性不可分的情况

• Q：如果一个数据集线性可分的，那么存在无限多个超平面可以对数据进行二分类，那么 哪一个超平面最好呢？

  
  A:基于最优化理论，选取使间隔最大的超平面
  注意 SVM寻找的最优分类直线应满足：
  1.该直线分开了两类
  2.该直线最大化间隔（margin）
  3.该直线处于间隔的中间，到所有SVM的距离相等（确保唯一性）

优化问题

• 调节系数倍数使得支持SVM处的$|w^T{x}_i+b|=1$，此时$d=\frac{1}{|w|}$,故 最小化$\frac{1}{2}{||w||}^2$→最小化$|w|$→最大化$d$

可以看到，这是凸优化问题（CONVEX OPTIMIZATION)中的二次规划问题。

• 二次规划定义
  1.目标函数（Objective Function)是二次项
  

  2.限制条件是一次项
  
  这样的凸优化问题，要么无解，要么只有唯一最小值。
  凸优化问题只有一个全局最小值，总可以用梯度下降法求解，所以可以视为已经解决的问题。

线性不可分情况

线性不可分情况下不存在$w$和$b$满足上面的限制条件
1.适当放松限制条件

2.增加新的限制
最小化：同时使得 ${\delta }_i$之和尽量小，比例因子$C$平衡两项，由人为设定

算法的超参数（HYPER PARAMETER)： 人为事先设定的参数
$$\{\begin{array}{rlr}& 超参数很少的算法模型：SVM& \\ & 超参数很多的算法模型：人工神经网络、卷积神经网络& \end{array}$$

→

低维到高维的映射

• $$扩大可选函数范围?\begin{array}{rlr}& 直接产生更多可选函数eg.人工神经网络、决策树& \\ & 将特征空间由低维映射到高维eg.SVM& \\ & （在高维空间仍然用线性超平面对数据分类）& \end{array}$$

• Q：
  

  A：
  
  
  由人为指定二维到五维的映射$?(X)$后，可以将数据集分为$\ge 0$和$<0$两类

• 定理
  假设：
  1.在一个M维空间上随机取N个训练样本，随机的对每个训练样本赋予标签+1或-1
  2.这些训练样本线性可分的概率为$P(M)$
  结论：
  当$M\to \infty$时，$P(M)=1$

这个定理说明，将训练样本由低维映射到高维，可以增加线性可分的概率。

• 高维空间的SVM优化问题
  $X_i$→$?(X_i)$；
  $w$维度与$X_i$维度相同→$w$维度与$?(X_i)$维度相同。

核函数的定义

不用具体知道$?(X_i)$的值，只需知道$K(X_1,X_2)$（一个数值），就能够求解出结果。

• 已知映射$?$求核函数$K$
  

• 已知核函数$K$求映射$?$
  
  

• 核函数$K$和映射$?$是一一对应的关系
  Mercer定理：
  
  →这个定理可以用于证明高斯核函数
  

原问题（PRIME PROBLEM）和对偶问题（DUAL PROBLEM)

• 定义

  Step.1原函数
  假设有K个不等式，m个等式
  
  Step.2定义函数$L(w,\alpha ,\beta )$
  
  Step.3对偶函数

  $L(w,\alpha ,\beta )$遍历所有定义域上的$w$,找到使$L(w,\alpha ,\beta )$最小的，同时将这个最小的函数值赋值给$\theta (\alpha ,\beta )$

• 定理
  1.定理一：对偶定理（DUALITY THEOREM)证明：
  

引申：对偶差距（DUALITY GAP）

KKT条件

2.定理二：强对偶定理（STRONG DUALITY THEOREM)