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.

Table of Contents:
1. Problems in the Design of Pattern Recognizers.- 1.1 Introduction.- 1.2 Three Areas of Application.- 1.3 The Configuration of a PR.- 1.4 Factors which Influence the Design of a PR.- 1.5 The Selection of the Attributes.- 1.6 Decision Procedures and Indices of Performance.- 1.7 Categorizer Design.- 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.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.3 The Gaussian Process Model.- 5.4 Processes Related to the 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.3 A Case Study.- 6.4 Second Example of the FOBW Search Procedure.- 7. Hardware Implementation.- 7.1 Two Applications.-7.2 Simple Hardware.- 7.3 The Sonic Analysis Demonstrator.- 7.4 The Word Recognizer.- 8. Summary.- Appendix 1. Some Recent Books.- Appendix 2. The ?-Transformation.