ML学习笔记(一)

SVM基础1

Posted by QIY on June 3, 2020

Machine Learning 的学习需稳扎稳打

1分类问题常用方法

2支持向量机概述(Support Vector Machine, SVM)

(百度百科)支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类(binary classification)的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane) [1-3] 。

SVM使用铰链损失函数(hinge loss)计算经验风险(empirical risk)并在求解系统中加入了正则化项以优化结构风险(structural risk),是一个具有稀疏性和稳健性的分类器 [2] 。SVM可以通过核方法(kernel method)进行非线性分类,是常见的核学习(kernel learning)方法之一 [4] 。

hyperplane(要找的超平面):有最大间隔的Large Margin 。

绿色的2个点,蓝色的3个点称谓Support Vectors 。

https://qqadapt.qpic.cn/txdocpic/0/a38446480f9acfbd4e5c59558ed7e56a/0

当数据不能线性分割时,可投放到高维空间分割。

3基础知识

SVM目前被认为是最好的现成的分类器,SVM整个原理的推导过程也很是复杂啊,其中涉及到很多概念,如:凸优化问题、拉格朗日乘子法、对偶问题,slater条件、KKT条件还有复杂的SMO算法!

3.1 凸优化

3.1.1 凸集

在点集拓扑学与欧几里得空间中,凸集是一个点集,其中每两点之间的直线上的点都落在该点集中。请看下图:

3.1.2 凸函数

一个定义在向量空间的凸子集C(区间)上的实值函数f,如果在其定义域C上的任意两点x,y以及t∈[0,1]有: 

这里写图片描述

则该函数为凸函数!凸函数另一个判别方式是:如果一个凸函数是一个二阶可微函数,则它的二阶导数是非负的。上图:

可以看出凸函数的二阶导非负;

3.1.3 凸优化

(百度百科)是指求取最小值的目标函数为凸函数的一类优化问题。其中,目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数,等式约束函数为仿射函数,并且定义域为凸集的优化问题为约束优化问题。

凸优化性质:

1、目的是求取目标函数的最小值;

2、目标函数和不等式约束函数都是凸函数,定义域是凸集;

3、若存在等式约束函数,则等式约束函数为仿射函数;

4、对于凸优化问题具有良好的性质,局部最优解便是全局最优解。

一个凸优化问题用公式描述为:

这里写图片描述

其目标函数f(x)

不等式约束条件g(x)便是凸函数

等式约束条件h(x)是仿射函数

仿射函数:即是deg(h(x))=1的函数,常数项为0的仿射函数称为线性函数。

其中符号 deg() 表示多项式h(x)的次数,即将函数看成多项式。

3.2 拉格朗日乘子法(考研必考题)

拉格朗日乘子法的作用:求函数f(x1,x2…)在g(x1,x2…)=0的约束条件下的极值。

1、定义新函数: 

这里写图片描述

2、利用偏导方式列出以下方程 

这里写图片描述

3、求解出x,y,σ的值带入F(x,y,σ)便是目标函数的极值。

3.3 对偶法

何为对偶?如下

maxminF(x)的对偶minxmaxF(x);

即:最小值的最大值 对偶为:最大值的最小值;

作用:最大值中最小的一个总比最小值中最大的那一个要大,也就是对偶问题提供了原问题最优值的一个下界

3.4 拉格朗日中的对偶应用

对于凸优化:

使用拉格朗日乘子法针对上面的最优化问题有: 

需要明确:其中α≥0、β任意,均为拉格朗日乘子,i=1,2,…,p且j=1,2,…,q。

L(x,α,β)对x以及参数α和β进行求导,然后得出结果带入原始便可求出我们需要的最优解。存在问题:

1、这里参数α和β总共p+q个,如果全部求偏导工作量太大,不现实; 
2、并且大家有没有想过,这个问题可能根本就没有最优解这种情况存在。

对偶问题的性质:无论原命题的形式如何,对偶问题都是一个凸优化问题,凸优化问题的好处就是局部最优解就是全局最优解,且易求解,将问题转化为其对偶问题就简化了问题的求解思路。

自定义一个函数如下: 

这里写图片描述

分析上面的自定义函数有: 

(1)式,当目标函数的约束条件都满足时,就是求maxL,(2)式是只要目标函数的约束条件有一个不满足,则自定义的函数便等于无穷大!

也就是当满足约束时存在最大值,当不满足约束时为无穷大,那么问题就可归并为求最大值的最小值,(相对于原来变量x 无约束了),即可将最初的优化问题写成:

这里写图片描述

其对偶便是:

这里写图片描述

令: 

这里写图片描述

