Bottom-Up Induction of Oblivious Read-Once Decision Graphs: Strengths and Limitations

Machine Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Decision-Tree Learning

We report improvements to HOODG, a supervised learning algorithm that induces concepts from labelled instances using oblivious, read-once decision graphs as the underlying hypothesis representation structure. While it is shown that the greedy approach to variable ordering is locally optimal, we also show an inherent limitation of all bottom-up induction algorithms, including HOODG, that construct such decision graphs bottom-up by minimizing the width of levels in the resulting graph. We report our empirical experiments that demonstrate the algorithm’s generalization power.