Entropy for Hidden Markov Processes and Markov Random Fields

点击翻译按钮获取中文摘要

Stationary Markov processes are ubiquitous as tractable models of random phenomena. The simplest setting is that of finite-state, discrete-time stationary Markov chains, which model one-dimensional random sequences. These processes are fairly well understood. In this project, we focus on two generalizations of this simple setting: 1) stationary hidden Markov processes (HMP) and 2) stationary Markov random fields (MRF). The former models sequences generated by a Markov chain and observed in the presence of noise. The latter models random arrays in higher dimensions, either on a square or cubic lattice or some other kind of graph structure. Both are indispensable for modeling random phenomena in applications ranging from speech recognition to network communications. For both classes, we focus on the finite-state, discrete-time and stationary cases. One of the the most fundamental properties of a stationary process is its entropy, sometimes called entropy rate. Computation of entropy is an important first step in the design of codes for data compression or error correction. While there is a simple, closed-form expression for the entropy of a Markov chain, it is rare that the entropy of an HMP or MRF can be computed exactly. The hard square model is a classical example, for which computation of entropy has eluded a solution for decades. The main goals of this project are to further develop estimates and asymptotics of entropy for HMP's and MRF's and to solve related structural problems for such processes. We will extend our previous work on HMP's from discrete-valued to continuous-valued processes and will improve our earlier work on exponentially-fast approximations to entropy for MRF's.