Learning pattern classification—A survey
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Any Discrimination Rule Can Have an Arbitrarily Bad Probability of Error for Finite Sample Size

paper_content:

Consider the basic discrimination problem based on a sample of size n drawn from the distribution of (X, Y) on the Borel sets of Rdx {O, 1}. If 0 < R*< is a given number, and 'n - 0 is an arbitrary positive sequence, then for any discrimination rule one can find a distribution for (X, Y), not depending upon n, with Bayes probability of error R* such that the probability of error (Rn) of the discrimination rule is larger than R* + 'On for infinitely many n. We give a formal proof of this result, which is a generalization of a result by Cover [1].
---
paper_title: Machine Learning: A Theoretical Approach

paper_content:

Chapter 1 Introduction Chapter 2 Learning Concept on Countable Domains Chapter 3 Time Complexity of Concept Learning Chapter 4 Learning Concepts on Uncoutable Domains Chapter 5 Learning Functions Chapter 6 Finite Automata Chapter 7 Neural Networks Chapter 8 Generalizing the Learning Model Chapter 9 Conclusion
---
paper_title: A Theory of Learning and Generalization

paper_content:

From the Publisher: ::: How does it differ from first edition? Includes new material on: * support vector machines (SVM's), * fat shattering dimensions * applications to neural network learning, * learning with dependent samples generated by beta-mixing process, * connections between system identification and learning theory * probabilistic solution of "intractable" problems in robust control and matrix theory using randomised algorithms. In addition, solutions to some open problems posed in the first edition are included, and new open problems are added. The author is a respected authority in the field of control and systems theory. This new edition, with substantial new material, takes account of important new developments in the theory of learning. It also deals extensively with the theory of learning control systems, which has now reached a level of maturity comparable to that of learning of neural networks. The book is written in a manner that would suit self-study and contains comprehensive references. The chapters are also written to be as autonomous as possible and contain updated open problems to enhance further research and self-study.
---
paper_title: An Introduction to Computational Learning Theory

paper_content:

The probably approximately correct learning model Occam's razor the Vapnik-Chervonenkis dimension weak and strong learning learning in the presence of noise inherent unpredictability reducibility in PAC learning learning finite automata by experimentation appendix - some tools for probabilistic analysis.
---
paper_title: Introduction to Statistical Pattern Recognition

paper_content:

This completely revised second edition presents an introduction to statistical pattern recognition. Pattern recognition in general covers a wide range of problems: it is applied to engineering problems, such as character readers and wave form analysis as well as to brain modeling in biology and psychology. Statistical decision and estimation, which are the main subjects of this book, are regarded as fundamental to the study of pattern recognition. This book is appropriate as a text for introductory courses in pattern recognition and as a reference book for workers in the field. Each chapter contains computer projects as well as exercises.
---
paper_title: Discriminatory Analysis - Nonparametric Discrimination: Small Sample Performance

paper_content:

Abstract : A classification procedure is worked out for the following situations: Two large samples, one from each of two populations, have been observed. An individual of unknown origin is to be classified as belonging to the first population if the majority of a specified odd number of individuals closet to the individual in question belong to the first population. This method has optimum properties when the number of closest individuals is permitted to be very large. For certain cases involving multivariate normal distributions with the same covariance matrix, the probabilities of possible misclassification have been computed and compared with those of the discriminant function method.
---
paper_title: Discriminatory Analysis - Nonparametric Discrimination: Consistency Properties

paper_content:

Abstract : The discrimination problem (two population case) may be defined as follows: e random variable Z, of observed value z, is distributed over some space (say, p-dimensional) either according to distribution F, or according to distribution G. The problem is to decide, on the basis of z, which of the two distributions Z has.
---
paper_title: Nearest Neighbor Pattern Classification

paper_content:

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error R of such a rule must be at least as great as the Bayes probability of error R^{\ast} --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the M -category case that R^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)) , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
---
paper_title: Distribution-free exponential error bound for nearest neighbor pattern classification

paper_content:

The rate of convergence of the nearest neighbor (NN) rule is investigated when independent identically distributed samples take values in a d -dimensional Euclidean space. The common distribution of the sample points need not be absolutely continuous. An upper bound consisting of two exponential terms is given for the probability of large deviations of error probability from the asymptotic error found by Cover and Hart. The asymptotically dominant first term of this bound is distribution-free, and its negative exponent goes to infinity approximately as fast as the square root of the number of preclassified samples. The second term depends on the underlying distributions, but its exponent is proportional to the sample size. The main term is explicitly given and depends very weakly on the dimension of the space.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Nearest Neighbor Pattern Classification

paper_content:

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error R of such a rule must be at least as great as the Bayes probability of error R^{\ast} --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the M -category case that R^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)) , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
---
paper_title: On the Inequality of Cover and Hart in Nearest Neighbor Discrimination

paper_content:

When (X1, ¿1),..., (Xn, ¿n) are independent identically distributed random vectors from IRd X {0, 1} distributed as (X, ¿), and when ¿ is estimated by its nearest neighbor estimate ¿(1), then Cover and Hart have shown that P{¿(1) ¿ ¿}n ¿ ¿ ¿ 2E {¿ (X) (1 - ¿(X))} ¿ 2R*(1 - R*) where R* is the Bayes probability of error and ¿(x) = P{¿ = 1 | X = x}. They have conditions on the distribution of (X, ¿). We give two proofs, one due to Stone and a short original one, of the same result for all distributions of (X, ¿). If ties are carefully taken care of, we also show that P{¿(1) ¿ ¿|X1, ¿1, ..., Xn, ¿n} converges in probability to a constant for all distributions of (X, ¿), thereby strengthening results of Wagner and Fritz.
---
paper_title: On the finite sample performance of the nearest neighbor classifier

paper_content:

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk R/sub m/ given that a reference m-sample of labeled points is available to the classifier. The statistical setup assumes that the pattern classes arise in nature with fixed a priori probabilities and that points representing the classes are drawn from Euclidean n-space according to fixed class-conditional probability distributions. The sample is assumed to consist of m independently generated class-labeled points. For a family of smooth class-conditional distributions characterized by asymptotic expansions in general form, it is shown that the m-sample risk R/sub m/ has a complete asymptotic series expansion R/sub m//spl sim/R/sub /spl infin//+/spl Sigma//sub k=2//sup /spl infin//c/sub k/m/sup -k/n/ (m/spl rarr//spl infin/), where R/sub /spl infin// denotes the nearest neighbor risk in the infinite-sample limit and the coefficients c/sub k/ are distribution-dependent constants independent of the sample size m. The analysis thus provides further analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included, and extensions of the theory discussed. The analysis also contains a novel application of Laplace's asymptotic method of integration to a multidimensional integral where the integrand attains its maximum on a continuum of points. >
---
paper_title: An Optimal Global Nearest Neighbor Metric

paper_content:

A quadratic metric dAO (X, Y) =[(X - Y)T AO(X - Y)]? is proposed which minimizes the mean-squared error between the nearest neighbor asymptotic risk and the finite sample risk. Under linearity assumptions, a heuristic argument is given which indicates that this metric produces lower mean-squared error than the Euclidean metric. A nonparametric estimate of Ao is developed. If samples appear to come from a Gaussian mixture, an alternative, parametrically directed distance measure is suggested for nearness decisions within a limited region of space. Examples of some two-class Gaussian mixture distributions are included.
---
paper_title: On The Strong Universal Consistency Of Nearest Neighbor Regression Function Estimates

paper_content:

Two results are presented concerning the consistency of the k-nearest neighbor regression estimate. We show that all modes of convergence in L 1 (in probability, almost sure, complete) are equivalent if the regression variable is bounded. Under the additional condition k/log n → ∞ we also obtain the strong universal consistency of the estimate
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Nearest Neighbor Pattern Classification

paper_content:

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error R of such a rule must be at least as great as the Bayes probability of error R^{\ast} --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the M -category case that R^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)) , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
---
paper_title: The optimal distance measure for nearest neighbor classification

paper_content:

A local distance measure is shown to optimize the performance of the nearest neighbor two-class classifier for a finite number of samples. The difference between the finite sample error and the asymptotic error is used as the criterion of improvement. This new distance measure is compared to the well-known Euclidean distance. An algorithm for practical implementation is introduced. This algorithm is shown to be computationally competitive with the present nearest neighbor procedures and is illustrated experimentally. A closed form for the corresponding second-order moment of this criterion is found. Finally, the above results are extended to
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: On Estimating Regression

paper_content:

A study is made of certain properties of an approximation to the regression line on the basis of sampling data when the sample size increases unboundedly.
---
paper_title: Remarks on Some Nonparametric Estimates of a Density Function

paper_content:

This note discusses some aspects of the estimation of the density function of a univariate probability distribution. All estimates of the density function satisfying relatively mild conditions are shown to be biased. The asymptotic mean square error of a particular class of estimates is evaluated.
---
paper_title: Nonparametric estimation and classification using radial basis function nets and empirical risk minimization

paper_content:

Studies convergence properties of radial basis function (RBF) networks for a large class of basis functions, and reviews the methods and results related to this topic. The authors obtain the network parameters through empirical risk minimization. The authors show the optimal nets to be consistent in the problem of nonlinear function approximation and in nonparametric classification. For the classification problem the authors consider two approaches: the selection of the RBF classifier via nonlinear function estimation and the direct method of minimizing the empirical error probability. The tools used in the analysis include distribution-free nonasymptotic probability inequalities and covering numbers for classes of functions.
---
paper_title: Fast Learning in Networks of Locally-Tuned Processing Units

paper_content:

We propose a network architecture which uses a single internal layer of locally-tuned processing units to learn both classification tasks and real-valued function approximations (Moody and Darken 1988). We consider training such networks in a completely supervised manner, but abandon this approach in favor of a more computationally efficient hybrid learning method which combines self-organized and supervised learning. Our networks learn faster than backpropagation for two reasons: the local representations ensure that only a few units respond to any given input, thus reducing computational overhead, and the hybrid learning rules are linear rather than nonlinear, thus leading to faster convergence. Unlike many existing methods for data analysis, our network architecture and learning rules are truly adaptive and are thus appropriate for real-time use.
---
paper_title: Probabilistic neural networks and the polynomial Adaline as complementary techniques for classification

paper_content:

Two methods for classification based on the Bayes strategy and nonparametric estimators for probability density functions are reviewed. The two methods are named the probabilistic neural network (PNN) and the polynomial Adaline. Both methods involve one-pass learning algorithms that can be implemented directly in parallel neural network architectures. The performances of the two methods are compared with multipass backpropagation networks, and relative advantages and disadvantages are discussed. PNN and the polynomial Adaline are complementary techniques because they implement the same decision boundaries but have different advantages for applications. PNN is easy to use and is extremely fast for moderate-sized databases. For very large databases and for mature applications in which classification speed is more important than training speed, the polynomial equivalent can be found. >
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: On exponential bounds on the Bayes risk of the kernel classification rule

paper_content:

The exponential, distribution-free bounds for the kernel classification rule are derived. The equivalence of all modes of the global convergence of the rule is established under optimal assumptions on the smoothing sequence. Also derived is the optimal global rate of convergence of the kernel regression estimate within the class of Lipschitz distributions. The rate is optimal for the nonparametric regression, but not for classifications. It is shown. using the martingale device, that weak, strong, and complete L/sub 1/ Bayes risk consistencies are equivalent. Consequently the conditions on the smoothing sequence h/sub n/ to 0 and nh/sub n/ to infinity are necessary and sufficient for Bayes risk consistency of the kernel classification rule. The rate of convergence of the kernel classification rule is also given. >
---
paper_title: Nonparametric Density Estimation: The L 1 View.

paper_content:

Differentiation of Integrals Consistency Lower Bounds for Rates of Convergence Rates of Convergence in L1 The Automatic Kernel Estimate: L1 and Pointwise Convergence Estimates Related to the Kernel Estimate and the Histogram Estimate Simulation, Inequalities, and Random Variate Generation The Transformed Kernel Estimate Applications in Discrimination Operations on Density Estimates Estimators Based on Orthogonal Series Index.
---
paper_title: Necessary and sufficient conditions for Bayes risk consistency of a recursive kernel classification rule

paper_content:

It is shown that, for a nonparametric recursive kernel classification rule, \sum^{n}_{i=1}h^{d}(i)I_{ \{h(i) > \epsilon \} } / \sum^{n}_{j=1} h^{d} (j) \rightarrow 0 {\rm as} n \rightarrow \infty, all \epsilon > 0 and \sum^{\infty}_{i=1}h^{d}(i)= \infty constitute a set of conditions which are not only sufficient but also necessary for weak and strong Bayes risk consistency of the rule. In this way, weak and strong consistencies are shown to be equivalent.
---
paper_title: Exponential bounds of mean error for the kernel estimates of regression functions

paper_content:

Abstract Let ( X , Y ), ( X 1 , Y 1 ), …, ( X n , Y n ) be i.d.d. R r × R -valued random vectors with E | Y | Q n ( x ) be a kernel estimate of the regression function Q ( x ) = E ( Y | X = x ). In this paper, we establish an exponential bound of the mean deviation between Q n ( x ) and Q ( x ) given the training sample Z n = ( X 1 , Y 1 , …, X n , Y n ), under conditions as weak as possible.
---
paper_title: Almost Everywhere Convergence of Recursive Kernel Regression Function Estimates

paper_content:

In the paper authors study universal consistency results for Wolverton, Wagner as well as Devroye, Wagner kernel type estimates of a regression function. There are proved sufficient conditions for weak and strong pointwise convergence under no assumptions on underlying distribution.
---
paper_title: A Recursive Partitioning Decision Rule for Nonparametric Classification

paper_content:

