章节目录
- 间隔与支持向量
- 对偶问题
- 核函数
- 软间隔与正则化
- 支持向量回归
- 核方法
支持向量机，因其英文名为support vector machine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
（一）间隔与支持向量
给定训练样本D={(x1, y1), (x2, y2), …,(xm, ym)}, yi∈{-1, +1}，分类学习最基本的想法就是基于训练集D在样本空间找到一个划分超平面：
在样本空间中，划分超平面可通过如下线性方程来描述，
假设超平面（w，b）能将训练样本正确分类，即对于(xi, yi)∈D，令，
距离超平面最近的这几个训练样本点称为“支持向量”（support vector），两个异类支持向量到超平面的距离之和为，
称为“间隔”（margin）。
找到“最大间隔”（maximum margin）的划分超平面，就是支持向量机（Support Vector Machine，简称SVM）的基本型。
目标函数：
由于求$||w||^{-1}$的最大值相当于求$||w||^2$的最小值，所以上述目标函数等价于（w由分母变成分子，从而也有原来的max问题变为min问题，很明显，两者问题等价）：
因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。
补充：函数间隔与几何间隔
在超平面w*x+b=0确定的情况下，|w*x+b|能够表示点x到距离超平面的远近，而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。
定义函数间隔为：
而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w, b)关于训练数据集T的函数间隔：
$$\hat\gamma= \text{min} \hat\gamma_i\; (i=1，…n)$$
但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。
事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离–几何间隔（geometrical margin）的概念。
假定对于一个点x ，令其垂直投影到超平面上的对应点为 $x_0$ ，$w$ 是垂直于超平面的一个向量，为样本x到超平面的距离，如下图所示：
根据平面几何知识，有:
$$x=x_0 +\gamma \frac w{||w||} $$
其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念），$\frac w{||w||}$是单位向量（一个向量除以它的模称之为单位向量）。
又由于$w_0$是超平面上的点，满足$w^Tx+b=0 $ ，代入超平面的方程，可得$w^Tx_0+b=0 $ ，即$w^Tx_0=-b $ 。
随即让此式$x=x_0 +\gamma \frac w{||w||} $的两边同时乘以$w^T$，再根据$w^Tx_0=-b $和$w^Tw=||w||^2$，即可算出：
$$\gamma = \frac {$w^Tx+b}{||w||} = \frac {f(x)}{||w||} $$
为了得到$\gamma$的绝对值，令$\gamma$乘上对应的类别y，即可得出几何间隔（用$\hat\gamma$表示）的定义：
$$\hat\gamma = y \gamma = \frac {\hat\gamma}{||w||} $$
从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。
（二）对偶问题
我们对SVM基本型求解是一个凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法。即对SVM的基本型使用拉格朗日算子法得到其“对偶问题”（dual problem）。
支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
KKT条件
一般地，一个最优化数学模型能够表示成下列标准形式：
其中，f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，p和q分别为等式约束和不等式约束的数量。
同时，得明白以下两点：
凸优化的概念：$\mathcal{X} \subset \mathbb{R}^n$ 为一凸集， $f:\mathcal{X}\to \mathbb{R}$ 为一凸函数。凸优化就是要找出一点 $x^\ast \in \mathcal{X}$ ，使得每一 $x \in \mathcal{X} $满足$ f(x^\ast)\le f(x)$ 。
KKT条件的意义：它是一个非线性规划（
Nonlinear Programming）问题能有最优化解法的必要和充分条件。
经过论证，我们这里的问题是满足 KKT 条件的（首先已经满足Slater条件，再者f和gi也都是可微的，即L对w和b都可导），因此现在我们便转化为求解第二个问题。
也就是说，原始问题通过满足KKT条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3个步骤：首先要让L(w，b，a) 关于 w 和 b 最小化，然后求对的极大，最后利用SMO算法求解对偶问题中的拉格朗日乘子。
（三）核函数
在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。
对这样的问题，可以将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如下图：
幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
令Φ(x)表示将x映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为，
$$f(x) = w^T \phi(x) +b $$
其对偶问题是，
求解设计到计算：
$$\phi(x_i)^T \phi(x_j) $$
，这是样本xi与xj映射到特征空间之后的内积。由于特征空间的维数可能很高，甚至可能到无穷维，因此直接计算通常是困难的。为了避开这个障碍，可以假设这样一个函数:
即xi与xj在特征空间的内积等于他们原始样本空间通过函数k(. , .)计算的结果。有了这样的函数，我们就不必直接计算高维甚至无穷维特征空间中的内积。这里的函数k(. , .)就是“核函数”（kernel function）。
“核函数选择”是支持向量机的最大变数。常用的核函数有:
此外，还可以通过函数的组合得到。
核函数的选择是支持向量机的最大变数。这方面有一些基本的经验。如文本分类通常采用线性核，情况不明时可先尝试高斯核。
补充：核函数的本质
简要概括下，即以下三点：
- 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去(映射到高维空间后，相关特征便被分开了，也就达到了分类的目的)；
- 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(如19维乃至无穷维的例子)。那咋办呢？
- 此时，核函数就隆重登场了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就避免了直接在高维空间中的复杂计算。
举例说明下核函数解决非线性问题的直观效果$ ^{3}$。
假设现在你是一个农场主，圈养了一批羊群，但为预防狼群袭击羊群，你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢？你很可能需要依据牛群和狼群的位置建立一个“分类器”，比较下图这几种不同的分类器，我们可以看到SVM完成了一个很完美的解决方案。
（四）软间隔与正则化
在前面的讨论中，我们一直假定训练样本在训练空间或特征空间中是线性可分的，即存在一个超平面将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。
缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此引入了“软间隔”（soft margin）的概念，如下图所示：
具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束，即所有样本必须划分正确，这称为“硬间隔”（hard margin），而软间隔则是允许这样的样本不满足约束。
原来的约束条件为：
现在考虑到outlier（偏离正常位置很远的数据点）问题，约束条件变成了：
其中$\xi_i \geq 0$ 称为松弛变量 (slack variable) ，对应数据点$x_i$允许偏离的 functional margin 的量。
所以，我们在原来的目标函数$\text{min} \frac 12 ||w||^2 $后面加上一项，使得这些$\xi_i $的总和也要最小：
$$\text{min} \frac 12 ||w||^2+ C \sum^{n}_{i=1} \xi_i $$
其中C是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。
完整的目标函数为：
三种常用的替代损失函数(surrogate loss)：
- hinge损失: $l_{hinge}(z) = max(1, 1-z)$
- 指数损失(exponential loss)：$l_{exp}(z) = exp(-z)$
- 对率损失(logistic losss)：$l_{log}(z) = log(1+exp(-z))$
至此可以做个小结，不准确的说，SVM它本质上即是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子a的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求a等价，而a的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。
（五）支持向量回归
对样本（x，y），传统回归模型通常直接基于模型输出f(x)与真实输出y之间的差别来计算损失，当切仅当f(x)与y完全相同时，损失才为零。于此不同，支持向量回归（Support Vector Regression，简称SVR）假设我们能容忍f(x)与y之间最多有ε的偏差，即仅当f(x)与y之间的差别绝对值大于ε时才计算损失。如下图所示，
（六）核方法
根据“表示定理”，对于一般的损失函数和正则化项（不要求是凸函数），优化问题的最优解都可表示为核函数的线性组合。这显示出核函数的巨大威力。
人们发展出一系列基于核函数的学习方法，统称为“核方法”（kernel methods）。最常见的，是通过“核化”（即引入核函数）来将线性学习器拓展为非线性学习器。
