这是一本基于公理研究学习算法的书。共 17章，由两部分组成。第一部分是机器学习公理以及部分理论演绎，包括第 1、2、6、8 章，论述学习公理以及相应的聚类、分类理论。第二部分关注如何从公理推出经典学习算法，包括单类、多类和多源问题。第 3～5 章为单类问题，分别论述密度估计、回归和单类数据降维。第 7、9～16 章为多类问题，包括聚类、神经网络、 K近邻、支持向量机、Logistic回归、贝叶斯分类、决策树、多类降维与升维等经典算法。最后第 17章研究了多源数据学习问题。

本书可以作为高等院校计算机、自动化、数学、统计学、人工智能及相关专业的研究生教材，也可以供机器学习的爱好者参考。

机器学习的主要目的是从有限的数据中学习到知识，而知识的基本单元是概念。借助于概念，人类可以在繁复的思想与多彩的世界之间建立起映射，指认各种对象，发现各种规律，表达各种想法，交流各种观念。一旦缺失相应的概念，人们将无法思考、交流，甚至无法顺利地生活、学习、工作、医疗、娱乐等。哲学家如卡西尔等甚至认为人类的本质特性是能够使用和创造各种符号概念。因此，如何使机器能够像人一样自动发现、运用概念，正是机器学习的基本研究内容。本书将集中讨论这个问题。

所谓的概念发现，是指从一个给定概念（或者概念集合）的有限外延子集提取对应的概念（或者概念集合）表示，又称归类问题。通过自然进化，人类可以从一个概念（或概念集合）的有限外延子集（有限的对象）中轻松提取概念（或概念集合）自身。对于人类如何处理归类问题，人们已经研究了很多年，发明了许多理论，比如经典概念理论、原型理论、样例理论和知识理论等，积累了很多的研究成果。本书借助认知科学的研究成果，提出了类的统一表示数学模型，以及与之相关的归类问题的统一数学表示。由此提出了类表示公理、归类公理和分类测试公理。据此，本书分别研究了归类结果分类、归类算法分类等诸多问题。特别需要提出的是，本书首次归纳了归类算法设计应该遵循的 4条准则 ——类一致性准则、类紧致性准则、类分离性准则和奥卡姆剃刀准则。在理论上，任何机器学习算法的目标函数设计都遵循上述 4条准则的 1条或者数条。

对于具体的机器学习问题，本书依据奥卡姆剃刀准则，按照归类表示从简单到复杂的顺序，重新进行了组织。本书不仅论述了单类问题比多类问题的归类表示简单，聚类问题比分类问题的归类表示简单，单源数据学习比多源数据学习的归类表示简单，而且对于单类问题、多类问题自身的归类表示复杂度也进行了研究。在此基础上，指出单类问题包括密度估计、回归和单类数据降维等，并借助提出的公理框架以统一的方式演绎推出了在密度估计、回归、数据降维、聚类和分类等问题中常用的机器学习算法。

本书中章节的组织结构都是类似的，特别是与具体学习算法有关的章节。每

章有一个简短的开篇词。如果该章是学习算法章节，该开篇词用来简要说明本章算法的主要设计思想。如果该章是理论章节，该开篇词说明该理论问题的主要目标。每章结尾有延伸阅读或者讨论，延伸阅读提供更深入的相关阅读文献，讨论说明本章的相关内容与分析或者尚未解决的问题。

作者讲授机器学习已十数年，有感于当前的机器学习算法理论依据过多过杂，同时也一直羡慕欧氏几何从五条公理出发导出所有结论的风格。撰写本书，既是将欧氏几何风格移植到机器学习的一个尝试，更是试图为机器学习与模式识别提供一个统一但又简单的理论视角。总之，机器学习公理化这个问题在本书中提出，也在本书中解决了。

于剑 2017年 3月

第 1章引言 .............................................................................................1 

1.1机器学习的目的：从数据到知识 .....................................................1 

1.2机器学习的基本框架 .....................................................................2 

1.2.1数据集合与对象特性表示 .....................................................3 

1.2.2学习判据 ............................................................................4 

1.2.3学习算法 ............................................................................5 

1.3机器学习思想简论 .........................................................................5 延伸阅读 ..............................................................................................7 习题 ....................................................................................................8 参考文献 ..............................................................................................9

第 2章归类理论..................................................................................... 11 

2.1类表示公理 ................................................................................. 13 

2.2归类公理 .................................................................................... 17 

2.3归类结果分类 ............................................................................. 20 

2.4归类方法设计准则 ....................................................................... 22 

2.4.1类一致性准则 ................................................................... 23 

2.4.2类紧致性准则 ................................................................... 23 

2.4.3类分离性准则 ................................................................... 25 

