机器学习
一个智能体程序的各个组件都可以通过机器学习进行改进，而学习则是面对未知环境的重要方法。改进及用于改进的技巧取决于下面几个因素：● 哪些组件可以被改进；● 智能体有哪些先验知识，这将影响模型构建；● 有哪些数据，以及关于这些数据的反馈。
从一组特定的观测结果得出一个普遍的规则，称之为归纳。例如，观察到过去的每一天太阳都会升起，因此推断太阳明天也会升起。这与逻辑中研究的演绎不同，因为归纳的结论可能是不正确的，然而在演绎中，只要前提是正确的，演绎的结论就保证是正确的。
当输出是一个有限集合中的某个值时（如晴天/阴天/雨天或者正确/错误），称该学习问题为分类（$classifica$$tion$）。当输出是一个数值时（例如明天的温度，无论它是一个整数还是其他实数），称该学习问题为回归（$regression$）。伴随输入有 3 种类型的反馈，它们决定了 3 种类型的学习：
在监督学习中，智能体观测到输入-输出对，并学习从输入到输出的一个函数映射。举个例子来说，输入是照
相机的图像，伴随输入的输出就是“公共汽车”或者“行人”等。诸如此类的输出，称之为标签。在智能体学习到一个函数之后，如果给它一个新的图像输入，它将预测一个合适的标签。
在无监督学习中，智能体从没有任何显式反馈的输入中学习模式。最常见的无监督学习任务是聚类：通过输入样例来检测潜在的有价值的聚类簇。例如，互联网上可以有数百万个图像，一个计算机视觉系统可以识别一大类相似的、被人类称为“猫”的图像。
在强化学习中，智能体从一系列的强化——奖励与惩罚——中进行学习。举例来说，在一局国际象棋比赛结束时，智能体会被告知它赢了（奖励）还是输了（惩罚）。智能体判断之前采取的哪个动作该为这一结果负责，并且改变它的动作以在未来得到更多的奖励。
函数$h$被称为关于世界的假设，它取自一个假设空间$H$，其中包含所有可能的函数。同样地，也可以称$h$是关于数据的模型，它取自模型类$H$，也可以说它取自函数类中的一个函数。称输出$y_i$为真实数据——人们总是希望模型能预测的正确答案。
那么，如何选择一个假设空间呢？最开始可能有一些关于数据生成过程的先验知识。如果没有的话，可以采用探索性数据分析：通过统计检验和可视化方法——直方图、散点图、箱形图——来探索数据以获得对数据的一些理解，以及洞察哪些假设空间可能是合适的。或者可以直接尝试多种不同的假设空间，然后评估哪个假设空间的效果最好。
有了假设空间后，如何从中选择一个好的假设呢？人们希望寻找一个一致性假设：假设$h$，对训练集中的任意一个$x_i$，都有$h(x_i) = y_i$。如果输出是连续值，则不能期望模型输出与真实数据精确匹配；相反，可以寄希望于寻找一个最佳拟合函数，使得每一个$h(x_i)$与$y_i$非常接近。
衡量一个假设的标准不是看它在训练集上的表现，而是取决于它如何处理尚未观测到的输入。可以使用一个测试集——第二组样本数据对$(x_i, y_i)$——来评估假设。如果$h$准确地预测了测试集的输出，则称$h$具有很好的泛化能力。
分析假设空间的一个方法是分析它们带来的偏差（不考虑训练集）和它们产生的方差（从一个训练集到另一个训练集）。偏差（$bias$）是指（不严格地）在不同的训练集上，假设所预测的值偏离期望值的平均趋势。偏差常常是由假设空间所施加的约束造成的。例如，当假设空间是线性函数时会导致较大的偏差：它只允许函数图像是一条直线。如果数据中除了直线的整体斜率以外还存在别的模式，线性函数将无法表示其他的模式。当一个假设不能找到数据中的模式时，称它是欠拟合（$underfitting$）的。但是，分段线性函数具有较小的偏差，其函数的形状是由数据决定的。
方差（$variance$）是指由训练数据波动而导致假设的变化量。下图两行所使用的数据集采样于同一个函数$f(x)$。两个数据集略有不同。对前三列函数来说，数据集的略微不同导致的假设差别比较小，称之为低方差的。但是第$4$列中的$12$次多项式函数则具有较大方差：可以看到它们在$x$轴两端的表现差别很大。显然，这两个多项式中至少有一个多项式对正确的函数$f(x)$的拟合效果较差。当一个函数过于关注它用来训练的特定训练数据集，进而导致它在没有见过的数据上表现较差时，称该函数对数据集是过拟合（$overfitting$）的。
通常这其中存在一个偏差-方差权衡（$bias$-$variance$ $tradeoff$）：在更复杂、低偏差的能较好拟合训练集的假设与更简单、低方差的可能泛化得更好的假设中做出选择。阿尔伯特·爱因斯坦曾于 1933 年说过，“任何理论的终极目标都是尽可能让不可削减的基本元素变得更加简单且更少，但也不能放弃对任何一个单一经验数据的充分阐释”。换句话说，爱因斯坦建议选择与数据相符的最简单的假设。这个原则可以追溯到 14 世纪的英国哲学家奥卡姆的威廉，他的原则“如无必要，勿增实体”被称为奥卡姆剃刀原则，因为它被用来“剔除”含糊的解释。
决策树
决策树表示了这么一类函数——它将属性值向量映射到单个输出值（即“决策”）。决策树通过执行一系列测试来实现其决策，它从根节点出发，沿着适当的分支，直到到达叶节点为止。树中的每个内部节点对应于一个输入属性的测试，该节点的分支用该属性的所有可能值进行标记，叶节点指定了函数要返回的值。
对许多问题，决策树会给出一个漂亮、简洁、容易理解的结果。实际上，许多内容为“如何……”的指南手册（如，汽车维修）都会按决策树形式来撰写。但有些函数并不能被简洁地表示，例如投票函数，当且仅当超过一半的输入为真时，它的输出为真，它需要指数量级大小的决策树来表示。事实上，决策树对一些函数来说是好表示的，而对另一些函数来说却是不合适的。是否存在一种表示方式使得任何函数都能被有效地表示？遗憾的是，答案是否定的——函数的形式过多，无法用少量的位来全部表示。
一般来说，任何训练集都有一个一致的决策树，要寻找一棵理论上最小且与样本一致的树是很困难的。但通过一些简单的启发式方法，可以高效地寻找一棵与最小的树接近的树。$Learn$-$Decision$-$Tree$算法采用贪心与分治的策略：总是首先测试当前最重要的属性，然后递归地去解决由该测试结果可能产生的更小的子问题。“最重要的属性”指的是对一个样例的分类结果能产生最大影响的属性。这样的话，通过少量的测试就有可能得到正确的分类结果，这意味着该树中的所有路径都比较短，整棵树的层数也比较浅。
如果分割后没有任何其他的属性剩余，但是存在正负两种样例，这意味着，这些样例有完全相同的属性值组合，但分类不同。这是可能发生的，或是因为数据中存在错误或噪声，或是因为该领域是非确定性的，再或是因为无法观测到可以区分样例的属性。此时的最好的选择就是返回剩余样例中最常见的输出值。
其思想核心类似于熵权法，也是采用了信息熵的概念。与熵权法有所区别的是在决策树中，信息熵是对事件中不确定的信息的度量，不确定信息越大，信息熵越大。一个系统的信息熵计算公式如下（其中 表示事件发生的概率）：
$$
E\left( p \right) =-\sum_i{p_i\cdot \log _2p_i}
$$
接下来引入信息增益的概念，这也是 ID3 算法的核心内容。信息增益是指一个事件中前后的不同信息之间的差值，通过信息增益的计算可以构建一个将信息熵逐渐降低的决策树，从而使不确定性达到最小，信息增益的计算公式如下：
$$
Gain\left( P_1,\ P_2 \right) =E\left( P_1 \right) -E\left( P_2 \right)
$$
在决策树的构建过程中通过计算$Gain\left( O,\,\,P_k \right) $来选择分类特征，其中$O$是指最终类别。分类完成后递归地使用信息增益方法进行计算，直到完全区分开所有类别。特别的，特征$k$的信息增益计算公式如下：
$$
E\left( P_k \right) =\sum_i{\frac{\left| p_{ki} \right|}{\left| P_k \right|}\cdot E\left( p_{ki} \right)}
$$
使用$cart$算法建立的决策树是一个二叉树，其既可做分类，亦可做回归；采用基尼指数来选择节点，一般在决策树构建完成后需要进行剪枝。由于$cart$算法的结构是二叉树，因此各个特征的分类应该为两类，即需要对数据进行特殊处理，在$cart$算法中常称为分支方法。
对于离散型数据：选择特征下的一种情况进行二分；对于连续型数据：选择中间值进行区分。由此引出另一个问题：即如何选择合适的划分方法。要确定最优特征首先应该找到最优切分点。$cart$算法先对连续值进行离散化，然后根据基尼指数来确定最优切分点进而确定最优特征。对于连续型数据，将在数据集$A$中某个连续型特征$P_k$的$m$个取值从小到大排列，遍历每个元素之间，选择中间值作为划分并计算基尼不纯度，基尼不纯度最小的划分对应的切分点就是最优切分点。基尼指数的计算公式为：
$$
Gini=1-\sum_i{p_{i}^{2}}
$$
基尼不纯度的计算公式为：
$$
Gini_{root}\left( T \right) =\frac{S_1}{S_1+S_2}\cdot Gini\left( T_1 \right) +\frac{S_2}{S_1+S_2}\cdot Gini\left( T_2 \right)
$$
分得子树以后递归地使用基尼指数计算，直到完全区分类别。
较大的假设空间（例如，具有更多节点的决策树）具有更强的拟合和过拟合能力，某些模型类比其他模型类更容易过拟合。对决策树来说，一种称为决策树剪枝的技术可以用于减轻过拟合。剪枝通过删去不明显相关的节点来实现，通常用统计学中的显著性检验来判断。
此外，信息增益和基尼指数不是等价的，但大多数时候它们的区别很小，信息增益对较混乱的集合有很好的表现力，但是基尼指数有所欠缺。另一方面，这也说明较纯的集合，基尼指数可能会区分得更清楚。
连续属性与多值输入属性：对于连续属性，可能每个样例都有不同的属性值。用信息增益来衡量属性将导致这样的属性得到理论上最高的信息增益，最终给出一棵以该属性为根的浅层树，其中每个可能值对应一个单样例子树。但是当需要对一个新的样例进行分类，且样例的该属性值并没有被观测过时，这棵树对分类没有帮助。处理连续值的一个更好的方法是采用分割点测试——一个关于属性值的不等式测试。找到好的分割点的有效方法是：首先对属性的值进行排序，然后只考虑将具有不同分类结果的两个相邻样例之间的值作为可能的分割点，同时以分割点得到的正负样例作为新样例继续算法。分割的实现是实际决策树学习应用中代价最高的部分。
连续值输出属性：如果要预测一个数值类型的输出，那么需要的是一棵回归树，而不是一棵分类树。回归树在每个叶节点上都有一个关于数值属性子集的线性函数，而不是一个单一的输出值。举个例子来说，两居室公寓的价格最终可能以一个关
于占地面积和浴室数量的线性函数输出。学习算法必须能够决定何时停止对树进行分割并开始对属性应用线性回归。
决策树有很多优点：易于理解，可推广到大型数据集，处理离散输入和连续输入及分类和回归问题的多功能性。然而，它们的精确度可能是次优的（主要是由贪心搜索导致），并且如果树很深，那么在调用树为一个新的样例进行预测时可能会有昂贵的运行代价。决策树也是不稳定的（unstable），因为仅添加一个新的样例，就可能更改根上的测试结果，从而更改整个树。随机森林模型可以解决这些问题中的一部分。
