In many applications, it is necessary to determine the similarity of two strings. A widely-used notion of string similarity is the edit distance: the minimum number of insertions, deletions, and substitutions required to transform one string into the other. In this report, we provide a stochastic model for string-edit distance. Our stochastic model allows us to learn a string-edit distance function from a corpus of examples. We illustrate the utility of our approach by applying it to the difficult problem of learning the pronunciation of words in conversational speech. In this application, we learn a string-edit distance with nearly one-fifth the error rate of the untrained Levenshtein distance. Our approach is applicable to any string classification problem that may be solved using a similarity function against a database of labeled prototypes.

We describe a simple variant of the interpolated Markov model with non-emitting state transitions and prove that it is strictly more powerful than any Markov model. Empirical results demonstrate that the non-emitting model outperforms the interpolated model on the Brown corpus and on the Wall Street Journal under a wide range of experimental conditions. The non-emitting model is also much less prone to overtraining.

Proposes a new way to model conditional independence in Markov models. The central feature of our nonuniform Markov model is that it makes predictions of varying lengths using contexts of varying lengths. Experiments on the Wall Street Journal reveal that the nonuniform model performs slightly better than the classic interpolated Markov model of Jelinek and Mercer (1980). This result is somewhat remarkable because both models contain identical numbers of parameters whose values are estimated in a similar manner. The only difference between the two models is how they combine the statistics of longer and shorter strings.

We introduce three new techniques for statistical language models: extension modeling, nonmonotonic contexts, and the divergence heuristic. Together these techniques result in language models that have few states, even fewer parameters, and low message entropies.

Current approaches to speech and handwriting recognition demand a strong language model with a small number of states and an even smaller number of parameters. We introduce four new techniques for statistical language models: multicontextual modeling, nonmonotonic contexts, implicit context growth, and the divergence heuristic. Together these techniques result in language models that have few states, even fewer parameters, and low message entropies. For example, our techniques achieve a message entropy of 2.16 bits/char on the Brown corpus using only 19374 contexts and 54621 parameters. Multicontextual modeling and nonmonotonic contexts, are generalizations of the traditional context model. Implicit context growth ensures that the state transition probabilities of a variable-length Markov process are estimated accurately. This technique is generally applicable to any variable-length Markov process whose state transition probabilities are estimated from string frequencies. In our case, each state in the Markov process represents a context, and implicit context growth conditions the shorter contexts on the fact that the longer contexts did not occur. In a traditional unicontext model, this technique reduces the message entropy of typical English text by 0.1 bits/char. The divergence heuristic, is a heuristic estimation algorithm based on Rissanen's (1978, 1983) minimum description length (MDL) principle and universal data compression algorithm.

We analyze the computational complexity of phonological models as they have developed over the past twenty years. The major results are that generation and recognition are undecidable for segmental models, and that recognition is NP-hard for that portion of segmental phonology subsumed by modern autosegmental models. Formal restrictions are evaluated.

In this paper, I revise generalized phrase structure grammar (GPSG) linguistic theory so that it is more tractable and linguistically constrained. Revised GPSG is also easier to understand, use, and implement. I provide an account of topicalization, explicative pronouns, and parasitic gaps in the revised system and conclude with suggestions for efficient parser design.

An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance, generalized phrase structure grammar (GPSG) appears to be a blessing on two counts. First, the precise formalisms of GPSG might be a direct and transparent guide for parser design and implementation. Second, since GPSG has weak context-free generative power and context-free languages can be parsed in O(n3) by a wide range of algorithms, GPSG parsers would appear to run in polynomial time. This widely-assumed GPSG "efficient parsability" result is misleading: here we prove that the universal recognition problem for current GPSG theory is exponential-polynomial time hard, and assuredly intractable. The paper pinpoints sources of complexity (e.g. metarules and the theory of syntactic features) in the current GPSG theory and concludes with some linguistically and computationally motivated restrictions on GPSG.

This paper is a formal analysis of whether generalized phrase structure grammar's (GPSG) weak context-free generative power will allow it to achieve three of its central goals: (1) to characterize all and only the natural language grammars, (2) to algorithmically determine membership and generative power consequences of GPSG's and (3) to embody the universalism of natural language entirely in the formal system. I prove that "=E*?" is undecidable for GPSGs and, on the basis of this result and the unnaturalness of E*, I argue that GPSG's three goals and its weak context-free generative power conflict with each other: there is no algorithmic way of knowing whether any given GPSG generates a natural language or an unnatural one. The paper concludes with a diagnosis of the result and suggests that the problem might be met by abandoning the weak context-free framework and assuming substantive constraints.