支持向量机简介

从Logistic回归到SVM

本节通过Logistic回归的代价函数，演化到SVM的代价函数，然后通过代价函数最小化推导SVM的判别界[1, P. 3—14]。

Logistic回归的代价函数为

\begin{equation} \begin{aligned} J(\boldsymbol\theta) = &-\frac{1}{m}\sum_{i=1}^{m}\left(y^{(i)}\log h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right)+\left(1-y^{(i)}\right)\log \left(1-h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right)\right)\right) \\ & + \frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2 \end{aligned}， \label{eq:cf-logistic-regression-r} \end{equation}

取出代价函数中的一项如下图，并绘制逼近Logistic代价函数的两个新的代价函数项$\mbox{cost}_1(\mathbf z)$和$\mbox{cost}_0(\mathbf z)$。

图 1: 图解Logistic回归的代价函数 [PNG]

将Logistic回归的代价函数提取$\lambda\over m$，令$C={1\over\lambda}$，并用新的代价函数项替代Logistic回归的代价函数项，可得SVM的代价函数

\begin{equation} J(\boldsymbol\theta) = C\sum_{i=1}^{m}\left(y^{(i)}\mbox{cost}_1\left(\boldsymbol\theta ^T\mathbf x^{(i)}\right)+\left(1-y^{(i)}\right)\mbox{cost}_0\left(\boldsymbol\theta ^T\mathbf x^{(i)}\right)\right) + \frac{1}{2}\sum_{j=1}^n\theta_j^2 ， \label{eq:cf-svm-r} \end{equation}

新的代价函数不再以$0$作为分类边界，而是以$+1$和$-1$。若代价函数\eqref{eq:cf-svm-r}要得最小值，可得SVM的判别界

\begin{equation} \begin{aligned} & \min_\boldsymbol\theta\frac{1}{2}\sum_{j=1}^{n}\theta_j^2 & \\ & \begin{aligned} \mbox{s.t.} & ~~ \boldsymbol\theta^T\mathbf x^{(i)} \geq 1 &\mbox{if} & ~~ y^{(i)} = 1 \\ & ~~ \boldsymbol\theta^T\mathbf x^{(i)} \leq -1 & \mbox{if} & ~~ y^{(i)} = 0 \end{aligned} \end{aligned}。 \label{eq:svm-decision-boundary} \end{equation}

图 2: 图解SVM的判别界 [PNG]

根据向量间的夹角公式$\cos\theta = \frac{\boldsymbol\theta^T\mathbf x^{(i)}}{\left\lVert\boldsymbol\theta\right\rVert\left\lVert\mathbf x^{(i)}\right\rVert}$，则$p^{(i)}=\left\lVert\mathbf x^{(i)}\right\rVert\cos\theta$表示向量$\mathbf x^{(i)}$在向量$\boldsymbol\theta$上的投影，SVM的判别界\eqref{eq:svm-decision-boundary}可以改写为

\begin{equation*} \begin{aligned} & \min_\boldsymbol\theta\frac{1}{2} \lVert\boldsymbol\theta\rVert^2 & \\ & \begin{aligned} \mbox{s.t.} & ~~ p^{(i)}\lVert\boldsymbol\theta\rVert \geq 1 &\mbox{if} & ~~ y^{(i)} = 1 \\ & ~~ p^{(i)}\lVert\boldsymbol\theta\rVert \leq -1 & \mbox{if} & ~~ y^{(i)} = 0 \end{aligned} \end{aligned}。 \end{equation*}

$\boldsymbol\theta$是判别界的法线，$p^{(i)}$的值可正可负。要满足判别界的条件，$\left\vert p^{(i)}\right\vert$越大越好，这样$\lVert\boldsymbol\theta\rVert$就可以取到很小的值。因此，上图中右下比左下有更大的$\left\vert p^{(i)}\right\vert$，是更合适的SVM判别界。

核函数

SVM为了解决非线性可分问题，需要引入核函数（kernel）。作为SVM的核函数须满足Mercer定理。

Mercer 定理[2]

---

函数$\kappa$是 $\mathbb R^n \times \mathbb R^n \to \mathbb R$ 上的映射。如果$\kappa$是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例$\{\mathbf x_1,\mathbf x_2,\ldots,\mathbf x_n\}$，其相应的核函数矩阵是对称半正定的。

通过特征与参考地标（landmark）$\mathbf l^{(i)}$之间的相似性，定义高斯核为[1, P. 17—20]

\begin{equation} \mathbf f_i = \mbox{similarity}\left(\mathbf x, \mathbf l^{(i)} \right) = \exp\left(-\frac{\left\lVert\mathbf x - \mathbf l^{(i)}\right\rVert}{2\sigma^2} \right)。 \end{equation}

核函数的作用相当于特征变换，SVM引入了核函数的代价函数为

\begin{equation} J(\boldsymbol\theta) = C\sum_{i=1}^{m}\left(y^{(i)}\mbox{cost}_1\left(\boldsymbol\theta ^T\mathbf f^{(i)}\right)+\left(1-y^{(i)}\right)\mbox{cost}_0\left(\boldsymbol\theta ^T\mathbf f^{(i)}\right)\right) + \frac{1}{2}\sum_{j=1}^n\theta_j^2。 \label{eq:cf-svm-kernel-r} \end{equation}

