机器学习札记18——SVM(1)

浏览: 1269

SVM支持向量机

简介

SVM(support vector machine)是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使其区别于感知机,感知机只是找到一个分离超平面。

  • SVM是非线性分类器
  • 学习策略:间隔最大化,等价于求解凸二次规划问题或者说正则化的合页损失函数的最小化问题
  • 学习算法:求解凸二次规划的最优化算法

分类

  • 线性可分支持向量机
  • 线性支持向量机
  • 非线性支持向量机

当训练数据线性可分,通过间隔最大化,学习到一个线性可分支持向量机:硬间隔支持向量机;数据近似线性可分,得到线性支持向量机;当数据线性不可分时,得到非线性支持向量机。

线性可分支持向量机

思想

  • 学习目标:在特征空间中找到一个分离超平面S,由w \bullet x+b=0决定,将实例分成不同的正类和负类
  • w是法向量,b是截距。法向量指向的那侧是正类,另一侧是负类
  • 通过间隔最大化求出的分离超平面具有唯一性

定义线性可分支持向量机

  • 分离超平面w^* \bullet x+b^* =0
  • 分类决策函数f(x)=sign(w^* \bullet x+b^* )
    • 到决策函数的距离大于1,表示正类
    • 到决策函数的距离小于1,表示负类

函数间隔和几何间隔

一个点到分离超平面的距离可以表示分类预测的确信程度。通常使用|w \bullet x+b|来表示点x到超平面的远近

  • w \bullet x+b > 0,y = +1或者w \bullet x+b < 0,y = -1都表示将将数据正确分类:即w \bullet x+b和类标记y的符号是一致的
  • 在给定数据集T,超平面(w,b)关于样本点(x_i,y_i)的函数间隔:\hat \gamma_i=y_i(w \bullet x_i+b)定义:超平面(w,b)关于训练数据集T的函数间隔,为所有T中样本点的函数间隔的最小值:\hat \gamma=\mathop {\min}\limits_{i=1,2,...,N} \hat \gamma_i

函数间隔表示分类预测的准确性和确信度。当w,b成比例的变化时,超平面并没有变化,因此需要规范化,加上||w||,此时变成了几何间隔。

几何间隔=\frac {函数间隔} {||w||}

点到超平面的距离

设样本点A到超平面(w,b)的距离为\gamma_i

  • 如果点在超平面正的一侧,即:y_i = +1,距离为:\gamma_i=\frac {w \bullet x_i+b} {||w||}
  • 如果点在超平面负的一侧,即:y_i = -1,距离为:\gamma_i=-(\frac {w \bullet x_i+b} {||w||})

统一地:当样本点被超平面正确分类时,点到超平面的距离为\gamma_i=y_i(\frac {w \bullet x_i+b} {||w||})那么,当||w||=1时候,函数间隔和几何间隔是相等的。

如果w,b等比例的变化,函数间隔相应的变化,但是几何间隔是不变的

间隔最大化

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。几何间隔最大的分离超平面是唯一的。这里的间隔最大化称之为硬间隔最大化

硬间隔最大化不仅能够将正负实例点分开,还能将最难分的实例点(距离超平面最近的点)也能分开,对应的模型为\mathop {\max} \limits_{w,b}\gamma
s.t. \qquad y_i({w \bullet x_i+b}{||w||}) \geq {\gamma}意思:

  • 最大化几何间隔
  • 约束条件表示的是超平面关于每个训练样本点的距离至少是\gamma

根据函数间隔和几何间隔的关系{\gamma}=\frac {\hat \gamma}{||w||},模型还可以表示为:\mathop {\max} \limits_{w,b}\frac {\hat \gamma}{||w||}
s.t. \qquad y_i(w \bullet x_i+b) \geq {\hat \gamma}

函数间隔不影响模型,就取\hat \gamma=1,那么最小化\frac {1}{||w||}和最小化\frac{1}{2}||w||^2等价(\frac{1}{2}方便求导)

线性可分支持向量机的最优化问题可以表示为凸二次优化问题:

最小化法向量:\mathop \min \limits_{w,b}\frac{1}{2} ||w||^2

约束条件:s.t. \qquad y_i(w \bullet x_i+b) \geq 0,i=1,2,...,N求解出上述两个的式子的解w^*,b^*就可以求出分离超平面w^* \bullet x+b^*和决策函数f(x)=sign(w^* \bullet x+b^*)

对偶问题

将线性可分支持向量机的最优化问题,通过拉格朗日对偶性,转换成求解对偶问题,得到对偶问题的最优解

  • 对偶问题更好求解
  • 自然引入核函数,推广到非线性支持向量机

如何构建对偶形式:

  • 引入拉格朗日乘子alpha_i \geq 0, i=1,2,3...,N,构建拉格朗日函数:L(w,b,\alpha)=\frac{1}{2}||w||^2 - \sum^N_{i=1}\alpha_iy_i(w \bullet x_i+b)+\sum ^N_{i=1}\alpha_i其中\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T为拉格朗日乘子向量
  • 原始问题的对偶问题是极大极小问题\mathop \max \limits_a \mathop \min \limits_{b,\alpha} L(w,b,\alpha)
  • L先对w,b求解极小,再对\alpha求解极大值
  • 具体过程见P_{120}-P_{123}
推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册