2.4.4奥卡姆剃刀准则 ................................................................ 25 讨论 .................................................................................................. 27 延伸阅读 ............................................................................................ 29 习题 .................................................................................................. 30 参考文献 ............................................................................................ 31

第 3章密度估计..................................................................................... 33 

3.1密度估计的参数方法 ................................................................... 33 

3.1.1最大似然估计 ................................................................... 33 

3.1.2贝叶斯估计 ....................................................................... 35 

3.2密度估计的非参数方法 ................................................................ 39 

3.2.1直方图 ............................................................................. 39 

3.2.2核密度估计 ....................................................................... 39 

3.2.3 K近邻密度估计法 ............................................................ 40 延伸阅读 ............................................................................................ 40 习题 .................................................................................................. 41 参考文献 ............................................................................................ 41

第 4章回归 ........................................................................................... 43 

4.1线性回归 .................................................................................... 43 

4.2岭回归 ....................................................................................... 47 

4.3 Lasso回归 .................................................................................. 48 讨论 .................................................................................................. 51 习题 .................................................................................................. 52 参考文献 ............................................................................................ 52

第 5章单类数据降维 .............................................................................. 53 

5.1主成分分析 ................................................................................. 54 

5.2非负矩阵分解 ............................................................................. 56 

5.3字典学习与稀疏表示 ................................................................... 57 

5.4局部线性嵌入 ............................................................................. 59 

5.5典型关联分析 ............................................................................. 62 

5.6多维度尺度分析与等距映射 ......................................................... 63 讨论 .................................................................................................. 65 习题 .................................................................................................. 66 参考文献 ............................................................................................ 66

第 6章聚类理论..................................................................................... 69 

6.1聚类问题表示及相关定义 ............................................................. 69 

6.2聚类算法设计准则 ....................................................................... 70 

6.2.1类紧致性准则和聚类不等式 ............................................... 70 

6.2.2类分离性准则和重合类非稳定假设 ..................................... 72 

6.2.3类一致性准则和迭代型聚类算法 ......................................... 73 

6.3聚类有效性 ................................................................................. 73 

6.3.1外部方法 .......................................................................... 73 

6.3.2内蕴方法 .......................................................................... 75 延伸阅读 ............................................................................................ 76 习题 .................................................................................................. 77 参考文献 ............................................................................................ 77

第 7章聚类算法..................................................................................... 81 

7.1样例理论：层次聚类算法 ............................................................. 81 

7.2原型理论：点原型聚类算法 .......................................................... 83 

7.2.1 C均值算法 ...................................................................... 84 

7.2.2模糊 C均值 ...................................................................... 86 

7.3基于密度估计的聚类算法 ............................................................. 88 

7.3.1基于参数密度估计的聚类算法 ............................................ 88 

7.3.2基于无参数密度估计的聚类算法 ......................................... 97 延伸阅读 .......................................................................................... 106 习题 ................................................................................................ 107 参考文献 .......................................................................................... 108

第 8章分类理论................................................................................... 111 

8.1分类及相关定义 ........................................................................ 111 

8.2从归类理论到经典分类理论 ....................................................... 112 

8.2.1 PAC理论 ....................................................................... 113 

8.2.2统计机器学习理论 ........................................................... 115 

8.3分类测试公理 ........................................................................... 118 讨论 ................................................................................................ 119 习题 ................................................................................................ 119 参考文献 .......................................................................................... 120

第 9章基于单类的分类算法：神经网络 .................................................. 121 

9.1分类问题的回归表示 ................................................................. 121 

9.2人工神经网络 ........................................................................... 122 

9.2.1人工神经网络相关介绍 .................................................... 122 

9.2.2前馈神经网络 ................................................................. 124 

9.3从参数密度估计到受限玻耳兹曼机 ............................................. 129 

9.4深度学习 .................................................................................. 131 

9.4.1自编码器 ........................................................................ 132 

9.4.2卷积神经网络 ................................................................. 132 讨论 ................................................................................................ 133 习题 ................................................................................................ 134 参考文献 .......................................................................................... 134

第 10章 K近邻分类模型 ...................................................................... 137 

10.1 K近邻算法 ............................................................................. 138 

10.1.1 K近邻算法问题表示 .................................................... 138 

10.1.2 K近邻分类算法 .......................................................... 139 

10.1.3 K近邻分类算法的理论错误率 ...................................... 140 

10.2距离加权最近邻算法 ................................................................ 141 

10.3 K近邻算法加速策略 ............................................................... 142 

10.4 kd树 ...................................................................................... 143 

10.5 K近邻算法中的参数问题 ......................................................... 144 延伸阅读 .......................................................................................... 145 习题 ................................................................................................ 145 参考文献 .......................................................................................... 145

第 11章线性分类模型 .......................................................................... 147 

11.1判别函数和判别模型 ................................................................ 147 

11.2线性判别函数 .......................................................................... 148 

11.3线性感知机算法 ...................................................................... 151 

11.3.1感知机数据表示 ........................................................... 151 

11.3.2感知机算法的归类判据 ................................................. 152 

11.3.3感知机分类算法 ........................................................... 153 

11.4支持向量机 ............................................................................. 156 

11.4.1线性可分支持向量机 .................................................... 156 

11.4.2近似线性可分支持向量机 ............................................. 159 

11.4.3多类分类问题 .............................................................. 162 讨论 ................................................................................................ 164 习题 ................................................................................................ 165 参考文献 .......................................................................................... 166 

第 12章对数线性分类模型 ................................................................... 167 

12.1 Softmax回归 .......................................................................... 167 

12.2 Logistic回归 ........................................................................... 170 讨论 ................................................................................................ 172 习题 ................................................................................................ 173 参考文献 .......................................................................................... 173

第 13章贝叶斯决策 ............................................................................. 175 

13.1贝叶斯分类器 .......................................................................... 175 

13.2朴素贝叶斯分类 ...................................................................... 176 

13.2.1最大似然估计 .............................................................. 178 

13.2.2贝叶斯估计 ................................................................. 181 

13.3最小化风险分类 ...................................................................... 183 

13.4效用最大化分类 ...................................................................... 185 讨论 ................................................................................................ 185 习题 ................................................................................................ 186 参考文献 .......................................................................................... 186

第 14章决策树 .................................................................................... 187 

14.1决策树的类表示 ...................................................................... 187 

14.2信息增益与 ID3算法 ............................................................... 192 

14.3增益比率与 C4.5算法 .............................................................. 194 

14.4 Gini指数与 CART算法 ........................................................... 195 

14.5决策树的剪枝 .......................................................................... 196 讨论 ................................................................................................ 197 习题 ................................................................................................ 197 参考文献 .......................................................................................... 198

第 15章多类数据降维 .......................................................................... 199 

15.1有监督特征选择模型 ................................................................ 199 

15.1.1过滤式特征选择 ........................................................... 200 

15.1.2包裹式特征选择 ........................................................... 201 

15.1.3嵌入式特征选择 ........................................................... 201 

15.2有监督特征提取模型 ................................................................ 202 

15.2.1线性判别分析 .............................................................. 202 

15.2.2二分类线性判别分析问题 ............................................. 202 

15.2.3二分类线性判别分析 .................................................... 203 

15.2.4二分类线性判别分析优化算法 ....................................... 205 

15.2.5多分类线性判别分析 .................................................... 205 延伸阅读 .......................................................................................... 207 习题 ................................................................................................ 207 参考文献 .......................................................................................... 207

第 16章多类数据升维：核方法 ............................................................. 209 

16.1核方法 .................................................................................... 209 

16.2非线性支持向量机 ................................................................... 210 

16.2.1特征空间 ..................................................................... 210 

16.2.2核函数 ........................................................................ 210 

16.2.3常用核函数 ................................................................. 212 

16.2.4非线性支持向量机 ....................................................... 212 

16.3多核方法 ................................................................................ 213 讨论 ................................................................................................ 215 习题 ................................................................................................ 215 参考文献 .......................................................................................... 216

第 17章多源数据学习 .......................................................................... 217 

17.1多源数据学习的分类 ................................................................ 217 

17.2单类多源数据学习 ................................................................... 217 

17.2.1完整视角下的单类多源数据学习 ................................... 218 

17.2.2不完整视角下的单类多源数据学习 ................................ 220 

17.3多类多源数据学习 ................................................................... 221 

17.4多源数据学习中的基本假设 ...................................................... 222 讨论 ................................................................................................ 222 习题 ................................................................................................ 223 参考文献 .......................................................................................... 223

后记 ........................................................................................................ 225

索引 ........................................................................................................ 229 

机器学习是本次人工智能热潮的核心技术。引起轰动的应用如AlphaGo等,都可以看到机器学习的身影。目前，机器学习理论纷繁复杂，算法形式花样百出。人们一直在疑惑，机器学习，特别是其中的深度学习的本质到底是什么？

作者积二十年研究之力，将各种学习理论融于一体，提出了五条学习公理，据此推导出了常见的学习算法，包括深度学习。如果想要知道机器学习的本质，快速理清各种学习算法之间的关系，本书是一条不容错过的终南捷径。

想要知道机器学习（包括深度学习）的本质吗？想要知道各种学习算法之间的关系吗？请读本书。