Ignorant Inference: MAP and Marginal Inference for Large Scale Graphical Models in NLP

講演日: 平成22年11月26日講演場所: 情報科学研究科大講義室L1Large scale graphical models naturally arise in many natural language processing applications. They provide an expressive language for users to define their probabilistic models in, and come with a set of generic inference methods, such as belief propagation and its variants. However, for many of the problems we encounter in practice, these methods do not scale up well. For example, when using Belief Propagation for a state-of-the-art second order dependency parsing model, analysis of a long sentence can still take minutes. In this work I present an approach to inference in such networks that can dramatically improve runtime, and memory footprint. The core idea is to be ignorant: instead of considering the full graphical model, we ignore most of its edges. Which edges to ignore is decided dynamically: we start with a very small sub-model, solve it using any solver of choice, and add edges only if they can significantly change the solution. This process is repeated until convergence and applicable for both MA