斯坦福第十二课：支持向量机(Support Vector Machines)
12.1 优化目标
12.2 大边界的直观理解
12.3 数学背后的大边界分类（可选）
12.4 核函数 1
12.5 核函数 2
12.6 使用支持向量机
12.1 优化目标
到目前为止,你已经见过一系列不同的学习算法。在监督学习中，许多学习算法的性能都非常类似，因此，重要的不是你该选择使用学习算法 A 还是学习算法 B，而更重要的是， 应用这些算法时，所创建的大量数据在应用这些算法时，表现情况通常依赖于你的水平。比 如：你为学习算法所设计的特征量的选择，以及如何选择正则化参数，诸如此类的事。还有 一个更加强大的算法广泛的应用于工业界和学术界，它被称为支持向量机(Support Vector Machine)。与逻辑回归和神经网络相比，支持向量机，或者简称 SVM。在学习复杂的非线性 方程时提供了一种更为清晰，更加强大的方式。因此，在接下来的视频中，我会探讨这一算 法。在稍后的课程中，我也会对监督学习算法进行简要的总结。当然，仅仅是作简要描述。 但对于支持向量机，鉴于该算法的强大和受欢迎度，在本课中，我会花许多时间来讲解它。 它也是我们所介绍的最后一个监督学习算法。
正如我们之前开发的学习算法，我们从优化目标开始。那么，我们开始学习这个算法。 为了描述支持向量机，事实上，我将会从逻辑回归开始展示我们如何一点一点修改来得到本 质上的支持向量机。
那么，在逻辑回归中我们已经熟悉了这里的假设函数形式，和右边的 S 型激励函数。然而，为了解释一些数学知识.我将用 z 表示 如果你进一步观察逻辑回归的代价函数，你会发现每个样本 (x, y)都会为总代价函数， 增加这里的一项，因此，对于总代价函数通常会有对所有的训练样本求和，并且这里还有一个 1/m 项，但是，在逻辑回归中，这里的这一项就是表示一个训练样本所对应的表达式。 现在，如果我将完整定义的假设函数代入这里。那么，我们就会得到每一个训练样本都影响这一项。 现在，先忽略 1/m 这一项，但是这一项是影响整个总代价函数中的这一项的。现在，一起来考虑两种情况：一种是 y 等于1的情况；另一种是y等于0的情况。在第一种情况中， 假设 y 等于 1，此时在目标函数中只需有第一项起作用，因为 y 等于 1 时，(1-y) 项将等于。因此，当在 y 等于 1 的样本中时，即在 (x, y) 中 y 等于 1，我们得到 当然，在代价函数中，y前面有负号。我们只是这样表示，如果 y 等于 1 代价函数中，这一项也等于 1。这样做是为了简化此处的表达式。如果画出关于 z 的函数，你会看到左下角的这条曲线，我们同样可以看到，当 z 增大时，也就是相当于 现在开始建立支持向量机，我们从这里开始：我们会从这个代价函数开始，也就是 新的代价函数将会水平的从这里到右边 (图外)，然后我再画一条同逻辑回归非常相似 的直线，但是，在这里是一条直线，也就是我用紫红色画的曲线，就是这条紫红色的曲线。 那么，到了这里已经非常接近逻辑回归中使用的代价函数了。只是这里是由两条线段组成， 即位于右边的水平部分和位于左边的直线部分，先别过多的考虑左边直线部分的斜率，这并不是很重要。但是，这里我们将使用的新的代价函数，是在 y=1 的前提下的。你也许能想到， 这应该能做同逻辑回归中类似的事情，但事实上，在之后的的优化问题中，这会变得更坚定， 并且为支持向量机，带来计算上的优势。例如，更容易计算股票交易的问题等等。 目前，我们只是讨论了 y=1 的情况，另外一种情况是当 y=0 时，此时如果你仔细观察代价函数只留下了第二项，因为第一项被消除了。如果当 y=0 时，那么这一项也就是 0 了。 所以上述表达式只留下了第二项。因此，这个样本的代价或是代价函数的贡献。将会由这一项表示。并且，如果你将这一项作为 z 的函数，那么，这里就会得到横轴 z。现在，你完成 了支持向量机中的部分内容，同样地，我们要替代这一条蓝色的线，用相似的方法。 如果我们用一个新的代价函数来代替，即这条从 0 点开始的水平直线，然后是一条斜线，像上图。那么，现在让我给这两个方程命名，左边的函数，我称之为 右边函数我称它为 这是我们在逻辑回归中使用代价函数 J(θ)。也许这个方程看起来不是非常熟悉。这是 因为之前有个负号在方程外面，但是，这里我所做的是，将负号移到了表达式的里面，这样 做使得方程看起来有些不同。对于支持向量机而言，实质上我们要将这替换为 然后，再加上正则化参数。现在，按照支持向量机的惯例，事实上，我们的书写会稍微 有些不同，代价函数的参数表示也会稍微有些不同。 首先，我们要除去 1/m 这一项，当然，这仅仅是由于人们使用支持向量机时，对比于 逻辑回归而言，不同的习惯所致，但这里我所说的意思是：你知道，我将要做的是仅仅除去 1/m 这一项，但是，这也会得出同样的θ最优值，好的，因为 1/m 仅是个常量，因此，你知 道在这个最小化问题中，无论前面是否有 1/m 这一项，最终我所得到的最优值θ都是一样 的。这里我的意思是，先给你举一个实例，假定有一最小化问题：即要求当 (u-5)^2+1 取得 最小值时的 u 值，这时最小值为：当 u=5 时取得最小值。 现在，如果我们想要将这个目标函数乘上常数 10，这里我的最小化问题就变成了：求 使得 10×(u-5)^2+10 最小的值 u，然而，使得这里最小的 u 值仍为 5。因此将一些常数乘以 你的最小化项，这并不会改变最小化该方程时得到 u 值。因此，这里我所做的是删去常量 m。也相同的，我将目标函数乘上一个常量 m，并不会改变取得最小值时的θ值。 第二点概念上的变化，我们只是指在使用，支持向量机时，一些如下的标准惯例，而不 是逻辑回归。因此，对于逻辑回归，在目标函数中，我们有两项：第一个是训练样本的代价， 第二个是我们的正则化项，我们不得不去用这一项来平衡。这就相当于我们想要最小化 A 加 上正则化参数λ，然后乘以其他项 B 对吧？这里的 A 表示这里的第一项，同时我用 B 表示 第二项，但不包括λ，我们不是优化这里的 A+λ×B。我们所做的是通过设置不同正则参数 λ 达到优化目的。这样，我们就能够权衡对应的项，是使得训练样本拟合的更好。即最小 化 A。还是保证正则参数足够小，也即是对于 B 项而言，但对于支持向量机，按照惯例，我 们将使用一个不同的参数替换这里使用的 λ来权衡这两项。你知道，就是第一项和第二项 我们依照惯例使用一个不同的参数称为 C，同时改为优化目标，C×A+B 因此，在逻辑回归中，如果给定λ，一个非常大的值，意味着给予 B 更大的权重。而这里，就对应于将 C 设定为非常小的值，那么，相应的将会给 B 比给 A 更大的权重。因此，这只是一种不同的方式来控 制这种权衡或者一种不同的方法，即用参数来决定是更关心第一项的优化，还是更关心第二 项的优化。当然你也可以把这里的参数 C 考虑成 1/λ，同 1/λ 所扮演的角色相同，并且 这两个方程或这两个表达式并不相同，因为 C 等于 1/λ，但是也并不全是这样，如果当 C 等于 1/λ时，这两个优化目标应当得到相同的值，相同的最优值θ。因此，就用它们来代替。 那么，我现在删掉这里的λ，并且用常数 C 来代替。因此，这就得到了在支持向量机中我们 的整个优化目标函数。然后最小化这个目标函数，得到 SVM 学习到的参数 C。 最后有别于逻辑回归输出的概率。在这里，我们的代价函数，当最小化代价函数，获得参数θ时，支持向量机所做的是它来直接预测 y 的值等于 1，还是等于 0。因此，这个假设函数会预测 1。当 人们有时将支持向量机看作是大间距分类器。在这一部分，我将介绍其中的含义，这有 助于我们直观理解 SVM 模型的假设是什么样的这是我的支持向量机模型的代价函数，在左边这里我画出了关于 z 的代价函数 如果 C 非常大，则最小化代价函数的时候，我们将会很希望找到一个使第一项为 0 的 最优解。因此，让我们尝试在代价项的第一项为 0 的情形下理解该优化问题。比如我们可以 把 C 设置成了非常大的常数，这将给我们一些关于支持向量机模型的直观感受。 我们已经看到输入一个训练样本标签为 y=1，你想令第一项为 0，你需要做的是找到一个 θ，使得 这将遵从以下的约束： 具体而言，如果你考察这样一个数据集，其中有正样本，也有负样本，可以看到这个数 据集是线性可分的。我的意思是，存在一条直线把正负样本分开。当然有多条不同的直线， 可以把正样本和负样本完全分开。 比如，这就是一个决策边界可以把正样本和负样本分开。但是多多少少这个看起来并不 是非常自然是么? 或者我们可以画一条更差的决策界，这是另一条决策边界，可以将正样本和负样本分开，但仅仅是勉强分开，这些决策边界看起来都不是特别好的选择，支持向量机将会选择这个黑 色的决策边界，相较于之前我用粉色或者绿色画的决策界。这条黑色的看起来好得多，黑线 看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。数学上来讲，这是什么 意思呢？这条黑线有更大的距离，这个距离叫做间距 (margin)。 当画出这两条额外的蓝线，我们看到黑色的决策界和训练样本之间有更大的最短距离。 然而粉线和蓝线离训练样本就非常近，在分离样本的时候就会比黑线表现差。因此，这个距 离叫做支持向量机的间距，而这是支持向量机具有鲁棒性的原因，因为它努力用一个最大间 距来分离样本。因此支持向量机有时被称为大间距分类器，而这其实是求解上一页幻灯片上 优化问题的结果。 我知道你也许想知道求解上一页幻灯片中的优化问题为什么会产生这个结果？它是如 何产生这个大间距分类器的呢？我知道我还没有解释这一点。 我将会从直观上略述为什么这个优化问题会产生大间距分类器。总之这个图示有助于你 理解支持向量机模型的做法，即努力将正样本和负样本用最大的间距分开。 在本节课中关于大间距分类器，我想讲最后一点：我们将这个大间距分类器中的正则化 因子常数 C 设置的非常大，我记得我将其设置为了 100000，因此对这样的一个数据集，也 许我们将选择这样的决策界，从而最大间距地分离开正样本和负样本。那么在让代价函数最小化的过程中，我们希望找出在 y=1 和 y=0 两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这 样的参数，则我们的最小化问题便转变成： 事实上，支持向量机现在要比这个大间距分类器所体现得更成熟，尤其是当你使用大间 距分类器的时候，你的学习算法会受异常点 (outlier) 的影响。比如我们加入一个额外的正 样本。 在这里，如果你加了这个样本，为了将样本用最大间距分开，也许我最终会得到一条类 似这样的决策界，对么？就是这条粉色的线，仅仅基于一个异常值，仅仅基于一个样本，就 将我的决策界从这条黑线变到这条粉线，这实在是不明智的。而如果正则化参数 C，设置的 非常大，这事实上正是支持向量机将会做的。它将决策界，从黑线变到了粉线，但是如果 C 设置的小一点，如果你将 C 设置的不要太大，则你最终会得到这条黑线，当然数据如果不是线性可分的，如果你在这里有一些正样本或者你在这里有一些负样本，则支持向量机也会 将它们恰当分开。因此，大间距分类器的描述，仅仅是从直观上给出了正则化参数 C 非常大 的情形，同时，要提醒你 C 的作用类似于 1/λ，λ是我们之前使用过的正则化参数。这只是C 非常大的情形，或者等价地λ非常小的情形。你最终会得到类似粉线这样的决策界，但是 实际上应用支持向量机的时候，当 C 不是非常非常大的时候，它可以忽略掉一些异常点的 影响，得到更好的决策界。甚至当你的数据不是线性可分的时候，支持向量机也可以给出好 的结果。 回顾 C=1/λ，因此： C 较大时，相当于 λ 较小，可能会导致过拟合，高方差。 C 较小时，相当于 λ 较大，可能会导致低拟合，高偏差。 我们稍后会介绍支持向量机的偏差和方差，希望在那时候关于如何处理参数的这种平衡会变得更加清晰。我希望，这节课给出了一些关于为什么支持向量机被看做大间距分类器的 直观理解。它用最大间距将样本区分开，尽管从技术上讲，这只有当参数 C 是非常大的时候 是真的，但是它对于理解支持向量机是有益的。 本节课中我们略去了一步，那就是我们在幻灯片中给出的优化问题。为什么会是这样的？ 它是如何得出大间距分类器的？我在本节中没有讲解，在下一节课中，我将略述这些问题背 后的数学原理，来解释这个优化问题是如何得到一个大间距分类器的。 在本节课中，我将介绍一些大间隔分类背后的数学原理。本节为选学部分，你完全可以 跳过它，但是听听这节课可能让你对支持向量机中的优化问题，以及如何得到大间距分类器， 产生更好的直观理解。 首先，让我来给大家复习一下关于向量内积的知识。假设我有两个向量，u 和 v 我将它 们写在这里。两个都是二维向量，我们看一下， 现在让我们回头来看向量 v ，因为我们想计算内积。v 是另一个向量，它的两个分量 v1 和 v2 是已知的。向量 v 可以画在这里，现在让我们来看看如何计算 u 和 v 之间的内积。 这就是具体做法，我们将向量 v 投影到向量 u 上，我们做一个直角投影，或者说一个 90 度 投影将其投影到 u 上，接下来我度量这条红线的长度。我称这条红线的长度为 p，因此 p 就 是长度，或者说是向量 v 投影到向量 u 上的量，我将它写下来，p 是 v 投影到向量 u 上的长度，因此可以将 最后一点，需要注意的就是 p 值，p 事实上是有符号的，即它可能是正值，也可能是负 值。我的意思是说，如果 u 是一个类似这样的向量，v 是一个类似这样的向量，u 和 v 之间 的夹角大于 90 度，则如果将 v 投影到 u 上，会得到这样的一个投影，这是 p 的长度，在这 个情形下我们仍然有 这就是我们先前给出的支持向量机模型中的目标函数。为了讲解方便，我做一点简化， 仅仅是为了让目标函数更容易被分析。 我接下来忽略掉截距，令θ0 = 0，这样更容易画示意图。我将特征数 n 置为 2，因此我 们仅有两个特征 x1 和 x2，现在 我们来看一下目标函数，支持向量机的优化目标函数。当我 们仅有两个特征，即 n=2 时，这个式子可以写作：，我们只有两个参数θ1 和θ2。你可能注意到括号里面的这一项是向量θ的范数，或者说是向量θ的长度。我的意思是如果我们将向量θ 写出来，那么我刚刚画红线的这一项就是向量θ的长度或范数。这里我们用的是之前学过的 向量范数的定义事实上这就等于向量θ的长度。 当然你可以将其写作θ0、θ1、θ2，如果θ0 等于 0，那就是θ1θ2 的长度。在这里我将 忽略θ0，这样来写θ的范数，它仅仅和θ1θ2 有关。但是，数学上不管你是否包含θ0，其 实并没有差别，因此在我们接下来的推导中去掉θ0 不会有影响这意味着我们的目标函数是等于 12.4 核函数 1 在上一节视频里，我们讨论了核函数这个想法，以及怎样利用它去实现支持向量机的一 些新特性。在这一节视频中，我将补充一些缺失的细节，并简单的介绍一下怎么在实际中使 用应用这些想法。 如何选择地标？ 我们通常是根据训练集的数量选择地标的数量，即如果训练集中有 m 个实例，则我们 选取 m 个地标，并且令：l(1)=x(1),l(2)=x(2),...,l(m)=x(m)。这样做的好处在于：现在我们得到的新特 征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即： 目前为止，我们已经讨论了 SVM 比较抽象的层面，在这个视频中我将要讨论到为了运 行或者运用 SVM。你实际上所需要的一些东西：支持向量机算法，提出了一个特别优化的问题。但是就如在之前的视频中我简单提到的，我真的不建议你自己写软件来求解参数θ，因 此由于今天我们中的很少人，或者其实没有人考虑过自己写代码来转换矩阵，或求一个数的 平方根等我们只是知道如何去调用库函数来实现这些功能。同样的，用以解决 SVM 最优化 问题的软件很复杂，且已经有研究者做了很多年数值优化了。因此你提出好的软件库和好的 软件包来做这样一些事儿。然后强烈建议使用高优化软件库中的一个，而不是尝试自己落实 一些数据。有许多好的软件库，我正好用得最多的两个是 liblinear 和 libsvm，但是真的有很 多软件库可以用来做这件事儿。你可以连接许多你可能会用来编写学习算法的主要编程语言。 在高斯核函数之外我们还有其他一些选择，如： 多项式核函数（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 另一个也很有可能很有效。但是随着 SVM 的复杂度增加，当你使用不同的内核函数来 学习复杂的非线性函数时，这个体系，你知道的，当你有多达 1 万（10,000）的样本时，也 可能是 5 万（50,000），你的特征变量的数量这是相当大的。那是一个非常常见的体系，也许在这个体系里，不带核函数的支持向量机就会表现得相当突出。你可以做比这困难得多需 要逻辑回归的事情。 最后，神经网络使用于什么时候呢？ 对于所有的这些问题，对于所有的这些不同体系 一个设计得很好的神经网络也很有可能会非常有效。有一个缺点是，或者说是有时可能不会 使用神经网络的原因是：对于许多这样的问题，神经网络训练起来可能会特别慢，但是如果 你有一个非常好的 SVM 实现包，它可能会运行得比较快比神经网络快很多，尽管我们在此之前没有展示，但是事实证明，SVM 具有的优化问题，是一种凸优化问题。因此，好的 SVM优化软件包总是会找到全局最小值，或者接近它的值。对于 SVM 你不需要担心局部最优。 在实际应用中，局部最优不是神经网络所需要解决的一个重大问题，所以这是你在使用 SVM 的时候不需要太去担心的一个问题。根据你的问题，神经网络可能会比 SVM 慢，尤其是在 这样一个体系中，至于这里给出的参考，看上去有些模糊，如果你在考虑一些问题，这些参 考会有一些模糊，但是我仍然不能完全确定，我是该用这个算法还是改用那个算法，这个没 有太大关系，当我遇到机器学习问题的时候，有时它确实不清楚这是否是最好的算法，但是 就如在之前的视频中看到的算法确实很重要。但是通常更加重要的是：你有多少数据，你有 多熟练是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能决定 你学习算法的变量等方面，通常这些方面会比你使用逻辑回归还是 SVM 这方面更加重要。 但是，已经说过了，SVM 仍然被广泛认为是一种最强大的学习算法，这是一个体系，包含了 什么时候一个有效的方法去学习复杂的非线性函数。因此，实际上与逻辑回归神经网络 SVM 一起使用这些方法来提高学习算法，我认为你会很好地建立很有技术的状态。 机器学习系统对于一个宽泛的应用领域来说，这是另一个在你军械库里非常强大的工具， 你可以把它应用到很多地方，如硅谷、在工业、学术等领域建立许多高性能的机器学习系统。
。 现在考虑下我们想要逻辑回归做什么：如果有一个y=1的样本，我的意思是不管是在训练集中或是在测试集中，又或者在交叉验证集中，总之是 y=1，现在我们希望 h(x) 趋近
，当 z 远大于 0 时，即到了该图的右边，你不难发现此时逻辑回归的输出将趋近于 1。相反地，如果我们有另一个样本，即 y=0。我们希望假设函数的输出值将趋近于 0，这对应于
。
增大时，z 对应的值会变的非常小。对整个代价函数而言，影响也非常小。这也就解释了，为什么逻辑回归在观察到正样本 y=1 时，试图将
12.2 大边界的直观理解
>=1，反之，如果 y 是等于 0 的，我们观察一下，函数 cost0(z)，它只有在 z<=1的区间里函数值为 0。这是支持向量机的一个有趣性质。事实上，如果你有一个正样本 y 等 于 1，则其实我们仅仅要求>0大的话，我们的模型代价函数值为 0，类似地，如果你有一个负样本，则仅需要<=0 就 会将负例正确分离，但是，支持向量机的要求更高，不仅仅要能正确分开输入的样本，即不 仅仅要求>0，我们需要的是比 0 值大很多，比如大于等于 1，我也想这个比 0 小很多， 比如我希望它小于等于-1，这就相当于在支持向量机中嵌入了一个额外的安全因子。或者说安全的间距因子。 当然，逻辑回归做了类似的事情。但是让我们看一下，在支持向量机中，这个因子会导致什么结果。具体而言，我接下来会考虑一个特例。我们将这个常数 C 设置成一个非常大 的值。比如我们假设 C 的值为 100000 或者其它非常大的数，然后来观察支持向量机会给出 什么结果？
<=-1。因此，现在考虑我们的优化问题。选择参数，使得第一项等于 0，就会导致下面的优化问题，因为我们将选择参数使第一项为 0，因此这个函数的第一项为 0， 因此是 C 乘以 0 加上二分之一乘以第二项。这里第一项是 C 乘以 0，因此可以将其删去， 因为我知道它是 0。
12.3 数学背后的大边界分类（可选）
u 表示 u 的范数，即 u 的长度，即向量 u 的欧几里得长度。根据毕达哥拉斯定理， 
极小化参数向量θ范数的平方或者说长度的平方。现在我将要看看这些项：
更深入地理解它们的含义。给定参数向量θ给定一个样本 x，这等于什么呢? 在前一页幻灯片上，我们画出了在不同情形下，
12.5 核函数 2
12.6 使用支持向量机
最新文章
热门文章