Data-parallel probabilistic inference

• US 10,496,929 B2
• Filed: 06/26/2014
• Issued: 12/03/2019
• Est. Priority Date: 09/30/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Tristan, Jean-Baptiste, Steele, Jr., Guy L., Huang, Daniel E., Tassarotti, Joseph
• Primary Examiner(s): Afshar, Kamran
• Assistant Examiner(s): Buss, Benjamin J
• Application Number:
  US14/316,186
• Publication Number:
  US 20150095277A1
• Time in Patent Office: 1,986 Days
• Field of Search: None
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

The present invention relates to a probabilistic programming compiler that (a) generates data-parallel inference code to sample from probability distributions in models provided to the compiler; and (b) utilizes a modular framework to allow addition and removal of inference algorithm information based on which the compiler generates the inference code. For a given model, the described compiler can generate inference code that implements any one or more of the inference algorithms that are available to the compiler. The modular compiler framework utilizes an intermediate representation (IR) that symbolically represents features of probability distributions. The compiler then uses the IR as a basis for emitting inference code to sample from the one or more probability distributions represented in the IR. Further, the compiler produces parallelized inference code that facilitates efficient parallel processing of inference computations in order to take advantage of highly data-parallel architectures, such as GPUs.

Claims

1. A method comprising:

compiling source code, representing a model of a body of data, into an intermediate representation of the model;

wherein the model of the body of data specifies one or more probability distributions;

wherein the intermediate representation of the model represents at least one probability distribution, of the one or more probability distributions, with one or more mathematical expressions;

identifying a particular inference algorithm of a plurality of inference algorithms; and

producing inference code that implements the particular inference algorithm;

wherein the inference code is configured to sample from the at least one probability distribution of the one or more probability distributions; and

wherein producing the inference code is based, at least in part, on an analysis of the one or more mathematical expressions;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 further comprising:

prior to producing the inference code, performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises identifying one or more features of the at least one probability distribution that are represented in the one or more mathematical expressions.

3. The method of claim 1, further comprising:

prior to identifying the particular inference algorithm, receiving information indicating one or more rules for analyzing intermediate representations of models;

wherein the one or more rules are specific to the particular inference algorithm.

4. The method of claim 3 further comprising:

prior to producing the inference code, performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises;

rewriting the one or more mathematical expressions based, at least in part, on the one or more rules that are specific to the particular inference algorithm, to produce one or more transformed mathematical expressions, and

identifying features of the at least one probability distribution based, at least in part, on analysis of the one or more transformed mathematical expressions.

5. The method of claim 1, further comprising performing the analysis of the one or more mathematical expressions without materializing, in computer memory, values for data points of a graphical representation of the at least one probability distribution.

6. The method of claim 1 further comprising:

identifying a second inference algorithm, of the plurality of inference algorithms; and

producing second inference code that implements the second inference algorithm;

wherein the second inference code is configured to sample from the at least one probability distribution of the one or more probability distributions; and

wherein producing the second inference code is based, at least in part, on a second analysis of the one or more mathematical expressions.

7. The method of claim 6 wherein:

the inference code is first inference code;

the first inference code, implementing the particular inference algorithm, explores all of the one or more probability distributions specified in the model of the body of data; and

the second inference code, implementing the second inference algorithm, explores all of the one or more probability distributions specified in the model of the body of data.

8. The method of claim 1 further comprising:

identifying a second inference algorithm, of the plurality of inference algorithms; and

producing second inference code that implements the second inference algorithm;

wherein the second inference code is configured to sample from a second probability distribution of the one or more probability distributions;

wherein the second probability distribution is not a probability distribution of the at least one probability distribution; and

wherein producing the second inference code is based, at least in part, on a second analysis of the one or more mathematical expressions.

9. The method of claim 1 further comprising:

performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises identifying independencies between variables in the one or more mathematical expressions; and

wherein producing the inference code comprises building parallelism into the inference code based, at least in part, on the identified independencies.

