Efficient large-scale multi-class image classification by learning balanced trees

Large-scale multi-class image classification is essential for big data applications. One of the challenges is to deal with situations in which the number of classes is very large and for which the standard one-versus-all method is not appropriate because its computational complexity is linear in the number of classes. Using a label tree is a popular way to reduce complexity. By organizing classes into a hierarchical structure, the number of classifier evaluations of a test sample when traveling from the root node to a leaf node is significantly reduced. Having a balanced learned tree is essential to this approach. The current methods for learning the tree structure use clustering techniques, such as k-means or spectral clustering, to group confusing classes into clusters associated with the nodes. However, the output tree in such cases might not be balanced. In this paper, we propose a method for learning effective and balanced trees by jointly optimizing balance and confusion constraints. Experimental results on large-scale datasets including Caltech-256, SUN-397, ILSVRC2010-1K, and ImageNet-10K, show that our method outperforms other state-of-the-art methods.