吴恩达《机器学习》课程学习笔记(九)—— 支持向量机SVM

吴恩达《机器学习》课程学习笔记(九)—— 支持向量机SVM

一、优化目标(Optimization Objective)

向量支持机(Support Vector Machine ,SVM)是另一种监督式学习算法。它有时候更加的简洁和强大。

我们回顾一下,逻辑回归中,我们有如下结论:

  • 如果y=1,那么​\( h_\theta(x) \approx 1 \)​且​\( \Theta^Tx \gg 0 \)
  • 如果y=0,那么​\( h_\theta(x) \approx 0 \)​且​\( \Theta^Tx \ll 0 \)

进一步,我们来回顾一下逻辑回归的代价函数:

\[ \begin{align*}J(\theta) & = \frac{1}{m}\sum_{i=1}^m -y^{(i)} \log(h_\theta(x^{(i)})) – (1 – y^{(i)})\log(1 – h_\theta(x^{(i)}))\\ & = \frac{1}{m}\sum_{i=1}^m -y^{(i)} \log\Big(\dfrac{1}{1 + e^{-\theta^Tx^{(i)}}}\Big) – (1 – y^{(i)})\log\Big(1 – \dfrac{1}{1 + e^{-\theta^Tx^{(i)}}}\Big)\end{align*} \]

为了引入支持向量机,首先,我们将代价函数的第一项转化为​\( -\log(h_{\theta}(x)) = -\log\Big(\dfrac{1}{1 + e^{-\theta^Tx}}\Big) \)​,第二项转化为​\( -\log(1 – h_{\theta(x)}) = -\log\Big(1 – \dfrac{1}{1 + e^{-\theta^Tx}}\Big) \)​。这样,我们就得到了SVM的代价函数。

为了分析代价函数的趋势,得出其优化解,我们把这两项关于z即\( θ^Tx \)​的函数图像画出来,得到两条光滑的sigmoid函数曲线。进一步地,使用两段直线来尝试替代曲线,这被称作hinge loss 函数,https://en.wikipedia.org/wiki/Hinge_loss

可以看到,使用替代的hinge loss函数后,当​\( θ^Tx \)​比1大的时候,我们有第一项为零;当\( θ^Tx \)比-1小的时候,我们有第二项为零。

而代价函数中,第一项的系数为y,在y为0时失效;

第二项的系数为(1-y),在y为1时失效。

这就意味着,如果我们想最小化代价函数,那么首先考虑这两个极端情况:

  • 在y为0的时候,需要让\( θ^Tx \)比-1小,此时第一第二项都为零。
  • 在y为1的时候,需要让\( θ^Tx \)比1大,此时第一项第二项都为零。

下面我们用规范的语言来描述它:

我们把第一项定义为​\( \text{cost}_1(z) \)​,第二项定义为​\( \text{cost}_0(z) \)​,那么可以说​\( \text{cost}_1(z) \)是当y=1时进行分类的代价函数,​\( \text{cost}_0(z) \)是当y=0时进行分类的代价函数。那么可以得到它们的取值范围如下:

\[ z = \theta^Tx \]

\[ \text{cost}_0(z) = \max(0, k(1+z)) \]

\[ \text{cost}_1(z) = \max(0, k(1-z)) \]

其中k是替代直线的斜率。

 

接下来,我们引入正则项。

首先逻辑回归的正则化代价函数为:

\[ J(\theta) = \frac{1}{m} \sum_{i=1}^m y^{(i)}(-\log(h_\theta(x^{(i)}))) + (1 – y^{(i)})(-\log(1 – h_\theta(x^{(i)}))) + \dfrac{\lambda}{2m}\sum_{j=1}^n \Theta^2_j \]

接着我们如前所述,用​\( \text{cost}_0(z) \)​和​\( \text{cost}_1(z) \)​来替代第一项和第二项:

\[ J(\theta) = \frac{1}{m} \sum_{i=1}^m y^{(i)} \ \text{cost}_1(\theta^Tx^{(i)}) + (1 – y^{(i)}) \ \text{cost}_0(\theta^Tx^{(i)}) + \dfrac{\lambda}{2m}\sum_{j=1}^n \Theta^2_j \space\space\space\space\space\space(1.1) \]

接着我们稍加变形,乘上一个​\( \frac{m}{\lambda} \)​,那么SVM的代价函数化为;

\[ J(\theta) = \frac{1}{\lambda}\sum_{i=1}^m y^{(i)} \ \text{cost}_1(\theta^Tx^{(i)}) + (1 – y^{(i)}) \ \text{cost}_0(\theta^Tx^{(i)}) + \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \]

我们记​\( C=\frac{1}{\lambda} \)​,那么有

\[ J(\theta) = C\sum_{i=1}^m y^{(i)} \ \text{cost}_1(\theta^Tx^{(i)}) + (1 – y^{(i)}) \ \text{cost}_0(\theta^Tx^{(i)}) + \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \space\space\space\space\space\space(1.2) \]

这就是通常使用的SVM代价函数,这个系数C本质上和λ一样的,都是改变普通代价函数项和正则项的权重关系。也就是说,如果我们想要加强正则化强度来处理过拟合,那么减小C;如果想要减少正则化强度来处理欠拟合,那么增大C。

最后,与逻辑回归中不同的是,SVM算法的假设函数并不代表y=0或1的概率,而是只输出0或1:

\[ h_\theta(x) =\begin{cases} 1 & \text{if} \ \Theta^Tx \geq 0 \\ 0 & \text{otherwise}\end{cases} \space\space\space\space\space\space(1.3) \]

 

二、对大余量的直观理解(Large Margin Intuition)

一个比较直观的理解SVM算法的角度是,将其看作大余量分类器。为什么这么说呢,我们需要看看SVM算法的决策边界。

首先我们回顾一下上一节的结论,由于引入了hinge loss函数来代替sigmoid函数,其输出关系如下:

  • 如果想要预测y=1,那么我们需要使​\( \Theta^Tx \geq 1 \)​(注意不仅仅是≥0)
  • 如果想要预测y=0,那么我们需要使​\( \Theta^Tx \leq -1 \)​(注意不仅仅是<0)

假如代价函数中我们使用了一个比较大的C。基于上面的结论,如果我们需要使得代价函数较小的话,那么需要令​\( \sum_{i=1}^m y^{(i)}\text{cost}_1(\Theta^Tx) + (1 – y^{(i)})\text{cost}_0(\Theta^Tx) = 0 \)

此时代价函数的结果为:

\[ \begin{align*} J(\theta) = C \cdot 0 + \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \newline = \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \end{align*} \]

在SVM算法中,决策边界的性质是:尽可能地远离正数据集与负数据集。为什么这样做呢?因为这样会使决策边界对于两种数据集都有一些余地,也就是有一些容错率。至于其数学原理,我们下一节会讨论。

有几点要注意的是:

  • 样本与决策边界之间的距离称为余量(margin),由于SVM需要最大化余量,因而又被称为大余量分类器(Large Margin Classifier)
  • SVM的大间距仅当C非常大的时候才能实现。
  • 如果我们存在一些偏差较大的数据(outlier),又不想让其过分影响决策边界时,那么我们需要减小C的数值。

 

三、大余量分类背后的数学原理(Mathematics Behind Large Margin Classification )

1.向量内积(Vector Inner Product)

假设我们有两个向量u和v,

\[ \begin{align*} u = \begin{bmatrix} u_1 \newline u_2 \end{bmatrix} && v = \begin{bmatrix} v_1 \newline v_2 \end{bmatrix} \end{align*} \]

那么向量v的长度​\( \sqrt{v_1^2 + v_2^2} \)​就记作||v||。v到u的投影记作p,且有

