1700534094
(3.6)
1700534095
1700534096
其中,
1700534097
1700534098
1700534099
.
1700534100
1700534101
(3.7)
1700534102
1700534103
可以看到,除支持向量外,其他系数均为0,因此SVM的分类结果与仅使用支持向量的分类结果一致,说明SVM的分类结果仅依赖于支持向量,这也是SVM拥有极高运行效率的关键之一。于是,我们证明了对于任意线性可分的两组点,它们在SVM分类的超平面上的投影都是线性不可分的。
1700534104
1700534105
实际上,该问题也可以通过凸优化理论中的超平面分离定理(Separating Hyperplane Theorem,SHT)更加轻巧地解决。该定理描述的是,对于不相交的两个凸集,存在一个超平面,将两个凸集分离。对于二维的情况,两个凸集间距离最短两点连线的中垂线就是一个将它们分离的超平面。
1700534106
1700534107
借助这个定理,我们可以先对线性可分的这两组点求各自的凸包。不难发现,SVM求得的超平面就是两个凸包上距离最短的两点连线的中垂线,也就是SHT定理二维情况中所阐释的分类超平面。根据凸包的性质容易知道,凸包上的点要么是样本点,要么处于两个样本点的连线上。因此,两个凸包间距离最短的两个点可以分为三种情况:两边的点均为样本点,如图3.12(a)所示;两边的点均在样本点的连线上,如图3.12(b)所示;一边的点为样本点,另一边的点在样本点的连线上,如图3.12(c)所示。从几何上分析即可知道,无论哪种情况两类点的投影均是线性不可分的。
1700534108
1700534109
1700534110
1700534111
1700534112
图3.12 两个凸包上距离最短的两个点对应的三种情况
1700534113
1700534114
至此,我们从SVM直观推导和凸优化理论两个角度揭示了题目的真相。其实,在机器学习中还有很多这样看上去显而易见,细究起来却不可思议的结论。面对每一个小问题,我们都应该从数学原理出发,细致耐心地推导,对一些看似显而易见的结论抱有一颗怀疑的心,才能不断探索,不断前进,一步步攀登机器学习的高峰。
1700534115
1700534116
问题2 是否存在一组参数使SVM训练误差为0?
1700534117
1700534118
难度:★★★☆☆
1700534119
1700534120
1700534121
一个使用高斯核训练的SVM中,试证明若给定训练集中不存在两个点在同一位置,则存在一组参数{α1,…,αm,b}以及参数γ使得该SVM的训练误差为0。
1700534122
1700534123
分析与解答
1700534124
1700534125
根据SVM的原理,我们可以将SVM的预测公式可写为
1700534126
1700534127
1700534128
,
1700534129
1700534130
(3.8)
1700534131
1700534132
1700534133
1700534134
其中为训练样本,而{α1,…,αm,b}以及高斯核参数γ为训练样本的参数。由于不存在两个点在同一位置,因此对于任意的i≠j,有。我们可以对任意i,固定αi=1以及b=0,只保留参数γ,则有
1700534135
1700534136
1700534137
1700534138
1700534139
(3.9)
1700534140
1700534141
将任意x(j)代入式(3.9)则有
1700534142
1700534143
[
上一页 ]
[ :1.700534094e+09 ]
[
下一页 ]