Multistage learner for efficiently boosting large datasets

• US 9,418,343 B2
• Filed: 12/30/2013
• Issued: 08/16/2016
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chandra, Tushar Deepak, Shaked, Tal, Singer, Yoram, Ie, Tze Way Eugene, Redstone, Joshua
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Afolabi, Ola Olude
• Application Number:
  US14/142,977
• Publication Number:
  US 20150186795A1
• Time in Patent Office: 960 Days
• Field of Search: 706/46
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning

Abstract

Implementations of the disclosed subject matter provide methods and systems for using a multistage learner for efficiently boosting large datasets in a machine learning system. A method may include obtaining a first plurality of examples for a machine learning system and selecting a first point in time. Next, a second point in time occurring subsequent to the first point in time may be selected. The machine learning system may be trained using m of the first plurality of examples. Each of the m examples may include a feature initially occurring after the second point in time. In addition, the machine learning system may be trained using n of the first plurality of examples, and each of the n examples may include a feature initially occurring after the first point in time.

Claims

1. A computer-implemented method comprising:

receiving a first plurality of examples for training a machine learning system, each example having a respective plurality of features, and each example being received at a respective time;

obtaining data defining a first point in time;

performing a first training iteration by training the machine learning system only on examples having at least one feature initially occurring after the first point in time;

obtaining data defining a second point in time occurring subsequent to the first point in time;

performing a second training iteration by training the machine learning system only on examples having a feature initially occurring after the second point in time; and

performing a third training iteration by training the machine learning system on a second plurality of examples, wherein at least one example of the second plurality has a feature initially occurring after the first point in time, and wherein at least one of the second plurality does not have any features initially occurring after the first point in time.

2. The method of claim 1, wherein a total number of examples on which the machine learning system is trained during the second training iteration m is greater than a total number of examples on which the machine learning system is trained during the first training iteration n.

3. The method of claim 1, further comprising determining, for each of the examples having at least one feature initially occurring after the second point in time, that the example includes a feature initially occurring after the second point in time.

4. The method of claim 1, further comprising determining, for each of the examples having at least one feature initially occurring after the first point in time, that the example includes a feature initially occurring after the first point in time.

5. The method of claim 1, further comprising selecting the first point in time based on the time at which a first feature is first present in any example obtained to train the machine learning system.

6. The method of claim 1, further comprising selecting the first point in time based on the time at which a threshold number of features are first present in any example obtained to train the machine learning system.

7. The method of claim 1, further comprising selecting the first point in time based on the time at which a threshold number of examples having a first feature are obtained to train the machine learning system.

8. The method of claim 1, further comprising selecting the first and second points in time based upon the rate at which new features are obtained to train the machine learning system.

9. A system comprising:

one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising;

receiving a first plurality of examples for training a machine learning system, each example having a respective plurality of features, and each example being received at a respective time;

obtaining data defining a first point in time;

performing a first training iteration by training the machine learning system only on examples having at least one feature initially occurring after the first point in time;

obtaining data defining a second point in time occurring subsequent to the first point in time;

performing a second training iteration by training the machine learning system only on examples having a feature initially occurring after the second point in time; and

performing a third training iteration by training the machine learning system on a second plurality of examples, wherein at least one example of the second plurality has a feature initially occurring after the first point in time, and wherein at least one of the second plurality does not have any features initially occurring after the first point in time.

10. The system of claim 9, wherein a total number of examples on which the machine learning system is trained during the second training iteration m is greater than a total number of examples on which the machine learning system is trained during the first training iteration n.

11. The system of claim 9, the operations further comprising determining, for each of the examples having at least one feature initially occurring after the second point in time, that the example includes a feature initially occurring after the second point in time.

12. The system of claim 9, the operations further comprising determining, for each of the examples having at least one feature initially occurring after the first point in time, that the example includes a feature initially occurring after the first point in time.

13. The system of claim 9, wherein the operations further comprising selecting the first point in time based on the time at which a first feature is first present in any example obtained to train the machine learning system.

14. The system of claim 9, wherein the operations further comprising selecting the first point in time based on the time at which a threshold number of features are first present in any example obtained to train the machine learning system.

15. The system of claim 9, wherein the operations further comprising selecting the first point in time based on the time at which a threshold number of examples having a first feature are obtained to train the machine learning system.

16. The system of claim 9, wherein the operations further comprising selecting the first and second points in time based upon the rate at which new features are obtained to train the machine learning system.

17. One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a first plurality of examples for training a machine learning system, each example having a respective plurality of features, and each example being received at a respective time;

obtaining data defining a first point in time;

performing a first training iteration by training the machine learning system only on examples having at least one feature initially occurring after the first point in time;

obtaining data defining a second point in time occurring subsequent to the first point in time;

performing a second training iteration by training the machine learning system only on examples having a feature initially occurring after the second point in time; and

performing a third training iteration by training the machine learning system on a second plurality of examples, wherein at least one example of the second plurality has a feature initially occurring after the first point in time, and wherein at least one of the second plurality does not have any features initially occurring after the first point in time.