A new criterion for deriving a recursive partitioning decision rule for nonparametric classification is presented. The criterion is both conceptually and computationally simple, and can be shown to have strong statistical merit. The resulting decision rule is asymptotically Bayes' risk efficient. The notion of adaptively generated features is introduced and methods are presented for dealing with missing features in both training and test vectors.
---
paper_title: Consistency of data-driven histogram methods for density estimation and classification

paper_content:

We present general sufficient conditions for the almost sureL1-consistency of histogram density estimates based on data-dependent partitions. Analogous conditions guarantee the almost-sure risk consistency of histogram classification schemes based on data-dependent partitions. Multivariate data is considered throughout. In each case, the desired consistency requires shrinking cells, subexponential growth of a combinatorial complexity measure, and sub-linear growth of the number of cells. It is not required that the cells of every partition be rectangles with sides paralles to the coordinate axis, or that each cell contain a minimum number of points. No assumptions are made concerning the common distribution of the training vectors. We apply the results to establish the consistency of several known partitioning estimates, including the kn-spacing density estimate, classifiers based on statistically equivalent blocks, and classifiers based on multivariate clustering schemes.
---
paper_title: A Nonparametric Partitioning Procedure for Pattern Classification

paper_content:

A nonparametric procedure is developed for determining a structure for multivariate, multiclass pattern classification. The resultant classifier is in the form of a layered machine which is composed of multithreshold elements. The basic algorithm determines partitions which are parallel hyperplanes orthogonal to the feature coordinate dimensions. Inherent in the procedure is the concept of a transgenerator unit used to establish new feature dimensions such that effective partitioning can be obtained. While the choice of which classes of transgeneration units to consider is ultimately up to the user, a number of such units are suggested herein. The algorithm gives an indication as to the effectiveness of various transgeneration units and hence can also be used in an interactive manner if so desired for the actual design of a classification structure.
---
paper_title: A Partitioning Algorithm with Application in Pattern Classification and the Optimization of Decision Trees

paper_content:

The efficient partitioning of a finite-dimensional space by a decision tree, each node of which corresponds to a comparison involving a single variable, is a problem occurring in pattern classification, piecewise-constant approximation, and in the efficient programming of decision trees. A two-stage algorithm is proposed. The first stage obtains a sufficient partition suboptimally, either by methods suggested in the paper or developed elsewhere; the second stage optimizes the results of the first stage through a dynamic programming approach. In pattern classification, the resulting decision rule yields the minimum average number of calculations to reach a decision. In approximation, arbitrary accuracy for a finite number of unique samples is possible. In programming decision trees, the expected number of computations to reach a decision is minimized.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Distribution-Free Pattern Verification Using Statistically Equivalent Blocks

paper_content:

A nonparametric classification procedure based on distribution-free tolerance regions is presented. Without knlowledge of the class probability distributions, the procedure gives information about the expected performance of the classifier through use of only one sample of statistically independent observations from each class. With this procedure, a two-class discriminant can be designed for a given expected false alarm probability or for a given confidence that the false alarm probability is less than a given amount. Three ordering methods are presented that appear intuitively reasonable for minimizing the miss probability. Even though the methods do not, in general, meet this objective, they are easily implemented on a computer and can give good results. A procedure for obtaining a measure of the miss probability is also presented. These methods are applied to the problem of verifying the purported identity of a speaker from a sample of the speaker's voice.
---
paper_title: Problems in the Analysis of Survey Data, and a Proposal

paper_content:

Abstract Most of the problems of analyzing survey data have been reasonably well handled, except those revolving around the existence of interaction effects. Indeed, increased efficiency in handling multivariate analyses even with non-numerical variables, has been achieved largely by assuming additivity. An approach to survey data is proposed which imposes no restrictions on interaction effects, focuses on Importance in reducing predictive error, operates sequentially, and is independent of the extent of linearity in the classifications or the order in which the explanatory factors are introduced.
---
paper_title: Some nonparametric multivariate procedures based on statistically equivalent blocks

paper_content:

Intumescent compositions of the invention comprise certain arylsulfonamidopyrazines, such as 2-sulfanilamidopyrazine, 2-sulfanilamidobenzopyrazine, and derivatives thereof. The intumescent agents may be employed in conjuction with additives conventionally used in intumescent compositions. For use in protecting substrates from heat and fire, the intumescent compositions may be applied to the substrates in any suitable manner, such as by electrodeposition, spraying onto an adhesive substrate, or application of a coating composition comprising the intumescent agent.
---
paper_title: Almost surely consistent nonparametric regression from recursive partitioning schemes

paper_content:

Presented here are results on almost sure convergence of estimators of regression functions subject to certain moment restrictions. Two somewhat different notions of almost sure convergence are studied: unconditional and conditional given a training sample. The estimators are local means derived from certain recursive partitioning schemes.
---
paper_title: A Comparison of Some Multivariate Discrimination Procedures

paper_content:

Abstract A sequence of observations is obtained; each observation is known to be a value on one of two distinct absolutely continuous p-dimensional random variables, X and Y. The problem is to decide whether each observation is on X or Y. Some discrimination procedures are suggested and, using Monte Carlo methods, they are compared with other discrimination procedures to be found in the literature. The overall best performer in the comparisons of this study is one of the suggested procedures, a “nearest neighbor” type procedure based on statistically equivalent blocks.
---
paper_title: A distribution-free discrimination procedure based on clustering

paper_content:

A method is presented for constructing distribution-free tolerance regions for one distribution based on the clusters of the sample from a second distribution. The tolerance regions are constructed so as to minimize the probability of reserve judgment in a two-class discrimination procedure that allows the conditional error probabilities to be controlled within prescribed upper bounds. The method results in discrimination functions that are easily implemented on a computer. Although the method is not, in general, consistent with optimal procedures, it is appealing for high-dimensional problems with multimodal distributions.
---
paper_title: Nonparametric Discrimination Using Tolerance Regions

paper_content:

0. Introduction and summary. A method is given which can be used to construct procedures for discriminating among distributions on a Euclidean space with continuous distribution functions. The decision space used includes "partial" decisions and the probabilities of errors are random variables with beta distributions. Emphasis is upon control of the distribution of the conditional overall probabilities of errors. These procedures can be used in a wide class of discrimination problems, such as, for example, discriminating among multivariate normal distributions with unknown, unequal dispersion matrices. A number of other writers have suggested nonparametric discrimination procedures. The first work in this area, to the knowledge of these writers, was by Fix and Hodges [2]. Since the work by those authors has remained unpublished, a brief statement of its approach and results is given in Section 4 for comparison. Procedures have been suggested also by Stoller [13], Anderson [1] and Kendall [8].
---
paper_title: Almost sure L 1 -norm convergence for data-based histogram density estimates

paper_content:

The main result of this paper is summarized in Theorem 1, which states that when certain conditions of a general nature are satisfied, the data-based histogram density estimator is strongly consistent in the sence that the mean absolute derivation of the estimator and the density function converges to zero almost surely for any density function, as the sample size increases to infinity.
---
paper_title: Consistent nonparametric regression from recursive partitioning schemes

paper_content:

We here extend our results on asymptotically Bayes risk efficient classification to the general regression scenario. More precisely, we find Lp consistent estimators for an arbitrary regression function provided only that the dependent variable has a finite absolute pth moment. The estimators are truncated and untruncated local means derived from recursive partitioning schemes.
---
paper_title: Locally Trained Piecewise Linear Classifiers

paper_content:

We describe a versatile technique for designing computer algorithms for separating multiple-dimensional data (feature vectors) into two classes. We refer to these algorithms as classifiers. Our classifiers achieve nearly Bayes-minimum error rates while requiring relatively small amounts of memory. Our design procedure finds a set of close-opposed pairs of clusters of data. From these pairs the procedure generates a piecewise-linear approximation of the Bayes-optimum decision surface. A window training procedure on each linear segment of the approximation provides great flexibility of design over a wide range of class densities. The data consumed in the training of each segment are restricted to just those data lying near that segment, which makes possible the construction of efficient data bases for the training process. Interactive simplification of the classifier is facilitated by an adjacency matrix and an incidence matrix. The adjacency matrix describes the interrelationships of the linear segments {£i}. The incidence matrix describes the interrelationships among the polyhedrons formed by the hyperplanes containing {£i}. We exploit switching theory to minimize the decision logic.
---
paper_title: A Recursive Partitioning Decision Rule for Nonparametric Classification

paper_content:

A new criterion for deriving a recursive partitioning decision rule for nonparametric classification is presented. The criterion is both conceptually and computationally simple, and can be shown to have strong statistical merit. The resulting decision rule is asymptotically Bayes' risk efficient. The notion of adaptively generated features is introduced and methods are presented for dealing with missing features in both training and test vectors.
---
paper_title: A Nonparametric Partitioning Procedure for Pattern Classification

paper_content:

A nonparametric procedure is developed for determining a structure for multivariate, multiclass pattern classification. The resultant classifier is in the form of a layered machine which is composed of multithreshold elements. The basic algorithm determines partitions which are parallel hyperplanes orthogonal to the feature coordinate dimensions. Inherent in the procedure is the concept of a transgenerator unit used to establish new feature dimensions such that effective partitioning can be obtained. While the choice of which classes of transgeneration units to consider is ultimately up to the user, a number of such units are suggested herein. The algorithm gives an indication as to the effectiveness of various transgeneration units and hence can also be used in an interactive manner if so desired for the actual design of a classification structure.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Tree-Structured Classification via Generalized Discriminant Analysis

paper_content:

Abstract The problem of constructing classification rules that can be represented as decision trees is considered. Each object to be classified has an associated x vector containing possibly incomplete covariate information. Tree construction is based on the information provided in a “learning sample” of objects with known class identities. The x vectors in the learning sample may have missing values as well. Procedures are proposed for each of the components of classifier construction, such as split selection, tree-size determination, treatment of missing values, and ranking of variables. The main idea is recursive application of linear discriminant analysis, with the variables at each stage being appropriately chosen according to the data and the type of splits desired. Standard statistical techniques used as basic building blocks include analysis of variance, linear and canonical discriminant analysis, and principal component analysis. A new method of tree-structured classification is obtained by assem...
---
paper_title: A method for the design of binary tree classifiers

paper_content:

Abstract A method based on multivariate stepwise regression is proposed for the design of binary tree classifiers. Experimental results of cell classification are given to illustrate the efficiency of the proposed method.
---
paper_title: Automated design of linear tree classifiers

paper_content:

Abstract An automated method is presented for the design of linear tree classifiers, i.e. tree classifiers in which a decision based on a linear sum of features is carried out at each node. The method exploits the discriminability of Tomek links joining opposed pairs of data points in multidimensional feature space to produce a hierarchically structured piecewise linear decision function. The corresponding decision surface is optimized by a gradient descent that maximizes the number of Tomek links cut by each linear segment of the decision surface, followed by training each node's linear decision segment on the data associated with that node. Experiments on real data obtained from ship images and character images suggest that the accuracy of the tree classifier designed by this scheme is comparable to that of the k -NN classifier while providing much greater decision speeds, and that the trade-off between the speed and the accuracy in pattern classification can be controlled by bounding the number of features to be used at each node of the tree. Further experiments comparing the classification errors of our tree classifier with the tree classifier produced by the Mui/Fu technique indicate that our tree classifier is no less accurate and often much faster than the Mui/Fu classifier.
---
paper_title: An Automated Approach to the Design of Decision Tree Classifiers

paper_content:

The classification of large dimensional data sets arising from the merging of remote sensing data with more traditional forms of ancillary data causes a significant computational problem. Decision tree classification is a popular approach to the problem. This type of classifier is characterized by the property that samples are subjected to a sequence of decision rules before they are assigned to a unique class. If a decision tree classifier is well designed, the result in many cases is a classification scheme which is accurate, flexible, and computationally efficient. This correspondence provides an automated technique for effective decision tree design which relies only on a priori statistics. This procedure utilizes canonical transforms and Bayes table look-up decision rules. An optimal design at each node is derived based on the associated decision table. A procedure for computing the global probability of correct classification is also provided. An example is given in which class statistics obtained from an actual Landsat scene are used as input to the program. The resulting decision tree design has an associated probability of correct classification of 0.75 compared to the theoretically optimum 0.79 probability of correct classification associated with a full dimensional Bayes classifier. Recommendations for future research are included.
---
paper_title: A multiclass nonparametric partitioning algorithm

paper_content:

Abstract Parametric classification procedures may not be optimal in real classification problems because the properties of the features are not in agreement with the assumptions made. Nonparametric procedures are valuable tools for the design of classifiers in these cases. This paper reviews a few algorithms from the literature which formed the basis for a procedure with the following properties: • - it generates a binary decision tree, • - it can handle mixed data types (discrete and continuous), • - it performs the feature and criterion selection simultaneously, • - it can handle multiclass problems, • - it is interactive and hence enables the user to control the design procedure. The performance of the algorithm will be demonstrated with a few examples.
---
paper_title: Analysis and Design of a Decision Tree Based on Entropy Reduction and Its Application to Large Character Set Recognition

paper_content:

Based on a recursive process of reducing the entropy, the general decision tree classifier with overlap has been analyzed. Several theorems have been proposed and proved. When the number of pattern classes is very large, the theorems can reveal both the advantages of a tree classifier and the main difficulties in its implementation. Suppose H is Shannon's entropy measure of the given problem. The theoretical results indicate that the tree searching time can be minimized to the order O(H), but the error rate is also in the same order O(H) due to error accumulation. However, the memory requirement is in the order 0(H exp(H)) which poses serious problems in the implementation of a tree classifier for a large number of classes. To solve these problems, several theorems related to the bounds on the search time, error rate, memory requirement and overlap factor in the design of a decision tree have been proposed and some principles have been established to analyze the behaviors of the decision tree. When applied to classify sets of 64, 450, and 3200 Chinese characters, respectively, the experimental results support the theoretical predictions. For 3200 classes, a very high recognition rate of 99.88 percent was achieved at a high speed of 873 samples/s when the experiment was conducted on a Cyber 172 computer using a high-level language.
---
paper_title: An Algorithm for Constructing Optimal Binary Decision Trees

