Probabilistic sampling using search trees constrained by heuristic bounds
First Claim
1. A method comprising:
- performing independent Metropolis-Hastings (MH) sampling of elements of a domain to be sampled to generate a set of samples, wherein the independent MH sampling is performed over a search tree of decision sequences representing the domain to be sampled, the search tree of decision sequences including non-terminal decision nodes and terminal nodes corresponding to elements of the domain, the independent MH sampling comprising following decision sequences of the search tree by traversing the search tree from node to node in a direction away from a root node following decision branches in accordance with the layout of the search tree with the decision sequence terminating at a terminal node identifying an element to be considered for acceptance or rejection; and
constraining the independent MH sampling using a bound on nodes of the search tree wherein the value of the bound at a non-terminal decision node is a bound on the values of all terminal nodes reachable by traversing the search tree from the non-terminal decision node;
wherein the performing and the constraining are performed by a digital processing device.
1 Assignment
0 Petitions
Accused Products
Abstract
Markov Chain Monte Carlo (MCMC) sampling of elements of a domain to be sampled is performed to generate a set of samples. The MCMC sampling is performed over a search tree of decision sequences representing the domain to be sampled and having terminal nodes corresponding to elements of the domain. In some embodiments the MCMC sampling is performed by Metropolis-Hastings (MH) sampling. The MCMC sampling is constrained using a bound on nodes of the search tree. The constraint may entail detecting a node whose bound value ensures that an acceptable element cannot be identified by continuing traversal of the tree past that node, and terminating the traversal in response. The constraint may entail selecting a node to serve as a starting node for a sampling attempt in accordance with a statistical promise distribution indicating likelihood that following a decision sequence rooted at the node will identify an acceptable element.
1 Citation
22 Claims
-
1. A method comprising:
-
performing independent Metropolis-Hastings (MH) sampling of elements of a domain to be sampled to generate a set of samples, wherein the independent MH sampling is performed over a search tree of decision sequences representing the domain to be sampled, the search tree of decision sequences including non-terminal decision nodes and terminal nodes corresponding to elements of the domain, the independent MH sampling comprising following decision sequences of the search tree by traversing the search tree from node to node in a direction away from a root node following decision branches in accordance with the layout of the search tree with the decision sequence terminating at a terminal node identifying an element to be considered for acceptance or rejection; and constraining the independent MH sampling using a bound on nodes of the search tree wherein the value of the bound at a non-terminal decision node is a bound on the values of all terminal nodes reachable by traversing the search tree from the non-terminal decision node; wherein the performing and the constraining are performed by a digital processing device. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An apparatus comprising:
a computer programmed to perform a method comprising; performing Markov Chain Monte Carlo (MCMC) sampling of elements of a domain to be sampled to generate a set of samples, wherein the MCMC sampling is performed over a search tree of decision sequences representing the domain to be sampled, the search tree including non-terminal decision nodes and terminal nodes corresponding to elements of the domain, the search tree being traversed in a decision sequence by moving from node to node in a downward direction following decision branches in accordance with the layout of the search tree with the downward traversal terminating at one of the terminal nodes; and constraining the MCMC sampling using a bound on nodes of the search tree wherein the value of the bound at a non-terminal decision node is a bound on the values of all terminal nodes below the non-terminal decision node in the search tree. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
18. A non-transitory storage medium storing instructions executable by a digital processing device to perform a method comprising:
-
performing Markov Chain Monte Carlo (MCMC) sampling of elements of a domain to be sampled to generate a set of samples, wherein the MCMC sampling is performed over a search tree of decision sequences representing the domain, the search tree including non-terminal decision nodes and terminal nodes corresponding to elements of the domain, the search tree being traversed in a decision sequence by moving from node to node in a downward direction following decision branches in accordance with the layout of the search tree with the downward traversal terminating at one of the terminal nodes, wherein the MCMC sampling accepts or rejects elements based on a probabilistic acceptance criterion and a drawn probability, and wherein the MCMC sampling constrains the sampling based on values of a bound at non-terminal decision nodes of the search tree wherein the value of the bound at a non-terminal decision node is a bound on the values of all terminal nodes below the non-terminal decision node in the search tree. - View Dependent Claims (19, 20, 21, 22)
-
Specification