System and method for approximating probabilities using a decision tree

• US 6,718,315 B1
• Filed: 12/18/2000
• Issued: 04/06/2004
• Est. Priority Date: 12/18/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rounthwaite, Robert L., Bernhardt, Jeffrey R., Chickering, David M., Meek, Christopher A.
• Primary Examiner(s): Davis, George B.
• Assistant Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/740,067
• Time in Patent Office: 1,205 Days
• Field of Search: 706/12, 706/14, 706/46
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Disclosed is a system for approximating conditional probabilities using an annotated decision tree where predictor values that did not exist in training data for the system are tracked, stored, and referenced to determine if statistical aggregation should be invoked. Further disclosed is a system for storing statistics for deriving a non-leaf probability corresponding to predictor values, and a system for aggregating such statistics to approximate conditional probabilities.

Claims

1. A computerize system for extracting predictions from a decision tree, comprising:

a first component that tracks, for one or more split nodes in the decision tree, one or more predictor values that did not appear in at least k records in relevant training cases for the split node, k being an integer;

a second component that stores, for one or more predictor attributes, a set of known values for the one or more predictor attributes;

a third component that detects, during a traversal of the decision tree, that a predictor attribute corresponding to a split in the decision tree has not been assigned a value in a query; and

a fourth component that stores in a leaf node of the decision tree statistics for deriving a non-leaf probability corresponding to the one or more predictor values.

2. The system of claim 1, further comprising:

a fifth component that aggregates statistics from at least a subset of all leaf nodes that are descendants of a split node to approximate probabilities, when a given predictor value is at least one of the following;

missing, in a state that did not appear in at least k records, k being an integer, in the relevant training data for the split node and, a new value.

3. The system of claim 2 wherein the fifth component aggregates statistics from the subset consisting of all nodes descending from a split node.

4. The system of claim 2 wherein the fifth component utilizes the consistent look-ahead method to determine the subset of descendant leaf nodes from which statistics are aggregated.

5. The system of claim 2, further comprising:

a sixth component that detects when the fifth component approximates a probability.

6. The system of claim 2 wherein the statistics are stored in one or more nodes in the decision tree.

7. The system of claim 1, wherein the tracking component stores the one or more predictor values that did not appear at least k times in the relevant training cases in one or more nodes in the decision tree.

8. The system of claim 5, wherein if the sixth component identifies a missing predictor problem, the aggregating function of the fifth component is initiated.

9. The system of claim 5, wherein if the sixth component identifies an inadequate training data problem, the aggregating function of the fifth component is initiated.

10. The system of claim 5, wherein if the sixth component identifies a new value problem, the aggregating function of the fifth component is initiated.

11. A computerize method for extracting predictions from a decision tree, comprising:

identifying for one or more split nodes, a plurality of predictor values that did not appear in at least k records in relevant training data for the split node;

identifying one or more known values for one or more predictor attributes; and

detecting, during a traversal of a decision tree, a situation where a predictor attribute corresponding to a split has not been assigned a value in a query.

12. The method of claim 11, further comprising:

generating one or more statistics for deriving one or more non-leaf probabilities corresponding to one or more predictor values.

13. The method of claim 12, further comprising:

storing within one or more split nodes the one or more statistics for deriving non-leaf probabilities corresponding to the one or more predictor; and

aggregating the statistics to approximate a probability.

14. The method of claim 13, further comprising:

detecting when an aggregating method approximates the probability.

15. The method of claim 14, further comprising:

aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node is missing.

16. The method of claim 14, further comprising:

aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node is in a state that did not appear at least k times in the relevant training cases for the split node, k being an integer.

17. The method of claim 14, further comprising:

aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node generates a new value situation.

18. The method of claim 15, wherein the aggregating method includes a consistent look-ahead method for determining one or more nodes from which to gather one or more sets of statistics to be aggregated.

19. The method of claim 16, wherein the aggregating method includes a consistent look-ahead method for determining one or More nodes from which to gather one or more sets of statistics to be aggregated.

20. The method of claim 15, wherein the aggregating method collects one or more sets of statistics from all descendent nodes of a split node associated with a missing predictor value problem.

21. The method of claim 16, the aggregating method including a consistent look-ahead method for determining one or more nodes from which to gather one or more sets of statistics to be aggregated.

22. The method of claim 16, wherein the aggregating method collects one or more sets of statistics from all descendent nodes of a split node associated with an inadequate training data problem.

23. The method of claim 17, the aggregating method including a consistent look-ahead method for determining one or more nodes from which to gather one or more sets of statistics to be aggregated.

24. The method of claim 17, wherein the aggregating method collects one or more sets of statistics from all descendent nodes of a split node associated with a new value problem.

25. A computerize system for extracting predictions from a decision tree, comprising:

means for tracking one or more predictor values not occurring at least k times in the relevant training cases, k being an integer;

means for storing the plurality of predictor values that did not occur at least k times in the relevant training cases, k being an integer,

means for collecting, for one or more predictor attributes, a set of known values for the one or more predictor attributes; and

means for recognizing a predictor value corresponding to a split that has not been assigned a value in a query.

26. The system of claim 25, further comprising:

means for generating statistics for deriving one or more non-leaf probabilities corresponding to one or more predictor values.

27. The system of claim 26, further comprising:

means for storing statistics for deriving one or more non-leaf probabilities corresponding to the one or more predictor values; and

means for aggregating statistics to approximate a probability.

28. The system of claim 27, further comprising:

means for detecting when aggregating means approximate the probability.

29. The system of claim 28, further comprising:

means for aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node is missing.

30. The system of claim 28, further comprising:

means for aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node is in a state that did not appear at least k times in the relevant training cases for the split node, k being an integer.

31. The system of claim 28, further comprising:

means for aggregating statistics of at least a subset of descendant leaf nodes of a split node when a predictor value corresponding to the split node generates a new value problem.