Analysis of the initialization stage of a Pittsburgh approach learning classifier system

ABSTRACT

This paper is focused on studying the initialization stage of learning classifier systems (LCS) applying the Pittsburgh approach. It has a theoretical part where the covering probability of a random rule set is modelled and a practical part. The practical part has the objective of developing general initialization policies that have competent performance on a broad range of datasets. Two kinds of policies are tested: (1) ways of tuning the initialization probability of the system and (2) smart initialization operators that create rules that are generalized versions of randomly sampled training instances. The results identify a subset of settings that are robust enough to be considered candidates to be the default initialization policy. These settings have competent performance compared to several alternative machine learning systems. Beside identifying the good policies, the experimentation made is also useful to give hints about what kind of initial solutions is the system able to process successfully to create well generalized solutions.

REFERENCES

• 1: J. Aguilar-Ruiz, J. Riquelme, and M. Toro. Evolutionary learning of hierarchical decision rules. IEEE Transactions on Systems, Man and Cybernetics, Part B, 33(2):324--331, April 2003.
• 2: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 3: J. Bacardit. Pittsburgh Genetics-Based Machine Learning in the Data Mining era: Representations, generalization, and run-time. PhD thesis, Ramon Llull University, Barcelona, Catalonia, Spain, 2004.
• 4: J. Bacardit and M. V. Butz. Data mining in learning classifier systems: Comparing xcs with gassist. In Proceedings of the 7th International Workshop on Learning Classifier Systems. (in press), LNAI, Springer-Verlag, 2004.
• 5: J. Bacardit, D. E. Goldberg, and M. V. Butz. Improving the performance of a pittsburgh learning classifier system using a default rule. In Proceedings of the 7th International Workshop on Learning Classifier Systems. (in press), LNAI, Springer-Verlag, 2004.
• 6: C. Blake, E. Keogh, and C. Merz. UCI repository of machine learning databases, 1998. (www.ics.uci.edu/mlearn/MLRepository.html).
• 7: C. Brodley. Addressing the selective superiority problem: Automatic algorithm /model class selection. In Proceedings of the Tenth International Conference on Machine Learning, pages 17--24. Morgan Kaufmann Publishers, 1993.
• 8: Martin Volker Butz , David E. Goldberg, Rule-based evolutionary online learning systems: learning bounds, classification, and prediction, University of Illinois at Urbana-Champaign, Champaign, IL, 2004
• 9: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. Department of Computer Science and Information Engineering, National Taiwan University, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 10: Kenneth A. De Jong , William M. Spears , Diana F. Gordon, Using Genetic Algorithms for Concept Learning, Machine Learning, v.13 n.2-3, p.161-188, Nov./Dec. 1993 [doi>10.1007/BF00993042]
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 13: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 14: Cezary Zygmunt Janikow, Inductive learning of decision rules from attribute-based examples: a knowledge-intensive genetic algorithm approach, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1992
• 15: G. H. John and P. Langley. Estimating continuous distributions in Bayesian classifiers. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pages 338--345. Morgan Kaufmann Publishers, San Mateo, 1995.
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: J. Rissanen. Modeling by shortest data description. Automatica, vol. 14:465--471, 1978.
• 18: T. Soule and J. A. Foster. Effects of code growth and parsimony pressure on populations in genetic programming. Evolutionary Computation, 6(4):293--309, Winter 1998.
• 19: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.
• 20: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation

Keywords:
evolutionary algorithms, learning classifier systems, rule induction