目的

  • 二分类模型

原理

  • 像什么就是什么

  • 相似性度量，在支持向量机领地被称为“核函数”，通常被归为先验性。通过核函数，将相似的样本投射到邻近的空间。

  • 在支持向量机中，并不是所有将正面训练例子从负面训练例子分离出来的边界都是平等的。我们可以把边界想象成一条弯曲的蛇，边界的宽度表示这条蛇能有多肥。

  • 和低宽度的支持向量机相比，高宽度的就不太可能因为画了一条过于复杂的边界而过拟合。

  • 支持向量机选择的支持向量越少，就能更好地进行概括。预测支持向量机的误差率，最多就是支持向量的那部分例子。随着维度的上升，这部分也会上升，因此支持向量机无法幸免于维数灾难，但它们最能抵抗这个灾难。

  • 除了实践中的功绩，支持向量机还完全改变了许多机器学习中的传统观点。例如，它揭穿了“模型越简单就越准确”这个谎言，有时候，这个观点会被误以为是奥卡姆剃刀理论。相反，支持向量机可能有无限数量的参数，而且只要它有足够大的边际，就不会过拟合。

  • 支持向量机唯一最让人吃惊的属性就是，无论它形成多么弯曲的边界，那些边界也总是直线（或一般为超平面）。我们可以把支持向量机利用核函数、支持向量、权值来做的事情，看作将数据映射到更高维数的空间中，并在那个空间找到最大边际超平面。对于一些核函数来说，衍生空间有无限的维数，但支持向量机完全不会因此而受到困扰。超空间可能是过度区域，但支持向量机已经弄明白如何操纵它。

  • 在任何类比学习算法中，最重要的问题就是如何度量相似性。相似性函数控制的是学习算法如何从已知例子归纳出新的例子。我们将自己对问题域所了解的东西插入学习算法中，这就变成了类推学派对于休谟问题的回答。我们可以将类比学习应用到所有种类的物体中，而不仅仅是属性向量，只要我们有度量它们之间相似度的方法。

  • 类比学者最棒的技巧在于跨问题域来进行学习。利用构造映射，类比学者可以完成这件事。结构映射采用两种描述方法，发现了它们某些部分和关系的一致对应关系，然后基于这种对应关系，进一步将一个结构中的属性转移到另一个结构中。

  • 支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；

  • 支持向量机还包括核技巧，这使它成为实质上的非线性分类器。

  • 支持向量机的学习策略就是间隔最大化，可以形式化为一个求解凸二次规划（convex quadratic programming）的问题，支持向量机的学习算法是求解凸二次规划的最优化算法。

  • 支持向量机的分类
    • 当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；
    • 当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；
    • 当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

  • 考虑一个二分类问题，假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以，输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。

  • 一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。

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

    \[w^{*} * x + b^{*} =0\]

    以及相应的分类决策函数

    \[f(x) = sign(w^{*} * x + b^{*})\]

    称为线性可分支持向量机。

  • 一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面\(w*x+b=0\)确定的情况下，\(\mid w*x+b \mid\)能够相对地表示点x距离超平面的远近。而\(w*x+b\)的符号与类标记y的符号是否一致能够表示分类是否哦正确。所以可用量\(y(w*x+b)\)来表示分类的正确性及确信度，这就是函数间隔（functional margin）的概念。

  • 选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，例如将它们改为2w和2b，超平面并没有改变，但函数间隔却成为原来的2倍。这一事实启示我们，可以对分离超平面的法向量w加某些约束，如规范化，\(\|w\|=1\)，使得间隔是确定的。这时函数间隔成为几何间隔（geometric margin）。此时，

    \[r_i = y_i(\frac{w}{\|w\|}*x_i+\frac{b}{\|w\|})\]

  • 定义超平面(w,b)关于训练集数据T的几何间隔为超平面(w,b)关于T中所有样本点\((x_i, y_i)\)的几何间隔之最小值，即

    \[r = \min_{i=1,...,N}r_i\]

  • 间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类，也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

  • 最大间隔分离超平面，可以表示为下面的约束最优化问题：

    \[\max_{w,b} r\] \[s.t. y_i(\frac{w}{\|w\|}*x_i+\frac{b}{\|w\|}) >= r, i=1,2,...,N\]

    考虑几何间隔和函数间隔的关系，可将这个问题改写为

    \[\max_{w,b} \hat{r}\] \[s.t. y_i(w*x_i+b) >= \hat{r}, i=1,2,...,N\]

    函数间隔\(\hat{r}\)的取值并不影响最优化问题的解。事实上，假设将w和b按比例改变为λw和λb,这是函数间隔成为λ\(\hat{r}\)。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取\(\hat{r}=1\)，将\(\hat{r}=1\)代入上面的最优化问题，得到

    \[\min_{w,b} \frac{1}{2}\|w||^2\] \[s.t. y_i(w*x_i+b)-1 >= 0, i=1,2,...,N\]

    这是一个凸二次规划问题（convex quadratic programming）问题。

  • 定理：最大间隔分离超平面的存在唯一性。若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

  • 支持向量与间隔边界

    在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector），支持向量是使约束条件式等号成立的点，即

    \[y_i(w*x_i+b)-1 = 0\]

    对 \(y_i=+1\)的正例点，支持向量在超平面

    \[H_1 : w*x+b=1\]

    上，对于\(y_i=-1\)的负例点，支持向量在超平面

    \[H_2 : w*x+b=-1\]

    上。注意\(H_1\)与\(H_2\)平行，并且没有实例点落在它们中间。在\(H_1\)与\(H_2\)之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即\(H_1\)与\(H_2\)之间的距离称为间隔（margin）。间隔依赖于分离超平面的法向量w，等于\(\frac{2}{\|w\|}\)。\(H_1\)和\(H_2\)称为间隔边界。

  • 在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量机在确定分离超平面中起着决定性作用，所以将这种分类模型成为支持向量机，支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

  • 为了求解线性可分支持向量机的最优化问题，我们通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

  • \(x^*\)和\(\alpha^*,\beta^*\)分别是原始问题和对偶问题的解的充分必要条件是\(x^*,\alpha^*, \beta^*\)满足Karush-Kuhn-Tucker（KKT）条件。

实现

相关算法

最近邻算法

感知机

应用SVM的文章

LI, Bin, Daqing ZHANG, Lin SUN, Chao CHEN, Shijian LI, Guande QI, and Qiang YANG. “Hunting or Waiting ? Discovering Passenger- Finding Strategies from a Large-Scale Real-World Taxi Dataset.” IEEE International Workshop on Managing Ubiquitous Communications and Services, no. August (2011): 63–68. doi:10.1109/PERCOMW.2011.5766967. (SVM用于特征选取)

参考文献

  1. 终极算法：机器学习和人工智能如何重塑世界 佩德罗·多明戈斯 第七章 类推学派：像什么就是什么
  2. 统计学习方法 李航 第7章 支持向量机
  3. Pattern Recognition And Machine Learning Bishop Section 7 Sparse Kernel Machines
  4. 关于SVM数学细节逻辑的个人理解（二）：从基本形式转化为对偶问题