Transcript Intro_NN

Artificial
Intelligence and
Machine Learning
in Robotics
1
We want to design some truly
intelligent robot
2
Or like this??
• musee mechanique
• http://museemecanique.citysearch.com/
3
What is AI?
Discipline that systematizes and automates
intellectual tasks to create machines that:
Act like humans
Act rationally
Think like humans
Think rationally
More formal and mathematical
Some Important Achievements of AI
 Logic reasoning (data bases)
 Applied in reasoning interactive robot helper
 Search and game playing
 Applied in robot motion planning
 Knowledge-based systems
 Applied in robots that use knowledge like internet
robots




Bayesian networks (diagnosis)
Machine learning and data mining
Planning and military logistics
Autonomous robots
MAIN BRANCHES OF AI
APPLICABLE TO ROBOTICS
Artificial
Intelligence
Neural
Nets
Fuzzy
Logic
Genetic
Algorithms
ARTIFICIAL INTELLIGENCE
Machine Learning
Decision Theoretic Techniques
Symbolic Concept Acquisition
Constructive Induction
Genetic learning
Un-supervised leaning
Treatment of uncertainty
Efficient constraint
satisfaction
Inductive Learning by
Nearest-Neighbor Classification
• One simple approach to inductive learning is to save each
training example as a point in feature space
• Classify a new example by giving it the same classification
(+ or -) as its nearest neighbor in Feature Space.
– A variation involves computing a weighted sum of class
of a set of neighbors where the weights correspond to
distances
– Another variation uses the center of class
• The problem with this approach is that it doesn't
necessarily generalize well if the examples are not well
"clustered."
example
•
Text Mining:
Information Retrieval and Filtering
20 USENET Newsgroups
–
comp.graphics
–
comp.os.ms-windows.misc rec.autos
talk.politics.guns
sci.crypt
–
comp.sys.ibm.pc.hardware rec.motorcycles
talk.politics.mideast
sci.electronics
–
comp.sys.mac.hardware
talk.politics.misc
sci.med
–
comp.windows.x
misc.forsale soc.religion.christian
rec.sports.baseball
rec.sports.hockey
–
•
sci.space
talk.religion.misc
alt.atheism
Problem Definition [Joachims, 1996]
– Given: 1000 training documents (posts) from each group
– Return: classifier for new documents that identifies the group it belongs to
•
Example: Recent Article from comp.graphics.algorithms
Hi all
I'm writing an adaptive marching cube algorithm, which must deal with cracks. I got the vertices of the cracks in a list (one list
per crack).
Does there exist an algorithm to triangulate a concave polygon ? Or how can I bisect the polygon so, that I get a set of connected
convex polygons.
The cases of occuring polygons are these:
...
•
Performance of Newsweeder (Naïve Bayes): 89% Accuracy
example
Rule and Decision Tree Learning
•
Example: Rule Acquisition from Historical Data
•
Data
– Customer 103 (visit = 1): Age 23, Previous-Purchase: no, Marital-Status: single, Children:
none, Annual-Income: 20000, Purchase-Interests: unknown, Store-Credit-Card: no,
Homeowner: unknown
– Customer 103 (visit = 2): Age 23, Previous-Purchase: no, Marital-Status: married,
Children: none, Annual-Income: 20000: Purchase-Interests: car, Store-Credit-Card: yes,
Homeowner: no
– Customer 103 (visit = n): Age 24, Previous-Purchase: yes, Marital-Status: married,
Children: yes, Annual-Income: 75000, Purchase-Interests: television, Store-Credit-Card:
yes, Homeowner: no, Computer-Sales-Target: YES
•
Learned Rule
– IF customer has made a previous purchase, AND customer has an annual income over
$25000, AND customer is interested in buying home electronics
THEN probability of computer sale is 0.5
– Training set: 26/41 = 0.634, test set: 12/20 = 0.600
– Typical application: target marketing
example
INDUCTIVE LEARNING
Example of Risk Classification
NO.
RISK
1.
2.
3.
4.
5.
6.
High
High
Mod.
High
Low
Low
CREDIT DEBT COLLATERAL INCOME
Bad
Unk.
Unk.
Unk.
Unk.
Unk.
Decision variable
(output) is RISK
High
High
Low
Low
Low
Low
none
none
none
none
none
none
$0-$15 K
$15-$35 K
$15-$35 K
$0-$15 K
>$35 K
>$35 K
INDUCTIVE LEARNING
Example of Risk Classification..
Income
Debt
Credit History
Collateral
example
The Block’s world
Hand-Coded Knowledge vs. Machine
Learning
•How much work would it be to enter knowledge by hand?
•Do we even know what to enter?
1952-62 Samuel’s checkers player learned its evaluation
function
1975
Winston’s system learned structural descriptions
from examples and near misses
1984
Probably Approximately Correct learning offers a
theoretical foundation
mid 80’s The rise of neural networks
example
Concept Acquisition
Example of “Arch” concept
two bricks support
a
brick
two bricks support
a Pyramid
Concept Acquisition (cont)
Polygon
Bricks and pyramids
are instances of
Polygon
Brick
Pyramid
ARCH => Two bricks
support
a polygon
Some Fundamental Issues
for Most AI Problems
• Learning
new knowledge is acquired
– inductive inference
– neural networks
– artificial life
– evolutionary approaches
What we’ll be doing
• Uncertain knowledge and reasoning
– Probability, Bayes rule
• Machine learning
– Decision trees, computationally learning
theory, reinforcement learning
ini   W j ,i a j  Wi  a j
j
A Generalized Model of Learning
Correct outputs
Training
System
Output
Input
Learning
Element
Knowledge
Base
Performance
Element
Feedback
Element
Training system is used to create learning pairs
(input, output) to train our robot
Starts with some knowledge. The performance element participates in performance. The feedback element
provides a comparison of actual output vs correct output which becomes input to the learning element. It
analyzes the differences and updates the knowledge base.
Correct outputs
Training
System
Output
Input
Learning
Element
Knowledge
Base
Performance
Element
Feedback
Element
Starts with some knowledge.
The performance element participates in performance.
The feedback element provides a comparison of actual output vs
correct output which becomes input to the learning element. It
analyzes the differences and updates the knowledge base.
Neural
Networks –
a very easy
introduction
Standard computers
• Referred to as Von Neumann machines
• Follows explicit instructions
• Sample program
if (time < noon)
print “Good morning”
else
print “Good afternoon”
No learning
No autonomous
intelligence
25
Neural networks
•
•
•
•
Modeled off the human brain
Does not follow explicit instructions
Is trained instead of programmed
Key papers
– McCulloch, W. and Pitts, W. (1943). A logical
calculus of the ideas immanent in nervous activity.
Bulletin of Mathematical Biophysics, 7:115 - 133.
– Rosenblatt, Frank. (1958) The Perceptron: A
Probabilistic Model for Information Storage and
Organization in the Brain. Psychological Review,
65:386-408.
26
Sources for lecture
• comp.ai.neural-networks FAQ
• Gurney, Kevin. An Introduction to
Neural Networks, 1996.
27
Neuron drawing
28
Neuron behavior
• Signals travel between neurons through
electrical pulses
• Within neurons, communication is
through chemical neurotransmitters
• If the inputs to a neuron are greater
than its threshold, the neuron fires,
sending an electrical pulse to other
neurons This is a simplification.
29
Perceptron (artificial neuron)
inputs
weights
threshold
xa
output
+
>10?
xb
30
Example of
Training a very
simple Neural
Network
31
Training
•
•
•
•
Inputs and outputs are 0 (no) or 1 (yes)
Initially, weights are random
Provide training input
Compare output of neural network to
desired output
– If same, reinforce patterns
– If different, adjust weights
32
Example
If both inputs are 1, output should be 1.
inputs
weights
threshold
x2
output
+
>10?
x3
33
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
threshold
x2
output
+
1
>10?
x3
34
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
x2
threshold
2
output
+
1
x3
>10?
3
35
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
x2
threshold
2
+
1
x3
5
output
>10?
3
36
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
x2
threshold
2
+
1
x3
5
output
0
>10?
3
37
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
x2
threshold
2
+
1
x3
5
output
0
>10?
3
38
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
x2
threshold
2
+
1
x3
5
output
0
>10?
3
39
Example (1,1)
If both inputs are 1, output should be 1.
inputs
1
weights
threshold
x2
output
+
1
>10?
x3
Repeat for all inputs until weights stop changing.
40
Function-Learning Formulation
 Goal function f
 Training set: (x(i), f(x(i))), i = 1,…,n
 Inductive inference: find a function h that
