1.1.2 机器学习

机器学习是人工智能的一个重要分支，并逐渐成为推动人工智能发展的关键因素。学习是人类具有的一种重要的智能行为，但如何准确定义学习，长期以来众说纷纭。社会学家、逻辑学家和心理学家各有其不同的看法。按照西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或改进，使得系统在下一次执行相同任务或类似任务时，会比现在做得更好或效率更高。

对于机器学习，至今还没有形成统一的定义，确实也很难给出一个公认和准确的定义。为了便于讨论和估计学科的进展，有必要对机器学习给出定义，即使这种定义是不完备的和不充分的。

定义1.1 顾名思义，机器学习是研究如何使用机器模拟人类学习活动的一门学科。

定义1.2 机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。

定义1.3 机器学习是用数据或以往的经验优化计算机程序的性能标准。

定义1.4 A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P，if its performance at tasks in T，as measured by P，improves with experience E.

综合上述定义，给出如下定义。

定义1.5 机器学习是研究机器模拟人类的经验、学习活动、获取知识和技能的理论与方法，以改善系统性能的学科。

机器学习是近20多年来兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为机器学习算法中涉及大量的统计学理论，机器学习与统计推断学联系尤为密切，所以也被称为统计学习理论。在算法设计方面，机器学习理论关注可以实现的、行之有效的学习算法。很多推论问题都是难以用特征工程（Feature Engineering）表示的，因此，部分机器学习研究是开发容易处理的近似算法。

1.机器学习的数学表述

机器学习（Machine Learning，ML）是指从有限的观测数据中总结出具有一般性的规律，并利用这些规律对未知数据进行预测。机器学习的目的是根据给定的训练样本求得某系统输入与输出之间的依赖关系的估计，使得机器学习能够对未知输出做出尽可能准确的预测。机器学习问题在数学上可以表述为“一个基于经验数据的函数估计问题”。最常见的最小二乘法数据拟合问题可以看作机器学习的一个最简单的实例，通过对已知数据进行学习，预测未知数据点处的函数值，从这个问题中可以看出机器学习的基本思想，如图1-1所示。

机器学习问题可以更一般地表示为：变量y与x存在一定的未知依赖关系，即遵循某一未知的联合概率分布F（x，y）（y和x之间的确定性关系可以看作其特例）。机器学习问题就是根据n个独立同分布观测样本

在一组函数{f（x，w）}中求一个最优函数f（x，w₀），对依赖关系进行估计，使期望风险

最小。其中，w为函数的广义参数；{f（x，w）}称为预测函数集，可以表示任何函数集；L[y，f（x，w）]为用f（x，w）对y进行预测而造成的损失，用来度量学习方法对实际函数关系的逼近程度。不同类型的机器学习问题有不同形式的损失函数。预测函数也称为学习函数、学习模型或学习机器。

对于机器学习，更一般的数学描述可参见图1-2，各部分的含义如下。

（1）G为产生器，产生随机向量x，从固定但未知的概率分布函数F（x）中独立抽取。

（2）S为训练器，对于每一个输入向量x返回一个输出值y，根据固定但未知的条件概率分布函数F（y|x）产生。

（3）LM为函数学习机，能够实现一定的函数集f（x，w），函数学习的过程即特征处理的过程，包括特征提取和特征转换，其中w∈Λ，Λ是参数集合。

对该模型而言，机器学习问题就是从给定的函数集f（x，w）中选择能够更好地逼近训练器的相应函数，即使用期望风险最小的函数。这种选择是基于训练集的，训练集由根据联合概率分布函数F（x，y）=F（x）F（x|y）抽取出的n个独立同分布观测样本（x₁，y₁），（x₂，y₂），…，（x_n，y_n）组成。

有3类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。

对于模式识别问题，输出y是类别标号，对于两类别分类问题，y∈[-1，1]，预测函数称为指示函数，损失函数可以定义为

风险最小就是在贝叶斯决策中使错误率最小。

在函数逼近问题中，y是连续变量（这里假设为单值函数），损失函数可以定义为

