Learning k μ decision trees on the uniform distribution
Thomas R. Hancock · 1993
We present a polynomial time algorithm that PAC learns kp decision trees on the uniform distribution for an arbitrary constant k (a p decision tree tests each attribute on a single node, and a kp decision tree tests each attribute on at most k different nodes).The algorithm produces a hypothesis that is a decision tree (t bough not necessarily k~).The algorithm haa the flavor of empirical decision tree algorithms in that it builds a hypothesis by choosing variables on which to split and then recursively solves smaller problems without backtracking.1