Transcript State graph

Chapter 10
Artificial Intelligence
Chapter 10: Artificial Intelligence







10.1 Intelligence and Machines
10.2 Understanding Images
10.3 Reasoning
10.4 Artificial Neural Networks
10.5 Genetic Algorithms
10.6 Other Areas of Research
10.7 Considering the Consequences
2
Intelligent agents

Agent = “device” that responds to
stimuli from its environment
Sensors—receive data from environment
--microphone, camera
 Actuators—response to the stimuli
--legs, wings, hands,


The goal of artificial intelligence is to
build agents that behave intelligently
3
Levels of intelligence in behavior




Reflex: actions are predetermined
responses to the input data
Intelligent response: actions affected by
knowledge of the environment
Goal seeking
Learning
4
Artificial intelligence research approaches
Agent’s intelligence is judged by
observing its input-response patterns
 Performance oriented: Researcher tries
to maximize the performance of the
agents.
 Simulation oriented: Researcher tries to
understand how the agents produce
responses.
5
Turing test




Proposed by Alan Turing in 1950
Benchmark for progress in artificial
intelligence
Test setup: Human interrogator
communicates with test subject by typewriter.
Test: Can the human interrogator distinguish
whether the test subject is human or machine?
6
Figure 10.1 The eight-puzzle in its
solved configuration
7
Figure 10.2 Our puzzle-solving machine
8
Techniques for understanding images



The first intelligent behavior required by the
puzzle-solving machine is the extraction of
information through a visual medium.
Unlike photographing an image, the problem
is to understand the image (Computer
Vision) –the ability to perceive.
Since the possible images are finite, the
machine can merely compare the different
sections of the picture to prerecorded
templates pixel by pixel, and reveal the
condition of the puzzle.
9
Techniques for understanding images



Optical readers apply the similar method for
image recognition (hand-writing).
A certain degree of uniformity(style, size,
orientation, non-overlapping, …) is required.
The alternative is to first extract the
geometric features(digit 1: a single vertical
line) and make comparison in terms of these
features
10
Techniques for understanding images





Template matching
Image processing: identify the characteristics
of the image.
Edge enhancement to clarify the boundary
(taking a derivative),
Region(with common properties: color, …)
finding for identifying objects,
Smoothing(removing flaws/noises in image),
11
Techniques for understanding images
Image analysis: identify the meaning of these
characteristics.
-- It is to recognize partially obstructed objects
from different perspectives.
-- First, assumption of what the image might
be is made. (clue)
-- Then, associate the image components with
the objects conjectured to exist.

12
Reasoning
After deciphering the positions of tiles from visual image,
the remaining task is to move the tiles to reach the
final state from the current state.
The eight-puzzle has many configurations such that
explicitly hard-coded each case for problem solving is
not generally feasible.
Some algorithm is necessary to resolve the problem in a
systematic way.
The machine will then ably make decisions, draw
conclusions, and perform elementary reasoning
activities.
13
Components of production
systems
A production system classifies the common
characteristics shared by a class of reasoning
problems, and has the following components:
1. Collection of states


Start or initial state
Goal state
2. Collection of productions: rules or moves

Each production may have preconditions
3. Control system: decides which production to
apply next
14
Data processing for production systems




State graph = states, productions, and
preconditions
A graph consists of nodes and arcs(arrows)
connecting nodes. A state graph has nodes
representing states and arrows representing rules.
The arc linking two nodes signifies two states can be
shift to each other using the rule; the absence of arcs
implicitly indicates the preconditions are not met.
The problem magnitude may be too large for
explicitly showing the entire state graph.
Partial representation of the state graph will help
understand the problem.
15
Data processing for production systems


State graph = states, productions,
and preconditions
Search tree = record of state
transitions explored while searching for
a goal state


Breadth-first search
Depth-first search
16
Figure 10.3 A small portion of the eightpuzzle’s state graph
17
Figure 10.4 Deductive reasoning in the
context of a production system
18
Figure 10.5 An unsolved
eight-puzzle
19
Figure 10.6 A sample search tree
20
Figure 10.7 Productions stacked for
later execution
21
Figure 10.8 An unsolved
eight-puzzle
22
Heuristic strategies




Generally, a search tree may grow much
huger if the nodes’ fan-outs are large.
It becomes more complicate if the goal is
very far away. (more generations)
Developing a full (exhaustive) search
tree[brute-force methods] may be impractical.
In contrast to this breadth-first approach
(layer by layer), we (humans) may attempt to
pursue the more promising paths to greater
depths in a depth-first manner. (vertical)
23
Heuristic strategies


Heuristic strategy is to develop a
heuristic–a quantitative measure on
how close a state is to the goal.
Requirements for good heuristics


Must be much easier to compute than a
complete solution
Must provide a reasonable estimate of
proximity to a goal
24
Figure 10.9 An algorithm for a control
system using heuristics
25
Figure 10.10 The beginnings of our heuristic
search
26
Figure 10.11 The search tree after two
passes
27
Figure 10.12 The search tree after
three passes
28
Figure 10.13 The complete search tree
formed by our heuristic system
29
Neural networks


CPU is not capable of perceive and reasoning
Artificial neuron



Each input is multiplied by a weighting factor.
Output is 1 if sum of weighted inputs exceeds a
threshold value; 0 otherwise.
Network is programmed by adjusting weights
using feedback from examples.
30
Figure 10.14 A neuron in a living
biological system
31
Neural networks


ANN are multi-processing architectures to
model networks of concurrent neurons.
Each processing unit in ANN is a simple
device to simulate the neuron.
The output of the unit may be 0 or 1, (or the
fractional numbers in-between), dependent
on the whether its effective input exceeds a
given threshold value.
32
Figure 10.15 The activities within a
processing unit
33
Figure 10.16 Representation of a
processing unit
34
Figure 10.17 A neural network with two different
programs: (a) o=1 when 2 inputs diff
(b)o=1 when both I=1
35
Neural networks


Different weights determine different
output values. Case (a) will produce 1
if its two inputs differ, while (b) outputs 1
if both inputs are 1’s.
A human brain contains roughly 10^11
neurons with about 10^4 synapses per
neuron.
36
character recognition:

A specific application –character
recognition: distinguish C and T,
regardless of the orientation. The
network produces a 0 if the recognized
letter is C, or a 1 if the letter is a T.
37
Figure 10.18 Uppercase C and
uppercase T
38
Figure 10.19 Various orientations of the
letters C and T
39
Neural networks
The system contains two levels of units. The
first level has many units, one for each 3x3
block of pixels.
Each unit has nine inputs; the inputs of adjacent
units overlap. Threshold = .5, center’s
weight = 2, others’weights = -1.
The second level only has one unit, with a
separate input for each unit in the first level.
Threshold = .5, each weight = 1.
It outputs a 1 iff at least one input is a 1.
40
Neural networks


If “C”is present, all the first level units
will produce a 0. All the possible cases
can be enumerated.
If “T”is present, only the first level’s unit
(highlighted below) will output a 1, while
others output 0’s. The final output is 1.
41
Figure 10.20 The structure of the
character recognition system
42
Figure 10.21 The letter C in the field of view
43
Figure 10.22 The letter T in the field of view
44
Associative memory


Associative memory = the retrieval
of information relevant to the
information at hand
One direction of research seeks to build
associative memory using neural
networks that when given a partial
pattern, transition themselves to a
completed pattern.
45
Figure 10.23 An artificial neural network
implementing an associative memory
1. The lines connecting
circles are two-way connection
i.e. output of one unit is connected
As input of other unit
2. The number associated with
Lines are weights
3. The number inside the circle is
threshold
46
Figure 10.24 The steps leading to a stable
configuration
1
-1
Two stable states
1. Perimeter stable state
(later stable state)
When we initialize the
Network with a least four
Adjacent units on the
Perimeter in their excited
states
47
The steps leading to a stable configuration
Two stable states
2. Center stable state
(former stable state)
When we initialize the
Network with center excited
And no more than two of
Perimeter in their excited
states
48
Genetic algorithms

Simulate genetic processes to evolve
algorithms




Start with an initial population of “partial solutions.”
Graft together parts of the best performers to
form a new population.
Periodically make slight modifications to some
members of the current population.
Repeat until a satisfactory solution is obtained.
49
Figure 10.25 Crossing two
poker-playing strategies
50
Figure 10.26 Coding the topology of an
artificial neural network
51
Language processing
Syntactic analysis(subject,verb, noun)
 Semantic analysis(identify actions)
 Contextual analysis(understanding)
--The bat flew from his hand.
Entire database
 Information retrieval(web searching)
 Information extraction(template)


Semantic net(a large linked data structure)
52
Figure 10.27 A semantic net
53
Robotics


Began as a field within mechanical and
electrical engineering
Today encompasses a much wider
range of activities


Robot cup competition
Evolutionary robotics
54
Expert systems

Expert system = software package to
assist humans in situations where
expert knowledge is required



Example: medical diagnosis
Often similar to a production system
Blackboard model: several problem-solving
systems share a common data area
55
Some issues raised by artificial intelligence



When should a computer’s decision be
trusted over a human’s?
If a computer can do a job better than
a human, when should a human do the
job anyway?
What would be the social impact if
computer “intelligence” surpasses that
of many humans?
56