即采用最小平方误差准则。

对于概率密度估计问题，学习的目的是根据训练样本确定x的概率密度。记估计的密度函数为p（x，w），此时损失函数可以定义为

在上面的问题表述中，学习的目标在于使期望风险最小。但是，由于可利用的信息只有式（1-1）所示的样本，式（1-2）的期望风险无法计算，因此，在传统的学习方法中，采用了经验风险，即

作为对式（1-2）的估计，设计学习算法使经验风险最小。上述原则称为经验风险最小化（Empirical Risk Minimization，ERM）归纳原则，简称ERM原则。

2.机器学习的相关理论

在理解机器学习的过程中，有几个非常重要的理论需要熟悉，有助于更好地掌握机器学习。

（1）PAC学习理论。

可能近似正确（Probably Approximately Correct，PAC）学习理论是机器学习的理论基础。机器学习的实质就是用优化算法从假设空间中选择一个假设，能够符合给定的数据描述。而PAC学习（PAC Learning）实际上只要求学习算法能以一定的概率学习到一个近似正确的假设。一种PAC可学习（PAC-Learnable）的算法是指该学习算法能够在多项式时间内，从合理数量的训练数据中学习到一个近似正确的f（x，w）。

PAC学习可满足以下两点。

① 近似正确（Approximately Correct）：一个假设f∈H是“近似正确”的是指其泛化误差（Generalization Error）小于一个界限ϵ。ϵ一般为0到之间的数，即。如果泛化误差比较大，则说明该模型不能用来做正确的“预测”。

② 可能正确（Probably Correct）：一种学习算法有“可能”以1-δ的概率学习到一个“近似正确”的假设。δ一般为0到之间的数，即。

因此，PAC学习可以表示为

P((R(f)-R_emp(f))≤ϵ)≥1-δ

其中，ϵ、δ是与样本数量N及假设空间H相关的变量。为了提高模型的泛化能力，通常需要正则化（Regularization）来限制模型复杂度。

PAC学习理论也可以帮助分析一种机器学习算法在什么条件下可以学习到一个近似正确的分类器。如果样本数量，就能保证模型在当前条件下是可学习的。如果希望模型的假设空间越大，泛化误差越小，那么需要的样本数量就越多。

（2）没有免费午餐定理。

没有免费午餐（No Free Lunch，NFL）定理是由Wolpert和Macerday在最优化理论中提出的。没有免费午餐定理证明：对于基于迭代的最优化算法，不存在某种算法对所有问题（在有限的搜索空间内）都有效。如果某算法对某些问题有效，那么它一定在另外一些问题上比纯随机搜索算法的效果更差。也就是说，不能脱离具体问题来谈论算法的优劣，任何算法都有局限性，必须要“具体问题具体分析”。没有免费午餐定理对机器学习算法同样适用。不存在一种机器学习算法适合任何领域或任务。如果有人宣称自己的模型在所有问题上都优于其他模型，那么肯定是虚假的。

（3）奥卡姆剃刀原理。

奥卡姆剃刀（Occam's Razor）原理是由逻辑学家William of Occam提出的一个解决问题的法则：“如无必要，勿增实体”。奥卡姆剃刀的思想和机器学习中的正则化思想十分类似：简单模型的泛化能力更好。也就是说，如果有两个性能相近的模型，那么应该选择更简单的模型。因此，在机器学习的学习规则上，经常会引入参数正则化来限制模型的泛化能力，避免过拟合。奥卡姆剃刀的一种形式化是最小描述长度（Minimum Description Length，MDL）原则，即对于一个数据集D，最好的模型f∈H会使数据集的压缩效果最好，即编码长度最小。

最小描述长度也可以通过贝叶斯学习的观点来解释。模型f在数据集D上的对数后验概率为

其中，-log p（f）和-log p（D|f）可以分别看作模型f的编码长度与在该模型下数据集D的编码长度。也就是说，我们不仅要使模型f可以编码数据集D，还要使模型f尽可能简单。

