Large scale machine learning systems and methods

• US 8,688,705 B1
• Filed: 01/28/2013
• Issued: 04/01/2014
• Est. Priority Date: 11/14/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R., Shazeer, Noam, Tong, Simon, Bem, Jeremy, Levenberg, Joshua L.
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US13/751,746
• Time in Patent Office: 428 Days
• Field of Search: 706/20, 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system for generating a model is provided. The system generates, or selects, candidate conditions and generates, or otherwise obtains, statistics regarding the candidate conditions. The system also forms rules based, at least in part, on the statistics and the candidate conditions and selectively adds the rules to the model.

Claims

1. A system comprising:

a plurality of computer nodes, one of the plurality of computer nodes being configured to;

store information for a plurality of instances;

receive information identifying a condition from a particular computer node of the plurality computer nodes;

analyze the condition and the plurality of instances to identify one or more instances, of the plurality of instances, that match the condition;

determine statistics for the condition based on the information for the one or more instances that match the condition;

send the statistics to the particular computer node,

the particular computer node generating a rule based on the statistics; and

receive the rule from the particular computer node.

2. The system of claim 1, where the one of the plurality of computer nodes is further configured to:

store information regarding the condition and each matching one of the one or more instances as a respective one or more condition-instance pairs; and

create a condition-instance list based on the one or more condition-instance pairs,

the condition-instance list being used to determine the statistics for the condition.

3. The system of claim 1, where the one of the plurality of computer nodes, when determining the statistics for the condition, is configured to:

generate a histogram based on the information for the one or more instances that match the condition; and

use the histogram to convey the statistics for the condition.

4. The system of claim 1, where the one of the plurality of computer nodes is further configured to:

determine a hash of the condition to form a hashed value; and

use the hashed value to identify the particular computer node.

5. The system of claim 1, where the one of the plurality of computer nodes is further configured to:

store a copy of a model that is also stored by one or more other ones of the plurality of computer nodes; and

add the rule to the stored copy of the model.

6. The system of claim 1, where the one of the plurality of computer nodes, when determining the statistics for the condition, is further configured to:

determine first and second derivatives of a log likelihood for one of the one or more instances that match the condition.

7. The system of claim 1, where the one of the plurality of computer nodes, when determining the statistics for the condition, is further configured to:

determine first and second derivatives of a probability of a label for one of the one or more instances that match the condition.

8. A method comprising:

storing, by one of a plurality of computer nodes, information for a plurality of instances;

receiving, by the one of the plurality of computer nodes, information identifying a condition from a particular computer node of the plurality computer nodes;

analyzing, by the one of the plurality of computer nodes, the condition and the plurality of instances to identify one or more instances, of the plurality of instances, that match the condition;

determining, by the one of the plurality of computer nodes, statistics for the condition based on the information for the one or more instances that match the condition;

sending, by the one of the plurality of computer nodes, the statistics to the particular computer node,

the particular computer node generating a rule based on the statistics; and

receiving, by the one of the plurality of computer nodes, the rule from the particular computer node.

9. The method of claim 8, further comprising:

storing information regarding the condition and each matching one of the one or more instances as a respective one or more condition-instance pairs; and

creating a condition-instance list based on the one or more condition-instance pairs,

the condition-instance list being used to determine the statistics for the condition.

10. The method of claim 8, where determining the statistics for the condition includes:

generating a histogram based on the information for the one or more instances that match the condition, and

using the histogram to convey the statistics for the condition.

11. The method of claim 8, further comprising:

determining a hash of the condition to form a hashed value; and

using the hashed value to identify the particular computer node.

12. The method of claim 8, further comprising:

storing a copy of a model that is also stored by one or more other ones of the plurality of computer nodes; and

adding the rule to the stored copy of the model.

13. The method of claim 8, where determining the statistics for the condition includes:

determining first and second derivatives of a log likelihood for one of the one or more instances that match the condition.

14. The method of claim 8, where determining the statistics for the condition includes:

determining first and second derivatives of a probability of a label for one of the one or more instances that match the condition.

15. A non-transitory computer-readable medium to store instructions, the instructions comprising:

one or more instructions that, when executed by one of a plurality of computer nodes, cause the one of the plurality of computer nodes to;

store information for a plurality of instances;

receive information identifying a condition from a particular computer node of the plurality computer nodes;

analyze the condition and the plurality of instances to identify one or more instances, of the plurality of instances, that match the condition;

determine statistics for the condition based on the information for the one or more instances that match the condition;

send the statistics to the particular computer node,

the particular computer node generating a rule based on the statistics; and

receive the rule from the particular computer node.

16. The computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions to;

store information regarding the condition and each matching one of the one or more instances as a respective one or more condition-instance pairs; and

create a condition-instance list based on the one or more condition-instance pairs,

the condition-instance list being used to determine the statistics for the condition.

17. The computer-readable medium of claim 15, where the one or more instructions to determine the statistics for the condition further include:

one or more instructions to;

generate a histogram based on the information for the one or more instances that match the condition; and

use the histogram to convey the statistics for the condition.

18. The computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions to;

determine a hash of the condition to form a hashed value; and

use the hashed value to identify the particular computer node.

19. The computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions to;

store a copy of a model that is also stored by one or more other ones of the plurality of computer nodes; and

add the rule to the stored copy of the model.

20. The computer-readable medium of claim 15, where the one or more instructions to determine the statistics for the condition further include:

one or more instructions to;

determine first and second derivatives for at least one of;

a log likelihood for one of the one or more instances that match the condition, or

a probability of a label for one of the one or more instances that match the condition.