Transcript NN and ML chap2

Neural Networks
and Machine Learning Applications
CSC 563
Prof. Mohamed Batouche
Computer Science Department
CCIS – King Saud University
Riyadh, Saudi Arabia
[email protected]
Complex Systems
Emergent Behaviors and Patterns
from Local Interactions
What is a complex system?

A complex system displays some or all of the
following characteristics:

Agent-based


Heterogeneous


Changes are often the result of feedback from the environment
Organization


Characteristics change over time, usually in a nonlinear way; adaptation
Feedback


The agents differ in important characteristics
Dynamic


Basic building blocks are the characteristics and activities of individual agents
Agents are organized into groups or hierarchies
Emergence

Macro-level behaviors that emerge from agent actions and interactions
3
Complex systems
The fundamental characteristic of a complex system is that it
exhibits emergent properties: Local interaction rules between
simple agents give rise to complex pattern and global behavior
4
Complex vs. Simple Systems
Have many parts
• Parts are interdependent in behaviour
• Difficult to understand because:
– behaviour of whole understood from behaviour of
parts
– behaviour of parts depends on behaviour of whole
5
Complex Systems
perspectives
Complex Systems as a Science
to Understand Nature
Complex Systems as a New
Form of Engineering
6
Complex Systems
A new form of Engineering

Engineering which faces complex problems using simple
dynamic systems.

« The whole is too much greater than the sum of the
parts »
7
Examples of Complex Systems









Brain
Government
Family
Wold Ecosystem
Local Ecosystem
(desert, ocean,
rainforest)
Weather
University
Ant colony
…
8
Anything to be Learnt from
Ant Colonies?


Fairly simple units generate complicated
global behaviour.
An ant colony expresses a complex
collective behavior providing intelligent
solutions to problems such as:




carrying large items
forming bridges
finding the shortest routes from the
nest to a food source, prioritizing food
sources based on their distance and ease
of access.
“If we knew how an ant colony works,
we might understand more about how all
such systems work, from brains to
ecosystems.”
(Gordon, 1999)
9
Shortest path discovery
10
Adaptation to Environmental
Changes
11
Interactions among Social
Insects
• Direct Interactions
• Food or liquid exchange
• Visual or tactile contact
• Indirect Interactions:
Stigmergy
• Pheromones
• Individual behaviour modifies
the environment (e.g., by
putting up signs = stigma),
which in turn modifies the
behaviour of other
individuals.
12
Demo NetLogo

Massively Parallel MicroWolds
13
Universal properties shared by
complex systems


Emergence: The appearance of
macroscopic patterns, properties,
or behaviors that are not simply
the “sum” of the microscopic
properties or behaviors of the
components
Self-organization: In biological
systems, the emergent order
often has some adaptive purpose
– e.g., efficient operation of ant colony
14
Emergence: Attempt of a
Definition
• From the book:
Steven Johnson, Emergence—The Connected Lives of
Ants, Brains, Cities, and Software
– Emergence is what happens when an interconnected system of
relatively simple elements self-organizes to form more
intelligent, more adaptive higher-level behaviour.
– It’s a bottom-up model; rather than being engineered by a
general or a master planner, emergence begins at the ground
level.
– Systems that at first glance seem vastly different […] all turn out
to follow the rules of emergence.
15
Emergence in complex
systems
• How do neurons respond to each other in a way that
produces thoughts (minds)?
• How do cells respond to each other in a way that
produces the distinct tissues of a growing embryo?
• How do species interact to produce predictable
changes, over time, in ecological communities?
• ...
16
Emergence in complex
systems

Boids of Craig Reynolds
17
Boids of Reynolds


Bird Flocking
“Boids” model was proposed by
Reynolds


Boids = Bird-oids (bird like)
Only three simple rules
18
Boids of Reynolds

simple rules give rise to complex
behavior
19
Collision Avoidance

Rule 1: Avoid Collision with neighboring
birds
20
Velocity Matching: Alignment

Rule 2: Match the velocity of
neighboring birds
21
Flock Centering: Cohesion

Rule 3: Stay near neighboring birds
22
Characteristics

Simple rules for each individual

No central control


Decentralized and hence robust
Emergent

