nach oben

Soft Computing

Erschienen in:

01.06.2012 | Original Paper

Multi-objective approach based on grammar-guided genetic programming for solving multiple instance problems

verfasst von: Amelia Zafra, Sebastián Ventura

Erschienen in: Soft Computing | Ausgabe 6/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Multiple instance learning (MIL) is considered a generalization of traditional supervised learning which deals with uncertainty in the information. Together with the fact that, as in any other learning framework, the classifier performance evaluation maintains a trade-off relationship between different conflicting objectives, this makes the classification task less straightforward. This paper introduces a multi-objective proposal that works in a MIL scenario to obtain well-distributed Pareto solutions to multi-instance problems. The algorithm developed, Multi-Objective Grammar Guided Genetic Programming for Multiple Instances (MOG3P-MI), is based on grammar-guided genetic programming, which is a robust tool for classification. Thus, this proposal combines the advantages of the grammar-guided genetic programming with benefits provided by multi-objective approaches. First, a study of multi-objective optimization for MIL is carried out. To do this, three different extensions of MOG3P-MI are designed and implemented and their performance is compared. This study allows us on the one hand, to check the performance of multi-objective techniques in this learning paradigm and on the other hand, to determine the most appropriate evolutionary process for MOG3P-MI. Then, MOG3P-MI is compared with some of the most significant proposals developed throughout the years in MIL. Computational experiments show that MOG3P-MI often obtains consistently better results than the other algorithms, achieving the most accurate models. Moreover, the classifiers obtained are very comprehensible.

Vorheriger Artikel Improved Izhikevich neurons for spiking neural networks

Nächster Artikel Polyadic tense -valued ukasiewicz–Moisil algebras

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Andrews S, Tsochantaridis I, Hofmann T (2002) Support vector machines for multiple-instance learning. In: NIPS’02: proceedings of neural information processing system, Vancouver, Canada, pp 561–568

Auer P, Ortner R (2004) 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. Springer, Pisa, pp 63–74

Bojarczuk CC, Lopes HS, Freitas AA (2000) Genetic programming for knowledge discovery in chest-pain diagnosis. IEEE Eng Med Biol Mag 19(4):38–44CrossRef

Chai YM, Yang ZW (2007) 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. Springer, Nanjing, pp 1162–1172

Chen X, Zhang C, Chen S, Rubin S (2009) A human-centered multiple instance learning framework for semantic video retrieval. IEEE Trans Syst Man Cybern Part C Appl Rev 39(2):228–233CrossRef

Chen Y, Bi J, Wang J (2006) MILES: Multiple-instance learning via embedded instance selection. IEEE Trans Pattern Anal Mach Intell 28(12):1931–1947CrossRef

Chen Y, Wang JZ (2004) Image categorization by learning and reasoning with regions. J Mach Learn Res 5:913–939

Chevaleyre YZ, Zucker JD (2001) 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. Springer, Ottawa, pp 204–214

Chien BC, Lin JY, Hong TP (2002) Learning discriminant functions with fuzzy attributes for classification using genetic programming. Expert Syst Appl 23(1):31–37CrossRef

Coello CA, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems. Genetic and evolutionary computation. 2nd edn. Springer, Berlin

Couchet J, Manrique D, Ros J, Rodrguez-Patn A (2006) Crossover operators for grammar-guided genetic programming. Soft Comput A Fusion of Found Methodol Appl 11(10):943–955

Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-II. In: PPSN VI: proceedings of the 6th international conference on parallel problem solving from nature. Springer, London, pp 849–858

Dehuri S, Cho SB (2008) Multi-objective classification rule mining using gene expression programming. In: ICCIT ’08: proceedings of the 3rd international conference on convergence and hybrid information technology. IEEE Computer Society, Washington, DC, pp 754–760

Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH

Dietterich TG, Lathrop RH, Lozano-Perez T (1997) Solving the multiple instance problem with axis-parallel rectangles. Artif Intell 89(1–2):31–71MATHCrossRef

Gao S, Suna Q (2008) Exploiting generalized discriminative multiple instance learning for multimedia semantic concept detection. Pattern Recogn 41(10):3214–3223MATHCrossRef

Garcia S, Fernandez A, Luengo J, Herrera F (2009) A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Comput A Fusion of Found Methodol Appl 13:959–977

Garcia S, Fernandez A, Luengo J, Herrera F (2010) Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power. Inf Sci 180(10):2044–2064CrossRef

Gartner T, Flach PA, Kowalczyk A, Smola AJ (2002) Multi-instance k0ernels. In: ICML’02: proceedings of the 19th international conference on machine learning. Morgan Kaufmann, Sydney, pp 179–186

Gu Z, Mei T, Hua X, Tang J, Wu X (2008) Multi-layer multi-instance learning for video concept detection. IEEE Trans Multimedia 10(8):1605–1616CrossRef

Jaszkiewicz A, Kominek P (2003) Genetic local search with distance preserving recombination operator for a vehicle routing problem. Eur J Oper Res 151(2):352–364MathSciNetMATHCrossRef

Keerthi S, Shevade S, Bhattacharyya C, Murthy K (2001) Improvements to platt’s smo algorithm for svm classifier design. Neural Comput 13(3):637–649MATHCrossRef

Kishore JK, Patnaik LM, Mani V, Agrawal VK (2000) Application of genetic programming for multicategory pattern classification. IEEE Trans Evol Comput 4(3):242–258CrossRef

Knuth DE (1964) Backus normal form vs. backus naur form. Commun ACM 7(12):735–736CrossRef

Liao S, Hsieh C, Lai P (2011) An evolutionary approach for multi-objective optimization of the integrated location-inventory distribution network problem in vendor-managed inventory. Expert Syst Appl 38(6):6768–6776CrossRef

Lu J, Ma S, Zhang M (2008) Multi-instance clustering approach for web image using one-class support vector machine. J Comput Inf Syst 4(3):1231–1240

Mangasarian OL, Wild EW (2008) Multiple instance classification via successive linear programming. J Optim Theory Appl 137(3):555–568MathSciNetMATHCrossRef

Maron O, Lozano-Pérez T (1997) A framework for multiple-instance learning. In: NIPS’97: proceedings of neural information processing system 10, Denver, CO, USA, pp 570–576

Mugambi EM, Hunter A (2003) Multi-objective genetic programming optimization of decision trees for classifying medical data. In: KES’03: knowledge-based intelligent information and engineering systems, pp 293–299.

Panait L, Luke S (2004) Alternative bloat control methods. In: GECCO’04: proceedings of the 2004 conference on genetic and evolutionary computation, Seattle, Washington, USA, pp 630–641

Pang J, Huang Q, Jiang S (2008) Multiple instance boost using graph embedding based decision stump for pedestrian detection. In: ECCV’08: proceedings of the 10th European conference on computer vision. Lectures Note in Computer Science, vol 5305. Springer, Berlin, pp 541–552

Pao H, Chuang S, Xu Y, Fu H (2008) An EM based multiple instance learning method for image classification. Expert Syst Appl 35(3):1468–1472CrossRef

Parrott D, Xiaodong L, Ciesielski V (2005) Multi-objective techniques in genetic programming for evolving classifiers. In: IEEE congress on evolutionary computation, vol 2, pp 1141–1148

Qian C, Yu Y, Zhou ZH (2011) An analysis on recombination in multi-objective evolutionary optimization. In: GECCO’11: proceedings of the 13th ACM conference on genetic and evolutionary computation, Dublin, Ireland, pp 2051–2058

Ramon J, De Raedt L (2000) Multi-instance neural networks. In: ICML’00: a workshop on attribute-value and relational learning at the 17th conference on machine learning

Ray S, Page D (2001) Multiple instance regression. In: Proceedings of the eighteenth international conference on machine learning, ICML’01, San Francisco, CA, USA, pp 425–432

Ron K (1995) A study of cross-validation and bootstrap for accuracy estimation and model selection. In: IJCAI’95: international joint conference on artificial intelligence, Montreal, Canada, pp 1137–1145

Ruffo G (2000) Learning single and multiple instance decision tree for computer security applications. PhD thesis, Department of Computer Science. University of Turin, Torino, Italy

Shukla PK, Deb K (2007) On finding multiple pareto-optimal solutions using classical and evolutionary generating methods. Eur J Oper Res 181(3):1630–1652MATHCrossRef

Tan KC, Tay Lee A, Heng T, CM (2002) Mining multiple comprehensible classification rules using genetic programming. In: CEC’02: proceedings of the congress on evolutionary computation, Honolulu, HI, USA, vol 2, pp 1302–1307

Tan K, Chiam S, Mamun A, Goh C (2009) Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization. Eur J Oper Res 197(2):701–713MATHCrossRef

Tsang CH, Kwong S, Wang H (2007) Genetic-fuzzy rule mining approach and evaluation of feature selection techniques for anomaly intrusion detection. Pattern Recogn 40(9):2373–2391MATHCrossRef

Veldhuizen DV, Lamont G (2000) Multiobjective evolutionary algorithms: analyzing the state-of-the-art. Evol Comput 8(2):125–147CrossRef

Ventura S, Romero C, Zafra A, Delgado JA, Hervás C (2007) JCLEC: AZ java framework for evolutionary computation soft computing. Soft Comput 12(4):381–392CrossRef

Wang J, Zucker JD (2000) Solving the multiple-instance problem: a lazy learning approach. In: ICML’00: Proceedings of the 17th international conference on machine learning, Stanford, CA, USA, pp 1119–1126

