支持向量机

模型从简单到复杂:

学习算法：序列最小最优化算法(SMO)

线性可分，线性不可分

线性可分，硬间隔，拉格朗日算子
不可分，软间隔，hinge损失函数

线性可分支持向量机

flowchart
max_gap(间隔最大化)
min_w(最小化法向量模)
raw_prob(原问题,凸优化问题)
dual_prob(对偶问题)

max_gap --> min_w
min_w --> raw_prob
raw_prob --> |拉格朗日乘子| dual_prob

数据集定义：，其中，+1时为正例，-1时为负例

线性可分：即可以在特征空间找到一个超平面使得正负样本分别在两侧

训练集线性可分时，一般会有无穷多个超平面可以分离正负类。感知机利用误差分类最小策略，有无穷多解。线性可分支持向量机利用间隔最大化求分离超平面，只有唯一解。

模型：超平面以及决策函数，称为支持向量机

函数间隔：样本点的函数间隔为，超平面关于训练集的函数间隔为:

几何间隔：需要对法向量加上约束，否则函数间隔不确定，超平面可以成倍，一般为，即，超平面几何间隔即为

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

支持向量机学习的基本想法是求解间隔最大的超平面。

即转换为以上约束最优化问题，进一步考虑几何间隔和函数间隔关系，转化为函数间隔可化为

由于函数间隔取值并不影响解，令，并且最大化和最小化等价，因此转化为，即原始问题

线性可分训练数据集的最大间隔分离超平面是存在且唯一的

在线性可分的情况下，训练基本中离分离超平面最近的样本点称为支持向量，既满足以下约束条件的点

对于的正例点，在超平面

对于的负例点，在超平面

被称为间隔边界，两者平行，且之间的距离被称为间隔，间隔依赖于分离超平面法向量，等于

首先构建拉格朗日函数，对每一个不等式约束引入拉格朗日乘子，定义拉格朗日函数为:

其中为拉格朗日乘子向量。

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

(1)求

对求偏导令其等于0

得

将两式中第一式带入式，并利用第二式化简可得

即

(2)求，即

将上式从极大转为极小，即可得

求解次优化问题可得对偶问题的解

易得下列KKT条件成立，KKT条件是原问题解等于对偶问题解的必要条件

即对于不在间隔边界上的点，支持向量的

flowchart
data(线性不可分训练集)
convex_prob(原问题,凸优化)
dual_prob(对偶问题)

data --> |最大化软间隔| convex_prob
convex_prob --> dual_prob

线性不可分即意味着不能存在一个间隔使得超平面分割样本，即不在对所有成立，因此对每个样本点引入一个松弛变量，使得函数间隔加上松弛变量大于1，即

同时对每个松弛变量，添加一个代价，使目标函数从原来的变为

因此线性不可分的线性支持向量机的学习问题变成如下的凸二次规划问题（原始问题）：

对于线性不可分的训练数据集，通过求解以上的凸二次规划问题，即软间隔最大化问题，得到分离超平面以及相应的分类决策函数称为线性支持向量机

通过和线性可分支持向量机一样的思路，可将原始问题转换为对偶问题

推理过程如下

原始最优化问题的拉格朗日函数为

最大最小问题即：

求导并代入可得最小问题:

所以转化为:

KKT条件：

利用上述条件，使用等式消去，从而只剩下，再将目标函数由求极大转为极小，即得到对偶问题

同线性可分一样，将对偶问题解中大于0的样本点称为支持向量，右下图所示，即在间隔边界另一侧的向量，若则支持向量在间隔边界上，若则分类正确，样本点在间隔边界和分离超平面之间，若则样本点在分离超平面上，若则样本点位于分离超平面误分一侧

上面为最大化软间隔思路，线性支持向量机还有另一种解释，最小化一下目标函数

其中第一项为经验损失或经验风险，也称为Hinge loss，所谓经验，即是从样本中计算得来

最大化软间隔问题，等价于

令，则成立，同时令，则可化为最大软间隔问题

令是输入空间(或者离散集合)，为特征空间(希尔伯特空间，即带卷积运算的空间)，如果存在一个映射：,对于所有，函数满足条件,则称为核函数

将核函数代入对偶问题中，则目标函数成为

同时分类决策函数成为

设,是定义在上的对称函数，如果对任意对应的Gram矩阵

是半正定矩阵，则称是正定核

1.多项式核函数

分类决策函数为

2.高斯核函数

分类决策函数为

核心是将问题拆解为迭代的二次规划，包括两个部分：求解两个变量的二次规划的解析方法和选择变量的启发式方法

待补充