The Speech Systems Incorporated (SSI) commercial, large-vocabulary, speaker-independent, continuous speech recognition system is described. The system utilizes a novel approach to speech representation: a two-stage encoding of speech, with an intervening compression of acoustic frames (segmentation) between the encoding stages, and a linguistic decoding process suitable for large, variable-duration segments. Binary decision trees trained using the maximum mutual information (MMI) criterion serve as encoders. The features used in encoding are listed, and their ability to discriminate the phonetic content of the speech is analyzed. Recognition results are given for a speaker-independent continuous speech, grammar-constrained radiology reporting product, and for an isolated-word grammar of high perplexity.>

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.

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.

The growing accuracy and sophistication of models in many fields often lead, paradoxically, to limitations upon their use. Computational cost, excessive input data requirements, and difficulty in interpretation of the implications of the model are typical impediments to the broad use of many complex models. Repro-modeling is an approach which, in many cases, overcomes these problems by creating an efficient input/output approximation to the model. Practical methodological approaches to this straightforward concept are proposed, including a practical algorithm for obtaining a continuous multivariate piecewise linear approximation with subregions of general form given a small randomly distributed set of input/output samples. Three examples of the successful application of repro-modeling are outlined: the impact on air quality of a traffic-restriction policy, the design of effective traffic-responsive freeway on-ramp control algorithms, and the radar return from a complex object.

In applications with high-dimensional spaces and relatively few samples, difficulties can arise in the feature selection algorithm proposed by Patrick and Fischer. This correspondence suggests a modification that overcomes these difficulties with little, if any, computational penalty.

This paper discusses a class of methods for pattern classification using a set of samples. They may also be used in reconstructing a probability density from samples. The methods discussed are potential function methods of a type directly derived from concepts related to superposition. The characteristics required of a potential function are examined, and it is shown that smooth potential functions exist that will separate arbitrary sets of sample points. Ideas suggested by Specht in regard to polynomial potential functions are extended.

This paper discusses some aspects of hazards in asynchronous sequential circuits. In particular, methods of hazard detection and correction are given for the analysis of circuits 1) designed by criteria other than hazard prevention, and/or 2) in which upper and lower bounds may be placed on delays. A natural ordering for sequential hazards is introduced as a basis for the procedures.

Abstract—Variable-threshold threshold elements (V-T threshold elements) are threshold elements in which the weights are fixed while the threshold may be varied. When the threshold is varied, a set of functions is generated.

Abstract—A variable-threshold net is a network of variable-threshold threshold elements in which the threshold of all elements is a common variable parameter. Synthesis of such nets to realize a given set of functions not realizable by a single element is discussed. An application to realizing sequential machines is described. The problem of prevention of malfunction due to component drift is formalized and solved.

A step in state minimization requires the selection of a minimal class of compatible sets of internal states which covers the given machine and is closed. Grasselli and Luccio have presented a solution of this problem which has certain drawbacks. This paper presents a simpler and shorter algorithm, guaranteed to yield all solutions, based upon their work and that of Paull and Unger.