机器学习理论导引

机器学习领域著名学者周志华教授领衔的南京大学LAMDA团队四位教授合著

系统梳理机器学习理论中的七大重要概念或理论工具，并给出若干分析实例

机器学习理论内容浩瀚广博，旨在为机器学习理论研究的读者提供入门导引

本书旨在为有志于机器学习理论学习和研究的读者提供一个入门导引。在预备知识之后，全书各章分别聚焦于：可学性、（假设空间）复杂度、泛化界、稳定性、一致性、收敛率、遗憾界。 除介绍基本概念外，还给出若干分析实例，如显示如何将不同理论工具应用于支持向量机这种常见机器学习技术。

周志华 教授，南京大学计算机系主任、人工智能学院院长、校学术委员会委员。欧洲科学院外籍院士。人工智能相关五大主流国际学会ACM、AAAI、AAAS、IEEE、IAPR均入选Fellow的首位华人学者，中国计算机学会、中国人工智能学会会士。曾获IEEE计算机学会Edward J. McCluskey技术成就奖、CCF王选奖等。著有《机器学习》（清华大学出版社）等。

王魏，南京大学计算机系副教授。主要研究方向为机器学习理论，曾获中国计算机学会优秀博士学位论文奖、江苏省优秀博士学位论文奖、CCF青年人才发展计划等荣誉。

高尉，南京大学人工智能学院副教授。主要研究方向为机器学习理论，曾获中国计算机学会优秀博士学位论文奖、江苏省优秀博士学位论文奖等荣誉。

张利军，南京大学计算机系副教授、博士生导师。主要研究方向为大规模机器学习与优化，曾获首届达摩院青橙奖、中国科协青年人才托举工程、CCF青年人才发展计划等荣誉。

（1）随着人工智能技术的不断发展和应用，机器学习在近年来备受关注，对机器学习理论感兴趣的专业人士也日益增多。

（2）机器学习理论的主要内容是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。虽然机器学习理论对深入理解机器学习技术非常重要，但由于内容艰深广袤，且来源流派颇为不同，学习难度非常大。

（3）国际上机器学习理论的专业图书很少，往往侧重从理论角度来理解机器学习具体技术，或聚焦于某项具体的学习理论，缺乏全面性和系统性。

（4）本书由机器学习领域著名学者周志华教授领衔的南京大学LAMDA团队四位教授合著，旨在为有志于机器学习理论学习和研究的读者提供一个入门导引。

（5）四位作者梳理出机器学习理论中的七个重要概念或理论工具，除介绍基本概念外，还给出若干分析实例，展示如何应用不同的理论工具来分析具体的机器学习技术。

前言

机器学习近年来备受关注，对机器学习理论感兴趣的人士也日渐增多。然而这方面的专门书籍颇少，中文读物尤甚。

顾名思义，机器学习理论研究的是关于机器学习的理论基础，主要内容是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。 虽然这方面的内容对深入理解机器学习技术甚为重要，但由于内容艰深广袤，既需对机器学习问题有恰当把握，又需相当的数学技巧，且不少内容来源流派颇为不同，不仅初学者感觉难以下手，浸淫多年的学者往往也难纵览全貌。

国际上关于机器学习理论的书籍大致有两类，一类从介绍机器学习具体技术的角度展开，重点在于告诉读者如何从理论角度来理解这些技术，学习理论自身的内容则散见于不同机器学习技术的讨论中。另一类则聚焦于某项具体的学习理论，其他理论内容则需另寻相关读物。

本书试图为有志于机器学习理论学习和研究的读者提供一个入门导引。作者以为，对理论学习和研究来说，弄清楚基础概念和工具尤为重要。因此，本书采取了与上述书籍不同的组织方式。作者梳理出机器学习理论这个“百宝箱”中的七个重要概念或理论工具，姑且称之为“七种武器”，即：可学性、(假设空间)复杂度、泛化界、稳定性、一致性、收敛率、遗憾界。本书每章聚焦其一，除介绍基本概念外，还给出若干分析实例，如展示出怎样应用不同的理论工具来分析支持向量机这种常见机器学习技术。读者今后对具体机器学习问题或技术作分析时，可根据条件选择适用的“武器”。需说明的是，“泛化界”与其他内容并列稍有勉强， 因为书中多种理论工具都可用于泛化界分析；不过，领头作者作为武侠爱好者，实难拒绝致敬《七种武器》的诱惑, 况且泛化界本身还真有那么点神似古龙先生未完成的传说中“什么都能往里装”的第七种武器“箱子”。

本书由四位作者合作完成。周志华规划了全书内容结构并撰写了第1-2章，王魏撰写了第3-4章，高尉撰写了第5-6章，张利军撰写了第7-8章，周志华修订统一了全书风格。机器学习理论内容浩瀚广博，本书虽仅为入门一瞥，成书过程却颇不易。鉴于中文机器学习理论读物之缺乏，周志华在2016年组织LAMDA研究所中专长学习理论的几位教师一起筹备本书。2017年春季在LAMDA内部学习班第一次试讲，大部分学生反映困难。调整内容后，2017年秋季在LAMDA内部第二次试讲，仍有部分学生感觉困难。进一步调整内容后，2018年春季学期在南京大学开设了计算机学科研究生选修课“机器学习理论研究导引”。学期结束后抽样调查显示，约1/3学生感觉难度较大. 再次调整内容后，在2019年春季学期研究生选修课上又讲授一轮，学生反馈情况大致符合预期。于是在2019年中裁定内容，又经半年修改完稿，再于庚子年初之抗疫禁足期间静修定稿。

