Stochastic Discrete Clenshaw-Curtis Quadrature

Nico Piatkowski, Katharina Morik
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:3000-3009, 2016.

Abstract

The partition function is fundamental for probabilistic graphical models—it is required for inference, parameter estimation, and model selection. Evaluating this function corresponds to discrete integration, namely a weighted sum over an exponentially large set. This task quickly becomes intractable as the dimensionality of the problem increases. We propose an approximation scheme that, for any discrete graphical model whose parameter vector has bounded norm, estimates the partition function with arbitrarily small error. Our algorithm relies on a near minimax optimal polynomial approximation to the potential function and a Clenshaw-Curtis style quadrature. Furthermore, we show that this algorithm can be randomized to split the computation into a high-complexity part and a low-complexity part, where the latter may be carried out on small computational devices. Experiments confirm that the new randomized algorithm is highly accurate if the parameter norm is small, and is otherwise comparable to methods with unbounded error.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-piatkowski16, title = {Stochastic Discrete Clenshaw-Curtis Quadrature}, author = {Piatkowski, Nico and Morik, Katharina}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {3000--3009}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/piatkowski16.pdf}, url = {https://proceedings.mlr.press/v48/piatkowski16.html}, abstract = {The partition function is fundamental for probabilistic graphical models—it is required for inference, parameter estimation, and model selection. Evaluating this function corresponds to discrete integration, namely a weighted sum over an exponentially large set. This task quickly becomes intractable as the dimensionality of the problem increases. We propose an approximation scheme that, for any discrete graphical model whose parameter vector has bounded norm, estimates the partition function with arbitrarily small error. Our algorithm relies on a near minimax optimal polynomial approximation to the potential function and a Clenshaw-Curtis style quadrature. Furthermore, we show that this algorithm can be randomized to split the computation into a high-complexity part and a low-complexity part, where the latter may be carried out on small computational devices. Experiments confirm that the new randomized algorithm is highly accurate if the parameter norm is small, and is otherwise comparable to methods with unbounded error.} }
Endnote
%0 Conference Paper %T Stochastic Discrete Clenshaw-Curtis Quadrature %A Nico Piatkowski %A Katharina Morik %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-piatkowski16 %I PMLR %P 3000--3009 %U https://proceedings.mlr.press/v48/piatkowski16.html %V 48 %X The partition function is fundamental for probabilistic graphical models—it is required for inference, parameter estimation, and model selection. Evaluating this function corresponds to discrete integration, namely a weighted sum over an exponentially large set. This task quickly becomes intractable as the dimensionality of the problem increases. We propose an approximation scheme that, for any discrete graphical model whose parameter vector has bounded norm, estimates the partition function with arbitrarily small error. Our algorithm relies on a near minimax optimal polynomial approximation to the potential function and a Clenshaw-Curtis style quadrature. Furthermore, we show that this algorithm can be randomized to split the computation into a high-complexity part and a low-complexity part, where the latter may be carried out on small computational devices. Experiments confirm that the new randomized algorithm is highly accurate if the parameter norm is small, and is otherwise comparable to methods with unbounded error.
RIS
TY - CPAPER TI - Stochastic Discrete Clenshaw-Curtis Quadrature AU - Nico Piatkowski AU - Katharina Morik BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-piatkowski16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 3000 EP - 3009 L1 - http://proceedings.mlr.press/v48/piatkowski16.pdf UR - https://proceedings.mlr.press/v48/piatkowski16.html AB - The partition function is fundamental for probabilistic graphical models—it is required for inference, parameter estimation, and model selection. Evaluating this function corresponds to discrete integration, namely a weighted sum over an exponentially large set. This task quickly becomes intractable as the dimensionality of the problem increases. We propose an approximation scheme that, for any discrete graphical model whose parameter vector has bounded norm, estimates the partition function with arbitrarily small error. Our algorithm relies on a near minimax optimal polynomial approximation to the potential function and a Clenshaw-Curtis style quadrature. Furthermore, we show that this algorithm can be randomized to split the computation into a high-complexity part and a low-complexity part, where the latter may be carried out on small computational devices. Experiments confirm that the new randomized algorithm is highly accurate if the parameter norm is small, and is otherwise comparable to methods with unbounded error. ER -
APA
Piatkowski, N. & Morik, K.. (2016). Stochastic Discrete Clenshaw-Curtis Quadrature. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:3000-3009 Available from https://proceedings.mlr.press/v48/piatkowski16.html.

Related Material