Self-adaptation of learning rate in XCS working in noisy and dynamic environments

An extended classifier system (XCS) is an adaptive rule-based technique that uses evolutionary search and reinforcement learning to evolve complete, accurate, and maximally general payoff map of an environment. The payoff map is represented by a set of condition-action rules called classifiers. Despite this insight, till now parameter-setting problem associated with LCS/XCS has important drawbacks. Moreover, the optimal values of some parameters are strongly influenced by properties of the environment like its complexity, changeability, and the level of noise. The aim of this paper is to overcome some of these difficulties by a self-adaptation of a learning rate parameter, which plays a key role in reinforcement learning, since it is used for updates of classifier parameters: prediction, prediction error, fitness, and action set estimation. Self-adaptive control of prediction learning rate is investigated in the XCS, whereas the fitness and error learning rates remain fixed. Simultaneous self-adaptation of prediction learning rate and mutation rate also undergo experiments. Self-adaptive XCS solves one-step problems in noisy and dynamic environments.     

Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy

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.     

Isolating an Odd Number of Elements and Applications in Complexity Theory

Naor and Naor [11] implicitly isolate an odd number of elements of a nonempty set of n -bit vectors. We perform a tighter analysis of their construction and obtain better probability bounds. Using this construction, we improve bounds on several results in complexity theory that originally used a construction due to Valiant and Vazirani [18]. In particular, we obtain better bounds on polynomials which approximate boolean functions; improve bounds on the running time of the ⊕ P machine in Toda's result [16]; and improve bounds on the size of threshold circuits accepting languages accepted by AC ⁰ circuits. Received July 1993, and in revised form January 1995, and in final form February 1997.     

XCS-based reinforcement learning algorithm for motion planning of a spherical mobile robot

A Reinforcement Learning (RL) algorithm based on eXtended Classifier System (XCS) is used to navigate a spherical robot. Traditional motion planning strategies rely on pre-planned optimal trajectories and feedback control techniques. The proposed learning agent approach enjoys a direct model-free methodology that enables the robot to function in dynamic and/or partially observable environments. The agent uses a set of guard-action rules that determines the motion inputs at each step. Using a number of control inputs (actions) and the developed RL scheme, the agent learns to make near-optimal moves in response to the incoming position/orientation signals. The proposed method employs an improved variant of the XCS as its learning agent. Results of several simulated experiments for the spherical robot show that this approach is capable of planning a near-optimal path to a predefined target from any given position/orientation.     

On optimal parameter selection for parabolic differential systems

In ordinary differential systems, it has been shown [4] recently that Boltyanskii's necessary conditions for optimal parameter selection [3, p. 263] can be easily derived from Gamkrelidze's general maximum principle [2]. In this note, necessary conditions on optimal parameter selection problem of parabolic differential systems are reported by using a recent result of Zolezzi [1]. The result is illustrated by an example.     

Batch Process Modelling and Optimal Control Based on Neural Network Model

This paper presents several neural network based modelling, reliable optimal control, and iterative learning control methods for batch processes. In order to overcome the lack of robustness of a single neural network, bootstrap aggregated neural networks are used to build reliable data based empirical models. Apart from improving the model generalisation capability, a bootstrap aggregated neural network can also provide model prediction confidence bounds. A reliable optimal control method by incorporating model prediction confidence bounds into the optimisation objective function is presented. A neural network based iterative learning control strategy is presented to overcome the problem due to unknown disturbances and model-plant mismatches. The proposed methods are demonstrated on a simulated batch polymerisation process.     

Batch Process Modelling and Optimal Control Based on Neural Network Models

This paper presents several neural network based modelling, reliable optimal control, and iterative learning control methods for batch processes. In order to overcome the lack of robustness of a single neural network, bootstrap aggregated neural networks are used to build reliable data based empirical models. Apart from improving the model generalisation capability, a bootstrap aggregated neural network can also provide model prediction confidence bounds. A reliable optimal control method by incorporating model prediction confidence bounds into the optimisation objective function is presented. A neural network based iterative learning control strategy is presented to overcome the problem due to unknown disturbances and model-plant mismatches. The proposed methods are demonstrated on a simulated batch polymerisation process.     

