支持向量机（SVM）

二类分类模型。它的基本模型是定义在特征空间上的最大间隔的线性分类器，间隔最大使它有别于感知机。

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

支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。

支持向量机的学习算法是求解凸二次规划的最优算法。

分类：

• 线性可分支持向量机
  硬间隔最大化
• 线性支持向量机
  训练数据近似线性可分时，通过软间隔最大化
• 非线性支持向量机
  当训练数据线性不可分是，通过使用核技巧及软间隔最大化

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积；
通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机，这样的方法称为核技巧
核方法是比支持向量机更为一般的机器学习方法。

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

1、线性可分支持向量机

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

假设特征空间上的训练数据集

image.png
正例，负例
学习目标：找到分类超平面

线性可分支持向量机：

image.png image.png

2、函数间隔和几何间隔

（1）函数间隔

点到分离超平面的远近|w·x+b|：表示分类预测的确信程度
w·x+b的符号与类标记y的符号是否一致：表示分类是否正确
所以，可用量y(w·x+b)表示分类的正确性和确信度。

image.png

（2）几何间隔

当成比例改变w和b,例如将他们改为2w和2b，超平面并没有改变，但函数间隔却成为原来的2倍。说明，可以对分离超平面的法向量w加某些约束，如规范化，||w||=1,使得间隔是确定的。这是函数间隔成为几何间隔

image.png
image.png

3、间隔最大化

（1）最大间隔分离超平面

image.png
考虑几何间隔和函数间隔的关系，改写
image.png
考虑：
image.png
线性可分支持向量机学习的最优化问题（这是一个凸二次规划问题）
image.png

凸优化问题是指约束最优化问题

image.png

线性可分支持向量机学习算法---最大间隔法

image.png

（2）最大间隔分离超平面的存在唯一性

image.png

（3）支持向量机和间隔边界

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

image.png image.png

4、学习的对偶算法

对于线性可分支持向量机的优化问题，原始问题：

image.png

应用拉格朗日对偶性，通过求解对偶问题，得到原始问题的解。
优点：对偶问题往往容易解；引入核函数，推广到非线性分类问题。

定义拉格朗日函数

image.png

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

image.png

得到对偶问题的解：
先求L(w,b,α)对w,b的极小值，再求对α的极大

image.png
image.png

定理：

image.png
由定理可知，分离超平面可以写成
image.png

分类决策函数可以写成

image.png
称为线性可分支持向量机的对偶形式

线性可分支持向量机学习算法

image.png

支持向量：

image.png

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

1、线性支持向量机

训练数据中有些特异点，不能满足函数间隔大于等于1的约束条件。
解决方法：

image.png

使得函数结果加上松弛变量大于等于1，约束条件变为：

image.png

目标函数变为：

image.png

C>0为惩罚参数

线性不可分的线性支持向量机的学习问题：

image.png

线性支持向量机的定义

image.png

2、学习的对偶算法

image.png
对偶问题是拉格朗日函数的极大极小问题
image.png image.png

定理：

image.png

线性支持向量机学习算法

image.png

3、支持向量

image.png

4、合页损失函数

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：

image.png

目标函数第一项是经验损失或者经验风险，函数

image.png
称为合页损失函数。
image.png

定理：线性支持向量机原始最优化问题

image.png
image.png

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

1、核技巧

（1）非线性分类问题

非线性可分问题

image.png

通过非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

image.png

用线性分类方法求解非线性分类问题分两步：

• 首先使用一个变换将原空间的数据映射到新空间；
• 然后在新空间里用线性分类学习方法从训练数据中学习分类模型。

核技巧就属于这样的方法
** 核技巧应用到支持向量机基本想法**：

image.png

（2）核函数的定义

image.png
核技巧的想法：
image.png

（3）核技巧在支持向量机中的应用

注意到：
线性支持向量机对偶问题中，无论是目标函数还是决策函数都只涉及输入实例和实例之间的内积

image.png

2、正定核

问题：

image.png image.png

（1）定义映射，构成向量空间S

image.png

（2）在S上定义内积，使其成为内积空间

image.png

（3）将内积空间S完备化为希尔伯特空间

image.png

（4）正定核的充要条件

image.png

正定核的等价定义：

image.png

3、常用核函数

image.png
image.png

4、非线性支持向量机学习算法

image.png image.png

四、序列最小最优化算法SMO
SMO解如下凸二次规划的对偶问题

image.png

启发式算法，基本思路：

image.png

SMO算法包括两个部分：

• 求解两个变量二层规划的解析方法
• 选择变量的启发式方法

1、两个变量二次规划的求解方法

image.png image.png image.png

求解过程：

image.png image.png

2、变量的选择方法

SMO算法在每个子问题选择两个变量优化，其中至少一个变量是违反KKT条件的
（1）第一个变量的选择：外循环

image.png

（2）第二个变量的选择：内循环

image.png

（3）计算阈值b和差值Ei
每次完成两个变量的优化后，重新计算阈值b和差值Ei

image.png

3、SMO算法

image.png