Dynamic Scaled Sampling for Deterministic Constraints
Lei Li, Bharath Ramsundar, Stuart Russell · 2013
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(X1,..., Xk) holds, where each Xi has a continuous prior pdf and we wish to obtain samples from the conditional distribution P (X1,..., Xk | Z = s). When f is addition, the problem is NP-hard even when the Xi are independent. In more restricted cases—for example, i.i.d. Boolean or categorical Xi—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. 1