Tree Learning

1. Symbolic/Concept Learning & Version Space

1.1. Symbolic Learning

符号学习是一类归纳推理

• 演绎 (正向) 推理: $P\land (P\to Q)\Rightarrow Q$
• 反绎 (溯因/反向) 推理: $(Q\land (P\to Q))\to P$
• 归纳推理: $P\land (P\to Q)\not\Rightarrow Q$

1.2. Concept Learning

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

Formally, for

• a set of instances $X$,
• a target concept $c^*:X\to\{T, F\}$,
• training examples $D=\{(x_1, c^*(x_1)), (x_2, c^*(x_2)), \cdots, (x_m, c^*(x_m))\}$,
• a hypothesis set $H$ of functions, $\forall h\in H(h:X\to \{T,F\})$,

the concept learning problem is to find a hypothesis $h\in H$ such that

$$\forall x\in X, h(x)=c^*(x) $$

2. Inductive Bias

归纳偏置

归纳推理/机器学习不得不考虑下面的几个基本的问题:

• 目标概念假设不在假设空问怎么办？
• 能设计包含所有假设的空间吗？
• 假设空间大小对未见实例的泛化能力有什么影响？
• 假设空间大小对所需训练样例数量有什么影响？

3. ID3 Algorithm

3.1. Decision Tree Learning

实例：“属性-值”对表示，应用最广的)纳推理算法之一
，目标函数具有离散的输出值
，很好的健壮性(样例可以包含错误，也可以处理缺少属性值的实例）
丷能够学习析取表达式
口算法
V ID3, Assistant, C4.5
，搜索一个完整表示的假设空间，表示为多个Ifthen规则
口归纳偏置
，优先选择较小的树

Information Gain

我的这篇数据科学笔记记录了更多关于信息熵部分的知识

4. Other Tree Algorithms

简单直观，生成的决策树很直观。相比于神经网络之类的黑盒分类模型，
决策树在逻辑上可以很好解释。
口基本不需要预处理，不需要提前归一化和处理缺失值。既可以处理离散值
也可以处理连续值。很多算法只是专注于离散值或者连续值。
口可以处理多维度输出的分类问题。
口使用决策树预测的代价是0（109211)。m为样本数。
口可以交叉验证的剪枝来选择模型，从而提高泛化能力。
口对于异常点的容错能力好，健壮性高。

树学习算法缺点
口树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本
数量和限制决策树深度来改进。
口决策树会因为样本发生一点的改动，导致树结构的剧烈改变。可以通过集
成学习之类的方法解决。
口寻找最优的决策树是一个NP难题，通过启发式方法，容易陷入局部最优。
可以通过集成学习的方法来改善。
口比较复杂的关系(如异或），决策树很难学习。一般这种关系只能用其他学
习方法(如神经网络)来解决。
口如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。可以通
过调节样本权重来改善。