Mustafa Gökçe BAYDOĞAN, Z. Caner TAŞKIN, Emel Şeyma KÜÇÜKAŞCI

A linear programming approach to multiple instance learning

Multiple instance learning (MIL) aims to classify objects with complex structures and covers a wide range of real-world data mining applications. In MIL, objects are represented by a bag of instances instead of a single instance, and class labels are provided only for the bags. Some of the earlier MIL methods focus on solving MIL problem under the standard MIL assumption, which requires at least one positive instance in positive bags and all remaining instances are negative. This study proposes a linear programming framework to learn instance level contributions to bag label without emposing the standart assumption. Each instance of a bag is mapped to a pseudo-class membership estimate and these estimates are aggregated to obtain the bag-level class membership in an optimization framework. A simple linear mapping enables handling various MIL assumptions with adjusting instance contributions. Our experiments with instance-dissimilarity based data representations verify the effectiveness of the proposed MIL framework. Proposed mathematical models can be solved efficiently in polynomial time.

PDF

___

[1] Kaliberda M, Lytvynenko L, Pogarsky S. Method of singular integral equations in diffraction by semi-infinite grating: H-polarization case. Turkish Journal of Electrical Engineering & Computer Sciences 2017; 25 (6): 4496-4509. doi: 10.3906/elk-1703-170
[2] Dietterich TG, Lathrop RH, Lozano-Pérez T. Solving the multiple instance problem with axis-parallel rectangles Artificial Intelligence. 1997; 89 (1-2): 31-71. doi:10.1016/s0004-3702(96)00034-3
[3] Chen Y, Bi J, Wang JZ. MILES: Multiple-instance learning via embedded instance selection IEEE Transactions on Pattern Analysis and Machine Intelligence. 2006;28 (12):1931-1947. doi:10.1109/TPAMI.2006.248
[4] Zhou ZH, Jiang K, Li M. Multi-instance learning based web mining Applied Intelligence. 2005;22 (2): 135-147. doi:10.1007/s10489-005-5602-z
[5] Briggs F, Lakshminarayanan B, Neal L, Fern XZ, Raich R et al. Acoustic classification of multiple simultaneous bird species: a multi-instance multi-label approach The Journal of the Acoustical Society of America. 2012; 131 (6): 4640-4650. doi:10.1121/1.4707424
[6] Scott S, Zhang J, Brown J. On generalized multiple-instance learning International Journal of Computational Intelligence and Applications. 2005; 5 (01): 21-35.
[7] Xu X. Statistical Learning in Multiple Instance Problems Hamilton, New Zealand: The University of Waikato; 2003.
[8] Amores J. Multiple instance classification: Review, taxonomy and comparative study Artificial Intelligence 2013; 201: 81-105. doi:10.1016/j.artint.2013.06.003
[9] Andrews S, Tsochantaridis I, Hofmann T. Support vector machines for multiple-instance learning In: Advances in Neural Information Processing Systems 15. MIT Press; 2003: 561-568.
[10] Poursaeidi MH, Kundakcioglu OE. Robust support vector machines for multiple instance learning Annals of Operations Research. 2014; 216 (1): 205-227. doi:10.1007/s10479-012-1241-z
[11] Kandemir M, Zhang C, Hamprecht FA. Empowering multiple instance histopathology cancer diagnosis by cell graphs In: Medical image computing and computer-assisted intervention : MICCAI International Conference on Medical Image Computing and Computer-Assisted Intervention. vol. 17. Springer; 2014. pp. 228–235.
[12] Vanwinckelen G, Tragante do OV, Fierens D, Blockeel H. Instance-level accuracy versus bag-level accuracy in multiinstance learning Data Mining and Knowledge Discovery. 2016; 30 (2): 313–341. doi:10.1007/s10618-015-0416-z
[13] Zhou ZH, Sun YY, Li YF. Multi-instance learning by treating instances as non-I.I.D. samples In: Proceedings of the 26th International Conference On Machine Learning, ICML 2009. ACM; 2009: 1249-1256.
[14] Zhou ZH. Multi-instance learning: A survey Department of Computer Science & Technology, Nanjing University, Tech Rep. 2004.
[15] Wang J, Zucker JD. Solving multiple-ınstance problem: a lazy learning approach In: In Proc. 17th International Conference on Machine Learning; 2000. p. 1119-1125.
[16] Maron O, Lozano-Pérez T. A framework for multiple-instance learning Advances in Neural Information Processing Systems; 1998: 570-576.
[17] Zhang Q, Goldman SA. Em-dd: An improved multiple-instance learning technique In: Advances in Neural Information Processing Systems; 2002: 1073-1080.
[18] Bunescu RC, Mooney RJ. Multiple instance learning for sparse positive bags In: ACM International Conference Proceeding Series. vol. 227. ACM; 2007. pp. 105–112. doi:10.1145/1273496.1273510
[19] Mangasarian OL, Wild EW. Multiple instance classification via successive linear programming Journal of Optimization Theory and Applications 2008; 137 (3): 555-568. doi:10.1007/s10957-007-9343-5
[20] Kundakcioglu OE, Seref O, Pardalos PM. Multiple instance learning via margin maximization Applied Numerical Mathematics. 2010; 60 (4): 358-369. doi:10.1016/j.apnum.2009.05.013 Available from: http://www.sciencedirect.com/science/article/pii/S0168927409001007
[21] Li WJ, Yeung DY. MILD: Multiple-instance learning via disambiguation IEEE Transactions on Knowledge and Data Engineering 2010; 22 (1): 76-89. doi:10.1109/TKDE.2009.58
[22] Erdem A, Erdem E. Multiple-instance learning with instance selection via dominant sets In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7005 LNCS. Springer; 2011: 177-191. doi:10.1007/978-3-642-24471-1_13
[23] Tax DMJ, Hendriks E, Valstar MF, Pantic M. The detection of concept frames using clustering multiinstance learning In: Proceedings - International Conference on Pattern Recognition. IEEE; 2010: 2917-2920. doi:10.1109/ICPR.2010.715
[24] Gärtner T, Flach PA, Kowalczyk A, Smola AJ. Multi-instance Kernels. In: Proceedings of the Nineteenth International Conference on Machine Learning; 2002. pp. 179-186.
[25] Cheplygina V, Tax DMJ, Loog M. Multiple instance learning with bag dissimilarities Pattern Recognition 2015; 48 (1): 264-275. doi:10.1016/j.patcog.2014.07.022
[26] Pahikkala T, Airola A, Suominen H, Boberg J, Salakoski T. Efficient AUC maximization with regularized leastsquares Frontiers in Artificial Intelligence and Applications; 2008 (173): 12-19.
[27] Mann HB, Whitney DR. On a test of whether one of two random variables is stochastically larger than the other The Annals of Mathematical Statistics 1947; 18 (1): 50-60. doi:10.1214/aoms/1177730491
[28] Ataman K, Street WN, Zhang Y. Learning to rank by maximizing AUC with linear programming In: IEEE International Conference on Neural Networks - Conference Proceedings. IEEE; 2006. pp. 123-129. doi:10.1109/ijcnn.2006.246669
[29] Fu Z, Robles-Kelly A, Zhou J. MILIS: Multiple instance learning with instance selection IEEE Transactions on Pattern Analysis and Machine Intelligence. 2011; 33 (5): 958–977. doi:10.1109/TPAMI.2010.155
[30] Duin RPW. The dissimilarity representation for pattern recognition , a tutorial vol. 64. World Scientific; 2009.
[31] Zhou ZH, Zhang ML. Solving multi-instance problems with classifier ensemble based on constructive clustering Knowledge and Information Systems 2007; 11 (2): 155-170. doi:10.1007/s10115-006-0029-3
[32] Gurobi Optimization Inc Gurobi optimizer reference manual; 2014. Available from:http://www.gurobi.com
[33] Pedregosa F, Varoquaux G, Buitinck L, Louppe G, Grisel O et al. Scikit-learn: Machine Learning in Python Journal of Machine Learning Research. 2015;19 (1):29–33.
[34] Küçükaşcı ES, Baydoğan MG. Bag encoding strategies in multiple instance learning problems; 2018. doi:10.1016/j.ins.2018.08.020 Available from: http://ww3.ticaret.edu.tr/eskucukasci/multiple-instance-learning/
[35] MATLAB version 8.5.0.197613 (R2015a) Natick, Massachusetts; 2015.
[36] Wei XS, Wu J, Zhou ZH. Scalable algorithms for multi-instance learning IEEE Transactions on Neural Networks and Learning Systems. 2017;28(4):975–987. doi:10.1109/TNNLS.2016.2519102
[37] Majnik M, Bosnić Z. ROC analysis of classifiers in machine learning: A survey Intelligent Data Analysis. 2013;17 (3):531–558. doi: 10.3233/IDA-130592
[38] Ling CX, Huang J, Zhang H. AUC: A better measure than accuracy in comparing learning algorithms In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 2671. Springer; 2003. p. 329–341. doi: 10.1007/3-540-44886-1_25
[39] Carbonneau MA, Granger E, Raymond AJ, Gagnon G. Robust multiple-instance learning ensembles using random subspace instance selection Pattern Recognition. 2016;58:83–99. doi:10.1016/j.patcog.2016.03.035
[40] Demšar J. Statistical comparisons of classifiers over multiple data sets Journal of Machine Learning Research. 2006;7:1–30.
[41] Friedman M. A Comparison of Alternative Tests of Significance for the Problem of $m$ Rankings The Annals of Mathematical Statistics. 1940;11 (1):86–92. doi:10.1214/aoms/1177731944
[42] Nemenyi P. Distribution-free Multiple Comparisons Princeton University; 1963.
[43] Nelder JA, Mead R. A Simplex Method for Function Minimization The Computer Journal. 1965;7 (4):308–313. doi:10.1093/comjnl/7.4.308
[44] Fan RE, Chang KW, Hsieh CJ, Wang XR, Lin CJ. LIBLINEAR: A library for large linear classification Journal of Machine Learning Research. 2008;9(8):1871–1874. doi:10.1145/1390681.1442794
[45] Chang CC, Lin CJ. LIBSVM: A Library for support vector machines ACM Transactions on Intelligent Systems and Technology. 2011;2 (3):27. doi:10.1145/1961189.1961199