🍍 支持向量机(Support Vector Machines)
一、优化目标 Optimization Objective
对于监督学习，还有一个更加强大的算法广泛的应用于工业界和学术界，它被称为支持向量机(Support Vector Machine)。与逻辑回归和神经网络相比，支持向量机，或者简称SVM，在学习复杂的非线性方程时提供了一种更为清晰，更加强大的方式。
正如我们之前开发的学习算法，我们从优化目标开始。
为了描述支持向量机，👍 我将会从逻辑回归开始，展示如何一点一点的修改来得到支持向量机。
那么，在逻辑回归中我们已经熟悉了这里的假设函数形式，和右边的 Sigmod 激活函数。为了解释一些数学知识，我将用 $z$ 表示 $\theta^Tx$。
现在考虑下我们想要逻辑回归做什么：如果有一个 $y=1$的样本，现在我们希望${{h}_{\theta }}\left( x \right)$ 趋近1。因为我们想要正确地将此样本分类，这就意味着当 ${{h}_{\theta }}\left( x \right)$趋近于1时，$\theta^Tx$ 应当远大于0。由于 $z$ 表示 $\theta^Tx$，当 $z$ 远大于0时，即到了该图的右边，此时逻辑回归的输出将趋近于1。相反地，如果我们有另一个样本，即 $y=0$。我们希望假设函数的输出值将趋近于0，这对应于 $\theta^Tx$，或者就是 $z$ 会远小于 0，因为对应的假设函数的输出值趋近0。
进一步观察逻辑回归的代价函数：
考虑两种情况：
y = 1：在目标函数中只需有第一项起作用，因为$y=1$时，$(1-y)$项将等于0。因此，当在 $y=1$ 的样本中时，即在 $(x, y) $中 ，我们得到 $y=1$ $-\log(1-\frac{1}{1+e^{-z}})$这样一项。画出关于 z 的函数：
当$z$ 增大时，也就是相当于$\theta^Tx$增大时，$z$ 对应的值会变的非常小。对整个代价函数而言，影响也非常小。这也就解释了，为什么逻辑回归在观察到正样本$y=1$时，试图将$\theta^Tx$设置得非常大。因为，在代价函数中的这一项会变的非常小。
⚡ 现在开始建立支持向量机，我们从这个代价函数开始：也就是从$-\log(1-\frac{1}{1+e^{-z}})$ 一点一点的修改，取 $z=1$ 点，先画出将要用的代价函数：
新的代价函数是由两条线段组成，即位于右边的水平部分和位于左边的直线部分，先别过多的考虑左边直线部分的斜率，这并不是很重要。注意，这里我们将使用的新的代价函数，是在 $y=1$ 的前提下的。你也许能想到，这应该能做同逻辑回归中类似的事情。
y = 0：代价函数只留下了第二项，因为第一项被消除了。所以上述表达式只留下了第二项。画出关于 z 的函数：
我们用一个新的代价函数来代替：
👇：
那么，现在让我给这两个方程命名，左边的函数，我称之为 ${\cos}t_1{(z)}$，同时，右边函数我称它为 ${\cos}t_0{(z)}$。这里的下标是指在代价函数中，对应的 $y=1$ 和 $y=0$ 的情况，拥有了这些定义后，现在，我们就开始构建支持向量机。
下图是逻辑回归中使用的代价函数：
对于支持向量机而言，我们要将 $-logh_θ(x^{(i)})$ 替换为 ${\cos}t_1{(z)}$，也就是${\cos}t_1{(\theta^Tx)}$，同样地，将 $-log(1-h_θ(x^{(i)}))$ 这一项替换为 ${\cos}t_0{(z)}$，也就是 ${\cos}t_0{(\theta^Tx)}$。因此，对于支持向量机，我们得到了它的最小化问题（加上正则化参数），即：
💡 无论前面是否有$1/m$ 和 后面的 1/2m 这一项，最终所得到的最优值${{\theta }}$都是一样的，因为$1/m$ (1/2m)仅是个常量。
对于逻辑回归，在目标函数中，我们有两项：第一个是训练样本的代价，第二个是我们的正则化项，我们不得不去用正则化项来平衡。这就相当于我们想要最小化$A$加上正则化参数$\lambda$，然后乘以其他项$B$。$A$表示这里的第一项，同时我用B表示第二项（不包括 $\lambda$），则逻辑回归的代价函数可表示为 $A+\lambda\times B$。我们所做的是通过设置不同正则参数 $\lambda$ 达到优化 A 的目的。这样，我们就能够权衡对应的项，是使得训练样本拟合的更好。
🚩 但对于支持向量机，我们将使用一个不同的参数替换这里使用的 $\lambda$ 来权衡这两项：$C×A+B$。 
在逻辑回归中，如果给定$\lambda$，一个非常大的值，意味着给予$B$更大的权重。而在支持向量机中，将$C$ 设定为非常小的值意味着将会给$B$比给$A$更大的权重。因此，这只是一种不同的方式来控制这种权衡的方法，即用参数来决定是更关心第一项的优化，还是更关心第二项的优化。
当然你也可以把这里的参数$C$ 考虑成$1/\lambda$，如果当 $C=1/\lambda$时，这两个优化目标应当得到相同的值，相同的最优值 ${{\theta }}$。那么，我现在删掉上述式子中的 $\lambda$，并且用常数 $C$ 来代替。因此，这就得到了在支持向量机中我们的整个优化目标函数。然后最小化这个目标函数，就得到了 SVM 学习到的参数$C$：
⭐ 
⭐ 有别于逻辑回归输出的概率，支持向量机的代价函数直接预测值等于1，还是等于0。
✅ OK，以上就是支持向量机数学上的定义。在接下来的视频中，我们将从直观的角度看看SVM的优化目标会带来什么，以及SVM的假设函数是什么样的，同时也会谈谈如何做些许修改，学习更加复杂、非线性的函数。
二、大间距的直观理解 Large Margin Intuition
人们有时将支持向量机看作是大间距分类器。在这一部分，我将介绍其中的含义，这有助于我们直观理解 SVM 模型的假设是什么样的。
上图是支持向量机模型的代价函数，在左边这里画出了关于 $z$ 的代价函数${\cos}t_1{(z)}$，此函数用于正样本，而在右边这里画出了关于$z$的代价函数 ${\cos}t_0{(z)}$，横轴表示 $z$ 。
现在让我们考虑一下，最小化这些代价函数的必要条件是什么。如果你有一个正样本，$y=1$，则只有在$z>=1$时，代价函数${\cos}t_1{(z)}$才等于0。
换句话说，如果你有一个正样本，我们会希望$\theta^Tx>=1$，反之，如果$y=0$，函数${\cos}t_0{(z)}$ 只有在$z<=-1$的区间里函数值为0。这是支持向量机的一个有趣性质。
事实上，如果你有一个正样本$y=1$，则其实我们仅仅要求$\theta^Tx$大于等于0，就能将该样本恰当分出，这是因为如果$\theta^Tx$>0的话，我们的模型代价函数值为0，类似地，如果你有一个负样本，则仅需要$\theta^Tx$<=0就会将负例正确分离。
但是，支持向量机的要求更高，不仅仅要能正确分开输入的样本，即不仅仅要求$\theta^Tx$>0，我们需要的是比0值大很多，比如大于等于1，我也想这个比0小很多，比如我希望它小于等于-1，这就相当于在支持向量机中嵌入了一个额外的安全因子，或者说安全的间距因子。
当然，逻辑回归做了类似的事情。但是让我们看一下，在支持向量机中，这个间距因子会带来什么样的好处。
💬 具体而言，如果你考察这样一个数据集，其中有正样本，也有负样本，可以看到这个数据集是线性可分的，即存在一条直线把正负样本分开。当然有多条不同的直线，可以把正样本和负样本完全分开。
支持向量机将会选择这个黑色的决策边界，相较于之前我用粉色或者绿色画的决策界。这条黑色的看起来好得多，黑线看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。数学上来讲，这是什么意思呢？这条黑线有更大的距离，这个距离叫做间距(margin)。
⚪ 当画出这两条额外的蓝线，我们看到黑色的决策界和训练样本之间有更大的最短距离。然而粉线和蓝线离训练样本就非常近，在分离样本的时候就会比黑线表现差。因此，这个距离叫做支持向量机的间距，它努力用一个最大间距来分离样本。因此支持向量机有时被称为大间距分类器。
🚨 最后，需要注意的是：当你使用支持向量机的时候，你的学习算法会受到异常点（outlier）的影响。比如我们加入一个额外的正样本：
为了将样本用最大间距分开，也许我最终会得到一条类似粉色这样的决策界，仅仅基于一个异常值，仅仅基于一个样本，就将我的决策界从这条黑线变到这条粉线，这实在是不明智的。而如果正则化参数$C$，设置的非常大，这事实上正是支持向量机将会做的，它将决策界，从黑线变到了粉线。但是如果$C$ 设置的小一点，则你最终会得到这条黑线，当然数据如果不是线性可分的，如果你在这里有一些正样本或者你在这里有一些负样本，则支持向量机也会将它们恰当分开。
因此，大间距分类器的描述，仅仅是从直观上给出了正则化参数$C$非常大的情形，同时，要提醒你$C$的作用类似于$1/\lambda$，$\lambda$是我们之前使用过的正则化参数。这只是$C$非常大的情形，或者等价的 $\lambda$ 非常小的情形。你最终会得到类似粉线这样的决策界，但是实际上应用支持向量机的时候，⭐ 当$C$不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。甚至当你的数据不是线性可分的时候，支持向量机也可以给出好的结果。
回顾 $C=1/\lambda$：
$C$ 较大时，相当于 $\lambda$ 较小，可能会导致过拟合，高方差。
$C$ 较小时，相当于$\lambda$较大，可能会导致欠拟合，高偏差。
这节课给出了一些关于为什么支持向量机被看做大间距分类器的直观理解。它用最大间距将样本区分开，尽管从技术上讲，这只有当参数$C$是非常大的时候是真的，但是它对于理解支持向量机是有益的。
三、大边界分类背后的数学（选修）
四、核函数 1 Kernels Ⅰ
回顾我们之前讨论过可以使用高阶的多项式模型来解决无法用直线进行分隔的分类问题：
为了获得上图所示的判定边界，我们的模型可能是${{\theta }_{0}}+{{\theta }_{1}}{{x}_{1}}+{{\theta }_{2}}{{x}_{2}}+{{\theta }_{3}}{{x}_{1}}{{x}_{2}}+{{\theta }_{4}}x_{1}^{2}+{{\theta }_{5}}x_{2}^{2}+\cdots $的形式。
我们可以用一系列的新的特征 $f$ 来替换模型中的每一项。例如令： ${{f}_{1}}={{x}_{1}},{{f}_{2}}={{x}_{2}},{{f}_{3}}={{x}_{1}}{{x}_{2}},{{f}_{4}}=x_{1}^{2},{{f}_{5}}=x_{2}^{2}$ ...
得到$h_θ(x)={{\theta }_{1}}f_1+{{\theta }_{2}}f_2+...+{{\theta }_{n}}f_n$。然而，除了对原有的特征进行组合以外，有没有更好的方法来构造$f_1,f_2,f_3$？我们可以利用核函数来计算出新的特征。
给定一个训练样本 $x$，我们利用 $x$ 的各个特征与我们预先选定的地标(landmarks) $l^{(1)},l^{(2)},l^{(3)}$ 的近似程度来选取新的特征 $f_1,f_2,f_3$。
🙂 下一节会讲解如何选取地标
例如：${{f}_{1}}=similarity(x,{{l}^{(1)}})=e(-\frac{{{|| x-{{l}^{(1)}} ||}^{2}}}{2{{\sigma }^{2}}})$
💡 $||w||$ 表示向量 w 的长度
⭐ 其中：${{|| x-{{l}^{(1)}} ||}^{2}}=\sum_{j=1}^{n}{{({{x}_{j}}-l_{j}^{(1)})}^{2}}$，为实例 $x$ 中所有特征与地标 $l^{(1)}$ 之间的距离的和。
这里的 $similarity(x,{{l}^{(1)}})$ 就是核函数，具体而言，这里是一个高斯核函数(Gaussian Kernel)。 注：这个函数与正态分布没什么实际上的关系，只是看上去像而已。
这些地标的作用是什么？🚩 如果一个训练样本 $x$ 与地标 $l$ 之间的距离近似于 0，则新特征 $f$ 近似于 $e^{-0}=1$，如果训练样本 $x$ 与地标 $l$ 之间距离较远，则 $f$ 近似于 $e^{-(一个较大的数)}=0$。
假设我们的训练样本含有两个特征[$x_{1}$ $x{_2}$]，给定地标$l^{(1)}$与不同的 $\sigma$ （高斯核函数的参数值）值，见下图：
图中水平面的坐标为 $x_{1}$，$x_{2}$而垂直坐标轴代表$f$。可以看出，只有当$x$与$l^{(1)}$重合时$f$才具有最大值。随着$x$的改变$f$值改变的速率受到$\sigma^2$的控制。
在下图中，当样本处于洋红色的点位置处，因为其离$l^{(1)}$更近，但是离$l^{(2)}$和$l^{(3)}$较远，因此$f_1$接近1，而$f_2$,$f_3$接近0。因此$h_θ(x)=θ_0+θ_1f_1+θ_2f_2+θ_1f_3>0$，因此预测$y=1$。同理可以求出，对于离$l^{(2)}$较近的绿色点，也预测$y=1$，但是对于蓝绿色的点，因为其离三个地标都较远，预测$y=0$。
这样，图中红色的封闭曲线所表示的范围，便是我们依据一个单一的训练样本和我们选取的地标所得出的判定边界，在预测时，我们采用的特征不是训练样本本身的特征，而是通过核函数计算出的新特征 $f_1,f_2,f_3$。
五、核函数 2 Kernels Ⅱ
❓ 如何选择地标？
我们通常是根据训练集的数量选择地标的数量，即⭐ **如果训练集中有$m$个样本，则我们选取$m$个地标，并且令:$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},.....,l^{(m)}=x^{(m)}$。**这样做的好处在于：现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即：
下面我们将核函数运用到支持向量机中，修改我们的支持向量机假设为：
给定$x$，计算新特征$f$，当$θ^Tf>=0$ 时，预测 $y=1$，否则反之。
相应地修改代价函数为：$\sum{_{j=1}^{n=m}}\theta _{j}^{2}={{\theta}^{T}}\theta $，$min C\sum\limits_{i=1}^{m}{[{{y}^{(i)}}cos {{t}_{1}}}( {{\theta }^{T}}{{f}^{(i)}})+(1-{{y}^{(i)}})cos {{t}_{0}}( {{\theta }^{T}}{{f}^{(i)}})]+\frac{1}{2}\sum\limits_{j=1}^{n=m}{\theta_{j}^{2}}$ 在具体实施过程中，我们还需要对最后的正则化项进行些微调整，在计算$\sum_{j=1}^{n=m}\theta _{j}^{2}={{\theta}^{T}}\theta $时，我们用$θ^TMθ$代替$θ^Tθ$，其中$M$是根据我们选择的核函数而不同的一个矩阵。这样做的原因是为了简化计算。
理论上讲，我们也可以在逻辑回归中使用核函数，但是上面使用 $M$ 来简化计算的方法不适用与逻辑回归，因此计算将非常耗费时间。
在此，我们不介绍最小化支持向量机的代价函数的方法，你可以使用现有的软件包（如liblinear,libsvm等）。在使用这些软件包最小化我们的代价函数之前，我们通常需要编写核函数，并且如果我们使用高斯核函数，那么在使用之前进行特征缩放是非常必要的。
另外，支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而样本非常少的时候，可以采用这种不带核函数的支持向量机。
⭐ 下面是支持向量机的两个参数$C$和$\sigma$的影响：
$C=1/\lambda$
$C$ 较大时，相当于$\lambda$较小，可能会导致过拟合，高方差；
$C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差；
$\sigma$较大时，可能会导致低方差，高偏差；
$\sigma$较小时，可能会导致低偏差，高方差。
六、使用支持向量机
在高斯核函数之外我们还有其他一些选择，如：
多项式核函数（Polynomial Kernel）
字符串核函数（String kernel）
卡方核函数（ chi-square kernel）
直方图交集核函数（histogram intersection kernel）
等等...
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足Mercer's定理，才能被支持向量机的优化软件正确处理。
多类分类问题：
假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有 $k$ 个类，则我们需要 $k$ 个模型，以及$k$个参数向量${{\theta }}$。我们同样也可以训练$k$个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。
尽管你不去写你自己的SVM的优化软件，但是你也需要做几件事：
提出参数$C$的选择。
选择内核参数或你想要使用的相似函数，其中一个选择是：我们选择不需要任何内核参数，没有内核参数的理念，也叫线性核函数。因此，如果有人说他使用了线性核的SVM，这就意味这他使用了不带有核函数的SVM。
❓ 从逻辑回归模型，我们得到了支持向量机模型，在两者之间，我们应该如何选择呢？⭐ 下面是一些普遍使用的准则：
$n$为特征数，$m$为训练样本数。
如果相较于$m$而言，$n$要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。
如果$n$较小，而且$m$大小中等，例如$n$在 1-1000 之间，而$m$在10-10000之间，使用高斯核函数的支持向量机。
如果$n$较小，而$m$较大，例如$n$在1-1000之间，而$m$大于50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。
值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，👍 选择支持向量机 SVM 的原因主要在于它的代价函数是凸函数，不存在局部最小值。
如今的SVM包会工作得很好，但是它们仍然会有一些慢。当你有非常非常大的训练集，且用高斯核函数是在这种情况下，我经常会做的是尝试手动地创建，拥有更多的特征变量，然后用逻辑回归或者不带核函数的支持向量机。把它们放在一起是有原因的：逻辑回归和不带核函数的支持向量机它们都是非常相似的算法，不管是逻辑回归还是不带核函数的SVM，通常都会做相似的事情，并给出相似的结果。但是根据你实现的情况，其中一个可能会比另一个更加有效。
但是随着SVM的复杂度增加，当你使用不同的内核函数来学习复杂的非线性函数时，如果你有多达1万（10,000）的样本时，也可能是5万（50,000），你的特征变量的数量是相当大的，也许在这个体系里，不带核函数的支持向量机就会表现得相当突出。
最后，神经网络使用于什么时候呢？ 对于所有的这些问题，对于所有的这些不同体系一个设计得很好的神经网络也很有可能会非常有效。有一个缺点是，或者说是有时可能不会使用神经网络的原因是：对于许多这样的问题，神经网络训练起来可能会特别慢。
但是我仍然不能完全确定，我是该用这个算法还是改用那个算法，这个没有太大关系，当我遇到机器学习问题的时候，有时它确实不清楚这是否是最好的算法。算法确实很重要，但是通常更加重要的是：你有多少数据，你有多熟练是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能决定你学习算法的变量等方面，通常这些方面会比你使用逻辑回归还是SVM这方面更加重要。
✍ Quiz
① 第 1 题
假设您使用训练了一个高斯内核的支持向量机，它在训练集上学习了以下决策边界：
你觉得支持向量机欠拟合了，应该试着增加或减少 C 吗？或者增加或减少 $σ_2$ ？
降低 C，增加 $σ_2$
降低 C，降低 $σ_2$
增加 C，增加 $σ_2$
✅ 增加 C，降低 $σ_2$
💡
$C$ 较大时，相当于$\lambda$较小，可能会导致过拟合，高方差；
$C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差；
$\sigma$较大时，可能会导致低方差，高偏差；
$\sigma$较小时，可能会导致低偏差，高方差。
② 第 2 题
高斯核的公式是由 $\text{similarity}(x,l^{(1)}) = \exp{(-\frac{||x-l^{(1)}||^2}{2\sigma^2})}$ 给出的。
下图显示了当$σ_2=1$时，$f_1 = \text{similarity}(x,l^{(1)})$ 的曲线图。
当 $σ^2=0.25$ 时，下列哪个是 f1 的曲线图？
A：
B：
C：
✅ D：
③ 第 3 题
支持向量机求解 $\min_\theta \space C \sum_{i=1}^m y^{(i)} \text{cost}_1(\theta^Tx^{(i)}) + (1-y^{(i)}) \text{cost}_0(\theta^Tx^{(i)}) + \sum_{j=1}^n \theta_j^2$，其中函数$cost_0(z)$和$cost_1(z)$图像如下：
目标中的第一项是：$C \sum_{i=1}^m y^{(i)} \text{cost}_1(\theta^Tx^{(i)}) + (1-y^{(i)}) \text{cost}_0(\theta^Tx^{(i)}).$ 如果以下四个条件中有两个为真，则第一项为零。使这个项等于零的两个条件是什么？
✅ 对于$y^{(i)}=1$的每个例子，有$\theta^Tx^{(i)} \geq 1$
✅ 对于$y^{(i)}=0$的每个例子，有$\theta^Tx^{(i)} \leq -1$
对于$y^{(i)}=1$的每个例子，有$\theta^Tx^{(i)} \geq 0$
对于$y^{(i)}=0$的每个例子，有$\theta^Tx^{(i)} \leq 0$
④ 第 4 题
假设您有一个具有 n=10 个特征和 m=5000 个示例的数据集。在用梯度下降训练逻辑回归分类器之后，您发现它与训练集欠拟合，并且在训练集或交叉验证集上没有达到所需的性能。以下哪个步骤有望改善？选出所有正确项
✅ 尝试使用具有大量隐藏单元的神经网络。
减少训练集中的示例数。
使用不同的优化方法，因为使用梯度下降训练逻辑可能会导致局部最小。
✅ 创建/添加新的多项式特征。
⑤ 第 5 题
以下哪项陈述是正确的？选出所有正确项
假设您使用支持向量机进行多类分类，并希望使用“一对所有”方法。如果你有K个不同的类，你将训练K−1个不同的支持向量机。
如果数据是线性可分的，那么不管C值是多少，线性内核的支持向量机都将返回相同的参数θ（即，θ的结果值不依赖于C）。
✅ 高斯核的最大值（即 $sim(x, l^{(1)})$）是1。
✅ 在使用高斯核之前进行特征归一化是很重要的。
