Transcript Chapter 1
Chapter 14: Artificial
Intelligence
Invitation to Computer Science,
C++ Version, Third Edition
Objectives
In this chapter, you will learn about:
Division of labor
Knowledge representation
Recognition tasks
Reasoning tasks
Invitation to Computer Science, C++ Version, Third Edition
2
Introduction
Artificial intelligence (AI)
Explores techniques for incorporating aspects of
intelligence into computer systems
Turing test
A test for intelligent behavior of machines
Allows a human to interrogate two entities, both
hidden from the interrogator
A human
A machine (a computer)
Invitation to Computer Science, C++ Version, Third Edition
3
Figure 14.1: The Turing Test
Invitation to Computer Science, C++ Version, Third Edition
4
Introduction (continued)
Turing test (continued)
If the interrogator is unable to determine which
entity is the human and which the computer, the
computer has passed the test
Artificial intelligence can be thought of as
constructing computer models of human
intelligence
Invitation to Computer Science, C++ Version, Third Edition
5
A Division of Labor
Categories of tasks
Computational tasks
Recognition tasks
Reasoning tasks
Computational tasks
Tasks for which algorithmic solutions exist
Computers are better (faster and more accurate)
than humans
Invitation to Computer Science, C++ Version, Third Edition
6
A Division of Labor (continued)
Recognition tasks
Sensory/recognition/motor-skills tasks
Humans are better than computers
Reasoning tasks
Require a large amount of knowledge
Humans are far better than computers
Invitation to Computer Science, C++ Version, Third Edition
7
Figure 14.2
Human and Computer Capabilities
Invitation to Computer Science, C++ Version, Third Edition
8
Knowledge Representation
Knowledge: a body of facts or truths
For a computer to make use of knowledge, it
must be stored within the computer in some form
Invitation to Computer Science, C++ Version, Third Edition
9
Knowledge Representation (continued)
Knowledge representation schemes
Natural language
Formal language
Pictorial
Graphical
Invitation to Computer Science, C++ Version, Third Edition
10
Knowledge Representation (continued)
Required characteristics of a knowledge
representation scheme
Adequacy
Efficiency
Extendability
Appropriateness
Invitation to Computer Science, C++ Version, Third Edition
11
Recognition Tasks
A neuron is a cell in the human brain, capable of:
Receiving stimuli from other neurons through its
dendrites
Sending stimuli to other neurons through its axon
Invitation to Computer Science, C++ Version, Third Edition
12
Figure 14.4: A Neuron
Invitation to Computer Science, C++ Version, Third Edition
13
Recognition Tasks (continued)
If the sum of activating and inhibiting stimuli
received by a neuron equals or exceeds its
“threshold” value, the neuron sends out its own
signal
Each neuron can be thought of as an extremely
simple computational device with a single on/off
output
Invitation to Computer Science, C++ Version, Third Edition
14
Recognition Tasks (continued)
Human brain: a connectionist architecture
A large number of simple “processors” with
multiple interconnections
Von Neumann architecture
A small number (maybe only one) of very powerful
processors with a limited number of
interconnections between them
Invitation to Computer Science, C++ Version, Third Edition
15
Recognition Tasks (continued)
Artificial neural networks (neural networks)
Simulate individual neurons in hardware
Connect them in a massively parallel network of
simple devices that act somewhat like biological
neurons
The effect of a neural network may be simulated
in software on a sequential-processing computer
Invitation to Computer Science, C++ Version, Third Edition
16
Recognition Tasks (continued)
Neural network
Each neuron has a threshold value
Incoming lines carry weights that represent stimuli
The neuron fires when the sum of the incoming
weights equals or exceeds its threshold value
A neural network can be built to represent the
exclusive OR, or XOR operation
Invitation to Computer Science, C++ Version, Third Edition
17
Figure 14.5
One Neuron with Three Inputs
Invitation to Computer Science, C++ Version, Third Edition
18
Figure 14.8
The Truth Table for XOR
Invitation to Computer Science, C++ Version, Third Edition
19
Recognition Tasks (continued)
Neural network
Both the knowledge representation and
“programming” are stored as weights of the
connections and thresholds of the neurons
The network can learn from experience by
modifying the weights on its connections
Invitation to Computer Science, C++ Version, Third Edition
20
Reasoning Tasks
Human reasoning requires the ability to draw on
a large body of facts and past experience to
come to a conclusion
Artificial intelligence specialists try to get
computers to emulate this characteristic
Invitation to Computer Science, C++ Version, Third Edition
21
Intelligent Searching
State-space graph:
After any one node has been searched, there are
a huge number of next choices to try
There is no algorithm to dictate the next choice
State-space search
Finds a solution path through a state-space graph
Invitation to Computer Science, C++ Version, Third Edition
22
Figure 14.12
A State-Space Graph with Exponential Growth
Invitation to Computer Science, C++ Version, Third Edition
23
Intelligent Searching (continued)
Each node represents a problem state
Goal state: the state we are trying to reach
Intelligent searching applies some heuristic (or
an educated guess) to:
Evaluate the differences between the present state
and the goal state
Move to a new state that minimizes those
differences
Invitation to Computer Science, C++ Version, Third Edition
24
Swarm Intelligence
Swarm intelligence
Models the behavior of a colony of ants
Swarm intelligence model
Uses simple agents that:
Operate independently
Can sense certain aspects of their environment
Can change their environment
May “evolve” and acquire additional capabilities
over time
Invitation to Computer Science, C++ Version, Third Edition
25
Intelligent Agents
An intelligent agent: software that interacts
collaboratively with a user
Initially an intelligent agent simply follows user
commands
Invitation to Computer Science, C++ Version, Third Edition
26
Intelligent Agents (continued)
Over time
Agent initiates communication, takes action, and
performs tasks on its own using its knowledge of
the user’s needs and preferences
Invitation to Computer Science, C++ Version, Third Edition
27
Expert Systems
Rule-based systems
Also called expert systems or knowledge-based
systems
Attempt to mimic the human ability to engage
pertinent facts and combine them in a logical way
to reach some conclusion
Invitation to Computer Science, C++ Version, Third Edition
28
Expert Systems (continued)
A rule-based system must contain
A knowledge base: set of facts about subject
matter
An inference engine: mechanism for selecting
relevant facts and for reasoning from them in a
logical way
Many rule-based systems also contain
An explanation facility: allows user to see
assertions and rules used in arriving at a
conclusion
Invitation to Computer Science, C++ Version, Third Edition
29
Expert Systems (continued)
A fact can be
A simple assertion
A rule: a statement of the form if . . . then . . .
Modus ponens (method of assertion)
The reasoning process used by the inference
engine
Invitation to Computer Science, C++ Version, Third Edition
30
Expert Systems (continued)
Inference engines can proceed through
Forward chaining
Backward chaining
Forward chaining
Begins with assertions and tries to match those
assertions to “if” clauses of rules, thereby
generating new assertions
Invitation to Computer Science, C++ Version, Third Edition
31
Expert Systems (continued)
Backward chaining
Begins with a proposed conclusion
Tries to match it with the “then” clauses of rules
Then looks at the corresponding “if” clauses
Tries to match those with assertions, or with the
“then” clauses of other rules
Invitation to Computer Science, C++ Version, Third Edition
32
Expert Systems (continued)
A rule-based system is built through a process
called knowledge engineering
Builder of system acquires information for
knowledge base from experts in the domain
Invitation to Computer Science, C++ Version, Third Edition
33
Summary of Level 5
Level 5: Applications
Simulation and modeling
New business applications
Artificial intelligence
Invitation to Computer Science, C++ Version, Third Edition
34
Summary
Artificial intelligence explores techniques for
incorporating aspects of intelligence into
computer systems
Categories of tasks: computational tasks,
recognition tasks, reasoning tasks
Neural networks simulate individual neurons in
hardware and connect them in a massively
parallel network
Invitation to Computer Science, C++ Version, Third Edition
35
Summary
Swarm intelligence models the behavior of a
colony of ants
An intelligent agent interacts collaboratively with
a user
Rule-based systems attempt to mimic the
human ability to engage pertinent facts and
combine them in a logical way to reach some
conclusion
Invitation to Computer Science, C++ Version, Third Edition
36