目录
本文是对人工智能基础的期末复习知识总结。
一、绪论
什么是人工智能？
从模拟人的角度来说，可以通过认知建模的过程让机器学会像人一样思考，可以以通过图灵测试为目标让机器具有和人一样的行为；而让机器模拟人并不是我们的目的，这里学习人工智能的是让机器具备理性（rationality），指的是通过思维法则的途径让机器学汇理性的思考，通过理性Agent的构造让机器具有理性的行为。这是四个维度不同层面的解释。
发展历史就不谈了，整体上是以十年为一个周期的发展态势，没意思。
什么是图灵测试？
图灵测试由Alan Turing在1950年提出，内容可以简单描述为，由一个人类询问者提出一些书面问题之后，无法判断书面回答是来自计算机还是人类，就说这台计算机通过了图灵测试。图灵测试是一个至今仍合适的测试，人工智能的研究者并没有一直致力于让计算机通过图灵测试，研究智能的基本原理比复制人类智能或让计算机模拟人更加重要。
人工智能的研究范围有哪些？
知识表示（语义网络等）、搜索技术（博弈树搜索等）、非经典逻辑&非经典推理（时序逻辑等&类比推理等）、机器学习（统计学习等）、自然语言理解（语法学等）、知识工程（专家系统等）、定理机器证明（归纳法等）、人工生命（细胞自动机等）、机器人（传感器数据融合等）、AI语言（Lisp/Prolog等）。
二、Agent
什么是Agent？
Agent是可以感知环境并且在环境中行动的东西。
Agent通过传感器感知环境，通过执行器对环境产生影响。Agent收到的所有输入数据的历史序列叫做感知序列，Agent在任何时可的行动选择依赖于到那个时刻为止该Agent的感知序列。Agent=体系结构+程序，体系结构就是图上所表现的，具备传感器和执行器的计算装置，计算装置上运行着Agent程序，程序实现的是从感知序列映射到行为的Agent函数。
Agent函数描述了Agent的行为，可以通过表格描述，Agent函数是抽象的数学描述，Agent程序是具体的实现。
什么是理性Agent？
理性Agent是做事正确的Agent，这是个很模糊的概念，准确来说，**理性Agent是对每一个可能的感知序列，根据已知的感知序列提供的证据和Agent具有的先验知识，理性Agent应该选择能使其性能度量最大化的行动。**所谓性能度量就是对Agent行为的评价，具体问题具体分析。以吸尘器的例子为例，性能度量是一定时间段内清理的灰尘总量，另外还有其他度量指标，比如保持干净地面加分，能耗高噪声大则减分。
这里有一个讲到的点，理性≠全知/完美，全知/完美是让实际的性能最大化，可以预见行动产生的实际结果并作出相应的动作，而理性只是将期望中的性能最大化。
如何构建理性Agent？
Agent要从环境中通过传感器收集信息，通过程序做出合理的行动指示，才能通过执行器对环境做出符合预期的行为。那么构建理性Agent就有三方面任务，第一是收集准确且足够的环境信息，第二是有合适的体系结构包括传感器和执行器，第三也是最关键的，是要设计出满足AI需求的Agent程序。
在书中24和25章才讲到了传感器和执行器，就不提了，主要学的是设计Agent程序。
首先要尽可能完全地定义任务环境，也就是明确Agent要解决的基本问题，然后是简单了解4种基本的Agent程序。
Ⅰ.任务环境描述–PEAS（Performance 性能 Environment 环境 Actuators 执行器 Sensors 传感器）
比如：
| Agent类型 | 性能度量P | 环境E | 执行器A | 传感器S |
|---|---|---|---|---|
| Taxi driver | 安全、快捷、合法、舒适性、利润最大化 | 道路、其他车辆、行人、乘客 | 方向盘、油门、刹车、车灯、喇叭、显示输出设备 | 摄像头、声呐、车速表、GPS、里程表、加速度计、乘客输入设备 |
Ⅱ.任务环境的性质
完全可观察的
传感器在每个时刻都能获取环境的完整状态，
若传感器能检测所有与行动决策相关的信息，则称为有效完全可观察的。
部分可观察的
噪声、传感器不够精确、传感器丢失了部分数据，则环境是部分可观察的。
单Agent、多Agent
环境中如果有多个对象，那么多个对象的行为是否依赖于其他对象的性能度量。
确定的、随机的
如果环境的下一个状态完全取决于当前状态和Agent执行的动作，则该环境是确定的，
否则，是随机的，也就是说后果是不确定的，可以用概率来量化。
片段式的
Agent的经历被分成一个一个的片段，下一个片段不依赖于以前的片段中采取的行动。
延续式的
当前的决策会影响到所有未来的决策。
静态的
环境在Agent计算的时候不会发生变化，
Agent在决策时不需要观察环境，也不需要顾虑时间流逝。
动态的
环境在Agent计算的时候会变化，
会持续的要求Agent做决策。
半动态的
环境本身不随时间变化，而性能度量随时间变化。
离散的、连续的
指环境的状态、时间的处理方式，以及Agent的感知信息和行动，
如出租车Agent的环境的状态就是连续的，随时间而变化，驾驶行动也是连续的。
已知的、未知的
指Agent的知识状态，
在已知环境中，Agent行动的所有后果是给定的。
在未知环境中，Agent需要学习环境是如何工作的，以便做出更好的决策。
Ⅲ.Agent程序
输入参数：从传感器得到的当前感知信息；返回值：执行器的行动决策。
这里有四种基本的Agent程序。
简单反射Agent
简单反射Agent，最简单的Agent – 基于当前的感知选择行动，不关注感知历史。仅仅根据当前感知的环境信息匹配规则，得出行为决策。
环境必须是完全可观察的。
基于模型的反射Agent
基于模型的反射Agent，在简单反射Agent根据当前感知的环境信息决策的基础上，结合当前的信息和过去内部状态得到当前行为决策。内部状态是靠感知历史维持的，会加入世界如何发展，行动会如何影响世界如何产生结果的信息。
可处理部分可观察的环境。
基于目标的Agent
基于目标的Agent，在基于模型的反射Agent根据当前感知的环境信息决策+过去内部状态的基础上，结合模型和增加的目标信息，同时记录世界的状态和目标集合，根据目标灵活改变行动序列来达成目标，方式包括搜索和规划。
基于效用的Agent
基于效用的Agent，在基于目标的基础上加入对效用的评价，追求对达到目标的最优化途径，通过效用函数决策。
可用在部分可观察和随机的环境中处理不确定性的决策。
三、搜索
上文的基于目标的Agent程序提到了，这类问题的解法会根据目标灵活地找出一个行动序列，而采用的方法是搜索或是规划，规划不学，以后有时间自学，这里搜索是一个大章，我尽量理解清晰，用简洁的语言总结清楚。
通过搜索求解问题
1.经典搜索
Ⅰ.无信息搜索
Ⅱ.有信息搜索
2.局部搜索
3.对抗搜索/博弈
4.约束满足问题(CSP)
四、机器学习
可能会考一个概念，监督学习、无监督学习和强化学习，怎么准确地描述出来。这里只分析一下监督学习和无监督学习，考到的概率挺大。
监督学习是我们对输入样本经过模型训练后有明确的预期输出，非监督学习就是我们对输入样本经过模型训练后得到什么输出完全没有预期。
监督学习是通过已有的一部分输入数据与输出数据之间的对应关系，生成一个函数，将输入映射到合适的输出，例如分类，而无监督学习是直接对数据进行建模，例如聚类。
监督学习是Agent观察某些“输入→输出”样例，学习从输入到输出的映射函数，训练集是带有类标签的，新的数据基于训练集进行分类；无监督学习是Agent学习输入中的模式，训练集是没有类标签的，提供一组属性，然后寻找出训练集中存在的类别或者聚集，新的数据基于聚类算法分出的类别进行归类；强化学习是Agent在强化序列（奖励和惩罚组合的序列）中学习。
1.监督学习
主要是分类问题，解决分类问题的模型也可以用来解决回归问题，比如随机森林构建500棵决策树，每颗决策树有10个叶子节点，也就是10个Label平均值，那么这个随机森林只可能预测出≤5000个可能值，可以说是划分得足够细的分类，达到了回归的效果。
Ⅰ.决策树
决策树是一个树状结构的分类器，用节点和边表示分类过程，以属性描述集合和相应数据作为输入，输出通常是一个分类，中间节点表示对某个属性的测试，叶节点则表示一个类别。分为分类树和回归树，取决于输入的属性是离散还是连续。
决策树例子
决策树的使用
如何生成决策树是一个重点，下面详细说，先理解生成了怎么用。
使用决策树时，输入是某个实例的属性数据，从根节点开始逐层向下，在根节点及每个中间节点，根据该节点的各条邻接边上采用的划分属性及该实例的该属性取值，选择其中一个分支，直到到达叶节点，就是最终分类了。
像这样通过把实例从根节点根据实例他本身的对应属性和边上的选择属性，排列到某个叶结点来分类实例，就能输出该实例所在的类别。
决策树的生成
总的来说，所有的决策树生成算法都是–决策树生成时，在每个中间节点选一个属性进行划分，根据属性的取值划分为不同的子树，直到不能划分。
算法通常是两个步骤：
- 树的生成
- 全部数据聚集在根节点
- 采用某种算法（宽度优先、递归等）生成树，关键是如何选取下一个属性以及属性如何划分
- 在每个中间节点选择某一个属性进行划分，直到不能继续划分
- 树的修剪
- 去掉一些可能是噪音或者异常的数据
关键是如何选取下一个属性以及属性如何划分，算法的区别主要就在这，另一个关键是确定何时停止划分。除了划分方式和停止时间之外，如何避免监督学习的过拟合也十分关键。下面就讨论这仨问题：
决策树停止生长一般有三种情况，1.当前节点包含的样本已经属于同一个类别了；2.当前属性集空了，能划分的属性都划分完了；3.节点里面所有的样本在所有属性上取值都相同，唯独分类不同，也无法继续划分；4.样本空了，纵使有这个属性也无法划分。
怎么在节点上选择划分哪个属性呢？
树和子树根节点的划分算法，都要让节点随着树生长，其中样本趋于同一类别，即节点的纯度（purity）越来越高。量化纯度的算法有很多，比如ID3 C4.5 CART等算法，
以ID3为例，首先计算出根节点的信息熵，再算出每个属性的信息增益，选信息增益大的作为节点的划分属性，这里我理解的信息增益就是对样本来说区分度最大的属性。C4.5用的是信息增益率，CART用的是基尼值，指的是随机抽取样本类别不一样的概率，基尼指数越小表示纯度越高越适合作为划分属性。总之划分节点选择的属性，找的是划分之后最大限度地减少分类的可能性的那个属性。
过拟合是模型泛化能力差，对训练集拟合度高而预测准确率低的情况，避免过拟合，可以通过剪枝进行优化，也可以通过下一个算法，基于决策树的随机森林进行优化。
剪枝分为预剪枝和后剪枝，分别是划分节点前进行估计预测，当前节点能否提升泛化能力；先生成决策树再Bottom-up地进行考察，如果把当前节点变成叶节点泛化能力可以提升就将子数变成叶节点。
这里偷个懒，贴一下课程ppt的图。
首先预剪枝，划分出训练集和测试集，这里的测试集用来评估精度，事对泛化能力的评估。
预剪枝的优缺点有，
-
优点
- 降低了过拟合的风险
- 显著减少了决策树的训练时间开销和预测试时间开销
-
缺点
- 有些分支的当前划分虽不能提升泛化能力、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高
- 预剪枝基于“贪心”，禁止这些分支展开，带来了欠拟合的风险
然后是后剪枝，
-
优点
- 欠拟合风险很小，泛化性能往往优于预剪枝决策树
-
缺点
- 后剪枝过程是在生成完全决策树之后进行的，并且要自底向上对树中的所有非叶节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多
后剪枝决策树通常比预剪枝决策树保留了更多的分支，而预剪枝使得很多分支都没有展开，增加了欠拟合的风险，但是后剪枝的时间开销比预剪枝大得多。
Ⅱ.随机森林
随机森林的算法包含了决策树的生成，一般是CART算法构造。
随机森林有几个特点
2.无监督学习
主要是聚类问题。