Predictive model training management

• US 8,489,632 B1
• Filed: 06/28/2011
• Issued: 07/16/2013
• Est. Priority Date: 06/28/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Breckenridge, Jordan M., Green, Travis H. K., Lin, Wei-Hao, Mann, Gideon S.
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US13/171,423
• Time in Patent Office: 749 Days
• US Class Current: 707/778
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 18/25 Fusion techniques
• CPC Class Codes: G06V 30/2528 Combination of methods, e.g. classifiers, working on the same input data

Abstract

Methods, systems, and apparatus, including computer programs encoded on one or more computer storage devices, for receiving training data for predictive modeling and executing multiple processes simultaneously to generate multiple trained predictive models using the training data and training functions. After executing the processes for an initial runtime, a convergence status of each process is determined that indicates a likelihood that the training function being executed will converge on the training data. Based on the determination, training functions are identified that are not likely to converge and processes that are executing these training functions are terminated. After an ultimate runtime has expired, processes that are still executing training functions that have not yet converged are terminated. An effectiveness score is generated for each of the trained predictive models that were successfully generated and a trained predictive model is selected based on the effectiveness scores.

Claims

1. A computer-implemented method comprising:

receiving training data for predictive modeling;

setting an ultimate time by which each of a plurality of processes executing training functions to generate respective trained predictive models is to be completed;

executing the plurality of processes simultaneously in parallel to generate the trained predictive models using the training data;

determining, after executing each of the plurality of processes for an initial time that is earlier than the ultimate time, a respective convergence status of each of the plurality of processes, wherein the convergence status indicates a likelihood that the process will converge, and based on the determination, identifying one or more processes that are not likely to converge, terminating processes that are not likely to converge, and allowing the remaining processes to continue executing;

after the ultimate time has been reached, terminating processes that have not yet converged and generating an effectiveness score for each of a plurality of trained predictive models that were generated by the remaining processes, wherein the effectiveness score for a particular trained predictive model represents an estimation of the effectiveness of the particular trained predictive model;

storing the plurality of trained predictive models in a repository of trained predictive models;

receiving input data and a prediction request;

selecting, for use in servicing the prediction request, a first trained predictive model from among the plurality of trained predictive models based on their respective effectiveness scores;

providing the input data to the first trained predictive model; and

receiving a predictive output from the first trained predictive model.

2. The method of claim 1, wherein the training data is received from a client computing system over a network, the method further comprising:

providing the client computing system access to the first trained predictive model in the repository of trained predictive models over the network.

3. The method of claim 1, wherein determining the respective convergence status of each of the plurality of processes comprises:

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

determining that the process is unlikely to converge if the difference exceeds the threshold value, and otherwise, determining that the process is likely to converge if the difference is less than the threshold value.

4. The method of claim 3, wherein the difference is a percentage change between two iterations and the predetermined threshold value is expressed as a percentage change.

5. The method of claim 3, wherein the difference is an absolute numerical value change between two iterations and the predetermined threshold value is expressed as a numerical value.

6. The method of claim 1, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the method further comprises:

for each process that has not yet converged, estimating a time to convergence and allowing the process to continue executing for the estimated time.

7. The method of claim 1, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the method further comprises:

for each process that has not yet converged,

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

terminating the process if the difference exceeds the threshold value, and otherwise, allowing the process to continues executing.

8. The method of claim 1, wherein generating an effectiveness score for each of the plurality of trained predictive models comprises:

partitioning the training data into k partitions, performing k-fold cross-validation and generating a cross-validation score for each of the plurality of trained predictive models that indicates the effectiveness of the trained predictive model, where k is an integer greater than 1.

9. The method of claim 1, further comprising:

obtaining one or more updateable trained predictive models from a predictive model repository, wherein the received training data is different than initial training data that was used with one or more training functions to train the one or more updateable trained predictive models; and

wherein executing the plurality of processes simultaneously in parallel to generate the plurality of trained predictive models using the training data and a plurality of training functions includes executing one or more processes to generate one or more retrained predictive models using the training data, the one or more updateable trained predictive models and the one or more training functions used to train said updateable trained predictive models.

10. A computer-implemented system comprising:

one or more computers;

one or more data storage devices coupled to the one or more computers, storing;

a repository of training functions, and

instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving training data for predictive modeling;

setting an ultimate time by which each of a plurality of processes executing training functions obtained from the repository of training functions to generate respective trained predictive models is to be completed;

executing the plurality of processes simultaneously in parallel to generate the trained predictive models using the training data;

determining, after executing each of the plurality of processes for an initial time that is earlier than the ultimate time, a respective convergence status of each of the plurality of processes, wherein the convergence status indicates a likelihood that the process will converge, and based on the determination, identifying one or more processes that are not likely to converge, terminating processes that are not likely to converge, and allowing the remaining processes to continue executing;

after the ultimate time has been reached, terminating processes that have not yet converged, and generating an effectiveness score for each of a plurality of trained predictive models that were generated by the remaining processes, wherein the effectiveness score for a particular trained predictive model represents an estimation of the effectiveness of the particular trained predictive model;

storing the plurality of trained predictive models in a repository of trained predictive models;

receiving input data and a prediction request;

selecting, for use in servicing the prediction request, a first trained predictive model from among the plurality of trained predictive models based on their respective effectiveness scores;

