SVM

一、支持向量机 SVM(Support Vector Machine)

SVM是一种二分类算法，旨在寻找最佳平面使得训练集上的正负样本间距最大。模型由简至繁可分为以下三种：

线性可分支持向量机（硬间隔支持向量机）：

线性支持向量机（软间隔支持向量机）：

非线性支持向量机：

二、线性可分支持向量机

1. 训练集线性可分，存在无数超平面可将两类数据正确分开，此时线性可分支持向量机利用间隔最大化求得最优分离超平面，此时最优解唯一

2. 定义

给定线性可分训练集，通过间隔最大化得到分离超平面

以及相应的分类决策函数

成为线性可分支持向量机

3. 分析

（1）设超平面为，其中为法向量，决定超平面的方向；b为位移项，决定超平面与原点直接的距离。那么，样本空间任意一点x到超平面的距离可写为

（2）假设超平面能将样本正确划分，即

为了使最后得到的分类器鲁棒性更强且便于计算，我们令

图形表示如下

由图可以清晰的看出，两个异类支持向量机到超平面的距离之和称为间隔，如下表示：

（3）要想最大化间隔，需要找满足约束条件的参数和b，同时使得最大，即

转化一下，变为

此为SVM的基本型

4. 求解上式

（1）引入拉格朗日函数

问题变为求解

对偶问题变为

（2）求

分别对w和b求偏导，可得

即

将上式代入拉格朗日函数中，可得

（3）求上式对于a的极大

上式可转化为

假设上式解为

（4）求解w及b

【定理】根据（3）中，存在下标j，使得，且可通过下式求得原始问题的解:

证明参考https://www.cnblogs.com/ooon/p/5721119.html

5. 线性可分支持向量机算法

输入：线性可分训练集，其中

输出：分离超平面和分类决策函数

（1）构造并求解约束最优化问题

求得最优解

（2）求

选择一个正分量，计算

（3）求得分离超平面

分类决策函数：

三、线性支持向量机

1. 当训练数据不满足线性可分的条件时，即训练数据中有一些特异点，将这些特异点去除后剩下大部分的样本点组成的集合是线性可分的

2. 为了解决上述问题，对每个样本点引入一个松弛变量，使函数间隔加上松弛变量大于等于1，约束条件变为

线性支持向量机变为如下凸二次规划问题：

类似的解法得到对偶问题

3. 线性支持向量机算法

输入：训练数据集，其中

输出：分离超平面和分类决策函数

（1）选择惩罚函数C>0，构造并求解凸二次规划问题

求得最优解

（2）计算

选择满足的分量，计算

（3）求得超平面

分类决策函数

四、非线性支持向量机

1. 场景

训练集线性不可分，利用核技巧将输入空间非线性问题转化到特征空间线性可分问题，如下图所示

2. 核函数

设ϕ(x)为输入空间到特征空间的映射函数，那么

称K(x,z)为核函数

3. 常用核函数

（1）多项式核函数

（2）高斯核函数

4. 非线性支持向量机算法

输入：训练数据集，其中

输出：分离超平面和分类决策函数

（1）选取合适的核函数K(x,z)和适当的参数C，构造并求解最优化问题

求得最优解

（2）选择一个正分量，计算

（3）构造决策函数