Classifier Systems

Anil Shankar

Dept. of Computer Science

University of Nevada, Reno
 Overview
• Introduction and problem overview
• Architecture
• Component details
• Track a specific example
• Summary

Anil Shankar Classifier Systems 2

 Introduction
• Learning
– “A computer program is said to learn from
experience E with respect to some class of
tasks T and performance measure P, if its
performance at tasks in T, as measured by P,
improves with experience E”
– Machine Learning, Tom Mitchell

Anil Shankar Classifier Systems 3

 Problem
Multiplexer Example
Rule Address Signal
# # # 0 0 0:0 0 0

# # 0 # 0 1:0 1 0

# 0 # # 1 0:0 2 0

0 # # # 1 1:0 3 0

# # # 1 0 0:1 0 1

# # 1 # 0 1:1 1 1

# 1 # # 1 0:1 2 1

1 # # # 1 1:1 3 1

Perfect Rule Set

Anil Shankar Classifier Systems 4

Classifier System (C.S)
• Learn simple string
rules in an arbitrary
environment
• A classifier is a simple
string rule
• Components
– Rule and Message
System
– Apportionment of
credit system
– Genetic Algorithm

Anil Shankar Classifier Systems 5

Rule and Message System
• Production system
• Fixed size representation
for rules
• Parallel activation
• Rating of a rule by an
information-based
economy
• <message>::= { 0, 1} l
• <classifier>::= <condition>:<message>
• <condition>::={0, 1, #}l

Anil Shankar Classifier Systems 6

Which classifier to choose?
• Bucket Brigade Algorithm
– For ranking or rating individual
classifiers
– Classifiers buy and sell the
right to trade information
(information-based economy)
– Auction house and clearing
house
– If a classifier matches a
message, it participates in an
auction.
– The bid (B) is proportional to
its strength (S)
– Once activated the winner
pays its bid to other classifiers
which also matched the
message

Anil Shankar Classifier Systems 7

Which classifier to choose?(contd…)
• Notation
– S = Strength
– P = Payment
– T = Tax
– R = Reward
– Cbid = Bid Coefficient
• The ith classifier strength (at time
step t)
Si(t+1) = Si(t) – Pi(t) – Ti(t) +
Ri(t)
• Bid
Bi = Cbid * Si
• Tax
Taxi = Ctax * Si
• Effective Bid
EBidi = Bi + N (σbid)
• In terms of strength
S(t+1) = S(t) – Cbid*S(t) –
Ctax*S(t) + R(t)

Anil Shankar Classifier Systems 8

 Generating better rules
• Bucket brigade algorithm evaluates rules and decides
among competing alternatives.
• Use a Genetic Algorithm (GA) to generate new rules
• A classifier’s strength (S) is used as its fitness
• Similar to the simple genetic algorithm
• Entire population is not replaced at the next generation
(Generation gap )
• GA period (epoch)
– Number of time steps between GA calls
– Time step = rule-message cycle
• Crowding to maintain diversity
• Mutation over a ternary alphabet {1, 0, # }

Anil Shankar Classifier Systems 9

 Generating better rules
• Selection is performed using roulette-
wheel selection
• The GA is run according every GA Period
or when conditioned on particular events
(lack of match or poor performance)

Anil Shankar Classifier Systems 10

 C.S in action (1)
Index Classifier
T= 0
1 01## : 0000
Index S Msg M B
2 00#0 : 1100 1 200 E 20
3 11## : 1000 2 200
3 200
4 ##00 : 0001
4 200
Environment
(E) 0111 E 0 0111
Strength (S)
CBid = 0.1
01##
Messages (Msg)
CTax = 0.0
Match (M) 0000
Bid (B)

Anil Shankar Classifier Systems 11

 C.S in action (2)
Index Classifier T= 1
1 01## : 0000 Index S Msg M B

1 180 0000
2 00#0 : 1100
2 200 1 20
3 11## : 1000
3 200
4 ##00 : 0001 4 200 1 20
Environment
(E) 0111 E 20
00#0 ##00
Strength (S)
Messages (Msg) CBid = 0.1 1100 0001
Match (M) CTax = 0.0
Bid (B)

Anil Shankar Classifier Systems 12

 C.S in action (3)
Index Classifier T= 2
1 01## : 0000 Index S Msg M B

1 220
2 00#0 : 1100
2 180 1100
3 11## : 1000
3 200 2 20
4 ##00 : 0001 4 180 0001 2 18
Environment
(E) 0111 E 20

Strength (S)
Messages (Msg) CBid = 0.1
Match (M) CTax = 0.0
Bid (B)

Anil Shankar Classifier Systems 13

 C.S in action (4)
Index Classifier T= 3
1 01## : 0000 Index S Msg M B

1 220
2 00#0 : 1100
2 218
3 11## : 1000
3 180 1000
4 ##00 : 0001 4 162 0001 3 16
Environment
(E) 0111 E 20

Strength (S)
Messages (Msg) CBid = 0.1
Match (M) CTax = 0.0
Bid (B)

Anil Shankar Classifier Systems 14

 C.S in action (5)
Index Classifier T= 4
1 01## : 0000 Index S Msg M B

1 220
2 00#0 : 1100
2 208
3 11## : 1000
3 196
4 ##00 : 0001 4 156 0001
Environment
(E) 0111 E 20

Strength (S)
Messages (Msg) CBid = 0.1
Match (M) CTax = 0.0
Bid (B)

Anil Shankar Classifier Systems 15

 C.S in action (6)
Index Classifier T= 5
1 01## : 0000 Index S Payoff

1 220
2 00#0 : 1100
2 208
3 11## : 1000
3 196
4 ##00 : 0001 4 206 50
Environment
(E) 0111 E 20

Strength (S)
CBid = 0.1
CTax = 0.0

Anil Shankar Classifier Systems 16

 Are these rule-sets the same?
Rule Address Signal Rule
# # # 0 0 0:0 0 0
# # # 0 0 0:0
# # 0 # 0 1:0 1 0
# # 0 # 0 1:0
# 0 # # 1 0:0 2 0
0 # # # 1 1:0 3 0 # 0 # # 1 0:0
# # # 1 0 0:1 0 1 0 # # # 1 1:0
# # 1 # 0 1:1 1 1 # # # # # # :1
# 1 # # 1 0:1 2 1
1 # # # 1 1:1 3 1

Anil Shankar Classifier Systems 17

 Multiplexer Example
• Default Hierarchy 0
###000
– General rules cover ##0#01 0
general conditions and
#0##10 0
specific rules cover
0###11 0
exceptions
###### 1
– Parsimony
• Fewer rules
– Enlargement of the
solution set
• While the problem
space remains the
same

Anil Shankar Classifier Systems 18

 Summary
• A classifier is a simple string
rule
• Classifier System
– rule-message system,
– apportionment of credit
mechanism
– GA

• Advantages of CS
– rules are simple
– use fixed length
representation
– parallel activation
– operate in an information-
based economy

Anil Shankar Classifier Systems 19

 Thank You
Questions ?

Anil Shankar Classifier Systems 20