Transcript Introduction to AI

Dr. Mike Bowman
Computer Science and Information
Systems Department
ACM Spring 2014
Acknowledgements
Learning Agents Center
and Computer Science Department
George Mason University
lalab.gmu.edu
Association for the Advancement of
Artificial Intelligence (AAAI)
www.aaai.org
2
AI – Thinking Machines?
Are you smarter than a machine?
Can machines think?
What is Skynet?
http://www.youtube.com/watch?v=DEtrzdGSXCU
What is the Matrix?
http://www.youtube.com/watch?v=WnEYHQ9dscY
3
4
How Smart Are You?
Can you
count the
cars in this
picture?
Can you
estimate
the time
of day in
this picture?
5
How Smart Are You?
Can you count the
Distribution of letters
in a book?
Add one thousand
4-digit numbers?
Match finger prints?
Search a list of a
million values for
duplicates?
6
AI – What is Real?
Are you smarter than a machine?
Who was Deep Blue?
http://www.youtube.com/watch?v=NJarxpYyoFI
Who is Watson?
http://www.youtube.com/watch?v=o6oS64Bpx0g&feature=related
What is the Singularity?
http://www.ted.com/talks/ray_kurzweil_announces_singularity_university.html
7
Current Reality?
The current reality is that computers and some robots
can do some really remarkable complex tasks, and in
some cases do them better than humans. But at the
same time, no one is yet arguing that machines are
conscious or possess human-level intelligence.
On the other hand, since no one seems to really
understand much about how the human brain works,
or what the basis of consciousness is (although some
are working on it), the state of AI today is still pretty
impressive.
8
Thinking Machines
Artificial intelligence (AI)
The study of computer systems that
attempt to model and apply the
intelligence of the human mind
For example, writing a program to pick
out objects in a picture
Where do you often
interact with AI?
9
AI in Games
The Good, the bad, and the ugly
(actually the reality)
Most modern computer/video games
include “intelligent” opposition – AI
http://www.youtube.com/watch?v=gr58eWO5Dgo
http://www.youtube.com/watch?v=tFxbakAamsc
http://www.youtube.com/watch?v=Ux0TZqEAiK0
10
The Turing Test
Turing test
A test to empirically determine whether a
computer has achieved intelligence
Alan Turing
An English mathematician wrote a landmark
paper in 1950 that asked the question: Can
machines think?
He proposed a test to answer the question
"How will we know when we’ve succeeded?"
11
The Turing Test
In a Turing test,
the interrogator
must determine
which responses
are from the
computer and
which are from
the human
12
The Loebner Prize
Loebner prize
The first formal instantiation
(1991) of the Turing test,
held annually
Chatbots
A program designed to carry on a
conversation with a human user
http://www.loebner.net/Prizef/loebner-prize.html
13
Some Focus Areas of AI
• Knowledge representation – represent
knowledge so that a computer can apply it
• Expert Systems – computer systems that
embody the knowledge of human experts
• Neural networks – computer systems that mimic
the processing of the human brain
• Natural language processing – computers that
can understand and use human speech
• Robotics – systems that can complete physical actions
to solve problems
Just a small sample of AI topics!
14
Knowledge Representation
How can we represent knowledge?
• We need to create a logical view of the
data, based on how we want to process it
• Natural language is very descriptive, but
doesn’t lend itself to efficient processing
• Semantic networks and search trees are
promising techniques for representing
knowledge
15
Semantic Networks
16
Knowledge Representation and Reasoning
Intelligent agents contain a representation of an application
domain, where information about the domain (objects, relations,
classes, laws, actions) are represented as symbolic expressions.
This mapping allows the agent to reason about the domain by
performing reasoning processes in the domain model, and
transferring the conclusions back into the application domain.
ONTOLOGY
OBJECT
SUBCLASS-OF
represents
BOOK
CUP
TABLE
INSTANCE-OF
If an object is on top of
another object that is itself
on top of a third object
then the first object is also
on top of the third object.
CUP1
ON
BOOK1
ON
TABLE1
RULE
 x,y,z  OBJECT,
(ON x y) & (ON y z)  (ON x z)
Application Domain
 2005, G.Tecuci, Learning Agents Center
Model of the Domain
17
Knowledge Base = Ontology + Rules
person
PROBLEM
SOLVING
TASK
ONTOLOGY
FRAGMENT
subconcept-of
Determine whether John Smith can be a PhD
advisor for Tom Even in Artificial Intelligence.
university
employee
student
subconcept-of
subconcept-of
IF: Determine whether ?O1 can be a PhD
advisor for ?O2 in ?O3.
faculty
undergraduate
staff
Main condition
member PhD_advisor
student
member
?O1 is
PhD_advisor
subconcept-of
has_as_employer
?O4
subconcept-of
has_as_position
?O5
professor
graduate
?O2 is
PhD_student
instructor
student
B.S. student
?O3 is
research_area
subconcept-of
?O4 is
university
subconcept-of
?O5 is
tenured_position
assistant
Except when condition
?O1 is
person
is_likely_to_move_to ?O6
?O6 is
employer
THEN: Determine whether ?O1 would
be a good PhD advisor for ?O2 in ?O3.
full
professor
professor
associate
professor
REASONING
RULE
Ph.D. student
M.S. student
 2005, G.Tecuci, Learning Agents Center
