We consider the problem of recognizing ordered labeled trees by processing their noisy subsequence-trees which are "patched-up" noisy portions of their fragments. We assume that H, a finite dictionary of ordered labeled trees, is given. X* is an unknown element of H, and U is any arbitrary subsequence-tree of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. The solution which we present is, to our knowledge, the first reported solution to the problem. We solve the problem by sequentially comparing Y with every element X of H, the basis of comparison being a new dissimilarity measure between two trees, which implicitly captures the properties of the corrupting mechanism that noisily garbles U into Y. The algorithm which incorporates this constraint has been used to test our pattern recognition system, and the experimental results obtained demonstrate good accuracy.

We consider a fundamental inference problem in syntactic pattern recognition (PR). We assume that the system has a dictionary which is a collection of all the ideal representations of the objects in question. To recognize a noisy sample, the system compares it with every element in the dictionary based on a nearest-neighbor philosophy, using three standard edit operations: substitution, insertion, and deletion, and the associated primitive elementary edit distances d(.,.). In this paper, we consider the assignment of the inter-symbol distances using the parametric distances. We show how the classifier can be trained to get the optimal parametric distance using vector quantization in the meta-space. In all our experiments, the training was typically achieved in a very few iterations. The subsequent classification accuracy we obtained using this single-parameter scheme was 96.13%. The power of the scheme is evident if we compare it to 96.67%, which is the accuracy of the scheme which uses the complete array of inter-symbol distances derived from a knowledge of all the confusion probabilities.

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.