paper_content:

We consider the problem of optimally partitioning an n-dimensional lattice, L = L, X ... X LN, where Lj is a one-dimensional lattice with kj elements, by means of a binary tree into specified (labeled) subsets of L. Such lattices arise from problems in pattern classification, in nonlinear regression, in defining logical equations, and a number of related areas. When viewed as the partitioning of a vector space, each point in the lattice corresponds to a subregion of the space which is relatively homogeneous with respect to classification or range of a dependent variable. Optimality is defined in terms of a general cost function which includes the following: 1) min-max path length (i. e., minimize the maximum number of nodes traversed in making a decision); 2) minimum number of nodes in the tree; and 3) expected path length. It is shown that an optimal tree can be recursively constructed through the application of invariant imbedding (dynamic programming). An algorithm is detailed which embodies this recursive approach. The algorithm allows the assignment of a "don't care" label to elements of L.
---
paper_title: Generalized regression trees

paper_content:

Abstract Trees are powerful tools to describe and organize knowledge. As a method of data analysis, trees are used in many disciplines to structure a priori knowledge as well as to formulate and test hypotheses. The author outlines in this paper a general approach to tree-growing whose goal is to predict a parameter of a statistical method, i.e., to develop a general framework for constructing regression trees from data in the context of a generalized regression model (GLIM). Problems of overfit bias and suggestions for further work are discussed.
---
paper_title: C4.5: Programs for Machine Learning

paper_content:

From the Publisher: ::: Classifier systems play a major role in machine learning and knowledge-based systems, and Ross Quinlan's work on ID3 and C4.5 is widely acknowledged to have made some of the most significant contributions to their development. This book is a complete guide to the C4.5 system as implemented in C for the UNIX environment. It contains a comprehensive guide to the system's use , the source code (about 8,800 lines), and implementation notes. The source code and sample datasets are also available on a 3.5-inch floppy diskette for a Sun workstation. ::: ::: C4.5 starts with large sets of cases belonging to known classes. The cases, described by any mixture of nominal and numeric properties, are scrutinized for patterns that allow the classes to be reliably discriminated. These patterns are then expressed as models, in the form of decision trees or sets of if-then rules, that can be used to classify new cases, with emphasis on making the models understandable as well as accurate. The system has been applied successfully to tasks involving tens of thousands of cases described by hundreds of properties. The book starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting. Advantages and disadvantages of the C4.5 approach are discussed and illustrated with several case studies. ::: ::: This book and software should be of interest to developers of classification-based intelligent systems and to students in machine learning and expert systems courses.
---
paper_title: A combined nonparametric approach to feature selection and binary decision tree design

paper_content:

Abstract An efficient procedure which integrates feature selection and binary decision tree construction is presented. The nonparametric approach is based on the Kolmogorov-Smirnov criterion which yields an optimal classification decision at each node. By combining the feature selection with the design of the classifier, only the most informative features are retained for classification.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Tree classifier design with a permutation statistic

paper_content:

Abstract This paper proposes a permutation statistic as a basis for designing binary tree classifiers of d -dimensional patterns. The statistic permits an objective and easily interpreted evaluation of a (feature, threshold) pair that is the core of the design paradigm. It has a known distribution that is independent of the number of training patterns. After defining the permutation statistic and explaining its properties, the paper proposes the design procedure whereby each non-terminal node is assigned a feature and a threshold on that feature. The design procedure is demonstrated on six test sets and compared to designs based on mutual information.
---
paper_title: Optimal partitioning for classification and regression trees

paper_content:

An iterative algorithm that finds a locally optimal partition for an arbitrary loss function, in time linear in N for each iteration is presented. The algorithm is a K-means-like clustering algorithm that uses as its distance measure a generalization of Kullback's information divergence. Moreover, it is proven that the globally optimal partition must satisfy a nearest neighbour condition using divergence as the distance measure. These results generalize similar results of L. Breiman et al. (1984) to an arbitrary number of classes or regression variables and to an arbitrary number of bills. Experimental results on a text-to-speech example are provided and additional applications of the algorithm, including the design of variable combinations, surrogate splits, composite nodes, and decision graphs, are suggested. >
---
paper_title: Problems in the Analysis of Survey Data, and a Proposal

paper_content:

Abstract Most of the problems of analyzing survey data have been reasonably well handled, except those revolving around the existence of interaction effects. Indeed, increased efficiency in handling multivariate analyses even with non-numerical variables, has been achieved largely by assuming additivity. An approach to survey data is proposed which imposes no restrictions on interaction effects, focuses on Importance in reducing predictive error, operates sequentially, and is independent of the extent of linearity in the classifications or the order in which the explanatory factors are introduced.
---
paper_title: On Tree Structured Classifiers

paper_content:

Abstract Classification trees constitute an important and increasingly popular form of hierarchical classifiers. We first describe and compare classification trees and feedforward neural network classifiers. We then focus on the specific problem of obtaining right-sized trees, i.e., trees which neither underfit nor overfit the data. A new efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. Numerical results on a waveform recognition problem are presented.
---
paper_title: An iterative growing and pruning algorithm for classification tree design

paper_content:

An efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative tree growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view. >
---
paper_title: Hierarchical Classifier Design Using Mutual Information

paper_content:

A nonparametric algorithm is presented for the hierarchical partitioning of the feature space. The algorithm is based on the concept of average mutual information, and is suitable for multifeature multicategory pattern recognition problems. The algorithm generates an efficient partitioning tree for specified probability of error by maximizing the amount of average mutual information gain at each partitioning step. A confidence bound expression is presented for the resulting classifier. Three examples, including one of handprinted numeral recognition, are presented to demonstrate the effectiveness of the algorithm.
---
paper_title: Classification trees with neural network feature extraction

paper_content:

The ideal use of small multilayer nets at the decision nodes of a binary classification tree to extract nonlinear features is proposed. The nets are trained and the tree is grown using a gradient-type learning algorithm in the multiclass case. The method improves on standard classification tree design methods in that it generally produces trees with lower error rates and fewer nodes. It also reduces the problems associated with training large unstructured nets and transfers the problem of selecting the size of the net to the simpler problem of finding a tree of the right size. An efficient tree pruning algorithm is proposed for this purpose. Trees constructed with the method and the CART method are compared on a waveform recognition problem and a handwritten character recognition problem. The approach demonstrates significant decrease in error rate and tree size. It also yields comparable error rates and shorter training times than a large multilayer net trained with backpropagation on the same problems. >
---
paper_title: Univariate Two-Population Distribution-Free Discrimination

paper_content:

Abstract A distribution-free procedure for classifying a univariate random variable, z, into one of two populations on the basis of a sample of size N, in which m members are classified into one population and the remaining (N – m) into the other, is given as follows: Let t(z) = k(z) – h(z), where k(z) is the number of observations from the first population which are less than z and h(z) is similarly defined for the second population. If z ≦ ζ*, where ζ* is that value of z for which t(z) is a maximum, classify z into the first population, otherwise into the second. The probability of correct classification, and its estimate, [N – m + t(ζ*)]/N, both converge in probability to the maximum attainable probability of correct classification.
---
paper_title: A theory of the learnable

paper_content:

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Convergence of stochastic processes

paper_content:

I Functional on Stochastic Processes.- 1. Stochastic Processes as Random Functions.- Notes.- Problems.- II Uniform Convergence of Empirical Measures.- 1. Uniformity and Consistency.- 2. Direct Approximation.- 3. The Combinatorial Method.- 4. Classes of Sets with Polynomial Discrimination.- 5. Classes of Functions.- 6. Rates of Convergence.- Notes.- Problems.- III Convergence in Distribution in Euclidean Spaces.- 1. The Definition.- 2. The Continuous Mapping Theorem.- 3. Expectations of Smooth Functions.- 4. The Central Limit Theorem.- 5. Characteristic Functions.- 6. Quantile Transformations and Almost Sure Representations.- Notes.- Problems.- IV Convergence in Distribution in Metric Spaces.- 1. Measurability.- 2. The Continuous Mapping Theorem.- 3. Representation by Almost Surely Convergent Sequences.- 4. Coupling.- 5. Weakly Convergent Subsequences.- Notes.- Problems.- V The Uniform Metric on Spaces of Cadlag Functions.- 1. Approximation of Stochastic Processes.- 2. Empirical Processes.- 3. Existence of Brownian Bridge and Brownian Motion.- 4. Processes with Independent Increments.- 5. Infinite Time Scales.- 6. Functional of Brownian Motion and Brownian Bridge.- Notes.- Problems.- VI The Skorohod Metric on D(0, ?).- 1. Properties of the Metric.- 2. Convergence in Distribution.- Notes.- Problems.- VII Central Limit Theorems.- 1. Stochastic Equicontinuity.- 2. Chaining.- 3. Gaussian Processes.- 4. Random Covering Numbers.- 5. Empirical Central Limit Theorems.- 6. Restricted Chaining.- Notes.- Problems.- VIII Martingales.- 1. A Central Limit Theorem for Martingale-Difference Arrays.- 2. Continuous Time Martingales.- 3. Estimation from Censored Data.- Notes.- Problems.- Appendix A Stochastic-Order Symbols.- Appendix B Exponential Inequalities.- Notes.- Problems.- Appendix C Measurability.- Notes.- Problems.- References.- Author Index.
---
paper_title: A Theory of Learning and Generalization

paper_content:

From the Publisher: ::: How does it differ from first edition? Includes new material on: * support vector machines (SVM's), * fat shattering dimensions * applications to neural network learning, * learning with dependent samples generated by beta-mixing process, * connections between system identification and learning theory * probabilistic solution of "intractable" problems in robust control and matrix theory using randomised algorithms. In addition, solutions to some open problems posed in the first edition are included, and new open problems are added. The author is a respected authority in the field of control and systems theory. This new edition, with substantial new material, takes account of important new developments in the theory of learning. It also deals extensively with the theory of learning control systems, which has now reached a level of maturity comparable to that of learning of neural networks. The book is written in a manner that would suit self-study and contains comprehensive references. The chapters are also written to be as autonomous as possible and contain updated open problems to enhance further research and self-study.
---
paper_title: An Introduction to Computational Learning Theory

paper_content:

The probably approximately correct learning model Occam's razor the Vapnik-Chervonenkis dimension weak and strong learning learning in the presence of noise inherent unpredictability reducibility in PAC learning learning finite automata by experimentation appendix - some tools for probabilistic analysis.
---
paper_title: Decision theoretic generalizations of the PAC model for neural net and other learning applications

paper_content:

We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x in X and an outcome y in Y , and tries to find a hypothesis h : X --< A , where h in H , that specifies the appropriate action a in A to take for each instance x , in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X times Y . Special cases include the problem of learning a function from X into Y , the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation). We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H , and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Pollard''s work, and a notion of *capacity* and *metric dimension* for classes of functions that map into a bounded metric space. (Supersedes 89-30 and 90-52.) [Also in "Information and Computation", Vol. 100, No.1, September 1992]
---
paper_title: Active Learning Using Arbitrary Binary Valued Queries

paper_content:

The original and most widely studied PAC model for learning assumes a passive learner in the sense that the learner plays no role in obtaining information about the unknown concept. That is, the samples are simply drawn independently from some probability distribution. Some work has been done on studying more powerful oracles and how they affect learnability. To find bounds on the improvement in sample complexity that can be expected from using oracles, we consider active learning in the sense that the learner has complete control over the information received. Specifically, we allow the learner to ask arbitrary yes/no questions. We consider both active learning under a fixed distribution and distribution-free active learning. In the case of active learning, the underlying probability distribution is used only to measure distance between concepts. For learnability with respect to a fixed distribution, active learning does not enlarge the set of learnable concept classes, but can improve the sample complexity. For distribution-free learning, it is shown that a concept class is actively learnable iff it is finite, so that active learning is in fact less powerful than the usual passive learning model. We also consider a form of distribution-free learning in which the learner knows the distribution being used, so that “distribution-free” refers only to the requirement that a bound on the number of queries can be obtained uniformly over all distributions. Even with the side information of the distribution being used, a concept class is actively learnable iff it has finite VC dimension, so that active learning with the side information still does not enlarge the set of learnable concept classes.
---
paper_title: Bounds for the uniform deviation of empirical measures

paper_content:

If X1,...,Xn are independent identically distributed Rd-valued random vectors with probability measure [mu] and empirical probability measure [mu]n, and if is a subset of the Borel sets on Rd, then we show that P{supA[set membership, variant][mu]n(A)-[mu](A)>=[var epsilon]}
---
paper_title: Lower bounds in pattern recognition and learning

paper_content:

Lower bounds are derived for the performance of any pattern recognition algorithm, which, using training data, selects a discrimination rule from a certain class of rules. The bounds involve the Vapnik-Chervonenkis dimension of the class, and L, the minimal error probability within the class. We provide lower bounds when L = 0 (the usual assumption in Valiant's theory of learning) and L > 0.
---
paper_title: Learning by Canonical Smooth Estimation, Part I: Simultaneous Estimation

paper_content:

This paper examines the problem of learning from examples in a framework that is based on, but more general than, Valiant's probably approximately correct (PAC) model for learning. In our framework, the Learner observes examples that consist of sample points drawn and labeled according to a fixed, unknown probability distribution. Based on this empirical data, the learner must select, from a set of candidate functions, a par- ticular function or "hypothesis" that will accurately predict the labels of future sample points. The expected mismatch between a hypothesis' prediction and the label of a new sample point is called the hypothesis' "generalization error." Following the pioneering work of Vapnik and Chervonenkis, others have attacked this sort of learning problem by finding hypotheses that minimize the relative frequency-based empirical error estimate. We generalize this approach by examining the "simultaneous estimation" problem: When does some procedure exist for estimating the generalization error of all of the candidate hypotheses, simultaneously, from the same labeled sample? We demonstrate how one can learn from such a simultaneous error estimate and propose a new class of estimators called "smooth estimators" that, in many cases of interest, contains the empirical estimator. We characterize the class of simultaneous estimation problems solvable by a smooth estimator and give a canonical form for the smooth simultaneous estimator.
---
paper_title: Mathematical foundations of neurocomputing

paper_content:

An attempt is made to establish a mathematical theory that shows the intrinsic mechanisms, capabilities, and limitations of information processing by various architectures of neural networks. A method of statistically analyzing one-layer neural networks is given, covering the stability of associative mapping and mapping by totally random networks. A fundamental problem of statistical neurodynamics is considered in a way that is different from the spin-glass approach. A dynamic analysis of associative memory models and a general theory of neural learning, in which the learning potential function plays a role, are given. An advanced theory of learning and self-organization is proposed, covering backpropagation and its generalizations as well as the formation of topological maps and neural representations of information. >
---
paper_title: The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality

paper_content:

Let F^ n denote the empirical distribution function for a sample of n i.i.d. random variables with distribution function F. In 1956 Dvoretzky, Kiefer and Wolfowitz proved that P(√n sup x (F^ n (x)−F(x))>λ)≤C exp(−2λ 2 ), where C is some unspecified constant. We show that C can be taken as 1, provided that exp(−2λ 2 )≤1/2. In particular, the two-sided inequality P(√n sup x |F^ n (x)−F(x)|>λ)≤2 exp(−2λ 2 ) holds without any restriction on λ. In the one-sided as well as in the two-sided case, the constants cannot be further improved
---
paper_title: Bounding sample size with the Vapnik-Chervonenkis dimension

paper_content:

A proof that a concept class is learnable provided the Vapnik—Chervonenkis dimension is finite is given. The proof is more explicit than previous proofs and introduces two new parameters which allow bounds on the sample size obtained to be improved by a factor of approximately 4 log2(e).
---
paper_title: Distribution-free consistency results in nonparametric discrimination and regression function estimation

paper_content:

first proposed by Watson (1964) and Nadaraya (1964) . In (1) k is a nonnegative function on R" and {h} n is a sequence of positive numbers . The pointwise consistency of (1) is discussed by Watson (1964), Nadaraya (1964, 1965), Rosenblatt (1969), Schuster (1972), Greblicki (1974) and Noda (1976) . The uniform consistency is treated in the papers by Nadaraya (1965, 1970), Greblicki (1974) and Devroye (1978a) .
---
paper_title: On the density of families of sets

paper_content:

If T is a family of sets and A some set we denote by T ∩ A the following family of subsets of A: T ∩ A = {F ∩ A; F ϵ T}. P. Erdos (oral communication) transmitted to me in Nice the following question: Is it true that if T is a family of subsets of some infinite set S then either there exists to each number n a set A ⊂ S with |A| = n such that |T ∩ A| = 2n or there exists some number N such that |T ∩ A| ⩽ |A|c for each A ⊂ S with |A| ⩾ N and some constant c? In this paper we will answer this question in the affirmative by determining the exact upper bound. (Theorem 2).1
---
paper_title: A Data-Dependent Skeleton Estimate and a Scale-Sensitive Dimension for Classification

paper_content:

The classical binary classification problem is investigated when it is known in advance that the posterior probability function (or regression function) belongs to some class of functions. We introduce and analyze a method which effectively exploits this knowledge. The method is based on minimizing the empirical risk over a carefully selected ``skeleton'' of the class of regression functions. The skeleton is a covering of the class based on a data--dependent metric, especially fitted for classification. A new scale--sensitive dimension is introduced which is more useful for the studied classification problem than other, previously defined, dimension measures. This fact is demonstrated by performance bounds for the skeleton estimate in terms of the new dimension.
---
paper_title: Vapnik-Chervonenkis bounds for generalization

paper_content:

The authors review the Vapnik and Chervonenkis theorem as applied to the problem of generalization. By combining some of the technical modifications proposed in the literature they derive tighter bounds and a new version of the theorem bounding the accuracy in the estimation of generalization probabilities from finite samples. A critical discussion and comparison with the results from statistical mechanics is given.
---
paper_title: Convergence of stochastic processes

paper_content:

I Functional on Stochastic Processes.- 1. Stochastic Processes as Random Functions.- Notes.- Problems.- II Uniform Convergence of Empirical Measures.- 1. Uniformity and Consistency.- 2. Direct Approximation.- 3. The Combinatorial Method.- 4. Classes of Sets with Polynomial Discrimination.- 5. Classes of Functions.- 6. Rates of Convergence.- Notes.- Problems.- III Convergence in Distribution in Euclidean Spaces.- 1. The Definition.- 2. The Continuous Mapping Theorem.- 3. Expectations of Smooth Functions.- 4. The Central Limit Theorem.- 5. Characteristic Functions.- 6. Quantile Transformations and Almost Sure Representations.- Notes.- Problems.- IV Convergence in Distribution in Metric Spaces.- 1. Measurability.- 2. The Continuous Mapping Theorem.- 3. Representation by Almost Surely Convergent Sequences.- 4. Coupling.- 5. Weakly Convergent Subsequences.- Notes.- Problems.- V The Uniform Metric on Spaces of Cadlag Functions.- 1. Approximation of Stochastic Processes.- 2. Empirical Processes.- 3. Existence of Brownian Bridge and Brownian Motion.- 4. Processes with Independent Increments.- 5. Infinite Time Scales.- 6. Functional of Brownian Motion and Brownian Bridge.- Notes.- Problems.- VI The Skorohod Metric on D(0, ?).- 1. Properties of the Metric.- 2. Convergence in Distribution.- Notes.- Problems.- VII Central Limit Theorems.- 1. Stochastic Equicontinuity.- 2. Chaining.- 3. Gaussian Processes.- 4. Random Covering Numbers.- 5. Empirical Central Limit Theorems.- 6. Restricted Chaining.- Notes.- Problems.- VIII Martingales.- 1. A Central Limit Theorem for Martingale-Difference Arrays.- 2. Continuous Time Martingales.- 3. Estimation from Censored Data.- Notes.- Problems.- Appendix A Stochastic-Order Symbols.- Appendix B Exponential Inequalities.- Notes.- Problems.- Appendix C Measurability.- Notes.- Problems.- References.- Author Index.
---
paper_title: A Theory of Learning and Generalization

paper_content:

From the Publisher: ::: How does it differ from first edition? Includes new material on: * support vector machines (SVM's), * fat shattering dimensions * applications to neural network learning, * learning with dependent samples generated by beta-mixing process, * connections between system identification and learning theory * probabilistic solution of "intractable" problems in robust control and matrix theory using randomised algorithms. In addition, solutions to some open problems posed in the first edition are included, and new open problems are added. The author is a respected authority in the field of control and systems theory. This new edition, with substantial new material, takes account of important new developments in the theory of learning. It also deals extensively with the theory of learning control systems, which has now reached a level of maturity comparable to that of learning of neural networks. The book is written in a manner that would suit self-study and contains comprehensive references. The chapters are also written to be as autonomous as possible and contain updated open problems to enhance further research and self-study.
---
paper_title: Probability Inequalities for Empirical Processes and a Law of the Iterated Logarithm

paper_content:

Given a class -F of functions on X, we can view Vn as a stochastic process indexed by -F and consider limit theorems for this process. To prove such theorems it is often helpful to have bounds on the tail of the r.v. sup _W I n(f ) I (see for example Dudley, 1978, Kuelbs and Dudley, 1980, Dudley and Phillip, 1983, or Gine and Zinn, 1983.) Our main question of interest is, for what classes -F can "best possible" bounds be obtained? So first we must ask, what are these best possible bounds? Of course
---
paper_title: Some special vapnik-chervonenkis classes

paper_content:

For a class C of subsets of a set X, let V(C) be the smallest n such that no n-element set F@?X has all its subsets of the form A @? F, A @? C. The condition V(C) <+~ has probabilistic implications. If any two-element subset A of X satisfies both A @? C = O and A @? D for some C, D@?C, then V(C)=2 if and only if C is linearly ordered by inclusion. If C is of the form C={@?^n"i"="1 C"i:C"i@?C"i, i=1,2,...,n}, where each C"i is linearly ordered by inclusion, then V(C)=0} for f in H, then V(C)=n.
---
paper_title: Improved upper bounds for probabilities of uniform deviations

paper_content:

We obtain Vapnik-Chervonenkis type upper bounds for the uniform deviation of probabilities from their expectations. The bounds sharpen previously known probability inequalities.
---
paper_title: ε-Entropy and ε-Capacity of Sets In Functional Spaces

paper_content:

The article is mainly devoted to the systematic exposition of results that were published in the years 1954–1958 by K. I. Babenko [1], A. G. Vitushkin [2,3], V. D. Yerokhin [4], A. N. Kolmogorov [5,6] and V. M. Tikhomirov [7]. It is natural that when these materials were systematically rewritten, several new theorems were proved and certain examples were computed in more detail. This review also incorporates results not published previously which go beyond the framework of such a systematization, and belong to V. I. Arnold (§6) and V. M. Tikhomirov (§§4,7 and §8).
---
paper_title: The Vapnik-Chervonenkis dimension of decision trees with bounded rank

paper_content:

Abstract We show that VCDIM( r DT n )=∑ r i =0( n i ),where r DT n denotes the set of all boolean functions on n bo olean variables defined by decision trees of rank at most r , and VCDIM( r DT n ) denotes its Vapnik-Chervonenkis dimension. It follows that the number of examples needed for pac-learning r DT n can be determined modulo a small factor.
---
paper_title: Decision theoretic generalizations of the PAC model for neural net and other learning applications

paper_content:

We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x in X and an outcome y in Y , and tries to find a hypothesis h : X --< A , where h in H , that specifies the appropriate action a in A to take for each instance x , in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X times Y . Special cases include the problem of learning a function from X into Y , the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation). We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H , and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Pollard''s work, and a notion of *capacity* and *metric dimension* for classes of functions that map into a bounded metric space. (Supersedes 89-30 and 90-52.) [Also in "Information and Computation", Vol. 100, No.1, September 1992]
---
paper_title: A Metric Entropy Bound is Not Sufficient for Learnability

paper_content:

The authors prove by means of a counterexample that it is not sufficient, for probably approximately correct (PAC) learning under a class of distributions, to have a uniform bound on the metric entropy of the class of concepts to be learned. This settles a conjecture of Benedek and Itai (1991). >
---
paper_title: Introduction to Neural Computing

paper_content:

Introduction - Why neural nets? Principles and promises. The McCulloch and Pitts legacy. The hard learning problem. Making neurons. The secrets of Wisard. Multi-layer perceptrons. Dynamic networks. Variations. Neurocontrol. Varieties of pattern analysis. Developments in weightless systems. Trends and promises.
---
paper_title: Minimum Complexity Regression Estimation with Weakly Dependent Observations

paper_content:

The minimum complexity regression estimation framework (Barron, 1991; Barron and Cover, 1991 and Rissanen, 1989) is a general data-driven methodology for estimating a regression function from a given list of parametric models using independent and identically distributed (i.i.d.) observations. We extend Barron's regression estimation framework to m-dependent observations and to strongly mixing observations. In particular, we propose abstract minimum complexity regression estimators for dependent observations, which may be adapted to a particular list of parametric models, and establish upper bounds on the statistical risks of the proposed estimators in terms of certain deterministic indices of resolvability. Assuming that the regression function satisfies a certain Fourier-transform-type representation, we examine minimum complexity regression estimators adapted to a list of parametric models based on neural networks and by using the upper bounds for the abstract estimators, we establish rates of convergence for the statistical risks of these estimators. Also, as a key tool, we extend the classical Bernstein inequality from i.i.d. random variables to m-dependent processes and to strongly mixing processes.
---
paper_title: An asymptotic property of model selection criteria

paper_content:

Probability models are estimated by use of penalized likelihood criteria related to the Akaike (1972) information criteria (AIC) and the minimum description length (MDL). The asymptotic risk of the density estimator is determined, under conditions on the penalty term, and is shown to be minimax optimal. As an application, we show that the optimal rate of convergence is achieved for the density in certain smooth nonparametric families without knowing the smooth parameters in advance.
---
paper_title: Minimum complexity density estimation

paper_content:

The authors introduce an index of resolvability that is proved to bound the rate of convergence of minimum complexity density estimators as well as the information-theoretic redundancy of the corresponding total description length. The results on the index of resolvability demonstrate the statistical effectiveness of the minimum description-length principle as a method of inference. The minimum complexity estimator converges to true density nearly as fast as an estimator based on prior knowledge of the true subclass of densities. Interpretations and basic properties of minimum complexity estimators are discussed. Some regression and classification problems that can be examined from the minimum description-length framework are considered. >
---
paper_title: Structural Risk Minimization Over Data-Dependent Hierarchies

paper_content:

The paper introduces some generalizations of Vapnik's (1982) method of structural risk minimization (SRM). As well as making explicit some of the details on SRM, it provides a result that allows one to trade off errors on the training sample against improved generalization performance. It then considers the more general case when the hierarchy of classes is chosen in response to the data. A result is presented on the generalization performance of classifiers with a "large margin". This theoretically explains the impressive generalization performance of the maximal margin hyperplane algorithm of Vapnik and co-workers (which is the basis for their support vector machines). The paper concludes with a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets. Four examples are given of such functions, including the Vapnik-Chervonenkis (1971) dimension measured on the sample.
---
paper_title: An experimental and theoretical comparison of model selection methods

paper_content:

We investigate the problem of {\it model\ selection} in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance between the complexity of the hypothesis chosen and its observed error on a random training sample of limited size, when the goal is that of minimizing the resulting generalization error. We undertake a detailed comparison of three well-known model selection methods — a variation of Vapnik‘s {\it Guaranteed\ Risk\ Minimization} (GRM), an instance of Rissanen‘s {\it Minimum\ Description\ Length\ Principle} (MDL), and (hold-out) cross validation (CV). We introduce a general class of model selection methods (called {\it penalty-based} methods) that includes both GRM and MDL, and provide general methods for analyzing such rules. We provide both controlled experimental evidence and formal theorems to support the following conclusions: ::: ::: \bulletEven on simple model selection problems, the behavior of the methods examined can be both complex and incomparable. Furthermore, no amount of “tuning” of the rules investigated (such as introducing constant multipliers on the complexity penalty terms, or a distribution-specific “effective dimension”) can eliminate this incomparability. ::: ::: \bulletIt is possible to give rather general bounds on the generalization error, as a function of sample size, for penalty-based methods. The quality of such bounds depends in a precise way on the extent to which the method considered automatically limits the complexity of the hypothesis selected. ::: ::: \bulletFor {\it any} model selection problem, the additional error of cross validation compared to {\it any} other method can be bounded above by the sum of two terms. The first term is large only if the learning curve of the underlying function classes experiences a phase transition” between (1-\gamma)m andm examples (where \gamma is the fraction saved for testing in CV). The second and competing term can be made arbitrarily small by increasing\gamma . ::: ::: \bulletThe class of penalty-based methods is fundamentally handicapped in the sense that there exist two types of model selection problems for which every penalty-based method must incur large generalization error on at least one, while CV enjoys small generalization error on both.
---
paper_title: Risk bounds for model selection via penalization

paper_content:

Performance bounds for criteria for model selection are developed using recent theory for sieves. The model selection criteria are based on an empirical loss or contrast function with an added penalty term motivated by empirical process theory and roughly proportional to the number of parameters needed to describe the model divided by the number of observations. Most of our examples involve density or regression estimation settings and we focus on the problem of estimating the unknown density or regression function. We show that the quadratic risk of the minimum penalized empirical contrast estimator is bounded by an index of the accuracy of the sieve. This accuracy index quantifies the trade-off among the candidate models between the approximation error and parameter dimension relative to sample size.
---
paper_title: Statistical learning networks: A unifying view

paper_content:

A frequency detection circuit having an input transistor connected to the primary winding of a coupling transformer. In the secondary winding circuit of the transformer there is connected a diode which cooperates with a parallel arrangement of a resistor and a capacitor arranged so that the current flowing through the resistor depends solely on the frequency of the input signal applied to the input transistor. The frequency detection circuit can simultaneously carry out a number of control functions in response to a corresponding number of frequencies of the input signal.
---
paper_title: Introduction To The Theory Of Neural Computation

paper_content:

From the Publisher: ::: This book is a comprehensive introduction to the neural network models currently under intensive study for computational applications. It is a detailed, logically-developed treatment that covers the theory and uses of collective computational networks, including associative memory, feed forward networks, and unsupervised learning. It also provides coverage of neural network applications in a variety of problems of both theoretical and practical interest.
---
paper_title: Brains, Machines, and Mathematics

paper_content:

This is a book whose time has come-again. The first edition (published by McGraw-Hill in 1964) was written in 1962, and it celebrated a number of approaches to developing an automata theory that could provide insights into the processing of information in brainlike machines, making it accessible to readers with no more than a college freshman's knowledge of mathematics. The book introduced many readers to aspects of cybernetics-the study of computation and control in animal and machine. But by the mid-1960s, many workers abandoned the integrated study of brains and machines to pursue artificial intelligence (AI) as an end in itself-the programming of computers to exhibit some aspects of human intelligence, but with the emphasis on achieving some benchmark of performance rather than on capturing the mechanisms by which humans were themselves intelligent. Some workers tried to use concepts from AI to model human cognition using computer programs, but were so dominated by the metaphor "the mind is a computer" that many argued that the mind must share with the computers of the 1960s the property of being serial, of executing a series of operations one at a time. As the 1960s became the 1970s, this trend continued. Meanwhile, experi mental neuroscience saw an exploration of new data on the anatomy and physiology of neural circuitry, but little of this research placed these circuits in the context of overall behavior, and little was informed by theoretical con cepts beyond feedback mechanisms and feature detectors."
---
paper_title: Introduction to Neural Computing

paper_content:

Introduction - Why neural nets? Principles and promises. The McCulloch and Pitts legacy. The hard learning problem. Making neurons. The secrets of Wisard. Multi-layer perceptrons. Dynamic networks. Variations. Neurocontrol. Varieties of pattern analysis. Developments in weightless systems. Trends and promises.
---
paper_title: Stochastic Dynamics of Neural Networks

paper_content:

The dynamics of stochastic neural networks are presented. The model is an algorithm based upon the assumption that the activities of neurons are asynchronous. It is proven that networks with fixed synaptic efficacies cannot sustain oscillating activities. Following Choi and Huberman, the dynamics of instantaneous frequencies is derived. The equations are solved for associative and for recursive networks by introducing order parameters coupled to stored patterns. It is shown that the networks relax towards one of the stored configurations in a matter of a few refractory periods, whatever the size of the network. The relaxation time diverges in recursive networks at a critical noise Bc, above which no stored pattern can be retrieved. These results have been confirmed using computer simulations.
---
paper_title: Mathematical foundations of neurocomputing

paper_content:

An attempt is made to establish a mathematical theory that shows the intrinsic mechanisms, capabilities, and limitations of information processing by various architectures of neural networks. A method of statistically analyzing one-layer neural networks is given, covering the stability of associative mapping and mapping by totally random networks. A fundamental problem of statistical neurodynamics is considered in a way that is different from the spin-glass approach. A dynamic analysis of associative memory models and a general theory of neural learning, in which the learning potential function plays a role, are given. An advanced theory of learning and self-organization is proposed, covering backpropagation and its generalizations as well as the formation of topological maps and neural representations of information. >
---
paper_title: Convergent activation dynamics in continuous time networks

paper_content:

Abstract The activation dynamics of nets are considered from a rigorous mathematical point of view. A net is identified with the dynamical system defined by a continuously differentiable vector field on the space of activation vectors, with fixed weights, biases, and inputs. Chaotic and oscillatory nets are briefly discussed, but the main goal is to find conditions guaranteeing that the trajectory of every (or almost every) initial activation state converges to an equilibrium. Several new results of this type are proved. These are illustrated with applications to additive nets. Cascades of nets are considered and a cascade decomposition theorem is proved. An extension of the Cohen-Grossberg convergence theorem is proved for certain nets with nonsymmetric weight matrices.
---
paper_title: The capacity of the Hopfield associative memory

paper_content:

Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory stores n -tuple of \pm 1 's. The components change depending on a hard-limited version of linear functions of all other components. With symmetric connections between components, a stable state is ultimately reached. By building up the connection matrix as a sum-of-outer products of m fundamental memories, one hopes to be able to recover a certain one of the m memories by using an initial n -tuple probe vector less than a Hamming distance n/2 away from the fundamental memory. If m fundamental memories are chosen at random, the maximum asympotic value of m in order that most of the m original memories are exactly recoverable is n/(2 \log n) . With the added restriction that every one of the m fundamental memories be recoverable exactly, m can be no more than n/(4 \log n) asymptotically as n approaches infinity. Extensions are also considered, in particular to capacity under quantization of the outer-product connection matrix. This quantized memory capacity problem is closely related to the capacity of the quantized Gaussian channel.
---
paper_title: Programmed interactions in higher-order neural networks: The outer-product algorithm

paper_content:

Abstract Recent results on the memory storage capacity of the outer-product algorithm indicate that the algorithm stores of the order of n /log n memories in a network of n fully interconnected linear threshold elements when it is required that each memory be exactly recovered from a probe which is close enough to it. In this paper a rigourous analysis is presented of generalizations of the outer-product algorithm to higher-order networks of densely interconnected polynomial thresh-old units of degree d . Precise notions of memory storage capacity are formulated, and it is demonstrated that both static and dynamic storage capacities of all variants of the outer-product algorithm of degree d are of the order of n d /log n .
---
paper_title: Neural networks and physical systems with emergent collective computational abilities

paper_content:

Abstract ::: Computational properties of use of biological organisms or to the construction of computers can emerge as collective properties of systems having a large number of simple equivalent components (or neurons). The physical meaning of content-addressable memory is described by an appropriate phase space flow of the state of a system. A model of such a system is given, based on aspects of neurobiology but readily adapted to integrated circuits. The collective properties of this model produce a content-addressable memory which correctly yields an entire memory from any subpart of sufficient size. The algorithm for the time evolution of the state of the system is based on asynchronous parallel processing. Additional emergent collective properties include some capacity for generalization, familiarity recognition, categorization, error correction, and time sequence retention. The collective properties are only weakly sensitive to details of the modeling or the failure of individual devices.
---
paper_title: Harmonic Analysis of polynomial threshold functions

paper_content:

The analysis of linear threshold Boolean functions has recently attracted the attention of those interested in circuit complexity as well as of those interested in neural networks. Here a generalization of linear threshold functions is defined, namely, polynomial threshold functions, and its relation to the class of linear threshold functions is investigated.A Boolean function is polynomial threshold if it can be represented as a sign function of a polynomial that consists of a polynomial (in the number of variables) number of terms. The main result of this paper is showing that the class of polynomial threshold functions (which is called $PT_1 $) is strictly contained in the class of Boolean functions that can be computed by a depth 2, unbounded fan-in polynomial size circuit of linear threshold gates (which is called $LT_2 $).Harmonic analysis of Boolean functions is used to derive a necessary and sufficient condition for a function to be an S-threshold function for a given set S of monomials. This cond...
---
paper_title: Programmed interactions in higher-order neural networks: Maximal capacity

paper_content:

Abstract The focus of the paper is the estimation of the maximum number of states that can be made stable in higher-order extensions of neural network models. Each higher-order neuron in a network of n elements is modeled as a polynomial threshold element of degree d . It is shown that regardless of the manner of operation, or the algorithm used, the storage capacity of the higher-order network is of the order of one bit per interaction weight. In particular, the maximal (algorithm independent) storage capacity realizable in a recurrent network of n higher-order neurons of degree d is of the order of n d d! . A generalization of a spectral algorithm for information storage is introduced and arguments adducing near optimal capacity for the algorithm are presented.
---
paper_title: Absolute stability of global pattern formation and parallel memory storage by competitive neural networks

paper_content:

Systems that are competitive and possess symmetric interactions admit a global Lyapunov function. However, a global Lyapunov function whose equilibrium set can be effectively analyzed has not yet been discovered. It remains an open question whether the Lyapunov function approach, which requires a study of equilibrium points, or an alternative global approach, such as the Lyapunov functional approach, which sidesteps a direct study of equilibrium points will ultimately handle all of the physically important cases.
---
paper_title: Memory capacity in neural network models: Rigorous lower bounds ☆

paper_content:

We consider certain simple neural network models of associative memory with N binary neurons and symmetric lth order synaptic connections, in which m randomly chosen N-bit patterns are to be stored and retrieved with a small fraction δ of bit errors allowed. Rigorous proofs of the following are presented both for l = 2 and l ≥ 3: ::: 1. ::: 1. m can grow as fast as αNl−1. ::: ::: 2. ::: 2. α can be as large as Bl/ln(1/δ) as δ → 0. ::: ::: 3. ::: 3. Retrieved memories overlapping with several initial patterns persist for (very) small α. ::: ::: ::: ::: ::: These phenomena were previously supported by numerical simulations or nonrigorous calculations. The quantity (l!) · α represents the number of stored bits per distinct synapse. The constant (l!) · Bl is determined explicitly; it decreases monotonically with l and tends to zero exponentially fast as l → ∞. We obtain rigorous lower bounds for the threshold value (l!) · αc (the maximum possible value of (l!) · α with δ unconstrained): 0.11 for l = 2 (compared to the actual value between 0.28 and 0.30 as estimated by Hopfield and by Amit, Gutfreund, and Sompolinsky), 0.22 for l = 3 and 0.16 for l = 4; as l → ∞, the bound tends to zero as fast as (l!) · Bl.
---
paper_title: Convergence results in an associative memory model

paper_content:

Abstract This paper presents rigorous mathematical proofs for some observed convergence phenomena in an associative memory model introduced by Hopfield (based on Hebbian rules) for storing a number of random n-bit patterns. The capability of the model to correct a linear number of random errors in a bit pattern has been established earlier, but the existence of a large domain of attraction (correcting a linear number of arbitrary errors) has not been proved. We present proofs for the following: • • When m , the number of patterns stored, is less than n /(4 log n ) , the fundamental memories have a domain of attraction of radius ρn with ρ = 0.024 , and the algorithm converges in time O (log log n ) . • • When m = α n (with α small), all patterns within a distance ρn from a fundamental memory end up, in constant time, within a distance ϵn from the fundamental memory, where ϵ is about e −1/4α We also extend somewhat Newman's description of the “energy landscape,” and prove the existence of an exponential number of stable states (extraneous memories) with convergence properties similar to those of the fundamental memories.
---
paper_title: Recurrent Backpropagation and the Dynamical Approach to Adaptive Neural Computation

paper_content:

Error backpropagation in feedforward neural network models is a popular learning algorithm that has its roots in nonlinear estimation and optimization. It is being used routinely to calculate error gradients in nonlinear systems with hundreds of thousands of parameters. However, the classical architecture for backpropagation has severe restrictions. The extension of backpropagation to networks with recurrent connections will be reviewed. It is now possible to efficiently compute the error gradients for networks that have temporal dynamics, which opens applications to a host of problems in systems identification and control.
---
paper_title: The Sigmoid Nonlinearity in Prepyriform Cortex

paper_content:

We report a study on the relationship between EEG amplitude values and unit spike output in the prepyriform cortex of awake and motivated rats. This relationship takes the form of a sigmoid curve, that describes normalized pulse-output for normalized wave input. The curve is fitted using nonlinear regression and is described by its slope and maximum value. ::: ::: Measurements were made for both excitatory and inhibitory neurons in the cortex. These neurons are known to form a monosynaptic negative feedback loop. Both classes of cells can be described by the same parameters. ::: ::: The sigmoid curve is asymmetric in that the region of maximal slope is displaced toward the excitatory side. The data are compatible with Freeman's model of prepyriform burst generation. Other analogies with existing neural nets are being discussed, and the implications for signal processing are reviewed. In particular the relationship of sigmoid slope to efficiency of neural computation is examined.
---
paper_title: The sigmoid nonlinearity in neural computation: An experimental approach

paper_content:

A sigmoid function, relating wave amplitude (EEG) to pulse density, is derived experimentally in the rat olfactory bulb. The bulb is the first central structure which is related to odor processing. The curve is asymmetric in that the region of maximal slope is displaced toward the excitatory side. The slope and the maximum of the curve vary with the state of arousal of the animal. This is in agreement with earlier experiments by Freeman in cats and rabbits. The data are explained in terms of his mode of the olfactory system. The relationship of sigmoid slope to efficiency of neural computation is examined by comparison to known analysis of neural networks.
---
paper_title: Directed drift: A new linear threshold algorithm for learning binary weights on-line

paper_content:

Abstract Learning real weights for a McCulloch-Pitts neuron is equivalent to linear programming and can hence be done in polynomial time. Efficient local learning algorithms such as Perceptron Learning further guarantee convergence in finite time. The problem becomes considerably harder, however, when it is sought to learn binary weights; this is equivalent to integer programming which is known to be NP-complete. A family of probabilistic algorithms which learn binary weights for a McCulloch-Pitts neuron with inputs constrained to be binary is proposed here, the target functions being majority functions of a set literals. These algorithms have low computational demands and are essentially local in character. Rapid (average-case) quadratic rates of convergence for the algorithm are predicted analytically and confirmed through computer simulations when the number of examples is within capacity. It is also shown that, for the functions under consideration, Preceptron Learning converges rapidly (but to an, in general, non-binary solution weight vector).
---
paper_title: Multilayer feedforward networks are universal approximators

paper_content:

Abstract This paper rigorously establishes that standard multilayer feedforward networks with as few as one hidden layer using arbitrary squashing functions are capable of approximating any Borel measurable function from one finite dimensional space to another to any desired degree of accuracy, provided sufficiently many hidden units are available. In this sense, multilayer feedforward networks are a class of universal approximators.
---
paper_title: Universal approximation bounds for superpositions of a sigmoidal function

paper_content:

Approximation properties of a class of artificial neural networks are established. It is shown that feedforward networks with one layer of sigmoidal nonlinearities achieve integrated squared error of order O(1/n), where n is the number of nodes. The approximated function is assumed to have a bound on the first moment of the magnitude distribution of the Fourier transform. The nonlinear parameters associated with the sigmoidal nodes, as well as the parameters of linear combination, are adjusted in the approximation. In contrast, it is shown that for series expansions with n terms, in which only the parameters of linear combination are adjusted, the integrated squared approximation error cannot be made smaller than order 1/n/sup 2/d/ uniformly for functions satisfying the same smoothness assumption, where d is the dimension of the input to the function. For the class of functions examined, the approximation rate and the parsimony of the parameterization of the networks are shown to be advantageous in high-dimensional settings. >
---
paper_title: Approximation by Superpositions of a Sigmoidal Function

paper_content:

The present invention relates to a vehicle rearview mirror remote-control device, mounted in a casing containing a control mechanism including a support member integral with the body of a vehicle and which extends inside the casing through an opening. The support member has a first axis around which is pivotally mounted a cross-piece, on which cross-piece is pivotally mounted the casing carrying the mirror, on a second axis perpendicular to the first, first movement-controlling means being provided between the support member and the cross-piece and second-movement controlling means being provided, in an offset manner with respect to the second axis, between the cross-piece and the casing.
---
paper_title: On the approximate realization of continuous mappings by neural networks

paper_content:

Abstract In this paper, we prove that any continuous mapping can be approximately realized by Rumelhart-Hinton-Williams' multilayer neural networks with at least one hidden layer whose output functions are sigmoid functions. The starting point of the proof for the one hidden layer case is an integral formula recently proposed by Irie-Miyake and from this, the general case (for any number of hidden layers) can be proved by induction. The two hidden layers case is proved also by using the Kolmogorov-Arnold-Sprecher theorem and this proof also gives non-trivial realizations.
---
paper_title: Constructive approximations for neural networks by sigmoidal functions

paper_content:

A constructive algorithm for uniformly approximating real continuous mappings by linear combinations of bounded sigmoidal functions is given. G. Cybenko (1989) has demonstrated the existence of uniform approximations to any continuous f provided that sigma is continuous; the proof is nonconstructive, relying on the Hahn-Branch theorem and the dual characterization of C(I/sup n/). Cybenko's result is extended to include any bounded sigmoidal (even nonmeasurable ones). The approximating functions are explicitly constructed. The number of terms in the linear combination is minimal for first-order terms. >
---
paper_title: Some new results on neural network approximation

paper_content:

We show that standard feedforward networks with as few as a single hidden layer can uniformly approximate continuous functions on compacta provided that the activation function @j is locally Riemann integrable and nonpolynomial, and have universal L^p (@m) approximation capabilities for finite and compactly supported input environment measures @m provided that @j is locally bounded and nonpolynomial. In both cases, the input-to-hidden weights and hidden layer biases can be constrained to arbitrarily small sets; if in addition @j is locally analytic a single universal bias will do.
---
paper_title: Multilayer feedforward networks with a nonpolynomial activation function can approximate any function

paper_content:

Several researchers characterized the activation function under which multilayer feedforward networks can act as universal approximators. We show that most of all the characterizations that were reported thus far in the literature are special cases of the following general result: A standard multilayer feedforward network with a locally bounded piecewise continuous activation function can approximate any continuous function to any degree of accuracy if and only if the network's activation function is not a polynomial. We also emphasize the important role of the threshold, asserting that without it the last theorem does not hold.
---
paper_title: Brains, Machines, and Mathematics

paper_content:

This is a book whose time has come-again. The first edition (published by McGraw-Hill in 1964) was written in 1962, and it celebrated a number of approaches to developing an automata theory that could provide insights into the processing of information in brainlike machines, making it accessible to readers with no more than a college freshman's knowledge of mathematics. The book introduced many readers to aspects of cybernetics-the study of computation and control in animal and machine. But by the mid-1960s, many workers abandoned the integrated study of brains and machines to pursue artificial intelligence (AI) as an end in itself-the programming of computers to exhibit some aspects of human intelligence, but with the emphasis on achieving some benchmark of performance rather than on capturing the mechanisms by which humans were themselves intelligent. Some workers tried to use concepts from AI to model human cognition using computer programs, but were so dominated by the metaphor "the mind is a computer" that many argued that the mind must share with the computers of the 1960s the property of being serial, of executing a series of operations one at a time. As the 1960s became the 1970s, this trend continued. Meanwhile, experi mental neuroscience saw an exploration of new data on the anatomy and physiology of neural circuitry, but little of this research placed these circuits in the context of overall behavior, and little was informed by theoretical con cepts beyond feedback mechanisms and feature detectors."
---
paper_title: Approximation and Estimation Bounds for Artificial Neural Networks

paper_content:

For a common class of artificial neural networks, the mean integrated squared error between the estimated network and a target function f is shown to be bounded by O \left ( {{C^2_f}\over n}\right ) + O\left ({nd\over N}{\rm log}\ N\right), where n is the number of nodes, d is the input dimension of the function, N is the number of training observations, and Cf is the first absolute moment of the Fourier magnitude distribution of f. The two contributions to this total risk are the approximation error and the estimation error. Approximation error refers to the distance between the target function and the closest neural network function of a given architecture and estimation error refers to the distance between this ideal network function and an estimated network function. With n ˜ Cf(N/(dlog N))1/2 nodes, the order of the bound on the mean integrated squared error is optimized to be O(Cf((d/N)log N)1/2). The bound demonstrates surprisingly favorable properties of network estimation compared to traditional series and nonparametric curve estimation techniques in the case that d is moderately large. Similar bounds are obtained when the number of nodes n is not preselected as a function of Cf (which is generally not known a priori), but rather the number of nodes is optimized from the observed data by the use of a complexity regularization or minimum description length criterion. The analysis involves Fourier techniques for the approximation error, metric entropy considerations for the estimation error, and a calculation of the index of resolvability of minimum complexity estimation of the family of networks.
---
paper_title: A Constructive Proof and An Extension of Cybenko's Approximation Theorem

paper_content:

In this paper, we present a constructive proof of approximation by superposition of sigmoidal functions. We point out a sufficient condition that the set of finite linear combinations of the form \(\sum \alpha _j\sigma (y_jx+\theta _j)\) is dense in \(C(\mathbb{I}^n)\), is the boundedness of the sigmoidal function σ(x). Moreover, we show that if the set of finite linear combinations of the form \(\sum c_j\omega (\xi _j+\eta _j)\), where ω is a univariate function, is dense in \(L^p[a,b] (1\leq p< \infty )\) (or C[a,b]) for any finite a,b, then the set of finite linear combinations of the form \(\sum c_j\omega (y_j.x+\theta _j)\) is dense in \(L^p(\mathbb{I}^n)(or C(\mathbb{I}^n))\). An extension in another direction is also presented in Theorem 4 of this paper.
---
paper_title: Probability Inequalities for Empirical Processes and a Law of the Iterated Logarithm

paper_content:

Given a class -F of functions on X, we can view Vn as a stochastic process indexed by -F and consider limit theorems for this process. To prove such theorems it is often helpful to have bounds on the tail of the r.v. sup _W I n(f ) I (see for example Dudley, 1978, Kuelbs and Dudley, 1980, Dudley and Phillip, 1983, or Gine and Zinn, 1983.) Our main question of interest is, for what classes -F can "best possible" bounds be obtained? So first we must ask, what are these best possible bounds? Of course
---
paper_title: Some special vapnik-chervonenkis classes

paper_content:

For a class C of subsets of a set X, let V(C) be the smallest n such that no n-element set F@?X has all its subsets of the form A @? F, A @? C. The condition V(C) <+~ has probabilistic implications. If any two-element subset A of X satisfies both A @? C = O and A @? D for some C, D@?C, then V(C)=2 if and only if C is linearly ordered by inclusion. If C is of the form C={@?^n"i"="1 C"i:C"i@?C"i, i=1,2,...,n}, where each C"i is linearly ordered by inclusion, then V(C)=0} for f in H, then V(C)=n.
---
paper_title: On the Infeasibility of Training Neural Networks with Small Squared Errors

paper_content:

We demonstrate that the problem of training neural networks with small (average) squared error is computationally intractable. Consider a data set of M points (Xi, Yi), i = 1,2, ..., M, where Xi are input vectors from Rd, Yi are real outputs (Yi ∈ R). For a network f0 in some class F of neural networks, (1/M) Σi=1M (f0(Xi)- Yi)2)1/2 - inff∈F(1/M) Σi=1M (f(Xi) - Yi)2)1/2 is the (avarage) relative error occurs when one tries to fit the data set by f0. We will prove for several classes F of neural networks that achieving a relative error smaller than some fixed positive threshold (independent from the size of the data set) is NP-hard.
---
paper_title: A new polynomial-time algorithm for linear programming

