Introduction to Artificial Intelligence
Mitch Marcus
CIS391
Fall, 2011
Welcome to CIS 391
Course home page: [Link]
Textbook: S. Russell and P. Norvig Artificial Intelligence: A
Modern Approach Prentice Hall, 2009, Third Edition
Lecturer: Mitch Marcus, mitch(@)[Link], Levine 503
TA: Ryan Kennedy, Levine 471, kenry (@) [Link]
TA: Qiuye Zhao, Levine 514, qiuye (@) [Link]
Prerequisites: CSE 121 (Good knowledge of programming,
data structures)
1/12/2011 CIS 391 - Spring 2011 2
Grading & Homework
Grading:
• 40% Homeworks (Final project will count for 1/4 of that
amount)
• 30% Midterm 1
• 30% Midterm 2
Homework:
• Homework will be due at 11:00 a.m. on specified dates
• Late homeworks will be penalized unless an extension has
been granted in advance :
—15% reduction if 0-24 hours late
—30% reduction if handed in at the following class
—45% reduction if handed in two classes later
—No credit if more than a week late
1/12/2011 CIS 391 - Spring 2011 3
Tell us about yourself:
What department and year are you in?
Have you has a class in
• Probability and/or Statistics
• Logic
Have you written code in Python?
1/12/2011 CIS 391 - Spring 2011 4
“Computers who will proud of us”
1/12/2011 CIS 391 - Spring 2011 5
A REAL Accomplishment: DARPA Grand Challenge
1/12/2011 CIS 391 - Spring 2011 6
A REAL Accomplishment: DARPA Urban Challenge
1/12/2011 CIS 391 - Spring 2011 7
Some Real Accomplishments of AI
DARPA Grand Challenge – 123 miles through the desert
DARPA Urban Challenge – Autonomous Driving in Traffic!
Deep Space 1 – Remote Agent Experiment
Deep Blue defeated the reigning world chess champion
Garry Kasparov in 1997
Proved a mathematical conjecture (Robbins conjecture)
unsolved for decades
Logistics Planning for 1991 Gulf War
Computer Algebra Systems (Maple, Mathematica)
Credit Evaluation, Fraud Detection
Internet Search, Spam Filtering
Handwritten character recognition (checks, US mail)
Speech Recognition (Dictation)
1/12/2011 CIS 391 - Spring 2011 8
Thinking humanly Thinking rationally
Acting humanly Acting rationally
What is AI?
Views of AI fall into four categories:
Thinking humanly Thinking rationally
Acting humanly Acting rationally
We will focus on "acting rationally"
1/12/2011 CIS 391 - Spring 2011 9
Thinking humanly Thinking rationally
Acting humanly: Acting humanly Acting rationally
Turing Test
Turing (1950) "Computing machinery and intelligence":
“Can machines think?” “Can machines behave intelligently?”
Operational test for intelligent behavior: the Imitation Game
Predicted that by 2000, a machine might have a 30% chance of
fooling a lay person for 5 minutes
Anticipated most major arguments against AI
Suggested major components of AI: knowledge, reasoning,
language understanding, learning
1/12/2011 CIS 391 - Spring 2011 10
Thinking humanly Thinking rationally
Thinking humanly: Acting humanly Acting rationally
cognitive modeling
1960s "cognitive revolution": information-processing
psychology
Requires scientific theories of internal activities of the brain
How to validate? Requires
1) Predicting and testing behavior of human subjects (top-down)
or
2) Direct identification from neurological data (bottom-up)
Both approaches (roughly, Cognitive Science and Cognitive
Neuroscience) are now distinct from AI
Caveat: ACT-R & SOAR communities do computational
modelling of high level mental functions
1/12/2011 CIS 391 - Spring 2011 11
Thinking humanly Thinking rationally
Thinking rationally: Acting humanly Acting rationally
"laws of thought"
Aristotle: what are correct arguments/thought
processes?
Several Greek schools developed various forms of logic:
notation and rules of derivation for thoughts; may or may
not have proceeded to the idea of mechanization
Direct line through mathematics and philosophy to
modern AI
Problems:
1. Not all intelligent behavior is mediated by logical deliberation
2. What is the purpose of thinking? What thoughts should I have?
3. Ignores the hard problem of perception
1/12/2011 CIS 391 - Spring 2011 12
Thinking humanly Thinking rationally
Acting rationally: Acting humanly Acting rationally
rational agents
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
1/12/2011 CIS 391 - Spring 2011 13
Thinking humanly Thinking rationally
Acting humanly Acting rationally
Rational agents
An agent is an entity that perceives and acts
This course is about effective programming techniques for
designing rational agents
Abstractly, an agent is a function from percept histories to
actions:
[f: P* A]
For any given class of environments and tasks, we seek the
agent (or class of agents) with the best performance
Caveat: computational limitations make perfect rationality
unachievable
design best program for given machine resources
1/12/2011 CIS 391 - Spring 2011 14
Rational Agent skills can include:
Vision Processing
Planning
Robotics
Natural Language Understanding
Search Reasoning Machine Learning
Representation of the World
Symbols (Logic, Numbers)
1/12/2011 CIS 391 - Spring 2011 15
Alternate approaches to AI
Symbolic representations of the world
• Relations between entities
—―Lyle’s bicycle is red‖
– (isa B3241 bicycle) (color B3231 red) (owns B3241 P119)
– (isa P119 person) (name P119 ―Lyle‖)
• Explicit logical models
• Logical inference, Search
• Chess, Sudoko, computer games, …
Instance-based and statistical models
• Prediction by look-up or by weighted combinations
—P(y=bicycle) = c0 + c1 x1 +c2 x2 + c3 x3 + …
• Implicit probabilistic models
• Machine vision, document retrieval, speech recognition, …
1/12/2011 CIS 391 - Spring 2011 16
Course Overview – First Half
Module 0: Introduction
• Intelligent Agents
• Python Programming (Week long introduction)
Module 1: Search Strategies
• Uninformed & Informed Search
• Constraint Satisfaction (Sudoku Solver)
• Adversarial Search (Game Playing)
• Homework: Build a solver for any Sudoku problem
• Final Project: Build a bot that competes against other game
bots to play a simple board game (Kingdoms)
1/12/2011 CIS 391 - Spring 2011 17
Course Overview – Second Half
Module 2: Machine Learning and Natural Language
Processing
• Introduction to Probability and Bayesian Networks
• Naive Bayes (Spam Filtering)
• Hidden Markov Models & Part of Speech Tagging
• Decision Trees
• Perceptrons and Support Vector Machines
• Homework: Build a spam filter using Naïve Bayes machine
learning
1/12/2011 CIS 391 - Spring 2011 18
Course Overview – Second Half (cont.)
Module 3: Knowledge Representation and Logic
• Logical Agents (Automated Wumpus adventurer)
• Topics in Knowledge Representation
• Homework: Build an agent that plays Hunt the Wumpus
using propositional logic theorem proving
1/12/2011 CIS 391 - Spring 2011 19