(9)在线学习1
需积分: 0 77 浏览量
2022-08-03
15:10:31
上传
评论
收藏 531KB PDF 举报
在线学习（Online Learning）
JerryLead
csxulijie@gmail.com
原题目叫做 The perception and large margin classifiers，其实探讨的是在线学习。这里将
题目换了换。以前讨论的都是批量学习（batch learning），就是给了一堆样例后，在样例上
学习出假设函数 h。而在线学习就是要根据新来的样例，边学习，边给出结果。
假设样例按照到来的先后顺序依次定义为
。X 为样
本特征，y 为类别标签。我们的任务是到来一个样例 x，给出其类别结果 y 的预测值，之后
我们会看到 y 的真实值，然后根据真实值来重新调整模型参数，整个过程是重复迭代的过程，
直到所有的样例完成。这么看来，我们也可以将原来用于批量学习的样例拿来作为在线学习
的样例。在在线学习中我们主要关注在整个预测过程中预测错误的样例数。
拿二值分类来讲，我们用 y=1 表示正例，y=-1 表示负例。回想在讨论支持向量机中提到
的感知算法（perception algorithm）。 我们的假设函数为
其中 x 是 n 维特征向量，是 n+1 维参数权重。函数 g 用来将
计算结果映射到-1 和 1
上。具体公式如下：
这个也是 logistic 回归中 g 的简化形式。
现在我们提出一个在线学习算法如下：
新来一个样例，我们先用从之前样例学习到的
来得到样例的预测值 y，如果
（即预测正确），那么不改变，反之
也就是说，如果对于预测错误的样例，进行调整时只需加上（实际上为正例）或者减
去（实际负例）样本特征 x 值即可。初始值为向量 0。这里我们关心的是
的符号，而不
是它的具体值。调整方法非常简单。然而这个简单的调整方法还是很有效的，它的错误率不
仅是有上界的，而且这个上界不依赖于样例数和特征维度。
下面定理阐述了错误率上界：
定理（Block and Novikoff）：
给定按照顺序到来的
样例。假设对于所有的样例
，也就是说特征向量长度有界为 D。更进一步，假设存在一个单位长度向量
且
。也就是说对于 y=1 的正例，
，反例
，
u 能够有的间隔将正例和反例分开。那么感知算法的预测的错误样例数不超过
。
根据前面对 SVM 的理解，这个定理就可以阐述为：如果训练样本线性可分，并且几何
评论0