A Faster Algorithm for Learning Decision Trees with Module Nodes

Ninth Midwest Artificial intelligence and Cognitive Science Conference

Volume

Ninth Midwest Artificial intelligence and Cognitive Science Conference

Contents

One of the challenging problems regarding learning decision trees is whether decision trees over the domain Z~, in which each internal node is labeled by a module function axi(mod N) for some i E (1 .... ,n), are efficiently learnable with equivalence and membership queries [5]. Given any decision tree T, let s be the number of its leaf nodes. Let N = p~l...p~ be its prime decomposition, and let 7(N) = (tl 1)... (t~ + 1). We show that when all the module functions in T have the same coefficient, then there is a polynomial time algorithm for learning T using at most s(s + 1)7(N) equivalence queries and at most s2nT(N) membership queries. Our algorithm is substantially more efficient than the algorithm designed in [7] for learning such decision trees. When N is a prime, our algorithm implies the best-known algorithm in [4] for learning decision trees over a finite alphabet.