Strong,Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection

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.     

Approximation Algorithms for Access Network Design

Abstract. We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale . A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal—dual approach to obtain a solution whose cost is within O(K ² ) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K) . Both bounds are obtained under weak assumptions on the trunk costs. Our primal—dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12].     

On the Applicability of the Interval Gaussian Algorithm

We consider a linear interval system with a regular n × n interval matrix [A] which has the form [A] = I + [-R,R]. For such a system we prove necessary and sufficient conditions for the applicability of the interval Gaussian algorithm where applicability means that the algorithm does not break down by dividing by an interval which contains zero. If this applicability is guaranteed we compare the output vector [x]G with the interval hull of the solution set . In particular, we show that in each entry of [x]G at least one of the two bounds is optimal. Linear interval systems of the above-mentioned form arise when a given general system is preconditioned with the midpoint inverse of the underlying coefficient matrix.     

Learning classifier systems from a reinforcement learning perspective

 We analyze learning classifier systems in the light of tabular reinforcement learning. We note that although genetic algorithms are the most distinctive feature of learning classifier systems, it is not clear whether genetic algorithms are important to learning classifiers systems. In fact, there are models which are strongly based on evolutionary computation (e.g., Wilson's XCS) and others which do not exploit evolutionary computation at all (e.g., Stolzmann's ACS). To find some clarifications, we try to develop learning classifier systems “from scratch”, i.e., starting from one of the most known reinforcement learning technique, Q-learning. We first consider thebasics of reinforcement learning: a problem modeled as a Markov decision process and tabular Q-learning. We introduce a formal framework to define a general purpose rule-based representation which we use to implement tabular Q-learning. We formally define generalization within rules and discuss the possible approaches to extend our rule-based Q-learning with generalization capabilities. We suggest that genetic algorithms are probably the most general approach for adding generalization although they might be not the only solution.     

Toward a theory of generalization and learning in XCS

Takes initial steps toward a theory of generalization and learning in the learning classifier system XCS. We start from Wilson's generalization hypothesis, which states that XCS has an intrinsic tendency to evolve accurate, maximally general classifiers. We analyze the different evolutionary pressures in XCS and derive a simple equation that supports the hypothesis theoretically. The equation is tested with a number of experiments that confirm the model of generalization pressure that we provide. Then, we focus on the conditions, termed "challenges," that must be satisfied for the existence of effective fitness or accuracy pressure in XCS. We derive two equations that suggest how to set the population size and the covering probability so as to ensure the development of fitness pressure. We argue that when the challenges are met, XCS is able to evolve problem solutions reliably. When the challenges are not met, a problem may provide intrinsic fitness guidance or the reward may be biased in such a way that the problem will still be solved. The equations and the influence of intrinsic fitness guidance and biased reward are tested on large Boolean multiplexer problems. The paper is a contribution to understanding how XCS functions and lays the foundation for research on XCS's learning complexity.     

Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates

Consider circuits consisting of a threshold gate at the top, Mod _m gates at the next level (for a fixed m ), and polylog fan-in AND gates at the lowest level. It is a difficult and important open problem to obtain exponential lower bounds for such circuits. Here we prove exponential lower bounds for restricted versions of this model, in which each Mod _m -of-AND subcircuit is a symmetric function of the inputs to that subcircuit. We show that if q is a prime not dividing m , the Mod _q function requires exponential-size circuits of this type. This generalizes recent results and techniques of Cai et al. [CGT] (which held only for q=2 ) and Goldmann (which held only for depth two threshold over Mod _m circuits). As a further generalization of the [CGT] result, the symmetry condition on the Mod _m subcircuits can be relaxed somewhat, still resulting in an exponential lower bound. The basis of the proof is to reduce the problem to estimating an exponential sum, which generalizes the notion of ``correlation" studied by [CGT]. This identifies the type of exponential sum that will be instrumental in proving the general case. Along the way we substantially simplify previous proofs. Received June 1997, and in final form October 1998.     

Gradient descent methods in learning classifier systems: improving XCS performance in multistep problems

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 extension to gradient methods highlights the relation of XCS to other function approximation methods in reinforcement learning.     

