感知机（三）
source link: https://ylhao.github.io/2018/05/04/238/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
感知机（三）
这篇文章主要讨论感知算法的对偶形式。
之前的文章，我们得到如果使用随机梯度下降法，那么更新 w,bw,b 的式子如下：
w←w+ηyixi b←b+ηyi w←w+ηyixib←b+ηyi
假设对于一个实例 (xi,yi)(xi,yi)，一共执行了 nini 次更新过程，那么 w,bw,b 关于 (xi,yi)(xi,yi) 的增量分别为 niηyixi,niηyiniηyixi,niηyi。
令：
αi=niηαi=niη
同时设一共有 N 个点，那么可以得到下式：
w=N∑i=1αiyixi b=N∑i=1αiyi αi≥0w=∑i=1Nαiyixib=∑i=1Nαiyiαi≥0
特别的，当 η=1η=1 时，αiαi 代表由于第 ii 个实例点误分而进行更新的次数。
引出对偶形式
将上面得到的 ww 代到原来的感知机模型中，得到原感知机模型的对偶形式：
f(x)=sign(N∑j=1αjyjxjx+b)f(x)=sign(∑j=1Nαjyjxjx+b)
我们可以认为模型的参数为 αα 和 bb，其中：
α=(α1,α2,…,αN)α=(α1,α2,…,αN)
在训练集中选一个点 (xi,yi)(xi,yi)，当该点分类错误时，有：
yi(N∑j=1αjyjxjx+b)<0yi(∑j=1Nαjyjxjx+b)<0
此时，需要更新 (x_i, y_i) 对应的参数：
αi=αi+η b=b+ηyiαi=αi+ηb=b+ηyi
然后再选选练集的下一个点，直到所有的点都被分对。其中式子 αi=αi+ηαi=αi+η 可以由式子 αi=niηαi=niη 推出。
Gram 矩阵
我们可以将所有的实例的内积计算出来，存到矩阵中，这个矩阵就是 Gram 矩阵，G=[xi⋅xj]N×NG=[xi⋅xj]N×N。
例如，我们假设 x1=(3,3)T,x2=(4,3)T,x3=(1,1)Tx1=(3,3)T,x2=(4,3)T,x3=(1,1)T，计算得到的 Gram 矩阵为：
G=[18216 21257 672]G=[1821621257672]
计算这个矩阵以后，我们就可以直接查矩阵中的元素去获取对应的向量内积了。最后总结感知机的对偶形式也是可以收敛的，与原始形式一样，存在多个解。
- 《统计学习方法》—— 李航
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]
文章标题:感知机（三）
文章字数:490
本文作者:ylhao
发布时间:2018-05-04, 13:26:33
最后更新:2019-06-07, 11:50:53
原始链接:https://ylhao.github.io/2018/05/04/238/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。
来做第一个留言的人吧！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK