• Thomas Mensink , Jakob Verbeek , Tiberio Caetano
NIPS, Sierra Nevada, Spain, December 16-17, 2011.
Ranking-based performance measures, such as precision-at-k and averageprecision,
are frequently used in information retrieval and image annotation. Often
the loss used to train models for such tasks is different from the loss that is used
to measure performance at test time. Only recently methods have appeared that
explicitly train to minimize such ranking losses. Motivated by image annotation
tasks where there are strong dependencies among the labels that should be ranked,
we are interested in accommodating for pairwise interactions in ranking models:
a feature not present in existing methods that optimize for ranking losses. We con
sider a generic family of such ranking models, where inference takes the form of a
quadratic assignment problem which is generally NP-hard. We identify a subclass
of such models with star-structured interactions, where inference can be in poly
nomial time. In particular, for the precision-at-k loss, this leads to a model where
inference is linear in the number of elements to rank, and exponential in the size
of the number of elements in the fully connected clique at the center of the star.
We validate the model on a public benchmark image annotation data set.
Report number: