能够通过ID3算法的搜索空间和搜索策略深入认识这个算法的优势和不足。
1) ID3算法中的如果空间包括全部的决策树， 避免了搜索不完整如果空间(说明一下：有些算法是搜索不完整如果空间的、详细參考<<机器学习>>这本书)的一个主要风险：如果空间可能不包括目标函数。
2) 当遍历决策树空间时,ID3仅维护单一的当前如果。由于仅考虑单一的如果,ID3算法失去了表示全部一致如果所带来的优势。(说明一下：意思就是说它不能推断有没有其它的决策树也是与现有的训练数据一致的。或者使用新的实例查询来最优地区分这些竞争如果)
3) 在搜索中不进行回溯。
每当在树的某一层次选择了一个属性进行測试,它不会再回溯又一次考虑这个选择。所以,它易受无回溯的爬山搜索中常见风险影响:收敛到局部最优的答案,但不是全局最优的。
4) 搜索的每一步都使用当前的全部训练例子,以统计为基础决定怎样精化当前的如果。
这与那些基于单独的训练例子递增作出决定的方法不同。使用全部例子的统计属性(比如,信息增益)的一个长处是大大减小了对个别训练例子错误的敏感性。
1从观測到的训练数据泛化以分类未见实例的策略是什么呢？
换句话说,它的归纳偏置是什么？
如果给定一个训练例子的集合,那么通常有非常多决策树与这些例子一致。
所以,要描写叙述ID3 算法的归纳偏置,应找到它从全部一致的如果中选择一个的依据。
ID3从这些决策树中选择哪一个呢?它选择在使用简单到复杂的爬山算法遍历可能的树空间时遇到的第一个可接受的树。
概略地讲,ID3的搜索策略为
a) 优先选择较短的树而不是较长的
b) 选择那些信息增益高的属性离根结点较近的树。
在ID3 中使用的选择属性的启示式规则和它遇到的特定训练例子之间存在着微妙的相互作用,由于这一点。非常难准确地刻划出ID3 的归纳偏置。然而我们能够近似地把它的归纳偏置描写叙述为一种对短的决策树的偏好。
近似的ID3 算法归纳偏置:较短的树比較长的优先
其实,我们能够想象一个相似于ID3的算法,它精确地具有这样的归纳偏置。考虑一种算法,它从一个空的树開始广度优先搜索逐渐复杂的树,先考虑全部深度为1 的树,然后全部深度为2的,......。
一旦它找到了一个与训练数据一致的决策树,它返回搜索深度的最小的一致树(比如,具有最少结点的树)。让我们称这样的广度优先搜索算法为BFS-ID3。
BFS-ID3寻找最短的决策树,因此精确地具有“较短的树比較长的得到优先”的偏置。ID3可被看作BFS-ID3的一个有效近似,它使用一种贪婪的启示式搜索企图发现最短的树,而不用进行完整的广度优先搜索来遍历如果空间。
由于ID3 使用信息增益启示式规则和“爬山”策略,它包括比BFS-ID3更复杂的偏置。尤其是,它并不是总是找最短的一致树,而是倾向于那些信息增益高的属性更靠近根结点的树。
ID3 归纳偏置的更贴切近似:
较短的树比較长的得到优先。那些信息增益高的属性更靠近根结点的树得到优先。
奥坎姆剃刀:优先选择拟合数据的最简单如果。
为什么应该优先选择较简单的如果呢?科学家们有时似乎也遵循这个归纳偏置。比如物理学家优先选择行星运动简单的解释,而不用复杂的解释。对这个问题并没有一个确定性的定论和证明、有兴趣的能够參考相关资料。
1. 避免过度拟合数据