发帖
雷达卡
摘要翻译：
自顶向下的决策树归纳已经被观察到由于剪枝阶段的功能不足而受到影响。特别是，已知得到的树的大小随样本量线性增长，即使树的精度没有提高。减少误差剪枝是一种算法，已被用作解释决策树学习问题的代表性技术。在本文中，我们提出了三种不同设置下的减少误差剪枝的分析。首先，我们研究了该方法的基本算法性质，独立于输入决策树的性质和剪枝实例。然后我们考察了一种情况，这种情况直观地会导致所考虑的子树被叶节点替换，在这种情况下，修剪示例的类标签和属性值是相互独立的。本分析是在两种不同的假设下进行的。一般分析表明，拟合纯噪声的节点的剪枝概率受一个函数的约束，该函数随树的大小呈指数递减。在一个具体的分析中，我们假设例子是均匀分布到树中的。这个假设让我们可以近似得到被剪枝的子树的数量，因为它们没有收到任何剪枝示例。本文阐明了减少误差剪枝算法的不同变体，对其算法性质有了新的认识，在分析该算法时引入了较少的假设，并将以前忽略的空子树引入到分析中。
---
英文标题：
《An Analysis of Reduced Error Pruning》
---
作者：
T. Elomaa, M. Kaariainen
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Top-down induction of decision trees has been observed to suffer from the inadequate functioning of the pruning phase. In particular, it is known that the size of the resulting tree grows linearly with the sample size, even though the accuracy of the tree does not improve. Reduced Error Pruning is an algorithm that has been used as a representative technique in attempts to explain the problems of decision tree learning. In this paper we present analyses of Reduced Error Pruning in three different settings. First we study the basic algorithmic properties of the method, properties that hold independent of the input decision tree and pruning examples. Then we examine a situation that intuitively should lead to the subtree under consideration to be replaced by a leaf node, one in which the class label and attribute values of the pruning examples are independent of each other. This analysis is conducted under two different assumptions. The general analysis shows that the pruning probability of a node fitting pure noise is bounded by a function that decreases exponentially as the size of the tree grows. In a specific analysis we assume that the examples are distributed uniformly to the tree. This assumption lets us approximate the number of subtrees that are pruned because they do not receive any pruning examples. This paper clarifies the different variants of the Reduced Error Pruning algorithm, brings new insight to its algorithmic properties, analyses the algorithm with less imposed assumptions than before, and includes the previously overlooked empty subtrees to the analysis.
---
PDF链接：
https://arxiv.org/pdf/1106.0668
京公网安备 11010802022788号
