Abstract

In computer vision efficient multi-class classification is be- coming a key problem as the field develops and the number of ob ject classes to be identified increases. Often ob jects might have some sort of structure such as a taxonomy in which the mis-classification score for ob- ject classes close by, using tree distance within the taxonomy, should be less than for those far apart. This is an example of multi-class classifica- tion in which the loss function has a special structure. Another example in vision is for the ubiquitous pictorial structure or parts based model. In this case we would like the mis-classification score to be proportional to the number of parts misclassified. It transpires both of these are examples of structured output rank- ing problems. However, so far no efficient large scale algorithm for this problem has been demonstrated. In this work we propose an algorithm for structured output ranking that can be trained in a time linear in the number of samples under a mild assumption common to many computer vision problems: that the loss function can be discretized into a small number of values. We show the feasibility of structured ranking on these two core com- puter vision problems and demonstrate a consistent and substantial im- provement over competing techniques. Aside from this, we also achieve state-of-the art results for the PASCAL VOC human layout problem.