Machine Learning-笔记 -SVM

本文介绍的是SVM算法原理(NG的ML课程笔记)

适应人群：想了解SVM原理的

为了好好理解SVM算法的原理，我们先从逻辑回归开始。

逻辑函数的假设函数(Hypothesis)如下图：

下面将用Z代替等号右边

$$Z=Θ^TX $$

逻辑回归用来做什么

很显然逻辑回归用来分类，如果有一个y=1的样本，我们希望h(x)趋近1，因为我们想正确地将此样本分类，这就意味着当h(x) 趋近于 1 时，Z应当远大于0，用数学符号表示Z>>0,从上图可以看出当Z>>0是对应的函数输出是1；相反，如果我们有另外一个样本，即y=0。我们希望假设函数的输出值将趋近于 0，对应的Z要远远小于0，Z<<0

进一步观察逻辑回归的代价函数,每一个样本都会为代价函数做贡献。现在，考虑两种情况，一种是 y 等于 1 的情况；另一种是 y 等于 0 的情况。

在第一种情况中，假设y=1，此时在目标函数中只需有第一项起作用，因为 y 等于 1 时，(1-y) 项将等于0。画出关于 z 的函数，你会看到左下角的这条曲线，当z增大时，z 对应的值会变的非常小。对整个代价函数而言，影响也非常小。这也就解释了，为什么逻辑回归在观察到正样本 y=1 时，试图将z设置得非常大。因为，在代价函数中的这一项会变的非常小。

建立SVM(支持向量机)

现在开始建立支持SVM(向量机)，首先从这个代价函数开始,一点点修改
$$ \log(1- \frac{1} {1+e^{-Z}})$$
红线画出的函数表示将要用的代价函数

新的代价函数将会水平的从这里到右边 (图外),到了这里已经非常接近逻辑回归中使用的代价函数了。只是这里是由两条线段组成，即位于右边的水平部分和位于左边的直线部分，先别过多的考虑左边直线部分的斜率，这并不是很重要.

我们用一个新的代价函数来代替逻辑函数，即这条从 0 点开始的水平直线，然后是一条斜线。左边的函数，我称之为 Cos t1(z)，同时，右边函数我称它为 Cos t0(z)。这里的下标是指在代价函数中，对应的 y=1 和 y=0 的情况.

开始构建SVM(支持向量机)

上面是逻辑回归当中使用的代价函数J(Θ),SVM在这里稍微做个转变,把括号里的log函数分别用上面提到的 Cos t1(z)和Cos t0(z)替换，然后再加上正则项。

这里我们有两项：第一是训练样本的代价，第二个是我们的正则化项，我们不得不去用这一项来平衡.这就相当于我们想要最小化 A 加上正则化参数λ，然后乘以其他项 B 对吧？这里的 A 表示这里的第一项，同时我用 B 表示第二项，但不包括λ，我们不是优化这里的 A+λ×B.

我们依照惯例使用一个不同的参数称为 C，那么，我现在删掉这里的λ，并且用常数 C 来代替。同时改为优化目标，C×A+B 因此SVM hypothesis可以表示为

现在让我们考虑一下，最小化这些代价函数的必要条件是什么.如果你有一个正样本，y 等于 1.则只有在 z 大于等于 1 时,代价函数 cost 1 (z)才等于 0.换句话说，如果你有一个正样本，我们会希望Θ^TX >=1，反之，如果 y 是等于 0 的，我们观察一下，函数 cost 0 (z)，它只有在 z<=1的区间里函数值为 0，这是支持向量机的一个有趣性质。

我接下来会考虑一个特例，将这个常数 C 设置成一个非常大,比如我们假设 C 的值为 100000 或者其它非常大的数，然后来观察支持向量机会给出什么结果？如果 C 非常大，则最小化代价函数的时候，我们将会很希望找到一个使第一项为 0 的最优解。因此，让我们尝试在代价项的第一项为 0 的情形下理解该优化题。

第一项为0，必须是c乘以0，所以这将遵循以下约束，y (i )是等于 1,Z >=1,如果 y (i )是等于 0的,Z<=-1.当你最小化这个关于变量 θ 的函数的时候，你会得到一个非常有趣的决策边界。那么就只剩下第二项，这个优化目标函数可以被写成等于
$$ \frac{1}{2}||Θ^2||
$$
具体而言，如果你考察这样一个数据集，其中有正样本，也有负样本，可以看到这个数据集是线性可分的。我的意思是，存在一条直线把正负样本分开。当然有多条不同的直线，可以把正样本和负样本完全分开。

