Transcript Class Notes # 1: Overview - School of Electrical Engineering and

CSI 4106
Introduction to
Artificial Intelligence
Winter 2005
CSI 4106, Winter 2005
Overview, page 1
Some Information (1)
• Instructor: Dr. Nathalie Japkowicz
• Office: STE 5-029
• Phone Number: 562-5800 x 6693 (don’t rely on it!)
• E-mail: [email protected] (best way to contact me!)
• Office Hours: Monday, Wednesday 1:00pm-2:00pm
or by appointment
CSI 4106, Winter 2005
Overview, page 2
Some Information (2)
• Textbook: Luger, George, F.: Artificial
Intelligence, Structures and Strategies for
Complex Problem Solving , Addison Wesley,
Fifth Edition, 2005.
• Course Requirements:
 3 Assignments…………………. 30%
 Project Report/Presentation …..15%
 Midterm Exam……………….……20%
 Final Exam………………35%
CSI 4106, Winter 2005
Overview, page 3
Assignments
• Assignments must be handed in at the beginning of
classes, the day they are due. There are no make-up
assignments. The three assignments will have to be
handed in on the following days. They will be posted
two weeks before their due-date.
• Assignment #1 (LISP/Search) ----Due Date: Wednesday, February 6, 2008
• Assignment #2 (PROLOG/Logic) -----Due Date: Wednesday, March 5, 2008
• Assignment #3 (WEKA/Learning) -----Due Date: Wednesday, April 2, 2008
CSI 4106, Winter 2005
Overview, page 4
Project
Students, in teams of two, will do a project on the
practical applications of Artificial Intelligence.
 This will involve carrying out research on the topic of
the team’s choice, submitting a report on this research,
and giving an in-class presentation of 15 or so minutes,
during which both team members will have to speak.
 You can choose a topic from one of the following areas
of application:
•
•
•
•
Computer Games (A very
popular topic, in general !)
Expert Systems
Robotics
Planning
CSI 4106, Winter 2005
•
•
•
•
•
Natural Language Processing
Machine Learning/Data Mining
Neural Networks
Genetic Algorithms
AI and Psychology
Overview, page 5
Overview
Knowledge and Search
Search
Topics
Basic Search Methods
Heuristic Search
Games
Knowledge Representation
Logic
Rules
Uncertainty
Natural Language Processing
Basic Facts about English
Syntax
Semantics
Planning
Machine Learning
CSI 4106, Winter 2005
Overview, page 6
Definitions, overview, history
Points
Definitions of AI:
systems that
 think like humans
 act like humans
 think rationally
 act rationally
