Using specialized workers to improve performance in machine learning

• US 9,269,057 B1
• Filed: 12/11/2013
• Issued: 02/23/2016
• Est. Priority Date: 12/11/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chandra, Tushar Deepak, Shaked, Tal, Ie, Tze Way Eugene, Singer, Yoram, Redstone, Joshua
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Fink, Thomas
• Application Number:
  US14/102,718
• Time in Patent Office: 804 Days
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Systems and techniques are disclosed for generating weighted machine learned models using multi-shard combiners. A learner in a machine learning system may receive labeled positive and negative examples and workers within the learner may be configured to receive either positive or negative examples. A positive and negative statistic may be calculated for a given feature and may either be applied separately in a model or may be combined to generate an overall statistic.

Claims

1. A method implemented by a computerized machine learning system, said method comprising:

receiving, at the computerized machine learning system, a plurality of examples, separable by feature into at least two classes, for distribution to a plurality of workers in a mapreduce process, each worker only receiving examples associated with a first class or a second class, wherein the first class is a positive class and the second class is a negative class, and wherein a worker is selected from the group consisting of a mapper and a reducer;

determining whether each example is either associated with the first class or associated with the second class;

distributing an example associated with the first class to a first worker of the plurality of workers in the machine learning system, the first worker receiving only examples associated with the first class; and

distributing an example associated with the second class to a second worker of the plurality of workers in the machine learning system, the second worker receiving only examples associated with the second class.

2. The method of claim 1, wherein the plurality of examples are from a learned training dataset.

3. The method of claim 1, wherein determining whether each example is either associated with the first class or the second class is conducted by an example sorter.

4. The method of claim 1, further comprising blocking examples associated with the second class from being distributed to a worker receiving only examples associated with the first class.

5. The method of claim 1, further comprising blocking examples associated with the first class from being distributed to a worker receiving only examples associated with the second class.

6. The method of claim 1, further comprising generating an updated weight based on an original weight and a weight function, wherein the weight function contains inputs selected from the group consisting of a positive statistic, a negative statistic, and a class specific statistic.

7. The method of claim 6, wherein the positive statistic is generated based on one or more workers that receives positive examples and wherein the negative statistic is generated based on one or more workers that receives negative examples.

8. The method of claim 1, further comprising:

determining that a threshold number of examples from the plurality of examples has been distributed; and

removing one or more workers from the plurality of workers, based on the determination.

9. The method of claim 8, wherein removing one or more workers form the plurality of workers further comprises:

removing a first number of workers associated with examples associated with the first class based on a number of examples associated with the first class being distributed; and

removing a second number of workers associated with examples associated with the second class based on a number of examples associated with the second class being distributed.

10. The method of claim 9, wherein the first number is based upon the number of distributed examples associated with the first class.

11. The method of claim 9, wherein the second number is based upon the number of distributed examples associated with the second class.

12. The method of claim 1, further comprising:

determining that a frequency of examples received is below a threshold frequency; and

removing one or more workers from the plurality of workers, based on the determination.

13. A machine learning system comprising:

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

receiving a plurality of examples, separable by feature into at least two classes, for distribution to a plurality of workers in a mapreduce process, each worker only receiving examples associated with a first class or a second class, wherein the first class is a positive class and the second class is a negative class, and wherein a worker is selected from the group consisting of a mapper and a reducer;

determining whether each example is either associated with the first class or associated with the second class;

distributing an example associated with the first class to a first worker of the plurality of workers in the machine learning system, the first worker receiving only examples associated with the first class; and

distributing an example associated with the second class to a second worker of the plurality of workers in the machine learning system, the second worker receiving only examples associated with the second class.

14. The system of claim 13, wherein the plurality of examples are from a learned training dataset.

15. The system of claim 13, wherein the operations further comprise determining whether each example is either associated with the first class or the second class is conducted by an example sorter.

