每天一个ml模型——支持向量机

该系列的宗旨为：少公式，简洁化，掌握核心思想，面向对机器学习感兴趣的朋友。

ps：主要源自李航《统计学习方法》以及周志华《机器学习》，水平所限，望大牛们批评指正。

支持向量机(support vector machines,SVM)：二类分类

模型特点：分离超平面，核技巧

模型类型：判别模型

学习策略：极小化正则化合页损失、软间隔最大化

学习的损失函数：合页损失

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

主要思想：svm的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使得它成为实质上的非线性分类器

1、前言介绍

1)当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机，又被称为硬间隔支持向量机

2)当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又被称为软间隔支持向量机

3)当训练数据线性不可分时，通过使用核技巧(kernel trick)及软间隔最大化，学习非线性支持向量机

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

2.1线性可分支持向量机

学习目标：在特征空间中找到一个分离超平面，能将实例分到不同的类.分离超平面对应于方程w • x +b = 0，该方程由法向量w和截距b决定，可用(w,b)来表示。

分类决策函数为： f(x) = sign(w*• x +b*)

二分类问题，圈表示正例，叉表示反例。用一个点距离超平面的远近来表示分类预测的确信程度，点A距分离超平面较远，若预测该点位正类，比较确信

2.2函数间隔与几何间隔

函数间隔：可以用w•x +b的符号与类标记y的符号是否一致能够表示分类是否正确，对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi,yi)的函数间隔为

函数间隔可以表示分类预测的正确性和确信度

几何间隔：对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi,yi)的几何间隔为

从上面两个式子可以看出

对分离超平面的法向量加上约束，使||w||为一个常数，可以使得间隔是固定的。

2.3间隔最大化

间隔最大化思想：以充分大的确信度对训练数据进行分类，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。

即求解

约束条件表示超平面(w,b)关于每个训练样本点的几何间隔至少是γ

线性可分支持向量机的最优解存在且唯一，位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。

2.4学习的对偶算法

为了求解线性可分支持向量机的最优化问题，可以将它作为原始最优化问题，通过求解对偶问题得到原始问题的最优解。

二次规划问题的对偶问题为：

通常，通过求解对偶问题学习线性可分支持向量机，即首先求解对偶问题的最优值α*，然后求最优值w*和b*，得到分离超平面和分类决策函数

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

3.1线性支持向量机

1).线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的。现实中训练数据是线性可分的情形较少，训练数据往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。

2).线性不可分意味着某些样本点(xi,yi)不能满足间隔大于等于1的约束条件。可以对每个样本点(xi,yi)引入一个松弛变量 ζi，使其“可分”，得到线性支持向量机学习的凸二次规划问题，则其最优化问题变成

其中C>0称为惩罚参数，一般由应用问题决定的，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。

3).线性支持向量机定义

对于给定的线性不可分的训练数据集，通过求解上式的凸二次规划问题，得到的分离超平面为

w*• x +b*=0

以及对应的分类决策函数为f(x) = sign(w*• x +b*)，称为线性支持向量机

线性可分支持向量机的解w*唯一，但b*不唯一

3.2学习的对偶算法

线性支持向量机的对偶学习算法，首先求解对偶问题得到最优解α*，然后求最优值w*和b*，得到分离超平面和分类决策函数

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

4.1核技巧

1).对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。

上图为非线性分类问题与核技巧示例，通过变换，将左图的椭圆变成右图的直线，将非线性分类问题变成了线性分类问题

2).核技巧的定义

设χ是输入空间，又设Η为特征空间，Η一般为高维的，如果存在一个χ到Η的映射

使得对所有x,z ∈χ，函数K(x,z)满足条件

则称K(x,z)为核函数

4.2非线性支持向量分类器

从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划，得到分类决策函数

K(x,z)为正定核函数

5、序列最小最优化算法(sequential minimal optimization,SMO)

背景：支持向量机的学习问题可以形式化求解凸二次规划问题，这样的凸二次规划问题具有全局最优价，并且有很多最优化算法可以求解这一问题。但是当训练样本容量很大的时候，这些算法往往变得会很低效，故提出了序列最小最优化(SMO)算法。

主要求解的凸二次规划的对偶问题：

变量是拉格朗日乘子，一个变量αi对应于一个样本点(xi,yi),变量的总数等于训练样本容量N

基本思路：不断将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。这样通过启发式的方法得到原二次规划问题的最优解

PS：最近有点小忙啊，事情有点多，，哈哈哈哈，尬笑一下。