支持向量机简介

| 研究学术  | 机器学习基础  支持向量机  回归 

从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)$。

图解Logistic回归的代价函数
图 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}

图解SVM的判别界
图 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。
高斯核的SVM分类效果
图 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]

Email转换为特征向量
图 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]

脚注


打赏作者


上一篇:机器学习实战技能     下一篇:聚类(1):k均值算法