吴恩达机器学习——支持向量机
本章内容简介：
· 12.1优化目标
· 12.2大边界的直观理解
· 12.3大边界分类背后的数学
· 12.4核函数 1
· 12.5核函数 2
· 12.6使用支持向量机
对支持向量机的一些理解：
支持向量机解决的是多维的分类问题。当给出一定的数据集时，分类学习的最基本想法就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本划分，又因为在训练学习中，数据大多是高维度的，并且数据不一定都是线性可分的，那么线性不可分的数据，和非线性函数怎么划分呢？这时候就需要使用到一种新的分类器，支持向量机，支持向量机是基于线性分类器提出的另一种设计最佳准则。
12.1优化目标
本节重点讲述了支持向量机的优化函数如何从逻辑回归函数演化而来。
1）逻辑回归代价函数：
1
2）SVM假设函数：
2
3）
对比上面两张图片，我们不难发现它们的形式大体相同。接下来我们就来讲讲SVM假设函数是如何转变而来的：
逻辑回归中的假设函数形式和右边的S型激励函数如上图，这里z =θ^T ·x。
如果有一个 y=1的样本，那么我们会希望h_θ (x) 趋近1。因为我们想要正确地将此样本分类，这就意味着当 h_θ (x)趋近于1时，θ^T ·x 应当远大于0，（这里的>>意思是远远大于0）又因为z=θ^T ·x，到了该图的右边，我们不难发现此时逻辑回归的输出将趋近于1。反之亦可推导。
而我们如果继续观察逻辑回归的代价函数的话（这里先不考虑正则化部分）会发现y=1或y=0时会发生两种情况，导致逻辑函数的代价函数在分别取得这两种情况时有两种表达的可能 。【如y=1时，(1-y)=0】
在第一种情况中，假设 y=1 ，此时在目标函数中只需有第一项起作用，因为y=1时，(1-y)项将等于0。因此，当在 y=1 的样本中时，即在 (x,y)中 ，我们得到 y=1 -log(1-1/(1+e^(-z) ))这样一项， z=θ^T x。当然，在代价函数中，y 前面有负号。我们只是这样表示，如果 y=1 代价函数中，这一项也等于1。如果画出关于z 的函数，你会看到左下角的这条曲线，我们同样可以看到，当z 增大时，也就是相当于θ^T· x增大时，z 对应的值会变的非常小。对整个代价函数而言，影响也非常小。这也就解释了，为什么逻辑回归在观察到正样本y=1时，试图将θ^T x设置得非常大。因为，在代价函数中的这一项会变的非常小。
现在我们从这个代价函数开始，也就是-log(1-1/(1+e^(-z) ))一点一点修改，取这里的z=1 点，先画出将要用的代价函数：
新的代价函数由途中的两条线段组成，即位于右边的水平部分和位于左边的直线部分，先别过多的考虑左边直线部分的斜率，这并不是很重要。但是，这里我们将使用的新的代价函数，是在y=1的前提下的。你也许能想到，这应该能做同逻辑回归中类似的事情，但事实上，在之后的优化问题中，这会变得更坚定，并且为支持向量机，带来计算上的优势。例如，更容易计算股票交易的问题等等。
而y=0的情况在这里不再赘述，只给出如下的图片：
现在让我们给上面提到的两个方程命名，左边的函数，我们称之为cost_1 (z)，同时，右边函数我称它为cost_0 (z)。（z=θ^T· x），如下图所示：
这里的下标是指在代价函数中，对应的 y=1 和 y=0 的情况，拥有了这些定义后，现在，我们就抗议开始构建支持向量机。
首先，我们要除去1/m这一项，（注：除去1/m这一项，也会得出同样的 θ 最优值——因为1/m 仅是个常量）打个比方：要求当(u-5)2+1取得最小值时的u值，这时最小值为：当u=5时取得最小值。而10(u-5)2+1取得最小值时的u值也是u=5时。
然后第二点概念上的变化便是——对于目标函数而言，我们有两项：第一个项是训练样本的代价，第二项是我们的正则化项。对于逻辑回归而言，优化目标是A+λ×B（通过设置不同正则化参数λ来调节A，B的权重：即使训练样本拟合的更好——即最小化A；保证正则参数足够小，更注重项目B。）
而对于支持向量机，按照惯例，我们将使用一个不同的参数替换逻辑回归中使用的λ来权衡这两项——就是第一项和第二项我们依照惯例使用一个不同的参数称为C，同时改优化目标为C×A+B。
在逻辑回归中，如果给定λ，一个非常大的值，意味着给予B更大的权重。而这里，就对应于将C 设定为非常小的值，那么，相应的将会给B比给A更大的权重。因此，这只是一种不同的方式来控制这种权衡或者一种不同的方法，即用参数来决定是更关心第一项的优化，还是更关心第二项的优化。当然你也可以把这里的参数C 考虑成1/λ，同 1/λ所扮演的角色相同，并且这两个方程或这两个表达式并不相同，因为C=1/λ，但是也并不全是这样，如果当C=1/λ时，这两个优化目标应当得到相同的值，相同的最优值 θ。**
这样一来，我们就能大体上知道逻辑回归代价函数是如何转化到SVM假设函数的。
12.2大边界的直观理解
这一节的重点在于解释为什么SVM(支持向量机)又被称为大间距分类器的原因。（在C很大的情况下讨论）
这是我们的支持向量机模型的代价函数，在左边画出了关于z的代价函数cost_1 (z)，此函数用于正样本，而在右边画出了关于z的代价函数cost_0 (z)，横轴表示z，现在让我们考虑一下，最小化这些代价函数的必要条件是什么。如果你有一个正样本，y=1，则只有在z>=1时，代价函数cost_1 (z)才等于0。
这是因为支持向量机的要求比逻辑回归更高，不仅仅要能正确分开输入的样本，即不仅仅要求θ^T· x>0，我们需要的是比0值大很多，比如大于等于1，这就相当于在支持向量机中嵌入了一个额外的安全因子，或者说安全的间距因子。
输入一个训练样本标签为y=1，你想令第一项为0，要使得第一项等于0，就会导致下面的优化问题，因为我们将选择参数使第一项为0，因此这个函数的第一项为0，因此是C乘以0加上二分之一乘以第二项。那么重点就到第二项（即正则化部分），那么在我们求解这个优化问题时，就会变成最小化这个关于变量θ的函数来得到我们的决策边界。
那么在让代价函数最小化的过程中，我们希望找出在y=1和y=0两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数，则我们的最小化问题便转变成：
在C很大的情况下，那么在我们区分一个线性可分的数据集时，支持向量机会确定一条决策界，使得正样本和负样本用最大的间距分开。（如下图中间的SVM给出的黑色决策边界）
因此支持向量机有时被称为大间距分类器
注意：
1）在数据线性可分的情况下:
①c很大时，对异常点很敏感 比如决策边界由一个异常点而将最优边界决策改变 ；
②c很小时,在没有异常点的情况下，最后也能得到c很大时得到的最优决策边界【类似于c过大会造成过拟合，c过小会造成欠拟合】
2）在数据不是线性可分时，SVM仍能完成分类任务，所以大间距分类器的描述，仅仅是从直观上给出了正则化参数𝐶非常大的情形，同时，要提醒我们𝐶的作用类似于1/𝜆，𝜆是我们之前使用过的正则化参数。这只是𝐶常大的情形，或者等价地 𝜆 非常小的情形。我们最终会得到类似粉线这样的决策界，但是实际上应用支持向量机的时候，当𝐶不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。甚至当你的数据不是线性可分的时候，支持向量机也可以给出好的结果。（比方之前你只能画一条曲线来区分数据，但是现在你可以画一个圆，来规定圆内的数据属于一类，圆外的数据属于一类）
回顾 𝐶 = 1/𝜆，因此：
𝐶 较大时，相当于 𝜆 较小，可能会导致过拟合，高方差。
𝐶 较小时，相当于 𝜆 较大，可能会导致低拟合，高偏差。
12.3大间隔分类器的数学原理
本节重点讲的是支持向量机的优化问题和大间距分类器之间的联系
1）
向量内积：
假定现在有向量u=[u_1，u_2]，v=[v_1，v_2]，那么u^T•v叫做向量u与v之间的内积。
||u||指向量u的范数，即欧几里得长度，根据毕达哥拉斯定理可知：||u||== √（𝑢_1^2 + 𝑢_2^2），此处||u||属于实数。
现在让我们回头来看向量𝑣 ，因为我们想计算内积。𝑣是另一个向量，它的两个分量𝑣1和𝑣2是已知的。我们将向量𝑣以90 度投影到向量𝑢上，接下来度量这条红线的长度p（或者说是向量𝑣投影到向量𝑢上的量）
此时可知：𝑢𝑇·𝑣 = 𝑝⬝||u||，这是从图形的几何意义上得知的。另外我们不难得知𝑢𝑇·𝑣 = 𝑝⬝||u||=u_1×v_1+u_2×v_2。
注意：p是带符号的，正负号具体取决于和𝑣之间的夹角与90度的关系。
此时p是负数。
2）约束替换
经过12.2最后的推导我们知道，当y=1 or y=0时，支持向量机做的全部事情，就是极小化参数向量𝜃范数的平方，或者说长度的平方：
在这里，让我们忽略截距，即令θ_0=0，同时令特征数n=2，即只有两个特征x_1，x_2，则目标函数最终会变成：
1/2 (θ_12+θ_22 )=1/2 (√(θ_12+θ_22 ))^2=1/2 ∥θ∥^2
现在看θ^T· x项，对于参数向量θ给定一个样本x，联想u^T v的示意图，θ和x^(i)就类似于u和v 。
那我们就会知道：这个θ^T ·x^((i))>=1 这样的约束是可以被p^((i))⋅∥θ∥>=1这个约束所代替的，如下图：
3）决策边界选择
对比左边和右边的绿色那条决策界，我们可以知道：第二条决策界所代表的就时支持向量机所选择的决策界。这是因为支持向量机它试图极大化这些p^((i))的范数，它们是训练样本到决策边界的距离。
注：最后一点，我们的推导自始至终使用了这个简化假设，就是参数θ_0=0。这个的作用是：θ_0=0的意思是我们让决策界通过原点。但实际上，支持向量机产生大间距分类器的结论，在θ_0≠0会被证明同样成立，证明方式是非常类似的，是我们刚刚做的证明的推广。
12.4&12.5 核函数
1）给出新特征
对于非线性分类数据，我们要获得如图所示的判定边界，可以先考虑使用高级数的多项式模型来处理。
为了获得上图所示的判定边界，我们的模型可能是θ_0+θ_1 x_1+θ_2 x_2+θ_3 x_1 x_2+θ_4 x_1^2+θ_5 x_2^2+⋯的形式。
我们可以用一系列的新的特征f来替换模型中的每一项。例如令： f_1=x_1,f_2=x_2,f_3=x_1 x_2,f_4=x_12,f_5=x_22
...得到h_θ (x)=θ_1 f_1+θ_2 f_2+...+θ_n f_n。
然而，除了对原有的特征进行组合以外，我们可以利用核函数来计算出新的特征。给定一个训练实例x，我们利用x的各个特征与我们预先选定的地标(landmarks)l((1)),l((2)),l^((3))的近似程度来选取新的特征f_1,f_2,f_3。
如果一个训练实例x与地标L之间的距离近似于0，则新特征 f
近似于𝑒−0=1，如果训练实例𝑥与地标𝐿之间距离较远，则𝑓近似于𝑒−(一个较大的数)=0。
假设我们的训练实例含有两个特征[x_1 x_2]，给定地标l^((1))与不同的σ值，见下图：
图中水平面的坐标为 x_1，x_2而垂直坐标轴代表f。可以看出，只有当x与l((1))重合时f才具有最大值。随着x的改变f值改变的速率受到σ2的控制。
在下图中，当实例处于洋红色的点位置处，因为其离l((1))更近，但是离l((2))和l^((3))较远，因此f_1接近1，而f_2,f_3接近0。因此h_θ (x)=θ_0+θ_1 f_1+θ_2 f_2+θ_1 f_3>0，因此预测y=1。同理可以求出，对于离l^((2))较近的绿色点，也预测y=1，但是对于蓝绿色的点，因为其离三个地标都较远，预测y=0。
这样，图中红色的封闭曲线所表示的范围，便是我们依据一个单一的训练实例和我们选取的地标所得出的判定边界，在预测时，我们采用的特征不是训练实例本身的特征，而是通过核函数计算出的新特征f_1,f_2,f_3。
2)选择地标
我们通常是根据训练集的数量选择地标的数量，即如果训练集中有m个实例，则我们选取m个地标，并且令:l((1))=x((1)),l((2))=x((2)),.....,l((m))=x((m))。这样做的好处在于：现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即：
下面是支持向量机的两个参数C和σ的影响：
C=1/λ
C 较大时，相当于λ较小，可能会导致过拟合，高方差；
C 较小时，相当于λ较大，可能会导致低拟合，高偏差；
σ较大时，可能会导致低方差，高偏差；
σ较小时，可能会导致低偏差，高方差。
12.6使用支持向量机
1）一些建议：
不建议自己去写软件来求解参数θ，可以去运用现在的软件包
库来实现（如sklearn、liblinear和libsvm）
在高斯核函数之外我们还有其他一些选择，如：
多项式核函数（Polynomial Kernel）
字符串核函数（String kernel）
卡方核函数（ chi-square kernel）
直方图交集核函数（histogram intersection kernel）
等等...
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足Mercer's定理，才能被支持向量机的优化软件正确处理。
2）多类分类问题
假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有k个类，则我们需要k个模型，以及k个参数向量θ。我们同样也可以训练k个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。
尽管你不去写你自己的SVM的优化软件，但是你也需要做几件事：
1、是提出参数C的选择。我们在之前的视频中讨论过误差/方差在这方面的性质。
2、你也需要选择内核参数或你想要使用的相似函数，其中一个选择是：我们选择不需要任何内核参数，没有内核参数的理念，也叫线性核函数。因此，如果有人说他使用了线性核的SVM（支持向量机），这就意味这他使用了不带有核函数的SVM（支持向量机）。
3）支持向量机一些普遍使用的准则：
n为特征数，m为训练样本数。
(1)如果相较于m而言，n要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。
(2)如果n较小，而且m大小中等，例如n在 1-1000 之间，而m在10-10000之间，使用高斯核函数的支持向量机。
(3)如果n较小，而m较大，例如n在1-1000之间，而m大于50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。
值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。
参考网站：
https://github.com/fengdu78/Coursera-ML-AndrewNg-Notes
