Source: http://www.google.com/patents/US8065248?dq=patent:6161142
Timestamp: 2017-03-30 01:37:57
Document Index: 77443901

Matched Legal Cases: ['§119', 'Application No. 60', 'Application No. 60', 'art 1', 'art 2', 'Application No. 200680051559', 'Application No. 08', 'Application No. 06838486', 'Application No. 06838488', 'art 1', 'art 2']

Patent US8065248 - Approximate hashing functions for finding similar content - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA 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...http://www.google.com/patents/US8065248?utm_source=gb-gplus-sharePatent US8065248 - Approximate hashing functions for finding similar contentAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8065248 B1Publication typeGrantApplication numberUS 12/909,484Publication dateNov 22, 2011Filing dateOct 21, 2010Priority dateJun 22, 2006Fee statusPaidAlso published asUS7831531, US8498951, US8504495Publication number12909484, 909484, US 8065248 B1, US 8065248B1, US-B1-8065248, US8065248 B1, US8065248B1InventorsShumeet Baluja, Michele CovellOriginal AssigneeGoogle Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (48), Non-Patent Citations (59), Referenced by (8), Classifications (5), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetApproximate hashing functions for finding similar content
US 8065248 B1Abstract
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.
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 indices to respective samples in those data structures; and
C) evaluating a target sample including:
providing the target sample to each trained learning system;
combining the outputs of the trained learning systems; and
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 system of claim 1, wherein the samples and target sample are audio samples.
3. The system of claim 1, wherein the learning systems are neural networks.
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 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.
5. The system of claim 4, wherein the samples and target sample are audio samples.
6. The system of claim 4, wherein the learning systems are neural networks.
evaluating 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.
8. The method of claim 7, wherein the samples and target sample are audio samples.
9. The method of claim 7, wherein the learning systems are neural networks.
10. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
11. The computer storage medium of claim 10, wherein the samples and target sample are audio samples.
12. The computer storage medium of claim 10, wherein the learning systems are neural networks.
13. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
14. The computer storage medium of claim 13, wherein the samples and target sample are audio samples.
15. The computer storage medium of claim 13, wherein the learning systems are neural networks.
16. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
17. The computer storage medium of claim 16, wherein the samples and target sample are audio samples.
18. The computer storage medium of claim 16, wherein the learning systems are neural networks.
providing, by a client machine, a target sample to one or more servers for evaluation as a best match to a sample in a data structure stored by the one or more servers, wherein evaluation as a best match comprises using an index system created using a plurality of learning systems to locate a match in the data structure, wherein samples that are included as entries in the data structure are mapped to locations in the data structure using the plurality of learning systems; and
receiving, by the client machine, data that identifies the best match from the one or more servers.
20. The method of claim 19, wherein the samples and target sample are audio samples.
21. The method of claim 19, wherein the learning systems are neural networks.
providing, by a client machine, a target sample to one or more servers for evaluation as a best match to samples in a data structure stored by the one or more servers, wherein evaluation as a best match comprises using a plurality of learning systems to locate a match in the data structure without directly comparing the target sample to the data structure sample, wherein samples that are included as entries in the data structure are mapped to locations in the data structure using the plurality of learning systems.
23. The method of claim 22, wherein the samples and target sample are audio samples.
24. The method of claim 22, wherein the learning systems are neural networks.
This application is a continuation (and claims the benefit of priority under 35 USC 120) of U.S. application Ser. No. 11/766,594, filed Jun. 21, 2007, now U.S. Pat. No. 7,831,531, and claims the benefit under 35 U.S.C. §119 of the filing dates of U.S. Provisional Application No. 60/818,182, filed Jun. 30, 2006, and U.S. Provisional Application No. 60/816,197, filed Jun. 22, 2006. The disclosures of the prior applications are considered part of (and are incorporated by reference in) the disclosure of this application.
The advent of highly distributable, high volume data storage has allowed for the storage of vast amounts of information on a variety of topics and in a variety of forms such as text, images, music, and videos.
The problem of efficiently finding similar items in a large corpus of high-dimensional data points arises in many real-world tasks, such as music, image, and video retrieval. Beyond the scaling difficulties that arise with lookups in large data sets, the complexity in these domains is exacerbated by an imprecise definition of similarity.
There exists a need to retrieve similar audio, image and video data from extensive corpuses of data. The large number of elements in the corpuses, the high dimensionality of the points, and the imprecise nature of “similar” make this task challenging in real world systems.
In one aspect, a method is described that includes 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. Training a plurality of learning systems 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. Initializing one or more data structures includes 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. Evaluating a target sample includes providing the target sample to each trained learning system, combining the outputs of the trained learning systems, and locating matching samples in the one or more data structures using the combined outputs of the trained learning system for the target sample.
The training set, samples, and target sample may be audio samples.
The learning systems may be neural networks. Each learning system may be seeded with a different seed. Combining outputs may include concatenating outputs. The training steps of providing, adjusting, and continuing may be repeated a plurality of times. The training step of identifying a training set may include identifying different training sets for at least two of the learning systems. The small number of cycles may be substantially 10.
Adjusting the target outputs may include evaluating actual learning system outputs and adjusting the target output for at least one sample to reflect at least one actual output.
Initializing the data structure may include providing corpus samples to the learning systems to classify each sample in the corpus. Initializing the data structure may include providing corpus samples to the learning systems and placing each sample in the data structure in accordance with the output provided by the learning systems.
Combining outputs may include selecting a subset of output values associated with one or more learning systems as representative of the combined output. Combining outputs may include determining least correlated bits to form the subset. Combining outputs may include 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. Evaluating a target sample may include selecting first and/or second subsets of output values as representative of the target sample.
In another aspect, a method is described that includes 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 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.
In another aspect, a method is described that includes 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 set 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 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.
In another aspect, a method is described that includes 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 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.
FIG. 1 is a block diagram illustrating an exemplary architecture for locating matching samples using a learning system.
FIG. 2 is a flow chart illustrating one method 200 for training, initializing, and using a neural network 110 to find similarities in data.
FIG. 3 is a schematic diagram illustrating an example system 300.
FIG. 4 is a schematic diagram of an example of a generic computer system 400.
FIG. 5 is a graph showing Lookups Per Hashed Bin for Systems with L=1−22 Sets of Hashes.
FIG. 6 shows the number of elements in the resulting bin (on average) as a function of the number of hidden units in the network.
FIG. 7 demonstrates more than just the single top match entry.
FIG. 1 is a block diagram illustrating an exemplary architecture 100 locating matching samples using a learning system.
The architecture 100 will be described in reference to a data processing system that implements a method to learn a similarity function from weakly labeled positive examples for use in, for example, audio retrieval. Other applicable areas include, but are not limited to, image or video retrieval. Once learned, the similarity function may be used as the basis of one or more hash functions to constrain the number of data points considered during a retrieval or comparison operation. To increase efficiency, no comparisons in the original high-dimensional space of points are required. Generally stated, the architecture will learn how to retrieve examples from a database that are similar to a probe sample in a manner that is both efficient and compact.
In general, machine learning attempts to correctly deduce a function ƒ such that ƒ(X)=Y, where X is an input and Y is an output. In many cases X or Y is unknown or loosely known. Examples of machine learning include, supervised learning, unsupervised learning, and reinforced learning. Learning can be accomplished by a neural network or other such learning systems.
One or more neural networks, such as the neural network represented by brace 110, may be used to sort samples. The neural network receives input 120 based on an audio-spectrogram, and outputs hash bits 130. Hash bits 130 may be used to specify a bin location such as bin locations 150, of one or more hash tables 140. The number of hash tables 140 and bin locations 150 may be any number. After proper training, the bin location 150 calculated by the neural network 110 will specify a bin location where similar audio-spectrograms are located.
A neural network 110 is one example of a learning system that can be used in the architecture 100. For the purposes of these discussions, a neural network is a digital construct that is a collection of units and weights. Generally, a neural network defines a non-linear function approximation tool that is very loosely based on neural networks in the brain. Inputs are generated from a sample, and passed to input units or ‘neurons.’ In one implementation, each input ‘neuron’ is connected via a directed connection to some number of hidden units in hidden-layerA, in hidden-layerB, etc., or directly to the outputs. There can be any number of hidden units and hidden layers. In turn, each neuron in hidden-layerA can be connected to neurons in hidden-layerB, etc., or in the outputs. In general, in a feed-forward networks (as can be used here), neurons are connected by weighted connections to neurons in layers deeper in the network. Units can be connected in various ways, such as fully connected, sporadically connected, or just connected to certain layers, etc. Generally, units are connected to each other very specifically, where each connection has an individual weight. In one implementation, each unit or neuron generates an output signal when it is activated. In one implementation, each connection has a weight associated with it. In one implementation, the stronger the weight, the stronger the from-neuron's activation will affect the to-neuron's activation.
Through the connections between neurons, the output of one unit can influence the activations of other units. The unit receiving an activation signal calculates its own activation by, for example, taking a weighted sum of the input signals. In one implementation, each neuron beyond the input layer performs a simple function: for each of its connections, it multiplies the weight of the connection with the activation of the neuron to which it was connected, and it then sums these values. The value is then passed through a function (usually non-linear) such as 1/tan h. This then becomes that neuron's activation. Typically, if the unit's activation is above some threshold, it will generate an output sending it, by way of its weighted connections, to the other units that it is connected to. This same process occurs in neurons throughout the neural network, until finally the output neurons perform.
Networks learn by changing the weights of the connections over training iterations, also know as epochs. The weights of the connections may be modified to minimize the error between the predicted outputs and the target outputs for each training example. For example, these weights may be modified through a gradient-descent procedure, or other procedure. There are a myriad of training techniques, such as back propogation, which can be used to generate a response throughout the neural network 110. For example, a neural network may be used to develop a hashing function to categorize audio snippets.
The network may learn from various inputs. For example, the system may receive audio samples produced by splitting songs into slices. In one implementation, slices are chosen such that they do not completely overlap. Slices can be of any length and taken from any part of the song. In one implementation, each slice is also assigned a song label for the purposes of classifying the slice. Songs can be received from a song database, or through some other mechanism, such as being sent to the system via a user interface.
Using the number of sample songs and the number of hash bins 150 of the one or more hash tables 140, the system calculates a total number of possible hash bits 130. The system assigns the song slices an output from the calculated set of bits. This initial value is used to begin the training process and may or may not be the final value of the hash bits 130 for the song slice.
In one implementation, training may be accomplished by selecting a number of snippets from a number of songs (for example, selecting 10 consecutive 1.4 second long snippets from 1024 songs, sampled 110 milliseconds apart for a total of 10,240 song snippets). In one implementation, each snippet from the same song is labeled with the same song code (i.e. forced to the same output bin). In one implementation, to start, the target output for each song is assigned randomly, chosen without replacements from P(S), where S is 10 bits, for example. Put another way, each song is assigned a different set of 10 bits and P(S) is the power set, containing 210 different sets of 10 bits. Over time, the target outputs may change as the neural network 110 is trained.
In some implementations, the neural network 110 learns to map similar songs closer together in the hash tables 140. The neural network also learns to map dissimilar songs farther apart.
In one implementation, measured over the training set of 10,240 snippets, the target outputs will have maximal entropy; each binary output will be targeted as “on” for exactly 50% of the samples. In one implementation, the target outputs shift throughout training. After every few epochs of weight updates, the neural network's response to each training sample is measured.
The target outputs of each sample are then dynamically reassigned to the member from P(S) that is closest to the aggregate response of the network to each of the song's snippets. In one implementation, during the dynamic reassignment, two constraints are maintained: each song's snippets must have the same output, and each output from P(S) must be assigned only once.
Training of the neural network 100 can be summarized by the following table:
SELECT M=2n songs and DEFINE B(t) = tth binary code
FOREACH (song Sm)
| FOR (Xm iterations ) { ADD snippet Sm,x to training set }
| SELECT target Tm ε {0,1}n s.t. Tm1 = Tm2 m1 = m2 FOR (Idyn iterations)
| TRAIN network for Edyn epochs (Edyn passes through data)
| FOREACH (song Sm)
| | SET Am = ΣxεX m O(Sm,x) / Xm | | (where O(Sm,x) = actual network output for snippet Sm,x)
| SET Ut = { t | 0 < t ≦ M} as the unassigned binary codes
| SET Us = {s | 0 < s ≦ M } as the unassigned songs
| FOR (M iterations)
| | FIND (s, t) = arg minsεU s ,tεU t ∥ B(t) − As ∥2 | | SET Ts = B(t)
| | REMOVE s from Us and REMOVE t from Ut TRAIN network for Efixed epochs
n=10 M=1024, Xm =10 (∀m), Edyn =10, Idyn =50, Efixed=500
In Table 1, n, m, Xm, Edyn, Idyn, and Efixed, can be of any value which matches the configuration parameters of the system. For example, in one implementation, n=10, M=1024, Xm=10 (∀ m), Edyn=10, Idyn=50, Efixed=500.
By allowing the neural network 110 to adapt the outputs as described above, the outputs across training examples can be effectively reordered to prevent forcing artificial distinctions. Through the reordering process, the outputs are effectively reordered to create a weak clustering of songs. Similar songs are likely to have small hamming distances in target outputs. A hamming distance is a value that defines the number of changes necessary to represent one value (e.g., a binary representation of a number, or a string) as another value. For example, the binary values 100000 and 100011 would have a hamming distance of 2.
In some implementations, more than one neural network 110 may be used to determine the hash bits 130. The overall system can use any or all of a neural network's output when constructing the set of hash bits 130. The outputs of the neural networks 110 can be combined into a single output of hash bits 130. Using the outputs from many, separately trained, neural networks 110, the system can improve performance by decreasing the number of look-ups required while avoiding the computation costs associated with training larger neural networks. Put another way, using many smaller neural networks to mimic the behavior of a larger one can yield improved performance.
When the system uses more outputs to construct the hash bits 130, the number of bins grows in size. For example, 10 bits for the has bits yields 1024 unique bins, while 22 bits for the hash bits 130 yields 4,194,304 unique bins.
The system can select from the unused outputs of the neural network 110 ensemble to build another hash function that indexes into another hash table. When a new query arrives, it is passed through all of the networks and the outputs of the networks, if they have been selected into one of L hash tables, are used to determine the bin location 150 of that hash table 140.
The method 200 includes training (step 210) one or more learning systems. The trained learning systems can then be initialized (step 220) using appropriate samples. The trained and initialized systems may then be used to evaluate (step 230) data, such as new song snippets to determine similarity between songs or song snippets.
The method 200 includes training a system 210. Initially, a training set is identified 211. The training set is then provided to the learning systems 212. The learning system may include one or more systems. For example, learning can be accomplished by one or more neural networks or other learning systems.
The learning systems are provided with the training set of data, and the data is provided with a starting target value. As an example, this may be accomplished by randomly assigning a song snippet a 10 bit value, and forcing the value to be the same across the samples having the same desired output (i.e. all song snippets from the same song). The learning systems are then trained in a conventional manner, for example, where a song snippet is passed to the neural network and is processed.
Through processing the song snippet, the neural network 110 can modify the weights of its connectors. After a certain amount of training, the results can be examined and evaluated, and the target outputs adjusted or reassigned (step 214). For example, when using a neural network, the results may be examined after a predetermined number of training epochs (e.g., 10). In the examination, the results are compared against expected or desired results. For example, a neural network system may dynamically reassign the outputs to an aggregate value based on the results of the evaluation. Over time, this results in more similar samples being grouped closer together. Implicit distance may be measured by an average hamming distance, total hamming, or other measure.
In one implementation, one or more neural networks may be used as the learning systems. A deterministic hash function maps the same point to the same bin. These methods create a hash function that also groups “similar” points in the same bin, where “similar” is defined by the task. This may be described as a forgiving hash function, in that it forgives differences that are small with respect to the implicit distance function being calculated.
Learning a forgiving hash function has several objectives: (1) function without an explicitly defined distance metric; (2) work with only weakly labeled examples, because although there are some indications of what points are similar (such as the song label), there is no information about which parts of songs sound similar to other parts; and (3) generalize beyond the examples given, as it cannot be trained on samples from all the songs that will be expected to be used with. Effectively, this means that the learned function must maintain entropy in the hashes for even new samples. Whether or not the songs have been seen before, they must be well distributed across the hash bins. If the entropy is not maintained, the points (samples) may be hashed to a small number of bins, rendering the hash ineffective.
In training, the entropy may be explicitly controlled by carefully setting the outputs of the training examples. Other learning methods may also be used, for example, controlling entropy of each output, and also between outputs (to ensure that they are not correlated). Furthermore, incremental training of a network also provides the opportunity to dynamically set the target outputs to minimize the artificial distinctions between similar sounding, but different, songs.
A neural network may be trained to take as input an audio-spectrogram and output a bin location where similar audio-spectrograms have been hashed. The outputs of the neural network may be represented in binary notation.
One difficulty in training arises in finding suitable target outputs for each network. In one implementation, every snippet of a particular song is labeled with the same target output. The target output for each song can be assigned randomly, chosen without replacement from P(S), where S is 10 bits—i.e., each song is assigned a different set of 10 bits and P(S) is the power set, containing 210 different sets of 10 bits. Sampling without replacement may be used as a component of this procedure. Measured over the training set, the target outputs will have maximal entropy: each binary output will be targeted as ‘on’ for exactly 50% of the samples.
Instead of statically assigning the outputs, in one implementation the target outputs shift throughout training. This approach overcomes the potential drawback of large hamming distances while retaining the benefit of not hindering/preventing the mapping. Thus, in one implementation, after every few epochs of weight updates, the network's response to each of the training samples is measured. The target outputs of all of the samples are then dynamically reassigned to the member from P(S) that is closest to the aggregate response of the network to each of the song's snippets. However, in this implementation, two constraints are maintained: each song's snippets must have the same output; and each output set from P(S) must be assigned once (no two song's snippets can have the same target outputs). This is a suitable approach, as the specific outputs of the network are not of interest, only the distribution of them (to maintain high entropy), and that similar snippets map to the same outputs.
By letting the network adapt the outputs in this manner, the outputs across training examples can be effectively reordered to prevent forcing artificial distinctions. Through this process, the outputs are effectively being reordered to perform a weak form of clustering of songs: similar songs are likely to have small hamming distances in target outputs.
In one implementation, a learning function may be created using only weakly labeled positive examples (similar pairs) coupled with a forced constraint towards maximum entropy (nearly uniform occupancy). Negative examples (dissimilar pairs) are not explicitly created, but instead the methods rely on a maximum-entropy constraint to provide separation. Such an approach attempts to explicitly learn the similarities and use them to guide the hash function. Furthermore, this approach allows similarity to be calculated on (potentially non-linear) transformations of the input rather than directly on the inputs. In addition, the use of multiple hashes (or multiple networks) in the system may be used to account for the imperfect learning of a difficult similarity functions. These learning systems would have the advantage of allowing for similarities between only nominally distinct samples, without requiring the learning structure to attempt to discover minor (or non-existent) differences in these close examples.
This approach attempts to explicitly learn the similarities and use them to guide the hash function. Furthermore, this approach allows similarity to be calculated on (potentially non-linear) transformations of the input rather than directly on the inputs. The use of multiple hashes in the system used here is to account for the imperfect learning of a difficult similarity functions.
Two of the metrics that may be used to measure performance of a network's outputs include: 1) the number of elements hashed to each bin (how many candidates must be considered at each lookup); and 2) the number of similar elements that are hashed to each bin (is there a snippet from the correct song in the bin when a lookup is done?). Various criterion may be used for measurement purposes, such as the likelihood of the correct snippet in the correct bin. For example, a simple recall criterion can be used for measurement purposes: of the snippets in the hashed bin, are any from the correct song? For example, a more stringent recall criterion can be whether there is a correct match with the song label associated with the single top-ranked snippet and a query.
A large-scale hashing system can be created to increase the number of bins. One implementation to scale the hash to a larger number of bins would be to train the network with more outputs. For example, a network trained with 10 outputs allows 1024 bins in the hash, while using 22 bits for the hash bits yields 4,194,304 bins in the hash. However, using larger networks necessitates more training data, and thus the approach can become computationally prohibitive.
In an alternative implementation, the system can leverage the facts that training networks is a randomized process dependent on the initial weights, and that networks with different architectures typically learn different mappings. Therefore, the outputs of multiple networks may be combined to create a large-scale hashing system. For example, multiple networks may be trained, and bits for the hash may be selected from any of the networks' outputs. Numerous methods can be used to select which outputs are used for a hash. For example, various methods of selecting the outputs include random selection, using sets with minimum correlation between the members, and using sets with minimum mutual information. The selection may be made in a greedy manner, or other manner. The methods that account for mutual information generally explicitly attempt to place the points across bins by ensuring that the combined entropy of the bits that compose the hash index remains high. For example, the outputs of more than one neural network can be concatenated to produce a set of hash bits. The hash bits can come from any output any neural network and not all neural networks need to be represented in the concatenated result. More than one neural network can also be combined by looking at the outputs and determining a correlation between the outputs bits. The system can use the correlation of bits to determine the set of bits used as hash bits. In one implementation, the system can look at the least correlated bits and use these least correlated bits as representative bits of the output.
Using an approach of combining the results of different networks allows for selection of an arbitrary number of outputs from the network ensemble for the hash function. This allows much greater freedom that the constraint of using only a number of bits equal to the output of a single network (for example, 10 bits in a single 10 output network).
The performance of a neural network can be measured in terms of lookups and correct matches as a function of bits that are used for the hash. By selecting the hash bits from multiple networks, the number of lookups when using the same number of bins (such as 1024) can be decreased. For example, in one implementation, selecting hash bits from multiple neural networks, decreased the number of lookups for 1024 bins by a factor of substantially 50%. The lookups were reduced from 200 per query when using 10 outputs from a single neural network to 90 lookups per query when using 10 outputs from more than one neural network in one exemplary system. In another implementation, increasing the number of bins both decreased the number of correct matches and decreased the number of lookups. However the number of lookups decreased (from 90 to 5 per query, a 94% reduction) more than the decrease in correct matches (approx. 50%), when going from 1024 bins to 4,194,304 bins in one exemplary implementation.
The learning systems can be trained in this fashion until the learning systems are determined (step 215) to be trained. This may be accomplished by meeting a predetermined accuracy threshold (such as exceeding an 80% correctness rate), by being trained a certain amount of time, or another measure. Once properly trained, the learning systems can be used to generate information to specify locations for the data. For example, in on implementation, a neural network may be trained for 1000 epochs, with the outputs evaluated and reassigned every 10 epochs. After these 1000 epochs, the neural network is considered trained.
After training, the data structures may be initialized. In some implementations, training the system also results in initialized data structures.
The method 200 may initialize (step 220) the data structures by providing (step 222) sample snippets for processing by the one or more learning systems. For each sample processed, the system can combine (step 224) one or more outputs from one or more learning systems. Using the combined outputs, the system can map (step 226) the outputs from one or more learning systems, providing indices to the samples provided. For example, the data structures may be initialized by populating with audio snippets from a database of songs.
The system can begin evaluation (step 230) of a target sample by being provided (step 232) the target sample. For example, the target sample may be a song snippet from such sources as a database or as specified by a user through a user interface. The sample is then input into one or more trained learning systems which generate output. The system can combine (234) the outputs from one or more learning systems into an index. Using the combined index, the system can locate (step 236) a matching sample in one or more indexed locations.
In one implementation, one or more neural networks may be used as the learning systems. One approach is that when a new query, q, arrives, it may be passed into an ensemble of networks from which select outputs may be used to determine a single hash location in a single hash table. However, this can be generalized to q hash tables, with L distinct hash functions. In one implementation, this may be accomplished by selecting from the unused outputs of the network ensemble to build another hash function that indexes into another hash table. Thus, for other approaches, when q arrives, it may be passed through all of the networks and the outputs of the networks (if they have been selected into one of L hashes) are used to determine the bin of that hash.
As can be understood from the description above, comparisons are not required to be performed in the original high dimensional spectrogram representation of the target sample. After passing through the networks; the sample snippet is reduced to the quantized binary outputs, and the original representation is not needed for comparison.
In general, a smaller number of bins will yield a larger number of candidate lookups for any number of networks used. Thus, as would be expected, as the number of bins increases, the number of candidates decreases rapidly for settings of L. In addition, for larger numbers of networks used, the ability to find the best match in one implementation barely decreases as the number of bins increases—despite the large drop in the number of lookups. One exception to this is that for very small numbers of networks used (such as 1-3), as the number of bins increases, the accuracy rises (though remaining below the accuracy of larger number of networks). The increase occurs because there are a large number of ties when using a small L, as many songs have the same support, and ties are generally by random selection. In general, however, as the number of snippets hashed to the same bin decreases, the correct song competes with fewer incorrect ties and has a higher chance of selection.
In one implementation, as the number of hashes increases, the number of candidates generally increases almost linearly. This indicates that the hashes are truly independent. If they were not independent, the number of unique candidates examined would overlap to a much greater degree. Thus, if there was significant repetition of candidates across the hashes, we would see the same “frequent-tie” phenomena described for L=1−3: the same songs would be repeatedly grouped and we would be unable to distinguish the correct co-occurrences from the accidental ones.
For music identification, the hashing scheme may be incorporated into existing systems that identify songs with large snippets (i.e. 10-30 seconds) by simply integrating evidence over time. The system may designed to work with video and images as well.
The example system 300 includes a client machine 310, a network 320, and one or more servers 330. The client machine 310 can send data, such as a song or song snippet, through the network 320 to one or more servers 330. The servers 330 can process the data, as described above, and can return results to the client 310 through the network 320. For example, if the data encompasses a song snippet, the servers 330 can return a list of one or more songs that may be the matching song. If the data encompasses a song, the servers 330 can, for example, return a list of one or more songs that sound similar to the original song.
FIG. 4 is a schematic diagram of an example of a generic computer system 400. The system 400 can be used for the operations described in association with the methods discussed above according to one implementation.
The system 400 includes a processor 410, a memory 420, a storage device 430, and an input/output device 440. Each of the components 410, 420, 430, and 440 are interconnected using a system bus 450. The processor 410 is capable of processing instructions for execution within the system 400. In one implementation, the processor 410 is a single-threaded processor. In another implementation, the processor 410 is a multi-threaded processor. The processor 410 is capable of processing instructions stored in the memory 820 or on the storage device 430 to display graphical information for a user interface on the input/output device 440.
Search engines may be used to leverage the vast amount of information available to them to execute “more-like-this” image queries or “which song does this audio snippet come from” type queries as described above. Other applications include, but are not limited to, searching a personal PC for a target image, or song based on the characteristics of the incoming image or song.
In some implementations, the song snippets can be assigned target values using alternate clustering methods. For example, songs can be grouped by genre such that country songs would be grouped more closely to other country songs and grouped farther apart from hip hop songs.
In some implementations, snippets of songs can also be hashed using different techniques. For example, snippets of songs could be hashed to more than one location if the snippet or song exhibited different musical styles, such as classical music and reggae music.
This example was constructed to meet the goal of identifying the song from which an audio sample came, given that the audio sample was an extremely short (˜1.4 second) audio “snippet” sampled from anywhere within a large data-base of songs.
A database was created using 6,500 songs, with 200 snippets extracted from each song, with a resulting total of 1,300,000 snippets. First, each song was first converted into a series of small snippets for storage in the database. Then, when a new song or snippet was looked up in the database, it was converted in the same manner.
Each song was converted from a typical audio format (i.e. mp3, way, etc.) to a mel-frequency spectrogram with tilt and amplitude normalization over a pre-selected frequency range. The frequency range may cover, for example, 400 Hz to 4 kHz or 300 Hz to 2 kHz. For computational efficiency, the input audio was low-pass filtered to about 5/4 of the top of the selected frequency range and then down sampled accordingly. For example, using 4 kHz as the top of our frequency range of interest and using 44.1 kHz as the input audio sampling rate, we low-pass filtered using a simple FIR filter with an approximate frequency cut between 5 and 5.5 kHz and then subsampled to a 11.025 kHz sampling rate. To minimize volume-change effects, we normalized the audio sample energy using the local average energy, taken over a tapered, centered 10-second window. To minimize aperture artifacts, the average energy was also computed using a tapered Hamming window.
A spectrogram “slice rate” of 100 Hz (that is, a slice step size of 10 ms) was used. For the slices, audio data was taken, and a tapered window (to avoid discontinuity artifacts in the output) applied, and then an appropriately sized Fourier transform was applied. The Fourier magnitudes were “de-tilted” using a single-pole filter to reduce the effects of low-frequency bias and then “binned” (averaged) into B frequency samples at mel-scale frequency spacing (e.g., B=33).
Training commenced by selecting 10 consecutive snippets from 1024 songs, sampled 110 ms apart (for a total 10,240 snippets). Each snippet from the same song was then labeled with the same target song code for that song. This was a weak label: although the snippets that are temporally close may be ‘similar’, there is no guarantee that snippets that are further apart will be similar—even if they are from the same song. Moreover, snippets from different songs may have been more similar than snippets from the same song; however, we did not require detailed labeling (as it would be very difficult to obtain for large sets).
Instead of statically assigning the outputs, the target outputs were allowed to shift throughout training. After every few epochs of weight updates, the network's response to each of the training samples was measured. A success was measured if any of the snippets in the hashed bin were from the correct song. The target outputs were then dynamically reassigned by assigning the target outputs of all of the samples to the member from the series that is closest to the aggregate response of the network to each of the song's snippets.
58 different networks were trained: 2 with 5 hidden units, 2 with 7 hidden units, etc, up to 2 with 61 hidden units. Each network was then used to hash approximately 38,000 snippets (drawn from 3,800 songs with 10 snippets each). These 3,800 formed our test set for this stage, and were independent from the training set. For this test, we removed the query q from the database and determined in which bin it would hash by propagating it through the networks—if the output of the network was greater than the median response of the output (as ascertained from the training set), the output was considered as +1; otherwise, it was considered as 0. The 10 outputs were treated as a binary number representing the hash bin.
By letting the network adapt the outputs in this manner, the outputs across training examples were effectively reordered to prevent forcing artificial distinctions. Through this process, the outputs were effectively being reordered to perform a weak form of clustering of songs, as similar songs were likely to have small hamming distances in target outputs.
For comparative purposes, training was also completed without output reordering, while using the same inputs, number of epochs, etc. Training a neural network without reordering resulted in a performance that was barely above random chance (5.4 matches out of 10 when using 5 hidden units, and 5.6 out of 10 when using 59 hidden layers). In comparison, neural networks trained using reordering performed much better (6.5-7 matches out of 10 when using 5 hidden units, and 7-7.5 matches out of 10 using 59 hidden units). Thus, a network trained with output reordering was able to learn a mapping more consistently than a network trained without reordering.
FIG. 6 shows the number of elements in the resulting bin (on average) as a function of the number of hidden units in the network. FIG. 6 also shows the percentage of lookups that resulted in a bin which contained a snippet from the correct song. Looking at the middle of the graph, every query on average was hashed into a bin with approximately 200 other snippets (˜0.5%) of the database. In ˜78% of the retrievals, the hash bin contained a snippet from the correct song. Note that if the hashes were completely random, we would expect to find a snippet from the same song less than 1% of the time. FIG. 6 also shows the negative effects of small networks, which may be seen in the lower precision (higher # of lookups) and largely unchanged recall (% correct matches) given by the networks with 5-9 hidden units. However, using only networks with 11 or more hidden units reduces the number of lookups by ˜70% (from ˜500-˜150) with only minor impact on the recall rate (˜2%).
Example 2 used the same technique described in example 1 to obtain song snippets. Example 3 described the results of changed attributes for L (1-22) and # of network outputs per hash (10-22: 1,024-4,194,304 bins per hash).
In Example 1, success was measured by whether the hashed bin contained a snippet from the correct song. Example 2 used a tightened definition of success. The snippets found in all of the L hashed bins were rank ordered according to the number of hashes that contained each snippet. Using these ranked snippets, success was determined as the correct match of the song label associated with the single top-ranked snippet and the query q.
FIG. 5 shows the lookups per hashed bin for a range of systems.
With L=22 hashes and with only 1,024 bins, the number of candidate lookups is unacceptably large—over 2,000. With a smaller number of hashes, the number of candidates decreases. As expected, as the number of bins increases, the number of candidates decreases rapidly for all of the settings of L considered. For 22 hashes, as the number of bins increases, the ability to find the best match barely decreases—despite the large drop in the number of lookups. For approximately 200-250 candidates (˜0.6% of the database), we achieve between 80-90% accuracy (L>14).
Note that for (L=1−3), as the number of bins increases, the accuracy rises—in almost every other case it decreases. The increase with L=1−3 occurs because there are a large number of ties with a small L; many songs have the same support, and we break ties with random selection. As the number of snippets hashed to the same bin decreases, the correct song competes with fewer incorrect ties and has a higher chance of selection.
Finally, note that as the number of hashes increases, the number of candidates increases almost linearly. This indicates that the hashes are truly independent. If they were not independent, the number of unique candidates examined would overlap to a much greater degree. If there was significant repetition of candidates across the hashes, we would see the same “frequent-tie” phenomena that we commented on for L=1: the same songs would be repeatedly grouped and we would be unable to distinguish the correct co-occurrences from the accidental ones.
A large scale test of a system was conducted using the trained networks (from Examples 1 and 2) to hash 1,300,000 snippets. 6,500 songs were selected, and 200 snippets from each song were procured. The snippets are of length 128*11 milliseconds, and are drawn approximately 110 ms apart. The spacing follows the experiments of previous studies. In Example 3, we use the same technique described in Example 1 to obtain our song snippets.
For every query snippet, the number of other snippets considered as potential matches (the union of the L hashes) were examined. In addition, the number of times the snippet with the maximum number of hits from all of the hashes came from the correct song was examined. 46 different parameter settings produced by varying L and the number of bins per hash were tried. Table 2 shows the performance for 5 groups of desired # of candidates. The rows of Table 2 indicate the desired % of candidates examined, while the rows show the achieved accuracy and associated parameter settings. For example, the first row of Table 2 (<0.15%) indicates that when the average query examined less than 0.15% of the database, the top accuracy that was achieved was 56%, and used 22 bins and L=10 sets of hashes. In summary, 1.4 second snippets could be found in a database of 6500 songs with 72% accuracy by using 22 bins and L=18 sets of hashes—while only examining 0.27% of the database per query.
Best Results for 0.15-0.55% Candidates
Best 3 Results
(Accuracy, Bins,/(sets))
56% (22, 10)
37% (20, 5)
36% (22, 5)
69% (22, 16)
66% (22, 14)
62% (22, 12)
72% (22, 18)
67% (20, 14)
63% (20, 12)
73% (20, 18)
70% (20, 16)
63% (16, 5)
0.45-0.55%
77% (20, 22)
75% (20, 20)
71% (18, 16)
FIG. 7 demonstrates more than just the single top match entry. As shown, when the top 25 snippets that appeared in the most bins are examined, there is a smooth drop-off in finding the correct song. Because there are 200 snippets from each song in the database, multiple snippets from the same song can be found.
Finally, we bring all of our results together and examine the performance of this system. In this example, we allowed fingerprints to be coarsely sampled to lower the memory required to recognize a large database of songs and resulted in improved recognition rates. For this example, we used s seconds of a song (1.4≦s≦25) and integrated the evidence from individual snippet lookups to determine the correct song. By removing the matching snippet from the database, this makes the sampling rate and points substantially the worst possible for the database—the closest matching snippet is temporally 11 ms away from q. In live service, with either stochastic or aligned sampling of the query, the maximum distance will be reduced to 5.5 ms. Results are shown in Table 3. For the forgiving hasher system proposed, we give the results using 222 bins & l=18 hashes. In summary, for our system, the near perfect accuracy at even 5s is achieved while considering only a tiny fraction of the candidates (0.027% per lookup). Also note that each candidate simply has a counter associated with it; neither the spectrogram, nor a representation of the spectrogram, is compared with each candidate.
Performance vs. Query Length (in seconds)
Forgiving-Hash
Particular embodiments of the subject matter described in this specification have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. Other embodiments are within the scope of the following claims.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4811399Jun 14, 1988Mar 7, 1989Itt Defense Communications, A Division Of Itt CorporationApparatus and method for automatic speech recognitionUS5706364Apr 28, 1995Jan 6, 1998Xerox CorporationMethod of producing character templates using unsegmented samplesUS6023693Oct 6, 1995Feb 8, 2000Fujitsu LimitedLearning system for a data processing apparatusUS6236758Oct 22, 1999May 22, 2001Sarnoff CorporationApparatus and method for encoding wavelet trees by backward predictive coding of wavelet transformed coefficientsUS6494720Nov 14, 1997Dec 17, 2002Jan MeyrowitschMethods for objectification of subjective classificationsUS6563909Dec 20, 2000May 13, 2003Koninklijke Philips Electronics N.V.X-ray examination apparatusUS6585521Dec 21, 2001Jul 1, 2003Hewlett-Packard Development Company, L.P.Video indexing based on viewers' behavior and emotion feedbackUS6704920Oct 30, 2001Mar 9, 2004Nova Measuring Instruments Ltd.Process control for micro-lithographyUS6751601Jul 20, 2001Jun 15, 2004Pablo ZegersMethod and a system for solving dynamic problems using the dynamical system architectureUS6763339Jun 25, 2001Jul 13, 2004The Regents Of The University Of CaliforniaBiologically-based signal processing system applied to noise removal for signal extractionUS6766523Nov 27, 2002Jul 20, 2004Microsoft CorporationSystem and method for identifying and segmenting repeating media objects embedded in a streamUS6773266Jun 18, 2002Aug 10, 2004Athenium, L.L.C.Method for implementing collaborative training and online learning over a computer network and related techniquesUS6782186Dec 23, 1996Aug 24, 2004Interval Research Corp.System and method for selective recording of informationUS6879967Mar 24, 2000Apr 12, 2005Ricoh Co., Ltd.Method and apparatus for open data collectionUS6892191Feb 7, 2000May 10, 2005Koninklijke Philips Electronics N.V.Multi-feature combination generation and classification effectiveness evaluation using genetic algorithmsUS6895514Jun 25, 1999May 17, 2005Lucent Technologies Inc.Method and apparatus for achieving secure password accessUS6944632Apr 21, 2003Sep 13, 2005Prn CorporationMethod and apparatus for gathering statistical information about in-store content distributionUS7103801Nov 1, 2002Sep 5, 2006AlcatelMethod and apparatus for analyzing alarms coming from a communications networkUS7107207Jun 19, 2002Sep 12, 2006Microsoft CorporationTraining machine learning by sequential conditional generalized iterative scalingUS7174293Jul 13, 2001Feb 6, 2007Iceberg Industries LlcAudio identification system and methodUS7266492Aug 16, 2006Sep 4, 2007Microsoft CorporationTraining machine learning by sequential conditional generalized iterative scalingUS7281219Dec 5, 2003Oct 9, 2007International Business Machines CorporationBlended learning experience tool and methodUS7375304Dec 6, 2004May 20, 2008Lincoln Global, Inc.System and method providing automated welding notificationUS7386479Aug 8, 2002Jun 10, 2008Yamaha CorporationContent sales site and programUS7472096Dec 16, 2005Dec 30, 2008Microsoft CorporationTraining a learning system with arbitrary cost functionsUS7617164Mar 17, 2006Nov 10, 2009Microsoft CorporationEfficiency of training for ranking systems based on pairwise training with aggregated gradientsUS7831531 *Jun 21, 2007Nov 9, 2010Google Inc.Approximate hashing functions for finding similar contentUS20020133499Aug 20, 2001Sep 19, 2002Sean WardSystem and method for acoustic fingerprintingUS20030093790Jun 8, 2002May 15, 2003Logan James D.Audio and video program recording, editing and playback systems using metadataUS20030101144Nov 29, 2001May 29, 2003Compaq Information Technologies Group, L.P.System and method for detecting repetitions in a multimedia streamUS20040025174May 29, 2003Feb 5, 2004Predictive Media CorporationMethod and system for the storage, viewing management, and delivery of targeted advertisingUS20040031058May 8, 2003Feb 12, 2004Richard ReismanMethod and apparatus for browsing using alternative linkbasesUS20040128682Dec 31, 2002Jul 1, 2004Kevin LigaTechniques for reinsertion of local market advertising in digital video from a bypass sourceUS20040199387Apr 26, 2004Oct 7, 2004Wang Avery Li-ChunMethod and system for purchasing pre-recorded musicUS20050066352Nov 12, 2004Mar 24, 2005Microsoft CorporationSystem and method for providing user control over repeating objects embedded in a streamUS20050086682Oct 15, 2003Apr 21, 2005Burges Christopher J.C.Inferring information about media stream objectsUS20050096920Dec 14, 2001May 5, 2005Matz William R.System and method for developing tailored contentUS20050147256Dec 30, 2003Jul 7, 2005Peters Geoffrey W.Automated presentation of entertainment content in response to received ambient audioUS20050193016Feb 17, 2005Sep 1, 2005Nicholas SeetGeneration of a media content database by correlating repeating media content in media streamsUS20050283792Aug 26, 2005Dec 22, 2005Swix Scott RSystems, methods and products for assessing subscriber content accessUS20060080356Oct 13, 2004Apr 13, 2006Microsoft CorporationSystem and method for inferring similarities between media objectsUS20060174348Jan 11, 2006Aug 3, 2006Rhoads Geoffrey BWatermark-based personal audio applianceUS20070124756Nov 27, 2006May 31, 2007Google Inc.Detecting Repeating Content in Broadcast MediaUS20070130580Nov 27, 2006Jun 7, 2007Google Inc.Social and Interactive Applications for Mass MediaUS20070143778Nov 27, 2006Jun 21, 2007Google Inc.Determining Popularity Ratings Using Social and Interactive Applications for Mass MediaUS20080090551Nov 27, 2007Apr 17, 2008Yoad GidronRule-based system and method for managing the provisioning of user applications on limited-resource and/or wireless devicesUS20080263041Nov 14, 2006Oct 23, 2008Mediaguide, Inc.Method and Apparatus for Automatic Detection and Identification of Unidentified Broadcast Audio or Video SignalsEP1524857A2Aug 23, 2004Apr 20, 2005Microsoft CorporationInferring information about media stream objects* Cited by examinerNon-Patent CitationsReference1"Community" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50045241?single=1&query-type=word&queryword=community.2"Compression" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50045890?single=1&query-type=word&queryword=compression.3"Database" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50057772?single=1&query-type=word&queryword=database.4"Encrypt" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/00292459?single=1&query-type=word&queryword=encrypt.5‘A Highly Robust Audio Fingerprinting System’ [online]. Haitsma et al. 2002,[retrieved on Nov. 16, 2006]. Retrieved from the Internet: <URL: www.ismir2002.ismir.net/proceedings/02-FP04-2.pdf>, 9 pages.6‘A Review of Algorithms for Audio Fingerprinting’ [online]. Cano et al., 2002, [retrieved on May 30, 2007]. Retrieved from the Internet: <URL: www.iua.upf.es/mtg/publications/MMSP-2002-pcano.pdf>, 5 pages.7‘Computer Vision for Music Identification’ [online]. Ke et al., 2005, [retrieved on May 30, 2007]. Retrieved from the Internet: <URL: www.cs.cmu.edu/˜yke/musicretrieval/cvpr2005-mr.pdf>, 8 pages.8‘CS276 Information Retrieval and Web Mining’ [online]. Stanford, 2005, [retrieved on Nov. 16, 2006]. Retrieved from the Internet: <URL: www.stanford.edu/class/cs276/handouts/lecture19.pdf>, 8 pages.9‘Data Mining: Associations’ [online]. Stanford, 2002, [retrieved on May 30, 2007]. Retrieved from the Internet: <URL: www.stanford.edu/class/cs345a/pdf/cs345-Ish.pdf>, 61 pages.10‘Duplicate Detection and Audio Thumbnails with Audio Fingerprinting’ [online]. Burges et al. 2004, [retrieved on Nov. 21, 2006]. Retrieved on the Internet: <URL: www.research.microsoft.com/˜cburges/tech—reports/tr-2004-19.pdf>, 5 pages.11‘Fast Multiresolution Image Querying’ [online]. Jacobs et al, 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: <URL: www.grail.cs.washington.edu/projects/query/mrquery.pdf>, 10 pages.12‘Finding Interesting Associations without Support Pruning’ [online]. Cohen et al. Retrieved from the Internet: <URL: www.dbis.informatik.hu-berlin.de/dbisold/lehre/WS0405/KDD/paper/CDFG—00.pdf> 12 pages.13‘Shazam Entertainment Brings Music Recognition to Windows Mobile 5.0 Powered Smartphones’ [online]. Shazam, 2006, [retrieved on Nov. 16, 2006]. Retrieved from the Internet: <URL: www.shazam.com/music/portal/sp/s/media-type/html/user/anon/page/default/template/pages/p/company—release30.html>, 1 page.14‘Shazam Experience Music’ [online]. [retrieved on May 30, 2007]. Retrieved from the Internet: <URL: www.shazam.com/music/portal/sp/s/media-type/html/user/anon/page/default/template/Myhome/music.html>, 2 pages.15‘Wavelets for Computer Graphics: A Primer, Part 1’ [online]. Stollnitz et al., 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: <URL: www.grail.cs.washington.edu/pub/stoll/wavelet1.pdf>, 8 pages.16‘Wavelets for Computer Graphics: A Primer, Part 2’ [online]. Stollnitz et al., 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: <URL: www.grail.cs.washington.edu/pub/stoll/wavelet2.pdf>, 9 pages.17"Community" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50045241?single=1&query—type=word&queryword=community.18"Compression" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50045890?single=1&query—type=word&queryword=compression.19"Database" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/50057772?single=1&query—type=word&queryword=database.20"Encrypt" definition. Oxford English Dictionary. Accessed Apr. 27, 2009. http://dictionary.oed.com/cgi/entry/00292459?single=1&query—type=word&queryword=encrypt.21'A Highly Robust Audio Fingerprinting System' [online]. Haitsma et al. 2002,[retrieved on Nov. 16, 2006]. Retrieved from the Internet: , 9 pages.22A Multi-layer ADaptive FUnction Neural Network (MADFUNN) for Analytical Function Recognition, Miao Kang; Palmer-Brown, D.; Neural Networks, 2006. IJCNN '06. International Joint Conference on Digital Object Identifier: 10.11 09/IJCNN.2006.246895 Publication Year: 2006 , pp. 1784-1789.23'A Review of Algorithms for Audio Fingerprinting' [online]. Cano et al., 2002, [retrieved on May 30, 2007]. Retrieved from the Internet: , 5 pages.24An adaptive function neural network (ADFUNN) for phrase recognition, Miao Kang; Palmer-Brown, D.; Neural Networks, 2005. IJCNN '05. Proceedings. 2005 IEEE International Joint Conference on vol. 1, Digital Object Identifier: 10.11 09/IJCNN.2005.1555898 Publication Year: 2005 , pp. 593-597 vol. 1.25An all-phoneme ergodic HMM for unsupervised speaker adaptation, Miyazawa, Y.; Acoustics, Speech, and Signal Processing, 1993. ICASSP-93., 1993 IEEE International Conference on vol. 2 Digital Object Identifier: 10.11 09/ICASSP.1993.319372, Publication Year: 1993, pp. 574-577 vol. 2.26An information theoretic approach to adaptive system training using unlabeled data Kyu-Hwa Jeong; Jian-Wu Xu; Principe, J.C.; Neural Networks, 2005. IJCNN '05. Proceedings. 2005 IEEE International Joint Conference on vol. 1, Jul. 31-Aug. 4, 2005 pp. 191-195 vol. 1 Digital Object Identifier 10.11 09/1JCNN.2005.1555828.27Baluja et al., "Learning "Forgiving" Hash Functions: Algorithms & Large Scale Tests" Jun. 2006, 7 pages.28Burges et al "Using Audio Fingerprinting for Duplicate Detection and Thumbnail Generation," Mar. 2005, 4 pages.29Cheng Yang, "MACS: Music Audio Characteristic Sequence Indexing for Similarity," Applications for Signal Processing to Audio and Acoustis, 2001 IEEE Workshop, Oct. 21-24, 2001, pp. 123-126.30Chinese Patent Office Action for Application No. 200680051559.0 dated Jan. 22, 2010, 14 pages.31'Computer Vision for Music Identification' [online]. Ke et al., 2005, [retrieved on May 30, 2007]. Retrieved from the Internet: , 8 pages.32Connectionist training of non-linear hidden Markov models for speech recognition Zhao, Z.; Neural Networks, 1991. 1991 IEEE International Joint Conference on Nov. 18-21, 1991 pp. 1647-1652 vol. 2, Digital Object Identifier 10.11 09/1JCNN.1991.170645.33'CS276 Information Retrieval and Web Mining' [online]. Stanford, 2005, [retrieved on Nov. 16, 2006]. Retrieved from the Internet: , 8 pages.34'Data Mining: Associations' [online]. Stanford, 2002, [retrieved on May 30, 2007]. Retrieved from the Internet: , 61 pages.35David A. Sadlier et al., "Automatic TV advertisement detection from MPEG bitstream," Pattern Recognition, vol. 35 (2002), Issue 12, pp. 2719-2726.36Deller, Jr. et al., Discrete-Time Processing of Speech Signals 1-936 (Reprint ed. 1999).37'Duplicate Detection and Audio Thumbnails with Audio Fingerprinting' [online]. Burges et al. 2004, [retrieved on Nov. 21, 2006]. Retrieved on the Internet: , 5 pages.38European Search Report, EP Application No. 08 15 3719 mailed Sep. 26, 2008, 8 pages.39'Fast Multiresolution Image Querying' [online]. Jacobs et al, 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: , 10 pages.40'Finding Interesting Associations without Support Pruning' [online]. Cohen et al. Retrieved from the Internet: 12 pages.41Gauch, J. M. et al., "Identification of New Commercials Using Repeated Video Sequence Detection," Sep. 11, 2005, Image Processing, 2005, ICIP 2005, IEEE International Conference on Genova, Italy Sep. 11-14, 2005, Piscataway, NJ, USA, IEEE, pp. 1252-1255.42Input Data Representation for Self-Organizing Map in Software Classification, Yuqing Lin; Huilin Ye; Knowledge Acquisition and Modeling, 2009. KAM '09. Second International Symposium on vol. 2, Digital Object Identifier: 10.11 09/KAM.2009.151 Publication Year: 2009 , pp. 350-353.43International Preliminary Report on Patentability, Application No. PCT/US06/45549 mailed Jun. 12, 2008, 7 pages.44International Preliminary Report on Patentability, Application No. PCT/US06/45551 mailed Apr. 2, 2009, 11 pages.45Learning to Rank Using Semantic Features in Document Retrieval, Tian Weixin; Zhu Fuxi; Intelligent Systems, 2009. GCIS '09. WRI Global Congress on vol. 3 Digital Object Identifier: 10.11 09/GCIS.2009.148, Publication Year: 2009 , pp. 500-504.46On adaptive acquisition of language, Gorin, AL.; Levinson, S.E.; Miller, L.G.; Gertner, AN.; Ljolje, A; Goldman, E.R.; Acoustics, Speech, and Signal Processing, 1990. ICASSP-90., 1990 International Conference on Digital Object Identifier: 10.11 09/ICASSP.1990.115784 Publication Year: 1990 , pp. 601-604 vol. 1.47PCT International Search Report for PCT/US2006/045549 dated Oct. 9, 2007, 10 pages.48PCT International Search Report for PCT/US2006/045551 dated Jul. 21, 2008, 20 pages.49Robust Technologies towards Automatic Speech Recognition in Car Noise Environments, Ding, P.; He, L.; Yan, X.; Zhao, R.; Hao, J.; Signal Processing, 2006 8th International Conference on vol. 1, Digital Object Identifier: 10.11 09/ICOSP.2006.345538 Publication Year: 2006.50'Shazam Entertainment Brings Music Recognition to Windows Mobile 5.0 Powered Smartphones' [online]. Shazam, 2006, [retrieved on Nov. 16, 2006]. Retrieved from the Internet: <URL: www.shazam.com/music/portal/sp/s/media-type/html/user/anon/page/default/template/pages/p/company-release30.html>, 1 page.51'Shazam Experience Music' [online]. [retrieved on May 30, 2007]. Retrieved from the Internet: <URL: www.shazam.com/music/portal/sp/s/media-type/html/user/anon/page/default/template/Myhome/music.html>, 2 pages.52Supplemental EP Search Report for EP Application No. 06838486.6 dated Feb. 16, 2010, 8 pages.53Supplemental EP Search Report for EP Application No. 06838488.2 dated Feb. 16, 2010, 8 pages.54Training neural networks with additive noise in the desired signal Chuan Wang; Principe, J.C.; Neural Networks Proceedings, 1998. IEEE World Congress on Computational Intelligence. The 1998 IEEE International Joint Conference on vol. 2, May 4-9, 1998 pp. 1084-1089 vol. 2 Digital Object Identifier 10.11 09/IJCNN.1998.685923.55Training neural networks with additive noise in the desired signal Chuan Wang; Principe, J.C.; Neural Networks, IEEE Transactions on vol. 10, Issue 6, Nov. 1999 pp. 1511-1517, Digital Object Identifier 10.1109/72.809097.56Viola and Jones, "Robust Real-Time Object Detection," Int. J. Computer Vision, 2002, 25 pages.57Wang, "The Shazam Music Recognition Service," Communications of the ACM, Aug. 2006, 49(8): 5 pages.58'Wavelets for Computer Graphics: A Primer, Part 1' [online]. Stollnitz et al., 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: , 8 pages.59'Wavelets for Computer Graphics: A Primer, Part 2' [online]. Stollnitz et al., 1995, [retrieved on Nov. 21, 2006]. Retrieved from the Internet: , 9 pages.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8498951 *Sep 30, 2011Jul 30, 2013Google Inc.Approximate hashing functions for finding similar contentUS8504495 *Sep 30, 2011Aug 6, 2013Google Inc.Approximate hashing functions for finding similar contentUS9069750Jun 30, 2011Jun 30, 2015Abbyy Infopoisk LlcMethod and system for semantic searching of natural language textsUS9075864Dec 31, 2010Jul 7, 2015Abbyy Infopoisk LlcMethod and system for semantic searching using syntactic and semantic analysisUS9098489Jun 30, 2011Aug 4, 2015Abbyy Infopoisk LlcMethod and system for semantic searchingUS9189482Nov 8, 2012Nov 17, 2015Abbyy Infopoisk LlcSimilar document searchUS9336302Mar 14, 2013May 10, 2016Zuci Realty LlcInsight and algorithmic clustering for automated synthesisUS9495358Oct 10, 2012Nov 15, 2016Abbyy Infopoisk LlcCross-language text clustering* Cited by examinerClassifications U.S. Classification706/25International ClassificationG06N3/08, G06F15/18Cooperative ClassificationG06N3/08European ClassificationG06N3/08Legal EventsDateCodeEventDescriptionJan 27, 2011ASAssignmentOwner name: GOOGLE INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BALUJA, SHUMEET;COVELL, MICHELE;REEL/FRAME:025705/0089Effective date: 20070531May 22, 2015FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services