小闹钟的机器学习笔记(7)
本次学习内容为cs229第七节
最优间隔分类器
几何距离表示样本和超平面上的距离,它有方向。最小距离称为最坏情况,因为我们希望距离能尽可能大。
将参数按倍数扩大,并不会影响几何距离。因为不会影响超平面的位置。
1. 最优化目标为几何距离。
求解参数,使得
其中||w||=1,使得几何距离=函数距离。
这个约束是个糟糕的非凸性约束,我们需要避免。
2. 最优化目标为函数距离/||w||。
这只是对同样问题的另一种表述方法。
戴帽子的是函数距离。
3. 最小化||w||的平方。
相当于最大化1/||w||。
可以添加约束条件:函数距离=1。
通过调整w的值来调整函数距离,使得样本到超平面的距离最小为1。
拉格朗日乘数法
首先应该建立一个算子,它等于原函数与限制条件的组合。
最优化的方法是对每个原始和拉格朗日算子求导,并设为0。
使得w* 为解的前提是这里存在一个beta* 能使偏导为0。
现在给出一般化的拉格朗日乘数法过程。
要最小化f(w),并且给出约束:
接下来是拉格朗日算子,这种情况下,
成为一般化的拉格朗日乘数法。
定义p*为原始问题的解。如果违背了约束条件,最终结果可能为无穷。
对偶问题
这里的D表示对偶,它以拉格朗日算子为参数,并不以w为参数。
在这里的l* 通常小于p*。通常情况下,max min<=min max。
原始问题的解可能会和对偶问题的解取同样的值,所有有时候可以用对偶问题的解代替原始问题的解。
支持向量机
当我们处理SVM问题时,我们只需要使用一个拉格朗日算子,而且我们有两个参数w和b。
我们的目标是:
并且要满足约束。
这约束规定了函数距离必须大于1。
函数距离为1的样本点通常对应的拉格朗日算子不为0,被称为支持向量。
支持向量的数目通常比较少,这意味着大部分点对应的拉格朗日算子=0。
它的对偶问题是:
要求出最小化,需要对参数求偏导,并使其为0。
w实际上是输入特征的线性组合。
另一个约束是:
代入求解:
最后一行的第一项称为W(a)
对偶问题是最大化W(a),同时满足下列约束:
我们用来求出SVM的最优间隔分类器的方法是对这个对偶问题求解。
通过该式子求出原始问题中的参数w,确定了w就确定了超平面的方向。接下来只需要决定使用哪个超平面就可以。
将a和w代入原始问题中就可以求出b。
对于它的直观理解是找到最差的正样本和最差的负样本,然后确定将超平面放到哪里。