PROBABILISTIC SAMPLING USING RESEARCH TREES CONSTRAINED BY HEURISTIC LIMITS

摘要

Markov Chain Monte Carlo (MCMC) sampling of elements of a domain (14) to be sampled is performed to generate a set of samples. MCMC sampling (10) is performed on a decision sequence search tree that represents the domain to be sampled and has terminal nodes that correspond to elements of the domain. In some embodiments, MCMC sampling is performed by Metropolis-Hasting (MH) sampling. MCMC sampling is constrained by using a limitation on at nodes (20) of the search tree. The constraint may include detecting a node whose limiting value ensures that an acceptable element can not be identified by continuing traversal of the tree beyond that node, and stopping the traversal in response. to that. The constraint may include selecting a node to serve as a starting node for a sampling attempt in accordance with a statistical promise distribution that indicates the likelihood that the follow-up of a decision sequence whose root is found at the node will identify an acceptable element.