Scaling machine learning using approximate counting

• US 8,606,730 B1
• Filed: 08/03/2012
• Issued: 12/10/2013
• 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): CHANG, LI WU
• Application Number:
  US13/566,289
• Time in Patent Office: 494 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 comprising:

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

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

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

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

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

identifying a value from the read values,

updating the value, and

replacing each of the read values with the updated value; and

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

2. The method of claim 1, further comprising:

storing the updated values into the respective memory locations.

3. The method of claim 1, where the operation is a write operation, the method, when performing the write operation, including:

determining a minimum count value of the read values;

incrementing the minimum count value; and

writing the updated values, associated with the read values and based on the incremented minimum count value, to the respective memory locations.

4. The method of claim 1, where the operation is a write operation, the method, when performing the write operation, including:

determining a mean count value of the read values or a median count value of the read values;

incrementing the mean count value or the median count value; and

writing the updated values, associated with the read values and based on the incremented mean count value or the incremented median count value, to the respective memory locations.

5. The method of claim 1, where

the value is a minimum value.

6. The method of claim 1, where

the value is a mean value or a median value,

the mean value or the median value being determined from the read values.

7. The method of claim 1, where, when using the updated values to make the prediction, the method further includes:

generating rules for a model based on the updated values.

8. One or more devices comprising:

one or more processors; and

one or more memories including a plurality of instructions that, when executed by the one or more processors, cause the one or more processors to;

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

subject a string, associated with the 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, the one or more processors, when performing the operation, being to;

identify a value from the read values,

update the value, and

replace each of the read values with the updated value; and

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

9. The one or more devices of claim 8, where the one or more processors are further to:

store the updated values into the respective memory locations.

10. The one or more devices of claim 8, where the operation is a write operation, and the one or more processors are further to:

determine a minimum count value of the read values;

increment the minimum count value; and

write the updated values, associated with the read values and based on the incremented minimum count value, to the respective memory locations.

11. The one or more devices of claim 8, where the operation is a write operation, and the one or more processors are further to:

determine a mean count value of the read values or a median count value of the read values;

increment the mean count value or the median count value; and

write the updated values, associated with the read values and based on the incremented mean count value or the incremented median count value, to the respective memory locations.

12. The one or more devices of claim 8, where

the value is a minimum value.

13. The one or more devices of claim 8, where

the value is a mean value or a median value,

the mean value or the median value being determined from the read values.

14. The one or more devices of claim 8, where, when using the updated values to make the prediction, the one or more processors are further to:

generate rules for a model based on the updated values.

15. A non-transitory computer-readable storage medium storing instructions, the instructions comprising:

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

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

subject a string, associated with the 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, the one or more instructions to perform the operation including one or more instructions which, when executed by the at least one processor, cause the at least one processor to;

identify a value from the read values,

update the value, and

replace each of the read values with the updated value; and

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

16. The medium of claim 15, further comprising:

one or more instructions to store the updated values into the respective memory locations.

17. The medium of claim 15, where the operation is a write operation, and the one or more instructions include:

one or more instructions to determine a minimum count value of the read values;

one or more instructions to increment the minimum count value; and

one or more instructions to write the updated values, associated with the read values and based on the incremented minimum count value, to the respective memory locations.

18. The medium of claim 15, where the operation is a write operation, and the one or more instructions include:

one or more instructions to determine a mean count value of the read values or a median count value of the read values;

one or more instructions to increment the mean count value or the median count value; and

one or more instructions to write the updated values, associated with the read values and based on the incremented mean count value or the incremented median count value, to the respective memory locations.

19. The medium of claim 15, where

the value is a minimum value.

20. The medium of claim 15, where

the value is a mean value or a median value,

the mean value or the median value being determined from the read values.