Bj. Oommen et Rl. Kashyap, A FORMAL THEORY FOR OPTIMAL AND INFORMATION-THEORETIC SYNTACTIC PATTERN-RECOGNITION, Pattern recognition, 31(8), 1998, pp. 1159-1177
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.