机器学习笔记 Week7 支持向量机

学习笔记(Machine Learning) Week7

全部笔记PDF版:http://vdisk.weibo.com/s/J4rRX/1373287206

Week7 支持向量机

支持向量机(Support Vector Machine)

支持向量机,SVM,是非常强大且流行的算法,在一些情况下,能面向一些复杂的非线性问题提供比逻辑回归或神经网络要更加简洁的解决方案。

1.1优化目标(Optimization Objective)

以逻辑回归为例展开讨论: 回顾逻辑回顾模型:

l h

我们分y=1和y=0两种情况讨论:

  • y=1时,希望假设hθ(x)预测的值尽可能接近1,即希望z=θTX尽可能地大
  • y=0时,希望假设hθ(x)预测的值尽可能接近0,即希望z=θTX尽可能地小

从代价函数来看,回顾逻辑回归模型的代价函数为:

log cost

针对任何训练集中任何一个实例,对总的代价的影响为:

cost ind

即:

图片2

为了使每一个实例造成的代价都尽可能地小,分y=1和y=0两种情况讨论,最佳的情况是代价为0,但是由曲线可以看出,代价始终存在而非0。

QQ截图20130702231537

在支持向量机中,我们将曲线的代价函数转变成由2条线段构成的折线:

  • 当y=1时, 我们希望构建新的代价函数如cost1(z)所示,当z>=1时,cost1(z)=0
  • 当y=0时,我们希望构建新的代价函数如cost0(z)所示,当z<=-1时,cost0(z)=0

QQ截图20130703094054

用这两个新构建的代价函数代替原本逻辑回归的代价函数,得到:

QQ截图20130703100726

对上面这个代价函数稍作调整:

  1. 因为1/m实际上不影响最优化的结果,将其去掉。
  2. 因为归一化参数λ控制的是归一化的这一项在整个代价函数中占的比例,对于支持向量机,我们想要控制的是新构建的代价函数部分,因此我们去掉λ的同时给第一项乘以一个常数C,相当于我们将整个代价函数除以了λ,且C=1/λ。

我们依旧是希望能找出能使该代价函数最小的参数。注意,调整后的代价函数是一个凸函数(convex function),而非之前逻辑回归那样的非凸函数,这意味着,求解的过程中,不会陷入局部最小值而错过全局最小值的情况:

QQ截图20130703100819

最后,给出支持向量机的假设为:

daum_equation_1372821631397

注意到,我们给出的支持向量机假设在预测时是以z与0的大小关系作为依据的,然而在训练函数时,我们是以正负1为依据的,这是支持向量机与逻辑回归的一个关键区别,且导致了下面要介绍的支持向量机的特性。

1.2支持向量机判定边界(SVM Decision Boundary)

支持向量机有的时候也被称为最大间隔分类器(Large Margin Classifier),其原因是:支持向量机可以尝试发现一个与样本数据集之间有着最大间隔的判定边界。

下图是一个可以用直线来区分的分类问题示例,图中绿色和洋红色的两条线代表着两条逻辑回归的判定边界,而黑色的线代表的则是支持向量机的判定边界,从图上看出黑色的线似乎是更合理的,蓝色的两条线代表的是支持向量机的判定边界与样本数据之间的间隔。

QQ截图20130703113629

下面我们思考一下支持向量机中归一化常数C的作用。

QQ截图20130703100819

假使我们选择的C是一个非常大的值,那么在让代价函数最小化的过程中,我们希望找出在y=1和y=0两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数,则我们的最小化问题便转变成:

QQ截图20130703115030

这种情况下,我们得出的支持向量机判定边界是上面的黑线那样,具有尝试使得判定边界与样本数据间间隔最大的特性。

然而使得判定边界与样本数据之间间隔最大并不总是好事。假使,我们的数据集如下图所示:

QQ截图20130703115513

我们发现数据集中间有一个较为明显的异常值,如果我们在选取较大的C,会导致得到的支持向量机判定边界为图中洋红色直线所示,似乎不是非常的合理。但如果我们选择的C较小,那么可能会获得图中黑色直线所示的判定边界。也就是说C值越小,支持向量机对异常值越不敏感。

回顾 C=1/λ,因此:

  • C较大时,相当于λ较小,可能会导致过拟合,高偏倚。
  • C较小时,相当于λ较大,可能会导致低拟合,高偏差。

1.3核函数(Kernels)

回顾我们之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题:

QQ截图20130703121017

为了获得上图所示的判定边界,我们的模型可能是QQ截图20130703121149的形式。我们可以用一系列的新的特征f来替换模型中的每一项。例如令:QQ截图20130703121329...得到hθ(x)=f1+f2+...+fn。然而,除了对原有的特征进行组合以外,有没有更好的方法来构造f1,f2,f3

我们可以利用核函数来计算出新的特征。

给定一个训练实例x,我们利用x的各个特征与我们预先选定的地标(landmarks)l(1),l(2),l(3)的近似程度来选取新的特征f1,f2,f3

