Efficient gradient computation for conditional Gaussian graphical models

• US 7,596,475 B2
• Filed: 12/06/2004
• Issued: 09/29/2009
• Est. Priority Date: 12/06/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Thiesson, Bo
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): PIERRE LOUIS, ANDRE
• Application Number:
  US11/005,148
• Publication Number:
  US 20080010043A1
• Time in Patent Office: 1,758 Days
• Field of Search: 703/2, 706/14, 706/21, 706/25, 706/41
• US Class Current: 703/2
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks

Abstract

The subject invention leverages standard probabilistic inference techniques to determine a log-likelihood for a conditional Gaussian graphical model of a data set with at least one continuous variable and with data not observed for at least one of the variables. This provides an efficient means to compute gradients for CG models with continuous variables and incomplete data observations. The subject invention allows gradient-based optimization processes to employ gradients to iteratively adapt parameters of models in order to improve incomplete data log-likelihoods and identify maximum likelihood estimates (MLE) and/or local maxima of the incomplete data log-likelihoods. Conditional Gaussian local gradients along with conditional multinomial local gradients determined by the subject invention can be utilized to facilitate in providing parameter gradients for full conditional Gaussian models.

Claims

1. A system that facilitates statistical modeling in an artificial intelligence application, comprising

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement the system, including;

a gradient determination component that utilizes a data set for a set of variables and probabilistic inference to determine parameter gradients for a log-likelihood of a conditional Gaussian (CG) graphical model over those variables with at least one continuous variable and with incomplete observation data for at least one of the variables, the CG graphical model employed to deduce a cause of a given outcome represented by the data set;

wherein the parameter gradients comprise conditional multinomial local gradients and at least one conditional Gaussian local gradient, the gradient determination component determines the conditional multinomial local gradients by performing a line search to update the parameters of an exponential model representation, converting the updated parameterization to a non-exponential representation, and utilizing a propagation scheme on the non-exponential representation to compute the next gradient.

2. The system of claim 1 employed by a gradient-based optimization process that iteratively adapts parameters of a model to improve incomplete data log-likelihood.

3. The system of claim 2, the gradient-based optimization process comprising a conjugate gradient process.

4. The system of claim 1, the gradient determination component utilizes a Recursive Exponential Mixed Model (REMM) representation of the CG graphical model to facilitate in determining the parameter gradients, the Recursive Exponential Mixed Model has both continuous and discrete variables and is defined in terms of local models represented as regular exponential models that satisfy global and partial local variation independence.

5. The system of claim 1, the gradient determination component determines parameter gradients of a graphical model with at least two equal parameters.

6. The system of claim 1, the gradient determination component determines parameter gradients of a graphical model with at least one parameter fixed to a specific value.

7. The system of claim 1, the gradient determination component determines parameter gradients of a graphical model with at least one parameter fixed to a specific value and with at least two equal parameters.

8. The system of claim 7, the graphical model comprising a stochastic autoregressive moving average model.

9. The system of claim 1, the gradient determination component employs an exponential model representation that automatically enforces that p^s≧

0 and

$\underset{s}{\sum <br><br>}<br><br><br><br>p^s=1$

to facilitate in optimizing at least one gradient parameter.

10. The system of claim 1, the incomplete observation data comprising data that is incomplete in a non-informative manner.

11. The system of claim 1, the probabilistic inference comprising a propagation scheme for Bayesian networks with conditional Gaussian distributions.

27. A device employing the system of claim 1 comprising at least one of a computer, a server, or a handheld electronic device.

12. A method for facilitating statistical modeling in an artificial intelligence application, comprising:

employing a processor executing computer-executable instructions stored on a computer-readable storage medium to implement the following acts;

receiving at least one data set representing an outcome, the at least one data set having incomplete observation data for a set of variables with at least one continuous variable;

utilizing the data set and probabilistic inference to determine parameter gradients for a log-likelihood of a conditional Gaussian (CG) graphical model over those variables;

representing the CG graphical model as a recursive exponential mixed model (REMM);

determining a conditional Gaussian regression in the REMM representation model;

utilizing a chain rule to transform a resulting parameter gradient expression into a parameter representation of c, β

, and σ

, representing an intercept, coefficients, and variance, respectively for a regression on continuous parents;

employing probabilistic inference to determine quantities in the parameter gradient expression;

converting a resulting parameterization into a non-exponential representation;

utilizing a propagation scheme on the non-exponential parameterization in order to compute at least one gradient;