18
Search Trees
Search tree
A structure that represents alternatives in
adversarial situations such as game playing
The paths down a search tree represent a
series of decisions made by the players
19
Search Trees
20
Search Trees
Techniques for pruning search space
Depth-first
A technique that involves the analysis of selected
paths all the way down the tree
Breadth-first
A technique that involves the analysis of all
possible paths but only for a short distance down
the tree
Breadth-first tends to yield the best results
21
Search Trees
Depth-first and breadth-first searches
22
Expert Systems
Knowledge-based system
Software that uses a specific set of information, from
which it extracts and processes particular pieces
Expert system
A software system based on the knowledge of human
experts; it is
– Rule-based system
• A software system based on a set of if-then rules
– Inference engine
• The software that processes rules to draw conclusions
23
Expert Systems
Gardner Expert System Example
24
Expert Systems
Named abbreviations that represent
conclusions
NONE – apply no treatment at this time
TURF – apply a turf-building treatment
WEED – apply a weed-killing treatment
BUG – apply a bug-killing treatment
FEED – apply a basic fertilizer treatment
WEEDFEED – apply a weed-killing and
fertilizer combination treatment
25
Expert Systems
Boolean variables needed to represent state
of the lawn
– BARE: the lawn has large, bare areas
– SPARSE: the lawn is generally thin
– WEEDS: the lawn contains many weeds
– BUGS: the lawn shows evidence of bugs
26
Expert Systems
Some rules
– if (CURRENT – LAST < 30) then NONE
– if (SEASON = winter) then not BUGS
– if (BARE) then TURF
– if (SPARSE and not WEEDS) then FEED
– if (BUGS and not SPARSE) then BUG
– if (WEEDS and not SPARSE) then WEED
– if (WEEDS and SPARSE) then WEEDFEED
27
Expert Systems
Operation of expert systems can involve dialog
between a human and the system
–
–
–
–
–
–
–
–
–
System:
User:
System:
User:
System:
User:
System:
User:
System:
Does the lawn have large, bare areas?
No
Does the lawn show evidence of bugs?
No
Is the lawn generally thin?
Yes
Does the lawn contain significant weeds?
Yes
You should apply a weed-killing and
fertilizer combination treatment.
28
Neural Networks
Artificial neural networks
An attempt to represent knowledge, and
solve problems, with approaches that
mimic the way the human brain works.
– often involves probabilities and statistics to
determine (guess?) most likely outcomes.
29
Natural versus Artificial
Biological
Artificial
http://research.yale.edu/ysm/images/78.2/articles-neural-neuron.jpg
http://faculty.washington.edu/chudler/color/pic1an.gif
30
Natural Language Processing
Three basic types of processing occur during
human/computer voice interaction
Voice synthesis
Using a computer to create the sound of human speech
Voice recognition
Using a computer to recognizing the words spoken by a
human
Natural language comprehension
Using a computer to apply a meaningful interpretation to
human communication
31
Natural Language Comprehension
What does this sentence mean?
Time flies like an arrow.
– Time goes by quickly
– Time flies (using a stop watch to measure
speed of a fly) as you would time an arrow
– Time flies (a kind of fly) are fond of an arrow
Crazy?
Maybe, but a computer has great
difficulty with understanding context.
32
Rules and Machine Learning
Imagine a simple rule such as:
A+B+C=D
It could represent the rule an agent uses to identify a cat:
(4 legs) + (fur) + (meow) = CAT
A sophisticated agent “learns.”
If presented with a dog [(4 legs) + (fur) + (bark) = ??]
It should recognize it as not being a cat, and ask a human trainer
for clarification, resulting in a new rule:
A + B + E = F (4 legs) + (fur) + (bark) = DOG
33
Rules and Machine Learning
Start with the same rule:
A+B+C=D
It could represent the rule an agent uses to identify a cat:
(4 legs) + (fur) + (meow) = CAT
A very sophisticated agent “learns rapidly.”
It might generalize the rule to (~A) + (~B) + (~C) = CAT
It will occasionally “miss-fire” (ID a dog as a cat) by misusing
the generalized rule, but given “supervision and corrections”
by humans (explaining why it misused the rule), it will learn
rapidly.
34
State of the Art in AI
IBM’s Deep Blue
• Deep Blue was a special purpose computer that was able to calculate
nearly a quarter of a billion chess positions per second. It lost a match with a
world champion in 1996, but defeated that same champion in 1997.
• Certain endgame arrangements were always thought to represent a draw -no human had ever seen a way to win. Deep Blue and other chess playing
programs have found ways to win some of these games.
• The Asian game "go" will not succumb to such brute force methods -- there
are simply too many possible moves for even the most powerful current and
planned supercomputers. Instead, "real" AI will be needed -- intelligence
based on pattern recognition, "insight," and strategy.
35
State of the Art in AI
IMB’s Watson – Jeopardy Champion
Research question: Can a system be designed that applies
advanced data management and analytics to natural language
in order to uncover a single, reliable insight — in a fraction of
a second?
Watson beat human champions in Jeopardy, and is now being
used to investigate human health issues.
36
State of the Art in AI
DARPA Grand Challenge
The DARPA Grand Challenge tasked entrants to build an
autonomous robotic vehicle that could successfully navigate a
long, complex course, without human intervention.
None of the entrants in the 2004 Grand Challenge 1 completed
more than 10 miles of the 100 mile course.
In the 2005 Grand Challenge II, 5 of the 20+ entrants
completed the 132 mile race through the Mojave Desert, well
under the 10 hour time limit.
The 2007-2010 Urban
Challenge was to drive
through an urban setting.
It was successfully
completed by multiple
entrants!
37
State of the Art in AI
DARPA Robotics Challenge
The latest DARPA event is called the Robotics Challenge and
tasks entrants to build an all-terrain autonomous device that can
successfully navigate through complex obstacles like stairs,
without human intervention AND successfully complete missions
that are hazardous to humans.
38
AI versus Bowman
Where has a famous AI system and someone
named Bowman crossed paths?
http://www.youtube.com/watch?v=ARJ8cAGm6JE
CSC370 – Fall 2014
Tuesday and Thursday – 2:00-3:15 PM
39