QQ截图20130703122849

例如:

QQ截图20130703122113

其中:QQ截图20130703122202,为实例x中所有特征与地标l(1)之间的距离的和。上例中的similarity(x,l(1))就是核函数,具体而言,这里是一个高斯核函数(Gaussian Kernel)。注:这个函数与正态分布没什么实际上的关系,只是看上去像而已。

这些地标的作用是什么?如果一个训练实例x与地标L之间的距离近似于0,则新特征f近似于e-0=1,如果训练实例x与地标L之间距离较远,则f近似于e-(一个较大的数)=0。

假设我们的训练实例含有两个特征[x1 x2],给定地标l(1)与不同的σ值,见下图:

QQ截图20130703122934

图中水平面的坐标为x1,x2而垂直坐标轴代表f。可以看出,只有当x与l(1)重合时f才具有最大值。随着x的改变f值改变的速率受到σ2的控制。

在下图中,当实例处于洋红色的点位置处,因为其离l(1)更近,但是离l(2)和l(3)较远,因此f1接近1,而f2,f3接近0。因此hθ(x)=θ01f12f21f3>0,因此预测y=1。同理可以求出,对于离l(2)较近的绿色点,也预测y=1,但是对于蓝绿色的点,因为其离三个地标都较远,预测y=0。

QQ截图20130703125814

这样,图中红色的封闭曲线所表示的范围,便是我们依据一个单一的训练实例和我们选取的地标所得出的判定边界,在预测时,我们采用的特征不是训练实例本身的特征,而是通过核函数计算出的新特征f1,f2,f3

如何选择地标?

我们通常是根据训练集的数量选择地标的数量,即如果训练集中有m个实例,则我们选取m个地标,并且令:l(1)=x(1),l(2)=x(2),...,l(m)=x(m)。这样做的好处在于:现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的,即:

QQ截图20130703130936

下面我们将核函数运用到支持向量机中,修改我们的支持向量机假设为:

  • 给定x,计算新特征f,当θTf>=0时,预测y=1,否则反之。

相应地修改代价函数为:

QQ截图20130703131256

在具体实施过程中,我们还需要对最后的归一化项进行些微调整,在计算QQ截图20130703131511时,我们用θTMθ代替θTθ,其中M是根据我们选择的核函数而不同的一个矩阵。这样做的原因是为了简化计算。

理论上讲,我们也可以在逻辑回归中使用核函数,但是上面使用M来简化计算的方法不适用与逻辑回归,因此计算将非常耗费时间。

在此,我们不介绍最小化支持向量机的代价函数的方法,你可以使用现有的软件包(如liblinear,libsvm等)。在使用这些软件包最小化我们的代价函数之前,我们通常需要编写核函数,并且如果我们使用高斯核函数,那么在使用之前进行特征缩放是非常必要的。

另外,支持向量机也可以不使用核函数,不使用核函数又称为线性核函数(linear kernel),当我们不采用非常复杂的函数,或者我们的训练集特征非常多而实例非常少的时候,可以采用这种不带核函数的支持向量机。

下面是支持向量机的两个参数C和σ的影响:

  • C较大时,相当于λ较小,可能会导致过拟合,高偏倚
  • C较小时,相当于λ较大,可能会导致低拟合,高偏差
  • σ较大时,导致高偏倚
  • σ较大时,导致高偏差

在高斯核函数之外我们还有其他一些选择,如:

  • 多项式核函数(Polynomial Kernel
  • 字符串核函数(String kernel
  • 卡方核函数( chi-square kernel
  • 直方图交集核函数(histogram intersection kernel
  • etc...

这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征,这些核函数需要满足Mercer's定理,才能被支持向量机的优化软件正确处理。

多类分类问题

假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有k个类,则我们需要k个模型,以及k个参数向量θ。我们同样也可以训练k个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能,我们只要直接使用即可。

1.4逻辑回归与支持向量机

从逻辑回归模型,我们得到了支持向量机模型,在两者之间,我们应该如何选择呢?

下面是一些普遍使用的准则:

  • 如果相较于m而言,n要大许多,即训练集数据量不够支持我们训练一个复杂的非线性模型,我们选用逻辑回归模型或者不带核函数的支持向量机。
  • 如果n较小,而且m大小中等,例如n在1-1000之间,而m在10-10000之间,使用带高斯核函数的支持向量机。
  • 如果n较小,而m较大,例如n在1-1000之间,而m大于50000,则使用支持向量机会非常慢,解决方案是创造、增加更多的特征,然后使用逻辑回归或不带核函数的支持向量机。

值得一提的是,神经网络在以上三种情况下都可能会有较好的表现,但是训练神经网络可能非常慢,选择支持向量机的原因主要在于它的代价函数是凸函数,不存在局部最小值。

课程地址:https://class.coursera.org/ml-003/class/index 

Leave a Reply

Your email address will not be published. Required fields are marked *