Efficient Large Scale Image Classification via Prediction Score Decomposition
There has been growing interest in reducing the test time complexity of multi-class classification problems with large numbers of classes. The key idea to solve it is to reduce the number of classifier evaluations used to predict labels. The state-of-the-
- PDF / 374,657 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 216 Views
ersity of Information Technology, VNU-HCM, Ho Chi Minh City, Vietnam {duyld,dungmt,thanhnd,ducda}@uit.edu.vn National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, Japan {ledduy,satoh}@nii.ac.jp
Abstract. There has been growing interest in reducing the test time complexity of multi-class classification problems with large numbers of classes. The key idea to solve it is to reduce the number of classifier evaluations used to predict labels. The state-of-the-art methods usually employ the label tree approach that usually suffers the well-know error propagation problem and it is difficult for parallelization for further speedup. We propose another practical approach, with the same goal of using a small number of classifiers to achieve a good trade-off between testing efficiency and classification accuracy. The proposed method analyzes the correlation among classes, suppresses redundancy, and generates a small number of classifiers that best approximate the prediction scores of the original large number of classes. Different from label-tree methods in which each test example follows a different traversing path from the root to a leaf node and results in a different set of classifiers each time, the proposed method applies the same set of classifiers to all test examples. As a result, it is much more efficient in practice, even in the case of using the same number of classifier evaluations as the label-tree methods. Experiments on several large datasets including ILSVRC20101K, SUN-397, and Caltech-256 show the efficiency of our method. Keywords: Large decomposition
1
scale
classification
·
Label
tree
·
Matrix
Introduction
Multi-class classification, which is the problem of classifying one example with a predefined set of classes, is one of the fundamental problems of computer vision. The availability of large-scale datasets, such as ImageNet [9], SUN [37], and Caltech-256 [17], that have many training and testing examples and many classes has posed significant challenges in computational issues. Electronic supplementary material The online version of this chapter (doi:10. 1007/978-3-319-46466-4 46) contains supplementary material, which is available to authorized users. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part VI, LNCS 9910, pp. 770–785, 2016. DOI: 10.1007/978-3-319-46466-4 46
Large Scale Image Classification via Prediction Score Decomposition
771
One of the challenges that has attracted growing attention is how to discriminate a large number of classes. The complexity in test time grows linearly with the number of classes when using the standard one-versus-all (OvA) approach [1,31], and this is prohibitive for large-scale datasets used in practical applications. The key idea to solve this problem is to reduce the number of classifiers evaluated for each testing example. The Error Correcting Output Codes (ECOC) based approaches [2,8,12–14, 30,39,40] combines multi binary classifiers to solve the multi-class classification problem. Given a testing example, the set of bit pre
Data Loading...
