## Theme: Emergent Behavior

• Behavior of a complex composition of simple behaviors

• Examples so far in this course:

• State-Space search: simple individual search steps combine to reach a global goal

• Machine Learning: combination of simple features are interpreted to accurately make a complex decision

• Neural Nets: combination of simple perceptrons makes sophisticated decisions

• Genetic Algorithms: Interaction of simple genomes produces complex answer

• Arguably the only road to AI

## Ensembles

• An ensemble is a collection of like things

• We are interested in emergent behavior of ensembles

• Inspiration is often drawn from biology

• Beehives

• Bird flocks, fish schools

• Ant colonies

## Ant Colony

• You want a short path through a maze

• Put a bunch of ants at the entrance and food at the exit

• Watch the ants wander through the space

• At first, they seem to be moving fairly randomly

• Over time, they form into lines. Why?

• When an ant finds food, it starts back down the line the other way

• The ants' path will become optimized for retrieving food

## Pheromones

• Ants deposit pheromones (smelly stuff) as they move

• Ants follow "pheromone trails" somewhat

• Pheromones decay slowly over time

• More pheromones are released while an ant is leaving a food source

• Net effect: frequently traversed stretches of trail are reinforced

## Ant Colony Optimization

• You want a short path through a maze

• Quite literal: move "ants" across a map, depositing pheromone trails and decaying pheromones

• After some running time, grab the strongest pheromone path

• http://github.com/pdx-cs-ai/sim-ant

## Ensembles of Learners

• Idea: Given an ensemble of weak machine learners, use some kind of weighted voting to make a stronger overall learner

• This only makes sense if there is some independence between the learners: method, source data, results

• A boosting algorithm is used to combine the learners

• An effective boosting algorithm

• Adjusts both weights of individual learners and weights of errors on individual instances passed to the learners

• Outline of training pseudocode (textbook p. 751)

w[x] ← 1 for all instances
create z[L]
for each learner L
E ← 0
for each incorrectly classified L(x)
E += w[x]
for each correctly classified L(x)
w[x] *= E / (1 - E)
normalize w
z[L] ← log (1 - E) / E
return z

• To classify an instance x, choose the class c that maximizes

sum[L in learners] (z[L] (L(x) = c))