Citation
L. Li, B. Ramsundar, S. Russell. "Dynamic Scaled Sampling for Deterministic Constraints". 16th International Conference on Artificial Intelligence and Statistics (AISTATS), 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(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.

Electronic downloads

• aistats13-dysc.pdf · application/pdf · 318 kbytes

• HTML

  L. Li, B. Ramsundar, S. Russell. <a
  href="http://robotics.eecs.berkeley.edu/pubs/10.html"
  >Dynamic Scaled Sampling for Deterministic
  Constraints</a>, 16th International Conference on
  Artificial Intelligence and Statistics (AISTATS), 2013.

• Plain text

  L. Li, B. Ramsundar, S. Russell. "Dynamic Scaled
  Sampling for Deterministic Constraints". 16th
  International Conference on Artificial Intelligence and
  Statistics (AISTATS), 2013.

• BibTeX

  @inproceedings{LiRamsundarRussell13_DynamicScaledSamplingForDeterministicConstraints,
      author = {L. Li and B. Ramsundar and S. Russell},
      title = {Dynamic Scaled Sampling for Deterministic
                Constraints},
      booktitle = {16th International Conference on Artificial
                Intelligence and Statistics (AISTATS)},
      year = {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(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.},
      URL = {http://robotics.eecs.berkeley.edu/pubs/10.html}
  }
  

Posted by Ehsan Elhamifar on 16 May 2014.
Groups: ehumans
For additional information, see the Publications FAQ or contact webmaster at robotics eecs berkeley edu.