Dynamic Scaled Sampling for Deterministic Constraints

Lei Li, Bharath Ramsundar, Stuart Russell
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:397-405, 2013.

Abstract

Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in which the relationship Z = f(X_1,...,X_k) holds, where each X_i has a continuous prior pdf and we wish to obtain samples from the conditional distribution P(X_1,...,X_k | Z= s). When f is addition, the problem is NP-hard even when the X_i are independent. In more restricted cases — for example, i.i.d. Boolean or categorical X_i — efficient exact samplers have been obtained previously. For the general continuous case, we propose a dynamic scaling algorithm (DYSC), and prove that it has O(k) expected running time and finite variance. We discuss generalizations of DYSC to functions f described by binary operation trees. We evaluate the algorithm on several examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-li13a, title = {Dynamic Scaled Sampling for Deterministic Constraints}, author = {Li, Lei and Ramsundar, Bharath and Russell, Stuart}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {397--405}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/li13a.pdf}, url = {https://proceedings.mlr.press/v31/li13a.html}, abstract = {Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in which the relationship Z = f(X_1,...,X_k) holds, where each X_i has a continuous prior pdf and we wish to obtain samples from the conditional distribution P(X_1,...,X_k | Z= s). When f is addition, the problem is NP-hard even when the X_i are independent. In more restricted cases — for example, i.i.d. Boolean or categorical X_i — efficient exact samplers have been obtained previously. For the general continuous case, we propose a dynamic scaling algorithm (DYSC), and prove that it has O(k) expected running time and finite variance. We discuss generalizations of DYSC to functions f described by binary operation trees. We evaluate the algorithm on several examples. } }
Endnote
%0 Conference Paper %T Dynamic Scaled Sampling for Deterministic Constraints %A Lei Li %A Bharath Ramsundar %A Stuart Russell %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-li13a %I PMLR %P 397--405 %U https://proceedings.mlr.press/v31/li13a.html %V 31 %X Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in which the relationship Z = f(X_1,...,X_k) holds, where each X_i has a continuous prior pdf and we wish to obtain samples from the conditional distribution P(X_1,...,X_k | Z= s). When f is addition, the problem is NP-hard even when the X_i are independent. In more restricted cases — for example, i.i.d. Boolean or categorical X_i — efficient exact samplers have been obtained previously. For the general continuous case, we propose a dynamic scaling algorithm (DYSC), and prove that it has O(k) expected running time and finite variance. We discuss generalizations of DYSC to functions f described by binary operation trees. We evaluate the algorithm on several examples.
RIS
TY - CPAPER TI - Dynamic Scaled Sampling for Deterministic Constraints AU - Lei Li AU - Bharath Ramsundar AU - Stuart Russell BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-li13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 397 EP - 405 L1 - http://proceedings.mlr.press/v31/li13a.pdf UR - https://proceedings.mlr.press/v31/li13a.html AB - Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in which the relationship Z = f(X_1,...,X_k) holds, where each X_i has a continuous prior pdf and we wish to obtain samples from the conditional distribution P(X_1,...,X_k | Z= s). When f is addition, the problem is NP-hard even when the X_i are independent. In more restricted cases — for example, i.i.d. Boolean or categorical X_i — efficient exact samplers have been obtained previously. For the general continuous case, we propose a dynamic scaling algorithm (DYSC), and prove that it has O(k) expected running time and finite variance. We discuss generalizations of DYSC to functions f described by binary operation trees. We evaluate the algorithm on several examples. ER -
APA
Li, L., Ramsundar, B. & Russell, S.. (2013). Dynamic Scaled Sampling for Deterministic Constraints. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:397-405 Available from https://proceedings.mlr.press/v31/li13a.html.

Related Material