Variational inference engine for probabilistic graphical models

• US 6,556,960 B1
• Filed: 09/01/1999
• Issued: 04/29/2003
• Est. Priority Date: 09/01/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Winn, John, Spiegelhalter, David J., Bishop, Christopher
• Primary Examiner(s): Broda, Samuel
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US09/388,268
• Time in Patent Office: 1,336 Days
• Field of Search: 703/2, 703/22, 706/22, 700/28
• US Class Current: 703/2
• 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

Abstract

A variational inference engine for probabilistic graphical models is disclosed. In one embodiment, a method includes inputting a specification for a model that has observable variables and unobservable variables. The specification includes a functional form for the conditional distributions of the model, and a structure for a graph of model that has nodes for each of the variables. The method determines a distribution for the unobservable variables that approximates the exact posterior distribution, based on the graph'"'"'s structure and the functional form for the model'"'"'s conditional distributions. The engine thus allows a user to design, implement and solve models without mathematical analysis or computer coding.

Claims

1. A computer-implemented method for a variational inference engine comprising:

inputting a specification for a model having a plurality of observable variables and a plurality of unobservable variables, the specification including a functional form for a plurality of conditional distributions of the model and a structure for a graph of the model having nodes for each of the plurality of observable variables and the plurality of unobservable variables;

determining a distribution for the plurality of unobservable variables that approximates the true posterior distribution based on the structure for the graph of the model and the functional form for the plurality of conditional distributions of the model, using variational methods; and

,

outputting at least the distribution that approximates the true posterior distribution of the model.

2. The method of claim 1, wherein determining a distribution that approximates the true posterior distribution of the model comprises:

initializing the distribution for the plurality of unobservable variables, the distribution having a plurality of distribution components corresponding to the plurality of unobservable variables, and a functional form that factorizes over the plurality of unobservable variables and that is based on the functional form for the plurality of conditional distributions of the model;

performing a free-form minimization over each distribution component in a distribution component-by-distribution component manner; and

,

repeating performance of the free-form minimization until a predetermined convergence criterion has been met.

3. The method of claim 1, wherein at least one of the plurality of unobservable variables is a meta variable representing a plurality of other unobservable variables.

4. The method of claim 1, wherein the functional form for the plurality of conditional distributions of the model comprises a conjugate distribution form.

5. The method of claim 1, wherein the functional form for the plurality of conditional distributions comprises a linear-Gaussian distribution form with Wishart priors for inverse covariance matrices of the distributions.

6. The method of claim 1, wherein the functional form for the plurality of conditional distributions is such that Bayesian Principal Component Analysis (PCA) is implemented.

7. The method of claim 1, wherein the functional form for the plurality of conditional distributions comprises a discrete distribution form having discrete nodes.

8. The method of claim 1, wherein the functional form for the plurality of conditional distributions comprises a discrete distribution form having Dirichlet nodes.

9. The method of claim 1, wherein inputting a specification comprises displaying a list of plurality of function forms for a user to select the functional form.

10. The method of claim 1, wherein inputting a specification comprises inputting a script representing the structure for the graph.

11. The method of claim 1, wherein inputting a specification comprises providing a graphical user interface for a user to draw the structure of the graph.

12. The method of claim 1, wherein outputting at least the distribution comprises outputting the model including the distribution that approximates the true posterior distribution of the model.

13. A computer-implemented method for a variational inference engine comprising:

inputting a specification for a model having a plurality of observable variables and a plurality of unobservable variables, the specification including a functional form for a plurality of conditional distributions of the model and a structure for a graph of the model having nodes for each of the plurality of observable variables and the plurality of unobservable variables;

initializing a distribution for the plurality of unobservable variables that approximates the true posterior distribution, the distribution having a plurality of distribution components corresponding to the plurality of unobservable variables and that is based on the functional form for the plurality of conditional distributions of the model;

performing a free-form minimization over each distribution component in a distribution component-by-distribution component manner;

repeating performance of the free-form minimization until a predetermined convergence criterion has been met; and

,

