Andrew NG 机器学习 笔记-week7-支持向量机(Support Vector Machines)
一、优化目标(Optimization Objective)
支持向量机(Support Vector Machine) 广泛应用于工业界和学术界。
与逻辑回归和神经网络相比,SVM在学习复杂的非线性方程时,提供了一种更为清晰,更加强大的方式。
是有监督算法。
从逻辑回归开始展示我们如何一点一点修改来得到本质上的支持向量机。
逻辑回归中的假设函数,右边S型激励函数。用 z 表示
逻辑回归的代价函数:
这个式子可以合并成:
即,逻辑回归的代价函数:
代价函数就是所有项代价之和,其中的一项
如果 y=1
Cost(
当 z=
如果 y=0
Cost(
当 z=
将图中的曲线分别用两条直线代替(粉红色),左边的函数用
拥有了这些定义后,现在,我们就开始构建支持向量机。
1、将 -log(
2、去掉
3、将正则化项的正则化参数 λ 去掉,在前一部分加上参数C,( λ的作用就是权重前后两部分,得到最小化的A,在A前面加参数C能起到相同的作用,这里C相当于 1/ λ)
有别于逻辑回归输出的概率。当最小化代价函数,获得参数 θ 时,支持向量机所做的是它来直接预测 y 的值等于 1,还是等于 0。
二、大间距的直观理解(Large Margin Intuition)
人们有时将支持向量机看作是大间距分类器。在这一部分,我将介绍其中的含义,这有助于我们直观理解 SVM 模型的假设是什么样的。
左边这里我画出了关于 z 的代价函数
我们考虑一下,最小化这些代价函数的必要条件是什么?
如果你有一个正样本,y 等于 1,则只有在 z 大于等于 1 时,代价函数
反之,如果 y 是等于 0 的,只有在 z 小于等于 -1 时,
这是支持向量机的一个有趣性质。事实上,如果你有一个正样本 y 等于 1,则其实我们仅仅要求
考虑一个特例,将C设置成一个非常大的值,比如100000,然后看支持向量机会给出什么结果?
如果 C 非常大,则最小化代价函数的时候,我们将会很希望找到一个使第一项为 0 的最优解。
这将遵从以下的约束:
最小化问题便转变成:
黑色的决策界和训练样本之间有更大的最短距离。
这个距离叫做支持向量机的间距,而这是支持向量机具有鲁棒性的原因,因为它努力用一个最大间距来分离样本。因此支持向量机有时被称为 大间距分类器。
大间距分类器的时候,你的学习算法会受异偏值 (outlier) 的影响。
如果你将 C 设置的不要太大,则你最终会得到这条黑线。
实际上应用支持向量机的时候,当 当 C 不是非常非常大的时候,它可以忽略掉一些异常点的影响,得到更好的决策界。
大间距分类器的描述仅仅是从直观上给出了正则化参数 C 非常大的情形。
C 的作用类似于 1/λ,λ是我们之前使用过的正则化参数。
回顾 C=1/λ,因此:
C 较大时,相当于 λ 较小,可能会导致过拟合,高方差。
C 较小时,相当于 λ 较大,可能会导致低拟合,高偏差。
三、大间距背后的数学(Behind Large Margin Classification)
向量内积:
||u|| 表示 u 的范数,即 u 的长度,即 u 的欧几里得长度。根据毕达哥拉斯定理,||u||=
p 事实上是有符号的,u 和 v 之间的夹角大于 90 度为负,小于 90 度为正。
这就是我们先前给出的支持向量机模型中的目标函数。为了讲解方便,我做一点简化,仅仅是为了让目标函数更容易被分析。
将特征数 n 置为 2,因此我们仅有两个特征 x1 和 x2 ,这时目标函数为:
因此支持向量机做的全部事情,就是极小化参数向量 θ 范数的平方, 或者说长度的平方。
另外,考虑
另
所以约束可以写为:
我们来看一下支持向量机会选择什么样的决策界。
这不是一个好的选择,看SVM为什么不选择他。
θ 事实上与 决策界 成 90度正交。(为了各个 x 投影后得到离决策界的距离)
样本
相反的,来看一个不同的决策边界。样本在 θ 上的投影 p 长度 较大。所以可以令 θ 的范数变小。
以上就是为什么支持向量机最终会找到大间距分类器的原因。因为它试图极大化这些
四、核函数1(Kernels 1)
对于一个非线性 Decision boundary,我们之前利用多项式拟合的方法进行预测:
f1, f2, … fn为提取出来的features。
定义预测方程
当
那么,除了将fn定义为x的幂次项组合,还有没有其他方法表示 f 呢?本节就引入了Kernel,核的概念。即用核函数表示f。
对于上图的非线性拟合,我们通过计算输入原始向量与landmark之间的相似度来计算核值f:
发现相似度计算公式很像正态分布(高斯分布)对不对?是的!这就是高斯核函数。由下图可以看出,
x和l越相似,f越接近于1;
x与l相差越远,f越接近于0;
下图中的横纵坐标为 x 的两个维度值,高为f(new feature)。制高点为x=
下面我们来看SVM核分类预测的结果:
引入核函数后,代数上的区别在于f变了,原来f是
引入核函数后,几何上来说可以更直观的表示是否应该归为该类了(如下图)
比如我们想将坐标上的所有数据点分为两类(如下图中)红色圈内希望预测为y=1;圈外希望预测为y=0。
通过训练数据集呢,我们得到了一组θ值(θ0,θ1,θ2,θ3)=(-0.5,1,1,0)以及三个点(L1,L2,L3),(具体怎么训练而成的大家先不要过分纠结,后面会讲)
对于每个test数据集中的点,我们首先计算它到(L1,L2,L3)各自的相似度,也就是核函数的值(f1,f2,f3),然后带入多项式
五、核函数2(Kernels 2)
上一节中我们遗留了两个问题,一个是一些 L 点的选取,一个是向量θ计算。
我们通常是根据训练集的数量选择地标的数量,即如果训练集中有 m 个实例,则我们选取 m 个地标,并且令:
这样做的好处在于:现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的,即:
PS:那么在这m个训练数据中,每一个训练数据
在SVM的训练中,将Gaussian Kernel带入cost function,通过最小化该函数就可与得到参数θ,并根据该参数θ进行预测:
若
else predict y=0;
如下图所示,这里与之前讲过的cost function的区别在于用kernel f 代替了x。
在此,我们不介绍最小化支持向量机的代价函数的方法,你可以使用现有的软件包(如liblinear,libsvm 等)。在使用这些软件包最小化我们的代价函数之前,我们通常需要编写核函数,并且如果我们使用高斯核函数,那么在使用之前进行特征缩放是非常必要的。
另外,支持向量机也可以不使用核函数,不使用核函数又称为数 线性核函数(linear kernel),当我们不采用非常复杂的函数,或者我们的训练集特征非常多而实例非常少的时候,可以采用这种不带核函数的支持向量机。
好了,至此Landmark点和θ的求取都解决了,还有一个问题,就是cost function中两个参数的确定:C和
对于C,由于C=1/λ,所以
C大,λ小,overfit,high variance
C小,λ大,underfit,high bias
对于方差
六、使用支持向量机(Using An SVM)
在高斯核函数之外我们还有其他一些选择,如:
多项式核函数(Polynomial Kernel)
字符串核函数(String kernel)
卡方核函数( chi-square kernel)
直方图交集核函数(histogram intersection kernel)
等等…(但不一定起作用)
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征,这些核函数需要满足 Mercer’s 定理,才能被支持向量机的优化软件正确处理。
想要进行SVM学习参数 θ ,需要指定 C 和 核函数,有哪两类:
一种是 No kernel(linear kernel),
另一种是使用kernel f(比如Gaussian Kernel),
最后,我们比较一下logistic regresion和 SVM:
用n表示feature个数,m表示training exampl个数。
①当n>=m,如n=10000,m=10~1000时,建议用logistic regression, 或者linear kernel的SVM
②如果n小,m不大不小,如n=1~1000,m=10~10000,建议用Gaussian Kernel的SVM
③如果n很小,m很大,如n=1~1000,m>50000,建议增加更多的feature并使用logistic regression, 或者linear kernel的SVM
原因,①模型简单即可解决,②如果还用Gaussian kernel会导致很慢,所以还选择logistic regression或者linear kernel
神经网络可以解决以上任何问题,但是速度是一个很大的问题。
详见下图: