University of Washington - Department of Statistics
Markov Random Fields are extremely useful and generally applicable for probabilistic modelling of a wide range of systems. We'll review methods for performing inference calculations (most likely configuration and marginal probabilities) on MRFs. Unfortunately, for many tasks, these basic calculations are computationally infeasible. We'll discuss the limitations of standard computation methods and the graph-theoretic properties related to computational complexity. We then present Coarse-to-Fine Dynamic Programming, one method which may be able to overcome these limitations under certain circumstances.