PROBABILISTIC SAMPLING USING SEARCH TREES CONSTRAINED BY HEURISTIC BOUNDS

• US 20120259807A1
• Filed: 04/11/2011
• Published: 10/11/2012
• Est. Priority Date: 04/11/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dymetman, Marc
• Granted Patent: US 8,983,887 B2
• Time in Patent Office: Days
• US Class Current: 706/50
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G06F 40/42 Data-driven translation
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

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.

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 and having terminal nodes corresponding to elements of the domain; and

constraining the independent MH sampling using a bound on nodes of the search tree;

wherein the performing and the constraining are performed by a digital processing device.

2. The method as set forth in claim 1, wherein the independent MH sampling comprises following decision sequences of the search tree to identify elements to be considered for acceptance or rejection, and the constraining comprises:

terminating the following of a decision sequence upon reaching a node whose bound value ensures that an acceptable element cannot be identified by continuing the following.

3. The method as set forth in claim 2, wherein the constraining further comprises:

in combination with the terminating, adding to the set of samples a repetition of a previously accepted sample.

4. The method as set forth in claim 1, wherein the independent MH sampling comprises selecting nodes of the search tree to serve as starting nodes for following decision sequences of the search tree to identify elements to be considered for acceptance or rejection, and the constraining comprises:

selecting a node to serve as a starting node in accordance with a statistical promise distribution indicating likelihood that following a decision sequence rooted at the node will identify an acceptable element.

5. The method as set forth in claim 4, wherein the constraining further comprises:

after selecting a starting node, adding to the set of samples n repetitions of a previously accepted sample where n is based on the value of the statistical promise distribution at the selected starting node.

6. The method as set forth in claim 1, wherein the domain comprises probabilistic parsings of natural language content and the search tree defines a parser comprising a probabilistic context-free grammar (PCFG).

7. The method as set forth in claim 6, wherein the search tree defines said parser comprising said PCFG multiplied by transversal constraint weights, the independent MH sampling uses the PCFG as a proposal distribution, and the bound on nodes of the search tree is based on the transversal constraint weights.

8. The method as set forth in claim 1, wherein the domain comprises probabilistic target language translations of natural language content in a source language and the search tree defines a translation engine comprising a statistical machine translation (SMT) multiplied by a target language n-gram language model.

9. The method as set forth in claim 8, wherein the independent MH sampling uses the SMT as a proposal distribution and the bound on nodes of the search tree is based on the n-gram language model.

10. A storage medium storing instructions executable by a processing device to perform a method as set forth in claim 1.

11. An apparatus comprising:

a digital processing device configured 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 and having terminal nodes corresponding to elements of the domain; and

constraining the MCMC sampling using a bound on nodes of the search tree.

12. The apparatus as set forth in claim 11, wherein the MCMC sampling comprises independent Metropolis-Hastings (MH) sampling.

13. The apparatus as set forth in claim 11, wherein the MCMC sampling comprises traversing decision sequences of the search tree to identify elements to be considered for acceptance or rejection, and the constraining comprises:

responsive to traversal of a decision sequence reaching a node whose bound value ensures that an acceptable element cannot be identified by continuing the traversal, performing the operations of terminating the traversal and adding a repetition of a previously accepted sample to the set of samples.

14. The apparatus as set forth in claim 11, wherein the MCMC sampling comprises selecting nodes of the search tree to serve as starting nodes for traversing the search tree to identify elements to be considered for acceptance or rejection, and the constraining comprises:

selecting a node to serve as a starting node in accordance with a statistical promise distribution indicating likelihood that following a decision sequence rooted at the node will identify an acceptable element.

15. The apparatus as set forth in claim 11, wherein the MCMC sampling comprises selecting nodes of the search tree to serve as starting nodes for traversing the search tree to identify elements to be considered for acceptance or rejection, and the constraining comprises:

(i) selecting a node to serve as a starting node in accordance with a statistical promise distribution indicating likelihood that following a decision sequence rooted at the node will identify an acceptable element and (ii) adding n repetitions of a previously accepted sample to the set of samples where n is based on the value of the statistical promise distribution at the selected starting node.

16. The apparatus as set forth in claim 11, wherein the domain comprises probabilistic parsings of natural language content and the method comprises a natural language parsing method.

17. The apparatus as set forth in claim 11, wherein the domain comprises probabilistic target language translations of natural language content in a source language and the method comprises a natural language translation method.

18. A 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 and having terminal nodes corresponding to elements of the domain,

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 nodes of the search tree.

19. The storage medium of claim 18, wherein the acceptance criterion comprises an unnormalized target probability to which the MCMC sampling conforms.

20. The storage medium of claim 18, wherein the performing comprises:

performing independent Metropolis-Hastings (MH) sampling over the search tree to generate the set of samples.

21. The storage medium of claim 18, wherein the performing comprises:

selecting a node of the search tree; and

traversing the search tree starting at the selected node until one of the following conditions is met;

(1) a terminal node is reached and (2) the value of the bound at a traversed nonterminal node does not satisfy the acceptance criterion.

22. The storage medium of claim 18, wherein the performing MCMC sampling of elements of a domain comprises:

selecting a node of the search tree in accordance with a statistical promise distribution; and

adding n repetitions of a previously accepted sample to the set of samples where n is based on the value of the statistical promise distribution at the selected node.