Publications

Bridging the gap: Learning sensorimotor-linked population codes for planning and motor control. Butz, M.V., Reif, K., & Herbort, O. (2008).
International Conference on Cognitive Systems (CogSys 2008).

Abstract Humans and animals are able to flexibly learn internal, cognitive maps of their environments and are able to use these maps to approach goals efficiently, reliably, and flexibly. Recent neuroscientific evidence suggests that such maps are formed in the hippocampus by means of interconnected place, view, and head direction cell encodings. This paper presents a neural learning architecture that develops an interconnected population code of place cells during random exploration. Connections develop dependent on the experienced sensorimotor contingencies. The learned spatial representation enables the agent to flexibly plan shortest paths to any goal location within the explored environment by means of dynamic programming. It approaches activated goal locations by means of closed loop control. While the algorithm currently relies on the Markov property, it is able to connect the network over radical sensory changes as long as they are close in sensorimotor distance. Moreover, the agent is able to flexibly adjust its behavior dependent on current constraints without further learning. This paper introduces the algorithm and evaluates its robustness and consequent behavioral flexibility.

Function Approximation with XCS: Hyperellipsoidal Conditions, Recursive Least Squares, and Compaction
Butz, M. V., Lanzi, Pier-Luca, & Wilson, Stewart W.
IEEE Transactions on Evolutionary Computation (2008), 12, 355-376.

Abstract An important strength of learning classifier systems (LCSs) lies in the combination ofAn important strength of learning classifier systems (LCSs) lies in the combination of genetic optimization techniques with gradient-based approximation techniques. The chosen approximation technique develops locally optimal approximations, such as accurate classification estimates, Q-value predictions, or linear function approximations. The genetic optimization technique is designed to distribute these local approximations efficiently over the problem space. Together, the two components develop a distributed, locally optimized problem solution in the form of a population of expert rules, often called classifiers. In function approximation problems, the XCSF classifier system develops a problem solution in the form of overlapping, piecewise linear approximations. This paper shows that XCSF performance on function approximation problems additively benefits from (1) improved representations, (2) improved genetic operators, and (3) improved approximation techniques. Additionally, this paper introduces a novel closest classifier matching mechanism for the efficient compaction of XCS's final problem solution. The resulting compaction mechanism can boil the population size down by 90% on average, while decreasing prediction accuracy only marginally. Performance evaluations show that the additional mechanisms enable XCSF to reliably, accurately, and compactly approximate even seven dimensional functions. Performance comparisons with other, heuristic function approximation techniques show that XCSF yields competitive or even superior noise-robust performance.

Paper upon request.

Context-dependent predictions and cognitive arm control with XCSF
Butz, M. V. & Herbort, O.
GECCO 2008: Genetic and Evolutionary Computation Conference, 1357-1364.

Abstract While John Holland has always envisioned learning classifier systems (LCSs) as cognitive systems, most work on LCSs has focused on classification, datamining, and function approximation. In this paper, we show that the XCSF classifier system can be very suitably modified to control a robot system with redundant degrees of freedom, such as a robot arm. Inspired by recent research insights that suggest that sensorimotor codes are nearly ubiquitous in the brain and an essential ingredient for cognition in general, the XCSF system is modified to learn classifiers that encode piecewise linear sensorimotor structures, which are conditioned on prediction-relevant contextual input. In the investigated robot arm problem, we show that XCSF partitions the (contextual) posture space of the arm in such a way that accurate hand movements can be predicted given particular motor commands. Furthermore, we show that the inversion of the sensorimotor predictive structures enables accurate goal-directed closed-loop control of arm reaching movements. Besides the robot arm application, we also investigate performance of the modified XCSF system on a set of artificial functions. All results point out that XCSF is a useful tool to evolve problem space partitions that are maximally effective for the encoding of sensorimotor dependencies. A final discussion elaborates on the relation of the taken approach to actual brain structures and cognitive psychology theories of learning and behavior.

An analysis of matching in learning classifier systems.
Butz, M. V., Lanzi, P. L., Llorà, X., & Loiacono, D.
GECCO 2008: Genetic and Evolutionary Computation Conference, 1349-1356.

Abstract We investigate rule matching in learning classifier systems for problems involving binary and real inputs. We consider three rule encodings: the widely used character-based encoding, a specificity-based encoding, and a binary encoding used in Alecsys. We compare the performance of the three algorithms both on matching alone and on typical test problems. The results on matching alone show that the population generality influences the performance of the matching algorithms based on string representations in different ways. Character-based encoding becomes slower and slower as generality increases, specificity-based encoding becomes faster and faster as generality increases. The results on typical test problems show that the specificity-based representation can halve the time required for matching but also that binary encoding is about ten times faster on the most difficult problems. Moreover, we extend specificity-based encoding to real-inputs and propose an algorithm that can halve the time require for matching real inputs using an interval-based representation.

Self-adaptive mutation in XCSF.
Butz, M. V., Stalph, P., & Lanzi, P. L.
GECCO 2008: Genetic and Evolutionary Computation Conference, 1365-1372.

Abstract Recent advances in XCS technology have shown that self-adaptive mutation can be highly useful to speed-up the evolutionary progress in XCS. Moreover, recent publications have shown that XCS can also be successfully applied to challenging real-valued domains including datamining, function approximation, and clustering. In this paper, we combine these two advances and investigate self-adaptive mutation in the XCS system for function approximation with hyperellipsoidal condition structures, referred to as XCSF in this paper. It has been shown that XCSF solves function approximation problems with an accuracy, noise robustness, and generalization capability comparable to other statistical machine learning techniques and that XCSF outperforms simple clustering techniques to which linear approximations are added. This paper shows that the right type of self-adaptive mutation can further improve XCSF's performance solving problems more parameter independent and more reliably. We analyze various types of self-adaptive mutation and show that XCSF with self-adaptive mutation ranges, differentiated for the separate classifier condition values, yields most robust performance results. Future work may further investigate the properties of the self-adaptive values and may integrate advanced self-adaptation techniques.

Towards increasing learning speed and robustness of XCSF: Experimenting with larger offspring set sizes.
Stalph, P. & Butz, M. V.
GECCO 2008: Genetic and Evolutionary Computation Conference, Workshop Proceedings IWLCS 2008.

Abstract The XCS classifier system has been successfully applied to various problem domains including datamining, boolean classifications, and function approximation. In all these applications just two classifiers were reproduced in a match or action set, given a time-recency threshold was met in the set. In this paper, we investigate the effect of selecting more than two classifiers for reproduction in XCSF. We either increase the number of selected classifiers or select a number of classifiers relative to the current match set size. In the functions investigated, both approaches showed a highly significant increase in initial learning speed. Also, in less challenging approximation tasks, the final accuracy reached is not affected by the approach. However, in harder functions, learning may stall due to over-reproductions of inaccurate, ill-estimated classifiers. Thus, we propose an adaptive offspring size rate that may depend on the current reliability of classifier parameter estimates. First results with a fixed offspring set size decrement show promising results. Future work is needed to speed-up XCS's learning progress and adjust its learning speed to the perceived problem difficulty.

Multimodal goal representations and feedback in hierarchical motor control.
Herbort, O., Butz, M. V., & Hoffmann, J.
International Conference on Cognitive Systems (CogSys 2008).

Abstract The capabilities of human motor behavior build on the integration of multiple sensory modalities in goal representation and feedback processing. Here, we present a hierarchical neural network model of motor control to simulate these capabilities, based on the SURE REACH model. The model is able to integrate visual and proprioceptive goal representations, but, by now, relies only on proprioceptive feedback to control ongoing movements. Here, we extend the model to a neural network that processes both, proprioceptive and visual feedback. In simulated reaching experiments we demonstrate that visual feedback considerably enhances the accuracy of the original controller. Moreover, the ability to combine visual and proprioceptive goal representations, or to adjust behavior to task-specific constraints is not affected. Finally, we discuss the results, propose further enhancements, and outline the model’s relevance for other domains of human cognition.

Exploiting Redundancy for Flexible Behavior: Unsupervised Learning in a Modular Sensorimotor Control Architecture
Butz, M. V., Herbort, Oliver, & Hoffmann, Joachim (2007).
Psychological Review, 114, 1015-1046.

Abstract Autonomously developing learning organisms face several problems when learning reaching movements, such as reaching for a glass. First, motor control has to be learned unsupervised, or self-supervised. Second, sensorimotor contingencies have to be acquired in contexts in which action consequences unfold over time. Third, motor redundancies need to be resolved. The proposed sensorimotor, unsupervised, redundancy-resolving control architecture (SURE_REACH) solves these problems self-supervised, based on the ideomotor principle. SURE_REACH encodes hand end-point coordinate space and angular posture space with population codes. A posture memory solves the inverse kinematics by associating end-point space activities with posture space activities. An inverse sensorimotor model associates posture transitions to motor commands. The population encoding, redundant posture memory, and the inverse sensorimotor model enable the architecture to learn sensorimotor grounded distance measures and to use dynamic programming to reach goals flexibly and efficiently. The architecture does not only solve the redundancy problem, but significantly increases goal approaching flexibility, accounting for additional task constraints or exhibiting obstacle avoidance. While the spatial population codes resemble neurophysiological structures, simulations on a three degree of freedom arm in a 2-D environment confirm the plausibility and flexibility of the model, mimicking various previously published behavior data on arm reaching tasks.

Paper upon request.

Learning to select targets within targets in reaching tasks.
Herbort, O., Ognibene, O., Butz, M.V., & Baldassarre, G. (2007).
6th IEEE International Conference on Development and Learning, ICDL 2007, 7 - 12.

