by pluskid, on 2010-09-10, in 
本文是“支持向量机系列”的第二篇，参见本系列的其他文章。
上一次介绍支持向量机，结果说到 Maximum Margin Classifier ，到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图：
可以看到两个支撑着中间的 gap 的超平面，它们到中间的 separating hyper plane 的距离相等（想想看：为什么一定是相等的？），即我们所能得到的最大的 geometrical margin $\tilde{\gamma}$ 。而“支撑”这两个超平面的必定会有一些点，试想，如果某超平面没有碰到任意一个点的话，那么我就可以进一步地扩充中间的 gap ，于是这个就不是最大的 margin 了。由于在 $n$ 维向量空间里一个点实际上是和以原点为起点，该点为终点的一个向量是等价的，所以这些“支撑”的点便叫做支持向量。
很显然，由于这些 supporting vector 刚好在边界上，所以它们是满足 $y(w^Tx+b)=1$ （还记得我们把 functional margin 定为 1 了吗？），而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有 $y(w^Tx+b) > 1$ 。事实上，当最优的超平面确定下来之后，这些后方的点就完全成了路人甲了，它们可以在自己的边界后方随便飘来飘去都不会对超平面产生任何影响。这样的特性在实际中有一个最直接的好处就在于存储和计算上的优越性，例如，如果使用 100 万个点求出一个最优的超平面，其中是 supporting vector 的有 100 个，那么我只需要记住这 100 个点的信息即可，对于后续分类也只需要利用这 100 个点而不是全部 100 万个点来做计算。（当然，通常除了 K-Nearest Neighbor 之类的 Memory-based Learning 算法，通常算法也都不会直接把所有的点记忆下来，并全部用来做后续 inference 中的计算。不过，如果算法使用了 Kernel 方法进行非线性化推广的话，就会遇到这个问题了。Kernel 方法在下一次会介绍。）
当然，除了从几何直观上之外，支持向量的概念也会从其优化过程的推导中得到。其实上一次还偷偷卖了另一个关子就是虽然给出了目标函数，却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目标函数：
\[
\max \frac{1}{\|w\|}\quad s.t., y_i(w^Tx_i+b)\geq 1, i=1,\ldots,n
\]
这个问题等价于（为了方便求解，我在这里加上了平方，还有一个系数，显然这两个问题是等价的，因为我们关心的并不是最优情况下目标函数的具体数值）：
\[
\min \frac{1}{2}\|w\|^2\quad s.t., y_i(w^Tx_i+b)\geq 1, i=1,\ldots,n
\]
到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的 QP (Quadratic Programming) 的优化包进行求解。所以，我们的问题到此为止就算全部解决了，于是我睡午觉去了~ 🙂
啊？呃，有人说我偷懒不负责任了？好吧，嗯，其实呢，虽然这个问题确实是一个标准的 QP 问题，但是它也有它的特殊结构，通过 Lagrange Duality 变换到对偶变量 (dual variable) 的优化问题之后，可以找到一种更加有效的方法来进行求解——这也是 SVM 盛行的一大原因，通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。此外，在推导过程中，许多有趣的特征也会被揭露出来，包括刚才提到的 supporting vector 的问题。
关于 Lagrange duality 我没有办法在这里细讲了，可以参考 Wikipedia 。简单地来说，通过给每一个约束条件加上一个 Lagrange multiplier，我们可以将它们融和到目标函数里去
\[
\mathcal{L}(w,b,\alpha)=\frac{1}{2}\|w\|^2-\sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1\right)
\]
然后我们令
\[
\theta(w) = \max_{\alpha_i\geq 0}\mathcal{L}(w,b,\alpha)
\]
容易验证，当某个约束条件不满足时，例如 $y_i(w^Tx_i+b) < 1$，那么我们显然有 $\theta(w)=\infty$ （只要令 $\alpha_i=\infty$ 即可）。而当所有约束条件都满足时，则有 $\theta(w)=\frac{1}{2}\|w\|^2$ ，亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化 $\frac{1}{2}\|w\|^2$ 实际上等价于直接最小化 $\theta(w)$ （当然，这里也有约束条件，就是 $\alpha_i\geq 0, i=1,\ldots,n$），因为如果约束条件没有得到满足，$\theta(w)$ 会等于无穷大，自然不会是我们所要求的最小值。具体写出来，我们现在的目标函数变成了： \[ \min_{w,b}\;\theta(w) = \min_{w,b}\; \max_{\alpha_i\geq 0}\; \mathcal{L}(w,b,\alpha) = p^* \] 这里用 $p^*$ 表示这个问题的最优值，这个问题和我们最初的问题是等价的。不过，现在我们来把最小和最大的位置交换一下： \[ \max_{\alpha_i\geq 0}\; \min_{w,b}\; \mathcal{L}(w,b,\alpha) = d^* \] 当然，交换以后的问题不再等价于原问题，这个新问题的最优值用 $d^*$ 来表示。并，我们有 $d^*\leq p^*$ ，这在直观上也不难理解，最大值中最小的一个总也比最小值中最大的一个要大吧！ 🙂 总之，第二个问题的最优值 $d^*$ 在这里提供了一个第一个问题的最优值 $p^*$ 的一个下界，在满足某些条件的情况下，这两者相等，这个时候我们就可以通过求解第二个问题来间接地求解第一个问题。具体来说，就是要满足 KKT 条件，这里暂且先略过不说，直接给结论：我们这里的问题是满足 KKT 条件的，因此现在我们便转化为求解第二个问题。
首先要让 $\mathcal{L}$ 关于 $w$ 和 $b$ 最小化，我们分别令 $\partial \mathcal{L}/\partial w$ 和 $\partial \mathcal{L}/\partial b$ 等于零：
\[
\begin{align}
\frac{\partial \mathcal{L}}{\partial w}=0 &\Rightarrow w=\sum_{i=1}^n \alpha_i y_i x_i \\
\frac{\partial \mathcal{L}}{\partial b} = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0
\end{align}
\]
带回 $\mathcal{L}$ 得到：
\[
\begin{align}
\mathcal{L}(w,b,\alpha) &= \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j – b\sum_{i=1}^n\alpha_iy_i + \sum_{i=1}^n\alpha_i \\
&= \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j
\end{align}
\]
此时我们得到关于 dual variable $\alpha$ 的优化问题：
\[
\begin{align}
\max_\alpha &\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \\
s.t., &\alpha_i\geq 0, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{align}
\]
如前面所说，这个问题有更加高效的优化算法，不过具体方法在这里先不介绍，让我们先来看看推导过程中得到的一些有趣的形式。首先就是关于我们的 hyper plane ，对于一个数据点 $x$ 进行分类，实际上是通过把 $x$ 带入到 $f(x)=w^Tx+b$ 算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到 $w=\sum_{i=1}^n \alpha_i y_i x_i$ ，因此
\[
\begin{align}
f(x)&=\left(\sum_{i=1}^n\alpha_i y_i x_i\right)^Tx+b \\
&= \sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b
\end{align}
\]
这里的形式的有趣之处在于，对于新点 $x$ 的预测，只需要计算它与训练数据点的内积即可（这里 $\langle \cdot, \cdot\rangle$ 表示向量内积），这一点至关重要，是之后使用 Kernel 进行非线性推广的基本前提。此外，所谓 Supporting Vector 也在这里显示出来——事实上，所有非 Supporting Vector 所对应的系数 $\alpha$ 都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。
为什么非支持向量对应的 $\alpha$ 等于零呢？直观上来理解的话，就是这些“后方”的点——正如我们之前分析过的一样，对超平面是没有影响的，由于分类完全有超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。这个结论也可由刚才的推导中得出，回忆一下我们刚才通过 Lagrange multiplier 得到的目标函数：
\[
\max_{\alpha_i\geq 0}\;\mathcal{L}(w,b,\alpha)=\max_{\alpha_i\geq 0}\;\frac{1}{2}\|w\|^2-\sum_{i=1}^n\alpha_i \color{red}{\left(y_i(w^Tx_i+b)-1\right)}
\]
注意到如果 $x_i$ 是支持向量的话，上式中红颜色的部分是等于 0 的（因为支持向量的 functional margin 等于 1 ），而对于非支持向量来说，functional margin 会大于 1 ，因此红颜色部分是大于零的，而 $\alpha_i$ 又是非负的，为了满足最大化，$\alpha_i$ 必须等于 0 。这也就是这些非 Supporting Vector 的点的悲惨命运了。 :p
嗯，于是呢，把所有的这些东西整合起来，得到的一个 maximum margin hyper plane classifier 就是支持向量机（Support Vector Machine），经过直观的感觉和数学上的推导，为什么叫“支持向量”，应该也就明了了吧？当然，到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，不过，在得到了 dual 形式之后，通过 Kernel 推广到非线性的情况就变成了一件非常容易的事情了。不过，具体细节，还要留到下一次再细说了。 🙂
深入浅出, 赞一个!
挑个刺儿: 对偶变量的优化公式没对齐:)
OK, update 了。 🙂
写的很好很赞 向师兄学习了
懂了一点点关于求解过程的真相 赞
不过把优化以w为参数的目标函数 变到 优化以alpha为参数的目标函数，这参数的数目不是变多了么？（虽然目标函数的样子是变PP了很多..）
参数有没有变多取决于你的原始维度和数据点的个数，例如生物里的那些基因信息，维度成千上万的，但是数据点通常都只有几十几百个，这类情况通常叫做“小样本学习”。另外，还要考虑到由于“支持向量”的特性，alpha 是稀疏的。此外，如果用了 Kernel ，就更要对 alpha 来求解了，否则（针对不同的 kernel 函数来说）就很难或者甚至根本没法求。
有道理，参数的多少取决于数据量和维度的相对多少。
Alpha的稀疏性有对解这个优化方程带来便利吗？
不知道，我对 optimization 了解得很有限。不过 $\alpha$ 的稀疏性至少是会对 prediction 的时候的计算带来很大的效率提升的，这个是显而易见的。
恩，不过这是针对kernel的情况。如果不是kernel，事先可以直接计算好投影向量w的值。
对 SVM 的应用也还并不是特别熟悉，不知道线性 kernel 用得多不，在各种领域里效果和非线性比起来怎么样。另外我一直觉得 kernel 方法很诡秘，这么几个预先给定的 kernel 函数就能这么牛了？就能把非线性搞成线性了？如果真是那样的话做 non-linear 降维只要先 kernel 映射一下再用线性 PCA 就可以了，实际上 KernelPCA 就是这样搞的。不过比如像 Gaussian kernel 虽然号称 feature space 是无穷维的，但是由有限个数据点张成的，其实也只是一个有限维的子空间而已。
预先给定的 kernel 函数我总是觉得还是有些不太靠谱，或者说其实应该有可以改进的地方的。我觉得 kernel 应该和数据有一定的相关性才对。当然这方面的研究也有不少，比如 LE 、LLE、Isomap 之类的其实都可以看成 Kernel PCA 在某一个特定的 Kernel 函数下的特例。不过我对这些工作也都还不是特别了解。
SVM若用在文本分类中的话，线性核与非线性核性能相仿，但训练速度显然快得多，因此台湾林智仁在libsvm之外又专门开发了liblinear。实际上若样本的特征空间维度很高，则线性核似乎都与非线性核差不多，据说其原因是本身维度已经很高了，再怎么映射也就那样了。。。囧。。我觉得如果能真正弄明白SVM在高维空间中遇见了什么，没准能写出一篇高水平文章。
你提到“不过比如像 Gaussian kernel 虽然号称 feature space 是无穷维的，但是由有限个数据点张成的，其实也只是一个有限维的子空间而已。”何指？对偶后特征空间不就是由内积刻画的么？
不过核与数据相关的思想应该是没错的，最近比较火的多核学习似乎就是这路子吧。
“SVM 在高维空间中遇见了什么”是什么意思？
核空间虽然是由内积刻画，但是也就可以看成数据对应的 RKHS 中的点张成的子空间呀，如果数据点是有限的，那么这个子空间只能是有限维的啊，我是这么理解的。
呵呵，我的意思是，应该弄明白SVM在高维特征空间中到底有什么样的行为，分类面是什么样的。因为我觉得什么东西推广到高维都挺费解的，不是低维空间那些香蕉图、蛋糕卷图（为什么都是吃的- -）等toy data能解释得清的。其实PCA也是这样，即使是人脸图像这样具有非线性特征的数据，先做PCA之后再做FLD或K-means也是work的，很费解。
我还是不明白你说的数据点张成的子空间是什么，它代表的是哪个空间？数据所在的子空间吗？这在SVM分类问题中有何意义？在我看来，SVM的最大间隔的性质保证了无论是100个数据点还是10000个数据点，训练出来的分类面应该不会有太大差别吧。数据越多，支持向量对分类面的控制就越精细，泛化性也会有所提高；但只要数据点别太少，应该都能找到足够好的支持向量，达到比较不错的泛化性。那么你说的那个子空间又是什么，有何实际意义呢？
@loveisp,
超过回复最大嵌套层数了，我直接在这里回了。PCA 没法处理非线性数据是说它不能把非线性数据展开，然而它可以做线性投影，在不触碰到非线性的那个结构之前就可以做很多处理，把空余的维度和噪声维度去掉，所以也能提升性能，这还是比较容易理解的。
数据点张成的子空间，就是每个数据点 $x$ 有一个到 RKHS 中的映射 $\phi:\mathcal{X}\rightarrow \mathcal{H}_K$ 使得 $\phi(x)=K(\cdot,x)$ ，N 个数据点就对应于 $\mathcal{H}_K$ 中的 N 个点，这 N 个点在 RKHS 中当然只能张成维度不超过 N 的一个子空间啦。
严谨的公式推导和直观的理解，太赞了。请问有什么关于机器学习的书籍可以推荐不？
稍微简单一点的《Pattern Classification》，偏统计难一点的《The Elements of Statistical Learning》，偏概率贝叶斯啥的《Pattern Recognition and Machine Learning》。如果能全部看明白的话，应该是对机器学习有一个很全面的了解了。
只翻过最后一个，多谢推荐！总觉得机器学习好悬，希望找些书看看，了解下。
[…] 支持向量机: Support Vector /?p=682 […]
[…] 形式上和以前一样，只是把 xi 换成了 fi ，w 换成了 g ，但是现在我们要求的参数 g 是在 Hilbert Space 中，特别当 H 是无穷维的时候，是没有办法直接使用数值方法来求解的。即使可以转到 dual 优化推导，但是里面涉及到对无穷维向量的求导之类的问题，我还不知道是不是能直接推广。不过幸运的是，我们在这里可以再把问题转化到有限维空间中。 […]
[…] 支持向量机: Support Vector —— 介绍支持向量机目标函数的 dual 优化推导，并得出“支持向量”的概念。 […]
看了很多讲解了，最让我不明白的是alpha最终是如何迭代，得到最优的呢？？能不能指导一下啊
可以看关于优化的第 5 篇，虽然那里也只是讲了个大概。
Hi,在Steve R. Gunn 的文章Support Vector Machines for Classification and Regression(链接：www.svms.org/tutorials/Gunn1998.pdf)之公式(2.23)有提到||w||^2等于所有\alpha_i之和，你是如何理解呢？
你好，我不知道他那个式子是怎么得到的呢，那个式子的最左边和最右边相等是显然的，但是中间的等号怎么成立我就不清楚了，如果 b=0 的话倒是对的，但是如果 $b\neq 0$ 似乎不能得到啊。
对，这个问题我也纠结了很久。因为$w \cdot x_i=-b+y_i$若$b$非零，最右边式子会带一个含$b$的项。
我看他那里提到这个式子似乎是在分析 VC dimension 之类的地方用到，关于这部分内容我不太了解。不过我想关于 VC dimension 似乎是对于算法结构的复杂性的分析，这样子的话，我如果把整体数据点的坐标平移一下，就可以让 b 等于 0 ，应该不会影响到算法的复杂度，也许这样所以它就直接考虑 b = 0 的情况了。纯属猜测。
更新一下链接:
Lagrange Duality 的链接现在是这个:Lagrange Duality
🙂
然后发现右侧的留言框被我的 link 撑爆了 =.=
恩，好的，链接更新啦。于是我编辑了下留言，现在撑不爆啦 :p
博文很赞啊，请教个问题：大家都在说SVM可以针对小样本，这里的小样本是什么意思啊
小样本就是样本数目比较小。
请问博主，$\sum_{i=1}^n\alpha_iy_i = 0$ 这个式子有什么含义？
你好,我想问一下,你的latex公式是怎么输入进去的啊,可否示范一下?
博主的文章太棒了，非常赞！！！
这里我有一个问题请教：判别点分类值的决策函数为f(w,b)时，计算新点从直观上理解只用计算一次，但是不容易计算，而将决策函数转换为f(α,x,y)后，容易计算（只用计算新点与支持向量的内积），但是否要计算多次呢？例如支持向量有三个，是否就要计算三次，这三次计算结果会不会不一样？（如果不一样那分类结果就不确定了），所以猜测应该三次会相同，如果相同，那不是只用挑一个支持向量计算就可以了，而不用麻烦的计算三次
多谢博主解答，问题有些长了，呵呵
你好，不是那样的，和所有支持向量的内积都要计算出来，并按照系数加权起来才能得到分类结果的。
多谢博主解答
ai 值是自己设定，还是算出来的
算出来的。
求问下大牛：
将min-max转化称max-min的动机是什么呢？如果单纯要化简，在min-max形式下应该也可以算出来一个用w和b表示的a的。
这个是跟SMO有关么？多谢
再求问下大牛有木有看过multi-class SVM的资料呢？ 如果用one-vs-all的话，会不会由于data bias导致结果有问题呢。。。多谢！
multiclass svm 有直接解的算法，搜索 crammer singer svm 。
非常感谢！
“最大值中最小的一个总也比最小值中最大的一个要大吧！”这个说法不科学吧，亲~
有个问题不明白，为什么L(theta,b, alpha)在条件不满足的时候只要设置alpha为无穷，他的值就是无穷？ 不是应该在加上alpha吗？
theta 为无穷，不是 L 为无穷。
讲得真好 非常有用 感谢！
目标函数应该是θ(w,b)而不是θ(w)吧？
嗯，是的。
嘿嘿，我最近做毕业设计也是这方面的内容。你的文章对我帮助很大，谢谢。
P.S. 虽然w的计算公式给出了，但是如果能给出b的计算公式，我觉得会更完整一些。
博主对svm了解的很透彻了，最近我也在深究svm。有些疑问，这篇博文里面最后的求解QP问题的时候，不是利用拉格朗日对偶变换做的吧，应该是Wolfe对偶变换做的（参考http://en.wikipedia.org/wiki/Duality_(optimization)#The_strong_Lagrangian_principle:_Lagrange_duality），此外，个人感觉求解svm中的QP问题有两个解法：一是利用wolfe对偶变换，二是利用kkt条件直接求解（参考http://mat.gsia.cmu.edu/classes/QUANT/NOTES/chap4.pdf）。不知博主怎么看？
你好世界
Wolfe Dual 不就是 Lagrange Dual 的特殊情况（函数可微）吗？SVM 的解法现有非常非常多种了，包括有非常多的直接解 primal 问题的方法。现成的软件包也有很多种类。
我使用sklearn中的svc计算出来的support vector并不满足y(\omega ^{T}x+b)=1,它们的结果是:
[0.95493544]
[0.68297233]
[0.78527174]
[0.75466533]
[1.00048702]
[0.61406257]
[ 0.779535 ]
[ 0.57337293]
[ 1.00024232]
[ 0.85852265]
[ 1.00024201]
[-1.46838687]]
请大神帮忙解释一下
我知道了，这是soft-margain svm，谢谢你分享的知识
最后一个公式，红色部分为0，/alpha 也可以为0啊，不是吗？
讲得真好 非常有用 感谢！
感谢博主详细的讲解
太cool了，想kid学习