Physical-symbol systems
Sources and areas of AI
Bits of history
CSI 4106, Winter 2005
Overview, page 7
Definitions of Artificial Intelligence
A general classification of AI systems,
due to Russell and Norvig (1995, 2003):
systems that
think like humans
systems that
act like humans
CSI 4106, Winter 2005
systems that
think rationally
systems that
act rationally
Overview, page 8
The Turing test
Assessing intelligence by observation is biased: the
experimenter is guided by guesses rather than
measurable properties. This is a blind test.
CSI 4106, Winter 2005
Overview, page 9
Systems that think like humans
AI systems of this type would try to
recreate the human mind and its innate
(precoded?) cognition mechanisms.
This is very difficult, because it requires a
thorough understanding of psychology,
neurophysiology, and philosophy.
Such systems would belong to Cognitive
Science rather than Artificial Intelligence.
CSI 4106, Winter 2005
Overview, page 10
Systems that act like humans
E. Rich & K. Knight (1991)
AI is the study of how to make
computers do things which, at
the moment, people do better:
• perception,
• communication,
• reasoning,
• learning,
• planning.
CSI 4106, Winter 2005
Overview, page 11
... act like humans (2)
We do not even consider social behaviour,
sense of humour, appreciation of arts and
other talents that so far only Science Fiction
gives to machines.
Even an approximation of these faculties
requires vast amounts of knowledge (to
represent explicitly cultural background,
common sense and so on).
People also rely on experience -- perhaps on
memory patterns that we do not yet know how
to recreate in computer systems.
CSI 4106, Winter 2005
Overview, page 12
... act like humans (3)
Things at which computers will soon be
appreciably better: advice, diagnosis, fault
detection, forecasting...
Those would be systems where specific
technical knowledge plays a central role.
Measurable success will come when we
solve the problems of organizing and
acquiring vast knowledge.
We also need experience, rules-of-thumb,
and the ability to reason in the absence of
full information.
CSI 4106, Winter 2005
Overview, page 13
... act like humans (4)
Things at which computers are already
better, or nearly so:
formalized games such as chess,
chequers, backgammon, Othello;
formal inference (but not creativity and
invention).
They do require good heuristics -shortcuts -- of the kind that skilled
people apply, sometimes even without
conscious reflection.
CSI 4106, Winter 2005
Overview, page 14
... act like humans (5)
Neat: it is easy to verify the success of
all these tasks (after all, we are better).
The tasks are challenging, and can
hardly be solved by algorithmic means.
Ugly: the amount of necessary
knowledge is overwhelming; too many
tasks end up solved in a toy form.
Heuristics are fallible, and AI systems
are not trusted as they perhaps
deserve to be.
CSI 4106, Winter 2005
Overview, page 15
Systems that think rationally
E. Charniak & D. McDermott (1985)
AI is the study of mental faculties
through the use of computational
models.
Mental faculties (reasoning, learning,
perception) are studied more or less as in
psychology, except that working with
programs is easier and more objective,
more measurable.
On the other hand, programs require full
and explicitly stated knowledge.
CSI 4106, Winter 2005
Overview, page 16
... think rationally (2)
INTERNALS
INPUT
Deduction and search
OUTPUT
Vision
Planning
Robotics
Language
Explanation
Speech
Learning
Does "computational" imply computing?
Do brains work like computers? No, but:
what brain does may be thought of as a
kind of computation.
CSI 4106, Winter 2005
Overview, page 17
... think rationally (3)
P. H. Winston (1992)
AI is the study of the computations
that make it possible to perceive,
reason, and act.
These are the hallmarks of intelligence,
and they can be measured more or less
objectively.
Now, if we could agree that this is what
intelligence is about...
CSI 4106, Winter 2005
Overview, page 18
... think rationally (4)
AI can be indirectly characterized by (some of) its goals:
•make computers more useful,
•understand the principles that make intelligence
possible.
The contribution of AI methods and techniques to the
classical study of intelligence:
•computational metaphors for mental processes,
•precision of the data and structures (that is, knowledge),
•establishing practical limits for "intelligent" programs,
•repeatability of experiments -- and no ethical problems.
CSI 4106, Winter 2005
Overview, page 19
Systems that act rationally
G. F. Luger & W. F. Stubblefield (1993),
G. F. Luger (2005)
AI is the branch of computer science
concerned with the automation of
intelligent behaviour.
This means seeing AI as part of computer
science that grows out of the same basic
principles.
CSI 4106, Winter 2005
Overview, page 20
...act rationally (2)
Once more, we ask what is intelligence (if it can be
defined, so can AI):
is intelligence innate or acquired?
what is the essence of learning, creativity, intuition?
can we observe intelligence without knowing the
internal mechanisms (memory, search)?
can psychology, neurology and other related fields
help build AI systems? is it possible to have
intelligence without a host (body)?
These questions show how much is yet unknown. Practical AI
(building systems in the absence of a philosophical foundation) is
more like a blind search for answers.
CSI 4106, Winter 2005
Overview, page 21
Physical-symbol systems
A physical-symbol system is collection of
expressions built of elementary symbols
(without inherent meaning), and
processes that create and modify such
expressions
that exist in the context of the "real world".
Symbols can be mapped into real-world
entities, and processes into real-world
events.
A physical-symbol system is what we may
call a model of the real world.
CSI 4106, Winter 2005
Overview, page 22
Physical-symbol systems (2)
The physical-symbol system hypothesis:
we can model intelligence.
M. Ginsberg (1993)
AI is the enterprise of constructing a physicalsymbol system that can reliably pass the Turing
test.
G. F. Luger (2005) [revised definition]
AI is the study of the mechanisms underlying
intelligent behaviour through the construction
and evaluation of artifacts designed to enact
those mechanisms.
CSI 4106, Winter 2005
Overview, page 23
The sources of Artificial Intelligence
• Philosophy (ontology, epistemology, ...)
• Mathematics (logic, geometry, probability,
decision theory, ...)
• Psychology
• Linguistics, psycholinguistics
• Computing (theory; engineering practice)
CSI 4106, Winter 2005
Overview, page 24
The areas of Artificial Intelligence
• Search (blind, informed, adversarial)
• Knowledge representation (logic, semantic
networks, frames, rules, neural networks)
• Planning
• Machine Learning (symbolic, statistical;
data mining)
• Natural Language Processing (symbolic,
statistical; text mining)
• Perception (vision, speech)
• Robotics
CSI 4106, Winter 2005
Overview, page 25
Elements of the history of
Artificial Intelligence
The forerunners of AI:
information theory,
cybernetics (the study of communication
and control processes in biological,
mechanical, and electronic systems;
comparison of these processes in
biological and artificial systems).
Simple neural network computers (!) were
also built in 1940s and early 1950s.
CSI 4106, Winter 2005
Overview, page 26
... history of AI (2)
The first, very ambitious, tasks that
computing science set itself included
Machine Translation and Chess Playing
(Shannon 1950). Artificial Intelligence was
not in the cards yet...
These have not been too successful:
machine translation is still more craft than
science, and computer chess has only
recently become truly competitive, thanks
to specialized or superfast hardware.
CSI 4106, Winter 2005
Overview, page 27
... history of AI (3)
The term "Artificial Intelligence" has been
coined in mid-1950s by John McCarthy
(later the inventor of Lisp).
The first period of growth -- and funding -came in the 1960s. General Problem
Solver (Newell & Simon 1972): Aristotelian
(!) means-ends analysis.
Other early applications: analogy
discovery; simple question-answering
systems in toy domains.
CSI 4106, Winter 2005
Overview, page 28
... history of AI (4)
There followed a disillusionment and the
withdrawal of funds.
Renewed interest in the late 1970s
brought large funding (particularly from the
military). In this period: more and more
subtle knowledge representation methods,
first of all standard logic and various
advanced logics.
AI is sometimes seen as "applied logic"
(Nilsson, early 1970s).
CSI 4106, Winter 2005
Overview, page 29
... history of AI (5)
Programming languages best suited to AI
tasks are Lisp (1960) and Prolog (1972).
There also have been specialized
knowledge representation systems and
languages, used to develop knowledge
bases and knowledge-based systems.
This includes expert systems, in which
probability and beliefs play an important
role. Commercialization of some expert
systems is one the signs of the growing
maturity of AI.
CSI 4106, Winter 2005
Overview, page 30
... history of AI (6)
First textbooks appeared late (1971, then
1984). No theory of AI exists in spite of the
massive publication rate and the
bandwagon effect (Genesereth & Nilsson
1987 is a rare textbook devoted to the
foundations of AI).
Fads and trends: expert systems, genetic
algorithms, neural networks, data mining.
Successes have been rare and sometimes
bizarre: are intelligent warheads a success?
CSI 4106, Winter 2005
Overview, page 31
That’s it.
We will now turn to methods,
tools and techniques (but we
will occasionally look at a bit
of theory).
CSI 4106, Winter 2005
Overview, page 32