Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

6-2013

Abstract

We study the problem of approximate inference in collective graphical models (CGMs), which were recently introduced to model the problem of learning and inference with noisy aggregate observations. We first analyze the complexity of inference in CGMs: unlike inference in conventional graphical models, exact inference in CGMs is NP-hard even for tree-structured models. We then develop a tractable convex approximation to the NP-hard MAP inference problem in CGMs, and show how to use MAP inference for approximate marginal inference within the EM framework. We demonstrate empirically that these approximation techniques can reduce the computational cost of inference by two orders of magnitude and the cost of learning by at least an order of magnitude while providing solutions of equal or better quality.

Discipline

Artificial Intelligence and Robotics | Numerical Analysis and Scientific Computing

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of Machine Learning Research: 30th International Conference on Machine Learning 2013, June 16-21, Atlanta, GA

Volume

28

Issue

3

First Page

1004

Last Page

1012

Publisher

JMLR

City or Country

Cambridge, MA

Copyright Owner and License

Authors

Additional URL

http://proceedings.mlr.press/v28/sheldon13.html

Download

Share

COinS