阅读 224

支持向量机

本文为《吴恩达机器学习》的要点记录

支持向量机 Support Vector Machine (SVM)

支持向量机,或者简称SVM。它与逻辑回归和神经网络相比,在学习复杂的非线性方程时提供了一种更为清晰,更加强大的方式。它的假设函数是:

\min_{\theta}C\sum_{i=1}^{m}[y^{(i)}cost_{1}(\theta^{T}x^{(i)}) + (1 - y^{(i)})cost_{0}(\theta^{T}x^{(i)})]+\frac{1}{2}\sum_{i=1}^{n}\theta_{j}^{2}

对于逻辑回归来说

cost_{1}(\theta^{T}x^{(i)})->-logh_{\theta}({x^{(i)})}

cost_{0}(\theta^{T}x^{(i)})->-logh_{\theta}^{x^{(i)}}(1-h_{\theta}(x^{(i)}))

如果你有一个正样本(y = 1),则其实我们仅仅要求\theta^{T}x > 0,就能将该样本恰当分出,这是因为如果\theta^{T}x > 0的话,我们的模型代价函数值为0。类似地,如果你有一个负样本,则仅需要\theta^{T}x < 0就会将负例正确分离。

但是,支持向量机的要求更高,不仅仅要能正确分开输入的样本,即不仅仅要求\theta^{T}x > 0,我们需要的是比0值大很多,比如大于等于1,我也想这个比0小很多,比如我希望它小于等于-1,这就相当于在支持向量机中嵌入了一个额外的安全因子,或者说安全的间距因子。那这个安全因子怎么训练出来呢?

理解大间距分类器

在SVM中我们可以把参数C理解为\frac{1}{\lambda},因此:

C较大时,相当于\lambda较小,可能会导致过拟合,高方差。

C较小时,相当于\lambda较大,可能会导致低拟合,高偏差。

比如上面的黑色决策边界和粉色决策边界是我们使用SVM训练出来的,如果将C设置的比较大,则你最终会得到这条粉线,如果设置的比较小的话,最终会得到黑色的线。这就是为什么SVM又叫做大间距分类器的直观理解。

大边界的数学原理

我们看一下SVM的决策边界:

上图 p^{(i)}\centerdot \lVert\theta\lVert >= 1 就是 \theta^{T}x >= 1

  1. 假设SVM选择了上图左边绿色的线作为决策边界。(其实SVM不会选择它,这个决策决策界离训练样本的距离很近)

使用线性代数的知识,可以说明这个绿色的决策界有一个垂直于它的向量\theta。从上图可以看到样本到\theta的投影p^{(i)}都比较小,这就导致最终最小化的\theta比较大

  1. 假设SVM选择了上图右边绿色的线作为决策边界。

这时你会发现样本到\theta的投影p^{(i)}都比左边图的大,因此对应求出的\theta会小的多,即:

\min_{\theta}\frac{1}{2}\sum_{j=1}^{n}\theta_{j}^{2}

即SVM会试图极大化p^{i}这些范数(他们是训练样本到决策边界的距离),这就是为什么支持向量机最终会找到大间距分类器的原因。

SVM的使用

核函数基本思想 Kernel Function

比如我们想分割上图正负样本,我们可以利用核函数来建立新的特征:

上图是我们随机选定的一些地标l^{(1)},l^{(2)},l^{(3)},我们利用他们与训练样本x的近似程度来选取新的特征f_{1}, f_{2}, f_{3}, 例如f_{1} :

f_{1} = similarity(x,l^{(1)}) = e(-\frac{\lVert x-l^{(1)}\lVert^{2}}{2\sigma^{2}})

其中\lVert x-l^{(1)}\lVert^{2} = \sum_{j=1}^{n}(x_{j}-l_{j}^{1})^{2},为实例x中所有特征与地标l^{(1)}之间的距离和。

similarity(x,l^{(1)})就是核函数(它是一个高斯核函数)。这些地标的作用是 : 如果一个训练样本x与地标l之间的距离近似于0,则新特征f近似于e^{-0} = 1,如果训练样本x与地标l之间距离较远,则f近似于e^{-(一个较大的数)}=0

除了这个核函数外还有很多核函数可以选择。

不同的l\sigma对核函数的影响

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

举个例子:

在上图中,当样本处于洋红色的点位置处,因为其离l^{(1)}更近,但是离l^{(2)}l^{(3)}较远,因此f_{1}接近1,而f_{2}, f_{3}接近0。因此h_{\theta}(x)=\theta_{0}+\theta_{1}f_{1}+\theta_{2}f_{2}+\theta_{3}f_{3} > 0, 因此预测y=1。但是对于蓝绿色的点,因为其离三个地标都较远,预测y=0

在使用核函数预测时,我们采用的特征不是训练样本本身的特征,而是通过核函数计算出的新特征f_{1},f_{2}, f_{3}

核函数的应用 & 支持向量机

-_-,,,,说实话到这里我只是大概听明白了核函数的原理,但是还不知道它是干嘛的。。。。。对于核函数的简单理解可以参考一下这篇文章 : SVM入门-为何需要核函数

即可以使用核函数把线性不可分的问题映射到高维空间,然后问题就变得线性可分(大概是这么个意思)

上面我们可以对SVM的特征做核函数映射。如果SVM不使用核函数又称为线性核函数,当我们不采用非常复杂的函数,或者我们的训练集特征非常多而样本非常少的时候,可以采用这种不带核函数的支持向量机。

核函数需要满足Mercer's定理,才能被支持向量机的优化软件正确处理。

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

C = \frac{1}{\lambda}

C较大时,相当于\lambda较小,可能会导致过拟合,高方差;

C较小时,相当于\lambda较大,可能会导致低拟合,高偏差;

\sigma较大时,可能会导致低方差,高偏差;

\sigma较小时,可能会导致低偏差,高方差。

对于 SVM 与 逻辑回归应该如何选择呢?

普遍使用的准则:

n为特征数,m为训练样本数。

(1)如果相较于m而言,n要大许多,即训练集数据量不够支持我们训练一个复杂的非线性模型,我们选用逻辑回归模型或者不带核函数的支持向量机。

(2)如果n较小,而且m大小中等,例如n在 1-1000 之间,而m在10-10000之间,使用高斯核函数的支持向量机。

(3)如果n较小,而m较大,例如n在1-1000之间,而m大于50000,则使用支持向量机会非常慢,解决方案是创造、增加更多的特征,然后使用逻辑回归或不带核函数的支持向量机。

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