assigning, for all families (X_v,X_pa(v)) where X_v is a continuous variable, each configuration of discrete parent variables x^d _pa(v) a sum vector and a sum of squares matrix for expected posterior statistics associated with conditional distributions for the continuous variable and its continuous parents (X_v,X^c_pa(v)) given configurations of discrete parents;

For each data case in a data set;

utilizing a propagation scheme for Bayesian networks with conditional Gaussian distributions to determine a mean vector and a covariance matrix associated with a posterior marginal distribution for all families (X_v,X_pa(v)), where X_v is a continuous variable;

employing posterior conditional means and variances to determine expected values (x_v*,x^c_pa(v)*) and ((x_vx_v)*, (x_v x^c_pa(v))*, (x_v x^c_pa(v)′

)*, (x^c_pa(v)′

X^c_pa(v))*) for continuous variables in each of these families given each configuration of discrete variables in the respective families;

adding the expected values to the sum and the sum of squares expected posterior statistics; and

determining the parameter gradients utilizing a formula for a sample of incomplete observations;

employing the CG graphical model to deduce a cause of the given outcome in an artificial intelligence application; and

displaying the deduced cause on a display device.

13. The method of claim 12 further comprising:

employing the parameter gradients in a gradient-based optimization process that iteratively adapts parameters of a model to improve incomplete data likelihood.

14. The method of claim 13, the gradient-based optimization process comprising a conjugate gradient process.

15. The method of claim 12 further comprising:

utilizing a Recursive Exponential Mixed Model (REMM) representation of the CG graphical model to facilitate in determining the parameter gradients.

16. The method of claim 12 further comprising:

determining parameter gradients of a graphical model with at least two equal parameters.

17. The method of claim 12 further comprising:

determining parameter gradients of a graphical model with at least one parameter fixed to a specific value.

18. The method of claim 12 further comprising:

determining parameter gradients of a graphical model with at least one parameter fixed to a specific value and with at least two equal parameters.

19. The method of claim 18, the graphical model comprising a stochastic autoregressive moving average model.

20. The method of claim 12 further comprising:

optimizing at least one gradient parameter via utilization of an exponential model representation that automatically enforces that p^s≧

0 and

$\underset{s}{\sum <br><br>}<br><br><br><br>p^s=1$

to facilitate in optimizing at least one gradient parameter;

converting the resulting parameterization into a non-exponential representation; and

utilizing a propagation scheme on the non-exponential parameterization in order to compute at least one gradient.

21. The method of claim 12, the incomplete observation data comprising data that is incomplete in a non-informative manner.

22. The method of claim 12, the parameter gradients comprising conditional multinomial local gradients and/or at least one conditional Gaussian local gradients.

23. The method of claim 12, the probabilistic inference comprising a propagation scheme for Bayesian networks with conditional Gaussian distributions.

24. The method of claim 12 further comprising:

assigning, for all families (X_v,X_pa(v)) where X_v is a continuous variable, each configuration of discrete parent variables x^d_pa(v) a local sample gradient vector and selling it to zero;

For each data case in a data set;

utilizing a propagation scheme for Bayesian networks with conditional Gaussian distributions to determine a mean vector and a covariance matrix associated with a posterior marginal distribution for all families (X_v,X_pa(v)), where X_v is a continuous variable;

employing posterior conditional means and variances to determine expected values (x_v*,x^c_pa(v)*) and ((x_vx_v)*, (x_v x^c_pa(v))*, (x_v x^c_pa(v)′

)*, (x^c_pa(v)′

x^c_pa(v))*) for continuous variables in each of these families given each configuration of discrete variables in the respective families;

determining sample parameter gradients utilizing a formula for a sample of incomplete observations; and

adding single observation gradients to the sample parameter gradients.

26. A device employing the method of claim 12 comprising at least one of a computer, a server, or a handheld electronic device.

25. A system that facilitates statistical modeling in an artificial intelligence application, comprising:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement the system, including;

means for receiving at least one data set representing a given outcome, the at least one data set containing a set of variables;

means for utilizing the data set for the set of variables and probabilistic inference to determine parameter gradients for a log-likelihood of a conditional Gaussian (CG) graphical model over those variables with at least one continuous variable and with incomplete observation data for at least one of the variables, the CG graphical model employed to deduce a cause of the given outcome in an artificial intelligence application;

means for optimizing at least one gradient parameter via utilization of an exponential model representation that automatically enforces that p^s≧

0 and

$\underset{s}{\sum <br><br>}<br><br><br><br>p^s=1$

to facilitate in optimizing at least one gradient parameter;

means for converting the resulting parameterization into a non-exponential representation;

means for utilizing a propagation scheme on the non-exponential parameterization in order to compute at least one gradient; and

means for displaying the parameter gradients on a display device.