### Approximate inference and global (in)coherence

Commenting on one
of our recent posts on "Escher sentences", Fernando Pereira
writes:

Over the last ten years, work on graph models of (mostly probabilistic) inference has focused on techniques for *approximate* inference. Many interpretation and inference tasks, for instance image segmentation, have graph formulations that are computationally intractable. Some approximation methods enforce local constraints of bounded size while relaxing other constraints. Others approximate the original graph with tractable subgraphs (typically trees). Others till relax a discrete assignment problem into a continuous optimization problem that
can be solved efficiently. In all cases, the results of inference may not
be globally coherent. The rough parallels between these ways of approximately
solving inference tasks and "Escher" perceptual phenomena are intriguing.

Posted by Mark Liberman at May 9, 2004 07:39 AM