Performs complex functions
23
Boids of Reynolds

Boids of Craig Reynolds
24
Emergence in complex
systems

Boids of Craig Reynolds
25
Emergence in complex
systems

Boids of Craig Reynolds
26
Demo NetLogo

Bird Flocking
27
Why Are Complex Systems
Important for CS?
• Fundamental to theory &
implementation of massively
parallel, distributed computation
systems
• How can millions of independent
computational (or robotic) agents
cooperate to process information
& achieve goals, in a way that is:
–
–
–
–
efficient
self-optimizing
adaptive
robust in the face of damage or
attack
28
Some of Natural Systems








adaptive path minimization by ants
fish schooling and bird flocking
evolution by natural selection
information processing in the brain
wasp and termite nest building
pattern formation in animal coats
game theory and the evolution of cooperation
computation at the edge of chaos
29
Some of Artificial Complex
Systems








artificial neural networks
simulated annealing
cellular automata
ant colony optimization
artificial immune systems
particle swarm optimization
genetic algorithms
other evolutionary computation systems
30
Reverse Emergence
• simple rules give complex behaviour
–but which simple rules give the desired complex
behaviour?
Reverse
emergence
31
Reverse Emergence



Searching simple rules by hand (trials).
Taking inspiration from nature (bees, ants…)
Optimization and Learning (GA, RL …)
Reverse
emergence
32
Reverse Emergence
Molecular NanoTechnology
• assembled artefact is emergent property
– of actions of vast number of nanites
• design requires “reverse emergence”
– from desired emergent artefact
– to behaviour of naniteassemblers
Reverse
emergence
• extreme example of “non-classical refinement”
• simple rules give complex behaviour
– but whichsimple rules give the
desiredcomplex behaviour?
Adapted from Susan Stepney Slides (April 2006) University of York – Journeys in non-classical computation
33
Artificial Complex Systems
Genetic Algorithms
Genetic programming
Particle Swarm optimization
Genetic Algorithms
Stochastic Search: Genetic Algorithms



Formally introduced in the US in the 70s by John
Holland.
GAs emulate ideas from genetics and natural selection
and can search potentially large spaces.
Before we can apply Genetic Algorithm to a problem,
we need to answer:
-
How is an individual represented?
What is the fitness function?
How are individuals selected?
How do individuals reproduce?
36
Stochastic Search: Genetic Algorithms
Representation of states (solutions)
•
Each state or individual is represented as a string over
a finite alphabet. It is also called chromosome which
Contains genes.
genes
Solution: 607
Encoding
1001011111
Chromosome:
Binary String
37
Stochastic Search: Genetic Algorithms
Fitness Function
•
Each state is rated by the evaluation function called fitness function.
Fitness function should return higher values for better states:
Fitness(X) should be greater than Fitness(Y) !!
[Fitness(x) = 1/Cost(x)]
Cost
States
X
Y
38
Stochastic Search: Genetic Algorithms
Selection
How are individuals selected ?
Roulette Wheel Selection
1
1
0
2
3
2
4
3
1
5
6
3
7
5
Rnd[0..18] = 7
Rnd[0..18] = 12
Chromosome4
Chromosome6
1
8
2
18
39
Stochastic Search: Genetic Algorithms
Cross-Over and Mutation
How do individuals reproduce ?
40
Stochastic Search: Genetic Algorithms
Crossover - Recombination
1011011111
1010000000
Parent1
Offspring1
1001011111
Parent2
Offspring2 1010000000
Crossover
single point random
With some high probability (crossover
rate) apply crossover to the parents.
(typical values are 0.8 to 0.95)
41
Stochastic Search: Genetic Algorithms
Mutation
Offspring1
1011011111
Offspring2 1010000000
Original offspring
Offspring1
mutate
1011001111
Offspring2 1000000000
Mutated offspring
With some small probability (the mutation rate) flip
each bit in the offspring (typical values between 0.1
and 0.001)
42
Genetic Algorithms

GA is an iterative process and can be described as
follows:

Iterative process

Start with an initial population of “solutions” (think:
chromosomes)

Evaluate fitness of solutions

Allow for evolution of new (and potentially better) solution
populations


