Abstract

In this paper we study how to perform ob ject classification in a principled way that exploits the rich structure of real world labels. We develop a new model that allows encoding of flexible relations between labels. We introduce Hierarchy and Exclusion (HEX) graphs, a new for- malism that captures semantic relations between any two labels applied to the same ob ject: mutual exclusion, overlap and subsumption. We then provide rigorous theoretical analysis that illustrates properties of HEX graphs such as consistency, equivalence, and computational implications of the graph structure. Next, we propose a probabilistic classification model based on HEX graphs and show that it enjoys a number of de- sirable properties. Finally, we evaluate our method using a large-scale benchmark. Empirical results demonstrate that our model can signifi- cantly improve ob ject classification by exploiting the label relations.