Hybrid Methods in Pattern Recognition

The following sections are included:

• Preface

• Contents

This chapter explains the handling of linguistic knowledge and fuzzy inputs in multi-layer feedforward neural networks for pattern classification problems. First we show how fuzzy input vectors can be classified by trained neural networks. The input-output relation of each unit is extended to the case of fuzzy inputs using fuzzy arithmetic. That is, fuzzy outputs from neural networks are denned by fuzzy arithmetic. The classification of each fuzzy input vector is performed by a decision rule using the corresponding fuzzy output vector. Next we show how neural networks can be trained from fuzzy training patterns. Our fuzzy training pattern is a pair of a fuzzy input vector and a non-fuzzy class label. We define a cost function to be minimized in the learning process as a distance between a fuzzy output vector and a non-fuzzy target vector. A learning algorithm is derived from the cost function in the same manner as the well-known back-propagation algorithm. Then we show how linguistic rules can be extracted from trained neural networks. Our linguistic rule has linguistic antecedent conditions, a non-fuzzy consequent class, and a certainty grade. We also show how linguistic rules can be utilized in the learning process. That is, linguistic rules are used as training data. Our learning scheme can simultaneously utilize linguistic rules and numerical data in the same framework. Finally we describe the architecture, learning, and application areas of interval-arithmetic-based neural networks, which can be viewed as a basic form of our fuzzified neural networks.

In this chapter we propose a new approach to pattern recognition, referred to as adaptive graphical pattern recognition which is inbetween decision-theoretic and structural pattern recognition. In particular we focus on the extension of classic supervised neural network-based approaches to pattern recognition, and show that the classic backpropagation learning scheme can naturally be extended to the case of patterns that are represented by directed ordered acyclic graphs. More general graphs can easily express complex patterns, but we demonstrate that the corresponding extension of classic neural network architectures and learning algorithms is less effective. This extended view of neural networks operating on graphs gives rise to a new wave of connectionist-based techniques. Experimental results on problems of pattern classification and image retrieval clearly indicate the effectiveness of the proposed approach, especially when neither purely structural nor purely subsymbolic representations are appropriate.

A new clustering algorithm, which is an extension of self-organizing map (som) into the domain of graphs, is introduced first. Then two adaptive versions of this algorithm are derived, which are able to find the optimal number of clusters automatically. While one of these adaptive clustering methods needs to be initialized with a number of clusters that is at least as large as the optimal number, the other does not need any prior knowledge about the true number of clusters. The suitability of both adaptive methods is experimentally evaluated. The paper is concluded with a discussion of the applicability of the proposed clustering algorithms, depending on available a priori knowledge about the optimal number of clusters.

This chapter focuses on granular clustering: a way of finding structure in heterogeneous data and representing the data in the form of information granules. The main features of the proposed granular clustering approach are: (a) a noninvasive exploration of data carried out under weak assumptions made as to the nature of the data, (b) transparency of the constructed information granules which assume the form of hyperboxes in the problem space. We introduce a compatibility measure that expresses a degree of “similarity” between two information granules and takes into account both a distance between the granules and their size. We show how to “grow” clusters through a process of merging existing data points that exhibit high values of the compatibility measure. The clustering algorithm is discussed along with a comprehensive validation mechanism for the resulting structures (collections of information granules). We formulate a problem of feature analysis in the setting of the information granules and introduce some quantitative measures describing each feature. Numerical experiments use two-dimensional synthetic data and the multivariable Boston housing data.

In this chapter, several methods for combining Hidden Markov Models (HMMs) and Neural Networks (NNs) for hybrid HMM/NN systems are presented. These systems can be used in a variety of pattern recognition applications that are most successfully handled by statistical recognition methods. Typical applications include speech and handwriting recognition, as well as face identification or similar computer vision problems. Hidden Markov Models as well as Neural Networks are both very powerful pattern recognition paradigms with different advantages and disadvantages, and therefore their combination seems to be an attractive option in order to improve current state-of-the-art pattern recognition systems. It turns out that the combination of HMMs and NNs is a challenging and interesting subject that leads to a variety of different approaches for the realization of hybrid systems. Besides architectural issues, that are concerned with finding the optimal structure for combining both paradigms, the joint estimation of system parameters – so that both paradigms can interact in an optimal way and support each other – is the major problem. The feasibility and success of hybrid systems is confirmed by numerous applications mentioned in this chapter, where hybrid systems have proved their superior performance compared to standard approaches.