Abstract We present a developmental neural network model of motor learning and control, called RL_SURE_REACH. In a childhood phase, a motor controller for goal directed reaching movements with a redundant arm develops unsupervisedly. In subsequent task-specific learning phases, the neural network acquires goal-modulation skills. These skills enable RL_SURE_REACH to master a task that was used in a psychological experiment by Trommershäuser, Maloney, and Landy (2003). This task required participants to select aimpoints within targets that maximize the likelihood of hitting a rewarded target and minimizes the likelihood of accidentally hitting an adjacent penalty area. The neural network acquires the necessary skills by means of a reinforcement learning based modulation of the mapping from visual representations to the target representation of the motor controller. This mechanism enables the model to closely replicate the data from the original experiment. In conclusion, the effectiveness of learned actions can be significantly enhanced by fine-tuning action selection based on the combination of information about the statistical properties of the motor system with different environmental payoff scenarios.

Combining Gradient-Based With Evolutionary Online Learning: An Introduction to Learning Classifier Systems
Butz, Martin V. (2007).
Seventh International Conference on Hybrid Intelligent Systems (HIS 2007), 12-17.

Abstract Learning Classifier Systems (LCSs), introduced by John H. Holland in the 1970s, are rule-based evolutionary online learning systems that combine gradient-based rule evaluation with evolutionary-based rule structuring techniques. Since the introduction of the accuracy-based XCS classi- fier system by Stewart W. Wilson in 1995, LCSs showed to be flexible, online learning methods that are applicable to datamining, reinforcement learning, and function approximation problems. Comparisons showed that performance is competitive with state-of-the art machine learning algorithms, but the learning algorithms applied are usually more flexible and highly adaptive. Moreover, problem knowledge can be extracted easily. This tutorial provides a gentle introduction to LCSs and their general functioning. It then gives further details on the XCS classifier system and highlights various successful applications. In conclusion, promising future directions of LCS research and applications are discussed.

Paper.

Anticipatory Behavior in Adaptive Learning Systems: From Brains to Individual and Social Behavior
Butz, M. V., Sigaud, O., Pezzulo, G., & Baldassarre, G. (Eds., 2007).
LNAI 4520 (State-of-the-Art Survey). Springer Verlag, Berlin-Heidelberg, Germany.

Preface The matter of anticipatory behavior in adaptive learning systems is steadily gaining interest, although many researchers still do not explicitly consider the actual anticipatory capabilities of their systems. Similarly to the previous two workshops, the third workshop on anticipatory behavior in adaptive learning systems (ABiALS 2006) has shown yet again that the similarities between different anticipatory mechanisms in diverse cognitive systems are striking. The discussions and presentations on the workshop day on the 30th of September 2006 during the Simulation of Adaptive Behavior Conference (SAB 2006) confirmed that the investigations into anticipatory cognitive mechanisms for behavior and learning strongly overlap among researchers from various disciplines, including the whole interdisciplinary cognitive science area.
Thus, further conceptualizations of anticipatory mechanisms seem mandatory. The introductory chapter of this volume therefore does not only provide an overview over the contributions included in this volume but also proposes a taxonomy of how anticipatory mechanisms can improve adaptive behavior and learning in cognitive systems. During the workshop it became clear that anticipations are involved in various cognitive processes that range from individual anticipatory mechanisms to social anticipatory behavior. This book reflects this structure by first providing neuroscientific as well as psychological evidence for anticipatory mechanisms involved in behavior, learning, language, and cognition. Next, individual predictive capabilities and anticipatory behavior capabilities are investigated. Finally, anticipation relevant in social interaction is studied.
Anticipatory behavior research on cognitive, adaptive systems aims at exploiting the insights gained from neuroscience, linguistics, and psychology for the improvement of behavior and learning in artificial cognitive systems. However, this knowledge exchange is expected to become increasingly bidirectional. That is, the insights gained during the design and evaluation of different anticipatory cognitive mechanisms and architectures may also provide insights into how anticipatory mechanisms can actually shape, guide, and control natural brain activity. This book reveals many interesting and thought-provoking connections between distinct cognitive science areas. We strongly hope that these connections do not only lead to a deeper understanding of the functioning of anticipatory processes but also enable a more effective, bidirectional knowledge exchange and consequently more effective scientific progress in the natural and artificial cognitive systems research disciplines.

Book available.

Anticipations, brains, individual and social behavior: An introduction to anticipatory systems
Butz, M.V., Sigaud, O., Pezzullo, G., & Baldassarre, G. (2007).
In Butz M.V., Sigaud O., Pezzulo G., & Baldassarre, G. (Eds.), Anticipatory Behavior in Adaptive Learning Systems: From Brains to Individual and Social Behavior. LNAI 4520, pp. 1-18, Berlin Heidelberg: Springer Verlag.

Abstract Research on anticipatory behavior in adaptive learning systems continues to gain more recognition and appreciation in various research disciplines. This book provides an overarching view on anticipatory mechanisms in cognition, learning, and behavior. It connects the knowledge from cognitive psychology, neuroscience, and linguistics with that of artificial intelligence, machine learning, cognitive robotics, and others. This introduction offers an overview over the contributions in this volume highlighting their interconnections and interrelations from an anticipatory behavior perspective. We first clarify the main foci of anticipatory behavior research. Next, we present a taxonomy of how anticipatory mechanisms may be beneficially applied in cognitive systems. With relation to the taxonomy, we then give an overview over the book contributions. The first chapters provide surveys on currently known anticipatory brain mechanisms, anticipatory mechanisms in increasingly complex natural languages, and an intriguing challenge for artificial cognitive systems. Next, conceptualizations of anticipatory processes inspired by cognitive mechanisms are provided. Subsequent chapters address predictive challenges in vision and the processing of event correlations over time. Next, anticipatory mechanisms in individual decision making and behavioral execution are studied. Finally, the book offers systems and conceptualizations of anticipatory processes involved in social interaction.

Paper

From Actions to Goals and Vice-versa: Theoretical Analysis and Models of the Ideomotor Principle and TOTE.
Pezzullo, G., Baldassarre, G., Butz, M. V., Castelfranchi, C., & Hoffmann, J. (2007).
In Butz M.V., Sigaud O., Pezzulo G., & Baldassarre, G. (Eds.), Anticipatory Behavior in Adaptive Learning Systems: From Brains to Individual and Social Behavior. LNAI 4520, pp. 73-93, Berlin Heidelberg: Springer Verlag.

Abstract How can goals be represented in natural and artificial systems? How can they be learned? How can they trigger actions? This paper describes, analyses and compares two of the most influential models of goal-oriented behavior: the ideomotor principle (IMP), which was introduced in the psychological literature, and the “test, operate, test, exit” model (TOTE), proposed in the field of cybernetics. This analysis indicates that the IMP and the TOTE highlight complementary aspects of goal-orientedness. In order to illustrate this point, the paper reviews three computational architectures that implement various aspects of the IMP and the TOTE, discusses their main peculiarities and limitations, and suggests how some of their features can be translated into specific mechanisms in order to implement them in artificial intelligent systems.

Paper

Encoding complete body models enables task dependent optimal behavior.
Herbort, Oliver, & Butz, Martin V. (2007).
Proceedings of International Joint Conference on Neural Networks, Orlando, Florida, USA, August 12-17, 2007, 1424-1429.

Abstract Many neural network models of (human) motor learning focus on the acquisition of direct goal-to-action mappings, thus rendering motor control inflexible. We propose a neural network architecture (SURE_REACH) that acquires complete body models by unsupervised learning. It encodes redundancy on the kinematic and on the motor command level to exert highly flexible, task-dependent optimal control. This paper shows that our approach accounts for two forms of effective human behavior based on exploiting kinematic redundancy. First, depending on the starting posture, hand targets are pursued in different ways optimizing movement efficiency. Second, the arm posture at the end of a movement can be aligned anticipatorily to facilitate a subsequent movement. A discussion of computational implications and relations to behavioral and neurophysiological findings concludes the paper.

Paper

Emergent effector-independent internal spaces: Adaptation and intermanual learning transfer in humans and neural networks.
Butz, M.V., Lenhard, A., & Herbort, O. (2007).
Proceedings of International Joint Conference on Neural Networks, Orlando, Florida, USA, August 12-17, 2007, 1509-1514.

Abstract Psychological studies have shown immense behavioral plasticity in arm reaching tasks. Intermanual learning transfer (ILT) tasks have shown that both reaching movements adapt to distorted spaces rather rapidly and the adaptation generalizes to the behavior of other limbs. In this paper, we present an ILT experiment and replicate it with feedforward neural network (NN) architectures. We show that the NN architecture is the key to successfully replicating the experiments. Moreover, we show that dependent on the architecture and the initial training schedule applied, an internal space representation emerges that enables ILT. The results confirm that internal body spaces, identified in neuroscience and cognitive psychological research, can emerge solely due to an interdependence between different limb movements and the right neural architecture. We hypothesize that, in order to develop internal spatial representations observed in animals and humans, it might be sufficient to enforce the integration of multiple correlated sensory and motor information into one compact internal representation.

Paper

Empirical Analysis of Generalization and Learning in XCS with Gradient Descent.
Lanzi, Pier-Luca, Butz, Martin V., & Goldberg, David E. (2007)
GECCO 2007: Genetic and Evolutionary Computation Conference, 1814-1821.

Abstract We analyze generalization and learning in XCS with gradient descent. At first, we show that the addition of gradient in XCS may slow down learning because it indirectly decreases the learning rate. However, in contrast to what was suggested elsewhere, gradient descent has no effect on the achieved generalization. We also show that when gradient descent is combined with roulette wheel selection, which is known to be sensitive to small values of the learning rate, the learning speed can slow down dramatically. Previous results reported no difference in the performance of XCS with gradient descent when roulette wheel selection or tournament selection were used. In contrast, we suggest that gradient descent should always be combined with tournament selection, which is not sensitive to the value of the learning rate. When gradient descent is used in combination with tournament selection, the results show that (i) the slowdown in learning is limited and (ii) the generalization capabilities of XCS are not affected.

