《机器学习实战》之支持向量机（1）算法概述

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 2,371 | 阅读时长 ≈ 9

前言

  这两周把之前落下的公式推导恶补了一下，导致博客更新不及时。本系列博客涉及到的公式推导目前来看就两部分，一部分是logistic回归（最大熵问题也算在这里面了），一部分就是SVM（重头戏）。这两部分的公式我是都自己推导完了，但是还没整理成博客内容进行发布。我的博客都是先在小书匠上面做笔记，整理之后再发布的，但是由于公式推导部分之前全是手稿，码到小书匠上需要花费一定时间，加之最近项目催得紧，所以公式推导部分更新可能会滞后相当长的一段时间。但是，《机器学习实战》这本书的内容还是打算按照原计划进度更新下去。

  有人说，支持向量机（ Support Vector Machines， SVM ）是最好的现成分类器，这里所谓的“现成”指的是分类器不加修改即可直接使用。同时，这就意味着在数据上应用基本形式 SVM 分类器就可以得到低错误率的结果。 SVM 能够对训练集之外的数据点做出很好的分类决策。

  本篇博文主要讲述SVM的基本概念。

基于最大间隔分隔数据

支持向量机：

  • 优点：泛化错误率低，计算开销不大，结果易解释。
  • 缺点：对参数调节和核函数的选择敏感，原始分类器不加修饰仅适用于处理二分类问题。
  • 试用数据类型：数值型和标称型数据。

  在介绍SVM之前，先解释几个概念。来看看下面这堆数据，我们能否画出一条直线将圆形点和方形点分开？



  有点复杂？没关系，我们先来看看下图A中的两组数据，它们之间已经分隔得足够开，因此很容易就可以在图中画出一条直线将两组数据点分开。在这种情况下，这种数据被称为线性可分（ linearly separable ）数据。稍后当直线不能将数据点分开时，我们会对上述假设做一些修改。



  上述将数据集分隔开来的直线称为分隔超平面（ separating hyperplane ）。上面的数据是二维的，所以此时分隔超平面就萎缩成一条直线了。如果数据时1024维的，那么就需要一个1023维的某某对象来对数据进行分隔。这个1023维的某某对象被称为超平面（ hyperplane ），也就是分类的决策边界。分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别。

  我们再来看框B到框D中的三条直线，它们都能将数据分隔开，但是其中哪一个更好呢？是否应该最小化数据点到分隔超平面的平均距离来求最佳直线？如果是那样，是不是就意味着框B和框C就真的比框D中的直线好呢？有木有感觉有点寻找最佳拟合直线的感觉？是的，上述做法确实有点像直线拟合，但并非最佳方案。我们希望找到离分隔超平面最近的点，确保它们离分割面的距离尽可能远。这里点到分割面的距离被称为间隔（ margin ）。我们希望这个距离尽可能地大，这样鲁棒性比较好。

  支持向量（ support vector ）就是离分隔超平面最近的那些点。接下来要试着最大化支持向量到分隔面的距离，需要找到此问题的优化求解方法。

寻找最大间隔

  分隔超平面的形式可以携程$ w^Tx + b $。要计算点A到分隔超平面的距离，就必须给出点到分隔面的法线或垂线的长度，该值为$ |w^Tx + b| / \begin{Vmatrix} w \end{Vmatrix} $。这里的常数b类似于Logistic回归中的截距$w_0$。这里的向量w和常数b一起描述了所给数据的分隔线或超平面。接下来我们讨论分类器。



分类器求解的优化问题

  理解分类器工作原理将有助于理解基于优化问题的分类器求解过程。输入数据给分类器会输出一个类别标签，这相当于一个类似于Sigmoid的函数在作用。下面将使用类似单位阶跃函数对$ w^Tx + b $作用得到$ f(w^Tx + b) $，其中当u < 0时f(u)输出-1，反之输出+1。Logistic那里的类别标签是0或1。

  这里的类别标签之所以采用-1或+1，是因为它们仅仅相差一个符号，方便数学上的处理。我们可以通过一个统一公式来表示间隔或者数据点到分隔超平面的距离，而不必担心数据到底属于哪一类。间隔通过$ label · (w^Tx + b) $来计算，这时就能体现出-1和+1类的好处了。如果数据点处于正方向（+1类），并且离分隔超平面很远的位置时，$ w^Tx + b $会是一个很大的正数，同时$ label · (w^Tx + b) $也会是一个很大的正数；同理，当数据点处于负方向（-1类）并且离分隔超平面很远的位置时，$ label · (w^Tx + b) $仍然是一个很大的正数。

  现在的目标就是要找出分类器定义中的w和b。那么，我们就需要找到具有最小间隔的数据点（支持向量），然后对该间隔最大化。可以写作：

$$ arg max_{w,b}{min_n(label · (w^Tx + b)) · \frac{1}{\begin{Vmatrix} w \end{Vmatrix}}}$$

  直接求解上述问题相当困难呐，对乘积进行优化是一种很鸡肋的事情啊，因此我们要做的是固定其中一个因子而最大化其他因子。如果令所有支持向量的$ label · (w^Tx + b) $都为1，那么就可以通过求$ \begin{Vmatrix} w \end{Vmatrix}^{-1} $的最大值来得到最终解。但是，只有那些离分隔超平面最近的点得到的值才为1，而离超平面越远的数据点，其$ label · (w^Tx + b) $的值就越大。

  上述问题是一个带约束条件的最优化问题，这里的约束条件就是$ label · (w^Tx + b) \geq 1.0 $。对于这类优化问题，有一个非常著名的求解方法，即拉格朗日乘子法。这里的约束条件都是基于数据点的，因此我们可以将超平面写成数据点的形式。于是，优化目标函数最后可以写成：

$$ max\alpha[\sum^m{i=1}\alpha - \frac{1}{2} \sum^m_{i,j=1}label^{(i)}·label^{(j)}· \alpha_i·\alphaj \left\langle x{(i)},x_{(j)} \right\rangle ] $$

  其约束条件为：

$$ \alpha \geq 0, \sum^m_{i-1}\alpha_i·label^{(i)} = 0 $$

  一切都是那么完美，但是这里有个假设：数据必须100%线性可分。数据如果不干净了，我们就需要引入所谓的松弛变量（ slack variable ），来允许有些数据点可以处于分隔面的错误一侧。这样我们的优化目标就能保持仍然不变，但是约束条件更改为：

$$ C \geq \alpha \geq 0, \sum^m_{i-1}\alpha_i·label^{(i)} = 0 $$

  这里的常数C常用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0”这两个目标的权重。我们可以通过调节C来得到不同的结果。一旦求出了所有的alpha，那么分隔超平面就可以通过这些alpha来表达。这一结论非常直接，SVM中的主要工作就是求解这些alpha，从而求出w，然后利用$ w^Tx + b $来分类。

SVM应用的一般框架

  在kNN中，我们定义了构建机器学习应用的一般步骤，但是这些步骤会随着机器学习任务或算法的不同而有所改变，因此有必要在此探讨如何在本章中实现他们。

Logistic回归的一般过程：

  • 收集数据：采用任意方法收集数据。
  • 准备数据：需要数值型数据
  • 分析数据：有助于可视化分隔超平面。
  • 训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。
  • 测试算法：十分简单的计算过程就可以实现。
  • 使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二分类分类器，对多类问题应用SVM需要对代码做一些修改。

  到目前为止，我们已经了解了SVM相关的概念，我们当然希望能够通过编程，在数据集上将这些理论付诸实践。下一节将介绍一个简单而又强大的实现算法—序列最小优化（ Sequential MInimal Optimization，SMO ）算法。

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%