支持向量机算法
SVM算法和感知机,逻辑回归一样,都是经典的二分类算法。其中,支持向量机找到的分割超平面具有更好的鲁棒性,因而被广泛使用在了很多任务上。
一、常见的几何性质(欧氏空间)
⎩⎪⎨⎪⎧wTx1+b=0wTx2+b=0w为法向量wT(x1−x2)=0(式1)
⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧wTx1+b=0λwT∣∣w∣∣w+b=0∣∣w∣∣−b为原点到平面的距离offset=∣∣w∣∣−b(式2)
r=∣∣w∣∣∣wTx+b∣r为点到平面的距离(式3)
推导如下:
r=∣∣∣∣w∣∣2wTxw−∣∣w∣∣2−bw∣∣
=∣∣∣∣w∣∣2wTx+∣∣w∣∣2−b∣∣∣∣w∣∣
=∣∣w∣∣∣∣wTx+b∣∣=∣∣w∣∣∣wTx+b∣(式4)
2、SVM原始形式的导出(核心是最大化间隔)
如图所示:
给定一个二分类器数据集D={(x(n),y(n))}n=1N,其中,yn∈{+1,−1},如若两类样本线性可分,即存在一个超平面:
wTx+b=0(式5)
将两类样本分开,那么对于每个样本都有y(n)(wTx(n)+b)>0.
数据集D中每个样本x(n)到分割超平面的距离为:
r(n)=∣∣w∣∣∣∣wTx(n)+b∣∣=∣∣w∣∣y(n)(wTx(n)+b)(式6)
定义间隔r为整个数据集D中所有样本到分割超平面的最短距离:
r=nminr(n).(式7)
如若间隔r越大,则分割超平面对两个数据集的划分越稳定,不容易受到噪声等因素的影响。支持向量机的目标为:找到一个超平面(w∗,b∗)使得r最大,即:
w,bmaxrs.t.∣∣w∣∣y(n)(wTx(n)+b)≥r,∀n∈{1,⋯,N}(式8)
因为间隔为r=∣∣w∣∣1,令∣∣w∣∣⋅r=1,则(式8)等价于:
w,bmax∣∣w∣∣21s.t.y(n)(wTx(n)+b)≥1,∀n∈{1,⋯,N}(式9)
数据集中所有满足y(n)(wTx(n)+b)=1的样本点都称之为支持向量。对于一个线性可分的数据集,其分割超平面有很多个,但是间隔最大的超平面是唯一的. 下图给定了支持向量机的最大间隔分割超平面的示例,其中红色样本点为支持向量.
三、SVM参数的学习
将(式9)写成凸优化问题,形式如下:
w,bmin21∣∣w∣∣2(式10)
s.t.1−y(n)(wTx+b)≤0,∀n∈{1,⋯,N}
使用拉格朗日乘数法,(式10)的拉格朗日函数为:
L(w,b,λ)=21∣∣w∣∣2+n=1∑Nλn(1−y(n)(wTx(n)+b))(式11)
其中,拉格朗日乘子λ≥0,计算L(w,b,λ)关于w和b的导数,并分别令为零.得到:
w=n=1∑Nλny(n)x(n)(式12)
0=n=1∑Nλny(n)(式13)
将(式12)带入到(式11),同时根据(式13),得到拉格朗日对偶函数如下:
Γ(λ)=−21n=1∑Nm=1∑Nλmλny(m)y(n)(x(m))Tx(n)+n=1∑Nλn(式14)
支持向量机的主优化问题为凸优化问题,满足强对偶性,即主优化问题可以
通过最大化对偶函数maxλ≥0Γ(λ)来求解. 对偶函数Γ(λ)是一个凹函数,因此最大化对偶函数是一个凸优化问题,可以通过多种凸优化方法来进行求解,得到拉格朗日乘数的最优值λ∗. 但由于其约束条件的数量为训练样本数量,一般的优化方法代价比较高,因此在实践中通常采用比较高效的优化方法,比如序列最小优化.
AIHUBEI
发布了12 篇原创文章 · 获赞 0 · 访问量 3387
私信
关注