Transcript Introduction to Artificial Intelligence – Unit 1 What is

Introduction to Artificial Intelligence –
Unit 1
What is AI?
Course 240530
Dr. Avi Rosenfeld
Based on slides from
The Hebrew University of Jerusalem
School of Engineering and Computer Science
Instructor: Jeff Rosenschein
Topics
Week Breakdown
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Introduction to A.I., Course Organization, Introduction to Search
A*, Minimax, BFS, DFS, Heuristic search
Local Search Constraint Satisfaction Problems, DSP and DCOP algorithms
STRIPS and planning algorithms, Probability Theory and Bayesian Networks
Web based A.I., information retrieval and recommender systems
Neural Nets, Perceptrons and Machine Learning
Knowledge Representation, Game Theory, Bounded Rationality and Fuzzy Logic
NLP
Agents and Multi-agent systems
Robotics and Vision
Multidisciplinary Topics And Applications
Business Intelligence Applications
Project #3 (B.I.)
Review
2
What is A.I.?
What is AI?
Views of AI fall into four categories:
Thinking humanly
Thinking rationally
Acting humanly
Acting rationally
The AMAI textbook advocates “acting rationally”
4
The Brain vs. a Computer
Computer
Human Brain
Computational
Units
Storage Units
1 CPU, 109
gates
1010 bits RAM
1011 neurons
Cycle time
10-9 seconds
10-3 seconds
Bandwidth
1010 bits/sec
1014 bits/sec
Memory
109
updates/second
1011 neurons
1014
5
Artificial Intelligence
 Why is it difficult to program computers to do what
humans easily do?
 Recognize faces
 Understand human language
 (Ironically, we can more successfully program computers
to do what humans cannot easily do
 Play chess at world champion levels
 Carry out massive optimization problems)
 Processing power? – doesn’t seem to be the real issue
 Software?
 Scruffy vs. Neat debate
6
Artificial Intelligence:
Scruffy vs. Neat
 The Scruffy approach says, “Build
systems that work, and principles
will emerge.”
 E.g., the Wright Brothers building a
heavier-than-air flying machine
 The Neat approach says, “Explore
principles first, and having
understood them, embody them
in systems.”
 E.g., radar
7
Acting humanly: Turing Test
 Turing (1950) “Computing machinery and
intelligence”:
 “Can machines think?”  “Can machines
behave intelligently?”
 Operational test for intelligent behavior: the
Imitation Game

8
Acting rationally: rational agent
 Rational behavior: doing the right thing
 The right thing: that which is expected to
maximize goal achievement, given the
available information
 Doesn’t necessarily involve thinking – e.g.,
blinking reflex – but thinking should be in the
service of rational action

9
State of the art
 Deep Blue defeated the reigning world chess
champion Garry Kasparov in 1997
 Proved a mathematical conjecture (Robbins
conjecture) unsolved for decades
 No hands across America (driving
autonomously 98% of the time from
Pittsburgh to San Diego); DARPA Grand
Challenges (and Google) show that cars can
drive themselves inside and outside of cities
10
State of the Art
 During the 1991 Gulf War, US forces deployed
an AI logistics planning and scheduling
program that involved up to 50,000 vehicles,
cargo, and people
 NASA’s on-board autonomous planning
program controlled the scheduling of
operations for a spacecraft, and for the Mars
Rover
 Proverb solves crossword puzzles better
than most humans
11
Topics We’ll Cover







Introduction and Background: ½ week
Search: 2 ½ weeks
Knowledge Representation: 2 weeks
Planning: 2 weeks
Learning: 3 weeks
Game Theory: 3 weeks
Summation: 1 week
12
IJCAI’07 Papers
Number of accepted papers, by topic:
 1,365 papers submitted
(authors from 45
different countries)
 Accepted 471 papers
(unusually high
percentage that year,
34.4% accepted)
13
AI’s Recent High-Visibility Successes
•
•
•
•
Self-driving cars
Watson
Siri
Data-intensive applications that use
information analysis and learning to do
things previously beyond machine
capabilities
14
DARPA’s Grand Challenge
 First Challenge: Driver-less vehicle go 130 miles
across desert
 This was not a simple task: it involved unclear roads,
tunnels, roads along cliffs, and the path was given to teams
only hours before the race
 2004: $1 million prize, utter failure
 2005: $2 million prize
15
Google Cars, New York Times,
IEEE Spectrum
How Google’s cars work:
http://spectrum.ieee.org/automaton/robotics/artificial-intelligence/how-google-selfdriving-car-works
16
Google Cars, New York Times
17
IBM’s Watson
• Jeopardy is a quiz show, where answers are given,
and 3 contestants compete to be the first to provide
the question:
– “Freud published this landmark study in 1899.”
• What is “The Interpretation of Dreams”?
• In 2011, Watson competed against Ken Jennings
(who had the longest championship streak, 75 days),
and Brad Rutter, the all-time biggest money winner
on the show
• Final Score: Watson, $77,147;
Jennings, $24,000, Rutter, $21,600
18
IBM’s Watson, Jeopardy Winner
• “The first person mentioned by name in ‘The
Man in the Iron Mask’ is this hero of a
previous book by the same author.”
• “Hemophilia is a hereditary condition in which
this coagulates extremely slowly.”
• This director, better known as an actor,
directed his wife Audrey
• “A long, tiresome speech delivered by a
dessert topping.”
19
Google’s News Page
20
AI Researchers Head Major Industry
Research Labs
 Microsoft, Yahoo, and Google all take this very,
