Transcript Chapter 14: Artificial Intelligence

Chapter 14: Artificial
Intelligence
Invitation to Computer Science,
Java Version, Third Edition
Objectives
In this chapter, you will learn about

A division of labor

Knowledge representation

Recognition tasks

Reasoning tasks

Robotics
Invitation to Computer Science, Java 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 being to interrogate two entities,
both hidden from the interrogator


A human being
A machine (a computer)
Invitation to Computer Science, Java Version, Third Edition
3
Figure 14.1
The Turing Test
Invitation to Computer Science, Java Version, Third Edition
4
Introduction (continued)

Turing test (continued)


If the interrogator is unable to determine which
entity is the human being and which is 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, Java 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 human beings
Invitation to Computer Science, Java Version, Third Edition
6
A Division of Labor (continued)


Recognition tasks

Sensory/recognition/motor-skills tasks

Human beings are better than computers
Reasoning tasks

Require a large amount of knowledge

Human beings are far better than computers
Invitation to Computer Science, Java Version, Third Edition
7
Figure 14.2
Human and Computer Capabilities
Invitation to Computer Science, Java 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, Java Version, Third Edition
9
Knowledge Representation
(continued)

Knowledge representation schemes

Natural language

Formal language

Pictorial

Graphical
Invitation to Computer Science, Java Version, Third Edition
10
Knowledge Representation
(continued)

Required characteristics of a knowledge
representation scheme

Adequacy

Efficiency

Extendability

Appropriateness
Invitation to Computer Science, Java Version, Third Edition
11
Recognition Tasks

A neuron is a cell in the brain capable of

Receiving stimuli from other neurons through its
dendrites

Sending stimuli to other neurons through its axon
Invitation to Computer Science, Java Version, Third Edition
12
Figure 14.4
A Neuron
Invitation to Computer Science, Java 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, Java 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, Java 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, Java 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, Java Version, Third Edition
17
Figure 14.5
One Neuron with Three Inputs
Invitation to Computer Science, Java Version, Third Edition
18
Figure 14.8
The Truth Table for XOR
Invitation to Computer Science, Java 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, Java 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, Java 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, Java Version, Third Edition
22
Figure 14.12
A State-Space Graph with Exponential Growth
Invitation to Computer Science, Java 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, Java 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, Java 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, Java 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, Java 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, Java 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, Java 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, Java 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, Java 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, Java 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, Java Version, Third Edition
33
Robotics

Robot: Device that can gather sensory
information autonomously

Many uses for robots (auto manufacturing, bomb
disposal, exploration, microsurgery)
Deliberative strategy: Robot has an internal
representation of its environment
Reactive strategy: Uses heuristic algorithms to
allow robot to respond directly to environment


Invitation to Computer Science, Java Version, Third Edition
34
Summary of Level 5

Level 5: Applications

Simulation and modeling

New business applications

Artificial intelligence
Invitation to Computer Science, Java Version, Third Edition
35
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, Java Version, Third Edition
36
Summary (continued)

Swarm intelligence models the behavior of a
colony of ants

Intelligent agent interacts 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

Robots can perform many useful tasks
Invitation to Computer Science, Java Version, Third Edition
37