1. 线性可分 ( Linear Separable )

用数学严格定义训练样本以及他们的标签 假设：我们有N个训练样本和他们的标签： 其中

1.1 用数学严格的定义线性可分

线性可分的严格定义：一个训练样本集，在 i=1~N 线性可分，是指存在,使得对 i=1~N ,有: (1) 若 = +1 ，则 (2) 若 = -1，则

1.2 用向量的形式定义线性可分

假设：

(1) 若 = +1 ，则 (2) 若 = -1，则

简化：

如果一个数据集是线性可分的，那么将存在无穷多个超平面，将各个类别分开。 支持向量机算法： 1. 解决线性可分问题; 2. 再将线性可分问题中获得的结论推广到线性不可分情况

支持向量机要找的是使得间隔（ Margin ）最大的那条直线，且这条线是在两条平行线的中间。

支持向量机寻找的最优分类直线应满足: (1) 该直线分开了两类; (2) 该直线最大化间隔(margin) (3) 该直线处于间隔的中间，到所有支持向量，距离相等

1.3 如何寻找最大化间隔？

假定训练样本集是线性可分的：支持向量机需要寻找的是最大化间隔(MARGIN)，特征空间维度>=四维时，分割将会变成超平面（Hyperplane）。

1.3.1 最小化(Minimize) :

事实1：

事实2：

相当于

支持向量机优化问题推导中最难理解的部分用 a 去缩放 、b：

( ，b) 表示的超平面和 (a，ab) 表示的超平面是同一个平面

根据事实2有：

因此，最大化支持向量到超平面的距离等价于最小化

1.3.2 限制条件 :

1.3.3 凸优化问题

二次规划的定义: （1）目标函数 (Objective Function)是二次项。 （2）限制条件是一次项。

凸优化问题要么无解，要么只有一个全局的极值解。

（注：可以了解模拟退火算法）

2. 线性不可分 ( Nonlinear Separable )

2.1 再线性可分的基础上添加松弛变量

放松限制条件的基本思路：对每个训练样本及标签，设置松弛变量 (slack variable)

限制条件改写：

比例因子 C ：人为设定，起到平衡两项的作用。

人为事先设定的参数叫做算法的超参数(HYPER PARAMETER)

我们需要不断变化C的值，同时测试算法的识别率，从而选取超参数C 。

支持向量机是超参数很少的模型。

2.2 扩大函数范围，提高非线性的处理能力

特征空间从低纬度映射到高纬度，在高纬特征空间中仍然用线性超平面对数据进行分类。

构造低纬到高纬的映射 ，能把线性可分的数据集变为线性不可分的数据集。

假设在一个M维空间上随机取N个训练样本，随机的对每个训练样本赋予标签+1或-1。假设这些训练样本线性可分的概率为P(M)，当M趋于无穷大的时候，P(M) = 1。

当特征空间的维度增加时，待估计参数 ( ，b) 的维度也会增加。整个算法的模型自由度也会增加。