支持向量机

约 750 个字 预计阅读时间 2 分钟

定义

支持向量机(Support vector Machine)的核心思想是找到一个超平面（比样本空间低一维），把不同类别的数据分开并且使每个类别距超平面最近的点到超平面间隔(margin)最大，间隔最大是它与感知机的区别。

支持向量是离超平面最近的样本点，支持向量机通过最大化支持向量到超平面的距离来选择最佳的超平面。

VC 维与结构风险最小化

在理论上，SVM认为：分类器对未知数据进行分类所产生的期望风险是由两部分组成： * 从训练集合数据所得的经验风险 * 置信风险，与分类器的VC维及训练样本数目有关

线性可分支持向量机

对于n个训练数据\((x_i,y_i)\in D(i=1,...,n) \(，记其类标签为1或-1分别代表了正样本或负样本。支持向量机从这些训练数据出发，寻找一个最优的超平面，其方程为\)w^Tx+b=0 \(，这里的\)w=(w_1,w_2,...,w_d) \(为超平面法向量，与超平面的方向有关，\)b\)为偏置项，决定了超平面与原点的距离。

显然，为了每个样本都被正确分类，要求对于正样本满足\(w^Tx+b\geq 0 \(，对于负样本\)w^Tx+b< 0 \(，样本空间任意样本到该平面的距离可以表示为\)r=d(w,b,x)=\frac{|w^Tx+b|}{||w||_2}(||w||_2=\sqrt{w^Tw}) \(。为了使\)w\)唯一，增加一个约束条件$r_{\min_i|w^Tx+b|} \(，即离超平面最近的正负样本代入超平面方程后其绝对值为1。于是对于超平面的约束变成\)y_i(w^Tx+b)\geq 1 $

两类样本中距离超平面最近的数据的距离可以用如下公式计算：$$\gamma=d(w,b)=min_{(x_k,y_k=1)}d(w,b,x_k)+min_{(x_m,y_m=-1)}d(w,b,x_m)\=min_{(x_k,y_k=1)}\frac{|w^Tx_k+b|}{||w||2}+min{||w||}\frac{|w^Tx_m+b|2}\=\frac{1}{||w||_2}(min $$}|w^Tx+b|+min_{x_m,y_m=1}|w^Tx+b|)=\frac{2}{||w||_2

SVM的目标就是在满足约束条件的情况下使\(\gamma\)最大，即等价于使\(w\)最小，为了方便计算，一般写作$$min_{w,b}\frac{||w||^2}{2}=min_{w,b}\frac{1}{2}w^Tw\y_i(w^Tx_k+b)\geq 1, i=1,2,...,n $$

松弛变量

如果不能完全用一个线性的超平面把不同样本完全分隔开，那么就应该设法在最大化支持向量到超平面的距离同时使不满足的样本数目尽可能少。

核函数

因为在当前维度数据未必是线性可分的，所以可以选择使用核函数把数据映射到更高的维度，在这个维度中，数据是线性可分的。如果原始空间是有限维，那么一定存在一个高维空间使数据线性可分。