这里写图片描述

所以有: P>=Q 

对偶问题提供了原问题最优值的一个下界,通过对偶问题求解原问题的最优解,所以只有当二者相等时即P=Q,才可能将原问题转化成对偶问题进行求解。当然,当满足一定条件的情况下,便有P=Q。而这个条件便是 slater条件和KTT条件。

slater条件:

slater条件官方正规定义:存在x,使得不等式约束g(x)<=0严格成立。 
slater条件性质: slater条件是原问题P可以等价于对偶问题Q的一个充分条件,该条件确保了鞍点的存在。

3.5 KKT条件

slater条件已经确保了鞍点的存在,但是鞍点不一定就是最优解啊,所以KKT条件的作用便体现出来了。 
KKT条件便是在鞍点中找出原函数最优解的充分条件,当然对于我们前面举得那个例子,当原问题是凸优化问题时,则KKT条件便是鞍点便是最优解的充要条件。

3.5.1 KKT条件

解释:

1:最优点x必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的;

2:在最优点x, ∇f必须是∇gi和∇hj的线性組合;

3:拉格朗日乘子不等式的一些限制,对于不等式的拉格朗日乘子限制条件有方向性, 所以每一个α都必须大于或等于零, 而等式限制条件没有方向性,只是β不等于0。

3.5.2 互补松弛解释

分成三种情况:

不等式约束等号成立,则拉格朗日乘子不为0;

不等式约束等号成立,则拉格朗日乘子为0;

不等式约束等号不成立,拉格朗日乘子为0;

不等式约束等号成立,则是支持向量。

不等式约束等号不成立,则是非支持向量。

延伸:

如果拉格朗日乘子>0或<0,则是一定支持向量

如果拉格朗日乘子=0,则不一定支持向量

注意,对于等式约束的Lagrange乘子,并没有非负的要求!以后求其极值点,不必再引入松弛变量,直接使用KKT条件判断!

3.5.2 hinge loss

https://qiy.net/2020/06/08/ML_Classifier/

4SVM分类方法

SVM本身是一个二值分类器   SVM算法最初是为二值分类问题设计的,当处理多类问题时,就需要构造合适的多类分类器。   目前,构造SVM多类分类器的方法主要有两类   (1)直接法,直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单,但其计算复杂度比较高,实现起来比较困难,只适合用于小型问题中;

  (2)间接法,主要是通过组合多个二分类器来实现多分类器的构造,常见的方法有one-against-one和one-against-all两种。 一对多法(one-versus-rest,简称OVR SVMs)   训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类,这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。   假如我有四类要划分(也就是4个Label),他们是A、B、C、D。   于是我在抽取训练集的时候,分别抽取   (1)A所对应的向量作为正集,B,C,D所对应的向量作为负集;   (2)B所对应的向量作为正集,A,C,D所对应的向量作为负集;   (3)C所对应的向量作为正集,A,B,D所对应的向量作为负集;   (4)D所对应的向量作为正集,A,B,C所对应的向量作为负集;   使用这四个训练集分别进行训练,然后的得到四个训练结果文件。   在测试的时候,把对应的测试向量分别利用这四个训练结果文件进行测试。   最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x)。   于是最终的结果便是这四个值中最大的一个作为分类结果。 评价:   这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased.因而不是很实用。可以在抽取数据集的时候,从完整的负集中再抽取三分之一作为训练负集。

一对一法(one-versus-one,简称OVO SVMs或者pairwise)

  其做法是在任意两类样本之间设计一个SVM,因此k个类别的样本就需要设计k(k-1)/2个SVM。

  当对一个未知样本进行分类时,最后得票最多的类别即为该未知样本的类别。

  Libsvm中的多类分类就是根据这个方法实现的。

  假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集,然后得到六个训练结果,在测试的时候,把对应的向量分别对六个结果进行测试,然后采取投票形式,最后得到一组结果。

  投票是这样的:   A=B=C=D=0;   (A,B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;   (A,C)-classifier 如果是A win,则A=A+1;otherwise, C=C+1;   …   (C,D)-classifier 如果是A win,则C=C+1;otherwise,D=D+1;   The decision is the Max(A,B,C,D)

评价:这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的。

层次支持向量机

层次分类法首先将所有类别分成两个子类,再将子类进一步划分成两个次级子类,如此循环,直到得到一个单独的类别为止。对层次支持向量机的详细说明可以参考论文《支持向量机在多类分类问题中的推广》(刘志刚,计算机工程与应用,2004)

参考:

https://blog.csdn.net/feilong_csdn/article/details/62427148

https://zhuanlan.zhihu.com/p/26514613