E.g., via “crossover,” “mutation”
Stop when “optimality” criteria are satisfied
43
Genetic Algorithms
Algorithm:
1.
Initialize population with p Individuals at random
2.
For each Individual h compute its fitness
3.
While max fitness < threshold do
Create a new generation Ps
4.
Return the Individual with highest fitness
44
Genetic Algorithms
Create a new generation Ps:
1.
2.
3.
4.
5.
Select (1-r)p members of P and add them to Ps. The probability of
selecting a member is as follows:
P(hi) = Fitness (hi) / Σj Fitness (hj)
Crossover: select rp/2 pairs of hypotheses from P according to
P(hi).
For each pair (h1,h2) produce two offspring by applying the
Crossover operator. Add all offspring to Ps.
Mutate: Choose mp members of Ps with uniform probability. Invert
one bit in the representation randomly.
Update P with Ps
Evaluate: for each h compute its fitness.
45
Genetic Algorithms
Cost
States
46
Genetic Algorithms
Mutation
Cross-Over
47
Genetic Algorithms
48
Genetic Algorithms
49
Genetic Algorithms
50
Genetic Algorithms
51
Genetic Algorithms
52
Genetic Algorithms
53
Genetic Algorithms
54
Genetic Algorithms
55
Genetic Algorithms
56
Genetic Algorithms
57
Genetic Algorithms
58
Genetic Algorithms
59
Genetic Algorithms
60
Genetic Algorithms
61
Genetic Algorithms
62
Genetic Algorithms
63
Genetic Algorithms
64
Genetic Programming
Genetic Programming
Genetic programming (GP)
Programming of Computers
by Means of Simulated
Evolution
How to Program a Computer
Without Explicitly Telling It
What to Do?
Genetic Programming is
Genetic Algorithms where
solutions are programs …
66
Genetic programming



When the chromosome encodes an entire
program or function itself this is called
genetic programming (GP)
In order to make this work, encoding is often
done in the form of a tree representation
Crossover entails swapping subtrees between
parents
67
Genetic programming
It is possible to evolve whole programs like this
but only small ones. Large programs with complex
functions present big problems
68
Genetic programming
Inter-twined Spirals: Classification Problem
Red Spiral
Blue Spiral
69
Genetic programming
Inter-twined Spirals: Classification Problem
70
Ant Colony Optimization
Shortest path discovery
Ants get to find the shortest path after few minutes …
72
Ant Colony Optimization
Each artificial ant is a probabilistic mechanism that constructs a
solution to the problem, using:
• Artificial pheromone deposition
• Heuristic information: pheromone trails, already
visited cities memory …
73
TSP Solved using ACO
74
Particle Swarm Optimization
Particle Swarm Optimization

Particle Swarm Optimization (PSO) mimics the collective
intelligent behavior of “ unintelligent ” creatures.

It was developed in 1995 by James Kennedy and Russell
Eberhart


Individuals interact with one another while learning from
their own experience, and gradually move towards the
goal.
It is easily implemented and has proven both very
effective and quick when applied to a diverse set of
optimization problems.
76


Bird flocking is one of the best example of
PSO in nature.
One motive of the development of PSO
was to model human social behavior.
77
Algorithm of PSO



Each particle (or agent) evaluates the function to
maximize at each point it visits in spaces.
Each agent remembers the best value of the function
found so far by it (pbest) and its co-ordinates.
Secondly, each agent know the globally best position
that one member of the flock had found, and its
value (gbest).
78
Algorithm of PSO

Using the co-ordinates of pbest and gbest,
each agent calculates its new velocity as:
vi = vi + c1 x rand() x (pbestxi – presentxi)
+ c2 x rand() x (gbestx – presentxi)
where 0 < rand() <1
presentxi = presentxi + (vi x Δt)
79
Algorithm of PSO
80
81
82
83
Conclusions

We can learn from nature and take advantage of the problems
that she has already solved.

Many simple individuals interacting with each other can make a
global behavior emerge.

Techniques based on natural collective behavior (Swarm
Intelligence) are interesting as they are cheap, robust, and
simple.

They have lots of different applications.

Swarm intelligence is an active field in Artificial Intelligence,
many studies are going on.
84