从感知机到 SVM,再到深度学习(一)
先考虑最简单的情况,也就是这两类点是没有交错在一起的,能够用一条直线
对于直线(或超平面),其实我们为了方便,我们可以给直线加一些不会影响最终结果的限制,让求解的模型少一些选择,只要依旧可以通过调整参数找到最优解就没问题。比如规定直线的大于 0 的一面一定是蓝点,小于 0 的一面一定是黄点。可能有人会问,那找到最优的直线的时候蓝点在小于 0 的一侧怎么办。但是没关系,即使是同一条直线,也可以通过两边同乘以 -1 达到让小于 0 和大于 0 换边的情况,所以这样假设没有关系,在进行参数优化的时候它自己就可以通过调整 a,b 来达到要求。加上这个限制,最终的目标函数就很好写了。首先给蓝、黄点分别标记为 p, q,训练集就是
接下来就是要对这个损失函数进行调参优化了。可以看出来,这个函数其实是找到当前的所有误分类点,然后通过它们进行调参,所以它是误分类点驱动的。但是即使找到了所有的无误分类点,由于损失函数是离散的,不连续也不可导,很难优化。所以需要找一个近似的,连续可导的函数来替换 f 函数。对于分错的点,我们可以用
- 随机给定 w, b
- 找到当前这条直线
ax1+bx2+c=0 的情况下,找到所有分错的点(x_no,y_no) - 把直线写作矩阵的形式:
wx+c=0 ,其中w=(w1,w2) ,x=(x1,x2)T ,然后通过找到的误分点用梯度下降法进行参数调优。∂L(w,b)∂w=∑ni=1yixi ∂L(w,b)∂b=∑ni=1yi w:=w+α∗∑ni=1yixi b:=b+α∗∑ni=1yi
其中α 是学习率。 - 重复 2, 3 步。直到找不到错分的点或者到达迭代上限为止。
经过实验发现这种目标函数收敛比平方的那个的要快,而且对于点刚好在直线上时,平方法中求出来的 a, b 的梯度都是 0,就无法处理了,所以只能认为刚好在直线上也是分对了。而这种方法由于有
如果初始值是线性不可分的,就会出现不收敛,一直在交叉的点之间震荡的情况。
这个就是传说中的感知机算法,这里的例子都是二维的,但是对于多维的情况也是一样的。无非就是直线变成一个超平面
感知机算法虽然能够将线性可分的数据集区分开,但是比较没追求…只要能找到一条能把两类点完全分开的直线就满足了。但是这样的直线是有无穷多条的,我们希望能根据训练数据找到一条“最优”的,这样有利于算法的泛化能力,也更加充分的利用了数据的信息。比如下图:
感知机会认为上面的图都是最优解。但是显然第二个优于第一个和第三个。那么怎么解决呢?
我们期望能找到一条基于当前训练数据的“最优”的直线。所谓“最优”还是需要量化,其实就对应了最大化目标函数。而感知机之所以没有最优是因为它的目标函数
1. 线性函数
2. sigmoid 函数
而感知机中用的是阶跃函数,相对比较粗糙。
其中用 sigmoid 函数作为**函数的就算法就叫 logistic 回归了,也是最常用的。sigmod 函数在 x > 0 的时候 y > 0.5, x< 0 的时候 y<0.5。这样函数就能与 0.5 进行比较,从而自动识别出点是否分对,以及分对(或分错)的程度了。
那么这个怎么转化为需要最大化的目标函数呢?其实这个还是用直线进行划分,我们还是假设 {a, b} 两类,其中让 a 类带入直线大于 0, b 类小于零(之前已经解释,这样做是没有问题的) 那么对于某个点,如果它是 a 类,我们就让 p 尽量大 ,如果是 b 类我们是要让 1 - p 尽量大。把这个目标写成式子就是:对于某个点,我们要
其实对于 sigmoid 函数而言,它已经把最后的输出值限制在 [0, 1] 的范围内,并且是以 0.5 为界。那么我们就可以把输出值看做一个概率,把分对、分错的程度(确信度)用一个概率值表示出来当分对的概率大于 0.5 的时候,我们就可以认为确实分对了。这样就有很多更好的损失函数的公式可以直接用进来,比如交叉熵,极大似然估计等。
比如用交叉熵,交叉熵的公式是:
这里带入交叉熵公式得到的损失函数是:
然后用梯度下降法优化就行了,步骤是:
- 获取 n 个训练样本 (x_{1}, x_{2}, y) , y 属于
0,1 - 对于直线
wx+b=0 ,需要minL(w,b)=−1n∑ni=1yisigmoid(xi)))+(yi−1)(1−sigmoid(xi))) ,对参数求梯度:∂L(w,b)w=−1n∑ni=1xi(yi−sigmoid(wxi+b)) ∂L(w,b)b=−1n∑ni=1yi−sigmoid(wxi+b) w:=w−α∂L(w,b)w b:=b−α∂L(w,b)b - 重复 1,2,直到 w, b 的梯度小于某个很小的值,或者达到循环上限。
如果用极大似然估计,由于在极大似然估计中需要取对数操作,为了方便,可以把
然后为了计算方便,取对数。为了把这个 max 变成 min,需要进行取反,这都是极大似然估计的标准步骤:
最后发现两种方法得到的表达式是一样的,所以后面的优化步骤都一样。
这个就是 logistic 回归的思路了。这里还是用二维的举例,对于高维的情况几乎是一样的,就是参数从
那么 logistic 回归就是完美的了吗,它至少还有两个缺点:1. 还是只能解决数据线性可分的问题 2. 考虑所有的点得到的最优直线还是会带来一些问题,比如:
明显图 2 优于图1 ,图 1 的泛化能力较差,新的黑点很容易就被分到黄点一侧了。
为什么会这样呢?通过 sigmoid 函数的图像可以看出来。
两个类别的数据量是一样的。但是由于黑点有一部分离得比较远,所以把直线向黑点侧移动一些对于那些黑点而言目标函数减少的很少。而黄点比较集中且离平面较近,让平面远离黄点的收益更大。这个问题当数据量不平衡的时候会更加严重。
那么如果用线性函数作为**函数呢?这样对于两类的数据量不相同的时候这个问题依然会出现。
感知机只考虑分错的点,会无法找到最理想的直线。而 logistic 回归考虑了所有点,但是对于离得比较远的点,甚至异常点也会过于敏感(比如这里黄点离得比较远的点就对平面产生了很大影响)。其实问题还是在我们对“最优直线”的定义上,我们其实是想让最终的直线离开两边的点都尽量远。所以其实可以只考虑离直线最近的那些点,只要让它们和直线的距离尽量大就行了。
如图,黑色虚线就是当前需要优化的目标。当它过于靠近黄点的时候,优化的目标就会变成直线跟最近的黄点的距离。因为需要对点和直线衡量距离,而不是像感知机中只要知道点在直线的那一侧就行了。所以这里就需要用点到直线的距离公式了,距离公式为
用这个目标函数的算法叫最优间隔分类器。接下来就需要用凸优化的理论来求解这个优化问题了,比较复杂,下次再写吧。
参考链接:
1. 【机器学习-斯坦福】学习笔记7 - 最优间隔分类器问题
2. 交叉熵(Cross-Entropy)
3. 感知机:从原理到训练
4. 拉格朗日乘数法
对机器学习感兴趣的新手或者大牛,如果有觉得对别人有帮助的,高质量的网页,大家可以通过 chrome 插件分享给其他人,在这里安装分享插件。