article

G3P-MI: A genetic programming algorithm for multiple instance learning

Authors:

Sebastián VenturaAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 180, Issue 23

Pages 4496 - 4513

https://doi.org/10.1016/j.ins.2010.07.031

Published: 01 December 2010 Publication History

Abstract

This paper introduces a new Grammar-Guided Genetic Programming algorithm for resolving multi-instance learning problems. This algorithm, called G3P-MI, is evaluated and compared to other multi-instance classification techniques in different application domains. Computational experiments show that the G3P-MI often obtains consistently better results than other algorithms in terms of accuracy, sensitivity and specificity. Moreover, it makes the knowledge discovery process clearer and more comprehensible, by expressing information in the form of IF-THEN rules. Our results confirm that evolutionary algorithms are very appropriate for dealing with multi-instance learning problems.

References

[1]

}}Alphonse, E. and Matwin, S., Filtering multi-instance problems to reduce dimensionality in relational learning. Journal Intelligence Information System. v22 i1. 23-40.

[2]

}}Amar, R.A., Dooly, D.R., Goldman, S.A. and Zhang, Q., Multiple-instance learning of real-valued data. In: ICML'01: Proceedings of 18th International Conference on Machine Learning, Williams College, Williamstown, MA, USA.

[3]

}}Andrews, S., Tsochantaridis, I. and Hofmann, T., Support vector machines for multiple-instance learning. In: NIPS'02: Proceedings of Neural Information Processing System, Vancouver, Canada.

[4]

}}Auer, P., On learning from multi-instance examples: empirical evaluation of a theoretical approach. In: ICML'97: Proceedings of the 14th International Conference on Machine Learning, Nashville, Tennessee, USA.

[5]

}}Auer, P., Long, P.M. and Srinivasan, A., Approximating hyper-rectangles: learning and pseudo-random sets. In: STOC'97: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA.

[6]

}}P. Auer, R. Ortner, A boosting approach to multiple instance learning, in: ECML'04: Proceedings of the 5th European Conference on Machine Learning, Lecture Notes in Computer Science, vol. 3201, Pisa, Italy, 2004.

[7]

}}Back, T., Fogel, D. and Michalewicz, Z., Handbook of Evolutionary Computation. 1997. Oxford University Press, Oxford, UK.

[8]

}}Blum, A. and Kalai, A., A note on learning from multiple-instance examples. Machine Learning. v30 i1. 23-30.

[9]

}}Böhm, W. and Geyer-Schulz, A., Exact uniform initialization for genetic programming. In: FOGA'96: Proceedings of the 4th Workshop on Foundations of Genetic Algorithms, Morgan Kaufmann, San Diego, CA, USA.

[10]

}}Bojarczuk, C.C., Lopes, H.S. and Freitas, A.A., Genetic programming for knowledge discovery in chest-pain diagnosis. IEEE Engineering in Medicine and Biology Magazine. v19 i4. 38-44.

[11]

}}Y.-M. Chai, Z.-W. Yang, A multi-instance learning algorithm based on normalized radial basis function network, in: ISSN'07: Proceedings of the 4th International Symposium on Neural Networks, Lecture Notes in Computer Science, vol. 4491, Nanjing, China, 2007.

[12]

}}Chellapilla, K., Evolving computer programs without subtree crossover. IEEE Transactions on Evolutionary Computation. v1 i3. 209-216.

[13]

}}Chen, X., Zhang, C., Chen, S. and Rubin, S., A human-centered multiple instance learning framework for semantic video retrieval. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews. v39 i2. 228-233.

[14]

}}Chen, Y., Bi, J. and Wang, J., Miles: multiple-instance learning via embedded instance selection. IEEE Transactions on Pattern Analysis and Machine Intelligence. v28 i12. 1931-1947.

[15]

}}Chen, Y. and Wang, J.Z., Image categorization by learning and reasoning with regions. Journal of Machine Learning Research. v5. 913-939.

[16]

}}Y. Chevaleyre, N. Bredeche, J. Zucker, Learning rules from multiple instance data: issues and algorithms, in: IPMU'02: Proceedings of the 9th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Annecy, France, 2002.

