A Faster Algorithm for Learning Decision Trees With Module Nodes
Zhixiang Chen, Xiannong Meng · 1998
One of the challenging problems regarding learn-ing 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 num-ber 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 mod-ule 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) equiv-alence queries and at most s2nT(N) member-ship 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. 1