16. The system of claim 13, wherein the operations further comprise blocking examples associated with the second class from being distributed to a worker receiving only examples associated with the first class.

17. The system of claim 13, wherein the operations further comprise blocking examples associated with the first class from being distributed to a worker receiving only examples associated with the second class.

18. The system of claim 13, the operations further comprise generating an updated weight based on an original weight and a weight function, wherein the weight function contains inputs selected from the group consisting of a statistic associated with the first class and a statistic associated with the second class.

19. The system of claim 18, wherein the statistic associated with the first class is generated based on one or more workers that receives examples associated with the first class and wherein the statistic associated with the second class is generated based on one or more workers that receives examples associated with the second class.

20. The system of claim 13, the operations further comprise blocking:

determining that a threshold number of examples from the plurality of examples has been distributed; and

removing one or more workers from the plurality of workers, based on the determination.

21. The system of claim 20, wherein removing one or more workers form the plurality of workers further comprises:

removing a first number of workers associated with examples associated with the first class based on a number of examples associated with the first class being distributed; and

removing a second number of workers associated with examples associated with the second class based on a number of examples associated with the second class being distributed.

22. The system of claim 21, wherein the first number is based upon the number of distributed examples associated with the first class.

23. The system of claim 21, wherein the second number is based upon the number of distributed examples associated with the second class.

24. The system of claim 13, the operations further comprise blocking:

determining that a frequency of examples received is below a threshold frequency; and

removing one or more workers from the plurality of workers, based on the determination.

25. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving, at a computerized machine learning system, a plurality of examples, separable by feature into at least two classes, for distribution to a plurality of workers in a mapreduce process, each worker only receiving examples associated with a first class or a second class, wherein the first class is a positive class and the second class is a negative class, and wherein a worker is selected from the group consisting of a mapper and a reducer;

determining whether each example is either associated with the first class or associated with the second class;

distributing an example associated with the first class to a first worker of the plurality of workers in the machine learning system, the first worker receiving only examples associated with the first class; and

distributing an example associated with the second class to a second worker of the plurality of workers in the machine learning system, the second worker receiving only examples associated with the second class.

26. The computer program product of claim 25, wherein the plurality of examples are from a learned training dataset.

27. The computer program product of claim 25, wherein the operations further comprise determining whether each example is either associated with the first class or the second class is conducted by an example sorter.

28. The computer program product of claim 25, wherein the operations further comprise blocking examples associated with the second class from being distributed to a worker receiving only examples associated with the first class.

29. The computer program product of claim 25, wherein the operations further comprising blocking examples associated with the first class from being distributed to a worker receiving only examples associated with the second class.

30. The computer program product of claim 25, wherein the operations further comprise generating an updated weight based on an original weight and a weight function, wherein the weight function contains inputs selected from the group consisting of a statistic associated with the first class and a statistic associated with the second class.

31. The computer program product of claim 30, wherein the statistic associated with the first class is generated based on one or more workers that receives examples associated with the first class and wherein the statistic associated with the second class is generated based on one or more workers that receives examples associated with the second class.

32. The computer program product of claim 25, wherein the operations further comprise:

determining that a threshold number of examples from the plurality of examples has been distributed; and

removing one or more workers from the plurality of workers, based on the determination.

33. The computer program product of claim 32, wherein removing one or more workers form the plurality of workers further comprises:

removing a first number of workers associated with examples associated with the first class based on a number of examples associated with the first class being distributed; and

removing a second number of workers associated with examples associated with the second class based on a number of examples associated with the second class being distributed.

34. The computer program product of claim 33, wherein the first number is based upon the number of distributed examples associated with the first class.

35. The computer program product of claim 33, wherein the second number is based upon the number of distributed examples associated with the second class.

36. The computer program product of claim 25, wherein the operations further comprise:

determining that a frequency of examples received is below a threshold frequency; and

removing one or more workers from the plurality of workers, based on the determination.