[17]

}}Y.-Z. Chevaleyre, J.-D. Zucker, Solving multiple-instance and multiple-part learning problems with decision trees and decision rules. Application to the mutagenesis problem, in: AI'01: Proceedings of the 14th of the Canadian Society for Computational Studies of Intelligence, Lecture Notes in Computer Science, vol. 2056, Ottawa, Canada, 2001.

Digital Library

[18]

}}Chien, B.-C., Lin, J.Y. and Hong, T.-P., Learning discriminant functions with fuzzy attributes for classification using genetic programming. Expert Systems with Applications. v23 i1. 31-37.

[19]

}}Davis, R.A., Charlton, A.J., Oehlschlager, S. and Wilson, J.C., Novel feature selection method for genetic programming using metabolomic 1H NMR data. Chemometrics and Intelligent Laboratory Systems. v81 i1. 50-59.

[20]

}}Demšar, J., Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research. v7. 1-30.

[21]

}}Dietterich, T.G., Lathrop, R.H. and Lozano-Perez, T., Solving the multiple instance problem with axis-parallel rectangles. Artifical Intelligence. v89 i1-2. 31-71.

[22]

}}Dooly, D.R., Zhang, Q., Goldman, S.A. and Amar, R.A., Multiple instance learning of real valued data. Journal Machine Learning Research. v3. 651-678.

[23]

}}Dunn, O.J., Multiple comparisons among means. Journal of the American Statistical Association. v56 i293. 52-64.

[24]

}}Feng, S. and Xu, D., Transductive multi-instance multi-label learning algorithm with application to automatic image annotation. Expert Systems with Applications. v37 i1. 661-670.

[25]

}}E. Frank, X. Xu, Applying propositional learning algorithms to multi-instance data, Tech. rep., Department of Computer Science, University of Waikato, 2003.

[26]

}}Y. Freund, R.E. Schapire, Experiments with a new boosting algorithm, in: ICML'96: Proceedings of the 13th International Conference on Machine Learning, Garda, Italy, 1996.

[27]

}}T. Gärtner, P.A. Flach, A. Kowalczyk, A.J. Smola, Multi-instance kernels, in: ICML'02: Proceedings of the 19th International Conference on Machine Learning, Morgan Kaufmann, Sydney, Australia, 2002.

[28]

}}Gärtner, T., Lloyd, J.W. and Flach, P.A., Kernels and distances for structured data. Machine Learning. v57 i3. 205-232.

[29]

}}Geyer-Schulz, A., Fuzzy Rule-Based Expert Systems and Genetic Machine Learning. 1995. first ed. Physica Verlag, Heidelberg, Germany.

[30]

}}Z. Gu, T. Mei, J. Tang, X. Wu, X. Hua, MILC2: A multi-layer multi-instance learning approach to video concept detection, in: MMM'08: Proceedings of the 14th International Conference of Multimedia Modeling, Kyoto, Japan, 2008.

Digital Library

[31]

}}Kishore, J.K., Patnaik, L.M., Mani, V. and Agrawal, V.K., Application of genetic programming for multicategory pattern classification. IEEE Transactions on Evolutionary Computation. v4 i3. 242-258.

[32]

}}Kouchakpour, P., Zaknich, A. and Brn++unl, T., Dynamic population variation in genetic programming. Information Sciences. v179 i8. 1078-1091.

[33]

}}Koza, J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection. 1992. MIT Press.

[34]

}}Larson, J. and Michalski, R.S., Inductive inference of vl decision rules. SIGART Newsletter. i63. 38-44.

[35]

}}Lavrač, N. and Flach, P.A., An extended transformation approach to inductive logic programming. ACM Transactions on Computation Logic. v2 i4. 458-494.

[36]

}}Lensberg, T., Eilifsen, A. and McKee, T.E., Bankruptcy theory development and classification via genetic programming. European Journal of Operational Research. v169 i2. 677-697.

[37]

}}Long, P.M. and Tan, L., PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Machine Learning. v30 i1. 7-21.

[38]

}}S. Luke, L. Panait, A survey and comparison of tree generation algorithms, in: GECCO'01: Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, California, 2001.

