Joint Embedding for Item Association

• US 20110191374A1
• Filed: 02/01/2011
• Published: 08/04/2011
• 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
• Granted Patent: US 9,110,922 B2
• Time in Patent Office: Days
• US Class Current: 707/780
• 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 training items of the plurality of item types in a joint embedding space configured in a memory coupled to at least one processor;

(b) 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

(c) 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.

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 mapping 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.

4. The method of claim 2, wherein the learning step (b) comprises:

(i) selecting a second item, a third item, and a fourth item from the embedded training items, wherein the second item and the third item are related, and wherein the second item and the fourth item are not related;

(ii) determining that a first distance is less than a second distance, wherein the first distance is a distance between the second item and the third item in the joint embedding space, and wherein the second distance is a distance between the second item and the fourth item in the joint embedding space; and

(iii) adjusting the one or more learned mappings based upon the determining.

5. The method of claim 4, wherein the adjusting step (iii) further comprises

changing locations in the joint embedding space of at least one of the second, third, and fourth items.

6. The method of claim 5, wherein the changing locations step comprises:

moving at least one of the second, third, or fourth item in the joint embedding space such that a distance between the second and third items is less than a distance from the second item to the fourth items.

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

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

9. The method of claim 4, wherein the selecting step (i) comprises:

iteratively choosing an item as the fourth item until a distance from the second item to the selected item is less than the distance between the second and third items; and

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

10. The method of claim 9, wherein the changing locations step comprises:

moving at least one of the second, third, or fourth item in the joint embedding space such that a distance between the second and third items is less than a distance from the second item to the fourth item.

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

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

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

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

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

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

14. 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.

15. 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 plurality of item types in a joint embedding space in the memory;

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; and

an item associator configured associate 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.

16. The system of claim 15, further comprising:

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

17. The system of claim 16, further comprising:

an annotator configured to annotate the first item based upon the one or more associated embedded training items.

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

19. The system of claim 18, wherein the item associator is further configured to:

iteratively choose an item as the fourth item until a distance from the second item to the selected item is less than the distance between the second and third items; and

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

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

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

21. The system of claim 15, 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.

22. A 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;

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.

23. A method for responding to a query, comprising:

receiving the query;

determining, in response to the query, a location in a joint embedding space configured in a memory coupled to at least one processor, wherein a distance between a first item and a second item embedded in the joint embedding space corresponds to a semantic relationship between the first and second items, and wherein items of a plurality of item types are embedded 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.

24. The method of claim 23, 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.

25. The method of claim 23, 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.

26. The method of claim 23, 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.

27. A method of querying, comprising:

transmitting a query to a server, wherein the server includes a joint embedding space configured in a memory coupled to at least one processor, wherein a distance between a first item and a second item embedded in the joint embedding space corresponds to a semantic relationship between the first item and the second item, wherein items of a plurality of item types are embedded in the joint embedding space; and

receiving a response from the server, wherein the response is formed by the server by identifying a location corresponding to the query in the joint embedding space, and by identifying one or more result items closest to the identified location.