paper_content:

We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O ( n 3-5 L 2 ), as compared to O ( n 6 L 2 ) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a e P , there is a projective transformation of the space that maps P , a to P' , a' having the following property. The ratio of the radius of the smallest sphere with center a' , containing P' to the radius of the largest sphere with center a' contained in P' is O ( n ). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time.
---
paper_title: What Size Net Gives Valid Generalization?

paper_content:

We address the question of when a network can be expected to generalize from m random training examples chosen from some arbitrary probability distribution, assuming that future test examples are drawn from the same distribution. Among our results are the following bounds on appropriate sample vs. network size. Assume 0 < e ≤ 1/8. We show that if m ≥ O(W/e log N/e) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 - e/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 1 - e of future test examples drawn from the same distribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than Ω(W/e) random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 - e fraction of the future test examples.
---
paper_title: Almost Linear VC-Dimension Bounds for Piecewise Polynomial Networks

paper_content:

We compute upper and lower bounds on the VC dimension and pseudo-dimension of feedforward neural networks composed of piecewise polynomial activation functions. We show that if the number of layers is fixed, then the VC dimension and pseudo-dimension grow as WlogW, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC dimension and pseudo-dimension grow as W2. We combine our results with recently established approximation error rates and determine error bounds for the problem of regression estimation by piecewise polynomial networks with unbounded weights.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Complexity Results on Learning by Neural Nets

paper_content:

We consider the computational complexity of learning by neural nets. We are interested in how hard it is to design appropriate neural net architectures and to train neural nets for general and specialized learning tasks. Our main result shows that the training problem for 2-cascade neural nets (which have only two non-input nodes, one of which is hidden) is {\mathscr NP}-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also {\mathscr NP}-complete. This result also demonstrates a surprising gap between the computational complexities of one-node (perceptron) and two-node neural net training problems, since the perceptron training problem can be solved in polynomial time by linear programming techniques. We conjecture that training a k-cascade neural net, which is a classical threshold network training problem, is also {\mathscr NP}-complete, for each fixed k ≥ 2. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is {\mathscr NP}-hard. ::: ::: Our neural net learning model encapsulates the idea of modular neural nets, which is a popular approach to overcoming the scaling problem in training neural nets. We investigate how much easier the training problem becomes if the class of concepts to be learned is known a priori and the net architecture is allowed to be sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.
---
paper_title: Strong Minimax Lower Bounds for Learning

paper_content:

Minimax lower bounds for concept learning state, for example, that for each sample size n and learning rule gn , there exists a distribution of the observation X and a concept C to be learnt such that the expected error of gn is at least a constant times V/n, where V is the vc dimension of the concept class. However, these bounds do not tell anything about the rate of decrease of the error for a fixed distribution-concept pair.In this paper we investigate minimax lower bounds in such a (stronger) sense. We show that for several natural k-parameter concept classes, including the class of linear halfspaces, the class of balls, the class of polyhedra with a certain number of faces, and a class of neural networks, for any sequence of learning rules {gn}, there exists a fixed distribution of X and a fixed conceptC such that the expected error is larger than a constant timesk/n for infinitely manyn. We also obtain such strong minimax lower bounds for the tail distribution of the probability of error, which extend the corresponding minimax lower bounds.
---
paper_title: A CLASS OF ITERATIVE PROCEDURES FOR LINEAR INEQUALITIES.

paper_content:

Abstract : A class of exponentially convergent and finite procedures for determining alpha such that A alpha > O is presented. (Author)
---
paper_title: Neural networks and physical systems with emergent collective computational abilities

paper_content:

Abstract ::: Computational properties of use of biological organisms or to the construction of computers can emerge as collective properties of systems having a large number of simple equivalent components (or neurons). The physical meaning of content-addressable memory is described by an appropriate phase space flow of the state of a system. A model of such a system is given, based on aspects of neurobiology but readily adapted to integrated circuits. The collective properties of this model produce a content-addressable memory which correctly yields an entire memory from any subpart of sufficient size. The algorithm for the time evolution of the state of the system is based on asynchronous parallel processing. Additional emergent collective properties include some capacity for generalization, familiarity recognition, categorization, error correction, and time sequence retention. The collective properties are only weakly sensitive to details of the modeling or the failure of individual devices.
---
paper_title: Feedforward nets for interpolation and classification

paper_content:

Abstract This paper deals with single-hidden-layer feedforward nets, studying various aspects of classification power and interpolation capability. In particular, a worst-case analysis shows that direct input to output connections in threshold nets double the recognition but not the interpolation power, while using sigmoids rather than thresholds allows doubling both. For other measures of classification, including the Vapnik-Chervonenkis dimension, the effect of direct connections or sigmoidal activations is studied in the special case of two-dimensional inputs.
---
paper_title: Programmed interactions in higher-order neural networks: Maximal capacity

paper_content:

Abstract The focus of the paper is the estimation of the maximum number of states that can be made stable in higher-order extensions of neural network models. Each higher-order neuron in a network of n elements is modeled as a polynomial threshold element of degree d . It is shown that regardless of the manner of operation, or the algorithm used, the storage capacity of the higher-order network is of the order of one bit per interaction weight. In particular, the maximal (algorithm independent) storage capacity realizable in a recurrent network of n higher-order neurons of degree d is of the order of n d d! . A generalization of a spectral algorithm for information storage is introduced and arguments adducing near optimal capacity for the algorithm are presented.
---
paper_title: Computation and learning in the context of neural network capacity

paper_content:

Publisher Summary This chapter focuses on a simple mathematical model for a neural element and computational structures comprised of interconnected networks of these formal elements. The key elements of the neural model are a linear accumulation of information; a non-linear decision rule that operates on the comparison between the accumulated information and a threshold; and a discrete time scale of operation. There are two types of neurons, namely, a linear neuron and a sigmoid neuron. The sigmoid neurons have nonlinear characteristics. Linear neurons with their linear characteristic are limited in their computational capability. The chapter describes a neural network. The neural network is a collection of neurons interconnected by having the output of each neuron function as input to any sub-collection of neurons. A set of neural inputs and outputs are identified as the network inputs and network outputs, respectively. The network state is the collection of individual neural states. The network operation is synchronous if all the neurons operate on the same time scale and asynchronous if the neurons operate on different time scales.
---
paper_title: On Properties of Networks of Neuron-Like Elements

paper_content:

The complexity and computational capacity of multi-layered, feedforward neural networks is examined. Neural networks for special purpose (structured) functions are examined from the perspective of circuit complexity. Known results in complexity theory are applied to the special instance of neural network circuits, and in particular, classes of functions that can be implemented in shallow circuits characterised. Some conclusions are also drawn about learning complexity, and some open problems raised. The dual problem of determining the computational capacity of a class of multi-layered networks with dynamics regulated by an algebraic Hamiltonian is considered. Formal results are presented on the storage capacities of programmed higher-order structures, and a tradeoff between ease of programming and capacity is shown. A precise determination is made of the static fixed point structure of random higher-order constructs, and phase-transitions (0-1 laws) are shown.
---
paper_title: Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

paper_content:

It is shown that high-order feedforward neural nets of constant depth with piecewise-polynomial activation functions and arbitrary real weights can be simulated for Boolean inputs and outputs by neural nets of a somewhat larger size and depth with Heaviside gates and weights from {-1, 0, 1}. This provides the first known upper bound for the computational power of the former type of neural nets. It is also shown that in the case of first-order nets with piecewise-linear activation functions one can replace arbitrary real weights by rational numbers with polynomially many bits without changing the Boolean function that is computed by the neural net. In order to prove these results, we introduce two new methods for reducing nonlinear problems about weights in multilayer neural nets to linear problems for a transformed set of parameters. These transformed parameters can be interpreted as weights in a somewhat larger neural net. ::: As another application of our new proof technique we show that neural nets with piecewise-polynomial activation functions and a constant number of analog inputs are probably approximately correct (PAC) learnable (in Valiant's model for PAC learning [Comm. Assoc. Comput. Mach., 27 (1984), pp. 1134--1142]).
---
paper_title: On the Intractability of Loading Neural Networks

paper_content:

Neural networks have been proposed as a tool for machine learning. In this role, a network is trained to recognize complex associations between inputs and outputs that were presented during a supervised training cycle. These associations are incorporated into the weights of the network, which encode a distributed representation of the information that was contained in the patterns. Once trained, the network will compute an input/output mapping which, if the training data was representative enough, will closely match the unknown rule which produced the original data. Massive parallelism of computation, as well as noise and fault tolerance, are often offered as justifications for the use of neural nets as learning paradigms.
---
paper_title: Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks

paper_content:

We introduce a new method for proving explicit upper bounds on the VC dimension of general functional basis networks and prove as an application, for the first time, that the VC dimension of analog neural networks with the sigmoidal activation function?(y)=1/1+e?yis bounded by a quadratic polynomialO((lm)2) in both the numberlof programmable parameters, and the numbermof nodes. The proof method of this paper generalizes to much wider class of Pfaffian activation functions and formulas and gives also for the first time polynomial bounds on their VC dimension. We present also some other applications of our method.
---
paper_title: Brains, Machines, and Mathematics

paper_content:

This is a book whose time has come-again. The first edition (published by McGraw-Hill in 1964) was written in 1962, and it celebrated a number of approaches to developing an automata theory that could provide insights into the processing of information in brainlike machines, making it accessible to readers with no more than a college freshman's knowledge of mathematics. The book introduced many readers to aspects of cybernetics-the study of computation and control in animal and machine. But by the mid-1960s, many workers abandoned the integrated study of brains and machines to pursue artificial intelligence (AI) as an end in itself-the programming of computers to exhibit some aspects of human intelligence, but with the emphasis on achieving some benchmark of performance rather than on capturing the mechanisms by which humans were themselves intelligent. Some workers tried to use concepts from AI to model human cognition using computer programs, but were so dominated by the metaphor "the mind is a computer" that many argued that the mind must share with the computers of the 1960s the property of being serial, of executing a series of operations one at a time. As the 1960s became the 1970s, this trend continued. Meanwhile, experi mental neuroscience saw an exploration of new data on the anatomy and physiology of neural circuitry, but little of this research placed these circuits in the context of overall behavior, and little was informed by theoretical con cepts beyond feedback mechanisms and feature detectors."
---
paper_title: Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers

paper_content:

The Vapnik-Chervonenkis (V-C) dimension is an important combinatorial tool in the analysis of learning problems in the PAC framework. For polynomial learnability, we seek upper bounds on the V-C dimension that are polynomial in the syntactic complexity of concepts. Such upper bounds are automatic for discrete concept classes, but hitherto little has been known about what general conditions guarantee polynomial bounds on V-C dimension for classes in which concepts and examples are represented by tuples of real numbers. In this paper, we show that for two general kinds of concept class the V-C dimension is polynomially bounded in the number of real numbers used to define a problem instance. One is classes where the criterion for membership of an instance in a concept can be expressed as a formula (in the first-order theory of the reals) with fixed quantification depth and exponentially-bounded length, whose atomic predicates are polynomial inequalities of exponentially-bounded degree. The other is classes where containment of an instance in a concept is testable in polynomial time, assuming we may compute standard arithmetic operations on reals exactly in constant time.Our results show that in the continuous case, as in the discrete, the real barrier to efficient learning in the Occam sense is complexity-theoretic and not information-theoretic. We present examples to show how these results apply to concept classes defined by geometrical figures and neural nets, and derive polynomial bounds on the V-C dimension for these classes.
---
paper_title: Linear Programming and Extensions

paper_content:

In real-world problems related to finance, business, and management, mathematicians and economists frequently encounter optimization problems. In this classic book, George Dantzig looks at a wealth of examples and develops linear programming methods for their solutions. He begins by introducing the basic theory of linear inequalities and describes the powerful simplex method used to solve them. Treatments of the price concept, the transportation problem, and matrix methods are also given, and key mathematical concepts such as the properties of convex sets and linear vector spaces are covered."The author of this book was the main force in establishing a new mathematical discipline, and he has contributed to its further development at every stage and from every angle. This volume ... is a treasure trove for those who work in this field--teachers, students, and users alike. Its encyclopaedic coverage, due in part to collaboration with other experts, makes it an absolute must."--S. Vajda, Zentralblatt fYr Mathematik und ihre Grenzgebiete
---
paper_title: An Automated Approach to the Design of Decision Tree Classifiers

paper_content:

The classification of large dimensional data sets arising from the merging of remote sensing data with more traditional forms of ancillary data causes a significant computational problem. Decision tree classification is a popular approach to the problem. This type of classifier is characterized by the property that samples are subjected to a sequence of decision rules before they are assigned to a unique class. If a decision tree classifier is well designed, the result in many cases is a classification scheme which is accurate, flexible, and computationally efficient. This correspondence provides an automated technique for effective decision tree design which relies only on a priori statistics. This procedure utilizes canonical transforms and Bayes table look-up decision rules. An optimal design at each node is derived based on the associated decision table. A procedure for computing the global probability of correct classification is also provided. An example is given in which class statistics obtained from an actual Landsat scene are used as input to the program. The resulting decision tree design has an associated probability of correct classification of 0.75 compared to the theoretically optimum 0.79 probability of correct classification associated with a full dimensional Bayes classifier. Recommendations for future research are included.
---
paper_title: Introduction to Neural Computing

paper_content:

Introduction - Why neural nets? Principles and promises. The McCulloch and Pitts legacy. The hard learning problem. Making neurons. The secrets of Wisard. Multi-layer perceptrons. Dynamic networks. Variations. Neurocontrol. Varieties of pattern analysis. Developments in weightless systems. Trends and promises.
---
paper_title: Neural net algorithms that learn in polynomial time from examples and queries

paper_content:

An algorithm which trains networks using examples and queries is proposed. In a query, the algorithm supplies a y and is told t(y) by an oracle. Queries appear to be available in practice for most problems of interest, e.g. by appeal to a human expert. The author's algorithm is proved to PAC learn in polynomial time the class of target functions defined by layered, depth two, threshold nets having n inputs connected to k hidden threshold units connected to one or more output units, provided k >
---
paper_title: The Sample Complexity of Pattern Classification With Neural Networks: The Size of the Weights is More Important Than the Size of the Network

paper_content:

Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A/sup 3/ /spl radic/((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.
---
paper_title: Universal approximation bounds for superpositions of a sigmoidal function

paper_content:

Approximation properties of a class of artificial neural networks are established. It is shown that feedforward networks with one layer of sigmoidal nonlinearities achieve integrated squared error of order O(1/n), where n is the number of nodes. The approximated function is assumed to have a bound on the first moment of the magnitude distribution of the Fourier transform. The nonlinear parameters associated with the sigmoidal nodes, as well as the parameters of linear combination, are adjusted in the approximation. In contrast, it is shown that for series expansions with n terms, in which only the parameters of linear combination are adjusted, the integrated squared approximation error cannot be made smaller than order 1/n/sup 2/d/ uniformly for functions satisfying the same smoothness assumption, where d is the dimension of the input to the function. For the class of functions examined, the approximation rate and the parsimony of the parameterization of the networks are shown to be advantageous in high-dimensional settings. >
---
paper_title: Connectionist nonparametric regression: multilayer feedforward networks can learn arbitrary mappings

paper_content:

Abstract It has been recently shown (e.g., Hornik, Stinchcombe & White, 1989, 1990) that sufficiently complex multilayer feedforward networks are capable of representing arbitrarily accurate approximations to arbitrary mappings. We show here that these approximations are learnable by proving the consistency of a class of connectionist nonparametric regression estimators for arbitrary (square integrable) regression functions. The consistency property ensures that as network “experience” accumulates (as indexed by the size of the training set), the probability of network approximation error exceeding any specified level tends to zero. A key feature of the demonstration of consistency is the proper control of the growth of network complexity as a function of network experience. We give specific growth rates for network complexity compatible with consistency. We also consider automatic and semi-automatic data-driven methods for determining network complexity in applications, based on minimization of a cross-validated average squared error measure of network performance. We recommend cross-validated average squared error as a generally applicable criterion for comparing relative performance of differing network architectures and configurations.
---
paper_title: Consistency of multilayer perceptron regression estimators

paper_content:

In the paper three layer perceptron with one hidden layer and the output layer consisting of one neuron is considered. This is commonly used architecture to solve regression problems where such a perceptron minimizing the mean squared error criterion for the data points (x"k, y"k), k = 1,..., N is sought. It is shown that in the model: y"k = g"0(x"k) + @ek, k = 1, ... N, where x"k is independent from zero mean error term @e"k, this procedure is consistent when N -> ~, provided that g"0 is represented as three layer perceptron with Heaviside transfer fucntion. The same result is true when transfer function is an arbitrary continuous function with bounded limits at +/-~ and the hidden-to-output weights in the considered family of perceptions are bounded.
---
paper_title: Approximation and Estimation Bounds for Artificial Neural Networks

paper_content:

For a common class of artificial neural networks, the mean integrated squared error between the estimated network and a target function f is shown to be bounded by O \left ( {{C^2_f}\over n}\right ) + O\left ({nd\over N}{\rm log}\ N\right), where n is the number of nodes, d is the input dimension of the function, N is the number of training observations, and Cf is the first absolute moment of the Fourier magnitude distribution of f. The two contributions to this total risk are the approximation error and the estimation error. Approximation error refers to the distance between the target function and the closest neural network function of a given architecture and estimation error refers to the distance between this ideal network function and an estimated network function. With n ˜ Cf(N/(dlog N))1/2 nodes, the order of the bound on the mean integrated squared error is optimized to be O(Cf((d/N)log N)1/2). The bound demonstrates surprisingly favorable properties of network estimation compared to traditional series and nonparametric curve estimation techniques in the case that d is moderately large. Similar bounds are obtained when the number of nodes n is not preselected as a function of Cf (which is generally not known a priori), but rather the number of nodes is optimized from the observed data by the use of a complexity regularization or minimum description length criterion. The analysis involves Fourier techniques for the approximation error, metric entropy considerations for the estimation error, and a calculation of the index of resolvability of minimum complexity estimation of the family of networks.
---
paper_title: Optimal stopping and effective machine complexity in learning

paper_content:

We study the problem of when to stop learning a class of feedforward networks - networks with linear outputs neuron and fixed input weights - when they are trained with a gradient descent algorithm on a finite number of examples. Under general regularity conditions, it is shown that there are in general three distinct phases in the generalization performance in the learning process, and in particular, the network has better generalization performance when learning is stopped at a certain time before the global minimum of the empirical error is reacherd. A notion of effective size of a machine is defined and used to explain the trade-off between the complexity of the machine and the training error in the learning process. The study leads naturally to a network size selection criterion, which turns out to be a generalization of Akaike's Information Criterion for the learning process. It is shown that stopping learning before the global minimum of the empirical error has the effect of network size selection.
---
paper_title: Decision theoretic generalizations of the PAC model for neural net and other learning applications

paper_content:

We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x in X and an outcome y in Y , and tries to find a hypothesis h : X --< A , where h in H , that specifies the appropriate action a in A to take for each instance x , in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X times Y . Special cases include the problem of learning a function from X into Y , the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation). We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H , and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Pollard''s work, and a notion of *capacity* and *metric dimension* for classes of functions that map into a bounded metric space. (Supersedes 89-30 and 90-52.) [Also in "Information and Computation", Vol. 100, No.1, September 1992]
---
paper_title: The Sample Complexity of Pattern Classification With Neural Networks: The Size of the Weights is More Important Than the Size of the Network

paper_content:

Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A/sup 3/ /spl radic/((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.
---
paper_title: Boosting Decision Trees

paper_content:

We introduce a constructive, incremental learning system for regression problems that models data by means of locally linear experts. In contrast to other approaches, the experts are trained independently and do not compete for data during learning. Only when a prediction for a query is required do the experts cooperate by blending their individual predictions. Each expert is trained by minimizing a penalized local cross validation error using second order methods. In this way, an expert is able to find a local distance metric by adjusting the size and shape of the receptive field in which its predictions are valid, and also to detect relevant input features by adjusting its bias on the importance of individual input dimensions. We derive asymptotic results for our method. In a variety of simulations the properties of the algorithm are demonstrated with respect to interference, learning speed, prediction accuracy, feature detection, and task oriented incremental learning.
---
paper_title: Structural Risk Minimization Over Data-Dependent Hierarchies

paper_content:

The paper introduces some generalizations of Vapnik's (1982) method of structural risk minimization (SRM). As well as making explicit some of the details on SRM, it provides a result that allows one to trade off errors on the training sample against improved generalization performance. It then considers the more general case when the hierarchy of classes is chosen in response to the data. A result is presented on the generalization performance of classifiers with a "large margin". This theoretically explains the impressive generalization performance of the maximal margin hyperplane algorithm of Vapnik and co-workers (which is the basis for their support vector machines). The paper concludes with a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets. Four examples are given of such functions, including the Vapnik-Chervonenkis (1971) dimension measured on the sample.
---
paper_title: Bagging Predictors

paper_content:

Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does a plurality vote when predicting a class. The multiple versions are formed by making bootstrap replicates of the learning set and using these as new learning sets. Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy. The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.
---
paper_title: A training algorithm for optimal margin classifiers

paper_content:

A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented. The technique is applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions. The effective number of parameters is adjusted automatically to match the complexity of the problem. The solution is expressed as a linear combination of supporting patterns. These are the subset of training patterns that are closest to the decision boundary. Bounds on the generalization performance based on the leave-one-out method and the VC-dimension are given. Experimental results on optical character recognition problems demonstrate the good generalization obtained when compared with other learning algorithms.
---
paper_title: Boosting the margin: A new explanation for the effectiveness of voting methods

paper_content:

One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often is observed to decrease even after the training error reaches zero. In this paper, we show that this phenomenon is related to the distribution of margins of the training examples with respect to the generated voting classification rule, where the margin of an example is simply the difference between the number of correct votes and the maximum number of votes received by any incorrect label. We show that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error. We also show theoretically and experimentally that boosting is especially effective at increasing the margins of the training examples. Finally, we compare our explanation to those based on the bias-variance
---
paper_title: Support-vector networks

paper_content:

Thesupport-vector network is a new learning machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed. Special properties of the decision surface ensures high generalization ability of the learning machine. The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data.High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated. We also compare the performance of the support-vector network to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Automatic Pattern Recognition: A Study of the Probability of Error

paper_content:

A test sequence is used to select the best rule from a class of discrimination rules defined in terms of the training sequence. The Vapnik-Chervonenkis and related inequalities are used to obtain distribution-free bounds on the difference between the probability of error of the selected rule and the probability of error of the best rule in the given class. The bounds are used to prove the consistency and asymptotic optimality for several popular classes, including linear discriminators, nearest-neighbor rules, kernel-based rules, histogram rules, binary tree classifiers, and Fourier series classifiers. In particular, the method can be used to choose the smoothing parameter in kernel-based rules, to choose k in the k-nearest neighbor rule, and to choose between parametric and nonparametric rules. >
---
paper_title: Algorithms for Recognizing Contour-Traced Handprinted Characters

paper_content:

A contour-tracing technique originally devised by Clemens and Mason was modified and used with several different classifiers to recognize upper case handprinted characters. Recognition accuracies obtained compare favorably with other published results, particularly when additional simple tests are performed to differentiate commonly confused characters. One suboptimum classifier, in addition to yielding near optimum performance when tested on training data, uses much less statistical information than the optimum Bayes classifier and is significantly better than the optimum classifier when training and test data are limited.
---
paper_title: Bootstrap Techniques for Error Estimation

paper_content:

The design of a pattern recognition system requires careful attention to error estimation. The error rate is the most important descriptor of a classifier's performance. The commonly used estimates of error rate are based on the holdout method, the resubstitution method, and the leave-one-out method. All suffer either from large bias or large variance and their sample distributions are not known. Bootstrapping refers to a class of procedures that resample given data by computer. It permits determining the statistical properties of an estimator when very little is known about the underlying distribution and no additional samples are available. Since its publication in the last decade, the bootstrap technique has been successfully applied to many statistical estimations and inference problems. However, it has not been exploited in the design of pattern recognition systems. We report results on the application of several bootstrap techniques in estimating the error rate of 1-NN and quadratic classifiers. Our experiments show that, in most cases, the confidence interval of a bootstrap estimator of classification error is smaller than that of the leave-one-out estimator. The error of 1-NN, quadratic, and Fisher classifiers are estimated for several real data sets.
---
paper_title: A Probabilistic Theory of Pattern Recognition

paper_content:

Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index
---
paper_title: Cross‐Validatory Choice and Assessment of Statistical Predictions

paper_content:

SUMMARY A generalized form of the cross-validation criterion is applied to the choice and assessment of prediction using the data-analytic concept of a prescription. The examples used to illustrate the application are drawn from the problem areas of univariate estimation, linear regression and analysis of variance.
---
paper_title: Topics in Statistical Pattern Recognition

paper_content:

Pattern recognition, from the broadest viewpoint, is the study of how one puts abstract objects or patterns into categories in a simple reliable way. We have chosen three areas to review: Nonparametric Discrimination, Finite Memory Learning, and Pattern Complexity. We feel that these statistical areas will ultimately play a role in any global pattern recognition theory which evolves.
---
paper_title: Bibliography on estimation of misclassification

paper_content:

Articles, books, and technical reports on the theoretical and experimental estimation of probability of misclassification are listed for the case of correctly labeled or preclassified training data. By way of introduction, the problem of estimating the probability of misclassification is discussed in order to characterize the contributions of the literature.
---
paper_title: Automatic Pattern Recognition: A Study of the Probability of Error

paper_content:

A test sequence is used to select the best rule from a class of discrimination rules defined in terms of the training sequence. The Vapnik-Chervonenkis and related inequalities are used to obtain distribution-free bounds on the difference between the probability of error of the selected rule and the probability of error of the best rule in the given class. The bounds are used to prove the consistency and asymptotic optimality for several popular classes, including linear discriminators, nearest-neighbor rules, kernel-based rules, histogram rules, binary tree classifiers, and Fourier series classifiers. In particular, the method can be used to choose the smoothing parameter in kernel-based rules, to choose k in the k-nearest neighbor rule, and to choose between parametric and nonparametric rules. >
---
paper_title: Additive estimators for probabilities of correct classification

paper_content:

Abstract Several methods for estimating a sample-based discriminant's probability of correct classification are compared with respect to bias, variance, robustness, and computation cost. “Smooth” modification of the counting estimator, or sample success proportion, is recommended to reduce bias and variance while retaining robustness. Also the “bootstrap” method of Efron (8) can approximately correct an additive estimator's bias using an ancillary computer simulation. In contrast, bias reduction achieved by the popular “leave-one-out” modification of counting method is vitiated by corresponding increase in variance.
---
paper_title: Estimating the Error Rate of a Prediction Rule: Improvement on Cross-Validation

paper_content:

Abstract We construct a prediction rule on the basis of some data, and then wish to estimate the error rate of this rule in classifying future observations. Cross-validation provides a nearly unbiased estimate, using only the original data. Cross-validation turns out to be related closely to the bootstrap estimate of the error rate. This article has two purposes: to understand better the theoretical basis of the prediction problem, and to investigate some related estimators, which seem to offer considerably improved estimation in small samples.
---
paper_title: Nonparametric Bayes error estimation using unclassified samples

paper_content:

The key measure of performance in a pattern recognition problem is the cost of making a decision. For the special case in which the relative cost of a correct decision is zero and the relative cost of an incorrect decision is unity, this cost is equal to the probability of an incorrect decision or error. A pattern recognition system may be viewed as a decision rule which transforms measurements into class assignments. The Bayes error is the minimum achievable error, where the minimization is with respect to all decision rules. The Bayes error is a function of the prior probabilities and the probability density functions of the respective classes. Unfortunately, in many applications, the probability density functions are unknown and therefore the Bayes error is unknown.
---

<format>
Title: Learning Pattern Classification—A Survey

Section 1: INTRODUCTION
Description 1: Explain the goals and background of learning theory, emphasizing the focus on two-class pattern classification problems and their relevance to real-life learning problems.

Section 2: NEAREST NEIGHBOR CLASSIFIERS
Description 2: Discuss the nearest neighbor classifier methodology, its formulation, associated risk, and refinements including consistency and choice of metric.

Section 3: KERNEL CLASSIFIERS
Description 3: Describe kernel classifiers, their formulation, including the moving-window and more general kernel rules, and discuss the significance of kernel function and smoothing factor.

Section 4: HISTOGRAM CLASSIFIERS
Description 4: Explore histogram classifiers, describing how feature spaces are partitioned and the subsequent classification of points. Discuss different partitioning methods including regular histogram rules and classification trees.

Section 5: VAPNIK-CHERVONENKIS THEORY
Description 5: Introduce the Vapnik-Chervonenkis theory, discussing VC dimension and empirical risk minimization, including the combinatorial measures of the richness of classifier sets and structural risk minimization.

Section 6: NEURAL NETWORKS
Description 6: Provide an overview of neural networks, including neuron models, network architectures, their universal classification capabilities, and performance bounds. Discuss specific types of networks like acyclic and recurrent networks and their associated learning algorithms.

Section 7: LARGE-MARGIN CLASSIFIERS
Description 7: Discuss large-margin classifiers, explaining the concept of margin, its importance in estimation, and support vector machines (SVMs). Also, touch on related methods such as boosting, bagging, and arcing.

Section 8: AUTOMATIC PARAMETER SELECTION
Description 8: Elaborate on methods for automatic parameter selection for classifiers, including resubstitution, deleted estimates, and other techniques to estimate error and select parameters based on available data.
</format>