\[ p = ||v|| \cos \theta \]

\[ u^Tv= p \cdot ||u|| \]

\[ u^Tv = ||u|| \cdot ||v|| \cos \theta \]

如果将u和v各自单独分出两个分向量,那么有

\[ u^Tv = v^Tu = p \cdot ||u|| = u_1v_1 + u_2v_2 \]

2.推广

由上面的投影观点,对于正则项我们可以得出:

\[ \begin{align*}&\min_\Theta \dfrac{1}{2}\sum_{j=1}^n \Theta_j^2 \newline&= \dfrac{1}{2}(\Theta_1^2 + \Theta_2^2 + \dots + \Theta_n^2) \newline&= \dfrac{1}{2}(\sqrt{\Theta_1^2 + \Theta_2^2 + \dots + \Theta_n^2})^2 \newline&= \dfrac{1}{2}||\Theta ||^2 \newline\end{align*} \]

且对于​\( \Theta^Tx^{(i)} \)​我们可以将其理解为向量x在向量θ上的投影:

\[ \Theta^Tx^{(i)} = p^{(i)} \cdot ||\Theta || = \Theta_1x_1^{(i)} + \Theta_2x_2^{(i)} + \dots + \Theta_n x_n^{(i)} \]

这样就好理解了。我们将代价函数最小化的过程,实质上是令数据集构成的向量X,在决策边界θ上的投影大于1或者小于-1。对于所有的数据​\( X^{(i)} \)​都进行这样的操作,就使得决策边界与所有数据集之间的余量变大了。

 

四、核函数(Kernels)

1.Kernels I – 高斯核函数与“地标”

之前,我们在处理非线性决策边界时,使用的方法是引入多项式

\[ h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2^2+… \]

我们可以将其抽象为

\[ h_\theta(x)=\theta_0+\theta_1f_1+\theta_2f_2+… \space\space\space\space\space\space(4.1) \]

这里提出的问题是,除了使用幂次项,还有别的办法替代​\( f_1、f_2 \)​吗?

现在假设我们的坐标系上有一些“地标”(landmark),我们要做的是,计算数据样本x与地标之间的接近程度,这里引入了一个新的函数similarity:

\[ f_i = similarity(x, l^{(i)}) = \exp(-\dfrac{||x – l^{(i)}||^2}{2\sigma^2}) \space\space\space\space\space\space(4.2) \]

可以看到,我们使用SVM算法的时候,利用similarity函数可以更有效地将决策边界与数据集之间的余量扩大。对于上面这个用来替代\( f_1、f_2 \)的相似函数,我们称作高斯核函数(Gaussian Kernel)。这是核函数里面的一种。

我们还能把相似函数表示为:

\[ f_i = similarity(x, l^{(i)}) = \exp(-\dfrac{\sum^n_{j=1}(x_j-l_j^{(i)})^2}{2\sigma^2}) \space\space\space\space\space\space(4.3) \]

函数中有两条比较重要的性质:

  • 如果​\( x \approx l^{(i)} \)​,即x离\( l^{(i)} \)​很近,那么​\( f_i = \exp(-\dfrac{\approx 0^2}{2\sigma^2}) \approx 1 \)
  • 如果x离​\( l^{(i)} \)​很远,那么​\( f_i = \exp(-\dfrac{(large\ number)^2}{2\sigma^2}) \approx 0 \)

如果我们有很多的地标,那么它们就可以为假设函数提供很多特征量:

\[ \begin{align*}l^{(1)} \rightarrow f_1 \newline l^{(2)} \rightarrow f_2 \newline l^{(3)} \rightarrow f_3 \newline\dots \newline h_\Theta(x) = \Theta_1f_1 + \Theta_2f_2 + \Theta_3f_3 + \dots\end{align*} \]

其中​\( \sigma^2 \)​是高斯核函数的一个参数,它可以控制特征量​\( f_i \)​的下降速度(drop-off)。如果我们同时查看θ内的值,可以通过选择这些地标来设定决策边界的一般形状。

