Classificação é, provavelmente, a tarefa mais estudada na área de Aprendizado de Máquina, possuindo aplicação em uma grande quantidade de problemas reais, como categorização de textos, diagnóstico médico, problemas de bioinformática, além de aplicações comerciais e industriais. De um modo geral, os problemas de classificação podem ser categorizados quanto ao número de rótulos de classe que podem ser associados à cada exemplo de entrada. A abordagem mais investigada pela comunidade de Aprendizado de Máquina é a de classes mutuamente exclusivas. Entretanto, existe uma grande variedade de problemas importantes em que cada exemplo de entrada pode ser associado a mais de um rótulo ou classe. Esses problemas são denominados problemas de classificação multirrótulo. Os Learning Classifier Systems(LCS) constituem uma técnica de Indução de Regras de Classificação que tem como principal mecanismo de busca um Algoritmo Genético. Essa técnica busca encontrar um conjunto de regras que tenha alta precisão de classificação, que seja compreensível e que possua regras consideradas interessantes sob o ponto de vista de classificação. Apesar de existirem na literatura diversos trabalhos sobre os LCS para problemas de classificação com classes mutuamente exclusivas...
This paper introduces a distributed data mining approach suited to
grid computing environments based on a supervised learning
classifier system. Different methods of merging data mining
models generated at different distributed sites are explored.
Centralized Data Mining (CDM) is a conventional method of data
mining in distributed data. In CDM, data that is stored in
distributed locations have to be collected and stored in a central
repository before executing the data mining algorithm. CDM
method is reliable; however it is expensive (computational,
communicational and implementation costs are high).
Alternatively, Distributed Data Mining (DDM) approach is
economical but it has limitations in combining local models. In
DDM, the data mining algorithm has to be executed at each one of
the sites to induce a local model. Those induced local models are
collected and combined to form a global data mining model. In
this work six different tactics are used for constructing the global
model in DDM: Generalized Classifier Method (GCM); Specific
Classifier Method (SCM); Weighed Classifier Method (WCM);
Majority Voting Method (MVM); Model Sampling Method
(MSM); and Centralized Training Method (CTM). Preliminary
experimental tests were conducted with two synthetic data sets
(eleven multiplexer and monks3) and a real world data set
(intensive care medicine). The initial results demonstrate that the
performance of DDM methods is competitive when compared
with the CDM methods.; Fundação para a Ciência e a Tecnologia (FCT)
Permutation-based statistics for evaluating the significance of class prediction, predictive attributes, and patterns of association have only appeared within the learning classifier system (LCS) literature since 2012. While still not widely utilized by the LCS research community, formal evaluations of test statistic confidence are imperative to large and complex real world applications such as genetic epidemiology where it is standard practice to quantify the likelihood that a seemingly meaningful statistic could have been obtained purely by chance. LCS algorithms are relatively computationally expensive on their own. The compounding requirements for generating permutation-based statistics may be a limiting factor for some researchers interested in applying LCS algorithms to real world problems. Technology has made LCS parallelization strategies more accessible and thus more popular in recent years. In the present study we examine the benefits of externally parallelizing a series of independent LCS runs such that permutation testing with cross validation becomes more feasible to complete on a single multi-core workstation. We test our python implementation of this strategy in the context of a simulated complex genetic epidemiological data mining problem. Our evaluations indicate that as long as the number of concurrent processes does not exceed the number of CPU cores...
Michigan-style learning classifier systems (M-LCSs) represent an adaptive and powerful class of evolutionary algorithms which distribute the learned solution over a sizable population of rules. However their application to complex real world data mining problems, such as genetic association studies, has been limited. Traditional knowledge discovery strategies for M-LCS rule populations involve sorting and manual rule inspection. While this approach may be sufficient for simpler problems, the confounding influence of noise and the need to discriminate between predictive and non-predictive attributes calls for additional strategies. Additionally, tests of significance must be adapted to M-LCS analyses in order to make them a viable option within fields that require such analyses to assess confidence. In this work we introduce an M-LCS analysis pipeline that combines uniquely applied visualizations with objective statistical evaluation for the identification of predictive attributes, and reliable rule generalizations in noisy single-step data mining problems. This work considers an alternative paradigm for knowledge discovery in M-LCSs, shifting the focus from individual rules to a global, population-wide perspective. We demonstrate the efficacy of this pipeline applied to the identification of epistasis (i.e....
In this report, we show how to prune the population size of the Learning Classifier System XCS for complex problems. We say a problem is complex, when the number of specified bits of the optimal start classifiers (the prob lem dimension) is not constant. First, we derive how to estimate an equiv- alent problem dimension for complex problems based on the optimal start classifiers. With the equivalent problem dimension, we calculate the optimal maximum population size just like for regular problems, which has already been done. We empirically validate our results.
Furthermore, we introduce a subsumption method to reduce the number of classifiers. In contrast to existing methods, we subsume the classifiers after the learning process, so subsuming does not hinder the evolution of optimal classifiers, which has been reported previously. After subsumption, the number of classifiers drops to about the order of magnitude of the optimal classifiers while the correctness rate nearly stays constant.
Classifier systems (Css) provide a rich framework for learning and induction, and they have beenı successfully applied in the artificial intelligence literature for some time. In this paper, both theı architecture and the inferential mechanisms in general CSs are reviewed, and a number of limitations and extensions of the basic approach are summarized. A system based on the CS approach that is capable of quantitative data analysis is outlined and some of its peculiarities discussed.
Let x be a vector of predictors and y a scalar response associated with it. Consider the regression problem of inferring the relantionship between predictors and response on the basis of a sample of observed pairs (x,y). This is a familiar problem for which a variety of methods are available. This paper describes a new method based on the classifier system approach to problem solving. Classifier systems provide a rich framework for learning and induction, and they have been suc:cessfully applied in the artificial intelligence literature for some time. The present method emiches the simplest classifier system architecture with some new heuristic and explores its potential in a purely inferential context. A prototype called PASS (Predictive Adaptative Sequential System) has been built to test these ideas empirically. Preliminary Monte Carlo experiments indicate that PASS is able to discover the structure imposed on the data in a wide array of cases.
In this work, a new Classifier System is proposed (CS). The system, a Reactive with Tags Classifier System (RTCS), is able to take into account environmental situations in intermediate decisions. CSs are special production systems, where conditions and actions are codified in order to learn new rules by means of Genetic Algorithms (GA). The RTCS has been designed to generate sequences of actions like the traditional classifier systems, but RTCS also has the capability of chaining rules among different time instants and reacting to new environmental situations, considering the last environmental situation to take a decision. In addition to the capability to react and generate sequences of actions, the design of a new rule codification allows the evolution of groups of specialized rules. This new codification is based on the inclusion of several bits, named tags, in conditions and actions, which evolve by means of GA. RTCS has been tested in robotic navigation. Results show the suitability of this approximation to the navigation problem and the coherence of tag values in rules classification.
In many cases, a real robot application requires the navigation in dynamic environments. The navigation problem involves two main tasks: to avoid obstacles and to reach a goal. Generally, this problem could be faced considering reactions and sequences of actions. For solving the navigation problem a complete controller, including actions and reactions, is needed. Machine learning techniques has been applied to learn these controllers. Classifier Systems (CS) have proven their ability of continuos learning in these domains. However, CS have some problems in reactive systems. In this paper, a modified CS is proposed to overcome these problems. Two special mechanisms are included in the developed CS to allow the learning of both reactions and sequences of actions. The learning process has been divided in two main tasks: first, the discrimination between a predefined set of rules and second, the discovery of new rules to obtain a successful operation in dynamic environments. Different experiments have been carried out using a mini-robot Khepera to find a generalised solution. The results show the ability of the system to continuous learning and adaptation to new situations.
One of the major problems related to Classifier Systems is the loss of rules. This loss is caused by the Genetic Algorithm being applied on the entire population of rules jointly. Obviously, the genetic operators discriminate rules by the strength value, such that evolution favors the generation of the stronger rules. When the learning process presents individual cases and allows the system to learn gradually from these cases, each learning interval with a set of individual cases can lead the strength to be distributed in favor of a given type of rules that would, in turn, be favored by the Genetic Algorithm. Basically, the idea is to divide rules into groups such that they are forced to remain in the system. This contribution is a method of learning that allows similar knowledge to be grouped. A field in which knowledge-based systems researchers have done a lot of work is concept classification and the relationships that are established between these concepts in the stage of knowledge conceptualization for later formalization. This job of classifying and searching relationships is performed in the proposed Classifier System by means of a mechanism, Tags, that allows the classification and the relationships to be discovered without the need for expert knowledge.
This paper is concerned with the general stimulus-response problem as addressed by a variety of simple learning c1assifier systems (CSs). We suggest a theoretical model from which the assessment of uncertainty emerges as primary concern. A number of representation schemes borrowing from fuzzy logic theory are reviewed, and sorne connections with a well-known neural architecture revisited. In pursuit of the uncertainty measuring goal, usage of explicit probability distributions in the action part of c1assifiers is advocated. Sorne ideas supporting the design of a hybrid system incorpo'rating bayesian learning on top of the CS basic algorithm are sketched.
Este trabalho tem como objetivos principais estudar, desenvolver e aplicar duas ferramentas computacionais bio-inspiradas em navegação autônoma de robôs. A primeira delas é representada pelos Sistemas Classificadores com Aprendizado, sendo que utilizou-se uma versão da proposta original, baseada em energia, e uma versão baseada em precisão. Adicionalmente, apresenta-se uma análise do processo de evolução das regras de inferência e da população final obtida. A segunda ferramenta trata de um modelo denominado sistema homeostático artificial evolutivo, composto por duas redes neurais artificiais recorrentes do tipo NSGasNets e um sistema endócrino artificial. O ajuste dos parâmetros do sistema é feito por meio de evolução, reduzindo-se a necessidade de codificação e parametrização a priori. São feitas análises de suas peculiaridades e de sua capacidade de adaptação. A motivação das duas propostas está no emprego conjunto de evolução e aprendizado, etapas consideradas fundamentais para a síntese de sistemas complexos adaptativos e modelagem computacional de processos cognitivos. Os experimentos visando validar as propostas envolvem simulação computacional em ambientes virtuais e implementações em um robô real do tipo Khepera II; The objectives of this work are to study...
In the family of Learning Classifier Systems, the classifier system XCS has
been successfully used for many applications. However, the standard XCS has no
memory mechanism and can only learn optimal policy in Markov environments,
where the optimal action is determined solely by the state of current sensory
input. In practice, most environments are partially observable environments on
agent's sensation, which are also known as non-Markov environments. Within
these environments, XCS either fails, or only develops a suboptimal policy,
since it has no memory. In this work, we develop a new classifier system based
on XCS to tackle this problem. It adds an internal message list to XCS as the
memory list to record input sensation history, and extends a small number of
classifiers with memory conditions. The classifier's memory condition, as a
foothold to disambiguate non-Markov states, is used to sense a specified
element in the memory list. Besides, a detection method is employed to
recognize non-Markov states in environments, to avoid these states controlling
over classifiers' memory conditions. Furthermore, four sets of different
complex maze environments have been tested by the proposed method. Experimental
results show that our system is one of the best techniques to solve partially
Learning Classifier Systems (LCS) are population-based reinforcement learners
that were originally designed to model various cognitive phenomena. This paper
presents an explicitly cognitive LCS by using spiking neural networks as
classifiers, providing each classifier with a measure of temporal dynamism. We
employ a constructivist model of growth of both neurons and synaptic
connections, which permits a Genetic Algorithm (GA) to automatically evolve
sufficiently-complex neural structures. The spiking classifiers are coupled
with a temporally-sensitive reinforcement learning algorithm, which allows the
system to perform temporal state decomposition by appropriately rewarding
"macro-actions," created by chaining together multiple atomic actions. The
combination of temporal reinforcement learning and neural information
processing is shown to outperform benchmark neural classifier systems, and
successfully solve a robotic navigation task.
A number of representation schemes have been presented for use within
learning classifier systems, ranging from binary encodings to neural networks.
This paper presents results from an investigation into using discrete and fuzzy
dynamical system representations within the XCSF learning classifier system. In
particular, asynchronous random Boolean networks are used to represent the
traditional condition-action production system rules in the discrete case and
asynchronous fuzzy logic networks in the continuous-valued case. It is shown
possible to use self-adaptive, open-ended evolution to design an ensemble of
such dynamical systems within XCSF to solve a number of well-known test
Knowledge representation is a key component to the success of all rule based
systems including learning classifier systems (LCSs). This component brings
insight into how to partition the problem space what in turn seeks prominent
role in generalization capacity of the system as a whole. Recently, knowledge
representation component has received great deal of attention within data
mining communities due to its impacts on rule based systems in terms of
efficiency and efficacy. The current work is an attempt to find a comprehensive
and yet elaborate view into the existing knowledge representation techniques in
LCS domain in general and XCS in specific. To achieve the objectives, knowledge
representation techniques are grouped into different categories based on the
classification approach in which they are incorporated. In each category, the
underlying rule representation schema and the format of classifier condition to
support the corresponding representation are presented. Furthermore, a precise
explanation on the way that each technique partitions the problem space along
with the extensive experimental results is provided. To have an elaborated view
on the functionality of each technique, a comparative analysis of existing
techniques on some conventional problems is provided. We expect this survey to
be of interest to the LCS researchers and practitioners since it provides a
guideline for choosing a proper knowledge representation technique for a given
problem and also opens up new streams of research on this topic.
Learning Classifier Systems (LCS) are population-based reinforcement learners
used in a wide variety of applications. This paper presents a LCS where each
traditional rule is represented by a spiking neural network, a type of network
with dynamic internal state. We employ a constructivist model of growth of both
neurons and dendrites that realise flexible learning by evolving structures of
sufficient complexity to solve a well-known problem involving continuous,
real-valued inputs. Additionally, we extend the system to enable temporal state
decomposition. By allowing our LCS to chain together sequences of heterogeneous
actions into macro-actions, it is shown to perform optimally in a problem where
traditional methods can fail to find a solution in a reasonable amount of time.
Our final system is tested on a simulated robotics platform.; Comment: 20 pages
We study the model of projective simulation (PS), a novel approach to
artificial intelligence based on stochastic processing of episodic memory which
was recently introduced [H.J. Briegel and G. De las Cuevas. Sci. Rep. 2, 400,
(2012)]. Here we provide a detailed analysis of the model and examine its
performance, including its achievable efficiency, its learning times and the
way both properties scale with the problems' dimension. In addition, we situate
the PS agent in different learning scenarios, and study its learning abilities.
A variety of new scenarios are being considered, thereby demonstrating the
model's flexibility. Furthermore, to put the PS scheme in context, we compare
its performance with those of Q-learning and learning classifier systems, two
popular models in the field of reinforcement learning. It is shown that PS is a
competitive artificial intelligence model of unique properties and strengths.; Comment: Accepted for publication in New Generation Computing. 23 pages, 23
Modern learning classifier systems typically exploit a niched genetic
algorithm to facilitate rule discovery. When used for reinforcement learning,
such rules represent generalisations over the state-action-reward space. Whilst
encouraging maximal generality, the niching can potentially hinder the
formation of generalisations in the state space which are symmetrical, or very
similar, over different actions. This paper introduces the use of rules which
contain multiple actions, maintaining accuracy and reward metrics for each
action. It is shown that problem symmetries can be exploited, improving
performance, whilst not degrading performance when symmetries are reduced.; Comment: 6 pages, 13 figures
Modern Learning Classifier Systems can be characterized by their use of rule
accuracy as the utility metric for the search algorithm(s) discovering useful
rules. Such searching typically takes place within the restricted space of
co-active rules for efficiency. This paper gives an historical overview of the
evolution of such systems up to XCS, and then some of the subsequent
developments of XCS to different types of learning.; Comment: 37 pages, 9 figures