A spectral analysis of a Boolean function is proposed for approximating the decision boundary of an ensemble of classifiers, and an intuitive explanation of computing Walsh coefficients for the functional approximation is provided. It is shown that the difference between the first- and third-order coefficient approximations is a good indicator of optimal base classifier complexity. When combining neural networks, the experimental results on a variety of artificial and real two-class problems demonstrate under what circumstances ensemble performance can be improved. For tuned base classifiers, the first-order coefficients provide performance similar to the majority vote. However, for weak/fast base classifiers, higher order coefficient approximation may give better performance. It is also shown that higher order coefficient approximation is superior to the Adaboost logarithmic weighting rule when boosting weak decision tree base classifiers.

An approach to approximating the decision boundary of an ensemble of two-class classifiers is proposed. Spectral coefficients are used to approximate the discrete probability density function of a Boolean Function. It is shown that the difference between first and third order coefficient approximation is a good indicator of optimal base classifier complexity. A theoretical analysis is supported by experimental results on a variety of Artificial and Real two-class problems.

Error Correcting Output Coding (ECOC) is a multiclass classification technique in which multiple binary classifiers are trained according to a preset code matrix such that each one learns a separate dichotomy of the classes. While ECOC is one of the best solutions for multi-class problems, one issue which makes it suboptimal is that the training of the base classifiers is done independently of the generation of the code matrix. In this paper, we propose to modify a given ECOC matrix to improve its performance by reducing this decoupling. The proposed algorithm uses beam search to iteratively modify the original matrix, using validation accuracy as a guide. It does not involve further training of the classifiers and can be applied to any ECOC matrix. We evaluate the accuracy of the proposed algorithm (BeamECOC) using 10-fold cross-validation experiments on 6 UCI datasets, using random code matrices of different sizes, and base classifiers of different strengths. Compared to the random ECOC approach, BeamECOC increases the average cross-validation accuracy in 83.3% of the experimental settings involving all datasets, and gives better results than the state-of-the-art in 75% of the scenarios. By employing BeamECOC, it is also possible to reduce the number of columns of a random matrix down to 13% and still obtain comparable or even better results at times.

Ensemble pruning aims to increase efficiency by reducing the number of base classifiers, without sacrificing and preferably enhancing performance. In this brief, a novel pruning paradigm is proposed. Two class supervised learning problems are pruned using a combination of first- and second-order Walsh coefficients. A comparison is made with other ordered aggregation pruning methods, using multilayer perceptron base classifiers. The Walsh pruning method is analyzed with the help of a model that shows the relationship between second-order coefficients and added classification error with respect to Bayes error.

A feature ranking scheme for multilayer perceptron (MLP) ensembles is proposed, along with a stopping criterion based upon the out-of-bootstrap estimate. To solve multi-class problems feature ranking is combined with modified error-correcting output coding. Experimental results on benchmark data demonstrate the versatility of the MLP base classifier in removing irrelevant features.

Two-class supervised learning in the context of a classifier ensemble may be formulated as learning an incompletely specified Boolean function, and the associated Walsh coefficients can be estimated without the knowledge of the unspecified patterns. Using an extended version of the Tumer-Ghosh model, the relationship between added classification error and second-order Walsh coefficients is established. In this brief, the ensemble is composed of multilayer perceptron base classifiers, with the number of hidden nodes and epochs systematically varied. Experiments demonstrate that the mean second-order coefficients peak at the same number of training epochs as ensemble test error reaches a minimum.

We investigate the effects, in terms of a bias-variance decomposition of error, of applying class-separability weighting plus bootstrapping in the construction of error-correcting output code ensembles of binary classifiers. Evidence is presented to show that bias tends to be reduced at low training strength values whilst variance tends to be reduced across the full range. The relative importance of these effects, however, varies depending on the stability of the base classifier type.

The difficulties of tuning parameters of multilayer perceptrons (MLP) classifiers are well known. In this paper, a measure is described that is capable of predicting the number of classifier training epochs for achieving optimal performance in an ensemble of MLP classifiers. The measure is computed between pairs of patterns on the training data and is based on a spectral representation of a Boolean function. This representation characterizes the mapping from classifier decisions to target label and allows accuracy and diversity to be incorporated within a single measure. Results on many benchmark problems, including the Olivetti Research Laboratory (ORL) face database demonstrate that the measure is well correlated with base-classifier test error, and may be used to predict the optimal number of training epochs. While correlation with ensemble test error is not quite as strong, it is shown in this paper that the measure may be used to predict number of epochs for optimal ensemble performance. Although the technique is only applicable to two-class problems, it is extended here to multiclass through output coding. For the output-coding technique, a random code matrix is shown to give better performance than one-per-class code, even when the base classifier is well-tuned.