Paper

Data mining in learning classifier systems: Comparing XCS with GAssist
Bacardit, J., & Butz, M.V. (2007).
In Kovacs, T., Llorà, X., Takadama, K., Lanzi, P.L., Stolzmann, W., & Wilson, S.W. (Eds.), Learning Classifier Systems: International Workshops, IWLCS 2003-2005, LNAI 4399. pp. 282-290, Berlin Heidelberg: Springer Verlag.

Abstract This paper compares performance of the Pittsburgh-style system GAssist with the Michigan-style system XCS on several datamining problems. Our analysis shows that both systems are suitable for datamining but have different advantages and disadvantages. The study does not only reveal important differences between the two systems but also suggests several structural properties of the underlying datasets.

Paper

Improving the performance of a Pittsburgh learning classifier system using a default rule
Bacardit, J., Goldberg, D.E., & Butz, M.V. (2007).
In Kovacs, T., Llorà, X., Takadama, K., Lanzi, P.L., Stolzmann, W., & Wilson, S.W. (Eds.), Learning Classifier Systems: International Workshops, IWLCS 2003-2005, LNAI 4399. pp. 291-307, Berlin Heidelberg: Springer Verlag.

Abstract An interesting feature of encoding the individuals of a Pittsburgh learning classifier system as a decision list is the emergent generation of a default rule. However, performance of the system is strongly tied to the learning system choosing the correct class for this default rule. In this paper we experimentally study the use of an explicit (static) default rule. We first test simple policies for setting the class of the default rule, such as the majority/minority class of the problem. Next, we introduce some techniques to automatically determine the most suitable class.

Paper

Effect of pure error-based fitness in XCS
Butz, M.V., Lanzi, P.L., & Goldberg, D.E. (2007).
In Kovacs, T., Llorà, X., Takadama, K., Lanzi, P.L., Stolzmann, W., & Wilson, S.W. (Eds.), Learning Classifier Systems: International Workshops, IWLCS 2003-2005, LNAI 4399. pp. 104-114, Berlin Heidelberg: Springer Verlag.

Abstract The accuracy-based fitness approach in XCS is one of the most significant changes in comparison with original learning classifier systems. Nonetheless, neither the scaled accuracy function, nor the importance of the relative fitness approach has been investigated in detail. The recent introduction of tournament selection to XCS has shown to make the system more independent from parameter settings and scaling issues. The question remains if relative accuracy itself is actually necessary in XCS or if the evolutionary process could be based directly on error. This study investigates advantages and disadvantages of pure error-based fitness vs. relative accuracy-based fitness in XCS.

Paper

Explorations of anticipatory behavioral control (ABC): A report from the cognitive psychology unit of the University of Würzburg
Hoffmann, J., Berner, M., Butz, M.V., Herbort, O., Kiesel, A., Kunde, W., Lenhard, A. (2007).
Cognitive Processing, 8, 133-142.

Paper upon request.

Spekulationen zur Struktur ideo-motorischer Beziehungen
Hoffmann, J., Butz, M.V., Herbort, O., Kiesel, A., & Lenhard, A. (2007).
Zeitschrift für Sportpsychologie, 14, 95-104.

Abstract According to the ideo-motor hypothesis, actions become bidirectionally connected to their sensory effects so that anticipations of the effects directly trigger the actions which have been learned to produce them. We discuss i) the role of exteroceptive as well proprioceptive effects, ii) the dependency of action-effect relations on the current situation, iii) the necessity of more abstract effector-unspecific action representations and finally iv) the use of sensory feedback in action control. The discussion led us to a tentative structure of ideo-motor relations by which the "idea" (anticipated goal) determines the "motor activity" (body movements) by a cascade of inverse models.

Paper (in German) upon request.

Problem Solution Sustenance in XCS: Markov Chain Analysis of Niche Support Distributions and the Impact on Computational Complexity
Butz, M. V., Goldberg, David E., Lanzi, Pier-Luca, & Sastry, K.
Genetic Programming and Evolvable Machines, 8, 5-37.

Abstract Michigan-style learning classifier systems iteratively evolve a distributed solution to a problem in the form of potentially overlapping subsolutions Each problem niche is covered by subsolutions that are represented by a set of predictive rules, termed classifiers. The genetic algorithm is designed to evolve classifier structures that together cover the whole problem space and represent a complete problem solution. An obvious challenge for such an online evolving, distributed knowledge representation is to continuously sustain all problem subsolutions covering all problem niches, that is, to ensure niche support. Effective niche support depends both on the probability of reproduction and on the probability of deletion of classifiers in a niche. In XCS, reproduction is occurrence-based whereas deletion is supportbased. In combination, niche support is assured effectively. In this paper we present a Markov chain analysis of the niche support in XCS, which we validate experimentally. Evaluations in diverse Boolean function settings, which require non-overlapping and overlapping solution structures, support the theoretical derivations. We also consider the effects of mutation and crossover on niche support. With respect to computational complexity, the paper shows that XCS is able to maintain (partially overlapping) niches with a computational effort that is linear in the inverse of the niche occurrence frequency.

Download earlier technical report version in pdf format - it is recommended, to get the journal version, though.

Automated Global Structure Extraction for Effective Local Building Block Processing in XCS
Butz, M. V., Pelikan, M., Llorà, Xavier,& Goldberg, David E.
Evolutionary Computation,14, 345-380 (2006)

Abstract Learning Classifier Systems (LCSs), such as the accuracy-based XCS, evolve distributed problem solutions represented by a population of rules. During evolution, features are specialized, propagated, and recombined to provide increasingly accurate subsolutions. Recently, it was shown that, as in conventional genetic algorithms (GAs), some problems require efficient processing of subsets of features to find problem solutions efficiently. In such problems, standard variation operators of genetic and evolutionary algorithms used in LCSs suffer from potential disruption of groups of interacting features, resulting in poor performance. This paper introduces efficient crossover operators to XCS by incorporating techniques derived from competent GAs: the extended compact GA (ECGA) and the Bayesian optimization algorithm (BOA). Instead of simple crossover operators such as uniform crossover or one-point crossover, ECGA or BOA-derived mechanisms are used to build a probabilistic model of the global population and to generate offspring classifiers locally using the model. Several offspring generation variations are introduced and evaluated. The results show that it is possible to achieve performance similar to runs with an informed crossover operator that is specifically designed to yield ideal problem-dependent exploration, exploiting provided problem structure information. Thus, we create the first competent LCSs, XCS/ECGA and XCS/BOA, that detect dependency structures online and propagate corresponding lower-level dependency structures effectively without any information about these structures given in advance.

Download earlier technical report version in pdf format (journal version recommended, though).

An Analysis of the Ideomotor Principle and TOTE
Pezzulo, G., Baldassarre, G., Butz, M. V., Castelfranchi, C., & Hoffmann, J.
Proceedings of the Third Workshop on Anticipatory Behavior in Adaptive Learning Systems (ABiALS 2006) (2006)

Abstract What does it mean for a system to be goal oriented? In this paper we investigate how goals are represented and how they activate actions. We review the main philosophical and psychological assumptions about the ideomotor principle and we compare it with the TOTE model in cybernetics. We also present three computational architectures that implement goal orientedness, discussing their main peculiarities and limitations with respect to the ideomotor principle and TOTE.

Performance of Evolutionary Algorithms on Random Decomposable Problems
Pelikan, M., Sastry, K., Butz, M., Goldberg, D. E.
Parallel Problem Solving from Nature - PPSN IX, 788-797 (2006)

Abstract Recently, studies with the XCS classifier system on Boolean functions have shown that in certain types of functions simple crossover operators can lead to disruption and, consequently, a more effective recombination mechanism is required. Simple crossover operators were replaced by recombination based on estimation of distribution algorithms (EDAs). The combination showed that XCS with such a statistics-based crossover operator can solve challenging hierarchical functions more efficiently. This study elaborates the gained competence further investigating the coding scheme for the EDA component (BOA in our case) of XCS as well as performance in randomly generated Boolean function problems. Results in hierarchical Boolean functions show that the originally used 2-bit coding scheme induces a certain learning bias that stresses additional diversity in the evolving XCS population. A 1-bit coding scheme as well as a restricted 2-bit coding scheme confirm the suspected bias. The alternative encodings decrease the unnecessary bias towards specificity and increase performance robustness. The paper concludes with a discussion on the challenges ahead for XCS in Boolean function problems as well as on the implications of the obtained results for real-valued and multiple-valued classification problems, multi-step problems, and function approximation problems.

Substructural Neighborhoods for Local Search in the Bayesian Optimization Algorithm
Lima, C. F., Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E., & Lobo, F. G.
Parallel Problem Solving from Nature - PPSN IX, 232-241 (2006)

Abstract This paper studies the utility of using substructural neigh- borhoods for local search in the Bayesian optimization algorithm (BOA). The probabilistic model of BOA, that automatically identi¯es important problem substructures, is used to de¯ne the structure of the neighbor- hoods to explore in local search. Three different neighborhoods operators are proposed for BOA, while the remaining of the paper focus on one of these operators to perform hillclimbing in the substructural space. Addi- tionally, a surrogate ¯tness model is considered to evaluate the improve- ment of the local search steps. Initial results indicate that performing local search in substructural neighborhoods signi¯catively reduces the number of generations necessary to converge to optimal solutions.

Hyper-ellipsoidal conditions in XCS: Rotation, linear approximation, and solution structure
Butz, M. V., Lanzi, Pier-Luca, & Wilson, S. W.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2006), 1457-1464 (2006)

Abstract The learning classifier system XCS is an iterative rule-learning system that evolves rule structures based on gradient-based prediction and rule quality estimates. Besides classification and reinforcement learning tasks, XCS was applied as an effective function approximator. Hereby, XCS learns space partitions to enable a maximally accurate and general function approximation. Recently, the function approximation approach was improved by replacing (1) hyperrectangular conditions with hyper-ellipsoids and (2) iterative linear approximation with the recursive least squares method. This paper combines the two approaches assessing the usefulness of each. The evolutionary process is further improved by changing the mutation operator implementing an angular mutation that rotates ellipsoidal structures explicitly. Both enhancements improve XCS performance in various non-linear functions. We also analyze the evolving ellipsoidal structures confirming that XCS stretches and rotates the evolving ellipsoids according to the shape of the underlying function. The results confirm that improvements in both the evolutionary approach and the gradient approach can result in significantly better performance.

Studying XCS/BOA learning in Boolean functions: Structure encoding and random boolean functions
Butz, M. V., & Pelikan, M.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2006), 1449-1456 (2006)

Abstract Recently, studies with the XCS classifier system on Boolean functions have shown that in certain types of functions simple crossover operators can lead to disruption and, consequently, a more effective recombination mechanism is required. Simple crossover operators were replaced by recombination based on estimation of distribution algorithms (EDAs). The combination showed that XCS with such a statistics-based crossover operator can solve challenging hierarchical functions more efficiently. This study elaborates the gained competence further investigating the coding scheme for the EDA component (BOA in our case) of XCS as well as performance in randomly generated Boolean function problems. Results in hierarchical Boolean functions show that the originally used 2-bit coding scheme induces a certain learning bias that stresses additional diversity in the evolving XCS population. A 1-bit coding scheme as well as a restricted 2-bit coding scheme confirm the suspected bias. The alternative encodings decrease the unnecessary bias towards specificity and increase performance robustness. The paper concludes with a discussion on the challenges ahead for XCS in Boolean function problems as well as on the implications of the obtained results for real-valued and multiple-valued classification problems, multi-step problems, and function approximation problems.

Unsupervised Learning of Inverse Dynamics Model
Herbort, O., & Butz, M. V.
CogSys II Radboud University Nijmegen, The Netherlands 12-13 April, 45 (2006)

Abstract The ability to interact efficiently and goal-directedly with a complex, dynamic, noisy environment is of paramount importance for any adaptive cognitive organism. To exert goal directed behavior, the organism must be able to convert a desired perceptual state into actual motor commands based on its experienced interactions with the environment. Thereby, the organism faces several problems: (1) Appropriate actions have to be triggered based on current state and selected goals (inverse dynamics). (2) The selected actions should optimize performance, that is, minimize effort (optimality principles). (3) These dynamics should be learned while interacting with the environment, without an actual teacher (unsupervised learning). Insights from psychology and neuroscience suggest that the problem of how to choose the right action given situation and goals is based on an anticipatory, successive decomposition of (perceptual) goals into progressively more action-related sub-goals. Our research focuses on the realization of such an anticipatory, adaptive system. We present an artificial recurrent neural network (ARNN) controller that implements an inverse dynamics model that incorporates optimality principles. The network can be entirely trained by unsupervised associative learning. We propose that a set of interacting modules can be used to control complex behavior by a cascade of ARNN controllers. The controller is implemented in a computational model and applied to a simple motor-arm control task.

Towards an Adaptive Hierarchical Anticipatory Behavioral Control System
Herbort, O., Butz, M.V.,& Hoffmann, J. AAAI Fall Symposium
(2005).

Abstract Despite recent successes in control theoretical programs for limb control, behavior-based cognitive approaches for control are somewhat lacking behind. Insights in psychology and neuroscience suggest that the most important ingredients for a successful developmental approach to control are anticipatory mechanisms and hierarchical structures. Anticipatory mechanisms are beneficial in handling noisy sensors, bridging sensory delays, and directing attention and action processing capacities. Moreover, action selection may be immediate using inverse modeling techniques. Hierarchies enable anticipatory influences on multiple levels of abstraction in time and space. This paper provides an overview over recent insights in anticipatory, hierarchical, cognitive behavioral mechanisms, reviews previous modeling approaches, and introduces a novel model well-suited to study hierarchical anticipatory behavioral control in simulated as well as real robotic control scenarios.

Download Submitted Paper in pdf format

Gradient Descent Methods in Learning Classifier Systems: Improving XCS Performance in Multistep Problems
Butz, M.V., Goldberg, D.E.,& Lanzi, P.L.
IEEE Transactions on Evolutionary Computation, 9, 452-473 (2005).

Abstract The accuracy-based XCS classifier system has been shown to solve typical data mining problems in a machine-learning competitive way. However, successful applications in multistep problems, modeled by a Markov decision process, were restricted to very small problems. Until now, the temporal difference learning technique in XCS was based on deterministic updates. However, since a prediction is actually generated by a set of rules in XCS and Learning Classifier Systems in general, gradient-based update methods are applicable. The extension of XCS to gradient-based update methods results in a classifier system that is more robust and more parameter independent solving large and difficult maze problems reliably. Additionally, the paper highlights the relation of XCS to other function approximation methods in reinforcement learning.

Download earlier and shorter technical report version in compressed postscript format - journal version recommended, though.

Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system
Butz, M.V.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005)
pp. 1835-1842.

Abstract Many learning classifier system (LCS) implementations are restricted to the binary problem realm. Recently, the XCS classifier system was enhanced to be able to handle real-valued inputs among others. In the real-valued enhancement, XCSF applies as a function approximation system that partitions the input space in hyperrectangular subspaces specified in the classifiers. This paper changes the classifier conditions to hyperspheres and hyperellipsoids and investigates the consequent performance impact. It is shown that the modifications yield improved performance in continuous functions. Even in discontinuous functions with parallel boundaries, XCS's performance does not degrade. Thus, for the real-valued problem domain, ellipsoidal condition structures can improve XCS's performance. From a more general perspective, this paper shows that XCS is readily applicable in diverse problem domains. To apply the system even more successfully, suitable kernel-based bases need to be found and used as classifier conditions. XCS distributes the available structures over the problem space evolving more specialized structures in more complex problem subspaces.

Download submitted version in pdf format.

Extracted global structure makes local building block processing effective in XCS
Butz, M.V., Goldberg, David E.,& Lanzi, P.L.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005)
pp. 655-662.

Abstract Michigan-style learning classifier systems (LCSs), such as the accuracy-based XCS system, evolve distributed problem solutions represented by a population of rules. Recently, it was shown that decomposable problems may require effective processing of subsets of problem attributes, which cannot be generally assured with standard crossover operators. A number of competent crossover operators capable of effective identification and processing of arbitrary subsets of variables or string positions were proposed for genetic and evolutionary algorithms. This paper effectively introduces two competent crossover operators to XCS by incorporating techniques from competent genetic algorithms (GAs): the extended compact GA (ECGA) and the Bayesian optimization algorithm (BOA). Instead of applying standard crossover operators, here a probabilistic model of the global population is built and sampled to generate offspring classifiers locally. Various offspring generation methods are introduced and evaluated. Results indicate that the performance of the proposed learning classifier systems XCS/ECGA and XCS/BOA is similar to that of XCS with informed crossover operators that is given all information about problem structure on input and exploits this knowledge using problem-specific crossover operators.

Download earlier technical report version in pdf format

Computational complexity of the XCS classifier system
Butz, M.V., Goldberg, David E.,& Lanzi, P.L.
In Bull, L., Kovacs, T. (Eds.) Foundations of Learning Classifier Systems
pp. 91-126 (2005).

Abstract Although Learning Classifier Systems date back more than twenty years ago, theory regard- ing issues like convergence or computational effort remained sparse. This paper establishes a PAC learning bound for the accuracy-based classifier system XCS. XCS is a flexible genetic-based learning mechanism applicable in classification problems, reinforcement learning problems, as well as different types of representations. Using a facet-wise analysis focusing on the learning of Boolean functions, we show that given several assumptions, k-DNF and related Boolean func- tions are PAC-learnable by XCS. The facet-wise analysis is modular, flexible, and extendable to other problem types and representations.

Download earlier technical report version in pdf format

Towards the Advantages of Hierarchical Anticipatory Behavioral Control
Herbort, O., Butz, M.V.,& Hoffmann, J. Proceedings of KogWis05. The German Cognitive Science Conference 2005, Schwabe, 2005, 77-82

Abstract Despite recent successes in control theoretical programs for limb control, behavior-based cognitive approaches for control are somewhat lacking behind. Insights in psychology and neuroscience suggest that the most important ingredients for a successful developmental approach to control are anticipatory mechanisms and hierarchical structures. Anticipatory mechanisms are beneficial in handling noisy sensors, bridging sensory delays, and directing attention and action processing capacities. Moreover, action selection may be immediate using inverse modeling techniques. Hierarchies enable anticipatory influences on multiple levels of abstraction in time and space. This paper provides an overview over recent insights in anticipatory, hierarchical, cognitive behavioral mechanisms, reviews previous modeling approaches, and introduces a novel model well-suited to study hierarchical anticipatory behavioral control in simulated as well as real robotic control scenarios.

Download Submitted Paper in pdf format

Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection
Butz, M. V., Sastry, Kumara,& Goldberg, David E.
Genetic Programming and Evolvable Machines, 6, 53-77.
also : IlliGAL Report No. 2003025

