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.
Please help me write a proper abstract based on the patent claims. CLAIM: 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, in a depth-first order at one or more persistent storage devices during a tree-construction pass of the training phase, respective representations of a plurality of nodes generated for a particular decision tree using at least a portion of the data set; 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 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, in a depth-first order 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 generated for a particular decision tree; 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 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 particular node is selected for removal based at least in part on one or more run-time optimization goals for an execution of the model, including 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, in a depth-first order 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 generated for a particular decision tree; 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 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 particular node is selected for removal based at least in part on one or more run-time optimization goals for an execution of the machine learning model, including 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.