Combining evolution strategy and gradient descent method for discriminative learning of bayesian classifiers

ABSTRACT

The optimization method is one of key issues in discriminative learning of pattern classifiers. This paper proposes a hybrid approach of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and the gradient decent method for optimizing Bayesian classifiers under the SOFT target based Max-Min posterior Pseudo-probabilities (Soft-MMP) learning framework. In our hybrid optimization approach, the weighted mean of the parent population in the CMA-ES is adjusted by exploiting the gradient information of objective function, based on which the offspring is generated. As a result, the efficiency and the effectiveness of the CMA-ES are improved. We apply the Soft-MMP with the proposed hybrid optimization approach to handwritten digit recognition. The experiments on the CENPARMI database show that our handwritten digit classifier outperforms other state-of-the-art techniques. Furthermore, our hybrid optimization approach behaved better than not only the single gradient decent method but also the single CMA-ES in the experiments.

REFERENCES

• 1: Auger, A., Schoenauer, M., and Vanhhaecke, N. 2004. LS-CMA-ES: A Second-Order Algorithm for Covariance Matrix Adaptation. In Proceedings of Eighth International Conference on Parallel Problem Solving from Nature PPSN VIII (2004). Springer, Berlin, 1611--3349.
• 2: Peter Cheeseman , John Stutz, Bayesian classification (AutoClass): theory and results, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: Chellapilla, K., Fogel, D.B. 2001. Evolving an Expert Checkers Playing Program without Using Human Expertise. IEEE Trans. Evolutionary Computation, 5, 4 (2001), 422--428.
• 4: Liu, X.B., Jia, Y.D., Chen, X.F., Deng, Y. and Fu, H. 2008 Image Classification Using the Max-Min Posterior Pseudo-Probabilities Method. Technical Report, BIT-CS-20080001. Beijing Institute of Technology. DOI=http://www.mcislab.org.cn/member/~xiabi/papers/2008_1.PDF
• 5: Chen, X. F., Liu, X. B., and Jia, Y. D. 2008. A Soft Target Method of Learning Posterior Pseudo-probabilities based Classifiers with its Application to Handwritten Digit Recognition, 2008 11th International Conference on Frontiers in Handwriting Recognition (Montréal, Canada, August 2008). ICFHR'08.
• 6: X. Chen , X. Liu , Y. Jia, Learning Handwritten Digit Recognition by the Max-Min Posterior Pseudo-Probabilities Method, Proceedings of the Ninth International Conference on Document Analysis and Recognition, p.342-346, September 23-26, 2007
• 7: Grant Cochenour , Jerad Simon , Sanjoy Das , Anil Pahwa , Surasish Nag, A pareto archive evolutionary strategy based radial basis function neural network training algorithm for failure rate prediction in overhead feeders, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068360]
• 8: Deng, Y., Liu, X.B., Jia, Y.D. 2007. Learning Semantic Concepts for Image Retrieval Using the Max-min Posterior Pseudo-Probabilities Method. In Proceedings of 2007 IEEE International Conference on Multimedia and Expo (Beijing China, 2007). ICME'07. 1970--1973.
• 9: Dong, J.X., Krzyzak, A., Suen, C.Y. 2002. Local Learning framework for handwritten character recognition. Engineering Applications of Artificial Intelligence, 15 (2002), 151--159.
• 10: Jian-xiong Dong , Adam Krzyzak , Ching Y. Suen, Fast SVM Training Algorithm with Decomposition on Very Large Data Sets, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.603-618, April 2005 [doi>10.1109/TPAMI.2005.77]
• 11: Holger Fröhlich , Olivier Chapelle , Bernhard Schölkopf, Feature Selection for Support Vector Machines by Means of Genetic Algorithms, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.142, November 03-05, 2003
• 12: Paul D. Gader , Mohamed Ali Khabou, Automatic Feature Generation for Handwritten Digit Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.12, p.1256-1261, December 1996 [doi>10.1109/34.546262]
• 13: Goh, C. K., Teoh, E. J., Tan, K. C. 2008. Hybrid Multiobjective Evolutionary Design for Aritificial Neural Networks. IEEE Trans. Neural Networks, 19, 9 (Sep. 2008), 1531--1548.
• 14: Nikolaus Hansen, An analysis of mutative σ-self-adaptation on linear fitness functions, Evolutionary Computation, v.14 n.3, p.255-275, September 2006 [doi>10.1162/evco.2006.14.3.255]
• 15: Hansen, N., Niederberger, A. S. P., Guzzella, L., and Koumoutsakos, P. 2009. A Method for Handling Uncertainty in Evolutionary Optimization with an Application to Feedback Control of Combustion. IEEE Trans. Evolutionary Computation, 13, 1 (2009), 180--197.
• 16: Hastie, T., Tibshirani, R., Friedman, J. 2001. The Elements of Statistical Learning, Data Mining, Inference, and Prediction. Springer Series in Statistica. Springer.
• 17: Christian Igel , Thorsten Suttorp , Nikolaus Hansen, A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144082]
• 18: Igel, C. 2005. Multiobjective Model Selection for Support Vector Machines. In Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization (Guanajuato, Mexico, March 9-11, 2005). EMO'05. Springer, Berlin, 534--546.
• 19: Jung, J. Y., Reggia. 2006. J. A. Evolutionary Design of Neural Network Architectures Using a Descriptive Encoding Language. IEEE Trans. Evolutionary Computation, 10, 6 (Dec. 2006), 676--688.
• 20: Leung, F., Lam, H., Ling S., and Tam, P. 2003. Tuning of the structure and parameters of a neural network using an improved genetic algorithm. IEEE Trans. Neural Network, 14, 1 (Jan. 2003), 79--88.
• 21: Liu, C. L., Nakashima, K., Sako, H., Fujisawa, H. 2003. Handwritten digit recognition: benchmarking of state-of-the-art techniques. Pattern Recognition, 36 (2003), 2271--2285.
• 22: Liu, C. L., Nakashima, K., Sako, H., Fujisawa, H. 2004. Handwritten digit recognition: investigation of normalization and feature extraction techniques. Pattern Recognition, 37 (2004), 265--279.
• 23: Xiabi Liu , Hui Fu , Yunde Jia, Gaussian mixture modeling and learning of neighboring characters for multilingual text extraction in images, Pattern Recognition, v.41 n.2, p.484-493, February, 2008 [doi>10.1016/j.patcog.2007.06.004]
• 24: Ingo Mierswa, Controlling overfitting with multi-objective support vector machines, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277323]
• 25: Nikolaerv, N., lba, H. 2003. Learning polynomial feedforward neural networks by genetic programming and backpropagation. IEEE Trans. Neural Network, 14, 2 (Mar. 2003), 337--350.
• 26: Il-Seok Oh , Jin-Seon Lee , Ching Y. Suen, Analysis of Class Separation and Combination of Class-Dependent Features for Handwriting Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.10, p.1089-1094, October 1999 [doi>10.1109/34.799913]
• 27: Palmes, P. P., Hayasaka, T., Usui, S. 2005. Mutation-Based Genetic Neural Network. IEEE Trans. Neural Networks, 16, 3 (May, 2005), 587--600.
• 28: Tanasanee Phienthrakul , Boonserm Kijsirikul, Evolutionary strategies for multi-scale radial basis function kernels in support vector machines, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068160]
• 29: Suen, C.Y., et al. 1992. Computer recognition of unconstrained handwritten numerals. Proc. IEEE, 80, 7 (1992), 1162--1180.
• 30: Thorsten Suttorp , Nikolaus Hansen , Christian Igel, Efficient covariance matrix update for variable metric evolution strategies, Machine Learning, v.75 n.2, p.167-197, May 2009 [doi>10.1007/s10994-009-5102-1]
• 31: Wu, C.H, Tzeng, G.H., Goo, Y. J., Fang, W.C. 2007. A real-valued genetic algorithm to optimize the parameters of support vector machine for predicting bankruptcy. Expert Systems with Applications, 32 (2007), 397--408.
• 32: Yao, X. 1999. Evolving Artificial Neural Networks. Proceedings of the IEEE, 87, 9 (1999), 1423--1447.
• 33: Zhang, R., Ding, X.Q. 2001. Offline Handwritten Numeral Recognition Using Orthogonal Gaussian Mixture Model. In Proceedings 6th Int. Conference document Analysis and Recognition (Seattle, USA, 2001). ICDAR'01. IEEE, 1126--1129.
• 34: Torch Machine Learning Library. DOI = http://www.torch.ch

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms

Keywords:
discriminative learning, evolution strategy, gradient descent, handwritten digit recognition, max-min posterior pseudo-probabilities (mmp)