机械工业出版社华章分社温莉芳和姚蕾二位老师十年前赴宁约稿，此后数次登门、经年常遇，敬业精神令作者感慨。陈朝晖老师友情协助封面设计，使本书蓬荜生辉。完稿校勘时得到赵鹏、吕沈欢、谭志豪、张腾、王璐、吴锦辉等同学协助，在此一并致谢。

需强调的是，本书虽已尽量降低难度, 但由于机器学习理论学习本身的要求，本书读者必须具备较为扎实的理工科高年级本科生的数学知识，至少应该有较好的线性代数、数学分析、概率统计、最优化方法的基础。本书读者还必须具备机器学习的基础知识，至少应该系统性地学习过机器学习的专门性教科书。机器学习理论内容学之不易，且不像机器学习技术工具那样可以立即付诸应用，学习过程难免有焦躁感，自学尤易陷入困局，读者务须有充分的心理准备。但是深入学习下来，不仅有助于理解机器学习的重要思想，更有助于感受和体会这个学科领域的美，一切努力最终都是值得的。

本书虽经多轮试讲修改，但由于每轮均有较多内容调整，且作者学识浅陋，对博大精深之机器学习理论仅略知皮毛，因此书中错谬之处在所难免，若蒙读者诸君不吝指正，将不胜感激。

作者

2020年4月于南京

前言

主要符号表

第1章 预备知识 ……………………………………………………………… 1

1.1 函数的性质 ………………………………………………………………… 1

1.2 重要不等式 ……………………………………………………………… 5

1.3 最优化基础 ……………………………………………………………… 9

1.4 支持向量机 ……………………………………………………………… 13

1.5 理论的作用 ……………………………………………………………… 18

1.6 阅读材料 ………………………………………………………………… 19

习题 ……………………………………………………………………………… 21

参考文献 ………………………………………………………………………… 22

第2章 可学性 ……………………………………………………………… 25

2.1 基本概念 …………………………………………………………………25

2.2 PAC学习 …………………………………………………………………… 26

2.3 分析实例 ………………………………………………………………… 30

2.4 阅读材料 ………………………………………………………………… 35

习题 ……………………………………………………………………………… 36

参考文献 ……………………………………………………………………… 37

第3章 复杂度 ……………………………………………………………39

3.1 数据分布无关 ………………………………………………………… 39

3.2 数据分布相关 ………………………………………………………… 46

3.3 分析实例 ……………………………………………………………… 50

3.4 阅读材料 …………………………………………………………………56

习题 ..……………………………………………………………………………… 58

参考文献 ……………………………………………………………………… 59

第4章 泛化界 ……………………………………………………………… 61

4.1 泛化误差上界 ………………………………………………………… 61

4.2 泛化误差下界 ………………………………………………………… 71

4.3 分析实例 ………………………………………………………………… 78

4.4 阅读材料 ………………………………………………………………… 83

习题 ……………………………………………………………………………… 84

参考文献 ……………………………………………………………………… 86

第5章 稳定性 …………………………………………………………… 89

5.1 基本概念 ………………………………………………………………… 89

5.2 重要性质 ………………………………………………………………… 92

5.3 分析实例 ………………………………………………………………… 98

5.4 阅读材料 ………………………………………………………………… 107

习题 ……………………………………………………………………………… 108

参考文献 ……………………………………………………………………… 110

第6章 一致性 …………………………………………………………… 113

6.1 基本概念 ……………………………………………………………… 113

6.2 替代函数 ……………………………………………………………… 117

6.3 划分机制 ……………………………………………………………… 122

6.4 分析实例 ……………………………………………………………… 125

6.5 阅读材料 ……………………………………………………………… 132

习题 ………………………………………………………………………… 134

参考文献 ………………………………………………………………… 135

第7章 收敛率 …………………………………………………………… 137

7.1 基本概念 ……………………………………………………………… 137

7.2 确定优化 ……………………………………………………………… 139

7.3 随机优化 ……………………………………………………………… 143

7.4 分析实例 ………………………………………………………………155

7.5 阅读材料 ……………………………………………………………… 157

习题 ……………………………………………………………………………… 159

参考文献 ……………………………………………………………………… 161

第8章 遗憾界 …………………………………………………………… 163

8.1 基本概念 ……………………………………………………………… 163

8.2 完全信息在线学习 ……………………………………………… 165

8.3 赌博机在线学习 ………………………………………………….170

8.4 分析实例 ……………………………………………………………184

8.5 阅读材料 …………………………………………………………… 188

习题 …………………………………………………………………………… 189

参考文献 …………………………………………………………………… 191

索引 ………………………………………………………………………… 193