fits the points well
f(x)
x
 Same Keep-It-Simple bias
Natural versus
Artificial
Neural
Networks
Afferent Neurons, Efferent Neurons and
Interneurons
Neural Connections in Central and Peripheral
Nervous Systems
How the activation works?
• Stimulus from
various
sources
• Threshold
• Cell
depolarization
and return of
rest potential
Weak Stimulus
Strong Stimulus
Step response of a model is different than in
real network
Mathematical
Models of
Neurons
Perceptrons
and Artificial
Neural
Networks
Perceptron
(The goal function f is a boolean one)
+
+
x1
+
+
-
-
-
+
xi wi
x2
S
xn
y = g(Si=1,…,n wi xi)
g
y
w 1 x1 + w 2 x2 = 0
x1
-
Perceptron
(The goal function f is a boolean one)
+
+
x0
xi wi
?
-
S
xn
y = g(Si=1,…,n wi xi)
g
y
+
+
-
+
-
Unit (Neuron)
x1
xi wi
S
xn
y = g(Si=1,…,n wi xi)
g(u) = 1/[1 + exp(-au)]
g
y
Neural Network
Network of interconnected neurons
x1
xi w
x1
i
xi w
i
xn
S
g
y
S
g
y
xn
Acyclic (feed-forward) vs. recurrent networks
Two-Layer Feed-Forward
Neural Network
w1j
Inputs
w2k
Hidden
layer
Output
layer
Comments and Issues on ANN
 How to choose the size and structure
of networks?
• If network is too large, risk of overfitting (data caching)
• If network is too small, representation
may not be rich enough
 Role of representation: e.g., learn the
concept of an odd number
 Incremental learning
HISTORY OF
RESEARCH ON
ARTIFICIAL
NEURAL NETS
65
Perceptrons
Early neural nets
Symbolic vs. Subsymbolic AI
Subsymbolic AI:
• Model intelligence at a level
similar to the neuron.
• Let such things as knowledge
and planning emerge.
Symbolic AI:
Model such things as
knowledge and planning in
data structures that make sense
to the programmers that build
them.
(blueberry (isa fruit)
(shape round)
(color purple)
(size .4 inch))
The Origins of Subsymbolic AI
1943 McCulloch and Pitts A Logical Calculus of the Ideas
Immanent in Nervous Activity
“Because of the “all-or-none” character of nervous
activity, neural events and the relations among them can
be treated by means of propositional logic”
Interest in Subsymbolic AI
40
50
60
70
80
90
00
10
Artificial Neural Networks
• Neural networks are composed of:
– Layers of nodes (artificial neurons)
– Weights connecting the layers of nodes
• Different types of neural networks:
– Radial basis function networks
– Multi-layer feed forward networks
– Recurrent networks (feedback)
• Learning algorithms:
– Modify the weights connecting the nodes
In what problems ANNs are good?
• Noisy data from sensors
– overhead camera poor for orientation
• Some sensors don’t work well
• Can’t add new sensors (rules of the game)
• Other parts of the system constrain
available information (eg. radio
communications takes 25ms, frame
processing takes 15ms, etc)
Many ways of using ANNs.
• Problems can be specified in a number of
ways for neural network creation
• Neural networks are a generic technology
• Problem specification has a direct impact
on the application of the generic neural
network technology
• Problem specific information is vital
Some
Applications of
ANN
Application 1: Pattern
Recognition
1.
2.
3.
4.
5.
6.
Face recognition
Optical character recognition (OCR)
Medicine
Games (chess, bridge, go, …)
Finance
Gambling (greyhound racing)
74
Example : RECOGNIZING A PERSON
Glasses
Facial features
Hairstyle
Height
Face recognition
76
Steve Lawrence, C. Lee Giles, A.C. Tsoi and A.D. Back. Face Recognition: A Convolutional Neural Network Approach. IEEE Transactions on
Neural Networks, Special Issue on Neural Networks and Pattern Recognition, Volume 8, Number 1, pp. 98-113, 1997.
EXAMPLE - Machine Discovery:
for instance of new drugs
Famous Applications
• NASA’s intelligent flight control system
(F15As and C19s – NOT space shuttle)
• Handwritten number recognition
(postcodes on snail mail)
• Robotic arm control
• Number plate recognition on moving
cars
• Detection of cancerous cells in smear
tests
Example: Robot Soccer
• Control for robotic soccer
• Part of system
requirements: move the
robot to a target position
with certain orientation
• Dynamics of robot too
hard to model directly
• Overhead camera for
position (i.e. some
environmental constraints)
How to Represent the
Problem?
• Input representation of current & target
state:
– Distance and time or velocity?
– Orientation, degrees? Radians?
– Target position, current position, x-y? Polar?
• Output representation:
– Wheel velocities and translate to motor
currents?
– Number of wheels “clicks” per second?
Example:
Application of NN
to
Motion Planning
(Climbing Robot)
Transition
one-step planning
initial 4-hold
stance
...
3-hold
stance
...
...
...
4-hold
stance
one-step
planning contact / zero force
breaking
Idea: Learn Feasibility
 Create a large database
of labeled transitions
 Train a NN classifier
Q : transition  {feasible, not feasible)
 Learning is possible because:
Shape of a feasible space is mostly determined
by the equilibrium condition that depends on
relatively few parameters
Creation of Database
 Sample transitions at random
(by picking 4 holds at random
within robot’s limb span)
 Label each transition – feasible
or infeasible – by sampling with
high time limit
 over 95% infeasible transitions
 Re-sample around feasible
transitions
 35-65% feasible transitions
 ~1 day of computation to create a
database of 100,000 labeled transitions
Training of a NN Classifier

3-layer NN, with 9 input units, 100 hidden
units, and 1 output unit

Training on 50,000 examples
(~3 days of computation)

Validation on the remaining 50,000 examples
 ~78% accuracy (ε = 0.22)
 0.003ms average running time
What Have We Learned?
 Useful methods
 Connection between fields, e.g., control theory, game theory, operational
research
 Impact of hardware (chess software  brute-force reasoning, case-base
reasoning)
 Relation between high-level (e.g., search, logic) and low-level (e.g., neural
nets) representations: from pixels to predicates
 Beyond learning: What concepts to learn?
 What is intelligence? Impact of other aspects of human nature: fear of dying,
appreciation for beauty, self-consciousness, ...
 Should AI be limited to information-processing tasks?
 Our methods are better than our understanding
Sources used
Ellen Spertus
89
Backpropagation (Principle)
 New example y(k) = f(x(k))
 φ(k) = outcome of NN with weights
w(k-1) for inputs x(k)
 Error function:
 E(k)(w(k-1)) = ||φ(k) – y(k)||2
 wij(k) = wij(k-1) – εE/wij
(w(k) = w(k-1) - eE)
 Backpropagation algorithm:
Update the weights of the inputs
to the last layer, then the weights
of the inputs to the previous layer,
etc.