A study of structural and parametric learning in XCS

The performance of a learning classifier system is due to its two main components. First, it evolves new structures by generating new rules in a genetic process; second, it adjusts parameters of existing rules, for example rule prediction and accuracy, in an evaluation step, which is not only important for applying the rules, but also for the genetic process. The two components interleave and in the case of XCS drive the population toward a minimal, fit, non-overlapping population. In this work we attempt to gain new insights as to the relative contributions of the two components. We find that the genetic component has an additional role when using the train/test approach which is not present in online learning. We compare XCS to a system in which the rule set is restricted to the initial random population (XCS-NGA, that is, XCS No Genetic Algorithm). For small Boolean functions we can give XCS-NGA all possible rules of a particular condition length. In online learning, XCS-NGA can, given sufficiently many rules, achieve a surprisingly high classification accuracy, comparable to that of XCS. In a train/test approach, however, XCS generalises better than XCS-NGA and there seem to be limitations of XCS-NGA which cannot be overcome simply by increasing the population size. This illustrates that the requirements of a function approximator tend to differ between reinforcement learning (which is typically online) and concept learning (which is typically train/test).     

ROBUST SAMPLED-DATA CONTROL SYSTEMS ANALYSIS BY APPROXIMATE Z-TRANSFORM USING HIGHER-ORDER INTEGRATORS

In this paper, robust sampled-data control systems are analyzed in the frequency domain. Stability analysis of a sampled-data control system using higher-order integrators was proposed by Wang et al. in 1990 [1] and adopted in the approximate Z-transform by Wang et al. in 1997 [2]. We further apply the approximate Z-transform to analyze the stability boundary of a sampled-data control system in which the plant transfer function has bounds prescribed on its parameters.     

On DNA Codes

We develop and study the concept of similarity functions for q-ary sequences. For the case q = 4, these functions can be used for a mathematical model of the DNA duplex energy [1,2], which has a number of applications in molecular biology. Based on these similarity functions, we define a concept of DNA codes [1]. We give brief proofs for some of our unpublished results [3] connected with the well-known deletion similarity function [4–6]. This function is the length of the longest common subsequence; it is used in the theory of codes that correct insertions and deletions [5]. Principal results of the present paper concern another function, called the similarity of blocks. The difference between this function and the deletion similarity is that the common subsequences under consideration should satisfy an additional biologically motivated [2] block condition, so that not all common subsequences are admissible. We prove some lower bounds on the size of an optimal DNA code for the block similarity function. We also consider a construction of close-to-optimal DNA codes which are subcodes of the parity-check one-error-detecting code in the Hamming metric [7].     

k元船方体网络的可靠性

[k]元[n]方体[Qkn]是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于[1≤m≤n-1],设[F]是[Qkn]中的一个由非空点集[VF]和非空边集[EF]构成的故障集,满足[Qkn-F]中不存在[Qkn-m]且[VF]破坏的[Qkn-m]的集合与[EF]破坏的[Qkn-m]的集合互不包含。设[f＊（n,m）]是破坏[Qkn]中的所有子立方[Qkn-m]所需要的故障集[F]的最小基数。证明了对于奇数[k≥3],[fk（n,1）]为[k＋1],[fk（n,n-1）]为[kn-1-1＋n],[f＊（n,m）]的上下界分别为[Cm-1n-1km＋Cm-1n-2km-1]和[km]。举例说明了上界[Cm-1n-1km＋Cm-1n-2km-1]是最优的。     

The Quantum Complexity of Set Membership

   Abstract. We study the quantum complexity of the static set membership problem: given a subset S (|S| ≤ n ) of a universe of size m ( >> n ), store it as a table, T: {0,1} ^r --> {0,1} , of bits so that queries of the form ``Is x in S ?' can be answered. The goal is to use a small table and yet answer queries using few bit probes. This problem was considered recently by Buhrman et al. [BMRV], who showed lower and upper bounds for this problem in the classical deterministic and randomized models. In this paper we formulate this problem in the ``quantum bit probe model'. We assume that access to the table T is provided by means of a black box (oracle) unitary transform O _T that takes the basis state | y,b > to the basis state | y,b