Scaling machine learning using approximate counting

• US 8,255,343 B1
• Filed: 08/09/2011
• Issued: 08/28/2012
• Est. Priority Date: 05/16/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tong, Simon, Shazeer, Noam
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US13/206,273
• Time in Patent Office: 385 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system may track statistics for a number of features using an approximate counting technique by: subjecting each feature to multiple, different hash functions to generate multiple, different hash values, where each of the hash values may identify a particular location in a memory, and storing statistics for each feature at the particular locations identified by the hash values. The system may generate rules for a model based on the tracked statistics.

Claims

1. A method performed by one or more of a plurality of computer devices, the method comprising:

identifying, by a first computer device of the plurality of computer devices, a feature set that includes at least a first feature and a second feature;

storing, by the first computer device and in a plurality of memory locations in a memory, values relating to the first feature;

subjecting, by the first computer device, a string, associated with the first feature, to multiple, different hash functions to generate multiple, different hash values;

identifying, by the first computer device, for each of the multiple, different hash values, a respective memory location, of the plurality of memory locations in the memory;

reading, by the first computer device, the values stored at the respective memory locations;

performing, by the first computer device, an operation on the read values from the respective memory locations to obtain updated values;

writing, by the first computer device, the updated values into the respective memory locations;

sending, by the first computer device, a request to a second computer device, of the plurality of computer devices, for information regarding the second feature;

receiving, by the first computer device, the information from the second computer device; and

using, by the first computer device, the updated values and the received information to make a prediction regarding particular data.

2. The method of claim 1, where the feature set includes a third feature, the method further comprising:

sending a request to a third computer device, of the plurality of computer devices, for information regarding the third feature;

receiving the information from the third computer device; and

using the updated values, the received information from the second computer device, and the received information from the third computer device to make a prediction regarding particular data.

3. The method of claim 1, where performing the operation on the read values includes:

identifying a minimum value from the read values,

updating the minimum value, and

replacing each of the read values with the updated minimum value.

4. The method of claim 1, where performing the operation on the read values includes:

determining a mean or median value from the read values,

updating the mean or median value, and

replacing each of the read values with the updated mean or median value.

5. The method of claim 1, further comprising:

determining a single value from the read values; and

replacing each of the read values with the single value.

6. The method of claim 1, where at least one of the first feature or the second feature includes a combination of multiple features.

7. The method of claim 1, where using the updated values and the received information to make the prediction includes generating rules for a model based on the updated values and the received information.

8. A system comprising:

a computer device to;

identify a feature set that includes at least a first feature and a second feature;

store, in a plurality of memory locations in a memory, values relating to the first feature;

subject a string, associated with the first feature, to multiple, different hash functions to generate multiple, different hash values;

identify, for each of the multiple, different hash values, a respective memory location, of the plurality of memory locations in the memory;

read the values stored at the respective memory locations;

perform an operation on the read values from the respective memory locations to obtain updated values;

write the updated values into the respective memory locations;

send a request to a second computer device for information regarding the second feature;

receive the information from the second computer device, and

use the updated values and the received information to make a prediction regarding particular data.

9. The system of claim 8, where the particular data includes particular e-mail data, and

where using the updated values and the received information to make a prediction regarding particular data includes using the updated values and the received information to predict whether the particular e-mail data includes spam.

10. The system of claim 8, where the particular data includes particular advertisement data, and

where using the updated values and the received information to make a prediction regarding particular data includes using the updated values and the received information to predict whether the particular advertisement data will be selected by a user.

11. The system of claim 8, where the feature set includes a third feature and the computer device is further to:

send a request to a third computer device for information regarding the third feature;

receive the information from the third computer device; and

use the updated values, the received information from the second computer device, and the received information from the third computer device to make a prediction regarding particular data.

12. The system of claim 8, where the computer device is further to:

determine a single value from the read values; and

replace each of the read values with the single value.

13. The system of claim 8, where at least one of the first feature or the second feature includes a combination of multiple features.

14. The system of claim 8, where, when using the updated values and the received information to make the prediction, the computer device is further to:

generate rules for a model based on the updated values and the received information.

15. A non-transitory computer-readable medium comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to identify a feature set that includes at least a first feature and a second feature;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to store, in a plurality of memory locations in a memory, values relating to the first feature;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to subject a string, associated with the first feature, to multiple, different hash functions to generate multiple, different hash values;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to identify, for each of the multiple, different hash values, a respective memory location, of the plurality of memory locations in the memory;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to read the values stored at the respective memory locations;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to perform an operation on the read values from the respective memory locations to obtain updated values;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to write the updated values into the respective memory locations;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to send a request to a computer device for information regarding the second feature;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to receive the information from the computer device, and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to use the updated values and the received information to make a prediction regarding particular data.

16. The non-transitory computer-readable medium of claim 15, where the feature set includes a third feature, the non-transitory computer-readable medium further comprising:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to send a request to another computer device for information regarding the third feature;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to receive the information from the other computer device; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to use the updated values, the received information from the computer device, and the received information from the other computer device to make a prediction regarding particular data.

17. The non-transitory computer-readable medium of claim 15, where the one or more instructions to cause the at least one processor to perform an operation on the read values includes:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to identify a minimum value from the read values;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to update the minimum value; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to replace each of the read values with the updated minimum value.

18. The non-transitory computer-readable medium of claim 15, where the one or more instructions to cause the at least one processor to perform an operation on the read values includes:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine a mean or median value from the read values;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to update the mean or median value; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to replace each of the read values with the updated mean or median value.

19. The non-transitory computer-readable medium of claim 15, where at least one of the first feature or the second feature includes a combination of multiple features.

20. The non-transitory computer-readable medium of claim 15, where the one or more instructions to cause the at least one processor to use the updated values and the received information to make the prediction includes:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to generate rules for a model based on the updated values and the received information.