【人工智能：现代方法】第19章：样例学习

• 智能体学习（learning）：一个智能体通过对世界进行观测来提高它的性能
• 机器学习（machine learning）：智能体是一台计算机 —— 一台计算机观测到一些数据，基于这些数据构建一个模型（model），并将这个模型作为关于世界的一个假设（hypothesis）以及用于求解问题的软件的一部分

为什么希望一台机器进行学习？

• 程序的设计者无法预见未来所有可能发生的情形
• 有时候设计者并不知道如何设计一个程序来求解目标问题——大多数人都能辨认自己家人的面孔，但是他们实现这一点利用的是潜意识

1 学习的形式

• 归纳（induction）：从一组特定的观测结果得出一个普遍的规则—— 归纳的结论可能是不正确【只要前提是正确的，演绎（deduction）的结论就保证是正确的】
• 分类（classification）：输出是一个有限集合中的某个值时
• 回归（regression）：输出是一个数值

根据输入有3种类型的反馈（feedback），学习可分为3类：

• 监督学习（supervised learning）：智能体观测到输入-输出对，并学习从输入到输出的一个函数映射 —— 输出称之为标签（label）
• 无监督学习（unsupervised learning）：智能体从没有任何显式反馈的输入中学习模式；最常见的无监督学习任务是聚类（clustering）
• 强化学习（reinforcement learning）中：智能体从一系列的强化——奖励与惩罚——中进行学习，智能体判断之前采取的哪个动作该为这一结果负责，并且改变它的动作以在未来得到更多的奖励

2　监督学习

监督学习的任务：

• 给定一个训练集（training set）含有N个“输入-输出”对样例： ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) , . . . , ( x N , y N ) (x_1,y_1),(x_2,y_2),(x_3,y_3),...,(x_N,y_N) (x1​,y1​),(x2​,y2​),(x3​,y3​),...,(xN​,yN​)
• 每一对数据都由一个未知的函数 y = f ( x ) y=f(x) y=f(x)生成
• 目标：寻找一个函数 h h h来近似真实的函数 f f f

• 函数 h h h ：关于世界的假设（hypothesis），取自一个包含所有可能的函数 假设空间（hypothesis space） H \mathcal{H} H【其他说法，模型-模型类，函数-函数类】
• 输出 y i y_i yi​：真实数据（ground truth）

如何选择一个假设空间

• 关于数据生成过程的先验知识【如果有的话】
• 采用探索性数据分析（exploratory data analysis）：通过统计检验和可视化方法——直方图、散点图、箱形图——来探索数据以获得对数据的一些理解，以及洞察哪些假设空间可能是合适的
• 直接尝试多种不同的假设空间，然后评估哪个假设空间的效果最好

如何从假设空间中选择一个好的假设

• 寻找一个一致性假设（consistent hypothesis）：假设 h h h ，对训练集中的任意一个 x i x_i xi​，都有 h ( x i ) = y i h(x_i) = yi h(xi​)=yi
• 如果输出是连续值，不能期望模型输出与真实数据精确匹配,而是寻找一个最佳拟合函数（best-fit function），使得每一个 h ( x i ) h(x_i) h(xi​)与 y i y_i yi​非常接近
• 衡量一个假设的标准不是看它在训练集上的表现，而是取决于它如何处理尚未观测到的输入：使用一个测试集（test set）—— 如果 h h h 准确地预测了测试集的输出，称 h h h 具有很好的泛化（generalize）能力

如何分析假设空间：

• 偏差（bias）：（不严格地）在不同的训练集上，假设所预测的值偏离期望值的平均趋势： - 常常是由假设空间所施加的约束造成的，如假设空间是线性函数时会导致较大的偏差，分段线性函数具有较小的偏差- 欠拟合（underfitting）：一个假设不能找到数据中的模式
• 方差（variance）：由训练数据波动而导致假设的变化量 - 过拟合（overfitting）：一个函数过于关注它用来训练的特定训练数据集，进而导致它在没有见过的数据上表现较差
• 偏差-方差权衡（bias-variance tradeoff）：在更复杂、低偏差的能较好拟合训练集的假设与更简单、低方差的可能泛化得更好的假设中做出选择

• 奥卡姆剃刀原则（Ockham’s razor）：如无必要，勿增实体

表达能力与复杂性的权衡：

• 表达性语言使简单的假设能够与数据相匹配
• 限制语言的表达能力则意味着任何一致性假设都必定是复杂的

3 决策树学习

决策树（decision tree）：将属性值向量映射到单个输出值（即“决策”）的函数

• 决策树通过执行一系列测试来实现其决策：从根节点出发，沿着适当的分支，直到到达叶节点为止
• 树中的每个内部节点对应于一个输入属性的测试，该节点的分支用该属性的所有可能值进行标记，叶节点指定了函数要返回的值

3.1 决策树的表达能力

• 命题逻辑中的任何函数都可以表示为决策树

一棵布尔型的决策树的逻辑语句：

•                                          O                               u                               t                               p                               u                               t                               ⇔                               （                               P                               a                               t                                           h                                  1                                          ∨                               P                               a                               t                                           h                                  2                                          ∨                               …                               ）                                      Output \Leftrightarrow （Path_1 \vee Path_2 \vee …）                        Output⇔（Path1​∨Path2​∨…）
  

•                                          P                               a                               t                                           h                                  i                                                 Path_i                        Pathi​：根节点到true叶节点的路径上的属性-值测试形式                                                         A                                  m                                          =                                           v                                  x                                          ∧                                           A                                  n                                          =                                           v                                  y                                          ∧                               …                               ）                                      A_m = v_x \wedge A_n = v_y \wedge …）                        Am​=vx​∧An​=vy​∧…）的合取
  

• 所有的决策树将空间分割为矩形，即与坐标轴平行的方框
• 不存在一种表示方式使得任何函数都能被有效地表示

最重要的属性：对一个样例的分类结果能产生最大影响的属性