这周的论文笔记是『A Tutorial on Support Vector Machines for Pattern Recognition』，说是这周，其实是贪心导师一个月前步骤的作业了(捂脸ing)，由于双十一前后公司各种上线，导致每天只能看看录播课程，不过接下来到年前应该都有时间，所以赶紧充（装）实（bi）起来！

摘要

关于这篇论文，堪称SVM最佳，而之所以最佳，在于它不同于一般论文直接从SVM概念入手，开篇即谈分类模型，而是先从VC维和结构风险化概述开始，通过这两个概念来阐述用于可分离和不可分离数据的线性支持向量机（SVMs），接下来通过一个机械类比（将两个或两类性质根本不同、仅有某些表面相似的对象进行类比的逻辑错误），讨论SVM在何时会是全局唯一解。然后讲解如何进行支持向量训练。再然后最重要的来了，详细的讨论了用于构造数据中非线性支持向量机解的核映射技术，后面还介绍SVMs如何支持超高VC维（甚至是无穷维），通过计算齐次多项式和高斯函数的VC维的径向基函数核等等。也正因此，支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础之上的。

简介

支持向量机（SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机也包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，即可转化成一个求解凸二次规划问题，亦可等价于一个正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

• 核函数

  当输入控件为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

• 核技巧

  通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。

• 核方法

  比支持向量机更为一般的机器学习方法。

• 结构风险最小化

  置信风险：分类器对未知样本进行分类，得到的误差

  经验风险：训练好的分类器，对训练样本重新分类得到的误差（即样本误差）。它是模型关于训练样本集的平均损失。当样本容量很大时，经验风险最小化能保证有很好的学习效果，比如：极大似然估计（MLE）就是经验风险最小化的例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就是等于极大似然估计。但当样本容量过小时，经验风险最小化学习的效果未必会很好，会产生过拟合现象。而结构风险最小化（Structural Risk Minimization, SRM）则是为了防止过拟合而提出的策略。

  结构风险：置信风险 + 经验风险

  结构风险最小化是为了防止过拟合而提出的一种策略，它等价于正则化。贝叶斯估计中最大后验概率估计就是结构风险最小化的一个例子。当模型的条件概率分布、损失函数是对数损失函数、模型复杂度由模型先验概率表示时，结构风险最小化等价于最大后验概率估计。监督学习问题变成经验风险或结构风险函数的最优化问题，这时经验风险或结构风险函数是最优化的目标函数。

• VC维

  将N个点进行分类，如分成两类（二维线性分类器），那么有$2^N$中分法。若存在这样一种假设H，它能准确的将$2^N$种问题进行分类。那么这些点的数量N，就是假设H的VC维，表示VC(H)。简单讲：只要存在N个样本能够被成功打散（Shatter），并且不存在N+1个样本能够被打散（随机划分类别）的话，就称这一函数集合的VC维是N。它反映一个模型（假设空间中的一个函数）的学习能力，VC维越大，则模型的容量越大。若H能够打散任意大小的集合，那么VC(H)为无穷大。

有关研究工作

SVM学习模型

Cortes与Vapnik提出非线性支持向量机，Boser、Cuyon与Vapnik又引入核技巧，提出非线性支持向量机。

线性可分支持向量机

线性可分支持向量机处理的是严格线性可分的数据集

给定线性可分训练集，通过间隔最大化或者等价地求解相应的凸二次规划问题学习得到的分离超平面为

  $w^{*}·x + b^{*} = 0$

以及相应的分类决策函数

  $f(x) = sign(w^{*}·x + b^{*})$

或者

  $f(x) = sign(\sum_{i=1}^{N} \alpha ^{*} y ^{*}< x_i, x > + b ^{*})$

称为线性可分支持向量机

其学习的优化问题如下：

    $\min_{w,b}$  $\frac{1}{2}\left | w \right |^{2}$

 s.t.  $y_i(w·x_i) - 1 \geq 0，i = 1,2,…,N$

线性支持向量机

线性支持向量机处理的是线性不可分的数据集。对于线性支持向量机的优化问题，就是在线性可分支持向量机的基础上加一个松弛变量。

其学习的优化问题如下：

    $\min_{w,b,\xi}$  $\frac{1}{2}\left | w \right |^{2} + C\sum_{i=1}^{N}\xi_i$

 s.t.  $y_i(w_i + b) \geq 1，i = 1,2,…,N$

    $\xi_i \geq 0，i = 1,2,…,N$

所求的分类超平面和决策函数与线性可分支持向量机相同

这里要简单介绍一下KKT条件（Karush-Kuhn-Tucker Conditions）和 拉格朗日乘子法，这个在SVM推导中需要用到

介绍之前，先了解一些定义（部分在周作业中证明过）

凸集定义： 欧式空间中，对于集合中的任意两点的连线，连线上任意一点都在集合中，那么这个集合就是凸集。
凸函数定义： 对于任意属于[0, 1]的 m 和 任意属于凸集上的两点$c_1$和$c_2$，有$f(mc_1 + (1-m)c_2) \leq mf(c_1) + (1-m)f(c_2)$，几何上的意义就是两点连线上的某点函数值，大于等于两点之间某点的函数值。凸函数上的任一局部最小点均是全局极小点。
半正定矩阵： 特征值大于等于0的实对称矩阵。
半正定矩阵的充要条件： 行列式（n阶顺序主子式）等于0，行列式的i阶顺序主子式 $\geq$ 0，i 从1到 n-1。
凸函数的充要条件： 如果f(x)在开凸集S上具有二阶连续偏导数，且f(x)的海森矩阵（二阶偏导矩阵）在S上处处半正定，则f(x)为S上的凸函数。

• 什么是KKT条件

  对于具有等式和不等式约束的一般优化问题

