机器学习第十三章——支持向量机
优化目标
在逻辑回归中，我们的预测函数为：
对于每一个样本 (x,y) 而言（注意是每一个），其代价函数为：
那么当 y=1 的时候， ，其代价函数的图像入左下图所示。
当 y=0 的时候， ，其代价函数的图像入右下图所示。
其中是一个常数可以去掉，因为对于代价函数求最小值，然后去参数
没有影响，然后我们将带入cost（）；
对于支持向量机而言，
的时候：
的时候：
当 y=1 时，随着 z 取值变大，预测代价变小，因此，逻辑回归想要在面对正样本 y=1 时，获得足够高的预测精度，就希望 。而 SVM 则将上图的曲线拉直为下图中的折线，构成了 y=1 时的代价函数曲线
：
当 y=1 时，为了预测精度足够高，SVM 希望 。
同样，在 y=0 时，SVM 定义了代价函数 ，为了预测精度足够高，SVM 希望
：
在逻辑回归中，其代价函数是：
对于逻辑回归而言，其代价函数是有两项决定的，第一项是来自训练样本的代价函数，第二项是正则化项，这就相当于我们用最小化 A 加上正则化参数 乘以参数平方项 B，其形式大概是：
。这里我们是通过设置不同的正则参数
来达到优化的目的。但是在支持向量机这里，把参数提到前面，用参数 C 作为 A 的参数，以 A 作为权重。所以其形式是这样的：
。
在逻辑回归中，我们通过正规化参数 调节 A、B 所占的权重，且 A 的权重与
取值成反比。而在 SVM 中，则通过参数 C 调节 A、B 所占的权重，且 A 的权重与 C 的取值成反比。亦即，参数 C 可以被认为是扮演了
的角色。
所以 这一项仅仅是相当于一个常量，对于最小化参数
是没有完全任何影响的，所以这里我们将其去掉。
支持向量机的代价函数为：
有别于逻辑回归假设函数输出的是概率，支持向量机它是直接预测 y 的值是0还是1。也就是说其假设函数是这样子的：
大间距分类器
支持向量机是最后一个监督学习算法，与前面我们所学的逻辑回归和神经网络相比，支持向量机在学习复杂的非线性方程时，提供了一种更为清晰、更加强大的方式。
支持向量机也叫做大间距分类器(large margin classifiers)。
假如我们有一个数据集是这样的，可以看出，这是线性可分的。但是有时候我们的决策边界就好像图中两条竖着的线一样，这样的决策边界看起来都不是特别好的选择。支持向量机就会选择斜着的那一条决策边界。这条边界相比之前跟正负样本有更大的距离，而这个距离就叫做间距（margin）。这也是为什么我们将支持向量机叫做大间距分类器的原因。
支持向量机模型的做法是，即努力将正样本和负样本用最大的间距分开，我们的目的就是要让边界线离他最近样本点的距离，也就是支持向量机的间距尽可能的大。
当 y=1 时，SVM 希望 。在 y=0 时，SVM 希望
，对于前面的那一项 A 最小化代价函数，那么最理想当然是为0。所以这就变成了：
参数 C 其实是支持向量机对异常点的敏感程度，C 越大就越敏感，任何异常点都会影响最终结果。 C 越小，对异常点就越不敏感，普通的一两个异常点都会被忽略。
，
为正则化的参数。
↑，C↓,会受到异常数据的影响较小。
↓，C↑,会受到异常数据的影响较大。
大间隔分类器的数学原理
以两个二维向量为例，我们把向量 v 投影到向量 u 上，其投影的长度为 p， 为向量 u 的模，那么向量的内积就等于
。在代数定义向量内积可表示为：
，根据此定义可以得出：
。
为
的范数，也就是向量
的欧几里得长度。
最小化函数为：
这里以简单的二维为例(也就是=0，n=2)：
毕达哥拉斯定理：
只要 能最小，最小化函数就能取到最小。
当垂直的时候 取最小值(垂直的时候，两个向量的夹角 cos
最小)。这就解释了为什么支持向量机的决策边界不会选择左图绿色那条。因为方便理解所以
，这就意味着决策边界要经过原点。然后我们可以看到在垂直于决策边界的
和
的关系（红色投影和粉红色投影），可以看到其投影
的值都比较小，这也就意味着要
的值很大。这显然是与最小化公式
矛盾的。所以支持向量机的决策边界会使
在
的投影尽量大。
这就是为什么决策边界会是右图的原因，也就是为什么支持向量机能有效地产生最大间距分类的原因。
,
越小，
越大。
=
就会越大。
因此只有最大间距才能使 大，从而
值小
核函数
1. 定义
在我们之前拟合一个非线性的判断边界来区别正负样本，是构造多项式特征变量。
我们先用一种新的写法来表示决策边界： 。我们这里用
表达新的特征变量。
假如是之前我们所学的决策边界，那么就是： ，等等。但是这样的高阶项作为特征变量并不是我们确定所需要的，而且运算量非常巨大，那么有没有其他更高的特征变量呢？
下面是构造新特征量的一种想法：
为了简单理解，我们这里只建立三个特征变量。首先我们在 坐标轴上手动选择3个不同的点：
。
然后我们将第一个特征量定义为： ，可以看做是样本 x 和第一个标记
的相似度。其中可以用这个公式表达这种关系：
(exp：自然常数e为底的指数函数)
类似的有： ，
。这个表达式我们称之为核函数（Kernels），在这里我们选用的核函数是高斯核函数（Gaussian Kernels）。
那么高斯核函数与相似性又有什么关系呢？
先来看第一个特征量 ，
假如样本 x 非常接近 ，即
，那么：
。
假如样本 x 离 非常远，即
，那么：
。
可视化如下：
从图中可以看到越接近 的值越大。
这里顺带说一下 这个高斯核函数的参数对函数的影响。从图中可以看到，减小或者增加只会对图像的肥瘦产生影响，也就是影响增加或者减小的速度而已，
的越小，函数的值减小的越快，
越大，函数的值减小的越慢 。
2. 标记点选取
通过标记点以及核函数，训练出非常复杂的非线性判别边界。那标记点 这些点是怎么来的？
假定我们有如下的数据集：
我们就将每个样本作为一个标记点：
则对于样本 ，我们计算其与各个标记点的距离：
得到新的特征向量：
其中
则具备核函数的 SVM 的训练过程如下：
SVMs in Practice
1. 使用流行库
作为当今最为流行的分类算法之一，SVM 已经拥有了不少优秀的实现库，如 libsvm 等，因此，我们不再需要自己手动实现 SVM（要知道，一个能用于生产环境的 SVM 模型并非课程中介绍的那么简单）。
在使用这些库时，我们通常需要声明 SVM 需要的两个关键部分：
- 参数 C
- 核函数（Kernel）
由于 C 可以看做与正规化参数 作用相反，则对于 C 的调节：
低偏差，高方差，即遇到了过拟合时：减小 C 值，也就是增加的值，也就是减小参数
的值，来解决过拟合。
高偏差，低方差，即遇到了欠拟合时：增大 C 值，也就是减小的值，也就是增加参数
的值，来解决欠拟合。
而对于核函数的选择有这么一些 tips：
-
当特征维度 n 较高，而样本规模 m 较小时，不宜使用核函数，否则容易引起过拟合。
-
当特征维度 n 较低，而样本规模 m 足够大时，考虑使用高斯核函数。不过在使用高斯核函数前，需要进行特征缩放（feature scaling）。
-
当核函数的参数
较大时，特征
较为平缓，即各个样本的特征差异变小，此时会造成欠拟合（高偏差，低方差），如下图上边的图，
-
当
2. 多分类问题
通常，流行的SVM库已经内置了多分类相关的 api，如果其不支持多分类，则与逻辑回归一样，使用 One-vs-All 策略来进行多分类：
- 轮流选中某一类型 i ，将其视为正样本，即 “1” 分类，剩下样本都看做是负样本，即 “0” 分类。
- 训练 SVM 得到参数
，即总共获得了 K−1 个决策边界。
- 通过比较
的值，那个分类模型的值最大，就是属于哪一类。
3. 分类模型的选择
目前，我们学到的分类模型有：
（1）逻辑回归；
（2）神经网络；
（3）SVM
怎么选择在这三者中做出选择呢？我们考虑特征维度 n 及样本规模 m ：
如果 n 相对于 m 非常大，例如 n=10000 ，而 ：此时选用逻辑回归或者无核的 SVM。
如果 n 较小，m 适中，如 ，而
：此时选用核函数为高斯核函数的 SVM。
如果 n 较小，m 较大，如 ，而 m>50000 ：此时，需要添加或者创建更多的特征（比如通过多项式扩展），再使用逻辑回归或者无核的 SVM。 神经网络对于上述情形都有不错的适应性，但是计算性能上较慢。