支持向量机(SVM)

1. 推导及理解

借鉴于逻辑回归的代价函数，我们给出了支持向量机的整个优化的目标函数如下：

当最小化这个代价函数，我们会得到参数θ$\theta$，然后用这个参数θ$\theta$来预测y$y$的值为１还是０。当θTx${\theta }^{T}x$大于或者等于０时，假设预测为１；否则，预测为０．
支持向量机常被称作大间距分类器，其实就是引入了安全的间距因子。如下图：

当y=1$y=1$我们希望θTx≥1${\theta }^{T}x\ge 1$，当y=０$y=０$我们希望θTx≤−1${\theta }^{T}x\le -1$，不再以０为边界，增强了限制，相当于嵌入了一个额外的安全因子！然后代价函数左边这一项会为０，只剩下右边这一项！按照这种方式优化，我们可以得到一个很有意思的边界！
我们可以通过一个图像来更加直观的来看，对于下面这样一个数据集，其中有正样本也有负样本，我们能否找到一条直线将正负样本分开呢？

没错，我们可以找到如下图很多直线来将正负样本分开。

可是，这条黑色的线比其他线要好很多，看起来像是更稳定的决策边界。如下图，

黑色的决策边界有和训练样本之间有更大的最短距离，这个距离我们称为间距(margin)。支持向量机的基本思想就是努力将正样本和负样本用最大的间距分开，因而也被成为最大间距分类器。
当上面代价函数左边为０时，支持向量机的最小化问题就变成：

补充小知识：向量的内积等与一个向量到另一个向量的投影乘以另一个向量的范数。

即uTv=p⋅||u||$u^{T}v=p\cdot ||u||$，注意投影p$p$可能为负。

那么我们就可以让x(i)$x^{(i)}$对参数向量θ$\theta$作投影得到ｐ(i)${ｐ}^{(i)}$，然后使用p(i)⋅||θ||$p^{(i)}\cdot ||\theta ||$代替代价函数中的θTx(i)${\theta }^T{x}^{(i)}$，得到：

下面来直观的理解支持向量机如何能有效的产生大分类器的原因。
当边距比较小时，投影p$p$会很小，由于我们需要p(i)⋅||θ||≥1，$p^{(i)}\cdot ||\theta ||\ge 1，$那么需要的||θ||$||\theta ||$会很大；对于负样本也是同样的道理，theta$theta$的范数也会很大，所以这看起来不是一个好的参数向量θ$\theta$的选择。

再看下图，当投影长度更长时，会有一个好一点的参数向量θ$\theta$的选择。

2.核函数

我们可以使用核函数构建一个更复杂的非线性的分类器。比如如下图所示的分类边界，

我们可以使用核函数计算出新的特征。
给定一个训练实例x$x$，利用x$x$的各个特征与我们预先选定的地标(landmarks)l(1),l(2),l(3)...$l^{(1)},l^{(2)},l^{(3)}...$，的近似程度来选取新的特征f1,f2,f3...$f_1,f_2,f_3...$。

这个例子中的similarity(x,l(1))$similarity(x,l^{(1)})$就是高斯核函数(Gaussian Kernel)。(这个函数和正态分布没什么关系，只是看上去像而已)
这些地标(landmark)的作用是什么？如果训练集x$x$与地标l$l$的之间的距离近似于０，则新特征f$f$近似于e−0=1$e^{-0}=1$；如果训练集x$x$与地标之间的距离较远，则f$f$近似于e−(一个较大的数)=0$e^{-(一个较大的数)}=0$.

对于上述选取三个地标的例子，我们得到了以下边界。在边界区域内我们预测为１，不在边界区域内我们预测为０.

预测时我们采用的特征不是训练实例本身的特征，而是通过核函数计算出来的新特征。

那么怎么去选取地标呢？
我们通常是根据训练集的数量来选取地标的数量，即如果训练集中有ｍ个实例，则我们选取ｍ个地标，并且令l(1)=x(1),l(2)=x(2),l(3)=x(3),....,l(m)=x(m)$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},l^{(3)}=x^{(3)},....,l^{(m)}=x^{(m)}$。这样做的好处在于：现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即，

另外，支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而实例非常少时，可以采用这种不带核函数的支持向量机。

注意：这里没有讲最小化支持向量机的代价函数的方法，可以参考使用现有的软件包liblinear,libsvm。

参考资料：
[1]course机器学习笔记
[2]周志华机器学习
[3]一文解析支持向量机(带公式推导)