目录
SVM是一种无监督机器学习方法,常用于二分类问题。其相较于逻辑回归,引入了核函数的概念,对非线性关系有更好的分类效果;同时由于对偶问题的引入,使得计算的复杂性由维度的大小转变为样本的数量,避免了维度爆炸。但是由于SVM的本质是二次规划问题,样本数量大的时候,需要占用大量的存储空间和时间,不容易实现;同时SVM解决多分类问题存在一定困难。
一、硬间隔SVM(Hard Margin SVM)
硬间隔SVM是一个二次凸规划问题,其形式为:
其推导过程为:
(1)列出原始目标函数和约束条件。
目标函数:使间隔最大(间隔指离分隔线最近点到分隔线的距离)
约束条件:分隔线两侧的所有点均属于同一类别
即:
其中,间隔(最小距离)的推导过程如下:
(2)表达式化简
目标函数中,由于w与x无关,所以可以将1/||w||提出来;
由第一步得到的约束条件可知,必定存在一个γ>0,使得所有样本到分隔线的距离>γ,即:
这样,可以将目标函数中的min后所有元素进行替换,即:
(3)最终形式
目标函数:将max化为min,转化为二次型
约束条件:由于最小距离等于1,所以所有样本的距离大于等于1
二、对偶问题(Dual Problem)
在本问题中,可以将上面推出的二次规划问题转化为对偶形式:
引入对偶形式后,其目的为:
(1)方便引入核函数
(2)使约束函数从由维度、样本数量有关,变为仅与样本数量有关,方便计算。
其推导过程使用了拉格朗日(Lagrange)乘子法,拉格朗日乘子法方法的推导可参考下面博客。我们在这里仅套用Lagrange乘子法。
深入理解拉格朗日乘子法(Lagrange Multiplier) 和KKT条件_lijil168的博客-CSDN博客_拉格朗日乘子法
1.将有约束问题转变为无约束问题
带入Lagrange函数以及KKT条件,得到如下形式:
2.强对偶关系
拉格朗日为凹函数,其仅有最小值,没有最大值。
而目前的形式需要求拉格朗日函数的最大值,无法求得。所以需要对问题进行转变。
拉格朗日函数满足强对偶关系,即min max f(x) = max min f(x),可将上式化简为:
3.计算拉格朗日函数的最小值
拉格朗日函数有唯一最小值,故极小值即为最小值。
极小值的计算方式为:令偏导数等于0
4.得到对偶形式
代回原目标函数,即可得到最终结果。
三、对偶形式的求解
1.KKT条件的引入
由KKT条件的第三个式子可知,只有处于支持向量上的点(yf(x)-1=0)才可以满足第三个条件。所以在SVM中,仅有在支持向量上的点才有意义
2.计算w和b
w和b即为确定超平面的参数。
w*的求解:直接带入
条件即可b的求解:由于仅有支持向量上的点起作用,所以代回支持向量上的样本点,对b进行求解。
四、软间隔SVM(Soft Margin SVM)
引入软间隔SVM的目的是:防止由于噪声数据而产生的过拟合现象。
1.Hinge Loss的引入
Hinge Loss设置了一个阈值,使得偏差数值尽可能小。其函数图像如下。
2.软间隔SVM的形式
Original: https://blog.csdn.net/weixin_48228548/article/details/124133393
Author: 力扣刷穿
Title: 【超详细】支持向量机(SVM)数学推导
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/649493/
转载文章受原作者版权保护。转载请注明原作者出处!