Abstract Recent analysis of the XCS classifier system have shown that successful genetic learning strongly depends on the amount of fitness pressure towards accurate classifiers. Since the traditionally used proportionate selection is dependent on fitness scaling and fitness distribution, the resulting evolutionary fitness pressure may be neither stable nor sufficiently strong. Thus, we apply tournament selection to XCS. In particular, we exhibit the weakness of proportionate selection and suggest tournament selection as a more reliable alternative. We show that tournament selection results in a learning classifier system that is more parameter independent, noise independent, and more efficient in exploiting fitness guidance in single-step problems as well as multistep problems. The evolving population is more focused on promising subregions of the problem space and thus finds the desired accurate, maximally general representation faster and more reliably.

Download Technical Report in ps.Z format

Anticipation for Learning, Cognition, and Education
Butz, M. V.
On the Horizon

2004, 12, 111-116.

Abstract Predictions, desires, or intentions have recently shown to strongly influence behavior, adaptation, and learning. These anticipations influence behavior mediating decision making and action execution as well as attention. Although it is not the future itself that influences the present but the anticipated future states or future properties, the difference to purely stimulus driven behavior and learning is highly significant. Recent analyses investigate under which environmental properties which type of anticipatory mechanism is helpful to improve behavior. Vice versa, since anticipatory mechanisms also bias attention, future sensory processing and thus future learning capabilities are immediately influenced by current anticipations. The impact on the understanding of the world, social systems, human learning and understanding, as well as education principles might be immense. The perspective of expectation and purpose as part of the cause in the general case might have been underestimated and requires further investigations and considerations.

Download in pdf format

Toward a Cognitive Sequence Learner: Hierarchy, Self-Organization, and Top-down Bottom-up Interaction
Butz, M. V.
IlliGAL report 2004021, University of Illinois at Urbana-Champaign (2004)

Abstract This paper introduces a hierarchical learning architecture that grows online an adaptive problem representation from scratch. The representation extracts frequent perceptual patterns representing them in a layered hierarchy where neural activity in higher layers is initiated bottom-up by firing neurons in lower layers and, vice versa, firing neurons in higher layers predispose activity and provide reinforcement feedback to neurons in lower layers. The structure evolves by a mixture of reinforcement learning and a genetic algorithm. Learning is biased towards extracting frequently recurring sequences in an input stream. We evaluate the architecture on a text document, which is presented iteratively---character by character---to the system. The results show that the proposed system reliably evolves representations of most frequent characters, syllables, and words in the document. We also confirm that top-down influences bias the evolution of syllable and character representations.
Download Technical Report in pdf format

Knowledge extraction and problem structure identification in XCS
Butz, M.V., Lanzi, P.L., Llorà, X., Goldberg, D.E.
Parallel Problem Solving from Nature - PPSN VIII, LNCS 3242
pp. 1051-1060. Springer Verlag, Berlin (2004)

Abstract XCS has been shown to solve hard problems in a machine-learning competitive way. Recent theoretical advancements show that the system can scale-up polynomially in the problem complexity and problem size given the problem is a k-DNF with certain properties. This paper addresses two major issues in XCS: (1) knowledge extraction and (2) structure identification. Knowledge extraction addresses the issue of mining problem knowledge from the final solution developed by XCS. The goal is to identify most important features in the problem and the dependencies among those features. The extracted knowledge may not only be used for further data mining, but may actually be re-fed into the system giving it further competence in solving problems in which dependent features, that is, building blocks, need to be processed effectively. This paper proposes to extract a feature dependency tree out of the developed rule-based problem representation of XCS. The investigations herein focus on Boolean function problems. The extension to nominal and real-valued features is discussed.
Download Technical Report in pdf format

Speeding-Up Pittsburgh Learning Classifier Systems: Modeling Time and Accuracy
Bacardit, J., Goldberg, D.E., Butz, M.V., Llorà, X.,& Garrell, J.M.
Parallel Problem Solving from Nature - PPSN VIII, LNCS 3242
pp. 1021-1031. Springer Verlag, Berlin (2004)

Abstract Windowing methods are useful techniques to reduce the computational cost of Pittsburgh style genetic-based machine learning techniques. If used properly, they additionally can be used to improve the classification accuracy of the system. In this paper we develop a theoretical framework for a windowing scheme called ILAS, developed previously by the authors. The framework allows us to approximate the degree of windowing we can apply to a given dataset as well as the gain in run-time. The framework sets the first stage for the development of a larger methodology with several types of learning strategies in which we can apply ILAS, such as maximizing the learning performance of the system, or achieving the maximum run-time reduction without significant accuracy loss.
Download Technical Report in pdf format

Toward a Theory of Generalization and Learning in XCS
Butz, M. V., Kovacs, Tim, Lanzi, Pier Luca, & Wilson, Stewart W.
IEEE Transaction on Evolutionary Computation, 8, 28-46 (2004)
previous version available as IlliGAL technical report 2002011

Abstract In this paper we provide the very first steps toward a theory of generalization and learning in XCS. We start from Wilson's generalization hypothesis which states that in XCS the interaction between niched evolution and panmictic deletion produces an intrinsic pressure toward generality. We analyze the different evolutionary pressures in XCS and derive a simple equation which support Wilson's hypothesis from a theoretical standpoint. The equation is tested with a number of experiments which confirm the basic model of generalization pressure we provide. Then, we focus on the conditions which must be satisfied for the existence of effective fitness or accuracy pressure in XCS. We analyze these conditions, termed ``challenges''. We derive two equations which provide some indications about how to set the population size and the covering probability so as to ensure the development of fitness pressure in XCS. We argue that when the challenges are met, XCS is able to evolve a solution to the problem reliably. When the challenges are not met, we suggest that intrinsic fitness guidance as well as biased reward in a problem might ease the challenges. The equations and the influence of intrinsic fitness guidance and biased reward are tested on Boolean multiplexer. The paper represents an initial contribution to the understanding of XCS functioning and lays the foundation for research on XCS's learning complexity.

Download Technical Report in ps.Z format

Gradient-based Learning Updates Improve XCS Performance in Multistep Problems
Butz, M. V., Goldberg, David E.,& Lanzi, Pier Luca
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004)
pp. 751-762. Springer Verlag, Berlin (2004)

Abstract This paper introduces a gradient-based reward prediction update mechanism to the XCS classifier system as applied in neural-network type learning and function approximation mechanisms. A strong relation of XCS to tabular reinforcement learning and more importantly to neural-based reinforcement learning techniques is drawn. The resulting gradient-based XCS system learns more stable and reliable in previously investigated hard multistep problems. While the investigations are limited to the binary XCS classifier system, the applied gradient-based update mechanism appears also suitable for the real-valued XCS and other learning classifier systems.

Bounding Learning Time in XCS
Butz, M. V., Goldberg, David E.,& Lanzi, Pier Luca
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004)
pp. 739-750. Springer Verlag, Berlin (2004)

Abstract It has been shown empirically that the XCS classifier system solves typical classification problems in a machine learning competitive way. However, until now, no learning time estimate has been available for the system. This paper introduces a time estimate that bounds the learning time of XCS until maximally accurate classifiers are found. We assume a domino convergence model in which each attribute is successively specialized to the correct value. It is shown that learning time in XCS scales polynomial in problem length and exponential in the order of problem difficulty and thus in a machine learning competitive way.
Download Technical Report in pdf format

Effective Online Detection of Task-Independent Landmarks
Butz, M. V., Samarth, Swarup ,& Goldberg, David E.
IlliGAL report 2004002, University of Illinois at Urbana-Champaign (2004)

Abstract One of the key problems in building adaptive autonomous agents is landmark detection. Landmarks can be used for efficient navigation as well as for developing hierarchical cognitive structures. Previous approaches to landmark detection often simply chose landmarks as the agent's location after fixed intervals of time. Other approaches to landmark detection have focused on the reliability and ease of detection of landmarks. However, systems that use landmarks for hierarchy formations rely on a set of landmarks that provides a means for a concise and effective decomposition of the environment. We believe that such a decomposition is achieved most effectively by identifying transitions that partition the environment into relatively independent sub-regions. Using notions of surprise and consolidation via continued novelty, implemented by relatively simple statistics on the sensory inputs, we introduce an online landmark detection mechanism that reliably identifies landmarks that correspond to such transitions. Since the detected landmarks partition the environment into relatively independent subspaces, the resulting set of landmarks should be useful for the formation of an online adaptive hierarchical problem decomposition enabling efficient hierarchical adaptation and cognition.
Download Technical Report in pdf format

Gradient Descent Methods in Learning Classifier Systems
Butz, M. V., Goldberg, David E.,& Lanzi, Pier Luca
IlliGAL report 2003028, University of Illinois at Urbana-Champaign (2003)

Abstract The accuracy-based XCS classifier system has been shown to solve typical data mining problems in a machine-learning competitive way. However, successful applications in multistep problems, modeled by a Markov decision process, were restricted to very small problems. Until now, the temporal difference learning technique in XCS was based on deterministic updates. However, since a prediction is actually generated by a set of rules in XCS and Learning Classifier Systems in general, gradient-based update methods are applicable. The extension of XCS to gradient-based update methods results in a classifier system that is more robust and more parameter independent solving large and difficult maze problems reliably. Additionally, the paper highlights the relation of XCS to other function approximation methods in reinforcement learning.
Download Technical Report in ps.Z format

Documentation of XCS+TS C-Code 1.2
Butz, M. V.
IlliGAL report 2003023, University of Illinois at Urbana-Champaign

Abstract This is the documentation of the XCS 1.2 C-code released on the IlliGAL web-page. The code includes the option to apply tournament selection as well as several other new features in comparison to the XCS1.1 release. Moreover, XCS parameters as well as experimental settings can be specified in a parameter file so that recompiling is not necessary anymore. Finally, an additional output file is generated that determines means and standard deviations over the run experiments. XCS 1.2 is written in ANSI C. This documentation explains the general outline of the code, all possible parameter manipulations, and how to test this implementation on other problems (environments).
Download Technical Report in ps.Z format
Download the Code in compressed TAR

Anticipatory Behavior: Exploiting Knowledge About the Future to Improve Current Behavior
Butz, M. V., Sigaud, Olivier,& Gérard, Pierre,
In Anticipatory Behavior in Adaptive Learning Systems: Foundations, Theories, and Systems (LNCS 2684), Butz, M. V., Sigaud, Olivier,& Gérard, Pierre (Eds.), 1-10, Springer Verlag, Berlin (2003)

Abstract This chapter is meant to give a concise introduction to the topic of this book. The study of anticipatory behavior is referring to behavior that is dependent on predictions, expectations, or intentions of future states. Hereby, behavior includes actual decision making, internal decision making, internal preparatory mechanisms, as well as learning. Despite several recent theoretical approaches on this topic, until now it remains unclear in which situations anticipatory behavior is useful or even mandatory to achieve competent behavior in adaptive learning systems. This book provides a collection of articles that investigate these questions. We provide an overview for all articles relating them to each other and highlighting their significance to anticipatory behavior research in general.
Anticipatory Behavior in Adaptive Learning Systems

Internal Models and Anticipations in Adaptive Learning Systems
Butz, M. V., Sigaud, Olivier,& Gérard, Pierre,
In Anticipatory Behavior in Adaptive Learning Systems: Foundations, Theories, and Systems (LNCS 2684), Butz, M. V., Sigaud, Olivier,& Gérard, Pierre (Eds.), 86-109, Springer Verlag, Berlin (2003)

Abstract The explicit investigation of anticipations in relation to adaptive behavior is a recent approach. This chapter first provides psychological background that motivates and inspires the study of anticipations in the adaptive behavior field. Next, a basic framework for the study of anticipations in adaptive behavior is suggested. Different anticipatory mechanisms are identified and characterized. First fundamental distinctions are drawn between implicitly anticipatory behavior, payoff anticipatory behavior, sensorial anticipatory behavior, and state anticipatory behavior. A case study allows further insights into the drawn distinctions. Many future research direction are suggested.
Anticipatory Behavior in Adaptive Learning Systems

Generalized State Values in an Anticipatory Learning Classifier System
Butz, M. V.,& Goldberg, David E.,
In Anticipatory Behavior in Adaptive Learning Systems: Foundations, Theories, and Systems (LNCS 2684), Butz, M. V., Sigaud, Olivier,& Gérard, Pierre (Eds.), 282-301, Springer Verlag, Berlin (2003)

Abstract This paper introduces generalized state values to the anticipatory learning classifier system ACS2. Previous studies with ACS2 showed that the system reliably evolves an accurate and generalized predictive model in typical Markov decision process (MDP) environments. The predictive model approximates the state transition function of the MDP in a compact, generalized form. However, it was also shown that the evolving generalized predictive model might be over-general for an accurate representation of reinforcement values. Thus, a function approximation module is added that approximates state values. In combination, actual action choice depends on state values predicted by the means of the predictive model yielding anticipatory behavior. It is shown that the function approximation module accurately generalizes the state value function in the investigated MDP.We also suggest the implementation of task dependent anticipatory attentional mechanisms exploiting the representation of the generalized state-value function. Moreover, improvement of the approach by the means of further anticipatory interaction between predictive model learner and state value learner is suggested.
Anticipatory Behavior in Adaptive Learning Systems

Bidirectional ARTMAP: An artificial mirror neuron system
Butz, M. V. and Ray, Sylvian
Proceedings of the International Joint Conference on Neural Networks, 1417-1422, (2003)

Abstract The recent detection of mirror neurons in monkeys suggests that brains encode parts of an observed action in a similar way they encode own actions. This paper models such a mirror system by means of adaptive resonance theory (ART) artificial neural networks coupling them in a manner similar to ARTMAP systems. Particularly, a bidirectional ARTMAP system (BiARTMAP) is created. The system associates executed actions with consequent action-effects. The associative structure gives the system mirror capabilities: On the one hand, perceived environmental changes cause an action association. On the other hand, activated action patterns cause the expectation of resulting environmental change. We also show that many other proposed cognitive processes relate to the BiARTMAP architecture. Future work includes the incorporation of situational dependencies, the combination of BiARTMAP with vector associative maps (VAMs), and the integration of BiARTMAP in a behavioral module enabling anticipatory behavior. Application wise, BiARTMAP can be applied as a general classifier and/or associative network.
Download ps.gz format

Analysis and Improvement of Fitness Exploitation in XCS: Bounding Models, Tournament Selection, and Bilateral Accuracy
Butz, M. V., Goldberg, David E.,& Tharakunnel, K.
Evolutionary Computation, 11, 239-277 (2003)

Abstract The evolutionary learning mechanism in XCS strongly depends on its accuracy-based fitness approach. The approach is meant to result in an evolutionary drive from classifiers of low accuracy to those of high accuracy. Since, given inaccuracy, lower specificity often corresponds to lower accuracy, fitness pressure most often also results in a pressure towards higher specificity. Moreover, fitness pressure should cause the evolutionary process to be innovative in that it combines low-order building blocks of lower accurate classifiers, to higher-order building blocks with higher accuracy. This paper investigates how, when, and where accuracy-based fitness results in successful rule evolution in XCS. Along the way, a weakness in the current proportionate selection method in XCS is identified. Several problem bounds are derived that need to be obeyed to enable proper evolutionary pressure. Moreover, a fitness dilemma is identified that causes accuracy-based fitness to be misleading. Improvements are introduced to XCS to make fitness pressure more robust and overcome the fitness dilemma. Specifically, (1) tournament selection results in a much better fitness-bias exploitation, and (2) bilateral accuracy prevents the fitness dilemma. While the improvements stand for themselves, we believe they also contribute to the ultimate goal of an evolutionary learning system that is able to solve decomposable machine-learning problems quickly, accurately, and reliably. The paper also contributes to the further understanding of XCS in general and the fitness approach in XCS in particular.

also previous version: IlliGAL Report No. 2002027
Download Technical Report in ps.Z format

Bounding the Population Size in XCS to Ensure Reproductive Opportunities
Butz, M. V.,& Goldberg, David E.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003)
pp. 1844-56. Springer Verlag, Berlin (2003)

Abstract Recently, the accuracy-based learning classifier system XCS successfully underwent several comparisons with other established machine learning algorithms. Despite these encouraging results, it is hardly understood how crucial parameters should be set in XCS nor how XCS scales up in larger problems. Previous research identified a covering challenge in XCS that needs to be obeyed to enable the genetic algorithm (GA) from taking place. Furthermore, a schema challenge was identified that, once obeyed, ensures the existence of accurate classifiers. This paper departs from these challenges deriving a reproductive opportunity bound. The bound assured that more accurate classifiers get a chance for reproduction. The relation to the previous bounds as well as the general specificity pressure in XCS are discussed as well. The derived bound shows that XCS scales in a machine learning competitive way.

also previous version: IlliGAL Report No. 2003009
Download Technical Report in ps.Z format

Towards Building Block Propagation in XCS: A Negative Result and Its Implications
Tharakunnel, Kurian, Butz, M. V., & Goldberg, David E.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003)
pp. 1906-1917. Springer Verlag, Berlin (2003)

Abstract The accuracy-based classifier system XCS is currently the most successful learning classifier system. Several recent studies showed that XCS can produce machine-learning competitive results. Nonetheless, until now the evolutionary mechanisms in XCS remained somewhat ill-understood. This study investigates the selectorecombinative capabilities of the current XCS system. We reveal the accuracy dependence of XCS's evolutionary algorithm and identify a fundamental limitation of the accuracy-based fitness approach in certain problems. Implications and future research directions conclude the paper.

Tournament Selection in XCS
Butz, M. V., Sastry, Kumara,& Goldberg, David E.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003)
pp. 1857-1869. Springer Verlag, Berlin (2003)

Abstract Selection in the accuracy-based learning classifier system XCS, introduced by Wilson in 1995, has always been done by the means of proportionate selection. Although it is known from GA literature that proportionate selection is subject to many pitfalls, the LCS community adhered to proportionate selection. In XCS, the accuracy-based fitness is scaled which made proportionate selection work in many problems. This paper investigates performance in Boolean functions in which proportionate selection fails to solve the function. Tournament selection with tournament sizes proportionate to the actual set size is shown to outperform proportionate selection in all investigated problems. Moreover, it is shown that tournament selection makes XCS more independent from various parameter settings. The message of this paper is plain and simple: Who works with XCS should use tournament selection with tournament sizes proportionate to the actual set size.

also previous version: IlliGAL Report No. 2002020
Download Technical Report in ps.Z format

Anticipations Control Behavior: Animal Behavior in an Anticipatory Learning Classifier System
Butz, M. V. and Hoffmann, Joachim
Adaptive Behavior, 10, 75-96

Abstract The concept of anticipations controlling behavior is introduced. Background is provided about the importance of anticipations from a psychological perspective. Based on the psychological background wrapped in a framework of anticipatory behavioral control, the anticipatory learning classifier system ACS2 is explained. ACS2 learns and generalizes online a predictive environmental model (a model that allows the prediction of future environmental states). The model is a subjective model, that is, no global state information is available to the agent. It is shown that ACS2 can simulate anticipatory learning processes and anticipatory controlled behavior by the means of the model. The simulations of various rat experiments, previously conducted by Colwill and Rescorla, show that the incorporation of anticipations is indeed crucial for simulating the behavior observed in rats. Despite the simplicity of the tasks, we show that the observed behavior reaches beyond the capabilities of model-free reinforcement learning as well as model-based reinforcement learning without online generalization. Possible future impacts of anticipations in adaptive learning systems are outlined.

