经典算法解读：一文看懂支持向量机以及推导
本文是吴恩达老师的机器学习课程[1]和《统计学习方法》[2]的笔记和代码复现部分（支持向量机）。
作者：黄海广[3]
备注：笔记和作业（含数据、原始作业文件）、视频都在 github 中下载。
我将陆续将课程笔记和课程代码发布在公众号“机器学习初学者”，敬请关注。这个是第三部分：支持向量机，是原教程的第七周，包含了笔记和作业代码（原课程作业是 OCTAVE 的，这里是复现的 python 代码）
已完成
本文资源都在 github：
https://github.com/fengdu78/Coursera-ML-AndrewNg-Notes https://github.com/fengdu78/lihang-code
笔记部分：
十二、支持向量机(Support Vector Machines)
12.1 优化目标
参考视频: 12 - 1 - Optimization Objective (15 min).mkv
到目前为止,你已经见过一系列不同的学习算法。在监督学习中，许多学习算法的性能都非常类似，因此，重要的不是你该选择使用学习算法A还是学习算法B，而更重要的是，应用这些算法时，所创建的大量数据在应用这些算法时，表现情况通常依赖于你的水平。比如：你为学习算法所设计的特征量的选择，以及如何选择正则化参数，诸如此类的事。还有一个更加强大的算法广泛的应用于工业界和学术界，它被称为支持向量机(Support Vector Machine)。与逻辑回归和神经网络相比，支持向量机，或者简称SVM，在学习复杂的非线性方程时提供了一种更为清晰，更加强大的方式。因此，在接下来的视频中，我会探讨这一算法。在稍后的课程中，我也会对监督学习算法进行简要的总结。当然，仅仅是作简要描述。但对于支持向量机，鉴于该算法的强大和受欢迎度，在本课中，我会花许多时间来讲解它。它也是我们所介绍的最后一个监督学习算法。
正如我们之前开发的学习算法，我们从优化目标开始。那么，我们开始学习这个算法。为了描述支持向量机，事实上，我将会从逻辑回归开始展示我们如何一点一点修改来得到本质上的支持向量机。
那么，在逻辑回归中我们已经熟悉了这里的假设函数形式，和右边的 S 型激励函数。然而，为了解释一些数学知识.我将用 表示。
现在考虑下我们想要逻辑回归做什么：如果有一个 的样本，我的意思是不管是在训练集中或是在测试集中，又或者在交叉验证集中，总之是 ，现在我们希望 趋近 1。因为我们想要正确地将此样本分类，这就意味着当 趋近于 1 时， 应当远大于 0，这里的意思是远远大于 0。这是因为由于 表示 ，当 远大于 0 时，即到了该图的右边，你不难发现此时逻辑回归的输出将趋近于 1。相反地，如果我们有另一个样本，即。我们希望假设函数的输出值将趋近于 0，这对应于，或者就是 会远小于 0，因为对应的假设函数的输出值趋近 0。
如果你进一步观察逻辑回归的代价函数，你会发现每个样本 都会为总代价函数，增加这里的一项，因此，对于总代价函数通常会有对所有的训练样本求和，并且这里还有一个项，但是，在逻辑回归中，这里的这一项就是表示一个训练样本所对应的表达式。现在，如果我将完整定义的假设函数代入这里。那么，我们就会得到每一个训练样本都影响这一项。
现在，先忽略 这一项，但是这一项是影响整个总代价函数中的这一项的。
现在，一起来考虑两种情况：
一种是等于 1 的情况；另一种是 等于 0 的情况。
在第一种情况中，假设 ，此时在目标函数中只需有第一项起作用，因为时，项将等于 0。因此，当在 的样本中时，即在 中 ，我们得到 这样一项，这里同上一张幻灯片一致。
我用 表示，即： 。当然，在代价函数中， 前面有负号。我们只是这样表示，如果 代价函数中，这一项也等于 1。这样做是为了简化此处的表达式。如果画出关于 的函数，你会看到左下角的这条曲线，我们同样可以看到，当 增大时，也就是相当于增大时， 对应的值会变的非常小。对整个代价函数而言，影响也非常小。这也就解释了，为什么逻辑回归在观察到正样本时，试图将设置得非常大。因为，在代价函数中的这一项会变的非常小。
现在开始建立支持向量机，我们从这里开始：
我们会从这个代价函数开始，也就是一点一点修改，让我取这里的 点，我先画出将要用的代价函数。
新的代价函数将会水平的从这里到右边(图外)，然后我再画一条同逻辑回归非常相似的直线，但是，在这里是一条直线，也就是我用紫红色画的曲线，就是这条紫红色的曲线。那么，到了这里已经非常接近逻辑回归中使用的代价函数了。只是这里是由两条线段组成，即位于右边的水平部分和位于左边的直线部分，先别过多的考虑左边直线部分的斜率，这并不是很重要。但是，这里我们将使用的新的代价函数，是在的前提下的。你也许能想到，这应该能做同逻辑回归中类似的事情，但事实上，在之后的优化问题中，这会变得更坚定，并且为支持向量机，带来计算上的优势。例如，更容易计算股票交易的问题等等。
目前，我们只是讨论了的情况，另外一种情况是当时，此时如果你仔细观察代价函数只留下了第二项，因为第一项被消除了。如果当时，那么这一项也就是 0 了。所以上述表达式只留下了第二项。因此，这个样本的代价或是代价函数的贡献。将会由这一项表示。并且，如果你将这一项作为的函数，那么，这里就会得到横轴。现在，你完成了支持向量机中的部分内容，同样地，我们要替代这一条蓝色的线，用相似的方法。
如果我们用一个新的代价函数来代替，即这条从 0 点开始的水平直线，然后是一条斜线，像上图。那么，现在让我给这两个方程命名，左边的函数，我称之为，同时，右边函数我称它为。这里的下标是指在代价函数中，对应的 和 的情况，拥有了这些定义后，现在，我们就开始构建支持向量机。
这是我们在逻辑回归中使用代价函数。也许这个方程看起来不是非常熟悉。这是因为之前有个负号在方程外面，但是，这里我所做的是，将负号移到了表达式的里面，这样做使得方程看起来有些不同。对于支持向量机而言，实质上我们要将这替换为，也就是，同样地，我也将这一项替换为，也就是代价。这里的代价函数，就是之前所提到的那条线。此外，代价函数，也是上面所介绍过的那条线。因此，对于支持向量机，我们得到了这里的最小化问题，即:
然后，再加上正则化参数。现在，按照支持向量机的惯例，事实上，我们的书写会稍微有些不同，代价函数的参数表示也会稍微有些不同。
首先，我们要除去这一项，当然，这仅仅是由于人们使用支持向量机时，对比于逻辑回归而言，不同的习惯所致，但这里我所说的意思是：你知道，我将要做的是仅仅除去这一项，但是，这也会得出同样的 最优值，好的，因为 仅是个常量，因此，你知道在这个最小化问题中，无论前面是否有 这一项，最终我所得到的最优值都是一样的。这里我的意思是，先给你举一个样本，假定有一最小化问题：即要求当取得最小值时的值，这时最小值为：当时取得最小值。
现在，如果我们想要将这个目标函数乘上常数 10，这里我的最小化问题就变成了：求使得最小的值，然而，使得这里最小的值仍为 5。因此将一些常数乘以你的最小化项，这并不会改变最小化该方程时得到值。因此，这里我所做的是删去常量。也相同的，我将目标函数乘上一个常量，并不会改变取得最小值时的值。
第二点概念上的变化，我们只是指在使用支持向量机时，一些如下的标准惯例，而不是逻辑回归。因此，对于逻辑回归，在目标函数中，我们有两项：第一个是训练样本的代价，第二个是我们的正则化项，我们不得不去用这一项来平衡。这就相当于我们想要最小化加上正则化参数，然后乘以其他项对吧？这里的表示这里的第一项，同时我用B表示第二项，但不包括，我们不是优化这里的。我们所做的是通过设置不同正则参数达到优化目的。这样，我们就能够权衡对应的项，是使得训练样本拟合的更好。即最小化。还是保证正则参数足够小，也即是对于B项而言，但对于支持向量机，按照惯例，我们将使用一个不同的参数替换这里使用的来权衡这两项。你知道，就是第一项和第二项我们依照惯例使用一个不同的参数称为，同时改为优化目标，。因此，在逻辑回归中，如果给定，一个非常大的值，意味着给予更大的权重。而这里，就对应于将 设定为非常小的值，那么，相应的将会给比给更大的权重。因此，这只是一种不同的方式来控制这种权衡或者一种不同的方法，即用参数来决定是更关心第一项的优化，还是更关心第二项的优化。当然你也可以把这里的参数 考虑成，同 所扮演的角色相同，并且这两个方程或这两个表达式并不相同，因为，但是也并不全是这样，如果当时，这两个优化目标应当得到相同的值，相同的最优值 。因此，就用它们来代替。那么，我现在删掉这里的，并且用常数来代替。因此，这就得到了在支持向量机中我们的整个优化目标函数。然后最小化这个目标函数，得到SVM 学习到的参数。
最后有别于逻辑回归输出的概率。在这里，我们的代价函数，当最小化代价函数，获得参数时，支持向量机所做的是它来直接预测的值等于 1，还是等于 0。因此，这个假设函数会预测 1。当大于或者等于 0 时，或者等于 0 时，所以学习参数就是支持向量机假设函数的形式。那么，这就是支持向量机数学上的定义。
在接下来的视频中，让我们再回去从直观的角度看看优化目标，实际上是在做什么，以及 SVM 的假设函数将会学习什么，同时也会谈谈如何做些许修改，学习更加复杂、非线性的函数。
12.2 大边界的直观理解
参考视频: 12 - 2 - Large Margin Intuition (11 min).mkv
人们有时将支持向量机看作是大间距分类器。在这一部分，我将介绍其中的含义，这有助于我们直观理解SVM模型的假设是什么样的。
这是我的支持向量机模型的代价函数，在左边这里我画出了关于的代价函数，此函数用于正样本，而在右边这里我画出了关于的代价函数，横轴表示，现在让我们考虑一下，最小化这些代价函数的必要条件是什么。如果你有一个正样本，，则只有在时，代价函数才等于 0。
换句话说，如果你有一个正样本，我们会希望，反之，如果，我们观察一下，函数，它只有在的区间里函数值为 0。这是支持向量机的一个有趣性质。事实上，如果你有一个正样本，则其实我们仅仅要求大于等于 0，就能将该样本恰当分出，这是因为如果>0 大的话，我们的模型代价函数值为 0，类似地，如果你有一个负样本，则仅需要<=0 就会将负例正确分离，但是，支持向量机的要求更高，不仅仅要能正确分开输入的样本，即不仅仅要求>0，我们需要的是比 0 值大很多，比如大于等于 1，我也想这个比 0 小很多，比如我希望它小于等于-1，这就相当于在支持向量机中嵌入了一个额外的安全因子，或者说安全的间距因子。
当然，逻辑回归做了类似的事情。但是让我们看一下，在支持向量机中，这个因子会导致什么结果。具体而言，我接下来会考虑一个特例。我们将这个常数设置成一个非常大的值。比如我们假设的值为 100000 或者其它非常大的数，然后来观察支持向量机会给出什么结果？
如果 非常大，则最小化代价函数的时候，我们将会很希望找到一个使第一项为 0 的最优解。因此，让我们尝试在代价项的第一项为 0 的情形下理解该优化问题。比如我们可以把设置成了非常大的常数，这将给我们一些关于支持向量机模型的直观感受。
我们已经看到输入一个训练样本标签为，你想令第一项为 0，你需要做的是找到一个，使得，类似地，对于一个训练样本，标签为，为了使 函数的值为 0，我们需要。因此，现在考虑我们的优化问题。选择参数，使得第一项等于 0，就会导致下面的优化问题，因为我们将选择参数使第一项为 0，因此这个函数的第一项为 0，因此是乘以 0 加上二分之一乘以第二项。这里第一项是乘以 0，因此可以将其删去，因为我知道它是 0。
这将遵从以下的约束：，如果 是等于 1 的，，如果样本是一个负样本，这样当你求解这个优化问题的时候，当你最小化这个关于变量的函数的时候，你会得到一个非常有趣的决策边界。
具体而言，如果你考察这样一个数据集，其中有正样本，也有负样本，可以看到这个数据集是线性可分的。我的意思是，存在一条直线把正负样本分开。当然有多条不同的直线，可以把正样本和负样本完全分开。
比如，这就是一个决策边界可以把正样本和负样本分开。但是多多少少这个看起来并不是非常自然是么?
或者我们可以画一条更差的决策界，这是另一条决策边界，可以将正样本和负样本分开，但仅仅是勉强分开，这些决策边界看起来都不是特别好的选择，支持向量机将会选择这个黑色的决策边界，相较于之前我用粉色或者绿色画的决策界。这条黑色的看起来好得多，黑线看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。数学上来讲，这是什么意思呢？这条黑线有更大的距离，这个距离叫做间距(margin)。
当画出这两条额外的蓝线，我们看到黑色的决策界和训练样本之间有更大的最短距离。然而粉线和蓝线离训练样本就非常近，在分离样本的时候就会比黑线表现差。因此，这个距离叫做支持向量机的间距，而这是支持向量机具有鲁棒性的原因，因为它努力用一个最大间距来分离样本。因此支持向量机有时被称为大间距分类器，而这其实是求解上一页幻灯片上优化问题的结果。
我知道你也许想知道求解上一页幻灯片中的优化问题为什么会产生这个结果？它是如何产生这个大间距分类器的呢？我知道我还没有解释这一点。
我将会从直观上略述为什么这个优化问题会产生大间距分类器。总之这个图示有助于你理解支持向量机模型的做法，即努力将正样本和负样本用最大的间距分开。
在本节课中关于大间距分类器，我想讲最后一点：我们将这个大间距分类器中的正则化因子常数设置的非常大，我记得我将其设置为了 100000，因此对这样的一个数据集，也许我们将选择这样的决策界，从而最大间距地分离开正样本和负样本。那么在让代价函数最小化的过程中，我们希望找出在和两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数，则我们的最小化问题便转变成：
事实上，支持向量机现在要比这个大间距分类器所体现得更成熟，尤其是当你使用大间距分类器的时候，你的学习算法会受异常点(outlier) 的影响。比如我们加入一个额外的正样本。
在这里，如果你加了这个样本，为了将样本用最大间距分开，也许我最终会得到一条类似这样的决策界，对么？就是这条粉色的线，仅仅基于一个异常值，仅仅基于一个样本，就将我的决策界从这条黑线变到这条粉线，这实在是不明智的。而如果正则化参数，设置的非常大，这事实上正是支持向量机将会做的。它将决策界，从黑线变到了粉线，但是如果 设置的小一点，**如果你将 C 设置的不要太大，则你最终会得到这条黑线，**当然数据如果不是线性可分的，如果你在这里有一些正样本或者你在这里有一些负样本，则支持向量机也会将它们恰当分开。因此，大间距分类器的描述，仅仅是从直观上给出了正则化参数非常大的情形，同时，要提醒你的作用类似于，是我们之前使用过的正则化参数。这只是非常大的情形，或者等价地 非常小的情形。你最终会得到类似粉线这样的决策界，但是实际上应用支持向量机的时候，**当不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。**甚至当你的数据不是线性可分的时候，支持向量机也可以给出好的结果。
回顾 ，因此：
较大时，相当于 较小，可能会导致过拟合，高方差。
较小时，相当于较大，可能会导致低拟合，高偏差。
我们稍后会介绍支持向量机的偏差和方差，希望在那时候关于如何处理参数的这种平衡会变得更加清晰。我希望，这节课给出了一些关于为什么支持向量机被看做大间距分类器的直观理解。它用最大间距将样本区分开，尽管从技术上讲，这只有当参数是非常大的时候是真的，但是它对于理解支持向量机是有益的。
本节课中我们略去了一步，那就是我们在幻灯片中给出的优化问题。为什么会是这样的？它是如何得出大间距分类器的？我在本节中没有讲解，在下一节课中，我将略述这些问题背后的数学原理，来解释这个优化问题是如何得到一个大间距分类器的。
12.3 大边界分类背后的数学（选修）
参考视频: 12 - 3 - Mathematics Behind Large Margin Classification (Optional) (20 min).mkv
在本节课中，我将介绍一些大间隔分类背后的数学原理。本节为选修部分，你完全可以跳过它，但是听听这节课可能让你对支持向量机中的优化问题，以及如何得到大间距分类器，产生更好的直观理解。
首先，让我来给大家复习一下关于向量内积的知识。假设我有两个向量，和，我将它们写在这里。两个都是二维向量，我们看一下，的结果。也叫做向量和之间的内积。由于是二维向量，我可以将它们画在这个图上。我们说，这就是向量即在横轴上，取值为某个，而在纵轴上，高度是某个作为的第二个分量。现在，很容易计算的一个量就是向量的范数。表示的范数，即的长度，即向量的欧几里得长度。根据毕达哥拉斯定理，，这是向量的长度，它是一个实数。现在你知道了这个的长度是多少了。我刚刚画的这个向量的长度就知道了。
现在让我们回头来看向量 ，因为我们想计算内积。是另一个向量，它的两个分量和是已知的。向量可以画在这里，现在让我们来看看如何计算和之间的内积。这就是具体做法，我们将向量投影到向量上，我们做一个直角投影，或者说一个 90 度投影将其投影到上，接下来我度量这条红线的长度。我称这条红线的长度为，因此就是长度，或者说是向量投影到向量上的量，我将它写下来，是投影到向量上的长度，因此可以将，或者说的长度。这是计算内积的一种方法。如果你从几何上画出的值，同时画出的范数，你也会同样地计算出内积，答案是一样的。另一个计算公式是：就是 这个一行两列的矩阵乘以。因此可以得到。根据线性代数的知识，这两个公式会给出同样的结果。顺便说一句，。因此如果你将和交换位置，将投影到上，而不是将投影到上，然后做同样地计算，只是把和的位置交换一下，你事实上可以得到同样的结果。申明一点，在这个等式中的范数是一个实数，也是一个实数，因此就是两个实数正常相乘。
最后一点，需要注意的就是值，事实上是有符号的，即它可能是正值，也可能是负值。我的意思是说，如果是一个类似这样的向量，是一个类似这样的向量，和之间的夹角大于 90 度，则如果将投影到上，会得到这样的一个投影，这是的长度，在这个情形下我们仍然有是等于乘以的范数。唯一一点不同的是在这里是负的。在内积计算中，如果和之间的夹角小于 90 度，那么那条红线的长度是正值。然而如果这个夹角大于 90 度，则将会是负的。就是这个小线段的长度是负的。如果它们之间的夹角大于 90 度，两个向量之间的内积也是负的。这就是关于向量内积的知识。我们接下来将会使用这些关于向量内积的性质试图来理解支持向量机中的目标函数。
这就是我们先前给出的支持向量机模型中的目标函数。为了讲解方便，我做一点简化，仅仅是为了让目标函数更容易被分析。
我接下来忽略掉截距，令，这样更容易画示意图。我将特征数置为 2，因此我们仅有两个特征，现在我们来看一下目标函数，支持向量机的优化目标函数。当我们仅有两个特征，即时，这个式子可以写作：，我们只有两个参数。你可能注意到括号里面的这一项是向量的范数，或者说是向量的长度。我的意思是如果我们将向量写出来，那么我刚刚画红线的这一项就是向量的长度或范数。这里我们用的是之前学过的向量范数的定义，事实上这就等于向量的长度。
当然你可以将其写作，如果，那就是的长度。在这里我将忽略，这样来写的范数，它仅仅和有关。但是，数学上不管你是否包含，其实并没有差别，因此在我们接下来的推导中去掉不会有影响这意味着我们的目标函数是等于。因此支持向量机做的全部事情，就是极小化参数向量范数的平方，或者说长度的平方。
现在我将要看看这些项：更深入地理解它们的含义。给定参数向量给定一个样本，这等于什么呢?在前一页幻灯片上，我们画出了在不同情形下，的示意图，我们将会使用这些概念，和就类似于和 。
让我们看一下示意图：我们考察一个单一的训练样本，我有一个正样本在这里，用一个叉来表示这个样本，意思是在水平轴上取值为，在竖直轴上取值为。这就是我画出的训练样本。尽管我没有将其真的看做向量。它事实上就是一个始于原点，终点位置在这个训练样本点的向量。现在，我们有一个参数向量我会将它也画成向量。我将画在横轴这里，将 画在纵轴这里，那么内积 将会是什么呢？
使用我们之前的方法，我们计算的方式就是我将训练样本投影到参数向量，然后我来看一看这个线段的长度，我将它画成红色。我将它称为用来表示这是第 个训练样本在参数向量上的投影。根据我们之前幻灯片的内容，我们知道的是将会等于 乘以向量 的长度或范数。这就等于。这两种方式是等价的，都可以用来计算和之间的内积。
这告诉了我们什么呢？这里表达的意思是：这个 或者的,约束是可以被这个约束所代替的。因为 ，将其写入我们的优化目标。我们将会得到没有了约束，而变成了。
需要提醒一点，我们之前曾讲过这个优化目标函数可以被写成等于。
现在让我们考虑下面这里的训练样本。现在，继续使用之前的简化，即，我们来看一下支持向量机会选择什么样的决策界。这是一种选择，我们假设支持向量机会选择这个决策边界。这不是一个非常好的选择，因为它的间距很小。这个决策界离训练样本的距离很近。我们来看一下为什么支持向量机不会选择它。
对于这样选择的参数，可以看到参数向量事实上是和决策界是 90 度正交的，因此这个绿色的决策界对应着一个参数向量这个方向,顺便提一句的简化仅仅意味着决策界必须通过原点。现在让我们看一下这对于优化目标函数意味着什么。
比如这个样本，我们假设它是我的第一个样本，如果我考察这个样本到参数的投影，投影是这个短的红线段，就等于，它非常短。类似地，这个样本如果它恰好是，我的第二个训练样本，则它到的投影在这里。我将它画成粉色，这个短的粉色线段是，即第二个样本到我的参数向量的投影。因此，这个投影非常短。事实上是一个负值，是在相反的方向，这个向量和参数向量的夹角大于 90 度，的值小于 0。
我们会发现这些将会是非常小的数，因此当我们考察优化目标函数的时候，对于正样本而言，我们需要,但是如果 在这里非常小,那就意味着我们需要的范数非常大.因为如果 很小,而我们希望,令其实现的唯一的办法就是这两个数较大。如果 小，我们就希望的范数大。类似地，对于负样本而言我们需要。我们已经在这个样本中看到会是一个非常小的数，因此唯一的办法就是的范数变大。但是我们的目标函数是希望找到一个参数，它的范数是小的。因此，这看起来不像是一个好的参数向量的选择。
相反的，来看一个不同的决策边界。比如说，支持向量机选择了这个决策界，现在状况会有很大不同。如果这是决策界，这就是相对应的参数的方向，因此，在这个决策界之下，垂直线是决策界。使用线性代数的知识，可以说明，这个绿色的决策界有一个垂直于它的向量。现在如果你考察你的数据在横轴上的投影，比如这个我之前提到的样本，我的样本，当我将它投影到横轴上，或说投影到上，就会得到这样。它的长度是，另一个样本，那个样本是。我做同样的投影，我会发现，的长度是负值。你会注意到现在 和这些投影长度是长多了。如果我们仍然要满足这些约束，>1，则因为变大了，的范数就可以变小了。因此这意味着通过选择右边的决策界，而不是左边的那个，支持向量机可以使参数的范数变小很多。因此，如果我们想令的范数变小，从而令范数的平方变小，就能让支持向量机选择右边的决策界。这就是支持向量机如何能有效地产生大间距分类的原因。
看这条绿线，这个绿色的决策界。我们希望正样本和负样本投影到的值大。要做到这一点的唯一方式就是选择这条绿线做决策界。这是大间距决策界来区分开正样本和负样本这个间距的值。这个间距的值就是等等的值。通过让间距变大，即通过这些等等的值，支持向量机最终可以找到一个较小的范数。这正是支持向量机中最小化目标函数的目的。
以上就是为什么支持向量机最终会找到大间距分类器的原因。因为它试图极大化这些的范数，它们是训练样本到决策边界的距离。最后一点，我们的推导自始至终使用了这个简化假设，就是参数。
就像我之前提到的。这个的作用是：的意思是我们让决策界通过原点。如果你令不是 0 的话，含义就是你希望决策界不通过原点。我将不会做全部的推导。实际上，支持向量机产生大间距分类器的结论，会被证明同样成立，证明方式是非常类似的，是我们刚刚做的证明的推广。
之前视频中说过，即便不等于 0，支持向量机要做的事情都是优化这个目标函数对应着值非常大的情况，但是可以说明的是，即便不等于 0，支持向量机仍然会找到正样本和负样本之间的大间距分隔。
总之，我们解释了为什么支持向量机是一个大间距分类器。在下一节我们，将开始讨论如何利用支持向量机的原理，应用它们建立一个复杂的非线性分类器。
12.4 核函数 1
参考视频: 12 - 4 - Kernels I (16 min).mkv
回顾我们之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题：
为了获得上图所示的判定边界，我们的模型可能是的形式。
我们可以用一系列的新的特征来替换模型中的每一项。例如令：
...得到。然而，除了对原有的特征进行组合以外，有没有更好的方法来构造？我们可以利用核函数来计算出新的特征。
给定一个训练样本，我们利用的各个特征与我们预先选定的地标(landmarks)的近似程度来选取新的特征。
例如：
其中：，为实例中所有特征与地标之间的距离的和。上例中的就是核函数，具体而言，这里是一个高斯核函数(Gaussian Kernel)。注：这个函数与正态分布没什么实际上的关系，只是看上去像而已。
这些地标的作用是什么？如果一个训练样本与地标之间的距离近似于 0，则新特征 近似于，如果训练样本与地标之间距离较远，则近似于一。
假设我们的训练样本含有两个特征[ ]，给定地标与不同的值，见下图：
图中水平面的坐标为 ，而垂直坐标轴代表。可以看出，只有当与重合时才具有最大值。随着的改变值改变的速率受到的控制。
在下图中，当样本处于洋红色的点位置处，因为其离更近，但是离和较远，因此接近 1，而,接近 0。因此，因此预测。同理可以求出，对于离较近的绿色点，也预测，但是对于蓝绿色的点，因为其离三个地标都较远，预测。
这样，图中红色的封闭曲线所表示的范围，便是我们依据一个单一的训练样本和我们选取的地标所得出的判定边界，在预测时，我们采用的特征不是训练样本本身的特征，而是通过核函数计算出的新特征。
12.5 核函数 2
参考视频: 12 - 5 - Kernels II (16 min).mkv
在上一节视频里，我们讨论了核函数这个想法，以及怎样利用它去实现支持向量机的一些新特性。在这一节视频中，我将补充一些缺失的细节，并简单的介绍一下怎么在实际中使用应用这些想法。
如何选择地标？
我们通常是根据训练集的数量选择地标的数量，即如果训练集中有个样本，则我们选取个地标，并且令:。这样做的好处在于：现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即：
下面我们将核函数运用到支持向量机中，修改我们的支持向量机假设为：
• 给定，计算新特征，当 时，预测 ，否则反之。
相应地修改代价函数为：，
在具体实施过程中，我们还需要对最后的正则化项进行些微调整，在计算时，我们用代替，其中是根据我们选择的核函数而不同的一个矩阵。这样做的原因是为了简化计算。
理论上讲，我们也可以在逻辑回归中使用核函数，但是上面使用 来简化计算的方法不适用与逻辑回归，因此计算将非常耗费时间。
在此，我们不介绍最小化支持向量机的代价函数的方法，你可以使用现有的软件包（如liblinear,libsvm等）。在使用这些软件包最小化我们的代价函数之前，我们通常需要编写核函数，并且如果我们使用高斯核函数，那么在使用之前进行特征缩放是非常必要的。
另外，支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而样本非常少的时候，可以采用这种不带核函数的支持向量机。
下面是支持向量机的两个参数和的影响：
较大时，相当于较小，可能会导致过拟合，高方差；
较小时，相当于较大，可能会导致低拟合，高偏差；
较大时，可能会导致低方差，高偏差；
较小时，可能会导致低偏差，高方差。
如果你看了本周的编程作业，你就能亲自实现这些想法，并亲眼看到这些效果。这就是利用核函数的支持向量机算法，希望这些关于偏差和方差的讨论，能给你一些对于算法结果预期的直观印象。
12.6 使用支持向量机
参考视频: 12 - 6 - Using An SVM (21 min).mkv
目前为止，我们已经讨论了SVM比较抽象的层面，在这个视频中我将要讨论到为了运行或者运用SVM。你实际上所需要的一些东西：支持向量机算法，提出了一个特别优化的问题。但是就如在之前的视频中我简单提到的，我真的不建议你自己写软件来求解参数，因此由于今天我们中的很少人，或者其实没有人考虑过自己写代码来转换矩阵，或求一个数的平方根等我们只是知道如何去调用库函数来实现这些功能。同样的，用以解决SVM最优化问题的软件很复杂，且已经有研究者做了很多年数值优化了。因此你提出好的软件库和好的软件包来做这样一些事儿。然后强烈建议使用高优化软件库中的一个，而不是尝试自己落实一些数据。有许多好的软件库，我正好用得最多的两个是liblinear和libsvm，但是真的有很多软件库可以用来做这件事儿。你可以连接许多你可能会用来编写学习算法的主要编程语言。
在高斯核函数之外我们还有其他一些选择，如：
多项式核函数（Polynomial Kernel）
字符串核函数（String kernel）
卡方核函数（ chi-square kernel）
直方图交集核函数（histogram intersection kernel）
等等...
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足 Mercer's 定理，才能被支持向量机的优化软件正确处理。
多类分类问题
假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有个类，则我们需要个模型，以及个参数向量。我们同样也可以训练个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。
尽管你不去写你自己的SVM的优化软件，但是你也需要做几件事：
1、是提出参数的选择。我们在之前的视频中讨论过误差/方差在这方面的性质。
2、你也需要选择内核参数或你想要使用的相似函数，其中一个选择是：我们选择不需要任何内核参数，没有内核参数的理念，也叫线性核函数。因此，如果有人说他使用了线性核的SVM（支持向量机），这就意味这他使用了不带有核函数的SVM（支持向量机）。
从逻辑回归模型，我们得到了支持向量机模型，在两者之间，我们应该如何选择呢？
下面是一些普遍使用的准则：
为特征数，为训练样本数。
(1)如果相较于而言，要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。
(2)如果较小，而且大小中等，例如在 1-1000 之间，而在 10-10000 之间，使用高斯核函数的支持向量机。
(3)如果较小，而较大，例如在 1-1000 之间，而大于 50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。
值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。
今天的SVM包会工作得很好，但是它们仍然会有一些慢。当你有非常非常大的训练集，且用高斯核函数是在这种情况下，我经常会做的是尝试手动地创建，拥有更多的特征变量，然后用逻辑回归或者不带核函数的支持向量机。如果你看到这个幻灯片，看到了逻辑回归，或者不带核函数的支持向量机。在这个两个地方，我把它们放在一起是有原因的。原因是：逻辑回归和不带核函数的支持向量机它们都是非常相似的算法，不管是逻辑回归还是不带核函数的SVM，通常都会做相似的事情，并给出相似的结果。但是根据你实现的情况，其中一个可能会比另一个更加有效。但是在其中一个算法应用的地方，逻辑回归或不带核函数的SVM另一个也很有可能很有效。但是随着SVM的复杂度增加，当你使用不同的内核函数来学习复杂的非线性函数时，这个体系，你知道的，当你有多达 1 万（10,000）的样本时，也可能是 5 万（50,000），你的特征变量的数量这是相当大的。那是一个非常常见的体系，也许在这个体系里，不带核函数的支持向量机就会表现得相当突出。你可以做比这困难得多需要逻辑回归的事情。
最后，神经网络使用于什么时候呢？对于所有的这些问题，对于所有的这些不同体系一个设计得很好的神经网络也很有可能会非常有效。有一个缺点是，或者说是有时可能不会使用神经网络的原因是：对于许多这样的问题，神经网络训练起来可能会特别慢，但是如果你有一个非常好的SVM实现包，它可能会运行得比较快比神经网络快很多，尽管我们在此之前没有展示，但是事实证明，SVM具有的优化问题，是一种凸优化问题。因此，好的SVM优化软件包总是会找到全局最小值，或者接近它的值。对于SVM你不需要担心局部最优。在实际应用中，局部最优不是神经网络所需要解决的一个重大问题，所以这是你在使用SVM的时候不需要太去担心的一个问题。根据你的问题，神经网络可能会比SVM慢，尤其是在这样一个体系中，至于这里给出的参考，看上去有些模糊，如果你在考虑一些问题，这些参考会有一些模糊，但是我仍然不能完全确定，我是该用这个算法还是改用那个算法，这个没有太大关系，当我遇到机器学习问题的时候，有时它确实不清楚这是否是最好的算法，但是就如在之前的视频中看到的算法确实很重要。但是通常更加重要的是：你有多少数据，你有多熟练是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能决定你学习算法的变量等方面，通常这些方面会比你使用逻辑回归还是SVM这方面更加重要。但是，已经说过了，SVM仍然被广泛认为是一种最强大的学习算法，这是一个体系，包含了什么时候一个有效的方法去学习复杂的非线性函数。因此，实际上与逻辑回归、神经网络、SVM一起使用这些方法来提高学习算法，我认为你会很好地建立很有技术的状态。（编者注：当时GPU计算比较慢，神经网络还不流行。）
机器学习系统对于一个宽泛的应用领域来说，这是另一个在你军械库里非常强大的工具，你可以把它应用到很多地方，如硅谷、在工业、学术等领域建立许多高性能的机器学习系统。
代码部分
机器学习练习 3 - 支持向量机
代码修改并注释：黄海广，haiguang2000@qq.com
在本练习中，我们将使用支持向量机（SVM）来构建垃圾邮件分类器。我们将从一些简单的 2D 数据集开始使用 SVM 来查看它们的工作原理。然后，我们将对一组原始电子邮件进行一些预处理工作，并使用 SVM 在处理的电子邮件上构建分类器，以确定它们是否为垃圾邮件。
我们要做的第一件事是看一个简单的二维数据集，看看线性 SVM 如何对数据集进行不同的 C 值（类似于线性/逻辑回归中的正则化项）。
import numpy as npimport pandas as pdimport matplotlib.pyplot as pltimport seaborn as sbfrom scipy.io import loadmat
raw_data = loadmat('data/ex6data1.mat')我们将其用散点图表示，其中类标签由符号表示（+表示正类，o 表示负类）。
data = pd.DataFrame(raw_data['X'], columns=['X1', 'X2'])data['y'] = raw_data['y']
positive = data[data['y'].isin([1])]negative = data[data['y'].isin([0])]
fig, ax = plt.subplots(figsize=(12, 8))ax.scatter(positive['X1'], positive['X2'], s=50, marker='x', label='Positive')ax.scatter(negative['X1'], negative['X2'], s=50, marker='o', label='Negative')ax.legend()plt.show()请注意，还有一个异常的正例在其他样本之外。这些类仍然是线性分离的，但它非常紧凑。我们要训练线性支持向量机来学习类边界。在这个练习中，我们没有从头开始执行 SVM 的任务，所以我要用 scikit-learn。
from sklearn import svmsvc = svm.LinearSVC(C=1, loss='hinge', max_iter=1000)svcLinearSVC(C=1, class_weight=None, dual=True, fit_intercept=True,
intercept_scaling=1, loss='hinge', max_iter=1000, multi_class='ovr',
penalty='l2', random_state=None, tol=0.0001, verbose=0)
首先，我们使用 C=1 看下结果如何。
svc.fit(data[['X1', 'X2']], data['y'])svc.score(data[['X1', 'X2']], data['y'])0.9803921568627451
其次，让我们看看如果 C 的值越大，会发生什么
svc2 = svm.LinearSVC(C=100, loss='hinge', max_iter=1000)svc2.fit(data[['X1', 'X2']], data['y'])svc2.score(data[['X1', 'X2']], data['y'])1.0
这次我们得到了训练数据的完美分类，但是通过增加 C 的值，我们创建了一个不再适合数据的决策边界。我们可以通过查看每个类别预测的置信水平来看出这一点，这是该点与超平面距离的函数。
data['SVM 1 Confidence'] = svc.decision_function(data[['X1', 'X2']])
fig, ax = plt.subplots(figsize=(12,8))ax.scatter(data['X1'], data['X2'], s=50, c=data['SVM 1 Confidence'], cmap='seismic')ax.set_title('SVM (C=1) Decision Confidence')plt.show()data['SVM 2 Confidence'] = svc2.decision_function(data[['X1', 'X2']])
fig, ax = plt.subplots(figsize=(12,8))ax.scatter(data['X1'], data['X2'], s=50, c=data['SVM 2 Confidence'], cmap='seismic')ax.set_title('SVM (C=100) Decision Confidence')plt.show()可以看看靠近边界的点的颜色，区别是有点微妙。如果您在练习文本中，则会出现绘图，其中决策边界在图上显示为一条线，有助于使差异更清晰。
现在我们将从线性 SVM 转移到能够使用内核进行非线性分类的 SVM。我们首先负责实现一个高斯核函数。虽然 scikit-learn 具有内置的高斯内核，但为了实现更清楚，我们将从头开始实现。
def gaussian_kernel(x1, x2, sigma): return np.exp(-(np.sum((x1 - x2)**2) / (2 * (sigma**2))))x1 = np.array([1.0, 2.0, 1.0])x2 = np.array([0.0, 4.0, -1.0])sigma = 2gaussian_kernel(x1, x2, sigma)0.32465246735834974
该结果与练习中的预期值相符。接下来，我们将检查另一个数据集，这次用非线性决策边界。
raw_data = loadmat('data/ex6data2.mat')
data = pd.DataFrame(raw_data['X'], columns=['X1', 'X2'])data['y'] = raw_data['y']
positive = data[data['y'].isin([1])]negative = data[data['y'].isin([0])]
fig, ax = plt.subplots(figsize=(12, 8))ax.scatter(positive['X1'], positive['X2'], s=30, marker='x', label='Positive')ax.scatter(negative['X1'], negative['X2'], s=30, marker='o', label='Negative')ax.legend()plt.show()对于该数据集，我们将使用内置的 RBF 内核构建支持向量机分类器，并检查其对训练数据的准确性。为了可视化决策边界，这一次我们将根据实例具有负类标签的预测概率来对点做阴影。从结果可以看出，它们大部分是正确的。
svc = svm.SVC(C=100, gamma=10, probability=True)svcSVC(C=100, cache_size=200, class_weight=None, coef0=0.0,
decision_function_shape='ovr', degree=3, gamma=10, kernel='rbf',
max_iter=-1, probability=True, random_state=None, shrinking=True,
tol=0.001, verbose=False)
svc.fit(data[['X1', 'X2']], data['y'])svc.score(data[['X1', 'X2']], data['y'])0.9698725376593279
data['Probability'] = svc.predict_proba(data[['X1', 'X2']])[:,0]fig, ax = plt.subplots(figsize=(12,8))ax.scatter(data['X1'], data['X2'], s=30, c=data['Probability'], cmap='Reds')plt.show()对于第三个数据集，我们给出了训练和验证集，并且基于验证集性能为 SVM 模型找到最优超参数。虽然我们可以使用 scikit-learn 的内置网格搜索来做到这一点，但是本着遵循练习的目的，我们将从头开始实现一个简单的网格搜索。
raw_data = loadmat('data/ex6data3.mat')X = raw_data['X']Xval = raw_data['Xval']y = raw_data['y'].ravel()yval = raw_data['yval'].ravel()
C_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]gamma_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]
best_score = 0best_params = {'C': None, 'gamma': None}
for C in C_values: for gamma in gamma_values: svc = svm.SVC(C=C, gamma=gamma) svc.fit(X, y) score = svc.score(Xval, yval)
if score > best_score: best_score = score best_params['C'] = C best_params['gamma'] = gamma
best_score, best_params(0.965, {'C': 0.3, 'gamma': 100})
大间隔分类器
from sklearn.svm import SVCfrom sklearn import datasetsimport matplotlib as mplimport matplotlib.pyplot as pltmpl.rc('axes', labelsize=14)mpl.rc('xtick', labelsize=12)mpl.rc('ytick', labelsize=12)iris = datasets.load_iris()X = iris["data"][:, (2, 3)] # petal length, petal widthy = iris["target"]
setosa_or_versicolor = (y == 0) | (y == 1)X = X[setosa_or_versicolor]y = y[setosa_or_versicolor]
# SVM Classifier modelsvm_clf = SVC(kernel="linear", C=float("inf"))svm_clf.fit(X, y)SVC(C=inf, cache_size=200, class_weight=None, coef0=0.0,
decision_function_shape='ovr', degree=3, gamma='auto_deprecated',
kernel='linear', max_iter=-1, probability=False, random_state=None,
shrinking=True, tol=0.001, verbose=False)
# Bad modelsx0 = np.linspace(0, 5.5, 200)pred_1 = 5*x0 - 20pred_2 = x0 - 1.8pred_3 = 0.1 * x0 + 0.5def plot_svc_decision_boundary(svm_clf, xmin, xmax): w = svm_clf.coef_[0] b = svm_clf.intercept_[0]
# At the decision boundary, w0*x0 + w1*x1 + b = 0 # => x1 = -w0/w1 * x0 - b/w1 x0 = np.linspace(xmin, xmax, 200) decision_boundary = -w[0]/w[1] * x0 - b/w[1]
margin = 1/w[1] gutter_up = decision_boundary + margin gutter_down = decision_boundary - margin
svs = svm_clf.support_vectors_ plt.scatter(svs[:, 0], svs[:, 1], s=180, facecolors='#FFAAAA') plt.plot(x0, decision_boundary, "k-", linewidth=2) plt.plot(x0, gutter_up, "k--", linewidth=2) plt.plot(x0, gutter_down, "k--", linewidth=2)
plt.figure(figsize=(12,2.7))
plt.subplot(121)plt.plot(x0, pred_1, "g--", linewidth=2)plt.plot(x0, pred_2, "m-", linewidth=2)plt.plot(x0, pred_3, "r-", linewidth=2)plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", label="Iris-Versicolor")plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", label="Iris-Setosa")plt.xlabel("Petal length", fontsize=14)plt.ylabel("Petal width", fontsize=14)plt.legend(loc="upper left", fontsize=14)plt.axis([0, 5.5, 0, 2])
plt.subplot(122)plot_svc_decision_boundary(svm_clf, 0, 5.5)plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs")plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo")plt.xlabel("Petal length", fontsize=14)plt.axis([0, 5.5, 0, 2])
plt.show()特征缩放的敏感性
Xs = np.array([[1, 50], [5, 20], [3, 80], [5, 60]]).astype(np.float64)ys = np.array([0, 0, 1, 1])svm_clf = SVC(kernel="linear", C=100)svm_clf.fit(Xs, ys)
plt.figure(figsize=(12,3.2))plt.subplot(121)plt.plot(Xs[:, 0][ys==1], Xs[:, 1][ys==1], "bo")plt.plot(Xs[:, 0][ys==0], Xs[:, 1][ys==0], "ms")plot_svc_decision_boundary(svm_clf, 0, 6)plt.xlabel("$x_0$", fontsize=20)plt.ylabel("$x_1$ ", fontsize=20, rotation=0)plt.title("Unscaled", fontsize=16)plt.axis([0, 6, 0, 90])
from sklearn.preprocessing import StandardScalerscaler = StandardScaler()X_scaled = scaler.fit_transform(Xs)svm_clf.fit(X_scaled, ys)
plt.subplot(122)plt.plot(X_scaled[:, 0][ys==1], X_scaled[:, 1][ys==1], "bo")plt.plot(X_scaled[:, 0][ys==0], X_scaled[:, 1][ys==0], "ms")plot_svc_decision_boundary(svm_clf, -2, 2)plt.xlabel("$x_0$", fontsize=20)plt.title("Scaled", fontsize=16)plt.axis([-2, 2, -2, 2])plt.show()硬间隔和软间隔分类
X_outliers = np.array([[3.4, 1.3], [3.2, 0.8]])y_outliers = np.array([0, 0])Xo1 = np.concatenate([X, X_outliers[:1]], axis=0)yo1 = np.concatenate([y, y_outliers[:1]], axis=0)Xo2 = np.concatenate([X, X_outliers[1:]], axis=0)yo2 = np.concatenate([y, y_outliers[1:]], axis=0)
svm_clf2 = SVC(kernel="linear", C=10**9)svm_clf2.fit(Xo2, yo2)
plt.figure(figsize=(12, 2.7))
plt.subplot(121)plt.plot(Xo1[:, 0][yo1 == 1], Xo1[:, 1][yo1 == 1], "bs")plt.plot(Xo1[:, 0][yo1 == 0], Xo1[:, 1][yo1 == 0], "yo")plt.text(0.3, 1.0, "Impossible!", fontsize=24, color="red")plt.xlabel("Petal length", fontsize=14)plt.ylabel("Petal width", fontsize=14)plt.annotate( "Outlier", xy=(X_outliers[0][0], X_outliers[0][1]), xytext=(2.5, 1.7), ha="center", arrowprops=dict(facecolor='black', shrink=0.1), fontsize=16,)plt.axis([0, 5.5, 0, 2])
plt.subplot(122)plt.plot(Xo2[:, 0][yo2 == 1], Xo2[:, 1][yo2 == 1], "bs")plt.plot(Xo2[:, 0][yo2 == 0], Xo2[:, 1][yo2 == 0], "yo")plot_svc_decision_boundary(svm_clf2, 0, 5.5)plt.xlabel("Petal length", fontsize=14)plt.annotate( "Outlier", xy=(X_outliers[1][0], X_outliers[1][1]), xytext=(3.2, 0.08), ha="center", arrowprops=dict(facecolor='black', shrink=0.1), fontsize=16,)plt.axis([0, 5.5, 0, 2])
plt.show()from sklearn.pipeline import Pipelinefrom sklearn.datasets import make_moonsX, y = make_moons(n_samples=100, noise=0.15, random_state=42)def plot_predictions(clf, axes): x0s = np.linspace(axes[0], axes[1], 100) x1s = np.linspace(axes[2], axes[3], 100) x0, x1 = np.meshgrid(x0s, x1s) X = np.c_[x0.ravel(), x1.ravel()] y_pred = clf.predict(X).reshape(x0.shape) y_decision = clf.decision_function(X).reshape(x0.shape) plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2) plt.contourf(x0, x1, y_decision, cmap=plt.cm.brg, alpha=0.1)def plot_dataset(X, y, axes): plt.plot(X[:, 0][y == 0], X[:, 1][y == 0], "bs") plt.plot(X[:, 0][y == 1], X[:, 1][y == 1], "g^") plt.axis(axes) plt.grid(True, which='both') plt.xlabel(r"$x_1$", fontsize=20) plt.ylabel(r"$x_2$", fontsize=20, rotation=0)from sklearn.svm import SVCgamma1, gamma2 = 0.1, 5C1, C2 = 0.001, 1000hyperparams = (gamma1, C1), (gamma1, C2), (gamma2, C1), (gamma2, C2)
svm_clfs = []for gamma, C in hyperparams: rbf_kernel_svm_clf = Pipeline([("scaler", StandardScaler()), ("svm_clf", SVC(kernel="rbf", gamma=gamma, C=C))]) rbf_kernel_svm_clf.fit(X, y) svm_clfs.append(rbf_kernel_svm_clf)
plt.figure(figsize=(12, 7))
for i, svm_clf in enumerate(svm_clfs): plt.subplot(221 + i) plot_predictions(svm_clf, [-1.5, 2.5, -1, 1.5]) plot_dataset(X, y, [-1.5, 2.5, -1, 1.5]) gamma, C = hyperparams[i] plt.title(r"$\gamma = {}, C = {}$".format(gamma, C), fontsize=12)
plt.show()svm 推导（统计学习方法）
1．支持向量机最简单的情况是线性可分支持向量机，或硬间隔支持向量机。构建它的条件是训练数据线性可分。其学习策略是最大间隔法。可以表示为凸二次规划问题，其原始最优化问题为
求得最优化问题的解为，，得到线性可分支持向量机，分离超平面是
分类决策函数是
最大间隔法中，函数间隔与几何间隔是重要的概念。
线性可分支持向量机的最优解存在且唯一。位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。 二次规划问题的对偶问题是
通常，通过求解对偶问题学习线性可分支持向量机，即首先求解对偶问题的最优值
，然后求最优值和，得出分离超平面和分类决策函数。
2．现实中训练数据是线性可分的情形较少，训练数据往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。线性支持向量机是最基本的支持向量机。
对于噪声或例外，通过引入松弛变量，使其“可分”，得到线性支持向量机学习的凸二次规划问题，其原始最优化问题是
求解原始最优化问题的解和，得到线性支持向量机，其分离超平面为
分类决策函数为
线性可分支持向量机的解唯一但不唯一。对偶问题是
线性支持向量机的对偶学习算法，首先求解对偶问题得到最优解，然后求原始问题最优解和，得出分离超平面和分类决策函数。
对偶问题的解中满的实例点称为支持向量。支持向量可在间隔边界上，也可在间隔边界与分离超平面之间，或者在分离超平面误分一侧。最优分离超平面由支持向量完全决定。
线性支持向量机学习等价于最小化二阶范数正则化的合页函数
3．非线性支持向量机
对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例与实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数来替换当中的内积。核函数表示，通过一个非线性转换后的两个实例间的内积。具体地，是一个核函数，或正定核，意味着存在一个从输入空间 x 到特征空间的映射，对任意，有
对称函数
，任意正整数，对称函数对应的 Gram 矩阵是半正定的。所以，在线性支持向量机学习的对偶问题中，用核函数替代内积，求解得到的就是非线性支持向量机
4．SMO 算法
SMO 算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足 KKT 条件为止。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。
分离超平面：
点到直线距离：
为 2-范数：
直线为超平面，样本可表示为：
margin：
函数间隔：
几何间隔：，当数据被正确分类时，几何间隔就是点到超平面的距离
为了求几何间隔最大，SVM 基本问题可以转化为求解:(为几何间隔，(为函数间隔)
分类点几何间隔最大，同时被正确分类。但这个方程并非凸函数求解，所以要先 ① 将方程转化为凸函数，② 用拉格朗日乘子法和 KKT 条件求解对偶问题。
① 转化为凸函数：
先令，方便计算（参照衡量，不影响评价结果）
再将转化成求解凸函数，1/2 是为了求导之后方便计算。
② 用拉格朗日乘子法和 KKT 条件求解最优值：
整合成：
推导：
根据 KKT 条件：
代入
再把 max 问题转成 min 问题：
以上为 SVM 对偶问题的对偶形式
kernel
在低维空间计算获得高维空间的计算结果，也就是说计算结果满足高维（满足高维，才能说明高维下线性可分）。
soft margin & slack variable
引入松弛变量，对应数据点允许偏离的 functional margin 的量。
目标函数：
对偶问题：
Sequential Minimal Optimization
首先定义特征到结果的输出函数：.
因为
有
import numpy as npimport pandas as pdfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitimport matplotlib.pyplot as plt%matplotlib inline# datadef create_data(): iris = load_iris() df = pd.DataFrame(iris.data, columns=iris.feature_names) df['label'] = iris.target df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label'] data = np.array(df.iloc[:100, [0, 1, -1]]) for i in range(len(data)): if data[i,-1] == 0: data[i,-1] = -1 # print(data) return data[:,:2], data[:,-1]X, y = create_data()X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)plt.scatter(X[:50,0],X[:50,1], label='0')plt.scatter(X[50:,0],X[50:,1], label='1')plt.legend()class SVM: def __init__(self, max_iter=100, kernel='linear'): self.max_iter = max_iter self._kernel = kernel
def init_args(self, features, labels): self.m, self.n = features.shape self.X = features self.Y = labels self.b = 0.0
# 将Ei保存在一个列表里 self.alpha = np.ones(self.m) self.E = [self._E(i) for i in range(self.m)] # 松弛变量 self.C = 1.0
def _KKT(self, i): y_g = self._g(i) * self.Y[i] if self.alpha[i] == 0: return y_g >= 1 elif 0 < self.alpha[i] < self.C: return y_g == 1 else: return y_g <= 1
# g(x)预测值，输入xi（X[i]） def _g(self, i): r = self.b for j in range(self.m): r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j]) return r
# 核函数 def kernel(self, x1, x2): if self._kernel == 'linear': return sum([x1[k] * x2[k] for k in range(self.n)]) elif self._kernel == 'poly': return (sum([x1[k] * x2[k] for k in range(self.n)]) + 1)**2
return 0
# E（x）为g(x)对输入x的预测值和y的差 def _E(self, i): return self._g(i) - self.Y[i]
def _init_alpha(self): # 外层循环首先遍历所有满足0<a<C的样本点，检验是否满足KKT index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C] # 否则遍历整个训练集 non_satisfy_list = [i for i in range(self.m) if i not in index_list] index_list.extend(non_satisfy_list)
for i in index_list: if self._KKT(i): continue
E1 = self.E[i] # 如果E2是+，选择最小的；如果E2是负的，选择最大的 if E1 >= 0: j = min(range(self.m), key=lambda x: self.E[x]) else: j = max(range(self.m), key=lambda x: self.E[x]) return i, j
def _compare(self, _alpha, L, H): if _alpha > H: return H elif _alpha < L: return L else: return _alpha
def fit(self, features, labels): self.init_args(features, labels)
for t in range(self.max_iter): # train i1, i2 = self._init_alpha()
# 边界 if self.Y[i1] == self.Y[i2]: L = max(0, self.alpha[i1] + self.alpha[i2] - self.C) H = min(self.C, self.alpha[i1] + self.alpha[i2]) else: L = max(0, self.alpha[i2] - self.alpha[i1]) H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])
E1 = self.E[i1] E2 = self.E[i2] # eta=K11+K22-2K12 eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel( self.X[i2], self.X[i2]) - 2 * self.kernel(self.X[i1], self.X[i2]) if eta <= 0: # print('eta <= 0') continue
alpha2_new_unc = self.alpha[i2] + self.Y[i2] * ( E1 - E2) / eta #此处有修改，根据书上应该是E1 - E2，书上130-131页 alpha2_new = self._compare(alpha2_new_unc, L, H)
alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * ( self.alpha[i2] - alpha2_new)
b1_new = -E1 - self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) * ( alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel( self.X[i2], self.X[i1]) * (alpha2_new - self.alpha[i2]) + self.b b2_new = -E2 - self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) * ( alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel( self.X[i2], self.X[i2]) * (alpha2_new - self.alpha[i2]) + self.b
if 0 < alpha1_new < self.C: b_new = b1_new elif 0 < alpha2_new < self.C: b_new = b2_new else: # 选择中点 b_new = (b1_new + b2_new) / 2
# 更新参数 self.alpha[i1] = alpha1_new self.alpha[i2] = alpha2_new self.b = b_new
self.E[i1] = self._E(i1) self.E[i2] = self._E(i2) return 'train done!'
def predict(self, data): r = self.b for i in range(self.m): r += self.alpha[i] * self.Y[i] * self.kernel(data, self.X[i])
return 1 if r > 0 else -1
def score(self, X_test, y_test): right_count = 0 for i in range(len(X_test)): result = self.predict(X_test[i]) if result == y_test[i]: right_count += 1 return right_count / len(X_test)
def _weight(self): # linear model yx = self.Y.reshape(-1, 1) * self.X self.w = np.dot(yx.T, self.alpha) return self.wsvm = SVM(max_iter=100)svm.fit(X_train, y_train)'train done!'
svm.score(X_test, y_test)0.48
参考资料
[1]机器学习课程: https://www.coursera.org/course/ml
[3]黄海广: https://github.com/fengdu78
[5]:[推导SVM: https://my.oschina.net/dfsj66011/blog/517766
[6]:[机器学习算法实践-支持向量机(SVM)算法原理: http://pytlab.org/2017/08/15/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E5%AE%9E%E8%B7%B5-%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA-SVM-%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86/
[7] :[Python实现SVM: http://blog.csdn.net/wds2006sdo/article/details/53156589
关于本站
往期精彩回顾