Math (Несколько текстов для зачёта), страница 10

(8) |a> arrow right |s> arrow right |f>,

which satisfies the consistency conditions simply because it is a solution of Schrodinger's equation.

On the other hand, the pair of mutually exclusive histories

(9) |a> arrow right |c> arrow right |f> and |a> arrow right |d> |f?,

in which the particle passes through either the c or d arm at the intermediate time t[sub 2] and then emerges in the f channel, are not consistent, because the corresponding weight operators are not orthogonal. The reader may check this by the methods of reference 9, but it will require some work.

Consequently, it makes no sense to say that the particle passes through the c or the d arm and then emerges in the f channel. However, the two histories

(10) |a> arrow right |c> arrow right (|e> + |f>)/ square root of 2 |a> arrow right |d> arrow right (-|e> + |f>)/ square root of 2

are consistent, because here the weight operators are orthogonal. Again we leave the proof as an exercise. Thus it makes perfectly good sense to say that the photon passes through the c arm and emerges in a certain coherent superposition of states in the two output channels, or through the d arm to emerge in a different superposition.

This Mach-Zehnder example is analogous to the canonical double-slit experiment, if one regards passing through the c or d arm as analogous to passing through the upper or lower slit, and emerging in e or f as analogous to the particle arriving at a point of minimum or maximum intensity in the double-slit interference zone.

AN ANALYSIS OF GENERALIZATION IN THE XCS CLASSIFIER SYSTEM

Source: Evolutionary Computation, Summer99, Vol. 7 Issue 2, p125, 25p, 2 diagrams, 14 graphs Author(s): Lanzi, Pier Luca

Abstract

The XCS classifier system represents a major advance in learning classifier systems research because (1) it has a sound and accurate generalization mechanism, and (2) its learning mechanism is based on Q-learning, a recognized learning technique. In taking XCS beyond its very first environments and parameter settings, we show that, in certain difficult sequential ("animat") environments, performance is poor. We suggest that this occurs because in the chosen environments, some conditions for proper functioning of the generalization mechanism do not hold, resulting in overly general classifiers that cause reduced performance. We hypothesize that one such condition is a lack of sufficiently wide exploration of the environment during learning. We show that if XCS is forced to explore its environment more completely, performance improves dramatically. We propose a technique, based on Sutton's Dyna concept, through which wider exploration would occur naturally. Separately, we demonstrate that the compacmess of the representation evolved by XCS is limited by the number of instances of each generalization actually present in the environment. The paper shows that XCS's generalization mechanism is effective, but that the conditions under which it works must be clearly understood.

Keywords

Learning classifier systems, XCS, generalization, genetic operators.

1 Introduction

Autonomous agents are not, in general, able to deal with the complexity of real environments. The ability of an agent to generalize over the different situations it experiences is essential in order to learn tasks in real environments. In fact, an agent which generalizes properly is able to synthesize, in a compact way, the knowledge it acquires so as to manipulate the concepts it learns.

Generalization is a very important feature of XCS, the classifier system introduced by Wilson (1995). XCS has been shown to evolve near-minimal populations of classifiers that are accurate and maximally general (Kovacs, 1997; Wilson, 1997a). Recently, Kovacs (1997) proposed an optimality hypothesis for XCS and presented experimental evidence of his hypothesis with respect to the Boolean multiplexer, a known testbed for studying generalization in learning classifier systems (Wilson, 1987; Wilson, 1995).

In taking XCS beyond its very first environments and parameter settings, Lanzi (1997) reported experimental results for problems involving artificial animals, animats (Wilson, 1987), showing that in difficult sequential problems XCS performance may fail dramatically. The author observed that in these kinds of tasks the generalization mechanism of XCS can be too slow to delete overly general classifiers before they proliferate in the population. In order to avoid this problem, Lanzi (1997) introduced a new operator, called specify, which helps XCS delete overly general classifiers by replacing them with more specific offspring. An alternate solution was suggested by Wilson in which the random exploration strategy employed in his first experiments with XCS was replaced with biased exploration (Wilson, 1997b).

Until recently (Kovacs, 1996; Lanzi, 1997b), the analysis of the generalization capabilities of XCS has been presented without considering the relation between XCS's performance and the environment structure. As a result it is not clear why one environment is easy to solve, while a similar one can be much more difficult.

The aim of this paper is to suggest an answer to this question enabling a better understanding of the generalization mechanism of XCS, while giving a unified view of the observations in Lanzi (1997) and Wilson (1997). First, we extend the results presented by Lanzi comparing the performance of XCS when it uses specify and when it employs the biased exploration strategy. The comparison is done in two new environments, Maze5 and Maze6, and then in Woods 14, the ribbon problem introduced by Cliff and Ross (1994). The results we present demonstrate that specify can adapt to all the three test environments while XCS with biased exploration may fail to converge to optimal solutions as the complexity of the environment increases. Although these results are interesting, they simply report experimental evidence and do not explain XCS's behavior which is our major goal. In order to explain XCS's behavior, we analyze the assumptions which underlie generalization in XCS and Wilson's generalization hypothesis (Wilson, 1995). We study XCS's generalization mechanism in depth and formulate a specific hypothesis. We verify our hypothesis by introducing a meta-exploration strategy, teletransportation, which we use as a validation tool.

