Joint embedding for item association

• US 9,110,922 B2
• Filed: 02/01/2011
• Issued: 08/18/2015
• Est. Priority Date: 02/01/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bengio, Samy, Weston, Jason
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US13/019,221
• Publication Number:
  US 20110191374A1
• Time in Patent Office: 1,659 Days
• Field of Search: 707/705, 707/736
• US Class Current: 1/1
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/53 Querying
• CPC Class Codes: G06F 16/9554 by using bar codes

Abstract

Methods and systems to associate semantically-related items of a plurality of item types using a joint embedding space are disclosed. The disclosed methods and systems are scalable to large, web-scale training data sets. According to an embodiment, a method for associating semantically-related items of a plurality of item types includes embedding training items of a plurality of item types in a joint embedding space configured in a memory coupled to at least one processor, learning one or more mappings into the joint embedding space for each of the item types to create a trained joint embedding space and one or more learned mappings, and associating one or more embedded training items with a first item based upon a distance in the trained joint embedding space from the first item to each said associated embedded training items. Exemplary item types that may be embedded in the joint embedding space include images, annotations, audio and video.

Claims

1. A method for associating semantically-related items of a plurality of item types, comprising:

(a) embedding, by one or more computers, training items of the plurality of item types in a joint embedding space having more than two dimensions configured in a memory coupled to at least one processor, wherein each of the dimensions is defined by a real-valued axis, wherein each embedded training item corresponds to a respective location in the joint embedding space, wherein said each embedded training item is represented by a respective vector of real numbers corresponding to the respective location, and wherein each of the real numbers of the vector corresponds to a mapping of the respective location to one of the dimensions;

(b) learning, by the one or more computers, one or more mappings into the joint embedding space for each of the plurality of item types to create a trained joint embedding space and one or more learned mappings, the learning including;

selecting, based on known relationships between the training items, a related pair of the training items that includes a first item and a second item, wherein the first item and the second item are separated by a first distance in the joint embedding space;

selecting a third item that is less related to the first item than the second item, but is closer to the first item than the second item in the joint embedding space; and

adjusting a mapping function to increase a distance between the first item and the third item relative to a distance between the first item and the second item; and

(c) associating, by the one or more computers, one or more of the embedded training items with a first item based upon a distance in the trained joint embedding space from the first item to each said associated embedded training items, wherein each said distance is determined based upon a first vector of real numbers corresponding to the first item and a second vector of real numbers corresponding to a respective one of the associated embedded training items.

2. The method of claim 1, further comprising:

(d) embedding the first item at a first location, determined by applying the one or more learned mappings for a first item type of the plurality of item types, in the trained joint embedding space.

3. The method of claim 2, further comprising:

(e) annotating the first item based upon the one or more associated embedded training items closest to the first item in the trained joint embedding space.

4. The method of claim 1, wherein the adjusting step (iii) further comprises updating a respective vector of real numbers to include one or more changed location of the third item.

5. The method of claim 1, further comprising:

moving at least one of the first or third items in the joint embedding space such that a distance in the trained joint embedding space.

6. The method of claim 5, wherein the moving is based upon a stochastic gradient descent technique.

7. The method of claim 1, wherein the adjusting is based upon a stochastic gradient descent technique.

8. The method of claim 1, wherein the selecting step (i) comprises:

iteratively choosing an item as the third item until a distance in the trained joint embedding space from the first item to the third item is less than the distance between the first and second items; and

estimating a rank of the third item in relation to the second item based upon a number of iterations required to choose the third item.

9. The method of claim 5, wherein the moving comprises:

moving, based on the adjusted mapping function, at least one of the first, second, or third items in the joint embedding space such that a distance in the trained joint embedding space between the first and second items is less than a distance between the first and third items.

10. The method of claim 9, wherein the moving is based upon a stochastic gradient descent technique weighted based upon the estimated rank.

11. The method of claim 1, wherein the learning step (b) further comprises:

(iv) repeating at least steps (i)-(iii) until a predetermined termination criteria is satisfied.

12. The method of claim 1, wherein the learning step (b) further comprises:

learning a first mapping function for all items of a first item type; and

learning respective mapping functions for each of a plurality of items of a second item type.

13. The method of claim 1, further comprising:

identifying a query subject in the trained joint embedding space, wherein the query subject is an embedded training item;

determining one or more trained embedded items located within a predetermined distance of the query subject as result items; and

outputting the result items.

22. The method of claim 1, further comprising:

receiving a query;

determining, in response to the query, a location in of the query in the joint embedding space;

identifying one or more results based upon one or more items embedded in the joint embedding space closest to the location; and

