Optimized decision tree based models

• US 10,339,465 B2
• Filed: 08/19/2014
• Issued: 07/02/2019
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Steele, Robert Matthias, Agarwal, Tarun, Dirac, Leo Parker, Qian, Jun
• Primary Examiner(s): Cassity, Robert A
• Assistant Examiner(s): Coughlan, Peter D
• Application Number:
  US14/463,434
• Publication Number:
  US 20150379426A1
• Time in Patent Office: 1,778 Days
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

During a training phase of a machine learning model, representations of at least some nodes of a decision tree are generated and stored on persistent storage in depth-first order. A respective predictive utility metric (PUM) value is determined for one or more nodes, indicating expected contributions of the nodes to a prediction of the model. A particular node is selected for removal from the tree based at least partly on its PUM value. A modified version of the tree, with the particular node removed, is stored for obtaining a prediction.

Claims

1. A system, comprising:

one or more computing devices configured to;

identify one or more run-time optimization goals for a decision-tree based machine learning model to be trained using a data set, including at least a goal for a memory footprint of an execution of the machine learning model subsequent to a training phase of the machine learning model;

store, at one or more persistent storage devices during a tree-construction pass of the training phase, respective representations of a plurality of nodes of a particular decision tree generated using at least a portion of the data set, wherein the representations of nodes of the particular decision tree are streamed to and stored in the persistent storage devices in a depth-first order of the particular decision tree as the nodes are being generated;

determine, for one or more nodes of the particular decision tree during the tree-construction pass, a respective value of a predictive utility metric (PUM), wherein a particular PUM value associated with a particular node of the one or more nodes is a measure of an expected contribution of the particular node to a prediction generated using the machine learning model;

generate, during a tree-pruning pass of the training phase, a modified version of the particular decision tree, wherein to generate the modified version, at least the particular node is removed from the particular decision tree, wherein the particular node is selected for removal based at least in part on the one or more run-time optimization goals for the execution of the machine learning model subsequent to the training phase of the machine learning model and based at least in part on the particular PUM value;

store a representation of the modified version of the particular decision tree; and

subsequent to the training phase, execute the machine learning model using at least the modified version of the particular decision tree to obtain a particular prediction.

2. The system as recited in claim 1, wherein the PUM comprises one or more of:

(a) an indication of a Gini impurity, (b) an information gain metric, or (c) an entropy metric.

3. The system as recited in claim 1, wherein the one or more run-time optimization goals include one or more of:

(a) a prediction time goal, (b) a processor utilization goal, or (c) a budget goal.

4. The system as recited in claim 1, wherein the one or more computing devices are further configured to:

generate a representation of a distribution of values of the PUM among the one or more nodes; and

select the particular node for removal based at least in part on the distribution.

5. The system as recited in claim 1, wherein the machine learning model comprises one or more of:

(a) a Random Forest model, (b) a classification and regression tree (CART) model, or (c) an adaptive boosting model.

6. A method, comprising:

performing, by one or more computing devices;

storing, at one or more persistent storage devices during a tree-construction pass of a training phase of a machine learning model, respective representations of a plurality of nodes of a particular decision tree generated in the tree-construction pass, wherein the representations of nodes of the particular decision tree are streamed to and stored in the persistent storage devices in a depth-first order of the particular decision tree as the nodes are being generated;

determining, for one or more nodes of the particular decision tree, a respective value of a predictive utility metric (PUM), wherein a particular PUM value associated with a particular node of the one or more nodes is a measure of an expected contribution of the particular node to a prediction generated using the machine learning model;

generating, during a tree-pruning pass of the training phase, a modified version of the particular decision tree, wherein said generating comprises removing at least the particular node from the particular decision tree, wherein the particular node is selected for removal based at least in part on the particular PUM value and one or more run-time optimization goals for execution of the machine learning model subsequent to a training phase of the machine learning model; and

executing the machine learning model using at least the modified version of the particular decision tree to obtain a particular prediction.

7. The method as recited in claim 6, wherein the one or more run-time optimization goals include one or more of:

(a) a memory-footprint goal (b) a prediction time goal, (c) a processor utilization goal, or (d) a budget goal.

8. The method as recited in claim 6, wherein the PUM comprises one or more of:

(a) an indication of a Gini impurity, (b) an information gain metric, or (c) an entropy metric.

9. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

determining a distribution of values of the PUM among the one or more nodes; and

selecting the particular node for removal based at least in part on the distribution.

10. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

accumulating, during the tree-pruning pass, values of the PUM for a plurality of nodes of the particular decision tree in a top-down traversal of the particular decision tree; and

selecting the particular node for removal based at least in part on a result of said accumulating.

11. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

examining, during the tree-pruning pass, values of the PUM for a plurality of nodes of the particular decision tree in a bottom-up traversal of the particular decision tree; and

selecting the particular node for removal based at least in part on a result of said examining.

12. The method as recited in claim 6, wherein the machine learning model comprises one or more of:

(a) a Random Forest model, (b) a classification and regression tree (CART) model, or (c) an adaptive boosting model.

13. The method as recited in claim 6, wherein the machine learning model is configured to utilize a plurality of decision trees including the particular decision tree, wherein the particular decision tree is generated at a particular thread of execution of a plurality of threads of execution of a machine learning service, further comprising performing, by the one or more computing devices:

generating a second decision tree of the plurality of decision trees at a different thread of execution of the plurality of threads of execution.

14. The method as recited in claim 6, wherein the machine learning model is configured to utilize a plurality of decision trees including the particular decision tree, wherein the modified version of the particular decision tree is generated at a particular thread of execution of a plurality of threads of execution of a machine learning service, further comprising performing, by the one or more computing devices:

generating a modified version of a second decision tree of the plurality of decision trees at a different thread of execution of the plurality of threads of execution.

15. The method as recited in claim 6, wherein the machine learning model is configured to utilize a plurality of decision trees including the particular decision tree, wherein the particular prediction is obtained at a particular thread of execution of a plurality of threads of execution of a machine learning service, further comprising:

obtaining a second prediction using a modified version of a second decision tree of the plurality of decision trees at a different thread of execution of the plurality of threads of execution.

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

store, at one or more persistent storage devices during a first tree-construction period of one or more tree-construction periods of a training phase of a machine learning model, respective representations of a plurality of nodes of a particular decision tree generated in the tree-construction pass, wherein the representations of nodes of the particular decision tree are streamed to and stored in the persistent storage devices in a depth-first order of the particular decision tree as the nodes are being generated;

determine, for one or more nodes of the particular decision tree, a respective value of a predictive utility metric (PUM), wherein a particular PUM value associated with a particular node of the one or more nodes is a measure of an expected contribution of the particular node to a prediction generated using the machine learning model;

select, during a first tree-pruning period of one or more tree-pruning periods of the training phase, the particular node for removal from the particular decision tree based at least in part on the particular PUM value and one or more run-time optimization goals for an execution of the machine learning model subsequent to a training phase of the machine learning model; and

store a modified version of the particular decision tree, wherein the modified version excludes the particular node.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the one or more run-time optimization goals include one or more of:

(a) a memory-footprint goal (b) a prediction time goal, (c) a processor utilization goal, or (d) a budget goal.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the particular node is selected for removal based at least in part on one or more goals specified by a client on whose behalf the machine learning model is created.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the instructions when executed at the one or more processors:

store a representation of a distribution of values of the PUM among the one or more nodes; and

select the particular node for removal based at least in part on the distribution.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the plurality of nodes of the particular decision tree is generated in response to an invocation of a programmatic interface of a machine learning service implemented at a provider network.

21. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the one or more tree-construction periods comprise a second tree-construction period performed after the first tree-pruning period, wherein the one or more tree-pruning periods comprise a second tree-pruning period performed after the second tree-construction period, and wherein the instructions when executed on the one or more processors:

store, during the second tree-construction period, a second node of the particular decision tree; and

determine, during the second tree-pruning period, whether to remove the second node from the particular decision tree based at least in part on a PUM value associated with the second node.