Multiple-instance learning with pairwise instance similarity

Yuan, L. ; Liu, J. ; Tang, X.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 3, pp. 567-577.

Résumé

Multiple-Instance Learning (MIL) has attracted much attention of the machine learning community in recent years and many real-world applications have been successfully formulated as MIL problems. Over the past few years, several Instance Selection-based MIL (ISMIL) algorithms have been presented by using the concept of the embedding space. Although they delivered very promising performance, they often require long computation times for instance selection, leading to a low efficiency of the whole learning process. In this paper, we propose a simple and efficient ISMIL algorithm based on the similarity of pairwise instances within a bag. The basic idea is selecting from every training bag a pair of the most similar instances as instance prototypes and then mapping training bags into the embedding space that is constructed from all the instance prototypes. Thus, the MIL problem can be solved with the standard supervised learning techniques, such as support vector machines. Experiments show that the proposed algorithm is more efficient than its competitors and highly comparable with them in terms of classification accuracy. Moreover, the testing of noise sensitivity demonstrates that our MIL algorithm is very robust to labeling noise.

Détail

Keywords: multiple instance learning, instance selection, similarity, support vector machine (SVM)
Mots-clés : uczenie maszynowe, podobieństwo, metoda wektorów wspomagających

Bibliographie

[1] Ali, S. and Shah, M. (2010). Human action recognition in videos using kinematic features and multiple instance learning, IEEE Transactions on Pattern Analysis and Machine Intelligence 32(2): 288–303.

[2] Andrews, S. and Hofmann, T. (2004). Multiple instance learning via disjunctive programming boosting, Proceedings of Advances in Neural Information Processing Systems 16, Vancouver and Whistler, BC, Canada, pp. 65–72.

[3] Andrews, S., Tsochantaridis, I. and Hofmann, T. (2003). Support vector machines for multiple-instance learning, Proceedings of Advances in Neural Information Processing Systems 15, Vancouver, BC, Canada, pp. 561–568.

[4] Auer, P. and Ortner, R. (2004). A boosting approach to multiple instance learning, Proceedings of the 15th European Conference on Machine Learning, Pisa, Italy, pp. 63–74.

[5] Babenko, B., Yang, M.-H. and Belongie, S. (2009). Visual tracking with online multiple instance learning, Proceedings of the 22nd Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, pp. 983–990.

[6] Babenko, B., Verma, N., Dollár, P. and Belongie, S. (2011a). Multiple instance learning with manifold bags, Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, USA, pp. 81–88.

[7] Babenko, B., Yang, M.-H. and Belongie, S. (2011b). Robust object tracking with online multiple instance learning, IEEE Transactions on Pattern Analysis and Machine Intelligence 33(8): 1619–1632.

[8] Bergeron, C., Moore, G., Zaretzki, J., Breneman, C.M. and Bennett, K. P. (2012). Fast bundle algorithm for multiple-instance learning, IEEE Transactions on Pattern Analysis and Machine Intelligence 34(6): 1068–1079.

[9] Blake, C.L. and Merz, C.J. (1998). UCI repository of machine learning databases, http://archive.ics.uci.edu/ml/.

[10] Chang, C.-C. and Lin, C.-J. (2011). LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology 2(27): 1–27, www.csie.ntu.edu.tw/~cjlin/libsvm/.

[11] Chen, Y., Bi, J. and Wang, J. Z. (2006). MILES: Multiple-instance learning via embedded instance selection, IEEE Transactions on Pattern Analysis and Machine Intelligence 28(12): 1931–1947.

[12] Chen, Y. and Wang, J. Z. (2004). Image categorization by learning and reasoning with regions, Journal of Machine Learning Research 5: 913–939.

[13] Czarnowski, I. and Jędrzejowicz, P. (2011). Application of agent-based simulated annealing and tabu search procedures to solving the data reduction problem, International Journal of Applied Mathematics and Computer Science 21(1): 57–68, DOI: 10.2478/v10006-011-0004-3.

[14] Dietterich, T. G., Lathrop, R. H. and Lozano-Pérez, T. (1997). Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence 89(1–2): 31–71.

[15] Dollár, P., Babenko, B., Belongie, S., Perona, P. and Tu, Z. (2008). Multiple component learning for object detection, Proceedings of the 10th European Conference on Computer Vision, Marseille, France, pp. 211–224.

[16] Fu, Z., Robles-Kelly, A. and Zhou, J. (2011). MILIS: Multiple instance learning with instance selection, IEEE Transactions on Pattern Analysis and Machine Intelligence 33(5): 958–977.

[17] Fung, G., Dundar, M., Krishnapuram, B. and Rao, R.B. (2007). Multiple instance learning for computer aided diagnosis, Proceedings of Advances in Neural Information Processing Systems 19, Vancouver, BC, Canada, pp. 425–432.

