Modular learning through output space decomposition

The modular learning paradigm is extended to the previously unexplored, but potentially useful, problem decomposition framework in which a C > 2 class problem is systematically decomposed into simpler two-(meta)class problems.

Abstract

Difficult classification problems often involve high dimensional inputs and a large number of classes. While feature selection/extraction techniques are often used to simplify the input space and alleviate the curse of dimensionality, modular learning paradigms based on the divide and conquer precept are used to decompose the problem into simpler classification tasks through input space, training set or feature space decomposition. In this thesis the modular learning paradigm is extended to the previously unexplored, but potentially useful, problem decomposition framework in which a C > 2 class problem is systematically decomposed into simpler two-(meta)class problems. Apart from improving generalization performance for difficult classification problems, such problem decomposition in output space allows class specific feature extraction, and yields significant domain knowledge that is not possible to obtain from conventional single classifiers or modular learning paradigms. Two frameworks for problem decomposition in output space are developed. In the first framework, called the PAIRWISE CLASSIFIER (PC) framework, a C-class problem is exhaustively decomposed into a set of ( C2 ) two-class problems. Features that best discriminate the two classes are extracted for each pairwise classifier and the outputs of all these classifiers are combined to yield the final output in the original output space. The second framework for problem decomposition in output space, called the BINARY HIERARCHICAL CLASSIFIER (BHC) framework, involves the decomposition of a C-class problem into a binary tree with C leaf nodes and C−1 internal nodes. Each internal node is comprised of a feature extractor and a classifier that discriminates between the two meta-classes represented by its two children. Both bottom-up (BU-BHC) and top-down (TDBHC) approaches for automatically building such a BHC are developed. The two frameworks for output space decomposition extend the modular learning paradigm for problems with high dimensional input and a moderately large number of classes or output space. The automatic discovery of domain knowledge, parallelizable (PC framework) and deterministic (BHC framework) algorithms for problem decomposition and a potential for improved generalization performance and interpretability of results make such a modular learning paradigm an attractive extension of the existing suite of modular learning approaches. (Abstract shortened by UMI.)