LABEL EMBEDDING TREES FOR MULTI-CLASS TASKS

• US 20120082371A1
• Filed: 10/01/2010
• Published: 04/05/2012
• Est. Priority Date: 10/01/2010
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bengio, Samy, Weston, Jason E.
• Application Number:
  US12/896,318
• Publication Number:
  US 20120082371A1
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for label embedding trees for large multi-class tasks. In one aspect, a method includes mapping each image in a plurality of images and each label in a plurality of labels into a multi-dimensional label embedding space. A tree of label predictors is trained with the plurality of mapped images such that an error function is minimized in which the error function counts an error for each mapped image if any of the label predictors at any depth of the tree incorrectly predicts that the mapped image belongs to the label predictor'"'"'s respective label set.

Claims

1. A computer-implemented method comprising:

mapping each image in a plurality of images and each label in a plurality of labels into a multi-dimensional label embedding space, in which a mapped image has a greater similarity to a mapped label that is the particular mapped image'"'"'s true label than to other mapped labels in the label embedding space;

identifying a tree with a plurality of nodes and a plurality of edges which are ordered pairs of parent and child nodes, in which each node represents a label predictor for a respective label set, and in which a label set of a root node of the tree encompasses the plurality of mapped labels and each respective child node label set is a subset of the respective label set of the child'"'"'s parent node; and

training the label predictors in the tree with the plurality of mapped images such that an error function is minimized in which the error function counts an error for each mapped image in the plurality of mapped images if any of the label predictors at any depth of the tree incorrectly predicts that the mapped image belongs to the label predictor'"'"'s respective label set.

2. The method of claim 1 in which the error function counts an error by checking, out of all the label predictors that have a common parent, if the label predictor whose respective label set contains the true label for the particular mapped image produces a highest score for the mapped image.

3. The method of claim 1, further comprising using the tree to classify a first image.

4. The method of claim 3 in which using the tree to classify the first image comprises mapping the first image to the label embedding space.

5. The method of claim 1, further comprising learning one or more mappings into the label embedding space for each image in the plurality of images and each label in the plurality of labels.

6. The method of claim 1 in which the similarity is based on a Euclidian distance between a position of the particular mapped image in the label embedding space and a position of the mapped label that is the particular mapped image'"'"'s true label in the label embedding space.

7. The method of claim 1 in which each image in the plurality of images has a respective representation in a first multi-dimensional space and in which the label embedding space has a lower dimensionality than the first space.

8. A system comprising:

a storage medium including instructions; and

one or more data processing apparatuses operable to execute the instructions to perform operations comprising;

mapping each image in a plurality of images and each label in a plurality of labels into a multi-dimensional label embedding space, in which a mapped image has a greater similarity to a mapped label that is the particular mapped image'"'"'s true label than to other mapped labels in the label embedding space;

identifying a tree with a plurality of nodes and a plurality of edges which are ordered pairs of parent and child nodes, in which each node represents a label predictor for a respective label set, and in which a label set of a root node of the tree encompasses the plurality of mapped labels and each respective child node label set is a subset of the respective label set of the child'"'"'s parent node; and

training the label predictors in the tree with the plurality of mapped images such that an error function is minimized in which the error function counts an error for each mapped image in the plurality of mapped images if any of the label predictors at any depth of the tree incorrectly predicts that the mapped image belongs to the label predictor'"'"'s respective label set.

9. The system of claim 8 in which the error function counts an error by checking, out of all the label predictors that have a common parent, if the label predictor whose respective label set contains the true label for the particular mapped image produces a highest score for the mapped image.

10. The system of claim 8, further including operations comprising using the tree to classify a first image.

11. The system of claim 10 in which using the tree to classify the first image comprises mapping the first image to the label embedding space.

12. The system of claim 8, further comprising learning one or more mappings into the label embedding space for each image in the plurality of images and each label in the plurality of labels.

13. The system of claim 8 in which the similarity is based on a Euclidian distance between a position of the particular mapped image in the label embedding space and a position of the mapped label that is the particular mapped image'"'"'s true label in the label embedding space.

14. The system of claim 8 in which each image in the plurality of images has a respective representation in a first multi-dimensional space and in which the label embedding space has a lower dimensionality than the first space.

15. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

mapping each image in a plurality of images and each label in a plurality of labels into a multi-dimensional label embedding space, in which a mapped image has a greater similarity to a mapped label that is the particular mapped image'"'"'s true label than to other mapped labels in the label embedding space;

identifying a tree with a plurality of nodes and a plurality of edges which are ordered pairs of parent and child nodes, in which each node represents a label predictor for a respective label set, and in which a label set of a root node of the tree encompasses the plurality of mapped labels and each respective child node label set is a subset of the respective label set of the child'"'"'s parent node; and

training the label predictors in the tree with the plurality of mapped images such that an error function is minimized in which the error function counts an error for each mapped image in the plurality of mapped images if any of the label predictors at any depth of the tree incorrectly predicts that the mapped image belongs to the label predictor'"'"'s respective label set.

16. The storage medium of claim 15 in which the error function counts an error by checking, out of all the label predictors that have a common parent, if the label predictor whose respective label set contains the true label for the particular mapped image produces a highest score for the mapped image.

17. The storage medium of claim 15, further including operations comprising using the tree to classify a first image.

18. The storage medium of claim 17 in which using the tree to classify the first image comprises mapping the first image to the label embedding space.

19. The storage medium of claim 15, further comprising learning one or more mappings into the label embedding space for each image in the plurality of images and each label in the plurality of labels.

20. The storage medium of claim 15 in which the similarity is based on a Euclidian distance between a position of the particular mapped image in the label embedding space and a position of the mapped label that is the particular mapped image'"'"'s true label in the label embedding space.

21. The storage medium of claim 15 in which each image in the plurality of images has a respective representation in a first multi-dimensional space and in which the label embedding space has a lower dimensionality than the first space.