Recursive partition tree

 

  
Figure 8: The distributions of class ``1'' and ``2''. The MDFs from a single level does not work well for this case.

For a complicated problem, the overall feature set may not be best for specific pairs of classes. It has been shown that when many variables are included, the MDFs may do extremely well in classifying the observations in the two training samples, but perform worse in classifying new observations than a set of MDFs based on fewer variables. Another problem is that in general, the criterion does not work well when the distributions are multimodal as illustrated in 8. A distribution of samples from one hand sign obtained under various lighting conditions and viewing directions usually is multimodal. In order to handle this situation, we propose a hierarchal structure.

Our hierarchal structure shares many common characteristics with the well known tree classifiers and the regression trees in the mathematics community [7], the hierarchical clustering techniques in the pattern recognition community [22, 28] and the decision trees or induction trees in the machine learning community [36]. The major differences between our tree and those traditional trees are:

1. Our automatically derives features directly from training images, while all the traditional trees work on a human pre-selected set of features.
2. The traditional trees either (a) at each internal node, search for a partition of the corresponding samples to minimize a cost function (e.g., ID3 [36] and clustering trees [28]), or (b) simply select one of the remaining unused features as the splitter (e.g., the k-d tree). Option (a) results in an exponential complexity that is way too computationally expensive for learning from high-dimensional input like images. Option (b) implies selecting each pixel as a feature, which simply does not work for image inputs (in the statistics literature, it generates what is called a dishonest tree [7]). Our tree directly computes the most discriminating features (MDF), using the Fisher's multi-class, multi-dimensional linear discriminant analysis [22, 26, 42], for recursive space partitioning at each internal node.

• Construction of recursive partition tree
• Approximation for recognition