Probabilistic syntactic pattern recognition for traditional and generalized transposition errors

We present experimental results that demonstrate that we can develop a foundational basis for probabilistic syntactic pattern recognition (PR). The patterns are “linearly” represented as strings. In an earlier paper Oommen and Kashyap (1996) had presented a formal basis for designing such systems when the errors involved were arbitrarily distributed substitution, insertion and deletion (SID) syntactic errors. In this paper we show that we can generalize the framework and permit these traditional errors and generalized transposition (GT) errors. We do this by developing a rigorous model, MG*, for channels which permit all these errors in an arbitrarily distributed manner. We also show how we can compute Pr[Y/U] the probability of receiving Y given that U was transmitted, can be computed in quartic time using dynamic programming. Experimental results which involve dictionaries with strings of lengths between 7 and 14 with an overall average noise of 70.5% demonstrate the superiority of our system over existing methods