This paper presents the dynamic programming approach to the design of optimal pattern recognition systems when the costs of feature measurements describing the pattern samples are of considerable importance. A multistage or sequential pattern classifier which requires, on the average, a substantially smaller number of feature measurements than that required by an equally reliable nonsequential classifier is defined and constructed through the method of recursive optimization. Two methods of reducing the dimensionality in computation are presented for the cases where the observed feature measurements are 1) statistically independent, and 2) Markov dependent. Both models, in general, provide a ready solution to the optimal sequential classification problem. A generalization in the design of optimal classifiers capable of selecting a best sequence of feature measurements is also discussed. Computer simulated experiments in character recognition are shown to illustrate the feasibility of this approach.

The problem of developing an appropriate data base for syntax-directed pattern analysis and recognition is considered. A new data base is introduced by generalizing the notion of concatenation in representing patterns with a relationship matrix. The characteristics of relationship matrix are demonstrated in teh context of formal language theory. It is shown that this data base will allow us to remove many of the present restrictions placed on the types of patterns that can be handled by syntax-directed systems. Problems in pattern analysis (description and generation) as well as in pattern recognition are discussed and examples are given to illustrate the potential application of this data base in both of these areas.

This paper deals with a sequential decision model for selecting feature subsets in pattern recognition. Based upon this model, a number of selection strategies are proposed and their properties are investigated. The basic criterion of these selection strategies, which depend only on the last r (r finite) recognition samples, is to maximize the long-run proportion of correct recognition, the maximization being overall possible feature subsets. The sequential model is particularly suitable for the implementation of on-line selection processes often required in pattern recognition. A character recognition experiment has been simulated on a digital computer to demonstrate the feasibility of this approach.

This paper presents the dynamic programming approach to the design of optimal pattern recognition systems when the costs of feature measurements describing the pattern samples are of considerable importance. A multistage or sequential pattern classifier which requires, on the average, a substantially smaller number of feature measurements than that required by an equally reliable nonsequential classifier is defined and constructed through the method of recursive optimization. Two methods of reducing the dimensionality in computation are presented for the cases where the observed feature measurements are 1) statistically independent, and 2) Markov dependent. Both models, in general, provide a ready solution to the optimal sequential classification problem. A generalization in the design of optimal classifiers capable of selecting a best sequence of feature measurements is also discussed. Computer simulated experiments in character recognition are shown to illustrate the feasibility of this approach.

In a recent paper Watanabe (1965) has established two useful theorems concerning the optimum properties of the Karhunen-Loeve expansion for the random functions of a stochastic process. The resulting coordinate system (Karhunen-Loeve system) was found to be optimum in the sense of i) minimizing the mean-square error committed by approximating the expansion of an infinite series by a finite number of terms, ii) minimizing the entropy function defined over the probability distribution of the coordinate coefficients for the entire ensemble. These optimum features were then effectively applied to the preprocessing of input data for the speech recognition problem. However, in the development of these properties considerations were only given to the situation where the random functions come from the same stochastic process, and consequently the coordinate coefficients in the expansion were treated to be nonrandom. The question then arises as to whether the optimum properties will hold if the random functions are realizations of more than one stochastic process as in the case of many preprocessing problems in pattern recognization and signal detection. The purpose of this correspondence is to show. that the cited optimum properties can be retained by defining a generalized Karhunen-Loeve expansion which considers the possibility of two or more stochastic processes generating the random functions. Necessary conditions are derived to assure the existence of such an expansion. Applications of these results are indicated in the ranking and selection of feature measurements for the sequential recognition (decision) problems.

In the problems of statistical pattern recognition, it has become increasingly known that there are many applications in which parametric assumptions regarding the pattern statistics are not justified. This paper treats a nonparametric design of a sequential recognition machine which uses the optimum property of Wald's sequential probability ratio test (SPRT). For the case of binary classification, a sequential ranking procedure is found useful in a two-sample problem in which we wish to test the hypothesis against the Lehmann alternatives, based on the successively ranked observations. The test procedure is then analyzed in terms of the performance criterion which in this case is the expected number of observations, with specified error probabilities. A generalization procedure of multiple classification is also given as a direct extension. Computer-simulated experiments have illustrated the effectiveness of this test procedure in the recognition of handwritten English characters, where the nonparametric method seems to be necessary and appropriate.

The problem of optimally terminating the sequential recognition procedure at a finite time prespecified by the designer is considered. The application arises, in practice, when the receptor (feature extraction) part of a sequential recognition machine has only a finite number of suitable features available to the categorizer (decision) part, or the cost of taking observation is found too high as the recognition process exceeds a certain time limit. In either case, the urgency to terminate the recognition procedure becomes greater when the available measurements are to be exhausted. The problem is studied by considering time-varying stopping boundaries for the sequential procedure such that by a preassigned length of time, the acceptance and rejection regions meet and, therefore, one of the pattern classes has to be accepted as the terminal decision. The idea of varying the stopping rules as a function of time enables us to investigate the behavior of a modified sequential test as compared to the standard Wald test with constant stopping boundaries. Computer simulation of English character recognition using the modified sequential test procedure indicates very satisfactory results.