Decision trees: equivalence and propositional operations
Hans Zantema · Utrecht University Repository (Utrecht University) · 1998
. For the well-known concept of decision trees as it is used for inductive inference we study the natural concept of equivalence: two decision trees are equivalent if and only if they represent the same hypothesis. We present a simple efficient algorithm to establish whether two decision trees are equivalent or not. The complexity of this algorithm is bounded by the product of the sizes of both decision trees. The hypothesis represented by a decision tree is essentially a boolean function, just like a proposition. Although every boolean function can be represented in this way, we show that disjunctions and conjunctions of decision trees can not efficiently be represented as decision trees, and simply shaped propositions may require exponential size for representation as decision trees. 1 Introduction The problem of inductive inference, or shortly induction, in machine learning ([7]) can be described as follows. Roughly speaking, a number of observations each having an outcome, has to ...