On learning decision trees with large output domains (extended abstract)
Nader H. Bshouty, Christino Tamon, David K. Wilson · 1995
For two disjoint sets of variables, X and l', and a class of functions (', we define DT(X, Y, C') to be the class of all decision trees over X whose leaves are functions from C over Y.We study the learnability of _DT(X, Y, C') using membership ,aud equivalence queries.Boolean decision trees, LIT(.Y, @, {O, 1}), were shown to be exactly learnable in [Bs93 ] but does this imply the learnability of decision trees that have non-boolean leaves?A simple encoding of atl possible leaf values will work provided that the size of C is reasonable.Our investigation involves several cases where simple encoding is not feasible, i.e., when ICl is large, We show how to learn decision trees whose leaves