providing the input data to the first trained predictive model; and

receiving a predictive output from the first trained predictive model.

11. The system of claim 10, wherein the training data is received from the client computing system over a network, the operations further comprising:

providing the client computing system access to the first trained predictive model in the repository of trained predictive models over the network.

12. The system of claim 10, wherein determining the respective a convergence status of each of the plurality of processes comprises:

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

determining that the process is unlikely to converge if the difference exceeds the threshold value, and otherwise, determining that the process is likely to converge if the difference is less than the threshold value.

13. The system of claim 12, wherein the difference is a percentage change between two iterations and the predetermined threshold value is expressed as a percentage change.

14. The system of claim 12, wherein the difference is an absolute numerical value change between two iterations and the predetermined threshold value is expressed as a numerical value.

15. The system of claim 10, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the operations further comprises:

for each process that has not yet converged, estimating a time to convergence and allowing the process to continue executing for the estimated time.

16. The system of claim 10, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the operations further comprise:

for each process that has not yet converged,

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

terminating the process if the difference exceeds the threshold value, and otherwise allowing the process to continue executing.

17. The system of claim 10, wherein generating an effectiveness score for each of the plurality of trained predictive models comprises:

partitioning the training data into k partitions, performing k-fold cross-validation and generating a cross-validation score for each of the plurality of trained predictive models that indicates the effectiveness of the trained predictive model, where k is an integer greater than 1.

18. The system of claim 10, the operations further comprising:

obtaining one or more updateable trained predictive models from a predictive model repository, wherein the received training data is different than initial training data that was used with one or more training functions to train the one or more updateable trained predictive models; and

wherein executing the plurality of processes simultaneously in parallel to generate the plurality of trained predictive models using the training data and a plurality of training functions includes executing one or more processes to generate one or more retrained predictive models using the training data, the one or more updateable trained predictive models and the one or more training functions used to train said updateable trained predictive models.

19. A computer-readable storage device encoded with a computer program product, the computer program product comprising instructions that when executed on one or more computers cause the one or more computers to perform operations implementing a predictive model training system, the operations comprising:

receiving training data for predictive modeling;

setting an ultimate time by which each of a plurality of processes executing training functions to generate respective trained predictive models is to be completed;

executing the plurality of processes simultaneously in parallel to generate the trained predictive models using the training data;

determining, after executing each of the plurality of processes for an initial time that is earlier than the ultimate time, a respective convergence status of each of the plurality of processes, wherein the convergence status indicates a likelihood that the process will converge, and based on the determination identifying one or more processes that are not likely to converge, terminating processes that are not likely to converge, and allowing the remaining processes to continue executing;

after the ultimate time has been reached, terminating processes that have not yet converged, and generating an effectiveness score for each of a plurality of trained predictive models that were generated by the remaining processes, wherein the effectiveness score for a particular trained predictive model represents an estimation of the effectiveness of the particular trained predictive model;

storing the plurality of trained predictive models in a repository of trained predictive models;

receiving input data and a prediction request;

selecting, for use in servicing the prediction request, a first trained predictive model from among the plurality of trained predictive models based on their respective effectiveness scores;

providing the input data to the first trained predictive model; and

receiving a predictive output from the first trained predictive model.

20. The computer-readable storage device of claim 19, wherein the training data is received from the client computing system over a network, the operations further comprising:

providing the client computing system access to the first trained predictive model in the repository of trained predictive models over the network.

21. The computer-readable storage device of claim 19, wherein determining the respective convergence status of each of the plurality of processes comprises:

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

determining that the process is unlikely to converge if the difference exceeds the threshold value, and otherwise, determining that the process is likely to converge if the difference is less than the threshold value.

22. The computer-readable storage device of claim 21, wherein the difference is a percentage change between two iterations and the predetermined threshold value is expressed as a percentage change.

23. The computer-readable storage device of claim 21, wherein the difference is an absolute numerical value change between two iterations and the predetermined threshold value is expressed as a numerical value.

24. The computer-readable storage device of claim 19, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the operations further comprises:

for each process that has not yet converged, estimating a time to convergence and allowing the process to continue executing for the estimated time.

25. The computer-readable storage device of claim 19, wherein after the ultimate time has been reached but before terminating processes that have not yet converged, the operations further comprise:

for each process that has not yet converged,

determining a difference between two or more training iterations and comparing the difference to a predetermined threshold value; and

terminating the process if the difference exceeds the threshold value, and otherwise, allowing the process to continue executing.

26. The computer-readable storage device of claim 19, wherein generating an effectiveness score for each of the plurality of trained predictive models comprises:

partitioning the training data into k partitions, performing k-fold cross-validation and generating a cross-validation score for each of the plurality of trained predictive models that indicates the effectiveness of the trained predictive model, where k is an integer greater than 1.

27. The computer-readable storage device of claim 19, the operations further comprising:

obtaining one or more updateable trained predictive models from a predictive model repository, wherein the received training data is different than initial training data that was used with one or more training functions to train the one or more updateable trained predictive models; and

wherein executing the plurality of processes simultaneously in parallel to generate the plurality of trained predictive models using the training data and a plurality of training functions includes executing one or more processes to generate one or more retrained predictive models using the training data, the one or more updateable trained predictive models and the one or more training functions used to train said updateable trained predictive models.