Selecting a good model of a set of input points by cross validation is a computationally intensive process, especially if the number of possible models or the number of training points is high. Tech(cid:173) niques such as gradient descent are helpful in searching through the space of models, but problems such as local minima, and more importantly, lack of a distance metric between various models re(cid:173) duce the applicability of these search methods. Hoeffding Races is a technique for finding a good model for the data by quickly dis(cid:173) carding bad models, and concentrating the computational effort at differentiating between the better ones. This paper focuses on the special case of leave-one-out cross validation applied to memory(cid:173) based learning algorithms, but we also argue that it is applicable to any class of model selection problems.

This paper presents a rigorous characterization of how a general nonlinear learning machine generalizes during the training process when it is trained on a random sample using a gradient descent algorithm based on reduction of training error. It is shown, in particular, that best generalization performance occurs, in general, before the global minimum of the training error is achieved. The different roles played by the complexity of the machine class and the complexity of the specific machine in the class during learning are also precisely demarcated.

Radial Basis Function (RBF) Networks, also known as networks of locally-tuned processing units (see [6]) are well known for their ease of use. Most algorithms used to train these types of net(cid:173) works, however, require a fixed architecture, in which the number of units in the hidden layer must be determined before training starts. The RCE training algorithm, introduced by Reilly, Cooper and Elbaum (see [8]), and its probabilistic extension, the P-RCE algorithm, take advantage of a growing structure in which hidden units are only introduced when necessary. The nature of these al(cid:173) gorithms allows training to reach stability much faster than is the case for gradient-descent based methods. Unfortunately P-RCE networks do not adjust the standard deviation of their prototypes individually, using only one global value for this parameter.

We have continued our study of a parallel perturbative learning method [Alspector et al., 1993] and implications for its implemen(cid:173) tation in analog VLSI. Our new results indicate that, in most cases, a single parallel perturbation (per pattern presentation) of the func(cid:173) tion parameters (weights in a neural network) is theoretically the best course. This is not true, however, for certain problems and may not generally be true when faced with issues of implemen(cid:173) tation such as limited precision. In these cases, multiple parallel perturbations may be best as indicated in our previous results.

If data collection is costly, there is much to be gained by actively se(cid:173) lecting particularly informative data points in a sequential way. In a Bayesian decision-theoretic framework we develop a query selec(cid:173) tion criterion which explicitly takes into account the intended use of the model predictions. By Markov Chain Monte Carlo methods the necessary quantities can be approximated to a desired preci(cid:173) sion. As the number of data points grows, the model complexity is modified by a Bayesian model selection strategy. The proper(cid:173) ties of two versions of the criterion ate demonstrated in numerical experiments.

This paper studies the convergence properties of the well known K-Means clustering algorithm. The K-Means algorithm can be de(cid:173) scribed either as a gradient descent algorithm or by slightly extend(cid:173) ing the mathematics of the EM algorithm to this hard threshold case. We show that the K-Means algorithm actually minimizes the quantization error using the very fast Newton algorithm.

We present a deterministic annealing variant of the EM algorithm for maximum likelihood parameter estimation problems. In our approach, the EM process is reformulated as the problem of min(cid:173) imizing the thermodynamic free energy by using the principle of maximum entropy and statistical mechanics analogy. Unlike simu(cid:173) lated annealing approaches, this minimization is deterministically performed. Moreover, the derived algorithm, unlike the conven(cid:173) tional EM algorithm, can obtain better estimates free of the initial parameter values.

Understanding knowledge representations in neural nets has been a difficult problem. Principal components analysis (PCA) of contributions (products of sending activations and connection weights) has yielded valuable insights into knowledge representations, but much of this work has focused on the correlation matrix of contributions. The present work shows that analyzing the variance-covariance matrix of contributions yields more valid insights by taking account of weights.

We construct a mixture of locally linear generative models of a col(cid:173) lection of pixel-based images of digits, and use them for recogni(cid:173) tion. Different models of a given digit are used to capture different styles of writing, and new images are classified by evaluating their log-likelihoods under each model. We use an EM-based algorithm in which the M-step is computationally straightforward principal components analysis (PCA). Incorporating tangent-plane informa(cid:173) tion [12] about expected local deformations only requires adding tangent vectors into the sample covariance matrices for the PCA, and it demonstrably improves performance.

Simard, LeCun & Denker (1993) showed that the performance of nearest-neighbor classification schemes for handwritten character recognition can be improved by incorporating invariance to spe(cid:173) the so cific transformations in the underlying distance metric - called tangent distance. The resulting classifier, however, can be prohibitively slow and memory intensive due to the large amount of prototypes that need to be stored and used in the distance compar(cid:173) isons. In this paper we develop rich models for representing large subsets of the prototypes. These models are either used singly per class, or as basic building blocks in conjunction with the K-means clustering algorithm.