统计学习方法读书笔记——第七章 支持向量机

支持向量机(support vector machines, SVM)是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。
间隔最大使它有别于感知机。
支持向量机还包括核技巧，这使它称为实质上的非线性分类器。

支持向量机学习方法 包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机、及非线性支持向量机。
训练数据线性可分时：硬间隔最大化，硬间隔支持向量机
近似线性可分时：软间隔最大化，软间隔支持向量机
线性不可分时：核技巧，非线性支持向量机

核技巧：

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

7.1.1 线性可分支持向量机

线性与非线性的区别：非线性支持向量机利用一个从输入空间到特征空间的非线性映射

训练数据：

训练目标：
找到一个分离超平面，将实例分到不同的类，且间隔最大化。

线性可分支持向量机的定义：

7.1.2 函数间隔和几何间隔

一般来说，一个点距离分离超平面的远近可以表示为分类预测的确信成都。

定义 函数间隔:

函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够，需要规范化，如，使得间隔是确定的。
这时函数间隔成为几何间隔。

几何间隔的定义：

超平面关于样本点的几何间隔一般是实例点到超平面的带符号的距离。

函数间隔和几何间隔的关系：

7.1.3 间隔最大化

支持向量机学习的基本思想：求解能够正确划分训练数据集并且几何间隔最大的分离超平面。线性可分=>硬间隔最大化。

间隔最大化的直观解释：以充分大的确信度对训练数据进行分类。不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样得到的超平面应该具有较好的泛化能力。

1. 最大间隔分离超平面
   
   函数间隔的取值并不影响最优化问题的解。这样就可以取，于是得到下面的线性可分支持向量机的最优化问题
   
   

凸优化问题的定义：

最大间隔法：

2. 最大间隔分离超平面的存在唯一性
   线性可分训练数据集的最大间隔分离超平面是存在且唯一的。
   证明：
   (1) 存在性：

   
   
   

   (2) 唯一性：

   
   

3. 支持向量和间隔边界

   
   
   
   

   支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

7.1.4 学习的对偶算法

应用拉格朗日对偶性，通过求解对偶问题，得到原始问题的最优解。
引入对偶算法的优点：
1.对偶问题往往更容易求解
2.自然引入核函数，进而推广到非线性分类问题

(1) 求

(2) 求对的极大，即是对偶问题

对于线性可分训练数据集，可以由求得原始最优化问题对的解，有如下定理：

线性可分支持向量机的对偶学习算法，先求解对偶问题的解，再求得原始问题的解，是线性可分支持向量机学习的基本算法：

支持向量：

7.2 线性支持向量机与软间隔最大化

7.2.1 线性支持向量机

线性可分问题的支持向量机学习方法对线性不可分的训练数据是不适用的。通常情况，训练数据中有一些特异点，这些特异点去除后，剩下大部分的样本点组成的集合是线性可分的。这就需要修改硬间隔最大化，使其成为软间隔最大化。

引进松弛变量

有了上面的思路，可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机学习问题。它称为软间隔最大化。

可以证明的解是唯一的，但的解不唯一，的解存在于一个区间

线性支持向量机：

线性支持向量机的定义：

7.2.2 学习的对偶算法

就定理形式叙述原始问题的最优解和对偶问题的最优解的关系：

综合前面的结果，有下面的算法：
线性支持向量机学习算法：

7.2.3 支持向量

7.2.4 合页损失函数

合页损失函数(hinge loss function)

定理：

合页损失函数的图像：

合页损失函数是0-1损失函数的上界，因为0-1损失函数不是连续可导的，直接优化比较困难，可以认为线性支持向量机是优化由0-1损失函数的上界（合页损失函数）构成的目标函数。
这时的上界损失函数又称为代理损失函数

7.3 非线性支持向量机与核函数

有时分类问题是非线性的，这时可以使用非线性支持向量机，其主要特点是利用核技巧(kernel trick)

7.3.1 核技巧

1. 非线性分类问题

   
   
   
   

   上面的例子说明：用线性分类方法求解非线性分类问题分为两步：1. 首先使用一个变换将原空间的数据映射到新空间；2.然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
   核技巧就属于这样的方法，基本思想：

   
   

2. 核函数的定义
   

   
   核技巧的想法是：在学习与预测中只定义核函数，而不显式地定义映射函数。
   
   核函数举例：
   

3. 核技巧在支持向量机中的应用
   注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。

   
   
   
   
   

7.3.2 正定核

不用构造映射能否直接判断一个给定的函数是不是核函数？
本节叙述正定核的充要条件。

1. 定义映射，构成向量空间
   
   
2. 在上定义内积，使其成为内积空间
   
3. 将内积空间完备化为希尔伯特空间
   
   

4. 正定核的充要条件

   
   

定义7.7正定核的等价定义：

7.3.3 常用的核函数

1. 多项式核函数

   
   

2. 高斯核函数

   
   

3. 字符串核函数

   
   

7.3.4 非线性支持向量分类机

如上所述，利用核技巧，可以将线性分类的学习方法应用到非线性分类问题中，只需将线性支持向量机对偶形式中的内积换成核函数。

下面叙述非线性支持向量机学习算法：

7.4 序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的凸二次规划问题具有全局最优解。但是当训练样本容量很大时，这些算法往往变得非常低效。所以如何高效地实现支持向量机学习就成为一个重要的问题。目前已提出很多快速实现方法，本节讲述序列最小最优化(sequential minimal optimization, SMO)算法。

SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。