Catálogo de publicaciones - libros

Rule-based evolutionary online learning systems, often referred to as Michiganstyle learning classifier systems (LCSs) ^1, were originally inspired by the general principles of Darwinian evolution and cognitive learning. In fact, when John Holland proposed the basic LCS framework (Holland, 1976; Holland, 1977; Holland & Reitman, 1978), he actually referred to LCSs as cognitive systems (CSs). Inspired by stimulus-response principles in cognitive psychology, Holland designed CSs to evolve a set of production rules that convert given input into useful output. Temporary memory in the form of a message list was added to simulate inner mental states situating the system in the current environmental context.

LCSs are designed to solve classification as well as more general reinforcement learning (RL) problems. LCSs solve these problems by evolving a rule-base of classifiers by the means of a critic based on RL techniques for rule evaluation and a GA for rule evolution. Before jumping directly into the LCS arena, we first look at these prerequisites.

Learning Classifier Systems (LCSs) (Holland, 1976; Booker, Goldberg, & Holland, 1989) are rule-based evolutionary learning systems. A basic LCS consists of (1) a set of rules, that is, a population of classifiers , (2) a rule evaluation mechanism, which usually is realized by adapted reinforcement learning (RL) (Kaelbling, Littman, & Moore, 1996; Sutton & Barto, 1998) techniques, and (3) a rule evolution mechanism, which is usually implemented by a genetic algorithm (GA) (Holland, 1975). The classifier population codes the current knowledge of the LCS. The evaluation mechanism estimates and propagates rule utility. Based on the estimated utilities, the evolutionary mechanism generates offspring classifiers and deletes less useful classifiers.

The creation of the accuracy-based classifier system XCS (Wilson, 1995) can be considered a milestone in classifier system research. XCS addresses the general LCS challenges in a very distributed fashion. The problem of generalization is approached by niche reproduction in conjunction with panmictic (population-wide) deletion. The problem of strong overgenerals is solved by deriving classifier fitness from the estimated accuracy of reward predictions instead of from the reward predictions themselves. In effect, XCS is designed to not only evolve a representation of the best solution for all possible problem instances but rather to evolve a complete and accurate payoff map of all possible solutions for all possible problem instances.

The last chapter gave a concise introduction to the accuracy-based XCS classi fier system. We saw that XCS is designed to evolve online a complete, maximally accurate, and maximally general solution to the problem at hand (e.g. by approximating the Q-value function). The accuracy-based approach assures that no strong overgenerals are possible since the maximally accurate classifiers receive maximal fitness.

The last chapter investigated fitness guidance and generalization in the XCS classifier system. We saw that several evolutionary pressures apply that are designed to push the evolutionary process towards the desired complete, maximally accurate, and maximally general problem solutions. To ensure reliable fitness pressure, offspring should be selected using tournament selection with tournament sizes proportional to the current action set size to ensure a constant minimal pressure towards selecting better offspring in action sets.

The facetwise approach to GA theory stresses effective mixing and decision making among BBs. The last chapter showed that in XCS, BBs are subsets of specified attributes that increase accuracy. The reproductive opportunity bound additionally ensures that BBs are able to grow in the population making time for the identification and reproduction of schema representatives. Until now, we assumed that mutation is sufficient to generate better classifiers as investigated in the time bound. However, the GA literature suggests that effective crossover operators are mandatory to solve boundedly difficulty optimization problems in which small, lower-level BBs may mislead the population to a local optimum.

With all parts of the facetwise theory in place, this chapter applies XCS to several further binary classification problems experimentally, confirming the usefulness of the introduced XCS enhancements as well as the theoretic learning behavior. In particular, we investigate further the effects of tournament selection, fitness pressure, the influence of noise, niching, model-based off- spring generation and overlapping problems. ^1

This chapter investigates XCS’s performance in various real- and/or nominal valued datasets as well as in function approximation problems. The application to problems other than binary valued ones requires a modification of the XCS classifier system condition parts as well as its genetic operators including covering, mutation, and crossover.

The performance investigations of XCS in various classification problems including diverse Boolean function problems as well as datamining problems showed that the facetwise LCS theory can predict XCS’s behavior accurately. We confirmed the importance of appropriate selection pressure, population sizing and specificity, as well as the dependence on problem properties such as the minimal order complexity, infrequent niche occurrences, or overlapping solution representations. The datamining applications confirmed XCS’s machine learning competitive learning behavior in terms of accuracy and solution generality.