10. The method of claim 9 wherein performing the analysis of the one or more mathematical expressions further comprises rewriting the one or more mathematical expressions based, at least in part, on one or more rewrite rules that are specific to a class of the at least one probability distribution, to produce one or more transformed mathematical expressions.

11. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

compiling source code, representing a model of a body of data, into an intermediate representation of the model;

wherein the model of the body of data specifies one or more probability distributions;

wherein the intermediate representation of the model represents at least one probability distribution, of the one or more probability distributions, with one or more mathematical expressions;

identifying a particular inference algorithm of a plurality of inference algorithms; and

producing inference code that implements the particular inference algorithm;

wherein the inference code is configured to sample from the at least one probability distribution of the one or more probability distributions; and

wherein producing the inference code is based, at least in part, on an analysis of the one or more mathematical expressions.

12. The one or more non-transitory computer-readable media of claim 11 wherein the instructions further comprise instructions that, when executed by one or more processors, cause:

prior to producing the inference code, performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises identifying one or more features of the at least one probability distribution that are represented in the one or more mathematical expressions.

13. The one or more non-transitory computer-readable media of claim 11, wherein the instructions further comprise instructions that, when executed by one or more processors, cause:

prior to identifying the particular inference algorithm, receiving information indicating one or more rules for analyzing intermediate representations of models;

wherein the one or more rules are specific to the particular inference algorithm.

14. The one or more non-transitory computer-readable media of claim 13 wherein the instructions further comprise instructions that, when executed by one or more processors, cause:

prior to producing the inference code, performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises;

rewriting the one or more mathematical expressions based, at least in part, on the one or more rules that are specific to the particular inference algorithm, to produce one or more transformed mathematical expressions, and

identifying features of the at least one probability distribution based, at least in part, on analysis of the one or more transformed mathematical expressions.

15. The one or more non-transitory computer-readable media of claim 11, wherein the instructions further comprise instructions that, when executed by one or more processors, cause performing the analysis of the one or more mathematical expressions without materializing, in computer memory, values for data points of a graphical representation of the at least one probability distribution.

16. The one or more non-transitory computer-readable media of claim 11 wherein the instructions further compromise instructions that, when executed by one or more processors, cause:

identifying a second inference algorithm, of the plurality of inference algorithms; and

producing second inference code that implements the second inference algorithm;

wherein the second inference code is configured to sample from the at least one probability distribution of the one or more probability distributions; and

wherein producing the second inference code is based, at least in part, on a second analysis of the one or more mathematical expressions.

17. The one or more non-transitory computer-readable media of claim 16 wherein:

the inference code is first inference code;

the first inference code, implementing the particular inference algorithm, explores all of the one or more probability distributions specified in the model of the body of data; and

the second inference code, implementing the second inference algorithm, explores all of the one or more probability distributions specified in the model of the body of data.

18. The one or more non-transitory computer-readable media of claim 11 wherein the instructions further comprise instructions that, when executed by one or more processors, cause:

identifying a second inference algorithm, of the plurality of inference algorithms; and

producing second inference code that implements the second inference algorithm;

wherein the second inference code is configured to sample from a second probability distribution of the one or more probability distributions;

wherein the second probability distribution is not a probability distribution of the at least one probability distribution; and

wherein producing the second inference code is based, at least in part, on a second analysis of the one or more mathematical expressions.

19. The one or more non-transitory computer-readable media of claim 11 wherein the instructions further comprise instructions that, when executed by one or more processors, cause:

performing the analysis of the one or more mathematical expressions;

wherein performing the analysis of the one or more mathematical expressions comprises identifying independencies between variables in the one or more mathematical expressions; and

wherein producing the inference code comprises building parallelism into the inference code based, at least in part, on the identified independencies.

20. The one or more non-transitory computer-readable media of claim 19 wherein performing the analysis of the one or more mathematical expressions further comprises rewriting the one or more mathematical expressions based, at least in part, on one or more rewrite rules that are specific to a class of the at least one probability distribution, to produce one or more transformed mathematical expression.