[39]

}}Mangasarian, O.L. and Wild, E.W., Multiple instance classification via successive linear programming. Journal of Optimization Theory and Applications. v137 i3. 555-568.

[40]

}}O. Maron, T. Lozano-Pérez, A framework for multiple-instance learning, in: NIPS'97: Proceedings of Neural Information Processing System 10, Denver, Colorado, USA, 1997.

[41]

}}Muharram, M., Evolutionary constructive induction. IEEE Transactions on Knowledge and Data Engineering. v17 i11. 1518-1528.

[42]

}}Muni, D.P., Pal, N.R. and Das, J., A novel approach to design classifiers using genetic programming. IEEE Transactions on Evolutionary Computation. v8 i2. 183-196.

[43]

}}Pao, H.T., Chuang, S.C., Xu, Y.Y. and Fu, H., An EM based multiple instance learning method for image classification. Expert Systems with Applications. v35 i3. 1468-1472.

[44]

}}Platt, J.C., Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods: Support Vector Learning. 185-208.

[45]

}}Raedt, L.D., Attribute-value learning versus inductive logic programming: The missing links (extended abstract). In: ILP '98: Proceedings of the 8th International Workshop on Inductive Logic Programming, Springer-Verlag, London, UK.

[46]

}}J. Ramon, L. De Raedt, Multi-instance neural networks, in: ICML'00: A Workshop on Attribute-Value and Relational Learning at the 17th Conference on Machine Learning, 2000.

[47]

}}Ray, S. and Craven, M., Supervised versus multiple instance learning: an empirical comparison. In: ICML'05: Proceedings of the 22nd International Conference on Machine Learning, ACM Press, Bonn, Germany.

[48]

}}Ray, S. and Page, D., Multiple instance regression. In: ICML'01: Proceedings of the 18th International Conference on Machine Learning, Williams College, Williamstown, MA, USA.

[49]

}}K. Ron, A study of cross-validation and bootstrap for accuracy estimation and model selection, in: IJCAI'95: International Joint Conference on Artificial Intelligence, Montreal, Canada, 1995.

[50]

}}G. Ruffo, Learning Single and Multiple Instance Decision Tree for Computer Security Applications, Ph.D. Thesis, Department of Computer Science, University of Turin, Torino, Italy, 2000.

[51]

}}Scott, S., Zhang, J. and Brown, J., On generalized multiple-instance learning. International Journal of Computational Intelligence and Applications. v5. 21-35.

[52]

}}A. Song, V. Ciesielski, H. Williams, Texture classifiers generated by genetic programming, in: CEC'02: Proceedings of Congress on Evolutionary Computation, Honolulu, HI, USA, 2002.

[53]

}}Srinivasan, A., Muggleton, S.H., Sternberg, M.J.E. and King, R.D., Theories for mutagenicity: a study in first-order and feature-based induction. Artificial Intelligence. v85 i1-2. 277-299.

[54]

}}K. Tan, A. Tay, T. Lee, C. Heng, Mining multiple comprehensible classification rules using genetic programming, in: CEC'02: Proceedings of the Congress on Evolutionary Computation, vol. 2, Honolulu, HI, USA, 2002.

[55]

}}Tao, Q., Scott, S., Vinodchandran, N.V. and Osugi, T.T., SVM-based generalized multiple-instance learning via approximate box counting. In: ICML'04: Proceedings of the 21st International Conference on Machine Learning, ACM Press, Banff, Alberta, Canada.

[56]

}}Tsakonas, A., A comparison of classification accuracy of four genetic programming-evolved intelligent structures. Information Sciences. v176 i6. 691-724.

[57]

}}Ventura, S., Romero, C., Zafra, A., Delgado, J.A. and Hervás, C., JCLEC: a java framework for evolutionary computation soft computing. Soft Computing. v12 i4. 381-392.

[58]

}}J. Wang, J.-D. Zucker, Solving the multiple-instance problem: a lazy learning approach, in: ICML'00: Proceedings of the 17th International Conference on Machine Learning, Standord, CA, USA, 2000.