2.Kernels II – 地标的选取

获取地标的一种方法是,将它们放在与训练样例完全相同的位置。这样我们可以得到m个地标,每个地标对应着一个训练样例。

例子如下:

\[ f_1 = similarity(x,l^{(1)}),f_2 = similarity(x,l^{(2)}),f_3 = similarity(x,l^{(3)}) \]

这样我们就得到了一个“特征向量”,我们可以额外的设置​\( f_0 = 1 \)​。

\[ x^{(i)} \rightarrow \begin{bmatrix}f_1^{(i)} = similarity(x^{(i)}, l^{(1)}) \newline f_2^{(i)} = similarity(x^{(i)}, l^{(2)}) \newline\vdots \newline f_m^{(i)} = similarity(x^{(i)}, l^{(m)}) \newline\end{bmatrix} \]

现在,我们已经得到了特征向量,那么就可以训练参数θ了!

\[ Cost = \min_{\Theta} C \sum_{i=1}^m y^{(i)}\text{cost}_1(\Theta^Tf^{(i)}) + (1 – y^{(i)})\text{cost}_0(\theta^Tf^{(i)}) + \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \space\space\space\space\space\space(4.4) \]

注:使用核函数来得到特征量f并不是SVM算法所独有的,它也可以应用于逻辑回归。然而,由于SVM算法在计算上的优势,核函数与SVM算法的结合能够远超其他算法,所以一般只看见核函数与SVM算法的结合使用。

3.选取SVM的参数(Choosing SVM Parameters)

这里有一些对于参数C的总结:

  • 如果C比较大,那么我们会有更高的方差、更低的偏差(过拟合)
  • 如果C比较小,那么我们会有更高的偏差、更低的方差(欠拟合)

还有一些对于参数​\( σ^2 \)​的总结:

  • 如果​\( σ^2 \)​比较大,那么特征量变化会更加平滑,这意味着更高的偏差、更低的方差(欠拟合)
  • 如果​\( σ^2 \)​比较小,那么特征量变化会没那么平滑,这意味着更高的方差、更低的偏差(过拟合)

4.使用SVM算法(Using An SVM)

已经有许多现成的SVM算法库了,比如Andrew Ng提到的 ‘liblinear’ 和 ‘libsvm’。这节作业里,我们会练习一下SVM算法的使用:

  • 参数C的选择
  • 核函数的选择
  • 不使用核函数(其实是线性核函数)– 给出标准的线性分类器
  • 决定什么时候n要大,什么时候m要小
  • 高斯核函数需要选择​\( σ^2 \)
  • 决定什么时候n要小,什么时候m要大

5.多类型分类(Multi-class Classification)

许多SVM库已经支持了多类型分类,我们可以像逻辑回归那章一样,使用“一对多”模型的方法来实现。

6.逻辑回归与SVM算法的对比(Logistic Regression vs. SVMs)

  • 如果n非常大(相对于m),那么使用逻辑回归,或者是无核函数的SVM算法(线性核函数)
  • 如果n比较小,m适中,那么使用高斯核函数支持的SVM算法
  • 如果n比较小,m非常大,那么手动地添加更多的特征量,然后使用逻辑回归或者不带核函数的SVM算法。

在第一种情况下,我们没有足够的样本来训练多项式假设函数。

在第二种情况下,我们有足够的样本来训练非线性假设函数。

在第三种情况下,我们想要增加更多的特征量,以此使得逻辑回归可以适用。

 

五、第六次编程作业

这次参与了编写一个基于SVM的垃圾邮件识别器,其中使用了一些字符串处理相关知识,但是核心代码Andrew Ng已经写出来了,所以感兴趣的同学可以深入研究其源码。

传送门:https://github.com/YongyiZhou/Andrew-Ng/tree/master/ex6



One Comment

Good job! THX

Reply

Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert