World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

LEARNING SVM WITH COMPLEX MULTIPLE KERNELS EVOLVED BY GENETIC PROGRAMMING

    https://doi.org/10.1142/S0218213010000352Cited by:5 (Source: Crossref)

    Classic kernel-based classifiers use only a single kernel, but the real-world applications have emphasized the need to consider a combination of kernels — also known as a multiple kernel (MK) — in order to boost the classification accuracy by adapting better to the characteristics of the data. Our purpose is to automatically design a complex multiple kernel by evolutionary means. In order to achieve this purpose we propose a hybrid model that combines a Genetic Programming (GP) algorithm and a kernel-based Support Vector Machine (SVM) classifier. In our model, each GP chromosome is a tree that encodes the mathematical expression of a multiple kernel. The evolutionary search process of the optimal MK is guided by the fitness function (or efficiency) of each possible MK. The complex multiple kernels which are evolved in this manner (eCMKs) are compared to several classic simple kernels (SKs), to a convex linear multiple kernel (cLMK) and to an evolutionary linear multiple kernel (eLMK) on several real-world data sets from UCI repository. The numerical experiments show that the SVM involving the evolutionary complex multiple kernels perform better than the classic simple kernels. Moreover, on the considered data sets, the new multiple kernels outperform both the cLMK and eLMK — linear multiple kernels. These results emphasize the fact that the SVM algorithm requires a combination of kernels more complex than a linear one in order to boost its performance.

    References

    • V.   Vapnik , The Nature of Statistical Learning Theory ( Springer , 1995 ) . CrossrefGoogle Scholar
    • B.   Schoelkopf and A. J.   Smola , Learning with Kernels ( The MIT Press , 2002 ) . Google Scholar
    • O. Chapelleet al., Machine Learning 46(1/3), 131 (2002), DOI: 10.1023/A:1012450327387. Crossref, Web of ScienceGoogle Scholar
    • G. R. G. Lanckrietet al., Journal of Machine Learning Research 5, 27 (2004). Web of ScienceGoogle Scholar
    • V. N.   Vapnik , Estimation of Dependences Based on Empirical Data ( Springer , 1982 ) . Google Scholar
    • B.   Schölkopf , K.   Tsuda and J. P.   Vert , Kernel Methods in Computational Biology ( MIT Press , 2004 ) . CrossrefGoogle Scholar
    • H. W. Mewes, D. Frishman, C. Gruber, B. Geier, D. Haase, A. Kaps, K. Lemcke, G. Mannhaupt, F. Pfeiffer, C. Schüller, S. Stocker, and B. Weil, MIPS: A database for genomes and protein sequences (2002) . Google Scholar
    • H. Lodhiet al., Journal of Machine Learning Research 2, 419 (2002), DOI: 10.1162/153244302760200687. Web of ScienceGoogle Scholar
    • B. Vanschoenwinkel and B. Manderick, Deterministic and Statistical Methods in Machine Learning, LNCS 3635, eds. J. Winkler, M. Niranjan and N. D. Lawrence (Springer, 2004) pp. 256–280. Google Scholar
    • S. Sonnenburget al., Journal of Machine Learning Research 7, 1531 (2006). Web of ScienceGoogle Scholar
    • F. R. Bach, G. R. G. Lanckriet and M. I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, ICML, ed. C. E. Brodley (ACM, 2004) pp. 41–48. Google Scholar
    • A.   Rakotomamonjy et al. , More efficiency in multiple kernel learning , Proceedings of the Twenty-fourth International Conference on Machine Learning (ICML) . Google Scholar
    • L. Diosanet al., Improving svm performance using a linear combination of kernels, Adaptive and Natural Computing Algorithms, ICANNGA'074432, LNCS (Springer, 2007) pp. 218–227. Google Scholar
    • H.-N. Nguyen, S.-Y. Ohn and W.-J. Choi, Combined kernel function for support vector machine and learning method based on evolutionary algorithm, Neural Information Processing, 11th International Conference, ICONIP 20043316, LNCS, eds. N. R. Palet al. (Springer, 2004) pp. 1273–1278. Google Scholar
    • S.-Y. Ohn, H.-N. Nguyen and S.-D. Chi, Evolutionary parameter estimation algorithm for combined kernel function in support vector machine, Content Computing, Advanced Workshop on Content Computing, AWCC 20043309, LNCS, eds. C.-H. Chi and K.-Y. Lam (Springer, 2004) pp. 481–486. Google Scholar
    • S.-Y. Ohnet al., Determining optimal decision model for support vector machine by genetic algorithm, Computational and Information Science, First International Symposium, CIS 20043314, LNCS, eds. J. Zhang, J.-H. He and Y. Fu (Springer, 2004) pp. 895–902. Google Scholar
    • R. S. S. Lessmann and S. Crone, Genetically constructed kernels for support vector machines, Proc. of German Operations Research (Springer, 2005) pp. 257–262. Google Scholar
    • C. S. Ong, A. Smola and B. Williamson, Journal of Machine Learning Research 6, 1043 (2005). Web of ScienceGoogle Scholar
    • N. Cristianiniet al., On kernel-target alignment, Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001], eds. T. G. Dietterich, S. Becker and Z. Ghahramani (MIT Press, 2001) pp. 367–373. Google Scholar
    • D. H. Wolpert and W. G. Macready, No free lunch theorems for search, Tech. Rep. SFI-TR-95-02-010, Santa Fe Institute (1995) . Google Scholar
    • J. R.   Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , 1992 ) . Google Scholar
    • N.   Cristianini and J.   Shawe-Taylor , An Introduction to Support Vector Machines ( Cambridge University Press , 2000 ) . Google Scholar
    • T. Joachims, Advances in Kernel Method — Support Vector Learning, eds. B. Scholkopf, C. J. C. Burges and A. J. Smola (MIT Press, 1999) pp. 169–184. Google Scholar
    • J. C. Burges, Knowledge Discovery and Data Mining 2 (Kluwer_Academic, 1998) pp. 121–167. Google Scholar
    • V.   Vapnik , Statistical Learning Theory ( Wiley , 1998 ) . Google Scholar
    • M. A. Aizerman, E. M. Braverman and L. I. Rozonoér, Automation and Remote Control 25, 821 (1964). Web of ScienceGoogle Scholar
    • B. E. Boser, I. Guyon and V. Vapnik, A training algorithm for optimal margin classifiers, COLT pp. 144–152. Google Scholar
    • B. Schölkopf, The kernel trick for distances, NIPS, eds. T. K. Leen, T. G. Dietterich and V. Tresp (MIT Press, 2000) pp. 301–307. Google Scholar
    • C. Cortes and V. Vapnik, Machine Learning 20, 273 (1995). Web of ScienceGoogle Scholar
    • H. Lin and C. Lin, A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods (2003) . Google Scholar
    • T. Howley and M. G. Madden, Artif. Intell. Rev. 24(3-4), 379 (2005), DOI: 10.1007/s10462-005-9009-3. Crossref, Web of ScienceGoogle Scholar
    • T. Howley and M. G. Madden, An evolutionary approach to automatic kernel construction, Artificial Neural Networks — ICANN 20064132, LNCS, eds. S. D. Kolliaset al. (Springer, 2006) pp. 417–426. Google Scholar
    • L.   Dioşan , A.   Rogozan and J.-P.   Pcuchet , Evolving kernel functions for svms by genetic programming , The 2007 International Conference on Machine Learning and Applications (ICMLA'07) . Google Scholar
    • C. Gagneet al., Genetic programming for kernel-based learning with co-evolving subsets selection, Parallel Problem Solving from Nature — PPSN IX, (9th PPSN'06)4193, LNCS, eds. T. P. Runarssonet al. (Springer, 2006) pp. 1008–1017. Google Scholar
    • C.   Berg , J. P. R.   Christensen and P.   Ressel , Harmonic Analysis on Semigroups ( Springer , 1984 ) . CrossrefGoogle Scholar
    • M. R. Hestenes and E. Stiefel, Journal of Research of the National Bureau of Standards 49(6), 409 (1952). Crossref, Web of ScienceGoogle Scholar
    • D. E.   Goldberg , Genetic Algorithms in Search, Optimization and Machine Learning ( Addison Wesley , 1989 ) . Google Scholar
    • F. R. Bach, G. R. G. Lanckriet and M. I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Machine Learning, Proceedings of ICML 2004 (ACM, 2004) p. 6. Google Scholar
    • M. Girolami and S. Rogers, Hierarchic bayesian models for kernel learning, ICML pp. 241–248. Google Scholar
    • J. Platt, Advances in Kernel Methods — Support Vector Learning, eds. B. Schölkopf, C. J. C. Burges and A. J. Smola (MIT Press, 1999) pp. 185–208. Google Scholar
    • W. Banzhaf, Genetic programming: An introduction: On the automatic evolution of computer programs and its applications (1998) . Google Scholar
    • G. Syswerda, Uniform crossover in genetic algorithms, ICGA pp. 2–9. Google Scholar
    • G. Syswerda, A study of reproduction in generational and steady state genetic algorithms, Proceedings of FOGA Conference, ed. G. J. E. Rawlins (Morgan Kaufmann, 1991) pp. 94–101. Google Scholar
    • C.-C. Chang and, C.-J. Lin, LIBSVM: a library for support vector machines, software available at (2001) , http://www.csie.ntu.edu.tw/~cjlin/libsvm . Google Scholar
    • C. B. D. J. Newman, S. Hettich, and C. Merz, UCI repository of machine learning databases (1998) , http://www.ics.uci.edu/~mlearn/MLRepository.html . Google Scholar
    • R. D. King, Statlog databases (1992) , http://www.liacc.up.pt/ML/old/statlog/datasets.html . Google Scholar
    • J. J. Grefenstette, IEEE Transactions on Systems, Man, and Cybernetics SMC 16(1), 122 (1986), DOI: 10.1109/TSMC.1986.289288. Crossref, Web of ScienceGoogle Scholar
    • T. Bäck, Parallel optimization of evolutionary algorithms, Parallel Problem Solving From Nature — PPSN III866, Lecture Notes in Computer Science, eds. Y. Davidor and H.-P. Schwefel (Springer Verlag, 1994) pp. 418–427. Google Scholar
    • W. Banzhaf, F. D. Francone and P. Nordin, Lecture Notes in Computer Science 1141, 300 (1996), DOI: 10.1007/3-540-61723-X_994. CrossrefGoogle Scholar
    • R. Poli and W. B. Langdon, Soft Computing in Engineering Design and Manufacturing, eds. P. K. Chawdhry, R. Roy and R. K. Pant (Springer-Verlag, London, 1997) pp. 180–189. Google Scholar
    • A. Piszcz and T. Soule, Genetic programming: Analysis of optimal mutation rates in a problem with varying difficulty, Proceedings of the Nineteenth International Florida Artificial Intelligence Research Society Conference, eds. G. C. J. Sutcliffe and R. G. Goebel (American Association for Artificial Intelligence, 2006) pp. 451–456. Google Scholar
    • G. Wang, D.-Y. Yeung and F. H. Lochovsky, A kernel path algorithm for support vector machines, ICML '07: Proceedings of the 24th International Conference on Machine Learning (ACM Press, 2007) pp. 951–958. Google Scholar
    • M. R. Hestenes and E. Stiefel, Technologies de l'information 4(1), 1 (2007). Web of ScienceGoogle Scholar
    • O. Chapelle, Support vector machines: Induction principle, adaptive tuning and prior knowledge, Ph.D. thesis, UPMC (2004) . Google Scholar
    • P. J. Angeline, An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover, Genetic Programming 1996: Proceedings of the First Annual Conference, eds. J. R. Kozaet al. (MIT Press, 1996) pp. 21–29. Google Scholar
    • T.   Bäck , Evolutionary Algorithms in Theory and Practice ( Oxford University Press , New York , 1996 ) . CrossrefGoogle Scholar
    • D. B. Fogel, L. J. Fogel and J. W. Atmar, Meta-evolutionary programming, Proc. of the 25th Asilomar Conf. on Signals, Systems, and Computers, ed. R. R. Chen (Maple, 1991) pp. 540–545. Google Scholar
    • Y. LeCunet al., Proceedings of the IEEE 86(11), 2278 (1998), DOI: 10.1109/5.726791. Crossref, Web of ScienceGoogle Scholar
    • S. Knerr, L. Personnaz and G. Dreyfus, Neurocomputing: Algorithms, Architectures and Applications F 68, 41 (1990). Google Scholar