Transcript Intelligent Systems

Intelligent Systems
Introduction
Dieter Fensel
Francois Scharffe
©www.sti-innsbruck.at
Copyright 2008 STI INNSBRUCK www.sti-innsbruck.at
Agenda
• Overview of the lecture
• Introduction to the lecture topics
www.sti-innsbruck.at
2
Overview
•
Course home page:
http://teaching-wiki.sti2.at/index.php/Intelligent_Systems
(schedule, lecture notes, exercises, etc).
•
Textbook:
S. Russell and P. Norvig
Artificial Intelligence: A Modern Approach
Prentice Hall, 2003, Second Edition
•
Lecturer:
Dieter Fensel ([email protected])
•
Tutors:
Gulay Unel
•
Each week: lecture – tutorials organization come here
•
Attendance of the tutorials is obligatory !
•
Miss at most 2 times with written excuse ("was such nice weather" doesn't count!)
Grades:
•
Lecture:
final exam determines your grade
•
Tutorials:
Proper presentation of the reports and active interaction improves your grade.
Reports should be submitted before the tutorial
(more Details in the tutorials)
•
…Questions?
www.sti-innsbruck.at
3
Overview
1
Introduction
2
Propositional Logic
3
Predicate Logic
4
Model checking and theorem proving
5
Search methods
6
CommonKADS
7
Problem-Solving Methods
8
Planning
9
Agents
10 Rule learning
11 Inductive Logic Programming
12 Formal Concept Analysis
13 Neural networks
14 Semantic Web and Exam Preparation
www.sti-innsbruck.at
4
What is AI?
Views of AI fall into four categories:
Thinking humanly
Thinking rationally
Acting humanly
Acting rationally
The textbook advocates "acting rationally"
www.sti-innsbruck.at
5
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
•
•
•
Predicted that by 2000, a machine might have a 30% chance of fooling a lay person for 5 minutes
Anticipated all major arguments against AI in following 50 years
Suggested major components of AI: knowledge, reasoning, language understanding, learning
www.sti-innsbruck.at
6
Thinking Humanly: Cognitive Modelling
•
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
www.sti-innsbruck.at
7
Thinking Rationally: Laws of Thought
• Aristotle(384-322 BC)
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 purely logical deliberation
2) What is the purpose of thinking? What thoughts should I have?
www.sti-innsbruck.at
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
"Thinking"
"Reflex"
www.sti-innsbruck.at
Declarative Problem
Solving
"hard-coded" solution
algorithm
9
Rational Agents
• An agent is an entity that perceives and acts
• This course is in some sense about 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
• BUT: computational limitations make perfect rationality unachievable
 design best program for given machine resources.