Download Paper in pdf format

The anticipatory classifier system and genetic generalization
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
Natural Computing, 1(4) 427-467
[An improved version, with clarifications and corrections, of: Technical Report No. 2000032 at the Illinois Genetic Algorithms Laboratory]

Abstract
The anticipatory classifier system (ACS) combines the learning classifier system framework with the cognitive learning theory of anticipatory behavioral control. The result is an evolutionary system that builds a complete and generalized predictive environmental model. Reinforcement learning techniques are applied to form a behavioral policy represented in the model. After providing some background as well as outlining the objectives of the system, we explain in detail all involved current processes. Furthermore, we analyze the deficiency of over-specialization in the anticipatory learning process (ALP), the main learning mechanism in the ACS. Consequently, we introduce a genetic algorithm (GA) to the ACS that is meant for generalization of over-specialized classifiers. We show that it is possible to form a symbiosis between a directed specialization and a genetic generalization mechanism achieving a learning mechanism that evolves a complete, accurate, and compact description of the perceived environment. Results in three different environmental settings confirm the usefulness of the genetic algorithm in the ACS. Finally, we discuss future research directions with the ACS and anticipatory systems in general.
Download Technical Report in compressed PS

Internal Models and Anticipations in Adaptive Learning Systems
Butz, M. V. and Sigaud, Olivier and Gérard, Pierre
From Animals to Animats 7: The seventh international conference on the Simulation of Adaptive Behavior (SAB 2002). Workshop Proceedings Adaptive Behavior in Anticipatory Learning Systems (ABiALS 2002)

Abstract
The workshop Adaptive Behavior in Anticipatory Learning Systems 2002 (ABiALS 2002) held in association with the seventh international conference on the Simulation of Adaptive Behavior (SAB 2002) in Edinburgh, Scotland, is the first of its kind. The explicit investigation of anticipations in relation to adaptive behavior is a recent approach. In this introduction to the workshop, we first provide psychological background that motivates and inspires the study of anticipations in the adaptive behavior field. Next, we endow the workshop with a basic framework for the study of anticipations in adaptive behavior. Different anticipatory mechanisms are identified and categorized. First fundamental distinctions are drawn between implicitly anticipatory mechanisms, payoff anticipations, sensorial anticipations, and state anticipations. A case study allows further insights into the drawn distinctions. Moreover, an overview of all accepted workshop contributions is provided categorizing the contributions in the light of the outlined distinctions and highlighting the relations to each other. Many future research directions are suggested.

Download Paper in pdf format

Generalized State Values in an Anticipatory Learning Classifier System
Butz, M. V. and Goldberg, David E.
From Animals to Animats 7: The seventh international conference on the Simulation of Adaptive Behavior (SAB 2002). Workshop Proceedings Adaptive Behavior in Anticipatory Learning Systems (ABiALS 2002)

Abstract
This paper introduces generalized state values to the anticipatory learning classifier system ACS2. Previous studies with ACS2 showed that the system reliably evolves a generalized predictive model in typical Markov decision process (MDP). The predictive model approximates the state transition function of the MDP in a compact, generalized form. However, it was also shown that the evolving predictive model might be over-general for an accurate representation of reinforcement values. Thus, a function approximation module is added that approximates state values. In combination, actual action choice depends on state values predicted by the means of the predictive model yielding anticipatory behavior. It is shown that the function approximation module accurately generalizes the state value function in the investigated MDP. We also suggest the implementation of task dependent anticipatory attentional mechanisms exploiting the representation of the generalized state-value function. Moreover, improvement of the approach by the means of further anticipatory interaction between predictive model learner and state value learner is suggested.

Download Paper in pdf format

State Value Learning with an Anticipatory Learning Classifier System in a Markov Decision Process
Butz, M. V.
Technical Report 2002018 at the Illinois Genetic Algorithms Laboratory

Abstract
This paper addresses the combination of an online generalizing model learner with a state value learner in a Markov decision process (MDP). The model learner evolves online a generalized representation of the MDP's state transition function. The learned model is called predictive model. State values are evaluated by the means of the evolving predictive model representation. State values approximate the Bellman equation giving rise to an optimal policy in the MDP. It is proven that if the reinforcement provision in the MDP only depends on resulting states, state values can be redefined to yield an optimal policy independent of any immediate reward representation. Internal temporal difference learning is applied to further speed up learning of an optimal policy.

Download Technical Report in compressed PS

An Algorithmic Description of ACS2
Butz, M. V. and Goldberg, David E.
In Lanzi, P. L., Stolzmann, W., and S. W. Wilson (Eds.),
Advances in Learning Classifier Systems: 4th International Workshop, IWLCS 2001
pp. 211-230. Berlin: Springer-Verlag (2002).

Abstract
The chapter investigates how model and behavioral learning can be improved in an anticipatory learning classifier system by biasing exploration. First, the applied system ACS2 is explained. Next, an overview over the possibilities of applying exploration biases in an anticipatory learning classifier system and specifically ACS2 is provided. In ACS2, a recency bias termed action delay bias as well as an error bias termed knowledge array bias is implemented. The system is applied in a dynamic maze task and an hand-eye coordination task to validate the biases. The experiments exhibit that biased exploration enables ACS2 to evolve and adapt its internal environmental model faster. Also adaptive behavior is improved.

Biasing exploration in an anticipatory learning classifier system
Butz, M. V.
Advances in Learning Classifier Systems: 4th International Workshop, IWLCS 2001
pp. 3-22. Berlin: Springer-Verlag (2001).

Abstract
The chapter investigates how model and behavioral learning can be improved in an anticipatory learning classifier system by biasing exploration. First, the applied system ACS2 is explained. Next, an overview over the possibilities of applying exploration biases in an anticipatory learning classifier system and specifically ACS2 is provided. In ACS2, a recency bias termed action delay bias as well as an error bias termed knowledge array bias is implemented. The system is applied in a dynamic maze task and an hand-eye coordination task to validate the biases. The experiments exhibit that biased exploration enables ACS2 to evolve and adapt its internal environmental model faster. Also adaptive behavior is improved.

Anticipatory learning classifier systems
Butz, M. V.
Boston, MA. Kluwer Academic Publishers.
Book in the book series Genetic Algorithms and Evolutionary Computation
More information about the book can be found here.

An implementation of the anticipatory classifier system ACS2 in C++
Butz, M. V.
Technical Report 2001026 at the Illinois Genetic Algorithms Laboratory

Abstract
A documentation of a C++ implementation of ACS2, the current state-of-the-art of the anticipatory learning classifier system ACS, is provided. The documentation explains how to get started with the code. A detailed overview of the structure of the code and of all possible parameter manipulations are given. Input and Output interfaces are revealed. Finally, the documentation exhibits how to run ACS2 in the provided test environments as well as how to program new environments for further runs with ACS2.

Download Technical Report in compressed PS
Download the Code in compressed TAR

Analyzing the evolutionary pressures in XCS
Butz, M. V. and Pelikan, M.
In Spector, Lee and Goodman, Erik D. and Wu, Annie and Langdon, W. B. and Voigt, Hans-Michael and Gen, Mitsuo and Sen, Sandip and Dorigo, Marco and Pezeshk, Shahram and Garzon, Max H. and Burke, Edmund
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)
pp. 935-942. San Francisco, CA: Morgan Kaufmann (2001)
(previous version as Technical Report 2001009 at the Illinois Genetic Algorithms Laboratory)

Abstract
After an increasing interest in learning classifier systems and the XCS classifier system in particular, this paper locates and analyzes the distinct evolutionary pressures in XCS. Combining several of the pressures, an equation is derived that validates the generalization hypothesis which was stated by Wilson (1995). A detailed experimental study of the equation exhibits its applicability in predicting the change in specificity in XCS as well as reveals several other specificity influences.

Download Technical Report version in compressed PS

How XCS evolves accurate classifiers
Butz, M. V. and Kovacs, Tim and Lanzi, Pier-Luca and Wilson, Stewart W.
In Spector, Lee and Goodman, Erik D. and Wu, Annie and Langdon, W. B. and Voigt, Hans-Michael and Gen, Mitsuo and Sen, Sandip and Dorigo, Marco and Pezeshk, Shahram and Garzon, Max H. and Burke, Edmund
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)
pp. 927-934. San Francisco, CA: Morgan Kaufmann (2001).
(previous version Technical Report 2001008 at the Illinois Genetic Algorithms Laboratory)

Abstract
Due to the accuracy based fitness approach, the ultimate goal for XCS is the evolution of a compact, complete, and accurate payoff mapping of an environment. This paper investigates what causes the XCS classifier system to evolve accurate classifiers. The investigation leads to two challenges for XCS, the covering challenge and the schema challenge. Both challenges are revealed theoretically and experimentally. Furthermore, the paper provides suggestions for overcoming the challenges as well as investigates environmental properties that can help XCS to overcome the challenges autonomously. Along those lines, a deeper insight into how to set the initial parameter values in XCS is provided.

Download Technical Report version in compressed PS

An Algorithmic Description of XCS
Butz, M. V. and Wilson, Stewart W.
In Lanzi, P. L., Stolzmann, W., and S. W. Wilson (Eds.), Advances in Learning Classifier Systems, LNAI 1996,
pp. 253-272. Berlin: Springer-Verlag (2001)
also
Soft Computing, 6, 144-153 (2002)
[An improved version, with clarifications and corrections, of: Technical Report No. 2000017 at the Illinois Genetic Algorithms Laboratory]

Abstract
A concise description of the XCS classifier system's parameters, structures, and algorithms is presented as an aid to research. The algorithms are written in modular structured pseudo code with accompanying explanations.

Download up-to-date version in gzipped PS

