A first order logic classifier system

ABSTRACT

Motivated by the intention to increase the expressive power of learning classifier systems, we developed a new Xcs derivative, Fox-cs, where the classifier and observation languages are a subset of first order logic. We found that Fox-cs was viable at tasks in two relational task domains, poker and blocks world, which cannot be represented easily using traditional bit-string classifiers and inputs. We also found that for these tasks, the level of generality obtained by Fox-cs in the portion of population that produces optimal behaviour is consistent with Wilson's generality hypothesis.

REFERENCES

• 1: M. Ahluwalia and L. Bull. A genetic programming-based classi . er system. In Banzhaf et al. {2} , pages 11--18.
• 2: W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors. GECCO'99: Proceedings of the Genetic and Evolutionary Computation Conference Morgan Kaufmann, 1999.
• 3: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 4: Hendrik Blockeel , Luc De Raedt , Nico Jacobs , Bart Demoen, Scaling Up Inductive Logic Programming by Learning from Interpretations, Data Mining and Knowledge Discovery, v.3 n.1, p.59-93, March 1999 [doi>10.1023/A:1009867806624]
• 5: L. B. Booker. Representing attribute-based concepts in a classifier system. In G. J. E. Rawlins, editor, Proceedings of the First Workshop on Foundations of Genetic Algorithms (FOGA91)pages 115--127, San-Maeto, 1991. Morgan Kaufmann.
• 6: Larry Bull , Toby O'Hara, Accuracy-based Neuro And Neuro-fuzzy Classifier Systems, Proceedings of the Genetic and Evolutionary Computation Conference, p.905-911, July 09-13, 2002
• 7: M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Soft Computing 6(3--4):144--153, 2002.
• 8: Sošo Džeroski , Luc De Raedt , Kurt Driessens, Relational reinforcement learning, Machine Learning, v.43 n.1/2, p.7-52, April/May 2001 [doi>10.1023/A:1007694015589]
• 9: David B. Fogel, Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, Piscataway, NJ, 1995
• 10: J. H. Holland. Escaping brittleness:the possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In R. S. Michalski, J. G. Carbonell, and T. M. Mitchell, editors, Machine Learning, an Artificial Intelligence Approach pages 593--623, Los Altos, California, 1986. Morgan Kaufmann.
• 11: W. V. Laer. From Propositional to First Order Logic in Machine Learning and Data Mining PhDthesis, Katholieke Universiteit Leuven, 2002.
• 12: P. L. Lanzi. Extending the representation of classifier conditions, part II: From messy codings to S-expressions. In Banzhaf et al. {2} , pages 345--352.
• 13: Learning Classifier Systems, From Foundations to Applications, January 2000
• 14: S. Muggleton. Inductive Logic Programming. In The MIT Encyclopedia of the Cognitive Sciences (MITECS) Academic Press, 1992.
• 15: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 16: Proceedings of the third international conference on Genetic algorithms, December 1989
• 17: Dale Schuurmans , Jonathan Schaeffer, Representational difficulties with classifier systems, Proceedings of the third international conference on Genetic algorithms, p.328-333, December 1989, George Mason University, United States
• 18: Lingyan Shu , Jonathan Schaeffer, VCS: variable classifier systems, Proceedings of the third international conference on Genetic algorithms, p.334-339, December 1989, George Mason University, United States
• 19: John Slaney , Sylvie Thiébaux, Blocks World revisited, Artificial Intelligence, v.125 n.1-2, p.119-153, Jan. 2001 [doi>10.1016/S0004-3702(00)00079-5]
• 20: P. Tadepalli, R. Givan, and K. Driessens, editors. Proceedings of the ICML'04 Workshop on Relational Reinforcement Learning 2004. http://eecs. oregonstate. edu/research/rrl/index. html.
• 21: Chris Thornton, Truth from trash: how learning makes sense, MIT Press, Cambridge, MA, 2000
• 22: S. W. Wilson. Classifier . tness based on accuracy. Evolutionary Computation 3(2):149--175, 1995.
• 23: S. W. Wilson. Generalization in the XCS classifier system. In Genetic Programming 1998: Proceedings of the Third Annual Conference pages 665--674, University of Wisconsin, Madison, Wisconsin, USA, 1998. Morgan Kaufmann.
• 24: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Languages

Keywords:
Xcs, blocks world, first order logic, learning classifier system, poker, relational learning