Wee H, Lo C, Hsu P (2009) A multi-objective joint replenishment inventory model of deteriorated items in a fuzzy environment. Eur J Oper Res 197(2):620–631MathSciNetMATHCrossRef

Whigham PA (1995) Grammatically-based genetic programming. In: Proceedings of the workshop on genetic programming: from theory to real-world applications, Tahoe City, CA, USA, pp 33–41

Whigham PA (1996) Grammatical bias for evolutionary learning. PhD thesis, School of Computer Science, University College, University of New South Wales, Australian Defence Force Academy, Canberra, Australia

Wiens TS, Dale BC, Boyce MS, Kershaw PG (2008) Three way k-fold cross-validation of resource selection functions. Ecol Model 212(3–4):244–255CrossRef

Witten I, Frank E (2005) Data mining: practical machine learning tools and techniques. 2nd edn. Morgan Kaufmann, San Francisco

Witten IH, Frank E (1999) Data mining: practical machine learning tools and techniques with java implementations. Morgan Kaufmann, San Francisco

Wu F, Zhou H, Zhao J, Cen K (2011) A comparative study of the multi-objective optimization algorithms for coal-fired boilers. Expert Syst Appl 38(6):7179–7185CrossRef

Xu L, Guo MZ, Zou Q, Liu Y, Li HF (2008) An improved diverse density algorithm for multiple overlapped instances. In: ICNC’08: Proceedings of the 4th international conference on natural computation. IEEE Computer Society, Washington, DC, pp 88–91

Xu X (2003) Statistical learning in multiple instance problems. PhD thesis, Department of Computer Science. University of Waikato

Xu X, Frank E (2004) 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. Springer, Sydney, pp 272–281

Yang C, Dong M, Fotouhi F (2005) Region based image annotation through multiple-instance learning. In: Multimedia’05: proceedings of the 13th annual ACM international conference on multimedia, New York, USA, pp 435–438

Yang E, Erdogan AT, Arslan T, Barton NH (2011) Multi-objective evolutionary optimizations of a space-based reconfigurable sensor network under hard constraints. Soft Computing 15(1):25–36CrossRef

Zhou Z-H, Wu J, Tang W (2002) Ensembling neural networks: Many could be better than all. Artif Intell 137(1–2): 239–263

Zafra A, Romero C, Ventura S (2011) Multiple instance learning for classifying students in learning management systems. Expert Syst Appl 38(12):15020–15031

Zafra A, Ventura S (2010) G3P-MI: A genetic programming algorithm for multiple instance learning. Information Sciences 180(23):4496–4513CrossRef

Zafra A, Ventura S, Romero C, Herrera-Viedma E (2009) Multi-instance genetic programming for web index recommendation. Expert Syst Appl 36(9):11470–11479CrossRef

Zhang D, Wanga F, Shib Z, Zhanga C (2010) Interactive localized content based image retrieval with multiple-instance active learning. Pattern Recognition 43(2):478–484MATHCrossRef

Zhang ML, Zhou ZH (2004) Improve multi-instance neural networks through feature selection. Neural Processing Letters 19(1):1–10MATHCrossRef

Zhang ML, Zhou ZH (2005) Ensembles of multi-instance Neural Networks. In: IIP’04: International Conference on intelligent information processing II. IFIP international federation for information processing, Beijing, China. vol 163, pp 471–474

Zhang ML, Zhou ZH (2006) Adapting RBF Neural Networks to multi-instance learning. Neural Processing Letters 23(1):1–26CrossRef

Zhang ML, Zhou ZH (2009) Multi-instance clustering with applications to multi-instance prediction. Applied Intelligences 31(1):47–68CrossRef

Zhang Q, Goldman S (2001) EM-DD: An improved multiple-instance learning technique. In: NIPS’01: Proceedings of Neural Information Processing System 14, Vancouver, Canada, pp 1073–1080

Zhou ZH, Jiang K, Li M (2005) Multi-instance learning based web mining. Applied Intelligence 22(2):135–147CrossRef

Zhou ZH, Zhang ML (2007) Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowledge and Information Systems 11(2):155–170CrossRef

Zitzler E, Laumanns M, Thiele L (2001) SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Tech. Rep. 103, Gloriastrasse 35

Titel: Multi-objective approach based on grammar-guided genetic programming for solving multiple instance problems
verfasst von: Amelia Zafra
Sebastián Ventura
Publikationsdatum: 01.06.2012
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 6/2012
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-011-0794-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2012

Improved Izhikevich neurons for spiking neural networks

On the class of λ-statistically convergent difference sequences of fuzzy numbers

Polyadic tense $$\theta$$ -valued $$\L$$ ukasiewicz–Moisil algebras

Combining seasonal ARIMA models with computational intelligence techniques for time series forecasting

Design of particle-reinforced polyurethane mould materials for soft tooling process using evolutionary multi-objective optimization algorithms

An improved cooperative quantum-behaved particle swarm optimization