of instances from the background dominate the effect of the Acknowledgements evidence instances on SIVAL.Because the background can appear in either positive or negative bags,the features based This research has been supported by General Research Fund 621407 from the Research Grants Council of the Hong on instances from the background actually have very low discrimination ability.Hence,the useful features in MILES Kong Special Administrative Region,China.We thank are very limited.As a result,MILES will be more easily Dr.Yixin Chen for sharing the code and data for MILES. affected by noise on the SIVAL data set.This might be the cause for the phenomenon that MILES is much more sensi- References tive to noise on the SIVAL data set. [1]M.Belkin,P.Niyogi,and V.Sindhwani.Manifold regular- ization:A geometric framework for learning from labeled 5.3.Computation Cost and unlabeled examples.Journal of Machine Learning Re- Table 4 lists the training time (on a 2GHz PC with IG search,.7:2399-2434,2006.8 memory)required by DD-SVM,MILES,and EC-SVM. [2]C.-C.Chang and C.-J.Lin.LIBSVM:a Library for "SIVAL"refers to the time for training 25 classifiers for Support Vector Machines,2001.Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm.5,7 all the 25 categories when four positive and four negative [3]Y.Chen,J.Bi,and J.Z.Wang.MILES:Multiple-instance images are used as the training set on the SIVAL data set. learning via embedded instance selection.IEEE Trans.Pat- "COREL"refers to the time for training 20 classifiers for all 1 ern Anal..Mach.Intell.,28(12:1931-1947,2006.2,4,5,6 the 20 categories when four positive and four negative im- 7,8 ages are used as the training set on the COREL data set.To [4]Y.Chen and J.Z.Wang.Image categorization by learning test the scalability of EC-SVM.we also evaluate the train- and reasoning with regions.Journal of Machine Learning ing time on the COREL data set based on a training set of Research,5:913-939,2004.2.4 500 images,denoted as"COREL2",which has been used [5]S.R.Cholleti,S.A.Goldman,and R.Rahmani.Mi- for efficiency comparison in MILES [3].We can see that Winnow:A new multiple-instance learning algorithm.In EC-SVM is much more efficient. 18th IEEE International Conference on Tools with Artificial Intelligence,pages 336-346,2006.5 Table 4.Computation time comparison (in minutes). [6]T.G.Dietterich,R.H.Lathrop,and T.Lozano-Perez.Solv- SIVAL COREL COREL2 ing the multiple instance problem with axis-parallel rectan- DD-SVM N/A N/A 40 gles.Artif.1nell,891-2):31-71,1997.1 MILES 0.34 0.064 0.85 [7]W.-J.Li and D.-Y.Yeung.MILD:Multiple-instance learning EC-SVM 0.23 0.005 0.2 via disambiguation.IEEE Transactions on Knowledge and Data Engineering,In Press.I 6.Conclusion and Future Work [8]O.Maron and T.Lozano-Perez.A framework for multiple- instance learning.In Advances in Neural Information Pro- Considering the high computation cost and high noise cessing Systems,1997.2.3 sensitivity of DD-SVM,and the very high dimensionality of [9]G.-J.Qi,X.-S.Hua,Y.Rui,T.Mei,J.Tang,and H.-J.Zhang. the feature vectors used by MILES,the feature representa- Concurrent multiple instance learning for image categoriza- tion scheme proposed in this paper is a much more practical tion.In IEEE Computer Society Conference on Computer one to effectively describe the bags in MIL. Vision and Pattern Recognition,2007.4 Although very promising performance has been [10]R.Rahmani and S.A.Goldman.MISSL:multiple-instance achieved by our method even though we simply use prior semi-supervised learning.In Proceedings of the Twenty- knowledge to determine how many evidence instances Third International Conference Machine Learning,pages 705-712,2006.5,6 should be identified from each positive bag,a better choice [11]R.Rahmani,S.A.Goldman,H.Zhang,S.R.Cholleti,and is to learn this parameter from data.Different positive J.E.Fritts.Localized content-based image retrieval.IEEE bags might have different numbers of evidence instances. Transactions on Pattern Analysis and Machine Intelligence, Hence,how to adaptively identify the appropriate number 30(11)1902-1912,2008.1 of evidence instances for each positive bag will be pursued [12]R.Rahmani,S.A.Goldman,H.Zhang,J.Krettek,and J.E. in our future work. Fritts.Localized content based image retrieval.In Multime- Furthermore,in CBIR,it is easy to get a large number dia Information Retrieval,pages 227-236,2005.1,2,3,5. of unlabeled images from the image repository.Hence, 6 semi-supervised learning methods,which can incorporate [13]H.Zhang,R.Rahmani,S.R.Cholleti,and S.A.Goldman. unlabeled data into the training process,are very meaning- Local image representations using pruned salient points with ful for CBIR.This will also be pursued in our future work. applications to CBIR.In ACM Multimedia,pages 287-296, For example,we can apply manifold regularization [for 2006.1,3,5 semi-supervised localized CBIR.of instances from the background dominate the effect of the evidence instances on SIVAL. Because the background can appear in either positive or negative bags, the features based on instances from the background actually have very low discrimination ability. Hence, the useful features in MILES are very limited. As a result, MILES will be more easily affected by noise on the SIVAL data set. This might be the cause for the phenomenon that MILES is much more sensi￾tive to noise on the SIVAL data set. 5.3. Computation Cost Table 4 lists the training time (on a 2GHz PC with 1G memory) required by DD-SVM, MILES, and EC-SVM. “SIVAL” refers to the time for training 25 classifiers for all the 25 categories when four positive and four negative images are used as the training set on the SIVAL data set. “COREL” refers to the time for training 20 classifiers for all the 20 categories when four positive and four negative im￾ages are used as the training set on the COREL data set. To test the scalability of EC-SVM, we also evaluate the train￾ing time on the COREL data set based on a training set of 500 images, denoted as “COREL2”, which has been used for efficiency comparison in MILES [3]. We can see that EC-SVM is much more efficient. Table 4. Computation time comparison (in minutes). SIVAL COREL COREL2 DD-SVM N/A N/A 40 MILES 0.34 0.064 0.85 EC-SVM 0.23 0.005 0.2 6. Conclusion and Future Work Considering the high computation cost and high noise sensitivity of DD-SVM, and the very high dimensionality of the feature vectors used by MILES, the feature representa￾tion scheme proposed in this paper is a much more practical one to effectively describe the bags in MIL. Although very promising performance has been achieved by our method even though we simply use prior knowledge to determine how many evidence instances should be identified from each positive bag, a better choice is to learn this parameter from data. Different positive bags might have different numbers of evidence instances. Hence, how to adaptively identify the appropriate number of evidence instances for each positive bag will be pursued in our future work. Furthermore, in CBIR, it is easy to get a large number of unlabeled images from the image repository. Hence, semi-supervised learning methods, which can incorporate unlabeled data into the training process, are very meaning￾ful for CBIR. This will also be pursued in our future work. For example, we can apply manifold regularization [1] for semi-supervised localized CBIR. Acknowledgements This research has been supported by General Research Fund 621407 from the Research Grants Council of the Hong Kong Special Administrative Region, China. We thank Dr. Yixin Chen for sharing the code and data for MILES. References [1] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regular￾ization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Re￾search, 7:2399–2434, 2006. 8 [2] C.-C. Chang and C.-J. Lin. LIBSVM: a Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm. 5, 7 [3] Y. Chen, J. Bi, and J. Z. Wang. MILES: Multiple-instance learning via embedded instance selection. IEEE Trans. Pat￾tern Anal. Mach. Intell., 28(12):1931–1947, 2006. 2, 4, 5, 6, 7, 8 [4] Y. Chen and J. Z. Wang. Image categorization by learning and reasoning with regions. Journal of Machine Learning Research, 5:913–939, 2004. 2, 4 [5] S. R. Cholleti, S. A. Goldman, and R. Rahmani. Mi￾Winnow: A new multiple-instance learning algorithm. In 18th IEEE International Conference on Tools with Artificial Intelligence, pages 336–346, 2006. 5 [6] T. G. Dietterich, R. H. Lathrop, and T. Lozano-Perez. Solv- ´ ing the multiple instance problem with axis-parallel rectan￾gles. Artif. Intell., 89(1-2):31–71, 1997. 1 [7] W.-J. Li and D.-Y. Yeung. MILD: Multiple-instance learning via disambiguation. IEEE Transactions on Knowledge and Data Engineering, In Press. 1 [8] O. Maron and T. Lozano-Perez. A framework for multiple- ´ instance learning. In Advances in Neural Information Pro￾cessing Systems, 1997. 2, 3 [9] G.-J. Qi, X.-S. Hua, Y. Rui, T. Mei, J. Tang, and H.-J. Zhang. Concurrent multiple instance learning for image categoriza￾tion. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007. 4 [10] R. Rahmani and S. A. Goldman. MISSL: multiple-instance semi-supervised learning. In Proceedings of the Twenty￾Third International Conference Machine Learning, pages 705–712, 2006. 5, 6 [11] R. Rahmani, S. A. Goldman, H. Zhang, S. R. Cholleti, and J. E. Fritts. Localized content-based image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11):1902–1912, 2008. 1 [12] R. Rahmani, S. A. Goldman, H. Zhang, J. Krettek, and J. E. Fritts. Localized content based image retrieval. In Multime￾dia Information Retrieval, pages 227–236, 2005. 1, 2, 3, 5, 6 [13] H. Zhang, R. Rahmani, S. R. Cholleti, and S. A. Goldman. Local image representations using pruned salient points with applications to CBIR. In ACM Multimedia, pages 287–296, 2006. 1, 3, 5