Embedded stochastic syntactic processes: A class of stochastic grammars equivalent by embedding to a Markov process

This article addresses the problem of suitably defining statistical models of languages derived from context-free grammars (CFGs), where the observed strings may be corrupted by noise or other mechanisms. This article uses the concept of a stochastic syntactic process (SSP), which we have introduced in previous work. An SSP is a stochastic process taking values in the set of all parse trees of a CFG. Inference problems such as estimating a parse tree for "noisy" processes are of obvious significance, particularly in the motivating example of metalevel target tracking. This article demonstrates that by careful application of the theory of probability, an SSP can be embedded into a Markov random field (MRF), thus opening up the possibility of the application of advanced machine learning algorithms based on graphical models to inference problems involving sophisticated target behavior at the "meta" level. This article provides a simple example of how a simple CFG can be embedded in an MRF. Extensions to context-sensitive grammars are discussed.