www.sti-innsbruck.at
10
What is AI for John McCarthy?
• Q. What is artificial intelligence?
• A. It is the science and engineering of making intelligent machines,
especially intelligent computer programs. It is related to the similar
task of using computers to understand human intelligence, but AI
does not have to confine itself to methods that are biologically
observable.
• Q. Yes, but what is intelligence?
• A. Intelligence is the computational part of the ability to achieve goals
in the world. Varying kinds and degrees of intelligence occur in
people, many animals and some machines.
• ....[http://www-formal.stanford.edu/jmc/whatisai.html]
www.sti-innsbruck.at
11
What is AI for Marvin Minsky?
“Artificial Intelligence is the science of making machines
do things that require intelligence if done by men.”
Minsky and John McCarthy co-founded the MIT Artificial Intelligence Laboratory in 1961
www.sti-innsbruck.at
12
What is AI?
www.sti-innsbruck.at
13
Types of AI
•
Symbolic AI: Symbolic AI is based on logic. It uses sequences of rules to tell the computer what to
do next. Expert systems consist of many so-called IF-THEN rules: IF this is the case, THEN do that.
Since both sides of the rule can be defined in complex ways, rule-based programs can be very
powerful.
•
Connectionist AI: Connectionism is inspired by the brain. It is closely related to computational
neuroscience, which models actual brain cells and neural circuits. Connectionist AI uses artificial
neural networks made of many units working in parallel. Each unit is connected to its neighbours by
links that can raise or lower the likelihood that the neighbour unit will fire (excitatory and inhibitory
connections respectively). Neural networks that are able to learn do so by changing the strengths of
these links, depending on past experience. These simple units are much less complex than real
neurons. Each can do only one thing: for instance, report a tiny vertical line at a particular place in an
image. What matters is not what any individual unit is doing, but the overall activity-pattern of the
whole network.
•
Evolutionary AI: Evolutionary AI draws on biology. Its programs make random changes in their own
rules, and select the best daughter programs to breed the next generation. This method develops
problem-solving programs, and can evolve the “brains” and “eyes” of robots. It is often used in
modelling artificial life (A-Life). A-Life studies self-organization: how order arises from something that
is ordered to a lesser degree. Biological examples include the flocking patterns of birds and the
development of embryos.
www.sti-innsbruck.at
14
Branches of AI (John McCarthy) (1)
•
Logical AI: What a program knows about the world in general the facts of the specific
situation in which it must act, and its goals are all represented by sentences of some
mathematical logical language. The program decides what to do by inferring that certain
actions are appropriate for achieving its goals.
•
Search: AI programs often examine large numbers of possibilities, e.g. moves in a
chess game or inferences by a theorem proving program. Discoveries are continually
made about how to do this more efficiently in various domains.
•
Pattern recognition: When a program makes observations of some kind, it is often
programmed to compare what it sees with a pattern. For example, a vision program
may try to match a pattern of eyes and a nose in a scene in order to find a face. More
complex patterns, e.g. in a natural language text, in a chess position, or in the history of
some event are also studied. These more complex patterns require quite different
methods than do the simple patterns that have been studied the most.
www.sti-innsbruck.at
15
Branches of AI (John McCarthy) (2)
•
Representation: Facts about the world have to be represented in some way. Usually
languages of mathematical logic are used.
•
Inference: From some facts, others can be inferred. Mathematical logical deduction is
adequate for some purposes, but new methods of non-monotonic inference have been
added to logic since the 1970s. The simplest kind of non-monotonic reasoning is default
reasoning in which a conclusion is to be inferred by default, but the conclusion can be
withdrawn if there is evidence to the contrary. Ordinary logical reasoning is monotonic
in that the set of conclusions that can the drawn from a set of premises is a monotonic
increasing function of the premises.
•
Common sense knowledge and reasoning: This is the area in which AI is farthest
from human-level, in spite of the fact that it has been an active research area since the
1950s. While there has been considerable progress, e.g. in developing systems of nonmonotonic reasoning and theories of action, yet more new ideas are needed. The Cyc
system contains a large but spotty collection of common sense facts.
www.sti-innsbruck.at
16
Branches of AI (John McCarthy) (3)
•
Learning from experience: Programs do that. The approaches to AI based
on connectionism and neural nets specialize in that. There is also learning of
laws expressed in logic. Programs can only learn what facts or behaviors their
formalisms can represent, and unfortunately learning systems are almost all
based on very limited abilities to represent information.
•
Planning: Planning programs start with general facts about the world
(especially facts about the effects of actions), facts about the particular
situation and a statement of a goal. From these, they generate a strategy for
achieving the goal. In the most common cases, the strategy is just a
sequence of actions.
•
Epistemology: This is a study of the kinds of knowledge that are required for
solving problems in the world.
www.sti-innsbruck.at
17
Branches of AI (John McCarthy) (4)
• Ontology: Ontology is the study of the kinds of things that exist. In AI,
the programs and sentences deal with various kinds of objects, and
we study what these kinds are and what their basic properties are.
Emphasis on ontology begins in the 1990s.
• Heuristics: A heuristic is a way of trying to discover something or an
idea imbedded in a program. The term is used variously in AI.
Heuristic functions are used in some approaches to search to
measure how far a node in a search tree seems to be from a goal.
Heuristic predicates that compare two nodes in a search tree to see if
one is better than the other, i.e. constitutes an advance toward the
goal, may be more useful.
• Genetic programming: Genetic programming is a technique for
getting programs to solve a task by mating random Lisp programs and
selecting fittest in millions of generations.
www.sti-innsbruck.at
18
AI prehistory
• Philosophy
• Mathematics
• Economics
• Neuroscience
• Psychology
Logic, methods of reasoning, mind as physical
system foundations of learning, language,
rationality
Formal representation and proof algorithms,
computation, (un)decidability, (in)tractability,
probability
utility, decision theory
physical substrate for mental activity
phenomena of perception and motor control,
experimental techniques
building fast computers
• Computer
engineering
• Control theory design systems that maximize an objective
function over time
• Linguistics
knowledge representation, grammar
www.sti-innsbruck.at
19
Abridged history of AI
•
•
•
•
•
•
•
•
•
•
•
•
1943
McCulloch & Pitts: Boolean circuit model of brain
1950
Turing's "Computing Machinery and Intelligence"
1956
Dartmouth meeting: "Artificial Intelligence" adopted
1952—69 Look, Ma, no hands!
1950s
Early AI programs, including Samuel's checkers
program, Newell & Simon's Logic Theorist,
Gelernter's Geometry Engine
1965
Robinson's complete algorithm for logical reasoning
1966—73 AI discovers computational complexity
Neural network research almost disappears
1969—79 Early development of knowledge-based systems
1980-AI becomes an industry
1986-Neural networks return to popularity
1987-AI becomes a science
1995-The emergence of intelligent agents
www.sti-innsbruck.at
20
State of the Art
• Deep Blue defeated the reigning world chess champion Garry
Kasparov in 1997
(http://www.research.ibm.com/deepblue/home/html/b.shtml)
• Automated Reasoning methods proved a mathematical conjecture
(Robbins conjecture) unsolved for decades
• No hands across America (driving autonomously 98% of the time from
Pittsburgh to San Diego)
• Military is still the strongest factor for AI research: 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
• Proverb solves crossword puzzles better than most humans
www.sti-innsbruck.at
21
AI around us
• ABS uses fuzzy logic
(http://support.intel.com/design/mcs96/designex/2351.htm)
• Group of elevators work together under planning techniques to
minimize the time that the users have to wait.
(http://www.informatik.uni-freiburg.de/~koehler/elev/elev.html)
• Video Games like Age of Empire or Commandos use sophisticated AI
techniques (neural networks, planning techniques, genetic algorithms,
etc.) to increase the difficulty and realism of the game
(http://www.itee.uq.edu.au/~penny/commercial_AI.htm).
www.sti-innsbruck.at
22
Some AI relevant People
•
•
•
•
•
•
Isaac Asimov * (http://www.asimovonline.com/)
Arthur C. Clark * (http://www.clarkefoundation.org/)
John McCarthy (http://www-formal.stanford.edu/jmc/)
Marvin Minsky (http://web.media.mit.edu/~minsky/)
Donald Michie (http://www.aiai.ed.ac.uk/~dm/dm.html)
Allen Newell*
(http://www.princeton.edu/~hos/frs122/newellobit.html)
• Herbert A. Simon*
(http://www.psy.cmu.edu/psy/faculty/hsimon/hsimon.html)
• Alan Turing* (http://www.turing.org.uk/turing/)
www.sti-innsbruck.at
23
References
• S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach
Prentice Hall, 2003, Second Edition
• Alan Turing, Computing Machinery and Intelligence, 1950
• J. Mac Carthy, Programs with Common Sense, 1959
• A. Newell, The Knowledge Level, 1981
• H. Simon, A Behavioral Model of Rational Choice, 1955
• D. Fensel, E.Motta, Structured Development of Problem Solving
Methods, 2001
• T. Berners-Lee, J.Hendler, O. Lassila, The Semantic Web, 2001
www.sti-innsbruck.at
24