NIPS 2010 - Label Embedding Trees for Large Multi-Class Tasks [edit]

Label Embedding Trees for Large Multi-Class Tasks by Samy Bengio, Jason Weston, David Gran is a paper about coping with classification in the presents huge amounts of data and many many classes. Of course the image net challenge comes to mind. But what they actually did is doing classification on all of image net, which is about 16.000 classes and over a million instances.
This work focuses on very fast recall but is very expensive to train - apparently the model was trained in a Google cluster.

This paper explores two ideas: hierarchical classification and low dimensional embeddings.
For the hierarchical classification part, a tree of label sets is build where the leaves are single classes.
Starting from all classes at the root, the set of classes is split into subsets similar classes which are represented by new nodes. This is done by training a one-vs-rest classifier and inspecting the confusion matrix. Classes that are easy to confuse are put into the same node.

At test-time, only log(n) many classifiers, each with only a few classes, have to be evaluated.
One obvious downside of the procedure is, that it assumes it is feasible to train many one-vs-rest classifiers for the root. [edit] It seems I misunderstood the procedure. Training of all one-vs-rest classifiers is used only for  the root. [/edit] If you have a cluster - no problem. If you don't, this is not for you.

The other part of the paper is about low dimensional embeddings for classifications. Here both the image features and the labels are jointly embedded into a low dimensional space using a linear transformation.
Then classification is done by finding the nearest label neighbour to a given embedded image. The idea is a straight forward and makes recall very fast.

The paper contains evaluations on both the tree structure with a simple classifier, the embedding method alone and a combination using the embedding as a classifier for the tree structure.

The paper also features an experiment where the actual category tree structure of image net is used instead of the learned tree. The results are quite bad. This is very expected since the semantic class hierarchy has not much to do with the visual appearances of objects and so very tough decisions are made very early.

I very much like the idea of learning a tree structure of labels on datasets with a lot of classes, but as I said before, this approach is very impractical if you have limited resources - like me with just about 25 CPUs and GPUs each.

Comments

  1. AnonymousJanuary 11, 2011 at 5:39 PM

    2 remarks :
    - I think the one vs rest classifiers are trained only once. After you can use a submatrix of the original confusion matrix for every internal node if you subsequent splits.

    - with 25 cpus and GPUs, you can deal with even bigger problems (datasets) than those discibed in the paper if you parallelize your computations ...

    ReplyDelete
  2. Andreas MuellerJanuary 18, 2011 at 6:10 PM

    Thanks for your comment. I took a look at the paper and you are right about computing the confusion matrix only once. When I wrote the entry, I had only talked to Samy Bengio at the poster.
    Even though we talked for quite a while, it seems I have misunderstood the approach. Thanks for pointing that out.
    Andy

    ReplyDelete
  3. UnknownFebruary 12, 2014 at 12:26 PM

    Hi,

    Thanks for your informative blog post.

    Actually I am also working on label tree embeddings method nowadays. Have you implemented it anyway? If yes, would you be considering of sharing it?

    Thanks again,
    Mert

    ReplyDelete

Post a Comment

Popular posts from this blog

Machine Learning Cheat Sheet (for scikit-learn)

Image
As you hopefully have heard, we at scikit-learn are doing a user survey (which is still open by the way). One of the requests there was to provide some sort of flow chart on how to do machine learning. As this is clearly impossible, I went to work straight away. This is the result: [edit2] clarification: With ensemble classifiers and ensemble regressors I mean random forests , extremely randomized trees, gradient boosted trees , and the soon-to-be-come weight boosted trees (adaboost). [/edit2] Needless to say, this sheet is completely authoritative.
Read more

A Wordcloud in Python

Image
Last week I was at Pycon DE , the German Python conference. After hacking on scikit-learn a lot last week, I decided to to something different on my way back, that I had planned for quite a while: doing a wordl -like word cloud . I know, word clouds are a bit out of style but I kind of like them any way. My motivation to think about word clouds was that I thought these could be combined with topic-models to give somewhat more interesting visualizations. So I looked around to find a nice open-source implementation of word-clouds ... only to find none. (This has been a while, maybe it has changed since). While I was bored in the train last week, I came up with this code . A little today-themed taste:
Read more

MNIST for ever....

Image
[update] This post is a bit old, but many people still seem interested. So just a short update: Nowadays I would use Python and scikit-learn to do this. Here is an example of how to do cross-validation for SVMs in scikit-learn. Scikit-learn even downloads MNIST for you. [/update] MNIST is, for better or worse, one of the standard benchmarks for machine learning and is also widely used in then neural networks community as a toy vision problem. Just for the unlikely case that anyone is not familiar with it: It is a dataset of handwritten digits, 0-9, in black on white background. It looks something like this: There are 60000 training and 10000 test images, each 28x28 gray scale. There are roughly the same number of examples of each category in the test and training datasets. I used it in some papers myself even though there are some reasons why it is a little weird. Some not-so-obvious (or maybe they are) facts are: - The images actually contain a 20x20 patch of digi...
Read more

Python things you never need: Empty lambda functions

Ever wanted to create an empty Python function in-line? No? Me neither. But my coworker does... We found the answer: <pre> x = lambda : None </pre> If you ever needed this, please tell me ;) [Edit] Apparently some people do need it :) Btw, most people seem to try Most people try lambda: pass first. But you have to remember, the thing at the right side of the colon is the return value of the function, not the body! So an expression is needed, not a statement. [\Edit]
Read more