Artificial Intelligence (AI) Research Paper
pqsulabwn
COSC1336Chapter15Presentation.pdf
INVITATION TO
Computer Science 11
Chapter 15 Artificial Intelligence
Objectives
After studying this chapter, students will be able to:
• Define “artificial intelligence” and describe the
range of techniques and applications
• Explain the pros and cons of various knowledge
representation methods
• Explain the parts of a simple neural network, how it
works, and how it relates to real neurons
• Construct a state-space tree for simple state-space
problems
• Describe how state-space search algorithms work
Invitation to Computer Science, 6th Edition 2
Objectives (continued)
After studying this chapter, students will be able to:
• List the reasoning techniques described here, and
explain how each works
• Describe the use of state-space search to play
games, and why certain games are easier or more
difficult
• Describe how Watson approached the Jeopardy!
problem, and why the problem is difficult
• Explain what a robot is, and the tasks robots are
currently suited to do
Invitation to Computer Science, 6th Edition 3
Introduction
• Artificial Intelligence (AI): creating computer
systems that exhibit aspects of intelligence
• What is intelligence?
• The Turing Test
– Human judge questions two hidden entities
– One entity is a person
– One entity is a computer
– If judge cannot distinguish computer from person,
then computer is intelligent!
Invitation to Computer Science, 7th Edition 4
Invitation to Computer Science, 7th Edition 5
Introduction (cont'd.)
A Division of Labor
• Computational tasks
– Example: managing a payroll
• Recognition tasks
– Example: understanding the spoken word
• Reasoning tasks
– Example: planning your major in college
Invitation to Computer Science, 7th Edition 6
A Division of Labor (cont'd.)
• Computational tasks
– Typically have algorithmic solutions
– Computers perform faster than humans
– Computers perform more accurately than humans
• Recognition tasks
– Process massive amounts of sensory information
– Access massive amounts of past experience
– Require approximation
– Humans perform much better than computers
Invitation to Computer Science, 7th Edition 7
A Division of Labor (cont'd.)
• Reasoning tasks
– Formal reasoning can be automated to some extent
• Problems become intractable quickly
– Common-sense reasoning
• Requires great experience and knowledge
Invitation to Computer Science, 7th Edition 8
Invitation to Computer Science, 7th Edition 9
A Division of Labor (cont'd.)
Knowledge Representation
• How can we represent knowledge for the
computer?
• Natural language
– Use requires understanding of the meanings of
words and combinations of words
– “Spot is a brown dog”
– “Every dog has four legs”
Invitation to Computer Science, 7th Edition 10
Knowledge Representation (cont'd.)
• Formal language
– Language of formal logic
– “Spot is a brown dog” becomes
• dog(Spot) AND brown(Spot)
– “Every dog has four legs” becomes
• For every x, if x is a dog then x has four legs
• (∀x) dog(x) -> four-legged(x)
Invitation to Computer Science, 7th Edition 11
Knowledge Representation (cont'd.)
• Pictorial representation
– Knowledge as a digital picture
– Cannot represent categorical information
• Example: every dog has four legs
• Graphical representation
– Knowledge as nodes connected by edges
– Semantic net
• Nodes for objects or categories of objects
• Edges for relationships
• Nodes inherit features through “isa” relationships
Invitation to Computer Science, 7th Edition 12
Invitation to Computer Science, 7th Edition 13
Knowledge Representation (cont'd.)
Knowledge Representation (cont'd.)
• Requirements of a representation
– Adequacy: must capture all relevant information
– Efficiency: avoid redundant information
– Extendability: easy to add new knowledge
– Appropriate: easy to use for particular purpose
Invitation to Computer Science, 7th Edition 14
Recognition Tasks
• Some AI work attempts to mimic the brain
• Humans have 86 billion (1012) neurons
• A neuron receives electrical stimuli from other
neurons through dendrites
• A neuron sends electrical stimuli through its axon
• Signals pass through gaps, synapses
• Some synapses cause increased activation; others
inhibit activation
• Neurons are like very simple computational devices
Invitation to Computer Science, 7th Edition 15
Invitation to Computer Science, 7th Edition 16
Recognition Tasks (cont'd.)
• The nervous system is like a connectionist
architecture
– Processing arises from many simple processors with
rich and complex connections
• Processing in the brain occurs in a massively
parallel way
– Individual neurons are slow compared to computer
computational speeds
– Allows for redundancy and neuron failure (fault
tolerant)
Invitation to Computer Science, 7th Edition 17
Recognition Tasks (cont'd.)
• Artificial neural networks mimic the connectionist
approach
• Individual artificial “neurons” have:
– A threshold for generating output
– An activation level
– Incoming weighted edges
– Outgoing weighted edges
Invitation to Computer Science, 7th Edition 18
Invitation to Computer Science, 7th Edition 19
Recognition Tasks (cont'd.)
Recognition Tasks (cont'd.)
• Neural networks are often organized into input and
output layers
• To provide an input to the network, fix the values of
the input layer to 0 or 1
• Output nodes compute weighted sum of all inputs
– Activation from node i to node j is wij * xi
Invitation to Computer Science, 7th Edition 20
Invitation to Computer Science, 7th Edition 21
Invitation to Computer Science, 7th Edition 22
Recognition Tasks (cont'd.)
Recognition Tasks (cont'd.)
• Networks with only input and output layers:
– Can solve many problems, but
– Cannot solve XOR (or many others)
Invitation to Computer Science, 7th Edition 23
Invitation to Computer Science, 7th Edition 24
Recognition Tasks (cont'd.)
Recognition Tasks (cont'd.)
• Add an intermediate layer between input and
output
– Hidden layer
• Can solve most problems given the right weights
• How can we determine the correct weights?
• Neural networks are “trained” on sample data
– Machine learning: the network “learns” correct
responses to inputs
Invitation to Computer Science, 7th Edition 25
Recognition Tasks (cont'd.)
Training neural networks
• Training data: input/output pairs where output is
known to be correct for input
• Output nodes that are incorrect have quantifiable
error
• Use error to update weights to generate less error
• Backpropagation: algorithm that propagates
errors back through hidden layer(s) to input
Invitation to Computer Science, 7th Edition 26
Reasoning Tasks Intelligent Searching
• Decision tree represents possible next items for
which to search
• Linear search and binary search assume:
– Data is organized linearly
– Exact match is required
• What if we relax the requirements?
– What if data is not linear?
– What if an approximate match is okay?
Invitation to Computer Science, 7th Edition 27
Invitation to Computer Science, 7th Edition 28
Reasoning Tasks Intelligent Searching (cont'd.)
Reasoning Tasks Intelligent Searching (cont'd.)
• State-space graph
– Each node is a state of our problem
– A node connects to another if that state can be
directly generated by the node
– Examples: tic-tac-toe, eight-puzzle, maze-solving
– Each node has many children
– May be many paths to a goal
• State-space search: seeks a path from start state
to goal state
Invitation to Computer Science, 7th Edition 29
Invitation to Computer Science, 7th Edition 30
Reasoning Tasks Intelligent Searching (cont'd.)
Reasoning Tasks Intelligent Searching (cont'd.)
• State-space graph
– Each node is a state of our problem
– A node connects to another if that state can be
directly generated by the node
– Examples: tic-tac-toe, eight-puzzle, maze-solving
– Each node has many children
– May be many paths to a goal
• State-space search: seeks a path from start state
to goal state
Invitation to Computer Science, 7th Edition 31
Reasoning Tasks Intelligent Searching (cont'd.)
• Searching for a path to a goal
– Brute force: trace all branches of decision tree
• Too slow
– Heuristics: use educated guess to guide which
branches to search
• Example: chess
– Brute force is impossible
– Good heuristics enable computers to play at grand
master level
– Chess is the last “easy” hard problem
Invitation to Computer Science, 7th Edition 32
Reasoning Tasks Swarm Intelligence (cont'd.)
• Swarm intelligence model
– Model communities of simple agents, e.g., ants,
termites, etc.
• Ant colonies
– Individuals exhibit simple behaviors
– Colonies accomplish great things
• Finding the shortest path to food
• Constructing nests
• Ant colony optimization: route-finding using
simulated ants
Invitation to Computer Science, 7th Edition 33
Reasoning Tasks Intelligent Agents (cont'd.)
• Intelligent agent works with human user
– Learns user’s preferences and takes actions on
user’s behalf
• Current examples
– Personalized web search (push technology)
– E-commerce site that tailors suggestions to your
interests (recommendation software)
• Future applications
– Personal travel planner: buys tickets for user
– Office manager: screens calls, arranges meetings
Invitation to Computer Science, 7th Edition 34
Reasoning Tasks Expert Systems (cont'd.)
• Expert system: mimics reasoning in some specific
domain
• Knowledge base: knowledge about a domain
• Inference engine: rules for reasoning with
knowledge
• Often use formal language to represent knowledge
and rules for inference
• Employ deductive reasoning, e.g., modus ponens
Invitation to Computer Science, 7th Edition 35
Reasoning Tasks Expert Systems (cont'd.)
Expert system reasoning
• Forward chaining
– Start with assertions ► look for rules to deduce new
assertions
– Given assertion A and rule “if A then B” ► deduce B
• Backward chaining
– Start with a query ► look for rules that could deduce
query
– Given question “Is B true?” and rule “if A then B” ► try
to determine “Is A true?”
Invitation to Computer Science, 7th Edition 36
Reasoning Tasks Expert Systems (cont'd.)
• Explanation facility
– Users can see explanation based on the reasoning
chain
• Knowledge engineering
– Human system builders must spend time with
experts
– Listing and codifying the expert knowledge
Invitation to Computer Science, 7th Edition 37
Reasoning Tasks The Games We Play (cont'd.)
Board games
• Many programs use forms of state-space search
• Tic-tac-toe
– Small state space
– Brute force works to play perfectly
• Checkers
– Chinook project built and searched the complete
state space
– Results can be embedded in a computer player
– Chinook can never be beaten
Invitation to Computer Science, 7th Edition 38
Reasoning Tasks The Games We Play (cont'd.)
Board games
• Chess
– State space is too large to solve
– Computer players depend on heuristics
– Deep Blue defeated world champion Gary Kasparov
(1997)
• Go
– Huge search space
– Difficult for a computer to play well
– Current research is underway to reach top levels
Invitation to Computer Science, 7th Edition 39
40
Reasoning Tasks The Games We Play (cont'd.)
Invitation to Computer Science, 7th Edition
Reasoning Tasks
The Games We Play (cont'd.)
Quiz games: Jeopardy!
• Watson defeated Jeopardy! Champions (2011)
• Given a quiz “answer” and category:
– Applies multiple kinds of AI agents to search
database (of information from the web)
• Produces 300-500 candidate answers
– Narrows to one answer and evaluates its certainty in
real time
• Scoring and evaluation are done in parallel
•41Invitation to Computer Science, 7th Edition
Invitation to Computer Science, 7th Edition 42
Reasoning Tasks The Games We Play (cont'd.)
Invitation to Computer Science, 7th Edition 43
Reasoning Tasks The Games We Play (cont'd.)
Robots and Drones
• A robot is a physical device that takes in sensory
data and makes autonomous responses
• Current robot tasks
– Repetitive or dangerous for humans
– Manufacturing, bomb disposal, search-and-rescue
• New research on multiple cooperating robots
– Schools of robot fish for studying sea life
– Swarms of robot flies for reconnaissance
– Groups of robot snowmobiles to study climate
change
Invitation to Computer Science, 7th Edition 44
Robots and Drones (cont'd.)
• Humanoid robots are designed for interacting with
people
– Help elderly or hospital patients
– Monitor small children
• Japan is a leader in humanoid robots
– Aging population needs support
• Asimo, by Honda
– Designed to walk and move fluidly and robustly
– Can open/close a door to go through, serve
refreshments, etc.
Invitation to Computer Science, 7th Edition 45
Invitation to Computer Science, 7th Edition 46
Robots and Drones (cont'd.)
Robots and Drones (cont'd.)
• Deliberative strategy for robot control programs
– Maintain detailed internal model of the world
– Reason about sensory inputs and choose best
response
• Reactive strategy
– Limit/eliminate internal model
– React immediately to sensory inputs
– Rapid cycle from inputs to responses to more inputs
Invitation to Computer Science, 7th Edition 47
Robots and Drones (cont'd.)
• Drone
– Unmanned Aerial Vehicle (UAV)
– Controlled by a human at a remote site
– Primarily used by military and law enforcement
• Potential uses
– Deliver medical supplies
– Monitor dangerous situations, e.g. fires, floods, etc.
– Document wildlife
– Document urban traffic
Invitation to Computer Science, 7th Edition 48
Summary
• Artificial intelligence programs solve problems in
“intelligent” ways
• Knowledge may be represented in many different
ways; choice of representation depends on task
• Neural networks simulate the connectionist
structure of the nervous system
• Neural networks are trained to produce the correct
responses to inputs
• Reasoning may often be state-space search
Invitation to Computer Science, 7th Edition 49
Summary (cont'd.)
• Swarm intelligence uses colonies of simple agents
to solve problems
• Intelligent agents would be artificial personal
assistants
• Expert systems reason with expert domain
knowledge
• Game-playing is a common application for AI
• Robots perform tedious and dangerous tasks
• Drones are unmanned aerial vehicles
Invitation to Computer Science, 7th Edition 50