[59]

}}N. Weidmann, E. Frank, B. Pfahringer, A two-level learning method for generalized multi-instance problems, in: ECML'03: Proceedings of the 14th European Conference on Machine Learning, Cavtat-Dubrovnik, Croatia, 2003.

Digital Library

[60]

}}P.A. Whigham, Grammatically-based genetic programming, in: Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, Tahoe City, California, USA.

[61]

}}P.A. Whigham, Grammatical Bias for Evolutionary Learning, Ph.D. Thesis, School of Computer Science, University College, University of New South Wales, Australian Defence Force Academy, Canberra, Australia (14 Oct. 1996).

[62]

}}Wiens, T.S., Dale, B.C., Boyce, M.S. and Kershaw, P.G., Three way k-fold cross-validation of resource selection functions. Ecological Modelling. v212 i3-4. 244-255.

[63]

}}Witten, I. and Frank, E., Data Mining: Practical Machine Learning Tools and Techniques. 2005. second ed. Morgan Kaufman, San Francisco.

[64]

}}Wongseree, W., Chaiyaratana, N., Vichittumaros, K., Winichagoon, P. and Fucharoen, S., Thalassaemia classification by neural networks and genetic programming. Information Sciences. v177 i3. 771-786.

[65]

}}X. Xu, Statistical Learning in Multiple Instance Problems, Ph.D. Thesis, Department of Computer Science. University of Waikato, Tauranga, New Zealand, 2003.

[66]

}}X. Xu, E. Frank, Logistic regression and boosting for labeled bags of instances, in: PAKDD'04: Proceedings of the 8th Conference of Pacific-Asia, Lecture Notes in Computer Science, vol. 3056, Sydney, Australia, 2004.

[67]

}}C. Yang, M. Dong, F. Fotouhi, Region based image annotation through multiple-instance learning, in: Multimedia'05: Proceedings of the 13th Annual ACM International Conference on Multimedia, New York, USA, 2005.

Digital Library

[68]

}}Yang, C. and Lozano-Perez, T., Image database retrieval with multiple-instance learning techniques. In: ICDE '00: Proceedings of the 16th International Conference on Data Engineering, IEEE Computer Society, Washington, DC, USA.

Digital Library

[69]

}}Zafra, A., Ventura, S., Romero, C. and Herrera-Viedma, E., Multi-instance genetic programming for web index recommendation. Expert Systems with Applications. v36 i9. 11470-11479.

[70]

}}Zhang, D., Wanga, F., Shib, Z. and Zhanga, C., Interactive localized content based image retrieval with multiple-instance active learning. Pattern Recognition. v43 i2. 478-484.

[71]

}}Zhang, M. and Smart, W., Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification. Pattern Recognition Letters. v27 i11. 1266-1274.

[72]

}}Zhang, M.-L. and Zhou, Z.-H., Improve multi-instance neural networks through feature selection. Neural Processing Letters. v19 i1. 1-10.

[73]

}}M.-L. Zhang, Z.-H. Zhou, Ensembles of multi-instance neural networks, in: IIP'04: International Conference on Intelligent Information Processing II, IFIP International Federation for Information Processing, vol. 163, Beijing, China, 2005.

Digital Library

[74]

}}Zhang, M.-L. and Zhou, Z.-H., Adapting RBF neural networks to multi-instance learning. Neural Processing Letters. v23 i1. 1-26.

Digital Library

[75]

}}Zhang, Q. and Goldman, S., EM-DD: an improved multiple-instance learning technique. In: NIPS'01: Proceedings of Neural Information Processing System, vol. 14. Vancouver, Canada.

[76]

}}Zhou, Z.-H., Multi-instance learning from supervised view. Journal Computer Science and Technology. v21 i5. 800-809.

[77]

}}Zhou, Z.-H., Jiang, K. and Li, M., Multi-instance learning based web mining. Applied Intelligence. v22 i2. 135-147.

[78]

}}Z.-H. Zhou, J.-M. Xu, On the relation between multi-instance learning and semi-supervised learning, in: ICML'07: Proceedings of the 24th International Conference on Machine Learning, Corvalis, Oregon, 2007.

[79]

}}Z.-H. Zhou, M.-L. Zhang, Neural networks for multi-instance learning, Technical report, AI Lab, Computer Science and Technology Department, Nanjing University, Nanjing, China, August 2002.

[80]

}}Zhou, Z.-H. and Zhang, M.-L., Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowledge and Information Systems. v11 i2. 155-170.

[81]

}}J.-D. Zucker, J.-G. Ganascia, Representation changes for efficient learning in structural domains, in: ICML'96: Proceedings of the 13th International Conference on Machine Learning, Garda, Italy, 1996.

Cited By

Quintero-Domínguez LMorell CVentura S(2022)WordificationMI: multi-relational data mining through multiple-instance propositionalizationProgress in Artificial Intelligence10.1007/s13748-019-00186-y8:3(375-387)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s13748-019-00186-y
Pereira MCarrano EDavis Júnior CVasconcelos J(2019)A comparative study of optimization models in genetic programming-based rule extraction problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2836-823:4(1179-1197)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00500-017-2836-8
Carbonneau MCheplygina VGranger EGagnon G(2018)Multiple instance learningPattern Recognition10.1016/j.patcog.2017.10.00977:C(329-353)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1016/j.patcog.2017.10.009
Show More Cited By

G3P-MI: A genetic programming algorithm for multiple instance learning
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
    2. Machine learning approaches

Recommendations

Grammar guided genetic programming for multiple instance learning: an experimental study
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

This paper introduces a new Grammar-Guided Genetic Programming algorithm for solving multi-instance Learning problems. This algorithm, called G3P-MI, is evaluated and compared with other Multi-Instance classification techniques on different application ...
A grammar-guided genetic programming algorithm for multi-label classification
EuroGP'13: Proceedings of the 16th European conference on Genetic Programming

Multi-label classification is a challenging problem which demands new knowledge discovery methods. This paper presents a Grammar-Guided Genetic Programming algorithm for solving multi-label classification problems using IF-THEN classification rules. ...
Multi-instance genetic programming for web index recommendation

This article introduces the use of a multi-instance genetic programming algorithm for modelling user preferences in web index recommendation systems. The developed algorithm learns user interest by means of rules which add comprehensibility and clarity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 180, Issue 23

December, 2010

279 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2010.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 December 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Quintero-Domínguez LMorell CVentura S(2022)WordificationMI: multi-relational data mining through multiple-instance propositionalizationProgress in Artificial Intelligence10.1007/s13748-019-00186-y8:3(375-387)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s13748-019-00186-y
Pereira MCarrano EDavis Júnior CVasconcelos J(2019)A comparative study of optimization models in genetic programming-based rule extraction problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2836-823:4(1179-1197)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00500-017-2836-8
Carbonneau MCheplygina VGranger EGagnon G(2018)Multiple instance learningPattern Recognition10.1016/j.patcog.2017.10.00977:C(329-353)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1016/j.patcog.2017.10.009
Stiborek JPevn TRehk M(2018)Multiple instance learning for malware classificationExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.10.03693:C(346-357)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.10.036
Farhana EHeber SBosman P(2017)Biogeography-based rule mining for classificationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071221(417-424)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071221
Xiao YLiu BHao Z(2017)A Sphere-Description-Based Approach for Multiple-Instance LearningIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2016.253995239:2(242-257)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TPAMI.2016.2539952
Wang RWang XKwong SXu C(2017)Incorporating Diversity and Informativeness in Multiple-Instance Active LearningIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2017.271780325:6(1460-1475)Online publication date: 28-Nov-2017
https://dl.acm.org/doi/10.1109/TFUZZ.2017.2717803
Cano AZafra AVentura S(2015)Speeding up multiple instance learning classification rules on GPUsKnowledge and Information Systems10.1007/s10115-014-0752-044:1(127-145)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10115-014-0752-0
Cano AZafra AVentura S(2013)An interpretable classification rule mining algorithmInformation Sciences: an International Journal10.1016/j.ins.2013.03.038240(1-20)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.ins.2013.03.038
Zafra APechenizkiy MVentura S(2013)HyDR-MIInformation Sciences: an International Journal10.1016/j.ins.2011.01.034222(282-301)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2011.01.034
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents