1. 支持向量机Support Vector Machines
1.1 介绍
在分类问题中,除了线性的逻辑回归模型和非线性的深度神经网络外,我们还可以应用一种被广泛应用于工业界和学术界的模型—支持向量机,简称SVM,与逻辑回归和神经网络相比,支持向量机在学习复杂的非线性方程时提供了一种更为清晰,更加强大的方式。
尽管现在深度学习十分流行,了解支持向量机的原理,对想法的形式化、简化、及一步步使模型更一般化的过程,及其具体实现仍然有其研究价值。另一方面,支持向量机仍有其一席之地。相比深度神经网络,支持向量机特别擅长于特征维数多于样本数的情况,而小样本学习至今仍是深度学习的一大难题。
关于支持向量机的简单概念和定义,请参考这篇文章: https://www.zhihu.com/question/21094489/answer/190046611
更详细地了解和推导SVM,请参考以下几篇文章:
https://zhuanlan.zhihu.com/p/40857202
https://zhuanlan.zhihu.com/p/31652569
1.2 从逻辑回归到SVM
下面,我们利用逻辑回归模型,建立简单的支持向量机,来进行对比和讲解。
1.2.1 假设函数
逻辑回归假设函数:函数图像如下:
y = 1时,我们希望z远大于0,
y = 0时,我们希望z远小于0,
1.2.2 损失函数
逻辑回归中的总损失函数:
其中,每个训练集样本点的损失:
当y = 1时,我们得到损失的表达式:
当y = 0时,我们得到
我们可以画出损失Cost和变量z之间的关系,如下图:
现在,我们将建立支持向量机,在此处,即画出线段,用于分割二维平面。
如图,对于左图,向量机建立如下:
以z = 1为端点,往左画出一条紧紧贴和函数曲线的直线,往右,画出一条平行z轴的直线,2条线交与z = 1这点
这两条直线构成了一个新的界限,我们命名此函数为对于右图,类似地,画出两条线,不过这次以z = -1为交点。命名新的函数为
1.2.3 SVM数学定义
逻辑回归中,损失函数如下:
我们在1.2.2中建立了支持向量机,用和替换了原来的逻辑回归,故此时的损失函数如下:
经过进一步简化,我们可以得到SVM中的损失函数:
这里C = 1/λ,去除了1/m,并不影响min(J(θ))这个目标的达成。
支持向量机的数学定义:
在这个例子中,我们可以看到:
1.这里的假设函数直接输出的是值0或1,而不是逻辑回归中的概率值。
2.支持向量机的定义类似损失函数,不过比损失函数更进一步,因为其要求min将损失最小化。
1.3 大间距的直观理解
有时候,人们会将把SVM叫做大间距分类器,为什么支持向量机被称为大间距分类器 ?这一小节将直观地介绍其中的含义。我们回顾一下支持向量机的模型定义:
我们的目标是最小化这个方程,下面我们结合图像说明最小化的过程:
1.3.1 参数C很大时
这里我们假设参数C很大,此时最小化方程式的重点放在左半部分,而可以"忽略"右边的所以我们的优化目标主要放在让左边式子为0上:
1.当样本为正,y = 1,则根据的函数图像,我们希望因为此时:我们可以使得方程最小化。
2.当样本为负时,即y = 0,则根据函数图像,此时,我们希望因为此时:
不过,我们注意到,如果一个样本满足y = 1时, 即可使模型能将其准确分类,对于负样本y = 0同样只需要 即可。那么支持向量机里,追求的最优化方程究竟会带来什么?
我们将样本点x在坐标系中向量化表示,即x是一条从原点开始,指向(x1,x2)的矢量,x的模长 = x1^2 + x2^2,则我们可以得到一系列样本点坐标图,如下:
答:会带来一条支持向量机的超平面,在二维方程中,超平面即一条直线,我们会得到一条直线,将样本点分割开来,且这条直线满足 即将这个表达式的值取到最小:
当然,当样本上升到3维、4维、N维时,支持向量机就表示一个平面、多维超平面,而不仅仅是一条线。但是同样会满足大间距分类器这样的含义。即保持到样本点间的最大距离。
这里需要说明的是:决策边界可以划出n条,如图中的粉色、绿色、黑色.....但满足最小化方程式的值的边界只有一条,这条边界被称为支持向量机。
1.3.2 参数C较小时
当然,我们上面都是基于假设参数C很大时的情况,那如果C不是很大时,我们就不仅仅要考虑方程式中左边的项,还需要同步考虑右边项了。下面我们再看一个例子:
当C很大时,我们的支持向量机画出了一条决策边界:
1.3.3 关于参数C
回顾之前的表达式可知,参数C = 1/λ 当C较大时,对应λ较小,即正则化参数较小,可能会导致过拟合,和支持向量机的高方差;当C较小时,对应λ较大,可能导致欠拟合(拟合不够),和支持向量机的高偏差
1.4 大间距的数学原理
1.4.1 向量内积
为了方便举例,此处以二维向量举例。u、v都是二维向量,它们的内积:
内积的含义在哪里 ? 图中我们可以用投影和范数(在欧几里得范数中即 = 模长)来表示:用文字表示:u和v的内积 = 向量v在向量u上的投影乘以向量向量u的范数(或者反过来表示也一样)
这里需要注意,如图中的第二个图所展示的:当向量u和v角度>90°时,p值为负。
1.4.2 SVM的数学原理
之前支持向量机的方程,写作:在数学里面s.t.是subject to 的缩写,意为:使得...满足
这里,为了方便说明,简化一下令此时此时,可以看作是向量的两个分量,则有对于 可以将其看作是的内积,表示上的投影,则向量关系示意图如下:
左图种的绿线是支持向量机的一种决策边界,我们称为A,右图的绿线是另一种决策边界B,支持向量机会更倾向于选择哪种决策边界呢? 答案是B
因为根据公式,支持向量机需要最小化θ的范数,即取到最小。
为了满足的条件,当||θ||取值越小时,向量机希望越大,即上的投影越大。且和绿色的决策边界垂直,很明显可以看出,当决策边界为B时,投影越大,即足够大,我们可以取到更小的
1.5 核函数
回顾我们之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题:
则假设函数便可以转化为: 这种方法即通过多项式模型的方式构造新特征那么有没有其他方式来构造新特征?有,通过核函数即可完成。
为了构造新的特征 我们引入地标(landmark)我们可以通过判断样本x和地标间的近似程度来选取新的特征
地标的作用是什么 ?如果一个样本x距离地标距离接近/等于0,则否则 = 0,于是我们利用样本和地标间的关系来得出了特征f的值。
1.5.1 地标landmark和𝜎
会对模型和特征f有什么影响? 我们看一个例子:
这里取地标为固定向量,三组不同的
1.红色顶点处,即向量和向量地标向量重合处,即距离= 0,故此时
2.可以看见越大,图像越宽,同样的x样本向量,譬如这个样本在图1中就会被判定为而在图3中则可能被判定为即会影响到最终特征值f的判断。即随着𝑥的改变𝑓值改变的速率受到𝜎的控制。
1.5.2 决策边界
假定:假设函数值>=0时预测y = 1,否则y = 0,则通过上面的高斯核函数我们可以算出每个样本点x距离地标l的距离,从而算出每个特征f,从而求出每个样本点的预测值y,即可以正确给每个样本分类,从而得到一条决策边界。例如:对于红色点x,由于其距离地标l1较近,故f1 = 1,同时其距离l2和l3较远,故f2 = f3 = 0,假设函数值= -0.5+1 = 0.5>0故预测其y = 1;
对于绿色点x,f2 = 1 ,假设函数值 = -0.5+0+1+0 =0.5故其预测也为1
.....
可以看出此例中存在一条决策边界,如红线划出的范围,在边界以内的样本都是预测y = 1,边界外的都是y = 0。
1.5.3 核函数2
上一个例子,比较简单地说明了核函数的应用,但是实际情况下,核函数怎么使用呢?地标l又如何选取?
得到新的特征后,我们可以写出代价函数的表达式:
另外,支持向量机也可以不使用核函数,不使用核函数又称为线性核函数(linear kernel),
当我们不采用非常复杂的函数,或者我们的训练集特征非常多而实例非常少的时候,可以采用这种不带核函数的支持向量机。
1.6 使用支持向量机
本节主要是对支持向量机、核函数等概念和使用的一个总结,我就直接copy了。
目前为止,我们已经讨论了SVM 比较抽象的层面,在这个视频中我将要讨论到为了运行或者运用 SVM。你实际上所需要的一些东西:支持向量机算法,提出了一个特别优化的问。但是就如在之前的视频中我简单提到的,我真的不建议你自己写代码来求解参数𝜃,因此由于今天我们中的很少人,或者其实没有人考虑过自己写代码来转换矩阵,或求一个数的平方根等我们只是知道如何去调用库函数来实现这些功能。同样的,用以解决 SVM 最优化
问题的软件很复杂,且已经有研究者做了很多年数值优化了。因此你提出好的软件库和好的软件包来做这样一些事儿。然后强烈建议使用高优化软件库中的一个,而不是尝试自己落实一些数据。有许多好的软件库,我正好用得最多的两个是liblinear 和 libsvm,但是真的有很多软件库可以用来做这件事儿。你可以连接许多你可能会用来编写学习算法的主要编程语言。
在高斯核函数之外我们还有其他一些选择,如:
多项式核函数(Polynomial Kernel)
字符串核函数(String kernel)
卡方核函数( chi-square kernel)
直方图交集核函数(histogram intersection kernel)
等等...
这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征,这些核函数需要满足Mercer's 定理,才能被支持向量机的优化软件正确处理。
1.6.2多类分类问题
假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有𝑘个类,则我们需要𝑘个模型,以及𝑘个参数向量𝜃。我们同样也可以训练𝑘个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能,我们只要直接使用即可。
尽管你不去写你自己的SVM 的优化软件,但是你也需要做几件事:
1、是提出参数𝐶的选择。我们在之前的视频中讨论过误差/方差在这方面的性质。
2、你也需要选择内核参数或你想要使用的相似函数,其中一个选择是:我们选择不需要任何内核参数,没有内核参数的理念,也叫线性核函数。因此,如果有人说他使用了线性核SVM(支持向量机),这就意味这他使用了不带有核函数的SVM(支持向量机)。
1.6.3逻辑回归or支持向量机
在两者之间,我们应该如何选择呢?
下面是一些普遍使用的准则:
𝑛为特征数,𝑚为训练样本数。
(1)如果相较于𝑚而言,𝑛要大许多,即训练集数据量不够支持我们训练一个复杂的非线性模型,我们选用逻辑回归模型或者不带核函数的支持向量机。
(2)如果𝑛较小,而且𝑚大小中等,例如𝑛在 1-1000 之间,而𝑚在 10-10000 之间,使用高斯核函数的支持向量机。
(3)如果𝑛较小,而𝑚较大,例如𝑛在 1-1000 之间,而𝑚大于 50000,则使用支持向量机会非常慢,解决方案是创造、增加更多的特征,然后使用逻辑回归或不带核函数的支持向量机。
值得一提的是,神经网络在以上三种情况下都可能会有较好的表现,但是训练神经网络可能非常慢,选择支持向量机的原因主要在于它的代价函数是凸函数,不存在局部最小值。
今天的SVM 包会工作得很好,但是它们仍然会有一些慢。当你有非常非常大的训练集,且用高斯核函数是在这种情况下,我经常会做的是尝试手动地创建,拥有更多的特征变量,然后用逻辑回归或者不带核函数的支持向量机。如果你看到这个幻灯片,看到了逻辑回归,或者不带核函数的支持向量机。
在这个两个地方,我把它们放在一起是有原因的。原因是:逻辑回归和不带核函数的支持向量机它们都是非常相似的算法,不管是逻辑回归还是不带核函数的SVM,通常都会做相似的事情,并给出相似的结果。但是根据你实现的情况,其中一个可能会比另一个更加有效。但是在其中一个算法应用的地方,逻辑回归或不带核函数的。SVM另一个也很有可能很有效。但是随着 SVM 的复杂度增加,当你使用不同的内核函数来学习复杂的非线性函数时,这个体系,你知道的,当你有多达 1 万(10,000)的样本时,也
可能是 5 万(50,000),你的特征变量的数量这是相当大的。那是一个非常常见的体系,也在这个体系里,不带核函数的支持向量机就会表现得相当突出。你可以做比这困难得多需要逻辑回归的事情。
最后,神经网络使用于什么时候呢?
对于所有的这些问题,对于所有的这些不同体系,一个设计得很好的神经网络也很有可能会非常有效。有一个缺点是,或者说是有时可能不会使用神经网络的原因是:对于许多这样的问题,神经网络训练起来可能会特别慢,但是如果你有一个非常好的SVM 实现包,它可能会运行得比较快比神经网络快很多,尽管我们在此之前没有展示,但是事实证明,SVM 的优化问题,是一种凸优化问题。
因此,好的 SVM优化软件包总是会找到全局最小值,或者接近它的值。对于SVM 你不需要担心局部最优。在实际应用中,局部最优不是神经网络所需要解决的一个重大问题,所以这是你在使用SVM的时候不需要太去担心的一个问题。根据你的问题,神经网络可能会比 SVM慢,尤其是在这样一个体系中,至于这里给出的参考,看上去有些模糊,如果你在考虑一些问题,这些参考会有一些模糊,但是我仍然不能完全确定,我是该用这个算法还是改用那个算法,这个没有太大关系,当我遇到机器学习问题的时候,有时它确实不清楚这是否是最好的算法,但是就如在之前的视频中看到的算法确实很重要。但是通常更加重要的是:你有多少数据,你有多熟练是否擅长做误差分析和排除学习算法,指出如何设定新的特征变量和找出其他能决定你学习算法的变量等方面,通常这些方面会比你使用逻辑回归还是 SVM 这方面更加重要。但是,已经说过了,SVM 仍然被广泛认为是一种最强大的学习算法,这是一个体系,包含了什么时候一个有效的方法去学习复杂的非线性函数。因此,实际上与逻辑回归、神经网络、SVM 一起使用这些方法来提高学习算法,我认为你会很好地建立很有技术的状态。(编者注:当时 GPU 计算比较慢,神经网络还不流行。)
机器学习系统对于一个宽泛的应用领域来说,这是另一个在你军械库里非常强大的工具,你可以把它应用到很多地方,如硅谷、在工业、学术等领域建立许多高性能的机器学习系统。