Staged mixture modeling

• US 7,133,811 B2
• Filed: 10/15/2002
• Issued: 11/07/2006
• Est. Priority Date: 10/15/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Heckerman, David E., Thiesson, Bo
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US10/270,914
• Publication Number:
  US 20040073537A1
• Time in Patent Office: 1,484 Days
• Field of Search: 703/2, 707/6, 707/5, 707/7, 707/101, 707/3, 707/100, 706/52, 706/48, 702/19, 345/767, 435/6, 435/7.1, 704/236, 705/10, 715/811, 382/187
• 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
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for generating staged mixture model(s) is provided. The staged mixture model includes a plurality of mixture components each having an associated mixture weight, and, an added mixture component having an initial structure, parameters and associated mixture weight. The added mixture component is modified based, at least in part, upon a case that is undesirably addressed by the plurality of mixture components using a structural expectation maximization (SEM) algorithm to modify at the structure, parameters and/or associated mixture weight of the added mixture component.

The staged mixture model employs a data-driven staged mixture modeling technique, for example, for building density, regression, and classification model(s). The basic approach is to add mixture component(s) (e.g., sequentially) to the staged mixture model using an SEM algorithm.

Claims

1. A staged mixture model for improved data mining, comprising:

a plurality of mixture components each having an associated mixture weight;

an added mixture component having a structure, parameters and associated mixture weight,

the added mixture component modified based upon at least one case that is undesirably addressed by the plurality of mixture components using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the added mixture component; and

a plurality of sequentially added mixture components, each added mixture component added to the staged mixture model and modified based upon at least one case that is undesirably addressed by the plurality of mixture components using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the added mixture component.

2. The staged mixture model of claim 1, wherein a weighted data set for the added mixture component is computed using a current staged mixture model based on the case that is that is undesirably addressed by the plurality of mixture components.

3. The staged mixture model of claim 2, wherein a potential added mixture component is learnt using the weighted data set for the added mixture component and the fractionally weighted-data learning method.

4. The staged mixture model of claim 3, wherein a staged mixture model score is calculated for the potential added mixture component and another score calculated for the added mixture component.

5. The staged mixture model of claim 4, wherein a comparison between the model score for the added mixture component and the model score of the potential added mixture component is applied to determine if the potential added mixture component should replace the added mixture component.

6. The staged mixture model of claim 5, wherein the staged mixture model is modified based upon the added mixture component, the associated mixture weight of the added mixture component and the current staged mixture model.

7. The staged mixture model of claim 1, wherein at least one of the mixture components comprises a Bayesian network.

8. The staged mixture model of claim 1, wherein at least one of the mixture components comprises a decision tree with a bounded number of leaves.

9. The staged mixture model of claim 1, wherein at least one of the mixture components comprises a decision tree.

10. A density estimation model employing the staged mixture model of claim 1.

11. A classification model employing the staged mixture model of claim 1.

12. A regression model employing the staged mixture model of claim 1.

13. A staged mixture model generation system for improved data mining, comprising:

a current mixture model including a plurality of mixture components each having an associated mixture weight;

a mixture component and weight provider that provides an added mixture component having a structure, parameters and an associated mixture weight; and

a mixture component modifier that modifies the added mixture component based upon at least one case that is undesirably addressed by the plurality of mixture components using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the added mixture component.

14. The system of claim 13, wherein the mixture component modifier computes a weighted data set for the added mixture component using the current staged mixture model to determine at least one case that is undesirably addressed by the plurality of mixture components.

15. The system of claim 14, wherein the mixture component modifier further learns a potential added mixture component using a weighted data set for the added mixture component and a fractionally weighted-data learning method.

16. The system of claim 15, wherein the mixture component modifier calculates a staged mixture model score for the potential added mixture component and another score for the added mixture component.

17. The system of claim 16, wherein the mixture component modifier uses a comparison between the model score for the added mixture component and the model score of the potential added mixture component to determine if the potential added mixture component should replace the added mixture component.

18. The system of claim 17, wherein the mixture component modifier modifies the staged mixture model based upon the added mixture component, the associated mixture weight of the added mixture component and the current staged mixture model.

19. The system of claim 13, wherein at least one of the mixture components comprises a Bayesian network.

