Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies
- 1 December 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 265-272
- https://doi.org/10.1109/iccv.2013.40
Abstract
Many methods have been proposed to solve the image classification problem for a large number of categories. Among them, methods based on tree-based representations achieve good trade-off between accuracy and test time efficiency. While focusing on learning a tree-shaped hierarchy and the corresponding set of classifiers, most of them [11, 2, 14] use a greedy prediction algorithm for test time efficiency. We argue that the dramatic decrease in accuracy at high efficiency is caused by the specific design choice of the learning and greedy prediction algorithms. In this work, we propose a classifier which achieves a better trade-off between efficiency and accuracy with a given tree-shaped hierarchy. First, we convert the classification problem as finding the best path in the hierarchy, and a novel branch-and-bound-like algorithm is introduced to efficiently search for the best path. Second, we jointly train the classifiers using a novel Structured SVM (SSVM) formulation with additional bound constraints. As a result, our method achieves a significant 4.65%, 5.43%, and 4.07% (relative 24.82%, 41.64%, and 109.79%) improvement in accuracy at high efficiency compared to state-of-the-art greedy "tree-based" methods [14] on Caltech-256 [15], SUN [32] and Image Net 1K [9] dataset, respectively. Finally, we show that our branch-and-bound-like algorithm naturally ranks the paths in the hierarchy (Fig. 8) so that users can further process them.Keywords
This publication has 15 references indexed in Scilit:
- Large-scale image classification: Fast feature extraction and SVM trainingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Articulated pose estimation with flexible mixtures-of-partsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Convolutional deep belief networks for scalable unsupervised learning of hierarchical representationsPublished by Association for Computing Machinery (ACM) ,2009
- Learning and using taxonomies for fast visual categorizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Exploiting Object Hierarchy: Combining Models from Different Category LevelsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Automatic Video Genre Categorization using Hierarchical SVMPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Multiclass boosting with repartitioningPublished by Association for Computing Machinery (ACM) ,2006
- Sharing features: efficient boosting procedures for multiclass object detectionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Support vector machine learning for interdependent and structured output spacesPublished by Association for Computing Machinery (ACM) ,2004
- An Automatic Method of Solving Discrete Programming ProblemsEconometrica, 1960