【机器学习 02】支持向量机

目录

1. 线性可分 ( Linear Separable )

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

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

1.3 如何寻找最大化间隔?

2. 线性不可分 ( Nonlinear Separable )

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

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


1. 线性可分 ( Linear Separable )

【机器学习 02】支持向量机_第1张图片

用数学严格定义训练样本以及他们的标签
假设:我们有N个训练样本和他们的标签:
\small \left \{ (X_1, y_1),(X_2, y_2),..,(X_N,y_N) \right \}
其中
\small X_i = [x_i_1,x_i_2]^T
\small y_i = \left \{ +1,-1 \right \}
 

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

        线性可分的严格定义:一个训练样本集\small \left \{ (X_1, y_1),(X_2, y_2),..,(X_N,y_N) \right \},在 i=1~N 线性可分,是指存在\small (\omega _1,\omega _2,b),使得对 i=1~N ,有:
(1) 若 \small y_i = +1 ,则 \small \omega _1x_i_1+ \omega _2x_i_2 + b > 0
(2) 若 \small y_i = -1,则 \small \omega _1x_i_1+ \omega _2x_i_2 + b < 0

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

        假设: X_i = [x_i_1,x_i_2]  \omega = [\omega _1,\omega _2]

(1) 若 \small y_i = +1 ,则 \small \omega ^TX_i + b > 0
(2) 若 \small y_i = -1,则 \small \omega ^TX_i + b < 0

 简化:y_i( \small \omega ^TX_i ) + b > 0

如果一个数据集是线性可分的,那么将存在无穷多个超平面,将各个类别分开。

支持向量机算法:
1. 解决线性可分问题;
2. 再将线性可分问题中获得的结论推广到线性不可分情况

 支持向量机要找的是使得间隔( Margin )最大的那条直线,且这条线是在两条平行线的中间。【机器学习 02】支持向量机_第2张图片

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

1.3 如何寻找最大化间隔?

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

1.3.1 最小化(Minimize) : \small \frac{1}{2}\left \|\omega \right \|^2

【机器学习 02】支持向量机_第3张图片


 事实1:

【机器学习 02】支持向量机_第4张图片

 事实2:

【机器学习 02】支持向量机_第5张图片

 相当于

【机器学习 02】支持向量机_第6张图片

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

【机器学习 02】支持向量机_第7张图片

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

 根据事实2有: 

【机器学习 02】支持向量机_第8张图片

 因此,最大化支持向量到超平面的距离等价于最小化 \small\left \|\omega \right \| 

 1.3.2 限制条件 : y_i( \small \omega ^TX_i + b ) \geq 1 \left (i= 1\sim N \right ) 

【机器学习 02】支持向量机_第9张图片

  1.3.3 凸优化问题

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

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

(注:可以了解模拟退火算法)

2. 线性不可分 ( Nonlinear Separable )

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

放松限制条件的基本思路:对每个训练样本及标签(X_i,Y_i),设置松弛变量 \delta _i (slack variable)

限制条件改写:y_i( \small \omega ^TX_i + b ) \geq 1 - \delta _i \left (i= 1\sim N \right )

 【机器学习 02】支持向量机_第10张图片

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

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

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

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

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

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

构造低纬到高纬的映射 \varphi \left ( x \right ) ,能把线性可分的数据集变为线性不可分的数据集。

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

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

【机器学习 02】支持向量机_第11张图片

你可能感兴趣的