20. The system of claim 13, wherein at least one of the mixture components comprises a decision tree with a bounded number of leaves.

21. The system of claim 13, wherein at least one of the mixture components comprises a decision tree.

22. A method for learning a staged mixture model for improved data mining, comprising:

loading a plurality of mixture components each having an associated mixture weight into a mixture model;

sequentially adding mixture components to the mixture model, the mixture components having a structure, parameters and associated mixture weights, and corresponding to cases that are undesirably addressed by existing mixture components of the mixture model; and

,

employing a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, parameters and the associated mixture weights of the added mixture components.

23. A method for generating a staged mixture model for improved data mining, comprising:

loading a plurality of mixture components each having an associated mixture weight into a mixture model;

adding a mixture component having a structure, parameters and associated mixture weight;

modifying at least one of the structure and parameters of the added mixture component based upon a fractionally weighted-data learning method; and

,

modifying the associated mixture weight of the added mixture component based upon a structural expectation maximization (SEM) algorithm.

24. A method for learning a staged mixture model for improved data mining, comprising:

loading a plurality of mixture components each having an associated mixture weight;

computing a weighted data set for the added mixture component using a current staged mixture model to determine at least one case that is undesirably addressed by the plurality of mixture components;

learning a potential added component based upon a fractionally weighted-data learning method;

calculating a model score associated with the potential added component and the added mixture component; and

,

modifying the added mixture component based upon the potential added component, if the model score of the potential added component is greater than the model score of the added mixture component; and

modifying the staged mixture model based upon an added mixture component, the current staged mixture model and associated weight of the added mixture component.

25. The method of claim 24, further comprising at least one of the following steps:

computing a weighted data set for the added mixture component using the current staged mixture model; and

,

modifying the associated weight of the added mixture component using the weighted data set and a structural expectation maximization (SEM) algorithm.

26. A staged method for constructing a mixture model for improved data mining, comprising:

providing a plurality of mixture components each having an associated mixture weight;

sequentially adding at least one mixture component to the mixture model with a pre-specified structure, parameters and associated mixture weight, each added mixture component added to the mixture model based upon at least one case that is undesirably addressed by the plurality of mixture components; and

,

employing a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the added mixture component.

27. The method of claim 26, wherein the structure and parameters of at least one of the added mixture components in the mixture model is fixed.

28. The method of claim 27, wherein associated weights of the added mixture components of the mixture model is fixed.

29. The method of claim 26, wherein the parameters of at least one of the added mixture components of the mixture model is fixed.

30. The method of claim 29, wherein associated weights of the added mixture components of the mixture model is fixed.

31. The method of claim 26, wherein the mixture weight of at least one of the added mixture components in the mixture model is fixed.

32. A method for learning a staged mixture model for improved data mining, comprising:

providing a plurality of mixture components each having an associated mixture weight;

adding a mixture component having a structure, parameters and associated mixture weight;

modifying at least one of the structure and the parameters of the added mixture component based upon a fractionally weighted-data learning method; and

,

modifying the associated mixture weight of the added mixture component using a structural expectation maximization (SEM) algorithm.

33. A computer implemented signal for a staged mixture model generation system, comprising the following computer executable components:

a mixture model component having at least one added mixture component, the at least one added mixture component having a structure, parameters and associated mixture weight, and modified based upon at least one case that was undesirably addressed by a plurality of mixture components;

the computer implemented signal using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the at least one added mixture component.

34. A computer readable medium storing computer executable instructions of a staged mixture model, comprising:

a plurality of mixture components each having a structure, parameters and associated mixture weight; and

,

at least one added mixture component having been modified based upon at least one case that is undesirably addressed by the plurality of mixture components and using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the at least one added mixture component.

35. A staged mixture model generation system for improved data mining, comprising:

means for providing a plurality of mixture components each having an associated mixture weight;

means for providing an added mixture component to the staged mixture model, the added mixture component having a structure, parameters and associated mixture weight;

means for modifying the added mixture component based upon at least one case that is undesirably addressed by a plurality of mixture components and using a fractionally weighted-data learning method and a structural expectation maximization (SEM) algorithm to modify the structure, at least one of the parameters and associated mixture weight of the added mixture component.