Learning Classifier Systems
Download
Report
Transcript Learning Classifier Systems
Learning Classifier Systems
Dominic Cockman, Jesper Madsen, Qiuzhen Zhu
1
Learning Classifier Systems
History and Motivations
2
History and Motivations for LCS
Robust machine learning techniques that can be applied to classification
tasks, large-scale data mining problems or robot control and cognitive system
applications, among others
Origins in John Holland’s work on cognitive systems, based on his research
into adaption in natural and artificial systems
LCS was introduced as a cognitive systems framework, based on psychology
principles and ideas from Darwinian evolution
3
History and Motivations for LCS
A computer program is said to learn from experience with respect to some
class of tasks and performance measure, if its performance at tasks in this
class, as measured by our chosen performance measure, improves with
experience
The required components of a successful LCS are:
A set of classifiers
Some evolution mechanism, either for the classifier or the population, designed to
improve rule structures over time
Some evolution mechanism, either for the classifier or the population, which
identifies the quality of the rule or population of rules
4
History and Motivations for LCS
LCS follows a ‘mixture of experts’ approach
The object of a learning system, natural or artificial, is the expansion of its
knowledge in the face of uncertainty
Ideal learning systems confront some subset of:
A perpetually stream of data from the environment
Continual requirements for action
Implicitly defined goals and sparse payoff - requiring long sequences of action.
5
History and Motivations for LCS
An LCS is "adaptive" - ability to choose the best action improves with
experience
Evolution takes place in the background
Effect of classifier evolution is to modify their conditions
Classifier systems are intended as a framework that uses genetic algorithms
to study learning in condition/ action, rule-based systems
6
History and Motivations for LCS
Classifier systems address three basic problems in machine learning:
Parallelism and coordination
Credit assignment
Rule discovery
LCS address all these issues
7
History and Motivations for LCS
Recent years have seen much effort put into LCS research and development
Advances have been made in many areas:
Different representations of conditions beyond the traditional binary/ ternary rules
Developments in other problem classes
Smarter exploration mechanisms
Theoretical advancements
8
Learning Classifier Systems
Characteritics & Implementations
9
Minimal Classifier System
10
Source: Fig. 3, Learning Classifier Systems: A Complete Introduction, Review, and Roadmap
Michigan and Pittsburg
Two main styles of LCSs
Primary differences:
Population characterization
Learning style
11
LCS Variations
Strength-based (Zeroth-level Classifier System)
Accuracy-based (eXtended Classifier System)
Fitness based on the expected reward of the classifier
Fitness based on the accuracy of the classifier
Discovery (Coverage and GA)
12
Learning Classifier Systems
Applications
13
classification tasks
graph coloring：
it is a way of coloring the vertices of a graph such that no two adjacent vertices share the
same color; this is called a vertex coloring，using the least colors.
A crossover derivative was developed to accommodate the graph coloring specifications.
Also, a method for verifying and validating the new offspring generated via genetic action, conforming to the
graph coloring rules and regulations was considered.
LCS:the condition of the classifier is the graph itself(connections between vertices), and the action component is
a valid coloring assignment for different vertices
14
data mining
EpiCS
LCS：output for:risk estimate,prediction of class membership
knowledge discovery in epidemiologic surveillance
input:population situation
15
robot control
mobile robot control
LCS:input:sensory sensing the environment
output:desired action
16
MODELLING
prediction on the transaction of the stock market
LCS:input:stock market performance
output:people's behaviours
120
100
80
60
40
20
0
1
2
3
4
17
other usage
military domain
phsychology modelling
traffic control
chemical reaction control
cognitive system
more...
18
References
Dr. J. Bacardit, Dr. N. Krasnogor. 2013. Introduction to Learning Classifier
Systems. [ONLINE] Available
at:http://www.exa.unicen.edu.ar/escuelapav/cursos/bio/l7.pdf. [Accessed 22
August 14]
J Bacardit, E Bernado-Mansilla & M V Butz. 2013. Learning Classifier Systems:
Looking Back and Glimpsing Ahead. [ONLINE] Available
at: http://www.cs.nott.ac.uk/~jqb/publications/LCS-Looking-Glimsing.pdf.
[Accessed 23 August 14]
J Holland, L Booker, et al.. [UNKNOWN]. What is a Learning Classifier System?.
[ONLINE] Available
at:http://www.cs.unm.edu/~forrest/publications/LearningClassifierSystems00.pdf. [Accessed 23 August 14]
L Booker, D Goldberh & J Holland. 1989. Classifier Systems and Genetic
Algorithms. [ONLINE] Available
at:http://deepblue.lib.umich.edu/bitstream/handle/2027.42/27777/0000171.pdf.
[Accessed 23 August 14]
Ezziane, Z, 1998. Learning Classifier System for Graph Coloring. Expert Systems,
Volume 15, Issue 4, 240-246.
Holmes, J, Durbin, D & Winston, F, 2000. The Learning Classifier System: An
Evolutionary Computation Approach to Knowledge Discovery in Epidemiologic
Surveillance. Artificial Intelligence in Medicine, Volume 19, Issue 1, 53-74.
19
References
Hurst, J & Bull, L, 2000. A Self-adaptive Neural Learning Classifier System
with Constructivism for Mobile Robot Control. Lecture Notes in Computer
Science, Volume 3242, 942-951.
Li, P, Stolzmann, W & Wilson, S, 2000. Learning Classifier Systems: From
Foundations to Applications (Lecture Notes in Computer Science / Lecture
Notes in Artificial Intelligence). 2000 Edition. Springer.
Urbanowicz, R & Moore, J, 2009. Learning Classifier Systems: A Complete
Introduction, Review, and Roadmap. Journal of Artificial Evolution and
Applications, Volume 2009, Article ID 736398.
20