3-树学习

1. 概念学习 Concept Learning

1.1. 推理

• 演绎（正向）推理：已知，P为真，则Q为真
• 反绎（溯因/反向）推理：已知，Q为真，则P为真
• 归纳推理：已知前件为真，后件未必为真

符号学习（概念学习）是一类归纳推理

1.2. 定义

• 定义：给定样例集合，以及每个样例是否属于某个概念，自动地推断出该概念的一般定义

1.3. 学习任务

sunny+Rainy+cloudy

实例集合X
目标概念c：定义在实例集上的布尔函数
训练样例：正例，反例
假设集H：每个假设h表示X上定义的布尔函数

概念学习：寻找一个假设h，使得

最一般假设：$$
最特殊假设：

1.4. 假设的一般到特殊序

更泛化：令和是定义在上的布尔函数，若当且仅当，

泛化：属性约束更弱
特化：属性学习更强

1.5. Find-S算法：寻找极大特殊假设

1. 将h初始化为H中最特殊的假设
2. 对每个正例x
   • 对h的每个属性约束，如果x满足，那么不做任何处理
   • 否则将h中的替换成x满足的另一个最一般的约束

对属性以合取式表示的假设空间,输出与正例一致的最特殊假设

1.6. 列表消除算法:List-Then-Eliminate

1.6.1. 算法过程

1. 变型空间(假设空间中所有假设的列表)
2. 对每个样例
   • 从变型空间中移除的假设
3. 输出的假设列表

要列出所有假设,不太现实

1.6.2. 变型空间

• 一致
  • 一个假设与训练样例集合一致
• 变型空间
• 极大泛化
• 极大特化

1.6.3. 变型空间表示定理

1.7. 候选消除算法:Candidate-Eliminate

正例用于泛化集合，搜索集合
反例用于特化集合，缩小集合

• 一致：对每个假设h都符合当前见过的所有样本(h与D一致)

2. 归纳偏置

原假设空间时合取式（有偏，与），而真实空间时由析取式（无偏，或） 表示
无偏无法使用，无法进行泛化

幂集：集合的所有子集的集合

2.1. 定义

• 核心
  • 学习器从训练样例中泛化并推断新实例分类过程中所采用的策略
• 精确定义：
  • 学习器的归纳偏置为符合的前提集合B，通过B，则归纳推理可由演绎推理派生

2.2. 不同归纳偏置

• 有偏程度不同的三种归纳学习算法

  1. 机械式学习器
  2. 候选消除算法
     • 偏置：所有的样本一定在假设空间里
  3. FIND-S

• 有偏性

  • 无归纳偏置
  • +任何实例，除非可以有其他先验推出，否则都为反例

有偏性越强，则学习器的归纳能力越强

3. 决策树学习

3.1. 特点

• 特点
  • 实例：属性-值 对表示
  • 目标函数具备离散的输出值
  • 很好的健壮性（样例可以包含错误，缺少属性值）
  • 可以学习析取表达式
  • 推理具备可解释性
• 算法
  • ID3,C4.5
  • 搜索一个完整表示的假设空间，表示为多个If-then规则(可解释性)
• 归纳偏置：
  • 优先选择较小的树，保证了在析取空间也具备泛化能力

3.2. 问题设置

可能的实例集，未知的目标函数，假设函数集

输入：未知目标函数的训练实例
输出：最佳近似f的假设

• 算法框架
  • 处理基本情况
  • 寻找最好的分类属性𝐴𝐴𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏
  • 用𝐴𝐴𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏建立一个节点划分样例
  • 递归处理每一个划分，作为其子节点/子树

3.3. 假设空间搜索

从一个假设空间中搜索一个正确拟合训练样例的假设。
搜索的假设空间就是可能的决策树的集合。
从简单到复杂的爬山算法遍历假设空间。
从空的树开始，然后逐步考虑更加复杂的假设。
引导爬山搜索的评估函数是信息增益度量

3.4. ID3算法

• 算法表示：

• 过程：

1. 创建树的Root节点
2. 如果Examples的目标属性均为正，那么返回label=”+”的单节点树Root
3. 如果Examples的目标属性均为反，那么返回label=”-“的单节点树Root
4. 如果Attributes为“空”，那么返回单结点树Root，label设置为Examples中最普遍的目标属性值
5. 如果Attributes不为“空”
   • 中分类Examples能力最好的属性
   • Root的决策属性
   • 对A的每个可能取值
     • 令为Examples中满足A属性值为的子集
     • 若Example为空(特殊情况)
       • 分支下加一个叶子节点,节点label设置为Examples中最普遍的目标属性值
     • 否则,这个分支下加一个子树
6. 否则,返回树Root

3.5. 如何选择最佳属性

• 信息增益:衡量给定的属性区分训练样例的能力
• 熵
  • 信息度量,刻画样例集的纯度
  • • 代表样例集合分为正样本和负样本

如果S的所有样本都属于同一类,则可以算出熵为0

3.6. 信息增益

3.7. 算法特点

1. 假设空间:包含所有决策树
2. 遍历过程:仅维持单一的当前假设
   • 不同于变型空间候选消除算法（维持满足训练样例的所有假设）
   • 如何评价其他候选假设
3. 回溯:不回溯
   • 局部最优解
4. 基于统计
   • 对错误样例不敏感
   • 不适用增量处理,只能离线处理

3.8. 决策树学习的归纳偏置

• 优先选择信息增益高的属性接近根结点的树

符号学习算法:限定偏置,构造合取式的假设空间

3.9. 奥卡姆剃刀

• 不是简单的选择最简化的假设，而是推理所依据的是使可证伪的假设的数目更少
  • eg.简历上写精通C++,很容易被证伪.不如不写.

4. 其他树算法

4.1. C4.5

• 属性取值越多,信息增益越大,但并不代表属性本身越好
• 使用信息增益比度量
  • 从信息增益高于平均水平的属性中选择增益率最高的

4.2. CART算法

与ID3 C4.5不同,CART构造的是二叉树

4.2.1. Gini指数

• 使用Gini指数度量: 对模型纯度的度量,越小越好,越小纯度越高
  • 不用对数计算
  • 只需要计算比例

: 样本集合中属于第类样本子集

• 基尼指数和熵正相关,很接近,可以近似代表分类的误差率
• 基尼指数和熵都表示集合的混乱程度,可以作为叶子节点的损失

4.2.2. 属性选择指标(回归)

• 对回归问题: 采用方差和度量

4.2.3. 连续值处理

C4.5基于信息增益比离散化，CART是基于基尼系数离散化。

4.2.4. 离散值处理

• 对离散值,采用不停的二分离散特征

4.3. 代表线性树算法对比

4.4. 剪枝处理

• 完全生长的树缺乏泛化能力
• 后剪枝:从完全生长的决策树的底端剪去一些子树，使决策树变小 （模型简单），从而增强泛化能力
  • 避免过强拟合