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