笔记:机器学习——吴恩达 第七周
课程目录
十二、支持向量机(Support Vector Machines)
12.2 大边界的直观理解
12.3 数学背后的大边界分类(选修)
12.4 核函数1
12.5 核函数2
12.6 使用支持向量机
笔记内容
十二、支持向量机(Support Vector Machines)
12.1 优化目标
在监督学习中,许多学习算法的性能都非常类似,表现情况的好坏,重要的不是你选择使用学习算法 A 还是B,而是通常依赖于你的水平。比如:你为学习算法所设计的 特征量的选择,以及如何选择 正则化参数,等等。
有一个广泛应用于工业界和学术界的更加强大的算法,它被称为支持向量机(Support Vector Machine)。与 逻辑回归 和 神经网络 相比,支持向量机,或者简称 SVM,在学习复杂的 非线性方程 时提供了一种更为清晰,更加强大的方式。它也是我们所介绍的最后一个监督学习算法。
如我们之前的学习算法,我们从优化目标开始。为了描述支持向量机,将会从逻辑回归开始展示我们如何一点一点修改来得到本质上的支持向量机。
在逻辑回归中我们已经熟悉了这里的 假设函数 形式,和右边的 S 型激励函数。然而,为了解释一些数学知识.我将用 z 表示 。
考虑一下我们想要逻辑回归做什么:如果有一个 y=1 的样本,我们希望 h(x) 趋近1。因为我们想要正确地将此样本分类,这就意味着当 h(x) 趋近于 1 时,应当远大于0。相反地,如果我们有另一个样本,即 y=0,我们希望,或者就是 z 会远小于 0,因为对应的假设函数的输出值趋近 0。
如果你进一步观察逻辑回归的代价函数,你会发现每个样本 (x, y)都会为总代价函数增加一项,因此,对于总代价函数通常会有对所有的训练样本求和,并且这里还有一个 1/m 项,但是,在逻辑回归中,这里的这一项就是表示一个训练样本所对应的表达式。现在,如果我将完整定义的假设函数代入这里,那么,我们就会得到每一个训练样本都影响这一项。
现在,先忽略 1/m 这一项,尽管这一项是影响整个总代价函数。现在,一起来考虑两种情况:一种是 y 等于 1 的情况;另一种是 y 等于 0 的情况。
在第一种情况中,假设 y 等于 1,此时在目标函数中只需有第一项起作用。因此,当在 y 等于 1 的样本中时,我们得到 这样一项。我用 z 表示 。如果画出关于 z 的函数,你会看到左图的这条曲线,我们同样可以看到,当 z 增大时,也就是相当于 增大时,z 对应的函数值会变的非常小。对整个代价函数而言,影响也非常小。这也就解释了,为什么逻辑回归在观察到正样本 y=1 时,试图将 设置得非常大。因为,在代价函数中的这一项会变的非常小。
现在开始建立支持向量机,我们会从这个代价函数开始,也就是 一点一点修改,让我取这里的 z=1 点,先画出将要用的代价函数。第二点概念上的变化,我们只是指在使用支持向量机而不是逻辑回归时,一些如下的标准惯例。
接下来,让我们再回去从直观的角度看看优化目标,实际上是在做什么,以及 SVM 的假设函数将会学习什么,同时也会谈谈如何做些许修改,学习更加复杂、非线性的函数 。
>=1,如果 y (i)是等于 1 的; <=-1,如果样本 i 是一个负样本,这样当你求解这个优化问题的时候,当你最小化这个关于变量 θ 的函数的时候,你会得到一个非常有趣的决策边界。
比如,这就是一个决策边界可以把正样本和负样本分开。支持向量机将会选择这个黑色的决策边界,相较于之前用粉色或者绿色画的决策界,黑线看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。数学上来讲,这条黑线有更大的距离,这个距离叫做 间距 (margin)。
当画出这两条额外的蓝线,我们看到黑色的决策界和训练样本之间有更大的最短距离。然而粉线和蓝线离训练样本就非常近,在分离样本的时候就会比黑线表现差。因此,这个距离叫做 支持向量机的间距,而这是支持向量机具有鲁棒性的原因,因为它努力用一个最大间距来分离样本。因此支持向量机有时被称为 大间距分类器,而这其实是求解上一节优化问题的结果。
接下来会从直观上略述为什么这个优化问题会产生大间距分类器。这个图示有助于你理解支持向量机模型的做法,即努力将正样本和负样本用最大的间距分开。
关于大间距分类器,我们将这个 大间距分类器 中的 正则化因子常数 C 设置的非常大,比如将其设置为了 100000。那么在让代价函数最小化的过程中,我们希望找出在 y=1 和 y=0 两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数,则我们的最小化问题便转变成:
事实上,支持向量机现在要比这个大间距分类器所体现得更成熟,尤其是当你使用大间距分类器的时候,你的学习算法会受异常点 (outlier) 的影响。比如我们加入一个额外的正样本。
在这里,如果你加了这个样本,为了将样本用最大间距分开,也许我最终会得到一条类似这样的决策界。就是这条粉色的线,仅仅基于一个异常值,仅仅基于一个样本,就将我的决策界从这条黑线变到这条粉线,这实在是不明智的。而如果 正则化参数 C 设置的非常大,这事实上正是支持向量机将会做的。它将决策界,从黑线变到了粉线,但是如果 C 设置的小一点,则你最终会得到这条黑线,当然数据如果不是线性可分的,在这里有一些正样本或者负样本,则支持向量机也会将它们恰当分开。
因此,大间距分类器的描述,仅仅是从直观上给出了 正则化参数 C 非常大的情形,同时,要提醒你 C 的作用类似于 1/λ ,λ是我们之前使用过的正则化参数 。这只是C 非常大的情形,或者等价地 λ 非常小的情形。你最终会得到类似粉线这样的决策界,但是实际上应用支持向量机的时候,当 C 不是非常非常大的时候,它可以忽略掉一些异常点的影响,得到更好的决策界。甚至当你的数据不是线性可分的时候,支持向量机也可以给出好的结果。
回顾 C=1/λ,因此:C 较大时,相当于 λ 较小,可能会导致过拟合,高方差。
C 较小时,相当于 λ 较大,可能会导致低拟合,高偏差。 我们稍后会介绍支持向量机的偏差和方差,希望在那时候关于如何处理参数的这种平衡会变得更加清晰。这节课给出了一些关于为什么支持向量机被看做大间距分类器的直观理解。它用 最大间距 将样本区分开,尽管从技术上讲,这只有当参数 C 是非常大的时候是真的,但是它对于理解支持向量机是有益的。
我们给出的优化问题为什么会是这样的?它是如何得出大间距分类器的?在本节中没有讲解,在下一节中,将略述这些问题背后的数学原理,来解释这个优化问题是如何得到一个大间距分类器的。
12.3 数学背后的大边界分类(可选)
在本节课中,我将介绍一些 大间隔分类背后的数学原理 。本节为选学部分,你完全可以跳过它,但是听听这节课可能让你对支持向量机中的优化问题,以及如何得到大间距分类器,产生更好的直观理解。
首先,复习一下关于向量内积的知识。假设有两个向量,u 和 v 。两个都是二维向量,我们看一下, 的结果。 也叫做向量 u 和 v 之间的内积。由于是二维向量,我可以将它们画在这个图上。现在,很容易计算的一个量就是向量 u 的范数。表示 u 的范数,即 u 的长度,即向量 u 的欧几里得长度。根据毕达哥拉斯定理, ,这是向量 u 的长度,它是一个实数。
现在让我们回头来看向量 v ,因为我们想计算内积。v 是另一个向量,它的两个分量 v1 和 v2 是已知的。向量 v 可以画在这里,现在让我们来看看如何计算 u 和 v 之间的内积。
这就是具体做法,我们将 向量 v 投影到向量 u 上,即做一个 90 度投影将其投影到 u 上。称这条红线的长度为 p, p 就是向量 v 投影到向量 u 上的量,即p 是 v 投影到向量 u 上的长度,因此可以将,或者说 u 的长度。这是计算内积的一种方法。如果你从几何上画出 p 的值,同时画出 u 的范数,你也会同样地计算出内积,答案是一样的。
另一个计算公式是: 就是[u1 u2] 这个一行两列的矩阵乘以 v。因此可以得到 u1×v1+ u2×v2。根据线性代数的知识,这两个公式会给出同样的结果。顺便说一句,。因此如果你将u 和 v 交换位置,将 u 投影到 v 上,而不是将 v 投影到 u 上,然后做同样地计算,只是把 u和 v 的位置交换一下,你事实上可以得到同样的结果。申明一点,在这个等式中 u 的范数是一个实数,p 也是一个实数,因此就是两个实数正常相乘。
最后一点,需要注意的就是 p 值,p 事实上是有符号的,即它可能是正值,也可能是负值。若u 和 v 之间的夹角大于 90 度,则如果将 v 投影到 u 上,在这个情形下我们仍然有 是等于 p 乘以 u 的范数。唯一一点不同的是 p 在这里是负的。在内积计算中,如果 u 和 v 之间的夹角小于 90 度,那么那条红线的长度 p 是正值。然而如果这个夹角大于 90 度,则 p 将会是负的。即如果它们之间的夹角大于 90 度,两个向量之间的内积也是负的。
我们接下来将会使用这些关于向量内积的性质试图来理解支持向量机中的目标函数。
这就是我们先前给出的支持向量机模型中的 目标函数。为了讲解方便,做一点简化,仅仅是为了让目标函数更容易被分析。
我接下来忽略掉截距,令 θ0 = 0,这样更容易画示意图。我将特征数 n 置为 2,因此我们仅有两个特征 x1和 x2,现在 我们来看一下目标函数,支持向量机的优化目标函数。当我们仅有两个特征,即n=2时,这个式子可以写作:
我们只有两个参数 θ1 和 θ2。括号里面的这一项是向量 θ 的长度。这里我们用的是之前学过的向量范数的定义,事实上这就等于向量 θ 的长度。
当然你可以将其写作 θ0、θ1、θ2,如果 θ0等于 0,那就是 θ1、θ2的长度。在这里我将忽略θ0,这样来写 θ 的范数,它仅仅和 θ1θ2有关。但是,数学上不管你是否包含 θ0,其实并没有差别。这意味着我们的目标函数是等于 。因此支持向量机做的全部事情,就是 极小化参数向量 θ 范数的平方,或者说长度的平方。
现在将要看看这些项:来更深入地理解它们的含义。给定参数向量 θ 给定一个样本x,这等于什么呢? 在上一节,我们画出了在不同情形下, 的示意图,我们将会使用这些概念,θ 和就类似于 u 和 v 。
让我们看一下示意图:我们考察一个单一的训练样本,我有一个正样本在这里,用一个叉来表示这个样本 ,意思是在水平轴上取值为 ,在竖直轴上取值为 。尽管我没有将其真的看做向量。它事实上就是一个始于原点,终点位置在这个训练样本点的向量。现在,我们有一个参数向量我会将它也画成向量。我将 θ1 画在横轴这里,将 θ2 画在纵轴这里,那么内积 将会是什么呢?
使用我们之前的方法,我们计算的方式就是我将训练样本投影到参数向量 θ,然后我来看一看这个线段的长度,我将它画成红色。我将它称为 用来表示 第 i 个训练样本在参数向量 θ 上的投影。根据我们之前的内容,我们知道的是 将会等于 p 乘以向量 θ 的长度或范数。这就等于 。这两种方式是等价的,都可以用来计算θ 和 之间的内积。这里表达的意思是:这个 或者 的约束是可以被 (???) 这个约束所代替的。因为 ,将其写入我们的优化目标。我们将会得到没有了约束, 而变成了 。
需要提醒一点,我们之前曾讲过这个优化目标函数可以被写成等于 。
现在让我们考虑下面这里的训练样本。现在,继续使用之前的简化,即 θ0 =0,我们来看一下支持向量机会选择什么样的决策界。这是一种选择,我们假设支持向量机会选择这个决策边界。这不是一个非常好的选择,因为它的间距很小。这个决策界离训练样本的距离很近。我们来看一下为什么支持向量机不会选择它。
对于这样选择的参数 θ,可以看到 参数向量 θ 事实上是和决策界是 90 度正交的,因此这个绿色的决策界对应着一个参数向量 θ 指向这个方向,顺便提一句 ,θ0 =0 的简化仅仅意味着决策界必须通过原点 (0,0)。现在让我们看一下这对于优化目标函数意味着什么。
比如这个样本,我们假设它是我的第一个样本 ,如果我考察这个样本到参数 θ 的投影,投影是这个短的红线段,就等于 ,它非常短。类似地,这个样本如果它恰好是 ,我的第二个训练样本,则它到 θ 的投影我将它画成粉色,这个短的粉色线段是 ,即第二个样本到我的参数向量 θ 的投影。 事实上是一个负值, 是在相反的方向,这个向量和参数向量 θ 的夹角大于 90 度, 的值小于 0。
我们会发现这些 将会是非常小的数,因此当我们考察优化目标函数的时候,对于正样本而言,我们需要 ,但是如果 在这里非常小,那就意味着我们需要 θ 的范数非常大。类似地,对于负样本而言我们需要<=-1。我们已经在这个样本中看到 会是一个非常小的数,因此唯一的办法就是 θ 的范数变大。但是我们的目标函数是希望找到一个参数 θ,它的范数是小的。因此,这看起来不像是一个好的参数向量 θ 的选择。
相反的,来看一个不同的决策边界。比如说,支持向量机选择了这个决策界,现在状况会有很大不同。如果这是决策界,这就是相对应的参数 θ 的方向,因此,在这个决策界之下,垂直线是决策界。使用线性代数的知识,可以说明,这个绿色的决策界有一个垂直于它的向量 θ 。现在如果你考察你的数据在横轴 x 上的投影,比如这个之前提到的样本 ,当将它投影到 θ 上,就会得到它的长度是 。另一个样本,做同样的投影,会发现 的长度是负值。你会注意到现在 和这些投影长度是长多了。如果我们仍然要满足这些约束,,则因为 变大了,θ 的范数就可以变小了。因此这意味着通过选择右边的决策界,而不是左边的那个,支持向量机可以使参数 θ 的范数变小很多。
因此,如果我们想令 θ 的范数变小,从而令 θ 范数的平方变小,就让支持向量机选择右边的决策界。这就是支持向量机如何能有效地产生大间距分类的原因。
看这条绿色的决策界。我们希望正样本和负样本投影到 θ 的值大。要做到这一点的唯一方式就是选择这条绿线做决策界。这是 大间距决策界 来区分开正样本和负样本这个间距的值。这个间距的值就是 等等的值。通过让间距变大,即通过这些 等等的值,支持向量机最终可以找到一个较小的 θ 范数。这正是支持向量机中最小化目标函数的目的。
以上就是为什么支持向量机最终会找到大间距分类器的原因。因为它试图极大化这些 的范数,它们是训练样本到决策边界的距离 。最后一点,我们的推导自始至终使用了这个简化假设,就是参数 θ=0。
就像之前提到的,θ0 = 0 的作用是我们让决策界通过原点。如果你令θ0不是 0 的话,含义就是你希望决策界不通过原点。我将不会做全部的推导。实际上,支持向量机产生大间距分类器的结论,会被证明同样成立,证明方式是非常类似的,是我们刚刚做的证明的推广。
之前说过,即便 θ0不等于 0,支持向量机要做的事情都是优化这个目标函数对应着 C 值非常大的情况,但是可以说明的是,即便 θ0不等于 0,支持向量机仍然会找到正样本和负样本之间的大间距分隔。总之,我们解释了为什么支持向量机是一个大间距分类器。在下一节我们,将开始讨论如何利用支持向量机的原理,应用它们建立一个复杂的 非线性分类器。
12.4 核函数 1
回顾我们之前讨论过可以使 用高级数的多项式模型来解决无法用直线进行分隔的分类问题:
为了获得上图所示的判定边界,我们的模型可能是 的形式。
我们可以用一系列的新的特征f来替换模型中的每一项。例如令:
...
得到 。
然而,除了对原有的特征进行组合以外,有没有更好的方法来构造 f1,f2,f3?
我们可以利用 核函数来计算出新的特征。给定一个训练实例x,我们利用x的各个特征与我们预先选定的 地标(landmarks) 的近似程度来选取新的特征 f1,f2,f3。
例如:
其中:,为实例 x 中所有特征与地标 之间的距离的和。上例中的 similarity(x, )就是 核函数,具体而言,这里是一个 高斯核函数(Gaussian Kernel)。 注意:这个函数与正态分布没什么实际上的关系,只是看上去像而已。
这些地标的作用是什么?如果一个训练实例 x 与地标 L 之间的距离近似于 0,则新特征 f 近似于 ,如果训练实例 x 与地标 L 之间距离较远,则 f 近似于 。假设我们的训练实例含有两个特征[x1 x2],给定 地标 与不同的 σ 值,见下图:
图中水平面的坐标为 x1,x2而垂直坐标轴代表 f。可以看出,只有当 x 与重合时 f 才具有最大值。随着 x 的改变 f 值改变的 速率受到 σ^2 的控制。
在下图中,当实例处于洋红色的点位置处,因为其离 更近,但是离和 较远,因此 f1接近 1,而 f2,f3 接近 0。因此 ,因此预测 y=1。同理可以求出,对于离 较近的绿色点,也预测 y=1,但是对于蓝绿色的点,因为其离三个地标都较远,预测 y=0。
这样,图中红色的封闭曲线所表示的范围,便是我们依据一个单一的训练实例和我们选取的地标所得出的判定边界,在预测时,我们采用的 特征是通过核函数计算出的新特征 f1,f2,f3 ,而不是训练实例本身的特征。
12.5 核函数 2
在上一节,我们讨论了核函数这个想法,以及怎样利用它去实现支持向量机的一些新特性。在这一节视频中,我将补充一些缺失的细节,并简单的介绍一下怎么在实际中使用应用这些想法。
如何选择地标? 我们通常是根据 训练集的数量选择地标的数量,即如果训练集中有 m 个实例,则我们选取 m 个地标,并且令:。这样做的好处在于:现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的,即:
下面我们 将核函数运用到支持向量机 中,修改我们的支持向量机假设为:
给定 x,计算新特征 f,当 时,预测 y=1,否则反之。 相应地修改代价函数为:
在具体实施过程中,我们还需要对最后的归一化项进行些微调整,在计算 时,我们用 代替 ,其中 M 是根据我们选择的核函数而不同的一个矩阵。这样做的原因是为了简化计算。
理论上讲,我们也可以在逻辑回归中使用核函数,但是上面使用 M 来简化计算的方法不适用与逻辑回归,因此计算将非常耗费时间。
在此,我们不介绍最小化支持向量机的代价函数的方法,你可以使用现有的软件包(如 liblinear,libsvm 等)。在使用这些软件包最小化我们的代价函数之前,我们通常需要编写 核函数,并且如果我们使用高斯核函数,那么在使用之前进行 特征缩放 是非常必要的。
另外,支持向量机也可以不使用核函数,不使用核函数又称为线性核函数(linear kernel), 当我们不采用非常复杂的函数,或者我们的 训练集特征非常多而实例非常少 的时候,可以采用这种不带核函数的支持向量机。
下面是支持向量机的两个参数 C 和 σ 的影响:C 较大时,相当于 λ 较小,可能会导致过拟合,高方差;
C 较小时,相当于 λ 较大,可能会导致低拟合,高偏差;
σ 较大时,导致高方差;
σ 较小时,导致高偏差。
这就是利用核函数的支持向量机算法,希望这些关于偏差和方差的讨论,能给你一些对于算法结果预期的直观印象。
12.6 使用支持向量机
目前为止,我们已经讨论了 SVM 比较抽象的层面,在这个视频中我将要讨论到为了运行或者运用 SVM,你实际上所需要的一些东西:支持向量机算法 提出了一个特别优化的问题。但是就如在之前提到的,不建议自己写程序来求解参数 θ。用以解决 SVM 最优化问题的软件很复杂,且已经有研究者做了很多年数值优化了。因此强烈建议使用高优化软件库中的一个,而不是尝试自己落实一些数据。
在高斯核函数之外我们还有其他一些选择,如:多项式核函数(Polynomial Kernel)
字符串核函数(String kernel)
卡方核函数( chi-square kernel)
直方图交集核函数(histogram intersection kernel)
等等...
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征,这些核函数需要满足 Mercer's 定理,才能被支持向量机的优化软件正确处理。
多类分类问题。假设我们利用之前介绍的 一对多方法 来解决一个 多类分类问题。如果一共有 k 个类,则我们需要 k 个模型,以及 k 个参数向量 θ。我们同样也可以训练 k 个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能,我们只要直接使用即可。
尽管不用亲自去写自己的 SVM(支持向量机)的优化软件,但是你也需要做几件事:1、提出 参数 C 的选择。我们在之前讨论过误差/方差在这方面的性质。
2、需要选择 内核参数 或你想要使用的相似函数,其中一个选择是:我们选择不需要任何内核参数,没有内核参数的理念,也叫 线性核函数。因此,如果有人说他使用了线性核的 SVM(支持向量机),这就意味这他使用了不带有核函数的 SVM(支持向量机)。
从逻辑回归模型,我们得到了支持向量机模型,在两者之间,我们应该如何选择呢? 下面是一些普遍使用的准则:
n 为特征数,m 为训练样本数。
(1)如果相较于 m 而言,n 要大许多,即 训练集数据量不够支持我们训练一个复杂的非线性模型,我们选用 逻辑回归模型或不带核函数的支持向量机。
(2)如果 n 较小,而且 m 大小中等,例如 n 在 1-1000 之间,而 m 在 10-10000 之间,使用 高斯核函数的支持向量机。
(3)如果 n 较小,而 m 较大,例如 n 在 1-1000 之间,而 m 大于 50000,则使用支持向量机会非常慢,解决方案是创造、增加更多的特征,然后使用 逻辑回归或不带核函数的支持向量机。
值得一提的是,神经网络 在以上三种情况下都可能会有较好的表现,但是训练神经网络 可能非常慢,选择 支持向量机 的原因主要在于它的 代价函数是凸函数,不存在局部最小值。今天的 SVM 包会工作得很好,但是它们仍然会有一些 慢。当你有非常非常大的训练集,且用高斯核函数。在这种情况下,我经常会做的是尝试手动地创建,拥有 更多的特征变量,然后用 逻辑回归或者不带核函数的支持向量机。把这两者放在一起是有原因的。原因是:它们都是非常相似的算法,不管是逻辑回归还是不带核函数的 SVM,通常都会做相似的事情,并给出相似的结果。但是根据你实现的情况,其中一个可能会比另一个更加有效。但是随着 SVM 的复杂度增加,当你使用不同的内核函数来学习复杂的非线性函数时,当你有多达 1 万(10,000)的样本时,也可能是 5 万(50,000),你的特征变量的数量这是相当大的(???)。那是一个非常常见的体系,也许在这个体系里,不带核函数的支持向量机就会表现得相当突出。你可以做比这困难得多需要逻辑回归的事情。
最后,神经网络使用于什么时候呢? 对于所有的这些问题, 一个设计得很好的神经网络很有可能也会非常有效。不过它有一个缺点是:对于许多这样的问题,神经网络训练起来可能会 特别慢。如果你有一个非常好的 SVM 实现包,它可能会运行得比神经网络快很多。SVM 具有的优化问题,是一种 凸优化问题,因此,好的 SVM优化软件包总是会找到 全局最小值,或者接近它的值。对于 SVM 你不需要担心局部最优。在实际应用中,局部最优不是神经网络所需要解决的一个重大问题,根据你的问题,神经网络可能会比 SVM 慢,尤其是在这样一个体系中,至于这里给出的参考,看上去有些模糊。如果仍然不能完全确定该用哪个算法,这个没有太大关系,当遇到机器学习问题的时候,有时确实不清楚它是否是最好的算法,但是就如在之前的看到的,算法确实很重要,但是通常 更加重要的是:你有多少数据,你有多熟练是否擅长做误差分析和排除学习算法,指出如何设定新的特征变量和找出其他能决定你学习算法的变量等方面。通常这些方面会比你使用逻辑回归还是 SVM 这方面更加重要。
但是,已经说过了,SVM 仍然被广泛认为是一种最强大的学习算法,这是一个体系,包含了什么时候用一个有效的方法去学习复杂的非线性函数。因此实际上,一起使用逻辑回归、神经网络、 SVM这些方法来提高学习算法,会很好地建立很有技术的状态。