A FORMAL THEORY FOR OPTIMAL AND INFORMATION-THEORETIC SYNTACTIC PATTERN-RECOGNITION

In this paper we present a foundational basis for optimal and informat ion theoretic syntactic pattern recognition. We do this by developing a rigorous model, m, for channels which permit arbitrarily distribute d substitution, deletion and insertion syntactic errors. More explicit ly, if A is any finite alphabet and A the set of words over A, we spe cify a stochastically consistent scheme by which a string U is an elem ent of A can be transformed into any Y is an element of A* by means o f arbitrarily distributed substitution, deletion and insertion operati ons. The scheme is shown to be functionally complete and stochasticall y consistent. Apart from the synthesis aspects, we also deal with the analysis of such a model and derive a technique by which Pr[Y\U], the probability of receiving Y given that U was transmitted, can be comput ed in cubic time using dynamic programming. One of the salient feature s of this scheme is that it demonstrates how dynamic programming can b e applied to evaluate quantities involving complex combinatorial expre ssions and which also maintain rigid probability consistency constrain ts. Experimental results which involve dictionaries with strings of le ngths between 7 and 14 with an overall average noise of 39.75% demonst rate the superiority of our system over existing methods. Apart from i ts straightforward applications in string generation and recognition, we believe that the model also has extensive potential applications in speech, uni-dimensional signal processing, and computational molecula r biology. (C) 1998 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.