机器学习之在线学习
发布日期:2021-10-22 18:11:16 浏览次数:3 分类:技术文章

本文共 1469 字,大约阅读时间需要 4 分钟。

online learning

原题目叫做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的理解,这个定理就可以阐述为:如果训练样本线性可分,并且几何间距至少是,样例样本特征向量最长为D,那么感知算法错误数不会超过。这个定理是62年提出的,63年Vapnik提出SVM,可见提出也不是偶然的,感知算法也许是当时的热门。

下面主要讨论这个定理的证明:

      感知算法只在样例预测错误时进行更新,定义是第k次预测错误时使用的样本特征权重, 初始化为0向量。假设第k次预测错误发生在样例上,利用计算值时得到的结果不正确(也就是说,调换x和顺序主要是为了书写方便)。也就是说下面的公式成立:

      

      根据感知算法的更新方法,我们有。这时候,两边都乘以u得到

      

      两个向量做内积的时候,放在左边还是右边无所谓,转置符号标注正确即可。

      这个式子是个递推公式,就像等差数列一样f(n+1)=f(n)+d。由此我们可得

      

      因为初始为0。

      下面我们利用前面推导出的和得到

      也就是说的长度平方不会超过与D的平方和。

      又是一个等差不等式,得到:

      

      两边开根号得:

      

      其中第二步可能有点迷惑,我们细想u是单位向量的话,

      

      因此上面的不等式成立,最后得到:

      

      也就是预测错误的数目不会超过样本特征向量x的最长长度与几何间隔的平方。实际上整个调整过程中就是x的线性组合。

      整个感知算法应该是在线学习中最简单的一种了,目前发现online learning挺有用的,以后多多学习。

 

转载于:https://www.cnblogs.com/zyber/p/6489312.html

转载地址:https://blog.csdn.net/weixin_30402343/article/details/94818361 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:http协议
下一篇:sql的连接查询方式

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月04日 02时08分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php 程序授权机制,授权认证详细说明 2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令? 2019-04-21
IP/tzgm.php,LianjiaSpider/在售数量.ipynb at master · BerSerK/LianjiaSpider · GitHub 2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件 2019-04-21
linux查看系统所有变量,Linux系统各指标命令 2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢? 2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构 2019-04-21
mysql构建url给scrapy_Python Scrapy从mysq填充起始url 2019-04-21
owdcloud mysql_MySQL在Ubuntu远程配置 2019-04-21