Recognition of Patterns : Using the Frequencies of Occurrence of Binary Words

This book is a revised updated edition of the second edition which appeared 1974.The work described in this publication was initiated at the General Electric Company's Electronics Laboratory, Syracuse, N.Y., U.S.A. The author would like to take this opportunity to express his gratitude to the Electronics Laboratory for its support and encouragement in this work. Thanks are in particular due to Dr. J.J. Suran for his continued interest and help. It is impossible to acknowledge all the help the au­ thor has received from members of the Laboratory staff. However, the au­ thor is particularly indebted to r·lr. T.C. Robbins for managing the build­ ing of the word recognizer (described in Section 7.4) and for many help­ ful discussions. The work was later continued in Denmark, supported by two grants: no. 1382 in 1966 and no. 1511 in 1967, received from the Danish Govern­ ment Fund for Industrial and Scientific Research. The author is grateful to said Fund, and thereby the Danish taxpayers, who gave the author an opportunity for uninterrupted work with pattern recognitions problems. In August 1967 the author joined the staff of the Electronics Labo­ ratory, Technical University of Denmark, where the subsequent pattern recognition work took place; the author is happy to acknowledge his debt to the members of the staff and to his students for many stimulating and helpful discussions.

1. Problems in the Design of Pattern Recognizers.- 1.1 Introduction.- 1.1.1 About this Book.- 1.1.2 The Two Phases in the Existence of a PR.- 1.2 Three Areas of Application.- 1.2.1 Certain Acts of Identification.- 1.2.2 Decisions Regarding Complex Situations.- 1.2.3 Imitation of Human Pattern Recognition.- 1.3 The Configuration of a PR.- 1.4 Factors which Influence the Design of a PR.- 1.4.1 Factors Associated with the Pattern Classes.- 1.4.2 Estimation of the PR’s Performance.- 1.4.3 Four Major Problem Areas.- 1.5 The Selection of the Attributes.- 1.5.1 Preliminary Processing.- 1.5.2 Generation of Sets of Attributes in Practice.- 1.5.3 An Effective Set of Attributes.- 1.5.3.1 A Definition of “An Effective Set of Attributes”.- 1.5.3.2 A Definition of “The Incremental Effectiveness of an Attribute”.- 1.5.4 One Attribute.- 1.5.5 Templet Matching.- 1.5.6 Selection of a Set of p Attributes.- 1.6 Decision Procedures and Indices of Performance.- 1.6.1 Some Functions Related to the Micro-Regions.- 1.6.2 Bayes’ Procedure.- 1.6.3 The Minimaxing Classification Procedure.- 1.6.4 The Likelihood Method.- 1.6.5 The Neyman-Pearson Method.- 1.6.6 Three Practical Difficulties.- 1.7 Categorizer Design.- 1.7.1 Estimation of a Multivariate Density Function.- 1.7.2 Explicit Partitioning of Pattern Space.- 1.7.2.1 Separation Surfaces of Simple Shape.- 1.7.2.2 The Need for Surfaces of Simple Shape.- 1.7.2.3 Parametric Training Methods.- 1.7.2.4 Non-Parametric Training Methods.- 1.7.3 Implicit Partitioning of the Pattern Space.- 1.7.3.1 Nearest-Neighbor-Pattern Classifier.- 1.7.3.2 Discriminant Functions and Separation Surfaces.- 1.7.3.3 Categorization Using NC Discriminants.- 1.7.3.4 The ?-Machine.- 1.7.3.5 The Nonlinear Generalized Discriminant.- 1.7.3.6 Parametric Training of Discriminants.- 1.7.4 Categorization of Members from More than Two Classes.- 1.8 Hardware Implementation.- 2. Design of a Pattern Recognizer Using the Frequency of Occurrence of Binary Words Method.- 2.1 Introduction.- 2.2 A Step by Step Description of the FOBW Design Procedure.- 2.3 The Ordered Array of Attributes.- 2.4 The Generation of New Sets of NH Attributes.- 2.5 Detection of Effective Attributes.- 3. Computational Rules for Binary Word Frequencies of Occurrence.- 3.1 Binary Word Probabilities, Frequencies of Occurrence and Sequence Length.- 3.2 Redundant Information in N-Gram Frequencies.- 3.2.1 The Problem.- 3.2.2 An Important Relationship.- 3.2.3 Four Digram Frequencies Described by Two Pieces of Information.- 3.2.4 2N N-Gram Frequencies Described by 2N?1 Pieces of Information.- 3.3 Other Sets of 2N?1 Pieces of Information.- 3.4 Bounds on the Binary Word Frequencies of Occurrence.- 3.5 Redundancy in Delayed N-Gram Frequencies.- 3.6 Eight Delayed Trigram Frequencies contain Five Pieces of Information.- 3.7 A Special Relationship between Delayed Digrams and Delayed Trigrams.- 3.8 The Frequencies of Symmetrical and Unsymmetrical Binary Words.- 4. S, A Measure of Separability.- 4.1 Four Statistics.- 4.2 Some Features of the S-Measure.- 4.3 A Conjecture Later Proven by Chernoff.- 5. Modeling of Pattern Generating Stochastic Processes.- 5.1 The Importance of a Model.- 5.2 The Transition Matrix Model.- 5.2.1 A Machine for Random Generation of Binits.- 5.2.2 The N-Gram Frequencies Determine All Other Binary Word Frequencies.- 5.2.3 Testing the Applicability of the Model.- 5.3 The Gaussian Process Model.- 5.3.1 The Examination of the Bivariate Distribution.- 5.3.2 The Gaussian Bivariate Distribution.- 5.3.3 The Relationship between m/?, ?, and the Delayed Digram Frequencies.- 5.3.4 The Case with Zero Mean.- 5.3.5 Estimation of the Normalized Autocorrelation Function.- 5.3.6 The Delayed Digram Frequencies Determine All Other Binary Word Frequencies.- 5.4 Processes Related to the Gaussian Process.- 5.4.1 A Special Type of Transmission Path.- 5.4.2 Additive Gaussian Noise.- 5.4.3 A Carrier Wave Modulated by a Gaussian Process.- 5.5 The ?0 and ?m Concepts.- 6. The Heuristic Search Procedure.- 6.1 The Search Rule.- 6.2 First Example of the FOBW Search Procedure.- 6.2.1 Three Diagram Frequencies and One Trigram Frequency.- 6.2.2 Some Linear Relationships.- 6.2.3 Strongly Correlated and Uncorrelated Attributes.- 6.2.4 The Geometric Argument.- 6.3 A Case Study.- 6.3.1 Some Background Information.- 6.3.2 The First Attribute.- 6.3.3 The Second Attribute.- 6.4 Second Example of the FOBW Search Procedure.- 6.4.1 Two N-Gram Frequencies and One (N+1)-Gram Frequency.- 6.4.2 Correlation between N-Gram Frequencies.- 6.4.3 The Values of the S-Measure.- 6.4.4 A Geometric Construction.- 6.4.5 Realistic Parameter Values.- 6.4.6 A Related Conclusion.- 6.4.7 An (N+l)-Gram Frequency Suggested by Two N-Gram Frequencies.- 7. Hardware Implementation.- 7.1 Two Applications.- 7.2 Simple Hardware.- 7.3 The Sonic Analysis Demonstrator.- 7.3.1 The Jet Engine Sound Simulator.- 7.3.2 The Pattern Recognizer.- 7.3.3 The Hardware Realization.- 7.4 The Word Recognizer.- 7.4.1 On Automated Recognition of Speech.- 8. Summary.- Appendix 1. Some Recent Books.- Appendix 2. The ?-Transformation.