outputting at least the distribution that approximates the true posterior distribution of the model.

14. The method of claim 13, wherein at least one of the plurality of unobservable variables is a meta variable representing a plurality of other unobservable variables.

15. The method of claim 13, wherein the functional form for the plurality of conditional distributions of the model comprises a conjugate distribution form.

16. The method of claim 13, wherein the functional form for the plurality of conditional distributions comprises one of:

a linear-Gaussian distribution form with Wishart priors for inverse covariance matrices of the distributions, and, a discrete distribution form having discrete nodes.

17. The method of claim 13, wherein inputting a specification comprises at least one of:

displaying a list of a plurality of function forms for a user to select the functional form, inputting a script representing the structure for the graph, and providing a graphical user interface for a user to draw the structure of the graph.

18. The method of claim 13, wherein outputting at least the distribution comprises outputting the model including the distribution that approximates the true posterior distribution of the model.

19. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for a variational inference engine comprising:

inputting a specification for a model having a plurality of observable variables and a plurality of unobservable variables, the specification including a functional form for a plurality of conditional distributions of the model and a structure for a graph of the model having nodes for each of the plurality of observable variables and the plurality of unobservable variables;

determining a distribution for the plurality of unobservable variables that approximates the true posterior distribution based on the structure for the graph of the model and the functional form for the plurality of conditional distributions of the model, using variational methods; and

,

outputting at least the distribution that approximates the true posterior distribution of the model.

20. The medium of claim 19, wherein determining a distribution that approximates the true posterior distribution of the model comprises:

initializing the distribution for the plurality of unobservable variables, the distribution having a plurality of distribution components corresponding to the plurality of unobservable variables, and a functional form that factorizes over the plurality of unobservable variables, and a functional form that factorizes over the plurality of unobservable variables and that is based on the functional form for the plurality of conditional distributions of the model;

performing a free-form minimization over each distribution component in a distribution component-by-distribution component manner; and

,

repeating performance of the free-form minimization until a predetermined convergence criterion has been met.

21. The medium of claim 19, wherein at least one of the plurality of unobservable variables is a meta variable representing a plurality of other unobservable variables.

22. The medium of claim 19, wherein the functional form for the plurality of conditional distributions of the model comprises a conjugate distribution form.

23. The medium of claim 19, wherein the functional form for the plurality of conditional distributions comprises one of:

a linear-Gaussian distribution form with Wishart priors for inverse covariance matrices of the distributions, and, a discrete distribution form having discrete nodes.

24. The medium of claim 19, wherein inputting a specification comprises at least one of:

displaying a list of a plurality of function forms for a user to select the functional form, inputting a script representing the structure for the graph, and providing a graphical user interface for a user to draw the structure of the graph.

25. A computer-readable medium having instructions stored thereon for execution by a processor to perform a method for a variational inference engine comprising:

inputting a specification for a model having a plurality of observable variables and a plurality of unobservable variables, the specification including a functional form for a plurality of conditional distributions of the model and a structure for a graph of the model having nodes for each of the plurality of observable variables and the plurality of unobservable variables;

initializing a distribution for the plurality of unobservable variables that approximates the true posterior distribution, the distribution having a plurality of distribution components corresponding to the plurality of unobservable variables, and a functional form that factorizes over the plurality of unobservable variables and that is based on the functional form for the plurality of conditional distributions of the model;

performing a free-form minimization over each distribution component in a distribution component-by-distribution component manner;

repeating performance of the free-form minimization until a predetermined convergence criterion has been met; and

,

outputting at least the distribution that approximates the true posterior distribution of the model.

26. The medium of claim 25, wherein at least one of the plurality of unobservable variables is a meta variable representing a plurality of other unobservable variables.

27. The medium of claim 25, wherein the functional form for the plurality of conditional distributions of the model comprises a conjugate distribution form.

28. The medium of claim 25, wherein inputting a specification comprises at least one of:

displaying a list of a plurality of function forms for a user to select the functional form, inputting a script representing the structure for the graph, and providing a graphical user interface for a user to draw the structure of the graph.