Natural language processing must sometimes consider the internal structure of words, e.g., in order to understand or generate an unfamiliar word.  Unfamiliar words are systematically related to familiar ones due to linguistic processes such as morphology, phonology, abbreviation, copying error, and historical change. We will show how to build joint probability models over many string-valued random variables.  In general, our models assume that the strings are generated by some random process.  By reconstructing the steps that may have given rise to our observations, we can predict unobserved strings, or predict the relationships among the observed strings.  However, this reconstruction can be computationally hard (indeed undecidable).  We outline approximate algorithms based on Markov chain Monte Carlo, expectation propagation, and dual decomposition.  We give results on some NLP tasks.

Jason Eisner is Professor of Computer Science at Johns Hopkins University, where he is also affiliated with the Center for Language and Speech Processing, the Machine Learning Group, the Cognitive Science Department, and the national Center of Excellence in Human Language Technology. His goal is to develop theprobabilistic modeling, inference, and learning techniques needed for a unified model of all kinds of linguistic structure. His 90+ papers have presented various algorithms for parsing, machine translation, and weighted finite-state machines; formalizations, algorithms, theorems, and empirical results in computational phonology; and unsupervised or semi-supervised learning methods for syntax, morphology, and word-sense disambiguation. He is also the lead designer of Dyna, a new declarative programming language that provides an infrastructure for AI research. He has received two school-wide awards for excellence in teaching.