Approximate hashing functions for finding similar content

• US 7,831,531 B1
• Filed: 06/21/2007
• Issued: 11/09/2010
• Est. Priority Date: 06/22/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Covell, Michele
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/766,594
• Time in Patent Office: 1,237 Days
• Field of Search: 706/25
• US Class Current: 706/25
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

A method including training a plurality of learning systems, each learning system implementing a learning function and having an input and producing an output, initializing one or more data structures, and evaluating a target sample is described. Also described are methods that include initializing one or more data structures and evaluating a target sample for a best match.

Claims

1. A method comprising:

A) training a plurality of learning systems, each learning system implementing a learning function and having an input and producing an output where training includes;

identifying a training set including target output values associated therewith;

providing the training set to each learning system in a small number of plurality of cycles and adjusting parameters of the learning system to improve matching to the target output values;

adjusting the target output values based on the actual output provided by the respective learning system; and

continuing training the learning system; and

B) initializing one or more data structures including;

providing samples to each trained learning system;

combining outputs of the learning systems for each sample; and

mapping the combined outputs to one or more data structures, the combined outputs providing an indices to a respective sample in those data structures; and

C) evaluating, by one or more processors, a target sample including;

providing the target sample to each trained learning system;

combining the outputs of the trained learning systems;

locating matching samples in the one or more data structures using the combined outputs of the trained learning system for the target sample.

2. The method of claim 1, where the training set, samples and target sample are audio samples.

3. The method of claim 1, where the learning systems are neural networks.

4. The method of claim 1, where each learning system is seeded with a different seed.

5. The method of claim 1, where combining outputs includes concatenating outputs.

6. The method of claim 1, where the training steps of providing, adjusting, and continuing are repeated a plurality of times.

7. The method of claim 1, where the training step of identifying a training set includes identifying different training sets for at least two of the learning systems.

8. The method of claim 1, where the small number of cycles is substantially 10.

9. The method of claim 1, where adjusting the target outputs includes evaluating actual learning system outputs and adjusting the target output for at least one sample to reflect at least one actual output.

10. The method of claim 1, where initializing the data structure includes providing corpus samples to the learning systems to classify each sample in the corpus.

11. The method of claim 1, where initializing the data structure includes providing corpus sample to the learning systems and placing each sample in the data structure in accordance with the output provided by the learning systems.

12. The method of claim 1, where combining outputs includes selecting a subset of output values associated with one or more learning systems as representative of the combined output.

13. The method of claim 12, where combining outputs includes determining least correlated bits to form the subset.

14. The method of claim 12, where combining outputs includes selecting a second subset of output values associated with the one or more learning system as representative of the combined output and creating a second data structure where the combined bits from the second subset are an index to samples in the second data structure.

15. The method of claim 1, where evaluating a target sample includes selecting first and/or second subsets of output values as representative of the target sample.

16. A method comprising:

initializing a data structure including mapping samples that are to be included as entries in the data structure to locations in the data structure using a plurality of learning systems; and

evaluating, by one or more processors, a target sample for a best match to a sample in the data structure including using an index system created using the plurality of learning systems to locate a match in the data structure.

17. A method comprising:

initializing one or more data structures including mapping samples that are to be included as entries in the data structure to locations in the data structure using a plurality of learning systems, where initializing includes training each learning system using a training sequence and target output values, adjusting the target output values based on the actual output of the respective learning system, and continuing to train the respective learning system; and

evaluating, by one or more processors, a target sample for a best match to a sample in the data structure including providing the target sample to the plurality of learning systems, and using the output therefrom to determine a best match in the data structure.

18. A method comprising:

initializing a data structure including mapping samples that are to be included as entries in the data structure to locations in the data structure using a plurality of learning systems; and

evaluating, by one or more processors, a target sample for a best match to the samples in the data structure including using the learning systems to locate a match in the data structure without directly comparing the target sample to the data structure sample.

19. An apparatus comprising:

means for initializing a data structure including mapping samples that are to be included as entries in the data structure to locations in the data structure using a plurality of learning systems; and

means for evaluating, by one or more processors a target sample for a best match to the samples in the data structure including using the learning systems to locate a match in the data structure without directly comparing the target sample to the data structure sample.