Approximate Inference in Collective Graphical Models

Daniel Sheldon, Tao Sun, Akshat Kumar, Tom Dietterich
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):1004-1012, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-sheldon13, title = {Approximate Inference in Collective Graphical Models}, author = {Sheldon, Daniel and Sun, Tao and Kumar, Akshat and Dietterich, Tom}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {1004--1012}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/sheldon13.pdf}, url = {https://proceedings.mlr.press/v28/sheldon13.html}, 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.} }
Endnote
%0 Conference Paper %T Approximate Inference in Collective Graphical Models %A Daniel Sheldon %A Tao Sun %A Akshat Kumar %A Tom Dietterich %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-sheldon13 %I PMLR %P 1004--1012 %U https://proceedings.mlr.press/v28/sheldon13.html %V 28 %N 3 %X 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.
RIS
TY - CPAPER TI - Approximate Inference in Collective Graphical Models AU - Daniel Sheldon AU - Tao Sun AU - Akshat Kumar AU - Tom Dietterich BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-sheldon13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 1004 EP - 1012 L1 - http://proceedings.mlr.press/v28/sheldon13.pdf UR - https://proceedings.mlr.press/v28/sheldon13.html AB - 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. ER -
APA
Sheldon, D., Sun, T., Kumar, A. & Dietterich, T.. (2013). Approximate Inference in Collective Graphical Models. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):1004-1012 Available from https://proceedings.mlr.press/v28/sheldon13.html.

Related Material