支持向量机学习笔记（二）

前言

在上一篇中，讲述了感知机是什么。接下来将叙述感知机的对偶形式，这在解决支持向量机问题中非常有用，因为直接求解存在困难时，我们往往会把它变换到其等价形式进行求解。这篇将继续上篇内容，把遗留的两个问题解释清楚。

感知机

感知机学习算法的对偶形式

现在考虑感知机学习算法的对偶形式。感知机学习算法的原始形式和对偶形式在支持向量机学习算法的原始形式和对偶形式相对应。

算法（感知学习算法的对偶形式）

支持向量机

支持向量机概念

书本《统计学习方法》定义为：支持向量机（support vector machine，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机（第一个特征来了！间隔最大化）；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。（第二个特征，解决线性不可分问题）。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优算法。

思考

1.间隔最大化，是什么东西？好抽象，看图秒懂。
2.核技巧？解决线性不可分问题？公式推导来，咱们立马给你推。
3.凸二次规划的问题，合页的损失函数最小问题。。。推荐《算法导论》中关于线性规划的章节，还不够，那就请看Convex Optimization Overview.

凸二次规划，可以这样理解，一个函数可以存在极值，但存在极值的函数在某一个局部的极值不一定是函数的极值，为什么要叫定义一个凸函数呢，因为凸函数的极值是唯一的，从局部求解出的极值问题就能代表该凸函数的极值。

支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case)、线性支持向量机（linear support vector machine)及非线性支持向量机（non-linear support vector machine)。简单模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化（hard margin maximization)，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization)，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧 (kernel trick)及软间隔最大化，学习非线性支持向量机。

本文呈现思路历程如下：叙述线性可分支持向量机，理解间隔最大化几何含义。线性支持向量机，区分硬间隔与软间隔。非线性支持向量，理解核函数推导由来。支持向量机对偶问题，理解对偶形式的求解。序列最小最优化SMO算法，带你进入凸二次规划算法中。

线性可分支持向量机与硬间隔最大化

硬间隔最大化

直接上图，感知机解决线性可分时，我们用的图为：

支持向量机解决线性可分问题时，我们用的图为：

两幅图对比中能够直观的看出支持向量机与感知机最大的区别，感知机只需要找到一条直线把两类数据进行分割即可，但支持向量机光找到这条直线还不够，它还需要在众多直线中找寻一条符合间隔最大化的直线，作为分割线。

看图易理解，但如果没有形式化的东西，往往很难针对支持向量机设计出有效的算法来对问题进行求解，我们必须借助数学工具来对这样的问题进行建模，回归书本，咱们来看看支持向量机对该直线是如何定义的。

假设给定一个特征空间上的训练数据集

函数间隔和几何间隔

继续看图：

继续看图：

间隔最大化

看图说话：