LEARNING SVM WITH COMPLEX MULTIPLE KERNELS EVOLVED BY GENETIC PROGRAMMING
Abstract
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 ) . Crossref, Google Scholar -
B. Schoelkopf and A. J. Smola , Learning with Kernels ( The MIT Press , 2002 ) . Google Scholar - Machine Learning 46(1/3), 131 (2002), DOI: 10.1023/A:1012450327387. Crossref, Web of Science, Google Scholar
- Journal of Machine Learning Research 5, 27 (2004). Web of Science, Google 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 ) . Crossref, Google 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
- Journal of Machine Learning Research 2, 419 (2002), DOI: 10.1162/153244302760200687. Web of Science, Google Scholar
- 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 , - Journal of Machine Learning Research 7, 1531 (2006). Web of Science, Google 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 , More efficiency in multiple kernel learning , Proceedings of the Twenty-fourth International Conference on Machine Learning (ICML) . Google Scholar L. Diosan , Improving svm performance using a linear combination of kernels, Adaptive and Natural Computing Algorithms, ICANNGA'074432,LNCS (Springer, 2007) pp. 218–227. Google ScholarH.-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. Pal (Springer, 2004) pp. 1273–1278. Google ScholarS.-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 ScholarS.-Y. Ohn , 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 ScholarR. 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- Journal of Machine Learning Research 6, 1043 (2005). Web of Science, Google Scholar
N. Cristianini , 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 - 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 - Automation and Remote Control 25, 821 (1964). Web of Science, Google Scholar
B. E. Boser , I. Guyon and V. Vapnik , A training algorithm for optimal margin classifiers, COLT pp. 144–152. Google ScholarB. 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- Machine Learning 20, 273 (1995). Web of Science, Google 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
- Artif. Intell. Rev. 24(3-4), 379 (2005), DOI: 10.1007/s10462-005-9009-3. Crossref, Web of Science, Google Scholar
T. Howley and M. G. Madden , An evolutionary approach to automatic kernel construction, Artificial Neural Networks — ICANN 20064132,LNCS , eds.S. D. Kollias (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. Gagne , 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. Runarsson (Springer, 2006) pp. 1008–1017. Google Scholar-
C. Berg , J. P. R. Christensen and P. Ressel , Harmonic Analysis on Semigroups ( Springer , 1984 ) . Crossref, Google Scholar - Journal of Research of the National Bureau of Standards 49(6), 409 (1952). Crossref, Web of Science, Google 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 ScholarM. Girolami and S. Rogers , Hierarchic bayesian models for kernel learning, ICML pp. 241–248. Google Scholar- 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 ScholarG. 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
- IEEE Transactions on Systems, Man, and Cybernetics SMC 16(1), 122 (1986), DOI: 10.1109/TSMC.1986.289288. Crossref, Web of Science, Google 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- Lecture Notes in Computer Science 1141, 300 (1996), DOI: 10.1007/3-540-61723-X_994. Crossref, Google Scholar
- 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 ScholarG. 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- Technologies de l'information 4(1), 1 (2007). Web of Science, Google 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. Koza (MIT Press, 1996) pp. 21–29. Google Scholar-
T. Bäck , Evolutionary Algorithms in Theory and Practice ( Oxford University Press , New York , 1996 ) . Crossref, Google 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- Proceedings of the IEEE 86(11), 2278 (1998), DOI: 10.1109/5.726791. Crossref, Web of Science, Google Scholar
- Neurocomputing: Algorithms, Architectures and Applications F 68, 41 (1990). Google Scholar
Remember to check out the Most Cited Articles! |
---|
Check out Notable Titles in Artificial Intelligence. |