Efficient Inference for Complex Queries on Complex Distributions

Lili Dworkin, Michael Kearns, Lirong Xia
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:211-219, 2014.

Abstract

We consider problems of approximate inference in which the query of interest is given by a complex formula (such as a formula in disjunctive formal form (DNF)) over a joint distribution given by a graphical model. We give a general reduction showing that (approximate) marginal inference for a class of distributions yields approximate inference for DNF queries, and extend our techniques to accommodate even more complex queries, and dense graphical models with variational inference, under certain conditions. Our results unify and generalize classical inference techniques (which are generally restricted to simple marginal queries) and approximate counting methods such as those introduced by Karp, Luby and Madras (which are generally restricted to product distributions).

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-dworkin14, title = {{Efficient Inference for Complex Queries on Complex Distributions}}, author = {Dworkin, Lili and Kearns, Michael and Xia, Lirong}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {211--219}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/dworkin14.pdf}, url = {https://proceedings.mlr.press/v33/dworkin14.html}, abstract = {We consider problems of approximate inference in which the query of interest is given by a complex formula (such as a formula in disjunctive formal form (DNF)) over a joint distribution given by a graphical model. We give a general reduction showing that (approximate) marginal inference for a class of distributions yields approximate inference for DNF queries, and extend our techniques to accommodate even more complex queries, and dense graphical models with variational inference, under certain conditions. Our results unify and generalize classical inference techniques (which are generally restricted to simple marginal queries) and approximate counting methods such as those introduced by Karp, Luby and Madras (which are generally restricted to product distributions).} }
Endnote
%0 Conference Paper %T Efficient Inference for Complex Queries on Complex Distributions %A Lili Dworkin %A Michael Kearns %A Lirong Xia %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-dworkin14 %I PMLR %P 211--219 %U https://proceedings.mlr.press/v33/dworkin14.html %V 33 %X We consider problems of approximate inference in which the query of interest is given by a complex formula (such as a formula in disjunctive formal form (DNF)) over a joint distribution given by a graphical model. We give a general reduction showing that (approximate) marginal inference for a class of distributions yields approximate inference for DNF queries, and extend our techniques to accommodate even more complex queries, and dense graphical models with variational inference, under certain conditions. Our results unify and generalize classical inference techniques (which are generally restricted to simple marginal queries) and approximate counting methods such as those introduced by Karp, Luby and Madras (which are generally restricted to product distributions).
RIS
TY - CPAPER TI - Efficient Inference for Complex Queries on Complex Distributions AU - Lili Dworkin AU - Michael Kearns AU - Lirong Xia BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-dworkin14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 211 EP - 219 L1 - http://proceedings.mlr.press/v33/dworkin14.pdf UR - https://proceedings.mlr.press/v33/dworkin14.html AB - We consider problems of approximate inference in which the query of interest is given by a complex formula (such as a formula in disjunctive formal form (DNF)) over a joint distribution given by a graphical model. We give a general reduction showing that (approximate) marginal inference for a class of distributions yields approximate inference for DNF queries, and extend our techniques to accommodate even more complex queries, and dense graphical models with variational inference, under certain conditions. Our results unify and generalize classical inference techniques (which are generally restricted to simple marginal queries) and approximate counting methods such as those introduced by Karp, Luby and Madras (which are generally restricted to product distributions). ER -
APA
Dworkin, L., Kearns, M. & Xia, L.. (2014). Efficient Inference for Complex Queries on Complex Distributions. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:211-219 Available from https://proceedings.mlr.press/v33/dworkin14.html.

Related Material