very seriously
 Peter Norvig, Google Director of Research
 Ron Brachman, built AT&T’s AI Research group,
now Vice President of Worldwide Research
Operations at Yahoo
 Eric Horvitz, head of Adaptive Systems &
Interaction Group, Microsoft Research
 AI Theory and AI Practice are looked to for
solutions
21
Ad Auctions
 “Google reported
revenues of $5.19
billion for the quarter
ended March 31,
2008”
 The vast majority of
this is from those
little ads on the right
of the page
22
Recommendation Systems
Collaborative
Filtering
Pioneered by, among others, Konstan
and Riedl, GroupLens
Commercial sites that use
collaborative filtering include:
Amazon
Barnes and Noble
Digg.com
half.ebay.com
iTunes
Musicmatch
Netflix (the Netflix Prize, grand prize
of $1,000,000 for algorithm that beats
Netflix's own by 10%)
TiVo
…
23
Data Mining
 Go through large amounts of data
 Extract meaningful insight
 Local Example: Ronen Feldman, Business
School professor at Hebrew University
(formerly Bar Ilan University), founded
ClearForest (bought by Reuters)
24
Collaborative Filtering plus
Data Mining
“The search for a better recommendation
continues with numerous companies selling
algorithms that promise a retailer more of an
edge. For instance, Barneys New York, the
upscale clothing store chain, says it got at
least a 10 percent increase in online revenue
by using data mining software that finds links
between certain online behavior and a
greater propensity to buy. Using a system
developed by Proclivity Systems, Barneys
used data about where and when a
customer visited its site and other
demographic information to determine on
whom it should focus its e-mail messages.” –
New York Times, 19.5.08
25
Spam Filters
When all those
emails from
Barneys New
York become
oppressive…
26
Comparative Shoppers
Pioneered by,
among others,
Bruce Krulwich
(BargainFinder),
Oren Etzioni
(MetaCrawler,
NetBot [bought by
Excite in 1997])
27
Comparison Shopping Plus Learning
 FareCast (formerly
Hamlet) tracks airline
prices, advises whether
to buy now or wait until
later
 Founded by Oren
Etzioni, bought by
Microsoft in April 2008
28
What Can’t They Do (Yet)?
 Integrate information in a more sophisticated
way
 “What were the combined earnings from ad
auctions across Google, Yahoo, and Microsoft in
2007?”
 Plan
 “How can I drive from San Francisco to Los
Angeles, in a way that reasonably maximizes the
number of Starbucks stores I pass?”
29
Translation
30
Speech Understanding
 Nuance’s Dragon
NaturallySpeaking and
IBM’s ViaVoice
31
Google Voice, 11.3.09
 "FREE VOICE MAIL TRANSCRIPTIONS: From
now on, you don’t have to listen to your
messages in order; you don’t have to listen to
them at all. In seconds, these recordings are
converted into typed text. They show up as email messages or text messages on your
cellphone."
32
iPhone Voice Control (pre-Siri)
33
Biology
 Computational Biology
 Techniques from Computer Science in general,
and Artificial Intelligence in particular, are
being used in the exploration of biological
questions
 AI researchers have played an important role
in this (e.g., Daphne Koller, Nir Friedman)
34
Computer Games
 Realistic single-agent and
multi-agent activity in
cooperative and competitive
environments
 What they call “AI” often isn’t
 But they are getting more
serious about it:
 Companies have started up
exploring
 Game AI
 Training programs (often military
training) for reacting to realistic
situations
35
Other Games: Poker
 Active research and
competitions (machine vs.
machine, machine vs.
person) in Texas Hold-Em
[University of Alberta,
Carnegie-Mellon University]
 Different domain than chess
– imperfect information
 CMU team is making use of
game theoretic equilibrium
concepts in their software
36
More Game Theory…
 Milind Tambe’s group at USC
studied optimal strategies for
intrusion detection, “Playing
Games for Security: An Efficient
Exact Algorithm for Solving
Bayesian Stackelberg Games”,
AAMAS’08
 Interesting theoretical work,
focused on efficient algorithms
 Deployed for last 18 months at
LAX airport in Los Angeles to tell
guards how to patrol
37
Contributions to Other Computer
Science Fields
 Operating Systems
 Programming Languages
 SmallTalk
 Lisp
 User Interface Design
 Advances in use of (not invention of) windows,
pointing devices, bitmapped graphics
 Web Services
 XML
38
A Moment on AI Ethics
• Who is responsible if a self-driving car is at fault in a
crash?
–
–
–
–
The software developer?
The company that installed the software?
The driver that trusted the software?
Society?
39
Agents and environments
 The agent function maps from percept histories to
actions:
[f: P*  A]
 The agent program runs on the physical architecture
to produce f
 agent = architecture + program
40
Agents
 An agent is anything that can be viewed as
perceiving its environment through sensors
and acting upon that environment through
actuators
 Human agent: eyes, ears, and other organs for
sensors; hands, legs, mouth, and other body
parts for actuators
 Robotic agent: cameras and infrared range
finders for sensors; various motors for
actuators
41