REx: Learning A Rule and Exceptions

We propose a method where the dataset is explained as a "rule" and a set of "exceptions" to the rule. The rule is a parametric model valid over the whole input space and exceptions are nonparametric and local. This approach is applicable both to function approximation and classification. We explain how the rule and exceptions can be learned using cross-validation. We investigate three ways of combining the rule and exceptions: (1) In a multistage approach, if the rule is confident of its output, we use it; otherwise, output is interpolated from a table of stored exceptions. (2) In a multiexpert approach, the exceptions are defined as gaussian units just like in a radial-basis functions network; the rule can be seen as a parametric input-dependent offset to which the gaussian exceptions are added. (3) The rule and exceptions can be written as a mixture model like in Mixtures of Experts and they can be combined in a cooperative or competitive manner. The system can be trained using a gradient based, or in the case of (3) EM, algorithm. The model can be combined with Hidden Markov models for sequence processing. We analyse REx as an arcing method and compare it with bagging and boosting. The proposed approaches are tested on several datasets in terms of generalization accuracy, memory requirement, and training time with significant performance.

ICSI Technical Report TR-97-040

Technical Report