Transcript Belief-optimal Reasoning for Cyber

CS B551: ELEMENTS OF
ARTIFICIAL INTELLIGENCE
1
Instructor: Kris Hauser
http://cs.indiana.edu/~hauserk
BASICS

Class web site


http://cs.indiana.edu/classes/b551
Textbook
S. Russell and P. Norvig
 Artificial Intelligence: a Modern Approach
 3rd edition


2nd edition can be used, but is not preferable
2
BASICS

Instructor


Kris Hauser ([email protected])
AIs

Mark Wilson ([email protected])
3
OFFICE HOURS

Kris Hauser


Tu 10-11,W 12-1 in Info E 257
Mark Wilson

M 1-2, Th 9-11 in TBA
4
AGENDA
Intro to AI
 Overview of class policies

5
WHAT IS AI?

AI is the reproduction of human reasoning and
intelligent behavior by computational methods
6
WHAT IS AI?

AI is an attempt of reproduction of human
reasoning and intelligent behavior by
computational methods
7
WHAT IS AI?

Discipline that systematizes and automates
reasoning processes to create machines that:
Think like humans
Think rationally
Act like humans
Act rationally
8
Think like humans
Think rationally
Act like humans
Act rationally
 The
goal of AI is: to build machines that
operate in the same way that humans think



How do humans think?
Build machines according to theory, test how
behavior matches mind’s behavior
Cognitive Science
 Manipulation
of symbolic knowledge
 How does hardware affect reasoning? Discrete
machines, analog minds
9
Think like humans
Think rationally
Act like humans
Act rationally
The goal of AI is: to build machines that perform tasks
that seem to require intelligence when performed by
humans
 Take a task at which people are better, e.g.:






Prove a theorem
Play chess
Plan a surgical operation
Diagnose a disease
Navigate in a building
and build a computer system that does it
automatically
 But do we want to duplicate human imperfections?

10
Think like humans
Think rationally
Act like humans
Act rationally
 The
goal of AI is: to build machines that make
the “best” decisions given current knowledge
and resources
 “Best” depending on some utility function

Influences from economics, control theory
 How
do self-consciousness, hopes, fears,
compulsions, etc. impact intelligence?
 Where do utilities come from?
11
WHAT IS INTELLIGENCE?
“If there were machines which bore a resemblance to our
bodies and imitated our actions as closely as possible for
all practical purposes, we should still have two very
certain means of recognizing that they were not real men.
The first is that they could never use words, or put
together signs, as we do in order to declare our thoughts to
others… Secondly, even though some machines might do
some things as well as we do them, or perhaps even better,
they would inevitably fail in others, which would reveal
that they are acting not from understanding, …”
Discourse on the Method, by Descartes (1598-1650)
12
WHAT IS INTELLIGENCE?

Turing Test (c. 1950)
13
14
AN APPLICATION OF THE TURING
TEST

CAPTCHA: Completely Automatic Public Turing
tests to tell Computers and Humans Apart
15
CHINESE ROOM (JOHN SEARLE)
16
CAN MACHINES ACT/THINK
INTELLIGENTLY?

Yes, if intelligence is narrowly defined as
information processing
AI has made impressive achievements showing
that tasks initially assumed to require
intelligence can be automated
Each success of AI seems to push further the
limits of what we consider “intelligence”
17
SOME ACHIEVEMENTS





Computers have won over world
champions in several games,
including Checkers, Othello, and
Chess, but still do not do well in
Go
AI techniques are used in many
systems: formal calculus, video
games, route planning, logistics
planning, pharmaceutical drug
design, medical diagnosis,
hardware and software troubleshooting, speech recognition,
traffic monitoring, facial
recognition, medical image
analysis, part inspection, etc...
DARPA Grand Challenge:
robotic car autonomously
traversed 132 miles of desert
IBM’s Watson competes with
Jeopardy champs
Some industries (automobile,
electronics) are highly robotized,
while other robots perform brain
and heart surgery, are rolling
on Mars, fly autonomously, …,
but home robots still remain
a thing of the future
18
18
CAN MACHINES ACT/THINK
INTELLIGENTLY?


Yes, if intelligence is narrowly defined as
information processing
AI has made impressive achievements showing
that tasks initially assumed to require
intelligence can be automated
Maybe yes, maybe not, if intelligence cannot be
separated from consciousness
Is the machine experiencing thought?
 Strong vs. Weak AI

