Feature selection algorithms for the generation of multiple classifier systems and their application to handwritten word recognition

Abstract

The study of multiple classifier systems has become an area of intensive research in pattern recognition recently. Also in handwriting recognition, systems combining several classifiers have been investigated. In this paper new methods for the creation of classifier ensembles based on feature selection algorithms are introduced. Those new methods are evaluated and compared to existing approaches in the context of handwritten word recognition, using a hidden Markov model recognizer as basic classifier.

Introduction

The field of off-line handwriting recognition has been a topic of intensive research for many years. First only the recognition of isolated handwritten characters was investigated (Suen et al., 1992), but later whole words (Simon, 1992) were addressed. Most of the systems reported in the literature until today consider constrained recognition problems based on vocabularies from specific domains, e.g. postal addresses (Kaltenmeier et al., 1993; Kim et al., 1999) or amounts on bank checks (Impedovo et al., 1997). Free handwriting recognition, without domain specific constraints and large vocabularies, was addressed only recently in a few papers (Kim et al., 1999, Marti and Bunke, 2001). The recognition rate of such systems is still low, and there is a need to improve it.

The combination of multiple classifiers was shown to be suitable for improving the recognition performance in difficult classification problems (Kittler and Roli, 2000). Particularly in handwriting recognition, classifiers combination has often been applied. Examples are given in (Huang and Suen, 1993, Lee and Srihari, 1993, Lee and Gomes, 1997, Maruyama and Nakano, 2000, Xu et al., 1992).

Recently a number of classifier combination methods, called ensemble methods, have been proposed in the field of machine learning (Bauer and Kohavi, 1999, Opitz and Maclin, 1999). Given a single classifier, called the base classifier, a set of classifiers can be automatically generated by changing the training set (Breiman, 1996), the input features (Ho, 1998), the input data by injecting randomness, or the parameters and architecture of the classifier. A summary of such methods is given in (Dietterich, 2000).

In this paper we propose a new ensemble creation method that is based on the selection of particular subsets of features. The problem of feature selection has been a focus of research in pattern recognition for a long time (Jain and Zongker, 1997). In statistical pattern recognition (Jain et al., 2000) features are typically vectors of real numbers, whereas in structural pattern recognition (Fu, 1982) symbolic data structures, such as strings, trees, and graphs, are used. In this paper we follow the statistical approach.

In general, the choice of features is application dependent and often very difficult. A way to solve this problem is to start with a set of candidate features and either modify or reduce them. The modification of a set of features includes transformations of the feature space, for example, Principal Component Analysis (Jolliffe, 1986). There exist many ways to reduce a given set of features (Kittler et al., 2001), and they all need an objective function to validate the quality of the considered subset of features. Often a validation set is used on which the recognition rate is measured. With this objective function the selection of the best subset of features becomes a search problem. An optimal approach is to calculate the objective function for all possible subsets. But this approach is only feasible for a rather small number of features. Branch and Bound algorithms (Narendra and Fukunaga, 1977) use a priori knowledge to reduce the search space. However, often there is no such a priori knowledge available and a suboptimal approach, such as sequential forward/backward search (Devijver and Kittler, 1982), floating search (Pudil et al., 1994) or oscillating search (Somol and Pudil, 2000), is used. An ensemble method using feature selection was introduced in (Alkoot and Kittler, 2000). In this method, a classifier always selects the single feature that leads to the best recognition rate of the whole classifier ensemble. In contrast with the algorithm proposed in the current paper, a feature may only be used by one classifier and the selection of the features is not reversible, i.e. features that have been selected cannot be abandoned at a later time. In (Oza and Tumer, 2001) a method was presented which creates a classifier for each class and use the set of features which are the most able to discriminate this class from all other classes for this classifier.

The contribution of the present paper is twofold. First, to the knowledge of the authors, it is the first study that applies classifier ensemble creation methods using feature subsets in the field of handwriting recognition. Secondly, in the present paper we propose a new method for classifier ensemble creation based on feature subsets. The new algorithm is based on the idea of applying feature subset search algorithms that allow to add and remove individual features to find useful subsets of features on which individual classifiers are trained. Multiple search algorithms are incorporated to increase the diversity of the resulting classifiers. Four different objective functions for assessing the quality of a feature set are proposed. In a series of experiments the new classifier ensemble creation method is compared to single classifiers and multiple classifier systems generated by means of methods proposed before.

The rest of the paper is organized as follows. Section 2 provides a review of some classical ensemble methods. In Section 3 the basic idea underlying the new ensemble creation method is described. The following section introduces some refinements to the basic algorithm. In Section 5 a description of the feature selection algorithm used in the experiments is given. Section 6 contains information about the handwritten word recognizer, which is used as the base classifier in the experiments. Those experiments are then discussed in Section 7 and, finally, conclusions are drawn in Section 8.