文章目录
  1. 1. 机器学习8—支持向量机(下)
    1. 1.1. 核函数
    2. 1.2. 核函数的判定
    3. 1.3. L1 norm 软间隔SVM
    4. 1.4. 第三种求解最优化的方法:坐标上升法
    5. 1.5. SMO优化算法
    6. 1.6. 总结

机器学习8—支持向量机(下)

上节回顾:从逻辑回归引出支持向量机—>定义函数间隔和几何间隔—>最优间隔分类器(通过最大化间隔,得到最优)—>引出拉格朗日对偶(作用:通过对偶将算法变得更高效;处理高维)—>将对偶用到最优间隔分类器
本节内容:核函数(升维)—>判定是否是有效的核函数—>L1 norm 软间隔SVM(针对不可分的情况)—>第三种求解最优化的方法:坐标上升法—>SMO优化算法(最快的二次规划优化算法)

核函数

1、定义

2、核函数的作用

a、低维映射到高维,从而更好的拟合;
b、将不可分的情况变为可分

3、举例:

例一:


说明:时间复杂度由
例二:
高斯核(把原始特征映射到无穷维):
映射后的优点:

4、映射后怎样进行预测

预测函数:
映射后:将
问题:怎样求取和判断核函数?下面将会介绍。

核函数的判定

1、符号说明

K:核函数矩阵$K={K{ij}} $ 第i,j个样本
$K
{ij}$ 或者$K(x^{(i)},x^{(j)}) $ :核函数$K_{ij}=K(x^{(i)},x^{(j)}) $

2、利用Mercer定理


简而言之,K是一个有效的核函数<—>核函数矩阵是对称半正定

L1 norm 软间隔SVM

当不可分时,利用L1 软间隔进行分离
1、 加入软间隔后的模型:

(1)凸规划

其中,C是离群点的权重(我们预定的,为已知数),越大表明对目标函数影响越大,也就是月不希望看到离群点。引入非负参数(称为松弛变量) , 就允许某些样本点的函数间隔小于1,即在最大间隔区间里面,或者函数间隔是负数,即样本点在对方的区域中。
(2)拉格朗日算子:

其中,
(3)推导结果
跟前面模型类似:先写出拉格朗日公式 (如上) ,然后将其看作是变量 w 和 b的函数,分别对其求偏导,得到 w 和 b 的表达式。然后代入公式中,求带入后公式的极大值。得到:

KTT条件:

第三种求解最优化的方法:坐标上升法

1、三种求解最优化的方法:

(1)梯度上升法(求解最小值问题时,称作梯度下降法)
(2)牛顿法(求解最值)
(3)坐标上升法(求解最小值问题时,称作坐标下降法)

2、假设求解下面问题:


其中,

3、算法过程:


SMO优化算法

最快的二次规划优化算法,特别针对线性 SVM 和数据稀疏时性能更优。
1、前面得到的结果

首先,先看前面的到的结果,如下图:

这个问题中:

按照坐标上升法的思路,只固定一个的话,由于限制条件中存在,将导致不再是变量。
因此,我们一次选取两个参数做优化。

2、SMO的主要步骤


注:第一步,利用启发式方法选取。第二步,固定其他参数,

3、 具体步骤

(1)固定除以外的参数,得:

(2)为了方便:

如下图:

其中,满足:
L和H的范围:

(3)将带入W中:

展开,得:

(4)这就是二次函数的最小值问题,容易求得(在纸上画图很容易看出来):

其中,为最终结果。为求导得到的结果。
同理,求得的最优解。

总结

1、本章的系统结构:

至此,我们得到:
预测问题只需要求解,即:

<—>上面的过程(SMO)求得的最优解
<—>
<—>
<—>
<—>
<—>(最大化几何间隔问题)

2、关于核问题(升维)的说明

核问题用来替换第一步中的部分:

文章目录
  1. 1. 机器学习8—支持向量机(下)
    1. 1.1. 核函数
    2. 1.2. 核函数的判定
    3. 1.3. L1 norm 软间隔SVM
    4. 1.4. 第三种求解最优化的方法:坐标上升法
    5. 1.5. SMO优化算法
    6. 1.6. 总结