On the Practice of Branching Program Boosting

Branching programs are a generalization of decision trees. From the viewpoint of boosting theory the former appear to be exponentially more efficient. However, earlier experience demonstrates that such results do not necessarily translate to practical success. In this paper we develop a practical version of Mansour and McAllester’s [13] algorithm for branching program boosting. We test the algorithm empirically with real-world and synthetic data. Branching programs attain the same prediction accuracy level as C4.5. Contrary to the implications of the boosting analysis, they are not significantly smaller than the corresponding decision trees. This further corroborates the earlier observations on the way in which boosting analyses bear practical significance.