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