returning the one or more results as a response to the query.

23. The method of claim 22, wherein the determining the location comprises:

determining a query item based upon the received query; and

embedding the query item at the location, wherein the location is determined by applying at least one learned mapping for an item type of the query item.

24. The method of claim 22, wherein the query includes an artist'"'"'s name or a song and the one or more results include at least one of a second artist'"'"'s name and a second song, wherein the at least one of a second artist'"'"'s name and a second song is associated with the artist'"'"'s name or the song.

25. The method of claim 22, wherein the query includes a tag, and the one or more results include at least one image, wherein the image is associated with the tag.

14. A system for associating semantically-related items of a plurality of item types, comprising:

at least one processor;

a memory coupled to the at least one processor;

a joint embedding space configurator configured to embed training items of the of the plurality of item types in a joint embedding space in the memory, wherein the joint embedding space has more than two dimensions, wherein each of the dimensions is defined by a real-valued axis, wherein each embedded training item corresponds to a respective location in the joint embedding space, wherein said each embedded training item is represented by a respective vector of real numbers corresponding to the respective location, and wherein each of the real numbers of the vector corresponds to a mapping of the respective location to one of the dimensions;

a mapper configured to learn one or more mappings into the joint embedding space for each of the item types to create a trained joint embedding space and one or more learned mappings, wherein the mapper learns the one or more mappings by performing operations including;

selecting, based on known relationships between the training items, a related pair of the training items that includes a first item and a second item, wherein the first item and the second item are separated by a first distance in the joint embedding space;

selecting a third item that is less related to the first item than the second item, but is closer to the first item than the second item in the joint embedding space; and

adjusting a mapping function to increase a distance between the first item and the third item relative to a distance between the first item and the second item; and

an item associator configured associate one or more of the embedded training items with a first item based upon a distance in the trained joint embedding space from the first item to each associated embedded training items, wherein each said distance is determined based upon a first vector of real numbers corresponding to the first item and a second vector of real numbers corresponding to a respective one of the associated embedded training items.

15. The system of claim 14, further comprising:

a new item embedder configured to embed a first item at a first location in the trained joint embedding space, the first location determined by applying a learned mapping for a first item type of the plurality of item types.

16. The system of claim 15, further comprising:

an annotator configured to annotate the first item based upon the one or more associated embedded training items closest to the first item in the trained joint embedding space.

17. The system of claim 15, wherein the mapper is further configured to learn the mapping for one or more item types using a stochastic gradient technique.

18. The system of claim 17, wherein the mapper is further configured to:

iteratively choose an item as the third item until a distance in the trained joint embedding space from the first item to the third item is less than the distance between the first and second items; and

estimate a rank of the third item in relation to the second item based upon a number of iterations required to choose the third item; and

move at least one of the first, second, or third items in the joint embedding space such that a distance in the trained joint embedding space between the first and second items is less than a distance between the first and third items, wherein the move is based on a stochastic gradient technique weighted based upon the estimated rank.

19. The system of claim 14, wherein the joint embedding space comprises a predetermined number of real valued axis.

20. The system of claim 14, further comprising:

a semantic query module configured to;

identify a query subject in the trained joint embedding space, wherein the query subject is an embedded training item; and

determine one or more trained embedded items located within a predetermined distance of the query subject as result items.

21. A non-transitory computer readable medium storing instructions wherein said instructions when executed cause at least one processor to associate semantically-related items of a plurality of item types using a method comprising:

embedding training items of the plurality of item types in a joint embedding space configured in a memory coupled to at least one processor, wherein the joint embedding space has more than two dimensions, wherein each of the dimensions is defined by a real-valued axis, and wherein each embedded training item corresponds to a respective location in the joint embedding space, wherein said each embedded training item is represented by a respective vector of real numbers corresponding to the respective location, and wherein each of the real numbers of the vector corresponds to a mapping of the respective location to one of the dimensions;

learning one or more mappings into the joint embedding space for each of the item types to create a trained joint embedding space and one or more learned mappings, the learning including;

selecting, based on known relationships between the training items, a related pair of the training items that includes a first item and a second item, wherein the first item and the second item are separated by a first distance in the joint embedding space;

selecting a third item that is less related to the first item than the second item, but is closer to the first item than the second item in the joint embedding space; and

adjusting a mapping function to increase a distance between the first item and the third item relative to a distance between the first item and the second item; and

associating one or more of the embedded training items with a first item based upon a distance in the trained joint embedding space from the first item to each said associated embedded training items, wherein each said distance is determined based upon a first vector of real numbers corresponding to the first item and a second vector of real numbers corresponding to a respective one of the associated embedded training items.