The haar wavelet motif relating decision trees, neural networks, and rule-exception sets
Dhananjay S. Phatak, Rory G. Mulvaney · 2013
This work presents a three-fold adaptation of the Haar Discrete Wavelet Transform (DWT), demonstrating its modification to efficiently transform a multiclass- (rather than numerical-) valued function over a multidimensional (rather than low dimensional) domain, or transform a multiclass-valued decision tree into another useful representation. It is proven that this multidimensional, multiclass DWT uses dynamic programming to minimize (within its framework) the number of nontrivial wavelet coefficients needed to summarize a training set or decision tree. It is a spatially-localized algorithm that takes linear time in the number of training samples, after a sort. Convergence of the DWT to benchmark training sets seems to degrade with rising dimension in this test of high dimensional wavelets, which have been seen as difficult to implement. This multiclass multidimensional DWT has tightly coupled applications from learning dyadic decision trees directly from training data, rebalancing or converting pre-existing decision trees to fixed depth boolean or threshold neural networks (in effect parallelizing the evaluation of the trees), or learning rule-exception sets represented as a new form of tree called an E-tree, which could greatly help interpretation/visualization of a dataset.