In this chapter, we present a hybrid on-line handwriting recognition system based on Hidden Markov Models (HMMs) and Neural Networks (NNs). This system has been designed to recognize both isolated words and sentences. It is basically organized into three layers: letter models, word models and sentence models. Letter-models are Left-Right HMMs where the emission densities in each state are approximated by mixtures of predictive multilayer perceptrons (MLPs). These perform local regression on the handwriting signal, and thus allow us to incoporate contextual information. At the word and sentence level, recognition is based on a tree-structured dictionary. The proposed tree search and pruning techniques reduce the search space considerably without losing recognition accuracy. The system's performance is evaluated on a part of the UNIPEN international database. This chapter summarizes previous work done in our group on this topic and describes new results concerning the tree search structure for word-sentence recognition and the extension of the system for sentence recognition.

During the 1990's many methods were proposed for combining multiple classifiers for a single recognition task. With these methods, the focus of the field shifted from the competition among specific statistical, syntactic, or structural approaches to the integration of all these as potential contributing components in a combined system. Deeper explorations of the combination methods revealed many links back to several fundamental issues of pattern recognition. Amid the excitement and confusion, there is a persistent uncertainty concerning the optimal match between a method and a problem, due to a strong dependence of classifier performance on the data. In this chapter I review several different motivations that have driven this development, summarize lessons learned in the exploration of combination methods, outline the difficulties encountered, and suggest ways to break out of the current plateau.

In the field of pattern recognition, multiple classifier systems based on the combination of outputs of a set of different classifiers have been proposed as a method for the development of high performance classification systems. In this chapter, the problem of multiple classifier system design is discussed and the reader is provided with a critical survey of the state of the art. A formulation of the design problem that provides motivations for the different design methods described in the literature is proposed. In particular, such a formulation points out the rationale behind the so-called overproduce and choose design paradigm. Six design methods based on this paradigm are described and compared by experiments with three different data sets. Though these design methods have some interesting features, they do not guarantee an optimal multiple classifier system design for the classification task at hand. Accordingly, the main conclusion in this chapter is that optimal design is still an open problem.

To improve recognition results, decisions of multiple neural networks can be aggregated into a committee decision. An efficient committee should consist of networks that are not only very accurate, but also diverse in the sense that the network errors occur in different regions of the input space. One issue investigated in this chapter is the effectiveness of the half & half sampling approach in creating accurate neural network committees fused through the Choquet integral. The second issue investigated is the influence of different types of fuzzy measures on the classification accuracy obtained from neural network committees fused by a fuzzy integral. The ordinary fuzzy measure, the λ-fuzzy measure, the cardinal fuzzy measure, and the 2-order additive fuzzy measure are investigated. Parameters determining the fuzzy measures are learned from a training data set. Learning the fuzzy measures through minimization of the classification error rate resulted in a significant improvement of the accuracy of the committees as compared to learning the measures by minimizing the sum-of-squared error.

In many applications, the analysis of images is a valuable source of information. However, advances in technology lead to increasing amounts of image data that cannot be analyzed manually and that make an automatic analysis more and more important. The automatic extraction of knowledge from images is often a difficult and complex process. We present applications from remote sensing, where we use hybrid Data Mining methods to analyze the machine vision process. The gained knowledge is exploited to improve the image processing algorithms.

For personal identification, fingerprint identification has been much more widely used than other automatic biometric identification methods. For reliable feature extraction we analyze the direction of ridges, and the structural characteristics, such as the ridge line width and interval, are automatically estimated based on the ridge line following algorithm. To eliminate false features outside the region of interest (ROI), we generate adaptive matching boundaries. The concept of fuzzy sets is applied to the extracted features and the quantitative feature values are defined. In the feature matching stage, we introduce a weighted matching score using quantitative feature values to guarantee reliable matching results. Furthermore, a two-step estimation of transformation parameters is employed to reduce the computational complexity. The experimental results show that our system can achieve a fast personal identification with a good performance.

The categorization of texts or text fragments into a given set of classes is a problem with ever increasing practical relevance. In this chapter we first present a symbolic approach for learning expressive document features, so-called complexes. This approach can be used, e.g., for learning features in the form of specific word sequences or substring tests. Such features are employed in two different learning approaches for generating text classifiers. In the first approach, the learning of complexes is embedded in a symbolic rule learner. In the second approach we use symbolically learned complexes to represent documents for a subsymbolic learning approach, namely, the Support Vector Machine (SVM). We compare the results of the purely symbolic rule learning, a purely statistical approach based on the SVM, and the hybrid approach. It is shown experimentally that rule learning as well as the SVM benefit from learning expressive document features in the form of complexes. In particular, best results are obtained by the hybrid approach combining the symbolic learning of document features with the SVM.