[18] Gärtner, T., Flach, P.A., Kowalczyk, A. and Smola, A.J. (2002). Multi-instance kernels, Proceedings of the 19th International Conference on Machine Learning, Sydney, NSW, Australia, pp. 179–186.

[19] Li, F. and Sminchisescu, C. (2010). Convex multiple-instance learning by estimating likelihood ratio, Proceedings of Advances in Neural Information Processing Systems 23, Vancouver, BC, Canada, pp. 1360–1368.

[20] Li, M., Kwok, J.T. and Lu, B.-L. (2010). Online multiple instance learning with no regret, Proceedings of the 23rd Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA, pp. 1395–1401.

[21] Li, W.-J. and Yeung, D.-Y. (2010). MILD: Multiple-instance learning via disambiguation, IEEE Transactions on Knowledge and Data Engineering 22(1): 76–89.

[22] Li, Y., Tax, D. M.J., Duin, R.P.W. and Loog, M. (2013). Multiple-instance learning as a classifier combining problem, Pattern Recognition 46(3): 865–874.

[23] Maron, O. and Lozano-Pérez, T. (1998). A framework for multiple-instance learning, Proceedings of Advances in Neural Information Processing Systems 10, Denver, CO, USA, pp. 570–576.

[24] Maron, O. and Ratan, A. L. (1998). Multiple-instance learning for natural scene classification, Proceedings of the 15th International Conference on Machine Learning, Madison, WI, USA, pp. 341–349.

[25] Nguyen, D.T., Nguyen, C.D., Hargraves, R., Kurgan, L.A. and Cios, K.J. (2013). mi-DS: Multiple-instance learning algorithm, IEEE Transactions on Cybernetics 43(1): 143–154.

[26] Rahmani, R., Goldman, S.A., Zhang, H., Cholleti, S.R. and Fritts, J.E. (2008). Localized content-based image retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence 30(11): 1902–1912.

[27] Ramon, J. and De Raedt, L. (2000). Multi instance neural networks, Proceedings of the 17th International Conference on Machine Learning/Workshop on Attribute-Value and Relational Learning, Stanford, CA, USA.

[28] Raykar, V.C., Krishnapuram, B., Bi, J., Dundar, M. and Rao, R.B. (2008). Bayesian multiple instance learning: Automatic feature selection and inductive transfer, Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, pp. 808–815.

[29] Settles, B., Craven, M. and Ray, S. (2008). Multiple-instance active learning, Proceedings of Advances in Neural Information Processing Systems 20, Vancouver, BC, Canada, pp. 1289–1296.

[30] Tao, Q., Scott, S.D., Vinodchandran, N.V., Osugi, T.T. and Mueller, B. (2008). Kernels for generalized multiple-instance learning, IEEE Transactions on Pattern Analysis and Machine Intelligence 30(12): 2084–2098.

[31] Trawiński, B., Smętek, M., Telec, Z. and Lasota, T. (2012). Nonparametric statistical analysis for multiple comparison of machine learning regression algorithms, International Journal of Applied Mathematics and Computer Science 22(4): 867–881, DOI: 10.2478/v10006-012-0064-z.

[32] Vezhnevets, A. and Buhmann, J. M. (2010). Towards weakly supervised semantic segmentation by means of multiple instance and multitask learning, Proceedings of the 23rd Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA, pp. 3249–3256.

[33] Viola, P.A., Platt, J.C. and Zhang, C. (2006). Multiple instance boosting for object detection, Proceedings of Advances in Neural Information Processing Systems 18, Vancouver, BC, Canada, pp. 1417–1424.

[34] Wang, J. and Zucker, J.-D. (2000). Solving the multiple-instance problem: A lazy learning approach, Proceedings of the 17th International Conference on Machine Learning, Stanford, CA, USA, pp. 1119–1126.

[35] Yang, C. and Lozano-Pérez, T. (2000). Image database retrieval with multiple-instance learning techniques, Proceedings of the 16th International Conference on Data Engineering, San Diego, CA, USA, pp. 233–243.

[36] Zha, Z.-J., Hua, X.-S., Mei, T., Wang, J., Qi, G.-J. and Wang, Z. (2008). Joint multi-label multi-instance learning for image classification, Proceedings of the 21st Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA, pp. 1–8.

[37] Zhang, M.-L. and Zhou, Z.-H. (2004). Improve multi-instance neural networks through feature selection, Neural Processing Letters 19(1): 1–10.

[38] Zhang, Q. and Goldman, S.A. (2002). EM-DD: An improved multiple-instance learning technique, Proceedings of Advances in Neural Information Processing Systems 14, Vancouver, BC, Canada, pp. 1073–1080.

[39] Zhang, Q., Goldman, S.A., Yu, W. and Fritts, J.E. (2002). Content-based image retrieval using multiple-instance learning, Proceedings of the 19th International Conference on Machine Learning, Sydney, NSW, Australia, pp. 682–689.