Tim Kovacs – författare

Classifier systems are an intriguing approach to a broad range of machine learning problems, based on automated generation and evaluation of condi­ tion/action rules. Inreinforcement learning tasks they simultaneously address the two major problems of learning a policy and generalising over it (and re­ lated objects, such as value functions). Despite over 20 years of research, however, classifier systems have met with mixed success, for reasons which were often unclear. Finally, in 1995 Stewart Wilson claimed a long-awaited breakthrough with his XCS system, which differs from earlier classifier sys­ tems in a number of respects, the most significant of which is the way in which it calculates the value of rules for use by the rule generation system. Specifically, XCS (like most classifiersystems) employs a genetic algorithm for rule generation, and the way in whichit calculates rule fitness differsfrom earlier systems. Wilson described XCS as an accuracy-based classifiersystem and earlier systems as strength-based. The two differin that in strength-based systems the fitness of a rule is proportional to the return (reward/payoff) it receives, whereas in XCS it is a function of the accuracy with which return is predicted. The difference is thus one of credit assignment, that is, of how a rule''s contribution to the system''s performance is estimated. XCS is a Q­ learning system; in fact, it is a proper generalisation of tabular Q-learning, in which rules aggregate states and actions. In XCS, as in other Q-learners, Q-valuesare used to weightaction selection.

Classifier systems are an intriguing approach to a broad range of machine learning problems, based on automated generation and evaluation of condi­ tion/action rules. Inreinforcement learning tasks they simultaneously address the two major problems of learning a policy and generalising over it (and re­ lated objects, such as value functions). Despite over 20 years of research, however, classifier systems have met with mixed success, for reasons which were often unclear. Finally, in 1995 Stewart Wilson claimed a long-awaited breakthrough with his XCS system, which differs from earlier classifier sys­ tems in a number of respects, the most significant of which is the way in which it calculates the value of rules for use by the rule generation system. Specifically, XCS (like most classifiersystems) employs a genetic algorithm for rule generation, and the way in whichit calculates rule fitness differsfrom earlier systems. Wilson described XCS as an accuracy-based classifiersystem and earlier systems as strength-based. The two differin that in strength-based systems the fitness of a rule is proportional to the return (reward/payoff) it receives, whereas in XCS it is a function of the accuracy with which return is predicted. The difference is thus one of credit assignment, that is, of how a rule's contribution to the system's performance is estimated. XCS is a Q­ learning system; in fact, it is a proper generalisation of tabular Q-learning, in which rules aggregate states and actions. In XCS, as in other Q-learners, Q-valuesare used to weightaction selection.

The Distinguished Dissertations series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. Machine learning promises both to create machine intelligence and to shed light on natural intelligence. A fundamental issue for either endevour is that of credit assignment, which we can pose as follows: how can we credit individual components of a complex adaptive system for their often subtle effects on the world? For example, in a game of chess, how did each move (and the reasoning behind it) contribute to the outcome?This text studies aspects of credit assignment in learning classifier systems, which combine evolutionary algorithms with reinforcement learning methods to address a range of tasks from pattern classification to stochastic control to simulation of learning in animals. Credit assignment in classifier systems is complicated by two features: 1) their components are frequently modified by evolutionary search, and 2) components tend to interact. Classifier systems are re-examined from first principles and the result is, primarily, a formalization of learning in these systems, and a body of theory relating types of classifier systems, learning tasks, and credit assignment pathologies. Most significantly, it is shown that both of the main approaches have difficulties with certain tasks, which the other type does not.

This volume brings together recent theoretical work in Learning Classifier Systems (LCS), which is a Machine Learning technique combining Genetic Algorithms and Reinforcement Learning. It includes self-contained background chapters on related fields (reinforcement learning and evolutionary computation) tailored for a classifier systems audience and written by acknowledged authorities in their area - as well as a relevant historical original work by John Holland.

The work embodied in this volume was presented across three consecutive e- tions of the International Workshop on Learning Classi?er Systems that took place in Chicago (2003), Seattle (2004), and Washington (2005). The Genetic and Evolutionary Computation Conference, the main ACM SIGEvo conference, hosted these three editions. The topics presented in this volume summarize the wide spectrum of interests of the Learning Classi?er Systems (LCS) community. The topics range from theoretical analysis of mechanisms to practical cons- eration for successful application of such techniques to everyday data-mining tasks. When we started editing this volume, we faced the choice of organizing the contents in a purely chronologicalfashion or as a sequence of related topics that help walk the reader across the di?erent areas. In the end we decided to or- nize the contents by area, breaking the time-line a little. This is not a simple endeavor as we can organize the material using multiple criteria. The tax- omy below is our humble e?ort to provide a coherent grouping. Needless to say, some works may fall in more than one category. The four areas are as follows: Knowledge representation. These chapters elaborate on the knowledge r- resentations used in LCS. Knowledge representation is a key issue in any learning system and has implications for what it is possible to learn and what mechanisms shouldbe used. Four chapters analyze di?erent knowledge representations and the LCS methods used to manipulate them.

The work embodied in this volume was presented across three consecutive e- tions of the International Workshop on Learning Classi?er Systems that took place in Chicago (2003), Seattle (2004), and Washington (2005). The Genetic and Evolutionary Computation Conference, the main ACM SIGEvo conference, hosted these three editions. The topics presented in this volume summarize the wide spectrum of interests of the Learning Classi?er Systems (LCS) community. The topics range from theoretical analysis of mechanisms to practical cons- eration for successful application of such techniques to everyday data-mining tasks. When we started editing this volume, we faced the choice of organizing the contents in a purely chronologicalfashion or as a sequence of related topics that help walk the reader across the di?erent areas. In the end we decided to or- nize the contents by area, breaking the time-line a little. This is not a simple endeavor as we can organize the material using multiple criteria. The tax- omy below is our humble e?ort to provide a coherent grouping. Needless to say, some works may fall in more than one category. The four areas are as follows: Knowledge representation. These chapters elaborate on the knowledge r- resentations used in LCS. Knowledge representation is a key issue in any learning system and has implications for what it is possible to learn and what mechanisms shouldbe used. Four chapters analyze di?erent knowledge representations and the LCS methods used to manipulate them.

This book constitutes the thoroughly refereed joint post-conference proceedings of two consecutive International Workshops on Learning Classifier Systems that took place in Seattle, WA, USA in July 2006, and in London, UK, in July 2007 - all hosted by the Genetic and Evolutionary Computation Conference, GECCO. The 14 revised full papers presented were carefully reviewed and selected from the workshop contributions. The papers are organized in topical sections on knowledge representation, analysis of the system, mechanisms, new directions, as well as applications.

This book constitutes the thoroughly refereed joint post-conference proceedings of two consecutive International Workshops on Learning Classifier Systems that took place in Seattle, WA, USA in July 2006, and in London, UK, in July 2007 - all hosted by the Genetic and Evolutionary Computation Conference, GECCO. The 14 revised full papers presented were carefully reviewed and selected from the workshop contributions. The papers are organized in topical sections on knowledge representation, analysis of the system, mechanisms, new directions, as well as applications.