We end the paper discussing another important aspect of generalization within XCS-the capability of XCS to evolve a maximally compact representation of the learned task. We show that, in particularly difficult environments, where few generalizations are admissible, XCS evolves generalizations right up to the limit of the instances actually offered by the environment.

The remainder of this paper is organized as follows: Section 2 gives a brief overview of the current version of XCS, and Section 3 presents the design of the experiments we employed in this paper. XCS with specify, referred to as XCSS, and XCS with biased exploration are compared in Section 4 using Maze5 and Maze6. In Section 5, the same comparison is done in the Woods14 environment. The results described in the previous sections are discussed in Section 6 where we formulate a hypothesis in order to explain why XCS may fail to converge to an optimal solution and discuss the implications introduced by our hypothesis. We verify our hypothesis in Section 7 by introducing teletransportation. We suggest how the ideas underlying teletransportation might be implemented in real-world applications in Section 8. Section 9 addresses the conditions under which XCS evolves a compact representation of a learned task, and Section 10 summarizes the results.

2 Description of XCS

We now overview XCS according to its most recent version (Wilson, 1997a). We refer the interested reader to Wilson (1995) for the original XCS description or to Kovacs's report (Kovacs, 1996) for a more detailed discussion for implementors.

Classifiers in XCS have three main parameters: (1) the prediction p, which estimates the payoff that the system expects if the classifier is used; (2) the prediction error c, which estimates the error of the prediction p; and (3) the fitness F, which evaluates the accuracy of the payoff prediction given by p and thus is a function of the prediction error Epsilon.

At each time step, the system input is used to build the match set [M] containing the classifiers in the population whose condition part matches the sensory configuration. If the match set is empty a new classifier which matches the input is created through covering. For each possible action a[sub i] in the match set, the system prediction P(a[sub i]) is computed as the fitness weighted average of the classifier predictions that advocate the action a[sub i] in [M]. P(a[sub i]) gives an evaluation of the expected payoff if action a[sub i] is performed. Action selection can be deterministic, the action with the highest system prediction is chosen, or probabilistic, the action is chosen with a certain probability among the actions with a non-null prediction.

The classifiers in [M], which propose the selected action, form the current action set [A]. The selected action is then performed in the environment and a scalar reward r is returned to the system together with a new input configuration.

The reward r is used to update the parameters of the classifiers in the action set corresponding to the previous time step [A][sub -1]. Classifier parameters are updated as follows. First, the Q-learning-like payoff P is computed as the sum of the reward received at the previous time step and the maximum system prediction, discounted by a factor Gamma (0 </= Gamma < 1). P is used to update the prediction p by the Widrow-Hoff delta rule (Widrow and Hoff, 1960) with learning rate Beta (0 </= Beta </= 1): p[sub j] arrow left p[sub j] + Beta (P - p[sub j]). Likewise, the prediction error Epsilon is adjusted with the formula: Epsilon arrow left Epsilon[sub j] + Beta(|P - p| Epsilon). The fitness update is slightly more complex. Initially, the prediction error is used to evaluate the classification accuracy Kappa of each classifier as Kappa = exp(ln Alpha(Epsilon - Epsilon[sub 0])/Epsilon[sub 0]) if Epsilon > Epsilon[sub 0] or Kappa = 1 otherwise. Subsequently the relative accuracy Kappa' of the classifier is computed from Kappa as Kappa' = Kappa/Sigma[sub [A][sub -1]] Kappa. Finally, the fitness parameter is adjusted by the rule F arrow left F + Beta(Kappa' - F).

The genetic algorithm in XCS is applied to the action set. It selects two classifiers with probability proportional to their fitnesses and copies them. It performs crossover on the copies using probability Chi while using probability Mu to mutate each allele.

Macroclassifiers. Introduced by Wilson (1995), an important innovation with XCS is the definition of macroclassifiers. These are classifiers that represent a set of classifiers with the same condition and the same action by means of a new parameter called numerosity. Whenever a new classifier has to be inserted in the population, it is compared to existing ones to check whether there already exists a classifier with the same condition-action pair. If such a classifier exists then the new classifier is not inserted in the population. Instead, the numerosity parameter of the existing (macro) classifier is incremented. If there is no classifier in the population with the same condition-action pair then the new classifier is inserted in the population.

Macroclassifiers are, essentially, a programming technique that speeds up learning by reducing the number of classifiers XCS has to process. Wilson shows that use of macroclassifiers substantially reduces the population for normal mutation rates, especially if the environment offers significant generalizations. In addition, he shows that the number of macroclassifiers is a useful statistic for measuring the level of generalization of the solution by the system.

Subsumption Deletion and Specify. Since XCS was introduced, two genetic operators have been proposed as extensions to the original system: subsumption deletion (Wilson, 1997a) and specify (Lanzi, 1997b).

Subsumption deletion was introduced to improve the generalization capability of XCS. Subsumption deletion acts when classifiers created by the genetic algorithm are inserted in the population. Offspring classifiers created by the GA are replaced with clones of their parents if: (1) they are specializations of the two parents, i.e., they are subsumed by their parents, (2) their parents are accurate, and (3) the parameters of their parents have been updated sufficiently. If all these conditions are satisfied the offspring classifiers are discarded and copies of their parents are inserted in the population; otherwise, the offspring are inserted in the population.