Data Dependent Risk Bounds and Algorithms for Hierarchical Mixture of Experts Classiflers
Arik Azran · 2004
According to the Oxford dictionary, a pattern is defined as a way in which something happens and the noun recognize is described as knowing, (being able to) identify again (a person or a thing) that one has seen, heard, etc before. Thus, by recognizing a pattern we identify something that is similar to something that we saw in the past. Pattern Recognition is about guessing the unknown nature of an observation as one out of a set of possibilities. In this work an observation is a collection of numerical measurements, denoted by x, where x ∈ R. The unknown nature of the observation is referred to as the label, denoted in this work by y, where y ∈ {0, 1}. In pattern recognition a mapping f : R 7→ {0, 1} is defined. This mapping is referred to as the classifier. There are many ways in which classifiers can be defined. One possibility is the Hierarchical Mixture of Experts classifier, which is in the focus of our discussion. The Hierarchical Mixture of Experts classifier is given by a recursive soft partition of the feature space R in a datadriven fashion. Such a procedure enables local classification where several experts are used, each of which is assigned with the task of classification over some subspace of the feature space. In this work, we provide data-dependent error bounds for this class of models, which lead to effective procedures for performing model selection. Tight bounds are particularly important here, because the model is highly parameterized. The theoretical results are complemented with some numerical experiments based on a randomized algorithm, which mitigates the effects of local minima that plague other approaches such as the expectationmaximization algorithm.