$$\left\{\begin{matrix} \min f(x) & 最值问题\\ s.t. g_j(x) \leq 0 (j = 1,2,3,...,m); & 不等式约束\\ h_k(x) = 0 (k = 1,2,3,...,l) & 等式约束 \end{matrix}\right.$$

  KKT条件给出了判断 $\mathbf{x}^{*}$是否为最优解的必要条件，即：

$$\left\{\begin{matrix} \frac{\partial f}{\partial x_i} + \sum_{j=1}^{m}\mu _j\frac{\partial g_i}{\partial x_i} + \sum_{k=1}^{l}\lambda _k \frac{\partial h_k}{\partial x_i} = 0\\ \\ h_k(x) = 0, (k = 1,2,3,...,l)\\ \\ \mu_jg_j(x) = 0, (j = 1,2,3,...,m)\\ \\ \mu_j \geq 0 \end{matrix}\right.$$

• 1、关于等式约束优化问题，这里其实就是拉格朗日乘子法
• 2、关于不等式优化问题，就是将不等式约束条件转换为等式约束条件（做法：引入松弛变量）

• 什么是拉格朗日乘子法

  简单点就是，一个无约束问题，加上一个被$\lambda$乘上的约束条件问题，当无约束问题的极值点梯度与约束条件问题的切线垂直，那么这个$\lambda$就是拉格朗日乘子。这样就将原来的无约束问题转换为在拉格朗日乘子处理之后的等式约束优化问题了。而对于不等式约束优化问题就交托给上面的KKT条件了。

非线性支持向量机

非线性支持向量机引入了核函数。

分类决策函数如下：

  $f(x) = sign(\sum_{i=1}^{N}\alpha ^{*} _i y_i \kappa (x_i, x) + b^ *)$

模式识别与机器学习的泛化性能边界

假设有$\varphi$个样本，每个样本包含如下一对数据$(x_i, y_i)$，其中，向量$\vec{x}_i \in R^n$，i=1，2，…，$\varphi$，$y_i$为给定的标签。

以树的识别问题来说，$\vec{x}_i$表示的是一个像素灰度值的向量，则 $y_i$ = 1（若图中有树）和 $y_i$ = -1（若图中无树）；

假设这些数据中存在未知的概率分布$P(\vec{x}, y)$，并且数据满足独立同分布（Independently Identically Distribution, IID）。【注】$P$代表累积概率分布，$p$代表密度分布。

这个假设相比于对每个$\vec{x}$给定一个标签$y$更加一般化：它允许对于给定的$\vec{x}$都有一个$y$的分布，在这种情况下，可靠源将会依照由$\vec{x}_i$而产生的固定分布对$y_i$进行赋值。即这将对每个给定的$\vec{x}$赋予一个固定的$y$。

现在假设我们有一个机器的任务：学习将$\vec{x}_i$映射到$y_i$上。这个机器实际上是通过一系列可能的映射$\vec{x}_i$ → $f(\vec{x}, \alpha)$来定义的。其中，函数$f(\vec{x}, \alpha)$通过可以调节的参数$\alpha$来标示的。$\alpha$的一个特别的选择生成了我们所谓的“训练机”。因此，一个有着固定的结构和确定权重偏量的神经网络被称为“学习机”。

 故一个训练机的测试误差的期望值如下：

    $R(\alpha) = \int \frac{1}{2}\left | y - f(\vec{x}, \alpha) \right |dP(\vec{x}, y)$

 当概率密度函数$p(\vec{x},y)$有值时，$dP(\vec{x}, y) = p(\vec{x}, y)\mathrm{d} x\mathrm{d} y$

    $R(\alpha)$被称为期望风险。

    $R_{emp}(\alpha)$则被称为经验风险：训练集测量的平均误差率（针对固定且有限的观测样本）

    $R_{emp}(\alpha) = \int \frac{1}{2\varphi}\sum_{i=1}^{\varphi}\left | y_i - f(\vec{x}, \alpha) \right |$

 $R_{emp}$是一个针对特定 $\alpha$ 的选择 和 一个特定训练集 $\{x_i, y_i\}$ 的固定数值。

 而$\frac{1}{2\varphi}\left | y_i - f(\vec{x}, \alpha) \right |$则被称为损失。对于此种情形，这里的损失只可以取值0和1。

 现在选择一些 $\eta$ 满足 $0\leq \eta\leq1$，对于选取这些值的损失，有概率 $1-\eta$，将会有如下所示边界：

    $R(\alpha) \leq R_{emp}(\alpha) + \sqrt{\frac{h(\log(\frac{2\varphi}{h} + 1)) - \log (\frac{\eta}{4})}{\varphi}}$

 其中，h是一个非负整数，即Vapnik Chervonenkis（VC）维数，上式右边称为“Risk Bound风险边界”，$\sqrt{\frac{h(\log(\frac{2\varphi}{h} + 1)) - \log (\frac{\eta}{4})}{\varphi}}$称为“VC置信”。

关于风险边界有三个特征：

• $P(\vec{x}, y)$的独立性；

• 计算左侧通常是不可能的；

• 如果我们知道VC维数，就可以很轻易的计算出右侧的值。

这样给定几个不同的学习机，选择一个固定的且相当小的 $\eta$ ，就可以选择能最小化右边式子的机器（函数），我们就可以给出实际风险最小边界的机器（函数）了。

支持向量机的VC维

在讲SVM的VC维之前，首先介绍一下影响置信风险的因素，这其中有：训练样本数目和分类函数的VC维。

因为训练样本数目，即样本越多，那么得到的误差又可以越小（置信风险就可以很小）；VC维越大，问题的解的种类就越多，推广泛化能力就越差，置信风险也就越大。因此增加样本数，降低VC维，才能降低置信风险。而一般的分类函数却需要提高VC维（即样本的特征数量），来降低经验风险，如多项式风雷函数。

结构风险最小化SRM就是同时兼顾经验风险和结构风险。在小样本情况下，能取得比较好的分类效果。保证分类精度（经验风险）的同时，降低学习机器的VC维。正因如此，SVM就是这样一种努力最小化结构风险的算法。

SVMs的泛化性能

这里引用一下维基百科介绍：在机器学习中，SVMs是具有相关学习算法的监督学习模型。它是用于分析分类和回归分析的数据的。而SVM的分类模型却可大致分成这四种：

• 最大边界分类器

• 使用核函数的分类器

• 软边缘分类器

• 软边缘 + 核函数分类器

可以发现，SVM既可以做线性分类，也可以做非线性分类，和线性回归等等，相较于逻辑回归、线性回归、决策树等模型，它的效果都是在它们之上的。

在sklearn中，是配有一个超参数C，来控制模型复杂度的。C越大，容忍度（泛化程度）越小，反之C越小，容忍度越高。而这个超参数C中，正是通过一个正则量，来控制SVM的泛化能力的，防止过拟合（一般使用grid search网格搜索，一种常用找最优超参数的算法）。

下面介绍SVM一些实现方法

LinearSVC

线性分类支持向量机，优点：简单 缺点：不支持核函数 复杂度：$O(m*n)$

最经典的就是手写体识别和鸢尾花识别

import numpy as np
from sklearn import datasets
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

iris = datasets.load_iris()
X = iris["data"][:,(2,3)]
y = (iris["target"]==2).astype(np.float64)
svm_clf = Pipeline((
    ("scaler",StandardScaler()),
    ("Linear_svc",LinearSVC(C=1,loss="hinge")),
    ))
svm_clf.fit(X,y)
print(svm_clf.predit([[5.5,1.7]]))

对于非线性数据的分类

无非两种处理方法：构造高维特征 和 构造相似度特征

• 使用高维空间特征：即映射高维空间上，利用Kernel思想

from sklearn.preprocessing import PolynomialFeatures
polynomial_svm_clf = Pipeline((
     ("poly_features", PolynomialFeatures(degree=3)),
     ("scaler", StandardScaler()),
     ("svm_clf", LinearSVC(C=10, loss="hinge"))
   ))
polynomial_svm_clf.fit(X, y)

这种核技巧可以极大地简化模型，不需要显式的处理高维特征，并且可以计算出较复杂的情况。但是模型越复杂，过拟合风险就越大，泛化性能就越差。

这里使用SVC（基于libsvm库，支持核函数，但是缺点是不能使用大规模数据，复杂度：$O(m^2*n) - O(m^3*n)$）

其中coef0参数表示：高次与低次权重

from sklearn.svm import SVC
poly_kernel_svm_clf = Pipeline((
      ("scaler", StandardScaler()),
      ("svm_clf", SVC(kernel="poly", degree=3, coef0=1, C=5))
    ))
poly_kernel_svm_clf.fit(X, y)

• 构造相似度特征：计算高斯距离（Gaussian RBF Kernel径向基函数）

高斯距离定义：

Gaussian RBF等式
  $\phi \gamma (\mathbf{X},\iota )=exp(-\gamma \left || \mathbf{X},\iota |\right | ^2)$

$\gamma$是用来控制高斯曲线形状的，对于数据点之间的距离才会发挥它应有的作用。

rbf_kernel_svm_clf = Pipeline((
      ("scaler", StandardScaler()),
      ("svm_clf", SVC(kernel="rbf", gamma=5, C=0.001))
   ))
rbf_kernel_svm_clf.fit(X, y)

… …

这里真的还能细挖出好多好多知识点，后面学习sklean框架时再补上吧。

总结

要说SVM的这篇论文阐述的知识，确实可以称得上是“细致入微”，而SVM的优势就在于解决小样本、非线性、以及高维的回归和二分类问题。在与问题复杂度上，SVM要求的样本是相对较少的；而在样本数据线性不可分上，SVM也是比较擅长的，通过核函数和松弛变量来实现；即使在样本维度很高情况下，SVM依然保持着优势，它产生的分类器简洁，用到样本信息还少，几乎可以有效的避免过拟合问题。基于种种，接下来还是需要结合实战，再配备这篇教程，好好体验一下SVM的强大。