Sublinear time classification via feature padding and hashing

Patent metadata

Field	Value
Publication number	US-9940552-B1
Application number	US-201615069697-A
Country	US
Kind code	B1
Filing date	Mar 14, 2016
Priority date	Jul 15, 2013
Publication date	Apr 10, 2018
Grant date	Apr 10, 2018

Abstract

A linear function describing a framework for identifying an object of class k in an image sample x may be described by: w k *x+b k , where b k is the bias term. The higher the value obtained for a particular classifier, the better the match or strength of identity. A method is disclosed for classifier and/or content padding to convert dot-products to distances, applying a hashing and/or nearest neighbor technique on the resulting padded vectors, and preprocessing that may improve the hash entropy. A vector for an image, an audio, and/or a video may be received. One or more classifier vectors may be obtained. A padded image, video, and/or audio vector and classifier vector may be generated. A dot product may be approximated and a hashing and/or nearest neighbor technique may be performed on the approximated dot product to identify at least one class (or object) present in the image, video, and/or audio.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a request to identify a label from a set of possible labels that is relevant to a particular input having a particular media type;
receiving a first feature vector representing the particular input: obtaining a plurality of second feature vectors, each of the second feature vectors representing a respective label from the set of possible labels;
generating a transformed first feature vector and, for each second feature vector, a corresponding transformed second feature vector such that a distance between the transformed first feature vector and the transformed second feature vector approximates a likelihood that the label represented by the second feature vector corresponding to the transformed second feature vector is relevant to the particular input;
identifying a nearest transformed second feature vector to the transformed first feature vector from the plurality of transformed second feature vectors by searching the plurality of transformed second feature vectors for the transformed first feature vector using locality sensitive hashing or a tree-based search; and
classifying the label represented by the second feature vector corresponding to the nearest transformed second feature vector as being relevant to the particular input.

2. The method of claim 1 , wherein the nearest transformed second feature vector is identified using locality sensitive hashing with a random Gaussian projection or random Gaussian projections.

3. The method of claim 1 , wherein the nearest transformed second feature vector is identified using a spill tree-based search.

4. The method of claim 1 , wherein the particular input having the particular media type is an input digital image.

5. The method of claim 1 , wherein the particular input having the particular media type is an input digital video.

6. The method of claim 1 , wherein particular input having the particular media type is an input digital audio segment.

7. The method of claim 1 , further comprising:
receiving an additional first feature vector representing an additional input;
generating an adjusted additional first feature vector by subtracting an adjustment value from the additional first feature vector;
generating a transformed additional first feature vector based on the adjusted additional first feature vector such that a distance between the transformed additional first feature vector and each of the transformed second feature vectors approximates a likelihood that a label represented by the second feature vector corresponding to each of the transformed second feature vectors is relevant to the additional input; and
identifying a nearest transformed second feature vector to the transformed adjusted additional first feature vector from the plurality of transformed second feature vectors by searching the plurality of transformed second feature vectors for the transformed adjusted additional first feature vector using locality sensitivity hashing or a tree-based search.

8. The method of claim 7 , wherein the adjustment value comprises a mean of data comprising the first feature vector and the additional first feature vector.

9. The method of claim 1 , further comprising applying a linear transformation to the first feature vector.

10. The method of claim 1 , further comprising applying a linear transformation to the plurality of second feature vectors.

11. The computer-implemented method of claim 1 , wherein generating a transformed first feature vector and, for each second feature vector, a corresponding transformed second feature vector such that a distance between the transformed first feature vector and the transformed second feature vector approximates a likelihood that a label represented by the second feature vector corresponding to the transformed second feature vector is relevant to the particular input comprises:
generating a padded first feature vector based on the first feature vector, and
generating a plurality of padded second feature vectors based on the plurality of second feature vectors, each of the plurality of second feature vectors padded with a scalar corresponding to the second feature vector.

12. A system comprising:
one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:
receiving a request to identify a label from a set of possible labels that is relevant to a particular input having a particular media type;
receiving a first feature vector representing the particular input: obtaining a plurality of second feature vectors, each of the second feature vectors representing a respective label from the set of possible labels;
generating a transformed first feature vector and, for each second feature vector, a corresponding transformed second feature vector such that a distance between the transformed first feature vector and the transformed second feature vector approximates a likelihood that the label represented by the second feature vector corresponding to the transformed second feature vector is relevant to the particular input;
identifying a nearest transformed second feature vector to the transformed first feature vector from the plurality of transformed second feature vectors by searching the plurality of transformed second feature vectors for the transformed first feature vector using locality sensitive hashing or a tree-based search; and
classifying the label represented by the second feature vector corresponding to the nearest transformed second feature vector as being relevant to the particular input.

13. The system of claim 12 , wherein the nearest transformed second feature vector is identified using locality sensitive hashing with a random Gaussian projection or random Gaussian projections.

14. The system of claim 12 , wherein the nearest transformed second feature vector is identified using a spill tree-based search.

15. The system of claim 12 , wherein the particular input having the particular media type is an input digital image.

16. The system of claim 12 , wherein the particular input having the particular media type is an input digital video.

17. The system of claim 12 , wherein the particular input having the particular media type is an input digital audio segment.

18. The system of claim 12 , wherein generating a transformed first feature vector and, for each second feature vector, a corresponding transformed second feature vector such that a distance between the transformed first feature vector and the transformed second feature vector approximates a likelihood that a label represented by the second feature vector corresponding to the transformed second feature vector is relevant to the particular input comprises:
generating a padded first feature vector based on the first feature vector, and
generating a plurality of padded second feature vectors based on the plurality of second feature vectors, each of the plurality of second feature vectors padded with a scalar corresponding to the second feature vector.

19. One or more computer-readable media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
receiving a request to identify a label from a set of possible labels that is relevant to a particular input having a particular media type;
receiving a first feature vector representing the particular input: obtaining a plurality of second feature vectors, e

Assignees

• Google Llc

Inventors

• Ioffe Sergey
• Toshev Alexander Toshkov

Classifications

• G06V10/761 Primary

  Proximity, similarity or dissimilarity measures · CPC title

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F18/2431

  Multiple classes · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06F18/24

  Classification techniques · CPC title