In addition, a feature map is used to reformulate the sum-match kernel function as a dot product of two mean feature vectors in a mapped-feature space. Furthermore, we proposed an algorithm for learning a balanced tree which gains the computational efficiency in classification. We carried out experiments on benchmark datasets including Caltech-256, SUN-397, and ImageNet-1K. The evaluation results indicated that our method achieves a significant improvement in terms of accuracy and efficiency compared to other methods. In particular, our method achieved in accuracy on ImageNet-1K, compared to of the Bengio et al.’s method. | Journal of Computer Science and Cybernetics, , (2016), 133–152 DOI no. USING SUM MATCH KERNEL WITH BALANCED LABEL TREE FOR LARGE-SCALE IMAGE CLASSIFICATION TIEN-DUNG MAI University of Information Technology, Vietnam National University-Ho Chi Minh City dungmt@ Abstract. Large-scale image classification is a fundamental problem in computer vision due to many real applications in various domains. One of the popular methods is to train one-versus-all binary classifiers independently for each class. Although this method is simple, they are impracticable in the case of a large number of classes because their testing complexity grows linearly with the number of classes. Another is to organize classes into a hierarchical tree structure. The number of classifier evaluations of a test sample when traveling from the root to a leaf node is significantly reduced. A challenging issue is how to learn a tree structure which achieves both classification accuracy and computational efficiency. The current methods use a confusion matrix and spectral clustering techniques to group confusing classes into clusters associated with the nodes. However, training one-vs-all classifiers used to calculate the confusion matrix is costly for a large number of classes. Moreover, the output tree might not be balanced because the objective function of spectral clustering penalizes unbalanced partitions. In this paper, we suggested a novel method to learn the tree structure by using a spectral clustering algorithm and a similarity matrix. Here, the similarity between two classes is exactly measured by the sum-match kernel. In addition, a feature map is used to reformulate the sum-match kernel function as a dot product of two mean feature vectors in a mapped-feature space. Furthermore, we proposed an algorithm for learning a balanced tree which gains the computational efficiency in classification. We carried out experiments on benchmark datasets .
