支持向量机

间隔与支持向量

​ 在样本空间中寻找一个超平面，将不同类别的样本分开

​ “正中间”的：鲁棒性最好，泛化能力最强

​

​

对偶问题

• 拉格朗日乘子法

  • 第一步：引入拉格朗日乘子ai>=0 得到拉格朗日函数

  

  • 第二步：令L(w,b,a)对w和b的偏导为零可得

  

  • 第三步：回代可得

  

  

  最终模型

  

  ​

  KKT条件

  

  ​

  必有ai=0或yif(xi)=1

  解的稀疏性：

  ​ 训练完成后，最终模型仅与支持向量有关

核函数

• 特征空间映射

  如果不存在一个能正确划分两类样本的超平面，将样本从原始空间映射到一个更高维的特征空间，是样本在这个特征空间内线性可分

  

  如果原始空间是有限维（属性数有限），那么一定存在一个高维特征空间使样本可分

• 在特征空间中

  设样本x 映射后的向量为ϕ(x),划分超平面为f(x)=wTϕ(x)+b

  • 原始问题

  

  • 对偶问题

  

  

  • 预测

  

• 核函数

  • 基本思路： 设计核函数

  k(xi,xj)=ϕ(xi)Tϕ(xj)

  绕过显式考虑特征映射、以及计算高维内积的困难

  • Mercer定理

  若一个对称函数所对应的核矩阵半正定，则它就能作为核函数来使用

  任意一个核函数，都隐式地定义了一个RKHS(Reproducing Kernel Hilbert Space,再生核希尔伯特空间)

  “核函数选择” 成为决定支持向量机性能的关键

• 常用核函数

  

  基本经验：文本数据常用线性核，情况不明时可先尝试高斯核

  可通过函数组合得到

  ​ 若k1 和k2 是核函数，则对任意正数γ1、γ2和任意函数g(x)

  均为核函数

软间隔与正规化

• 软间隔

  

  现实中很难确定合适的核函数，使训练样本在特征空间中线性可分，即便貌似线性可分，也很难判定是否是因过拟合造成的

  引入软间隔，允许在一些样本上不满足约束

• 优化目标

  • 基本思路：

  最大化间隔的同时，让不满足约束 yi(wTxi)+b≥1 的样本尽可能少

  

  ​

• 替代损失

  

  • 替代损失函数性质较好，一般是0/1损失函数的上界
  • 采用替代损失函数，是在解决困难问题时的常见技巧
  • 求解替代函数得到的解是否仍是原问题的解？理论上称为替代损失的“一致性”问题

  软间隔支持向量机

  • 原始问题

  

  • 引入“松弛变量”

  

  

  • 对偶问题

  

  根据KKT条件可知，最终模型仅与支持向量有关，也即采用hinge损失函数后仍保持了SVM解的稀疏性

• 正规化

  • 正规化可理解为“罚函数法”

  通过对不希望的结果施以惩罚，使得优化过程趋向于希望目标

  • 从贝叶斯估计的角度，则可认为是提供了模型的先验概率

支持向量回归

• 示意图

  ​

  

  ​ 基本思路： 允许模型输出与实际输出间存在2ε 的差别

• ε-不敏感损失函数

  

• 支持向量回归

  • 原始问题

  

  • 对偶问题

  

  • 预测

  

  ​

核方法

• 表示定理

  

  ​

  ​ 基于表示定理能得到很多线性模型的“核化”版本

• 核线性判别分析

  • 学习目标

  

  • 分析后

  

  ​