比如，这就是一个决策边界可以把正样本和负样本分开。但是多多少少这个看起来并不是非常自然是么?

或者我们可以画一条更差的决策界，这是另一条决策边界，可以将正样本和负样本分开，但仅仅是勉强分开，这些决策边界看起来都不是特别好的选择，支持向量机将会选择这个黑色的决策边界，相较于之前我用粉色或者绿色画的决策界。这条黑色的看起来好得多.在分离正样本和负样本上它显得的更好。数学上来讲，这是什么意思呢？这条黑线有更大的距离，这个距离叫做间距 (margin).因此支持向量机有时被称为 大间距分类器，而这其实是求解上面优化问题的结果。

大间隔分类背后的数学原理

首先复习一下关于向量内积的知识,假设我有两个向量，u 和 v 。uTv 叫做向量 u 和 v 之间的内积。向量的内积在几何上的表示为将 v 投影到 u上，p 是 v 投影到向量 u 上的长度, uTv =p * ||u||。
顺便说一句，uTv=vTu。最后一点，需要注意的就是 p 值，p 事实上是有符号的。如果 u 和 v 之间的夹角小于 90 度，那么那条红线的长度 p 是正值。然而如果这个夹角大于 90 度，则 p 将会是负的。

我们接下来将会使用这些关于向量内积的性质试图来理解支持向量机中的目标函数。

接下来忽略掉截距，令 θ 0 = 0,这样更容易画示意图。我将特征数 n 置为 2，因此我们仅有两个特征 x 1 和 x 2 ，现在 我们来看一下目标函数，支持向量机的优化目标函数。当我们仅有两个特征，即n=2时，这个式子可以写作：
$$ \frac{1}{2}(Θ^2_1+Θ^2_2) = \frac{1}{2}(\sqrt{Θ^2_1+Θ^2_2})^2= \frac{1}{2}||Θ||^2
$$
因此支持向量机做的全部事情，就是 极小化参数向量 θ 范数的平方 ， 或者说长度的平方.

现在我将要看看这些项：
我们考察一个单一的训练样本，我有一个正样本在这里，用一个叉来表示这个样本x(i),意思是在水平轴上取值为x1(i),在竖直轴上取值为x2(i).，我们有一个参数向量我会将它也画成向量。我将 θ 1 画在横轴这里，将 θ 2 画在纵轴这里，那么内积θT*X(i)将会是什么呢？

使用我们之前的方法，我们计算的方式就是我将训练样本投影到参数向量 θ,θT*X(i)=P*||θ||=θ1*X1+θ2*X2

转换一下约束：Z>=1或者Z<=-1时，约束是被P(i)*θ>=1,或者<=-1代替，因为θT*X(i)=P*||θ||.

前面提到的代价函数可以被写成等于
$$ \frac{1}{2}||Θ^2||$$
现在，继续使用之前的简化，即 θ 0 =0。(θ 过原点)
要想最小化代价函数，必须使得θ的范式尽可能小。但是不要忘了一个前提当为正样本时，P(i)*||Θ||>=1,所以必须满足P尽可能的大。而P是特征向量X在参数向量Θ的投影。这个投影长度越大，说明产生间距越大。这就是支持向量机如何能有效地产生大间距分类的原因。

看这条绿线，这个绿色的决策界。我们希望正样本和负样本投影到 θ 的值大。要做到这一点的唯一方式就是选择这条绿线做决策界。这是大间距决策界来区分开正样本和负样本这个间距的值。这个间距的值就是 p (1) p (2) p (3) 等等的值。通过让间距变大，支持向量机最终可以找到一个较小的 θ 范数。这正是支持向量机中最小化目标函数的目的。

核函数

以上介绍的一条直线就可以划分边界的情况，是线性核函数，但很多情况是不能简单的用一条直线就能够划分边界出来的。这时就需要换用更复杂的核函数。这里仅仅列举一下常用的核函数。

• 高斯核函数（Gaussian Kernel）
• sigmoid核函数
• 线性核函数
• 多项式核函数

一些规则

下面是一些普遍使用的准则：
n 为特征数，m 为训练样本数。

• 如果相较于 m 而言，n 要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。
• 如果 n 较小，而且 m 大小中等，例如 n 在 1-1000 之间，而 m 在 10-10000 之间，使用高斯核函数的支持向量机。
• 如果 n 较小，而 m 较大，例如 n 在 1-1000 之间，而 m 大于 50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。

SVM优点：主要在于它的代价函数是凸函数，不存在局部最小值

---