在使用高斯核之前，需要对特征进行规范化，使其取值取值近似位于同一区间。SVM代价函数和核函数的参数对SVM分类有如下影响[1, P. 25]：

1. 大的$C~\left(C={1\over\lambda}\right)$导致Low Bias和High Variance；
2. 小的$C~\left(C={1\over\lambda}\right)$导致High Bias和Low Variance；
3. 大的$\sigma^2$使得特征$\mathbf f_i$变化平缓，导致High Bias和Low Variance；
4. 小的$\sigma^2$使得特征$\mathbf f_i$变化较大，导致Low Bias和High Variance。

图 3: 高斯核的SVM分类效果 [SVG, PNG]

对于在线性可分的数据集上训练线性核的SVM，采用不同的$C$也会得到不同的分界面。比如，增大$C$可能得到更大的$\boldsymbol\theta$值，以增大在特定样本之间的分类间隔。

SMO算法

使用SVM

Logistic回归强调所有点尽可能地远离中间那条线，SVM更应该关心靠近中间分割线的点，让他们尽可能地远离中间线。SVM考虑局部（不关心已经确定远离的点），Logistic回归考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）[3]。

Logistic回归、SVM、神经网络

如何在分类器Logistic回归、SVM和神经网络之间做出选择？

$n$为特征数目（$x\in \mathbb{R}^{n+1} $），$m$为训练集样本数目，分类器选择的方法如下[1, P. 31]：

1. 若$n$很大（比如$n\geq m, n=10000,m=10,\ldots,1000$），采用Logistic回归或者无核函数（线性核函数）的SVM（此种情况，用Logistic回归难以训练好非线性分类器）；
2. 若$n$很小而$m$大小适中（比如$n=1,\ldots,1000,m=10,\ldots,10000$），采用高斯核的SVM；
3. 若$n$很小而$m$很大（比如$n=1,\ldots,1000,m=50000+$），先可以增加特征，然后采用Logistic回归或者无核函数（线性核函数）的SVM（此种情况，高斯核的SVM分类器训练会慢）；
4. 神经网络在以上大多数情况都工作较好，但是可能训练速度会很慢；
5. 神经网络是非凸优化，会陷入局部极值，SVM是凸优化，不用担心陷入局部极值。

选择Logistic回归或者无核函数（线性核函数）的SVM，是因为Logistic回归和无核函数（线性核函数）的SVM相似。

核函数的Logistic回归训练较慢，核函数的SVM可以训练较快。

应用案例

垃圾邮件分类[4, P. 10—15]

图 4: Email转换为特征向量 [SVG]

垃圾邮件分类首先需要将Email文本转换为特征向量。如上图所示，转换方法如下：

1. 将Email文本转换为纯单词，比如：单词小写化，移除所有HTML标签，url链接均用单词httpaddr代替，提取词干（例如including、includes和included都用include代替）等；
2. 利用事先准备的词典，将单词用其在词典中的索引表示，实际应用中，词典通常有10000到50000个单词；
3. 将索引转换为$\{0, 1\}$特征向量，向量长度和词典中词汇数目一样，某个单词出现用$1$表示，否者用$0$表示。

相关评论

事实上，支持向量机是一个具有很好数学基础的分类方法，但它本质上也只不过是一个简单的两层方法：第一层可以看作是一些单元集合（一个支持向量就是一个单元），这些单元通过核函数能够度量输入向量和每个支持向量的相似度；第二层则把这些相似度做了简单的线性累加。支持向量机第一层的训练和最简单的无监督学习基本一致：利用支持向量来表示训练样本。一般来讲，通过调整核函数的平滑性（参数）能在线性分类和模板匹配之间做出平衡。从这个角度来讲，核函数只不过是一种模板匹配方法。[5]

［@余凯_西二旗民工］很多有关SVM的教科书都有misleading: (1)KKT条件，support vectors，quadratic programing都是浮云；（2）kernel本身对理解学习问题有帮助，但实际工程上用处为0；（3）hinge loss只是众多可选项之一，logistic效果一点不差。［@老师木］做论文时迷信kernel，margin，认为这些机制和graphical model结合不就无敌了吗？等论文出来的结论是hinge loss对比无优越性。再翻vapnik的 统计学习的本质，原来他老人家也早做过对比试验，没发现svm相对于lr的优越性。看损失函数曲线，真看不出hinge loss比log loss好，只是hinge loss能得到稀疏解，看上去很美。当然理解这些优化理论本身会给人一些享受。数据线性可分的可能性随维度升高而变大，这是Thomas cover五六十年代得出的结论。要严格一点，数据线性可分和线性无关等价，张成维度高的线性空间所需的基多，其实就是VC维了。引入kernel就是引入非线性，使变换后的样例线性无关。Rbf核等价于无穷次多项式拟合，相对于有限的样例，没有不能分开的。[6]

参考资料

1. [1]A. Ng, “Support Vector Machines.” Coursera, 2014. [Online]
2. [2]July, “支持向量机通俗导论（理解SVM的三层境界）.” csdn, 2014. [Online]
3. [3]JerryLead, “支持向量机SVM（一）.” cnblogs, 2011. [Online]
4. [4]A. Ng, “Programming Exercise 6: Support Vector Machines.” Coursera, 2014. [Online]
5. [5]Y. LeCun, “深度学习与支持向量机有什么联系？.” 52cs, 2014. [Online]
6. [6]老师木, “SVM神话.” 52cs, 2014. [Online]

脚注