May 09, 2004

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