间隔与支持向量

对于给定训练样本集$D = {( \boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m)}$，分类学习最基本的想法就是基于训练集$D$在样本空间中找到一个划分超平面将不同类别的样本分开。

但是实际上存在多种划分方式，如图所示，理论上来说正中间红色的划分超平面是最好的，因为对训练样本的局部扰动容忍性最好，对未见示例的泛化能力最强。

一个超平面可以表示为：

$$\boldsymbol{w}^T\boldsymbol{x}+b=0$$

其中$\boldsymbol{w}$决定了平面的方向，而$b$决定了平面与原点之间的距离。空间中任意点$\boldsymbol{x}$实际上是一个向量，其到超平面的距离(这里还去补了一下点到面的距离公式)为：

$$r=\frac{\boldsymbol{w}^T\boldsymbol{x}+b}{\left | \left |w \right | \right |} $$

那么，如果这个超平面分类成功，我们令

$$\boldsymbol{w}^T\boldsymbol{x}+b≥+1, yi=+1$$

$$\boldsymbol{w}^T\boldsymbol{x}+b≤−1, yi=−1$$

这样，那些使等号成立的点，也即距离超平面最近的点称作支持向量 (support vector)，两个类到超平面距离之和也即两类之间的间隔 (margin) 是

$$\gamma=\frac{2}{\left | \left |w \right | \right |}$$

如图所示

对偶问题

基本SVM的优化目标本身是一个凸二次规划问题，可以利用优化计算包求解，但是据说拉格朗日有更高效的解法：

对上一节最后式子使用拉格朗日乘子法就可以得到它的对偶问题（dual problem），对偶问题出现在线性规划中，每一个求极小的线性规划问题都有一个求极大的线性规划问题互称对偶问题，解决了一个就对应解决了其对偶问题。具体到这里，对式子的每条约束添加非负拉格朗日乘子$\alpha_i$，拉格朗日函数是

其中涉及的详细推导过程，可见该链接

这又是一个二次规划问题，但通用解法规模正比于样本数，在大规模数据上开销很大，可以考虑其它高效算法如SMO (Sequential Minimal Optimization)。SMO的简单描述是其不断重复以下两个步骤直至收敛：

选取一对需更新的变量$\alpha_i$和$\alpha_j$
固定$\alpha_i$和$\alpha_j$以外的参数，求解对偶问题更新后的$\alpha_i$和$\alpha_j$。

SMO算法在一时间也不能得到完整的理解，希望能作为学习二次规划问题的一个复杂例子在之后研究。

核函数

为了保证我们寻找的划分超平面存在，我们要求样本在空间中是线性可分的。如果非线性可分，那么就需要将问题映射到一个更高维的特征空间去。理论证明，若原始空间是有限维的，那么一定存在一个高维特征空间使样本线性可分。

取映射函数$\phi$，特征空间划分超平面模型表示为：

称作核函数 (kernal function)。有定理表明：只要一个对称函数对应的核矩阵半正定，它就能作为核函数使用。几种常用的核函数有：

如何选择核函数将样本映射到真正显示其分布规律的高维空间非常重要。

软间隔与正则化

实际上很多问题并不能简单地归结为线性可分线性不可分，一些问题的样本空间看来是线性可分的，但总有几个样本跑到了敌对阵营，就为此强行线性可分就可能出现过拟合的情况。于是引入了软间隔 (soft margin)：允许有若干个样本被线性空间划分错误。前文中要求所有样本均满足约束的情况称为硬间隔。

软间隔时允许某些样本不满足约束$$y_i(\boldsymbol{w}^T\boldsymbol{x_i}+b)\geq 1$$

此时的优化目标变为：

其中$C$是一个常数，可以理解问允许多少个样本被分错，而$ℓ0/1$是0/1损失函数，当样本被分错时，它的取值为1，否则为0。这个函数直观，简单，然而非凸，非连续，常用一些替代函数：

hinge损失：$ℓhinge(z)=max(0,1,1−z)$
指数损失 (exponential loss)：$ℓexp(z)=exp(−z)$
对率损失 (logistic loss)：$ℓlog(z)=log(1+exp(−z))$

其中hinge损失比较常用。

代入优化目标后同样可以找到它们的对偶问题进行求解。实际上此时的优化目标可以看作两部分：第一项描述划分超平面的间隔大小，第二项描述数据集上的误差。对于误差还有更一般的形式：

其中$Ω(f)$称为结构风险(structural risk)，用于描述f的某些性质；后一项称为经验风险(emprircal risk)，用于描述模型与训练数据的契合程度；$C$用于对二者进行折中。结构风险方便引入领域知识和用户意图：用户希望得到何种性质的模型，同时它也有助于削减假设空间。这个式子称为正则化 (regularization)。

支持向量回归

普通的回归问题计算损失为函数预测值与真实值的差，而使用支持向量回归 (Support Vector Regression, SVR)，我们容忍ϵ的误差，那就相当于在预测函数两端建立了一个宽为$2ϵ$的隔离带，在此间隔带种的样本被默认为预测正确，而在此间隔带外的样本计算它的真实值与预测函数得到值的差作为损失，就此SVR问题可形式化为：

同样可通过拉格朗日乘子法解出。

若考虑特征向高维映射，也可引入核函数。

核方法

根据数学推导，在给定训练样本，不考虑偏移项$b$的情况下，SVM和SVR问题学得的模型总可以表示成核函数的线性组合，由“表示定理”保证。由此人们发展了一系列基于核函数的学习方法，统称为核方法 (kernel methods)。最常见的就是引入核函数来将线性学习器拓展为非线性学习器，从而得到核线性判别分析 (Kernelized Linear Discriminant Analysis)。

核函数直接决定了支持向量机与核方法的最终性能，但遗憾的是，核函数的选择是一个未决问题，多核学习（multiple kernel learning）借助集成学习机制，使用多个核函数并通过学习获得其最优化凸组合作为最终的核函数。