《机器学习》笔记-计算学习理论(12)

作者:刘才权

编辑:李雪冬

前 言

如今机器学习和深度学习如此火热,相信很多像我一样的普通程序猿或者还在大学校园中的同学,一定也想参与其中。不管是出于好奇,还是自身充电,跟上潮流,我觉得都值得试一试。对于自己,经历了一段时间的系统学习(参考《机器学习/深度学习入门资料汇总》),现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书,并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录,同时,也会增加自己的理解,包括过程中的疑问,并尽量的和实际的工程应用和现实场景进行结合,使得知识不只是停留在理论层面,而是能够更好的指导实践。记录笔记,一方面,是对自己先前学习过程的总结和补充。 另一方面,相信这个系列学习过程的记录,也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

  • 基础知识
  • PAC学习
  • 有限假设空间
  • VC维
  • Rademacher复杂度
  • 稳定性

01

基础知识

顾名思义,计算学习理论(computation learning theory)研究的是关于通过“计算”来进行“学习”的理论。即关于机器学习的理论基础,其目的是分析学习任务的困难本质,为学习算法提供理论保证,并根据分析结果指导算法设计。

02

PAC学习

计算学习理论中最基本的是概率近似正确(Probably Approximately Correct,简称PAC)学习理论。

给定训练集D,我们希望基于学习算法ξ学得的模型所对应的假设h尽可能接近目标概念c。 PAC学习中一个关键因素是假设空间H的复杂度。H包含了学习算法ξ所有可能输出的假设,若在PAC学习中假设空间与概念类完全相同,即H=C,这称为“恰PAC可学习”(properly PAC learnable);直观地看,这意味着学习的能力与学习任务“恰好匹配”。然而,这种让所有候选假设都来自概念类的要求看似合理,但却并不实际,因为在现实应用中我们对概念类C通常一无所知,更别说获得一个假设空间与概念类恰好相同的学习算法。显然,更重要的研究假设空间与概念类不同的情形,即H≠C。一般而言,H越大,其包含任意目标概念的可能性越大,但从中找到某个具体目标概念的难道也越大。|H|有限时,我们称H为“有限假设空间”,否则称为“无限假设空间”。

03

有限假设空间

  • 可分情形 可分情形意味着目标概念c属于假设空间H,即c∈H;
  • 不可分情形 对较为困难的学习问题,目标概念c往往不存在与假设空间H中;

04

机器学习算法的挑战VC维

现实学习任务所面临的通常是无限假设空间。欲对此种情形的学习性进行研究,需度量假设空间的复杂度。最常见的办法是考虑假设空间的“VC维”(Vapnik-Chervonenkis dimension)。

05

Rademacher复杂度

基于VC维的泛化误差界是分布无关、数据独立的,也就是说,对任何数据分布都成立。这使得基于VC维的学习性分析结果具有一定的“普适性”;但从另一个方面来说,由于没考虑数据自身,基于VC维得到的泛化误差界通常比较“松”,对那些与学习问题的典型情况相差甚远的较“坏”分布来说尤其如此。

Rademacher复杂度(Rademacher complexity)是另一种刻画假设空间复杂度的途径,与VC维不同的是,它在一定程度上考虑了数据分布。

06

稳定性

无论是基于VC维还是Rademacher复杂度来推导泛化误差界,所得到的结果均与具体学习算法无关。对所有学习算法都适用。这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质。但在另一方面,若希望获得与算法有关的分析结果,则需另辟蹊径。稳定性(stability)分析是这方面一个值得关注的方向。 顾名思义,算法的“稳定性”考察的是算法在输入发生变化时,输出是否会随之发生较大的变化。

往期回顾之作者刘才权专栏

【1】《机器学习》笔记-聚类(9)

【2】《机器学习》笔记-集成学习(8)

【3】《机器学习》笔记-贝叶斯分类器(7)

【4】《机器学习》笔记-支持向量机(6)

【5】《机器学习》笔记-神经网络(5)

【6】2017年历史文章汇总|机器学习

原文发布于微信公众号 - 机器学习算法工程师(Jeemy110)

原文发表时间:2018-05-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

高级数据科学家阿萨姆:如何应对机器学习过程中的多项选择问题?| 分享总结

AI 研习社按:随着硬件算力的上升、数据量的加大以及各种新算法的浮现,机器学习也变得一天比一天火热。不夸张的说,这是机器学习的时代。然而,机器学习虽然能够给出惊...

36860
来自专栏奇点大数据

机器学习和深度学习的区别

近来有一些朋友问我,深度学习是不是算机器学习,如果是为什么一定要单拿出来算一个概念,那我在这就说说我的理解。 首先,深度学习确实仍然是依靠机器来做学习的不管是监...

33360
来自专栏AI

什么是深度学习?

深度学习是机器学习的一个子领域,涉及被称为人工神经网络的大脑的结构和功能所启发的算法。

28770
来自专栏数说工作室

logistic回归:从生产到使用【上:使用篇】

logistic回归:从生产到使用【上:使用篇】 前面介绍过几个算法,如KNN、决策树等(在微信公众号“数说工作室”中回复“jrsj”查看,不要引号),都可以用...

42960
来自专栏企鹅号快讯

人工智能与机器学习有哪些不同

每天读一篇一线开发者原创好文 来自:51CTO.COM,作者:RickyHo,刘妮娜译 链接:http://network.51cto.com/art/2017...

32700
来自专栏IT派

IBM长文解读人工智能、机器学习和认知计算

导语:人类对如何创造智能机器的思考从来没有中断过。期间,人工智能的发展起起伏伏,有成功,也有失败,以及其中暗藏的潜力。今天,有太多的新闻报道是关于机器学习算法的...

350140
来自专栏机器之心

学习世界模型,通向AI的下一步:Yann LeCun在IJCAI 2018上的演讲

Yann LeCun 开场介绍说,当前几乎所有的机器学习从业者在实践中使用的都是监督式学习:向机器展示大量的样本,然后告诉机器正确的答案与内部参数,然后就能做图...

13620
来自专栏AI研习社

教程 | Hinton 机器学习视频中文版:神经网络架构介绍(2.1)

本套课程中,Hinton 重点介绍了人工神经网络在语音识别和物体识别、图像分割、建模语言和人类运动等过程中的应用,及其在机器学习中发挥的作用。与吴恩达的《Mac...

35890
来自专栏雪胖纸的玩蛇日常

10.贝叶斯理论

10330
来自专栏AI科技评论

学界 | 迁移学习效果优化不再是难题,杨强教授团队带来自动找到最佳算法的L2T

AI 科技评论按:近日,香港科技大学杨强教授团队发表了一篇关于迁移学习的论文。在论文中,他们提出了一种新颖的迁移学习范式 Learning to Transfe...

34880

扫码关注云+社区

领取腾讯云代金券