吴恩达机器学习-7-支持向量机SVM
本周主要是讲解了支持向量机SVM的相关知识点
- 硬间隔
- 支持向量
- 软间隔
- 对偶问题
优化目标Optimization Objectives
主要是讲解如何从逻辑回归慢慢的推导出本质上的支持向量机。逻辑回归的假设形式:
- 左边是假设函数
- 右边是
Sigmoid
激活函数
令$z={\theta}^{T}x$,如果满足:
- 若$y=1$,希望$h{(\theta)}$约为1,将样本正确分类,那么z必须满足$z>>0$
- 若$y=0$,希望$h(\theta)$约为0,将样本正确分类,那么z必须满足$z<<0$
样本正确分类指的是:假设函数h(x)得到的结果和真实值y是一致的
总代价函数通常是对所有的训练样本进行求和,并且每个样本都会为总代价函数增加上式的最后一项(还有个系数$\frac{1}{m}$,系数忽略掉)
如果$y=1$,目标函数中只有第一项起作用,得到了表达式 :
支持向量机
根据逻辑回归推导得到的支持向量机的公式 :
两个cost
函数是上面提到的两条直线。对于逻辑回归,在目标函数中有两项:
- 第一个是训练样本的代价
- 第二个是正则化项
大边界的直观解释
下面是支持向量机的代价函数模型。
SVM决策边界
SVM鲁棒性:间隔最大化,是一种大间距分类器。
关于上图的解释:
C
太大的话,将是粉色的线C
不是过大的话,将是黑色的线
大间距分类器的描述,仅仅是从直观上给出了正则化参数C非常大的情形,C的作用类似于之前使用过的正则化参数$\frac{1}{\lambda}$
C
较大,可能导致过拟合,高方差C
较小,可能导致低拟合,高偏差
硬间隔模型
间隔和支持向量
注释:本文中全部采用列向量:
给定一个样本训练集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$,其中$y_i \in {(-1,+1)}$
分类学习的基本思想就是:基于训练集D
在样本空间上找到一个划分的超平面
上面红色的线是最好的。所产生的分类结果是最鲁棒的,最稳定的,泛化能力是最好的。
划分超平面的的线性描述: $${w\cdot x+b=0}$$
W称之为法向量(看做是列向量),决定平面的方向;b是位移项,决定了超平面和原点之间的距离。
空间中任意一点x到超平面(w,b)的距离是:
在$+$区域的点满足$y=+1$:
在$-$区域的点满足$y=-1$:
综合上面的两个式子有:
支持向量
距离超平面最近的几个点(带上圆圈的几个点)称之为支持向量support vector
,这个点到超平面到距离称之为间隔margin
刚好在决策边界上的点(下图中带上圆圈的点)满足上式中的等号成立:
间距margin
求解间距margin
就是求解向量${({x_+}-{x_-})}$在法向量上的投影
决策边界上的正例表示为:
决策边界行的负例表示为:
将两个结果带入margin
的表达式中:
SVM的基本模型
最大间隔化只需要将$||w||$最小化即可:
SVM-对偶模型
模型参数推导
希望求解上面基本模型对应超平面的模型:
利用拉格朗日乘子$\alpha_i$,改成拉格朗日函数:
分别对$w,b$求导,可以得到:
对偶模型
原始问题是极大转成最大值问题:
带入拉格朗日函数中,得到对偶问题(全部是关于$\alpha$系数):
转换一下,变成最小值问题(上面的式子加上负号):
那么超平面的模型 :
SMO算法
思想
SMO算法指的是Sequential Minimal Optimization
,序列最小优化算法。算法的根本思路是:
所有的$\alpha$满足:
-
先选取需要更新的变量$\alpha_i$和$\alpha_j$
-
固定变量$\alpha_i$和$\alpha_j$以外的参数,求解更新后的变量$\alpha_i$和$\alpha_j$
其中$c$使得上式成立:
- 将变量$\alpha_i$和$\alpha_j$的其中一个用另一个来表示,得到关于$\alpha_i$的单变量二次规划问题,就可以求出来变量$\alpha_i$
软间隔最大化
上面的结论和推导都是针对的线性可分的数据。线性不可分数据意味着某些样本点$(x_i,y_i)$不再满足函数间隔大于等于1的约束条件,比如下图中的红圈中的点,故引入了松弛变量$\xi_i \geq0$,满足:
因此,目标函数由原来的$\frac{1}{2}{||w||^2}$变成了
其中$C\geq0$是惩罚项参数,C
值越大对误分类的越大,C
越小对误分类的惩罚越小。