Probability-Enhanced Predictions in the Anticipatory Classifier System
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
In Lanzi, P. L., Stolzmann, W., and S. W. Wilson (Eds.), Advances in Learning Classifier Systems, LNAI 1996,
pp. 37-51. Berlin: Springer-Verlag (2001).
[An improved version, with clarifications and corrections, of: Technical Report No. 2000016, Illinois Genetic Algorithms Laboratory]

Abstract
The Anticipatory Classifier System (ACS) recently showed many capabilities new to the Learning Classifier System field. Due to its enhanced rule structure with an effect part, it forms an internal environmental representation, learns latently besides the common reward learning, and can use many cognitive processes. This paper introduces a probability-enhancement in the predictions of the ACS which enables the system to handle different kinds of non-determinism in an environment. Experiments in two different mazes will show that the ACS is now able to handle action-noise and irrelevant random attributes in the perceptions. Furthermore, applications with a recently introduced GA will reveal the general independence of the two new mechanism as well as the ability of the GA to substantially decrease the population size.

Download technical report version in compressed PS

XCSJava 1.0: An Implementation of the XCS classifier system in Java
Butz, M. V.
Technical Report 2000027 at the Illinois Genetic Algorithms Laboratory

Abstract
The XCSJava 1.0 implementation of the XCS classifier system in Java is freely available from the IlliGAL anonymous ftp-site. The implementation covers the basic features of the XCS classifier system and provides a multiplexer and maze environment for testing purposes. This paper explains how to download, compile, and run the code. Moreover, it explains the object oriented approach in the implementation and the possible parameter manipulation as well as the environmental interface to hook in other test environments. Additionally to the source code, an executable package of the version as well as an XCSJava 1.0 API documentation is provided.

Download Technical Report in compressed PS
Download the Code in compressed TAR

Investigating Generalization in the Anticipatory Classifier System
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
Proceedings of the sixth international conference on Parallel Problem Solving from Nature (PPSN2000)
[previous version as Technical Report 2000014 at the Illinois Genetic Algorithms Laboratory]

Abstract
Recently, a genetic algorithm (GA) was introduced to the Anticipatory Classifier System (ACS) which surmounted the occasional problem of over-specification of rules. This paper investigates the resulting generalization capabilities further by monitoring in detail the performance of the ACS in the highly challenging multiplexer task. Moreover, by comparing the ACS to XCS in this task it is shown that the ACS generates accurate, maximally general rules and its population converges to those rules. Besides the observed ability of latent learning and the formation of an internal environmental representation, this ability of generalization adds a new advantage to the ACS in comparison with similar approaches.

Download Technical Report in compressed PS

First Cognitive Capabilities in the Anticipatory Classifier System
Stolzmann, Wolfgang, Butz, M. V., Hoffmann, Joachim, and Goldberg, David E.
Proceedings of the sixth international conference on the Simulation of Adaptive Behavior (SAB2000), 287-296 (2000).
[previous version as Technical Report 2000008 at the Illinois Genetic Algorithms Laboratory]

Abstract
This paper adds a new viewpoint to the Anticipatory Classifier System (ACS). It approaches the system from a psychological perspective and thus provides new insights to the current system. The main learning mechanism in the ACS, the Anticipatory Learning Process (ALP), evolved out of the psychological learning theory of anticipatory behavioral control. The paper compares the ALP directly to this theory and reveals the similarities. Moreover, it investigates the behavior of the ACS. By simulating previously published rat experiments, the paper compares the behavior of the ACS with the behavior of the rats. Finally, two further cognitive mechanisms are introduced to the ACS. These two mechanisms result in an animal-like behavior of the ACS in the simulations. Furthermore, they prove the usability of the internal environmental model for reward-learning tasks for the first time.

Download Technical Report in compressed PS

Introducing a genetic generalization pressure to the Anticipatory Classifier System
Part 2: Performance Analysis
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000)
[previous version as Technical Report 2000006 at the Illinois Genetic Algorithms Laboratory]

Abstract
The Anticipatory Classifier System (ACS) is able to form a complete internal representation of an environment. Unlike most other classifier system and reinforcement learning approaches, it is able to learn latently (i.e. to learn in an environment without getting any reward). Compared to other systems which are also able to form an internal representation of the outside world, the advantage of the ACS is that it is not forming an identical copy of the environment but it is generating a complete but more general model. After the observation that the model is not necessarily maximally general a genetic generalization pressure was introduced to the ACS (Butz:Technical Report 2000005). This paper focuses on the different mechanisms in the anticipatory learning process, which resembles the specification pressure, and in the genetic algorithm, which realizes the genetic generalization pressure. The capability of generating maximally general rules and evolving a completely converged population is investigated in detail. Furthermore, the paper approaches a first comparison with the XCS classifier system in different mazes and the multiplexer problem.

Download Technical Report in compressed PS

Introducing a genetic generalization pressure to the Anticipatory Classifier System
Part 1: Theoretical approach
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000)
[previous version as Technical Report 2000005 at the Illinois Genetic Algorithms Laboratory]

Abstract
The Anticipatory Classifier System is a learning classifier system that is based on the cognitive mechanism of anticipatory behavioral control. Besides the common reward learning, the ACS is able to learn latently (i.e. to learn in an environment without getting any reward) which is not possible with reinforcement learning techniques. Furthermore, it is forming a complete internal representation of the environment and thus, it is able to use cognitive processes such as reasoning and planning. Latest research showed that there are problems that challenge the current ACS learning mechanism. It was observed that the ACS is not generating accurate, maximally general rules reliably (i.e. rules which are accurate and in the mean time as general as possible), but it is sometimes generating over-specific rules. This paper shows how a genetic algorithm can be used to overcome this present pressure of over-specification in the ACS mechanism with a genetic generalization pressure. The ACS works then as a hybrid which learns latently, forms a cognitive map, and evolves accurate, maximally general rules.

Download Technical Report in compressed PS

An Implementation of the XCS classifier system in C
Butz, M. V.
Technical Report 99021 at the Illinois Genetic Algorithms Laboratory

Abstract
The XCS classifier system was developed by Wilson (1995). The learning mechanism is based on the accuracy of its reward prediction. This method leads to the formation of accurate most general classifiers. This paper explains how to download, compile and use the XCS code version 1.0 written in ANSI C. It discusses how to select various parameter settings, how to add and remove certain procedures in the XCS, how to apply the XCS in the multiplexer environment and diverse woods environments, and how to add code to apply the XCS in other environments. The code provides the mechanisms introduced by Wilson (1995) and the enhancements published by Wilson (1998).

Download Technical Report in compressed PS

New Challenges for an Anticipatory Classifier System: Hard Problems and Possible Solutions
Butz, M. V., Goldberg, David E., and Stolzmann, Wolfgang
Technical Report 99019 at the Illinois Genetic Algorithms Laboratory

Abstract
An Anticipatory Classifier System (ACS) is a learning mechanism based on learning classifier systems and the cognitive model of ``Anticipatory Behavioral Control''. By comparing perceived consequences with its own expectations (anticipations), an ACS is able to learn in multi-step environments. To date, the ACS has proven its abilities in various problems of that kind. It is able to learn latently (i.e. to learn without getting any reward) and it is able to distinguish between non-Markov states. Additionally, an ACS is capable of incrementally building a cognitive map that can be used to do action-planning. Although the ACS has proven to scale up in suitable environments, it depends on certain environmental properties. It believes itself to be the only agent that can change the perceptions received from an environment. Any environmental change is considered and believed to be caused by the executed actions. The ACS learns from the changes by using fixed mechanisms. This paper reveals the properties of an environment that the current ACS assumes to be given. By investigating the problems of the current ACS when violating these properties we believe that this investigation will immediately serve for a better understanding of the ACS and lead to many ideas to improve the current ACS. We will propose some ideas and discuss the important ones in more detail.

Download Technical Report in compressed PS

Action-Planning in Anticipatory Classifier Systems
Butz, M. V. & Stolzmann, Wolfgang
Presented on the Second International Workshop on Learning Classifier Systems (2.IWLCS'99) during the Genetic and Evolutionary Computation Conference (GECCO 1999)
Also appeared in a slightly different form In Lanzi, Stolzmann, & Wilson (Eds.), Learning Classifier Systems - From Foundations to Applications.
In chapter Latent learning and action-planning in robots with Anticipatory Classifier Systems.

Abstract
Learning consists in the acquisition of knowledge. In Reinforcement Learning this is knowledge about how to reach a maximum of environmental reward. We are interested in the acquisition of knowledge that consists in having expectations of behavioral consequences. Behavioral consequences depend on the current situation, so it is necessary to learn in which situation S which behavior/reaction R leads to which behavioral consequences C. In other words, SRC units are learned. It was the psychologist Edward Tolman (1932) who firstly stated that animals learn SRC units. Seward (1949) proved that rats are able to learn in the absence of reward and confirmed Tolman's assumption. Learning in the absence of reinforcement is called 'latent learning' and cannot be explained by usual reinforcement learning techniques. In the field of Learning Classifier Systems (LCS) latent learning is realized in Riolo's CFSC2 (Riolo, 1991) and Stolzmann's ACS (Stolzmann, 1997, 1998). Both authors prove the performance of their learning algorithms with a simulation of Seward's experiment. This experiment consists in a learning phase without any reward followed by a test phase where the rats have to use the knowledge they acquired during the learning phase to do action-planning. Action-planning and latent learning occur at different times. This paper focuses on the integration of action-planning and latent learning in ACS. Using an example about learning of the hand-eye coordination of a robot arm in conjunction with a camera it will be shown, that a combination of action-planning and latent learning in ACS induces a substantial reduction of the number of trials which are required to learn a complete model of a prototypically environment.

...last modified: 13 September 2007