支持向量机算法 SVM

很努力地把公式截图贴到简书上，但效果还是不理想。因为文字间的公式非常难排版，且弄起来老感觉蛋疼 ...... 如果想看完整排版的移步 http://blog.kamidox.com/svm.html

支持向量机算法 SVM 是 Support Vector Machine 的缩写，它是工业和学术界都有广泛应用的强大的算法。

从逻辑回归算法谈起

逻辑回归算法的预测函数

逻辑回归算法的预测函数称为 Sigmoid Function ，如下图：

logistic cost function

如果我们去掉 $\frac{1}{m}$ 和累加器，同时暂时不考虑正则项，则可以得到另外一个样式的成本函数：

logistic cost function: style 1

当 $y^{(i)}=1$ 时，$1-y^{(i)}=0$，故这一式子再简化为：

logistic cost function: style 2

把上述函数以成本 J 为纵坐标，z 为横坐标，画出来的函数曲线如下：

logistic cost function for y=0

把上述函数以成本 J 为纵坐标，z 为横坐标，画出来的函数曲线如下：

svm cost function

这就是用在支持向量机算法里的成本函数。这里的参数 C 越大，正则项的比重就越小，就容易造成过拟合。反之，如果 C 越小，正则项的比重就越大，就容易造成欠拟合。

支持向量机的预测函数

我们定义支持向量机的预测函数如下：

svm predict function

这里和逻辑回归算法比较，针对逻辑回归算法，其正负样本分界线为 $\theta^T x = 0$，即 $\theta^T x > 0$ 时为正样本，当 $\theta^T x < 0$ 时为负样本。而支持向量机的分类预测函数要求更严格，它要求 $\theta^T x >= 1$ 时为正样本，$\theta^T x <= -1$ 时为负样本。根据支持向量机的成本函数图形，只有这样成本才最小，即成本为零。如下图所示：

simplified cost function for svm

求解这个函数的结果，就会让我们获得一个较大间距的分类算法。如下图所示，假设我们有个分类问题。那么洋红色和绿色的都可以是合法的分界线，但 SVM 可以得到黑色的分界线，即确保到两个类别有最大的间距。

vector inner product

其中 p 就是 v 在 u 上的投影的长度，它是有符号的实数；$|u|$ 是向量 u 的范数，即向量 u 的长度，其值为 $\sqrt{u_1^2 + u_2^2}$。

从数学上理解为什么支持向量机会把类别边界的间距做到最大

假设我们只有两个特征，即 n = 2，则 $J(\theta) = \frac{1}{2} \sum_{j=1}^n \theta_j^2$ 简化为：

simplified svm cost function

回到 SVM 算法的预测函数：

svm prediction function

即当预测为正样本时，我们需要 $\theta^T x >=1$，这个式子可以理解为向量内积，它的几何含义是x 在 $\theta$ 上的投影的长度大于等于 1，即 $p | \theta | >= 1$。如下图所示：

theta and x inner product

而我们的算法求解目标是使 $J(\theta) = \frac{1}{2} | \theta |^2$ 最小，所以 SVM 算法的求解目标就是要让 p 尽可能最大。即使所有的训练样例点 $x^{i}$ 到参数向量 $\theta$ 的投影长度最大。在几何上，决策边界和参数 $\theta$ 是正交的。如下图所示：

svm decision boundary

绿色线为决策边界，绿色线为 $\theta$ 所代表的向量。那么 SVM 的求解目标就是让各个训练样例的点 $x^{i}$ 到 $\theta$ 上的投影长度最大。上图中，我们可以试着换一个决策边界，试着画出训练样例到这个新的决策边界所决定的参数 $\theta$ 的投影长度，即可理解为什么 SVM 可以让决策边界得到最大的间距。