The goal of designing an ensemble of simple classifiers is to improve the accuracy of a recognition system. However, the performance of ensemble methods is problem-dependent and the classifier learning algorithm has an important influence on ensemble performance. In particular, base classifiers that are too complex may result in overfitting. In this paper, the performance of Bagging, Boosting and Error-Correcting Output Code (ECOC) is compared for five decision tree pruning methods. A description is given for each of the pruning methods and the ensemble techniques. AdaBoost.OC which is a combination of Boosting and ECOC is compared with the pseudo-loss based version of Boosting, AdaBoost.M2 and the influence of pruning on the performance of the ensembles is studied. Motivated by the result that both pruned and unpruned ensembles made by AdaBoost.OC give similar accuracy, pruned ensembles are compared with ensembles of Decision Stumps. This leads to the hypothesis that ensembles of simple classifiers may give better performance for some problems. Using the application of face recognition, it is shown that an AdaBoost.OC ensemble of Decision Stumps outperforms an ensemble of pruned C4.5 trees for face identification, but is inferior for face verification. The implication is that in some real-world tasks to achieve best accuracy of an ensemble, it may be necessary to select base classifier complexity.

We develop a novel approach to face verification based on the Error Correcting Output Coding (ECOC) classifier design concept. In the training phase the client set is repeatedly divided into two ECOC specified sub-sets (superclasses) to train a set of binary classifiers. The output of the classifiers defines the ECOC feature space, in which it is easier to separate transformed patterns representing clients and impostors. The proposed method exhibits superior verification performance on the well known XM2VTS data set as compared with previously reported results. 1

The error correcting output coding (ECOC) approach to classifier design decomposes a multi-class problem into a set of complementary two-class problems. We show how to apply the ECOC concept to automatic face verification, which is inherently a two-class problem. The output of the binary classifiers defines the ECOC feature space, in which it is easier to separate transformed patterns representing clients and impostors. We propose two different combining strategies as the matching score for face verification. The first uses the first order Minkowski metric, and requires a threshold to be set. The second is a kernel-based method and has no parameters to set. The proposed method exhibits better performance on the well known XM2VTS data set compared with previous reported results.

Error correcting output coding (ECOC), an information theoretic concept, seems an attractive idea for improving the performance of automatic classifiers, particularly for problems that involve large number of classes. In this paper, we look at the conditions necessary for reduction of error in this framework and introduce a new version of ECOC. To show the error reduction procedure and compare the new algorithm with traditional one, we use an artificial benchmark on which we are able to control the rate of noise to investigate the behaviour of system in different parts of input space, as well as a few real problems.

We propose a spectral technique for analysing intermediate feature space of multiple classifier decisions, which enables a separable subset of patterns to be extracted. The method is applied to finding a set of patterns that are inconsistently classified, a random subset of which is left out of the training set of each expert in a multiple classifier framework.

Thermochromic paint, paint that changes colour according to the maximum temperature it has experienced, has a variety of uses within the automotive industry. Currently interpretation is performed manually by a human operator. This paper addresses the task of automatic interpretation, specifically addressing problems relating to feature space ambiguity. We derive a cost function to overcome these problems and utilise this within a simulated annealing framework. The method was developed using synthetic data which models the causes of ambiguity, and results are presented for real image data derived from paint-coated industrial parts.

A new surface based approach to implicit surface polygonisation is introduced. This is applied to the reconstruction of 3D surface models of complex objects from multiple range images. Geometric fusion of multiple range images into an implicit surface representation was presented in previous work. This paper introduces an efficient algorithm to reconstruct a triangulated model of a manifold implicit surface, a local 3D constraint is derived which defines the Delaunay surface triangulation of a set of points on a manifold surface in 3D space. The 'marching triangles' algorithm uses the local 3D constraint to reconstruct a Delaunay triangulation of an arbitrary topology manifold surface. Computational and representational costs are both a factor of 3-5 lower than previous volumetric approaches such as marching cubes.

Thermal paint, paint that changes colour with maximum temperature, has a variety of uses within the automotive industry. The analysis of samples after exposure to heat is a task currently performed by humans. We present the current findings of our attempts to automate this procedure by means of image analysis. A framework has been developed within which colour is mapped to an RGB space curve which is a function of temperature. This models the context imparted by the physical process, as well as spatial context, and gives us better results than those obtained by using conventional image segmentation techniques.

We propose a formalism for analysing multilayer perceptron (MLP) networks as propagations of binary transitions along excitatory and inhibitory sensitised paths. By characterising a Boolean function as sets of detected transitions, we produce a spectral summation and construct a network from the derived weight constraints. We build hidden node feature detectors by incorporating k-monotonicity checks in the partitioning step of a constructive algorithm. Propagation constraints are also used in an MLP network using gradient descent learning to limit hyperplane movement in weight space. Results for a pattern classification task represented as a binary-to-binary mapping show improved convergence and generalisation performance.

Range images may be used for a variety of applications in object recognition, inspection and reverse engineering. In many of these applications it is important to obtain good estimates of the local surface curvature. Good curvature estimates require good derivative estimates, but the estimation of derivatives from sampled data is highly susceptible to noise. In this paper, we introduce a new way of characterizing range data by a single parameter. From this characterization we show how to make an optimal choice of whatever parameters there are in a particular derivative estimation method, and obtain an estimate of the error one might expect. Finally, we show how the analysis may be applied to measuring derivatives on a cylinder.

Reliable curvature estimation is an important goal in image analysis to provide viewpoint independent cues for shape classification. This paper presents a model of the relationship between the variance of curvature estimates and the image noise. Agreement to within 10% is obtained for 3D range data. Previous models have only provided qualitative agreement with experimental observations. A perturbation error analysis is performed on the local least square surface fitting algorithm which is commonly used to obtain partial derivative estimates in the presence of noise.