（4）丑小鸭定理。

丑小鸭定理（Ugly Duckling Theorem）是在1969年由渡边慧提出的。这里的“丑小鸭”是指白天鹅的幼雏，而不是“丑陋的小鸭子”。丑小鸭定理即“丑小鸭和白天鹅之间的区别与两只白天鹅之间的区别一样大”。这个定理初看好像不符合常识，但是仔细思考后是非常有道理的。因为世界上不存在相似性的客观标准，一切相似性的标准都是主观的。如果从体型大小或外貌的角度来看，丑小鸭和白天鹅之间的区别大于两只白天鹅之间的区别；但是如果从基因的角度来看，丑小鸭与其父母之间的差别要小于其父母与其他白天鹅之间的差别。

3.机器学习的主要分类

如果按照学习的方式分类，那么机器学习主要可分为监督学习、无监督学习、半监督学习、强化学习。

（1）监督学习。

监督学习（Supervised Learning）表示机器学习的数据是带标记的，这些标记可以包括数据类别、数据属性及特征点位置等。这些标记作为预期效果，不断修正机器的预测结果。

具体实现过程是：首先通过大量带有标记的数据训练机器，机器将预测结果与期望结果进行比对；接着根据比对结果修改模型中的参数，再一次输出预测结果；然后将预测结果与期望结果进行比对，重复多次，直至收敛；最终生成具有一定鲁棒性的模型来实现智能决策的能力。

常见的监督学习有分类、回归和结构化学习。

分类（Classification）是指将一些实例数据分到合适的类别中，其预测结果是离散的。

回归（Regression）是指将数据归到一条“线”上，即为离散数据生成拟合曲线，因此其预测结果是连续的。

结构化学习（Structured Learning）是一种特殊的分类问题，这一类标签数据通常是结构化的对象，如序列、树或图等。

（2）无监督学习。

无监督学习（Unsupervised Learning）表示机器学习的数据是没有标记的。机器从无标记的数据中探索并推断出潜在的联系。

常见的无监督学习有聚类和降维。

在聚类（Clustering）工作中，由于事先不知道数据类别，因此只能通过分析数据样本在特征空间中的分布，如基于密度或基于统计学概率模型等，从而将不同数据分开，把相似数据聚为一类。

降维（Dimensionality Reduction）是指将数据的维度降低。例如，要描述一个西瓜，若只考虑外皮颜色、根蒂、敲声、纹理、大小及含糖率这6个属性，则这6个属性表示西瓜数据的维度为6。进一步考虑降维，由于数据本身具有庞大的数量和各种属性特征，若对全部数据信息进行分析，则会增加训练的负担和存储空间，因此可以通过主成分分析等其他方法，考虑主要影响因素，舍弃次要因素，从而平衡准确度与效率。

（3）半监督学习。

监督学习往往需要大量的标注数据，而标注数据的成本比较高，因此可以利用大量的无标注数据来提高学习的效率。这种利用少量标注数据和大量无标注数据进行学习的方式称为半监督学习（Semi-Supervised Learning）。常用的半监督学习算法有自训练和协同训练。

（4）强化学习。

强化学习（Reinforcement Learning）是一类通过智能体和环境的交互不断学习并调整策略的机器学习算法。这种算法带有一种激励机制，如果智能体根据环境做出的一个动作是正确的，则将施予一定的“正激励”；如果动作是错误的，则会给出一个惩罚（也可称为“负激励”）。通过不断地累加激励，以期获得激励最大化的回报。

强化学习最为火热的应用就是谷歌AlphaGo的升级品——AlphaGo Zero。相较于AlphaGo，AlphaGo Zero舍弃了先验知识，不再需要人为设计特征，直接将棋盘上黑、白棋子的摆放情况作为原始数据输入模型中，机器使用强化学习来自我博弈，不断提升自己，最终出色地完成下棋任务。AlphaGo Zero的成功证明，在没有人类的经验和指导下，深度强化学习依然能够出色地完成指定任务。