19
BIG OPEN QUESTIONS

Is intelligent behavior just information
processing?
(Physical symbol system hypothesis)


If so, can the human brain solve problems
that are inherently intractable for
computers? Will a general theory of
intelligence emerge from neuroscience?
In a human being, where is the interface
between “intelligence” and the rest of
“human nature”


Self-consciousness, emotions, compulsions
What is the role of the body?
(Mind-body problem)
20



AI contributes to building an information
processing model of human beings, just as
Biochemistry contributes to building a model
of human beings based on bio-molecular
interactions
Both try to explain how a human being
operates
Both also explore ways to avoid human
imperfections (in Biochemistry, by engineering new
proteins and drug molecules; in AI, by designing
rational reasoning methods)


Both try to produce new useful technologies
Neither explains (yet?) the true meaning of
being human
21
MAIN AREAS OF AI







Knowledge representation
(including formal logic)
Search, especially heuristic
search (puzzles, games)
Planning
Reasoning under
uncertainty, including
probabilistic reasoning
Learning
Robotics and perception
Natural language processing
Agent
Robotics
Reasoning
Search
Perception
Learning
Knowledge Constraint
rep.
satisfaction
Planning
Natural
language
...
Expert 22
Systems
BITS OF HISTORY






1956: The name “Artificial Intelligence” is coined
60’s: Search and games, formal logic and theorem
proving
70’s: Robotics, perception, knowledge
representation, expert systems
80’s: More expert systems, AI becomes an
industry
90’s: Rational agents, probabilistic reasoning,
machine learning
00’s: Systems integrating many AI methods,
machine learning, natural language processing,
reasoning under uncertainty, robotics again
23
AI REFERENCES

Conferences


Journals


AI, Comp. I, IEEE Trans. Pattern Anal. Mach. Intel.,
IEEE Int. Sys., JAIR
Societies


IJCAI, ECAI, AAAI, NIPS
AAAI, SIGART, AISB
AI Magazine (Editor: IU’s David Leake)
24
CAREERS IN AI

‘Pure’ AI


Academia, industry labs
Applied AI
Almost any area of CS!
 NLP, vision, robotics
 Economics


Cognitive Science
25
SYLLABUS

Introduction to AI


Search


Probability, planning under uncertainty, Bayesian
networks, probabilistic inference, temporal sequences
Machine learning


Uninformed search, heuristic search, heuristics, game
playing
Reasoning under uncertainty


Philosophy, history, agent frameworks
Neural nets, decision tree learning, support vector
machines, etc.
Applications

Constraint satisfaction, motion planning, computer
vision
26
Computer Vision
Knowledge representation and
learning
B657
B552
S626
B555
S675
B553
I486
B556
Algorithms for Optimization
and Learning
B553
Biologically-inspired computing
Game theory
B551
E626
Robotics
B335
Q360
I400
Q570
Topics in AI
Natural Language Processing
B659
B651
27
CLASS POLICIES
28
PREREQUISITES
C211
 I recommend:

Two semesters programming
 Basic knowledge of data structures
 Basic knowledge of algorithmic complexity

29
PROGRAMMING ASSIGNMENTS
Projects will be written in Python
 Great for scripting


Peter Norvig, Director of Research at Google, and
textbook author
Easy to learn
 2 weeks for each assignment

30
GRADING

70% Homework


8 assignments - lowest score will be dropped
30% Final
31
HOMEWORK POLICY

Due at end of class on due date


Typically Thursdays
Extensions only granted in rare cases

Require advance notice except emergencies
32
FINAL PROJECT
 Encouraged
Individual or small groups (up to 3)
 Counts as three homework assignments

 Content



Software, new research, or technical report
Mid-semester project proposal
End-of-year report and in-class presentation
33
if you are intending to do
research or coursework in AI, pursue
higher degree
ENROLLMENT

Add/drop deadline
No penalty: Sept 2
 Late drop/add: Oct 26


Waitlist deadline: Sept 3
34
TAKEAWAYS

AI has many interpretations
Act vs. think, human-like vs. rational
 Concept has evolved


“Intelligence” has many interpretations
Turing test
 Chinese room


AI success stories from each perspective
35
HOMEWORK
Register
 Textbook
 Survey
 http://cs.indiana.edu/classes/b551
 Readings:

R&N Ch. 1, 26 (introduction and historical
perspectives)
 R&N 3.1-3

36