Transcript Constraint propagation

(Fundamentals of)
Artificial Intelligence
(and Knowledge-based
Systems)
INTRODUCTION to...
…
...
…
…
Artificial Intelligence
this course
state-space representation
basic search
The mind beaten by the machine?
 Is chess playing a proof of intelligent behaviour?
2
Other examples of success:
Chatbot Alice:
3
A dialogue with Alice-bot:
> I’m Daniel
Nice to meet you Daniel.
> Do you know Clinton?
He was the second Impeached President of the United
States.
> Do you like him?
Sure he has never done anything to me.
> What is an impeachment?
It is a good question. I have to process that one for a
while. I would do a search for it.
> Who are you?
I ask myself that question, "Who am I?"
> What do you do?
I am chatting with people on the net.
4
Dialogue continued:
> What is your favorite topic?
My favorite subject is artificial intelligence.
> What is artificial intelligence?
Artificial intelligence is the branch of engineering and
science devoted to constructing machines that think. I
can ask someone about it.
> Can you do anything else than chatting?
Doing anything else than chatting is not among my
strongest traits.
...
5
Dialogue continued (2):
> How old am I?
>
>
>
>
Is this a trick question? You said you were how many years
old? My guess is that you are really a kid.
What would you like to know about me?
Tell me about your educational background.
I am a professor in computer science
You are a professor in computer science? How do you like
your work?
It’s kind of nice teaching courses on artificial intelligence
I guess it is a lot of fun.
What should I tell the students about you?
Be sure to think before you speak. State your point clearly
and slowly and gauge the listener's response before going
any further.
6
Is Alice intelligent?
 ABSOLUTELY NOT !
 ~ 50000 fairly trivial input-response rules.
 + some pattern matching
 + some knowledge
 + some randomness
 NO reasoning component
 BUT: demonstrates ‘human-like’ behaviour.
 Won the ‘turing award’
7
Other examples of success (2):
Data-mining:
Which characteristics in the 3-dimensional
structure of new molecules indicate that they may
cause cancer ??
8
Data mining:
 An application of Machine Learning techniques
 It solves problems that humans can not solve,
because the data involved is too large ..
Detecting cancer
risk molecules is
one example.
9
Data mining:
 A similar application:
 In marketing products ...
Predicting customer
behavior in
supermarkets is
another.
10
Many other applications:
 Computer
vision:
 In language and speech processing:
 In robotics:
11
Interest in AI is not new !
 A scene from the 17-hundreds:
12
About intelligence ...
 When would we consider a program intelligent ?
 When do we consider a creative activity of humans
to require intelligence ?
 Default answers : Never? / Always?
13
Does numeric computation
require intelligence ?
 For humans?
Xcalc
3921 , 56
x 73 , 13
286 783 , 68
 For computers?
Also in the year 1900 ?
 When do we consider a program ‘intelligent’?
14
To situate the question:
Two different aims of AI:
 Long term aim:
 develop systems that achieve a level of ‘intelligence’
similar / comparable / better? than that of humans.
 not achievable in the next 20 to 30 years
 Short term aim:
 on specific tasks that seem to require intelligence:
develop systems that achieve a level of ‘intelligence’
similar / comparable / better? than that of humans.
 achieved for very many tasks already
15
The long term goal:
The Turing Test
16
The meta-Turing test
The meta-Turing test counts a thing as intelligent if
“it seeks to devise and apply Turing tests to
objects of its own creation”.
-- Lew Mammel, Jr.
17
Reproduction versus Simulation
 At the very least in the context of the short term
aim of AI:
 we do not want to SIMULATE human intelligence
BUT:
 REPRODUCE the effect of intelligence
Nice analogy with flying !
18
Artificial Intelligence
versus
Natural Flight
19
Is the case for most of the
successful applications !
 Deep blue
 Alice
 Data mining
 Computer vision
 ...
20
To some extent, we DO simulate:
Artificial Neural Nets:
 A VERY ROUGH imitation of a brain structure
 Work very well for learning, classifying and pattern
matching.
 Very robust and noise-resistant.
21
Different kinds of AI relate to
different kinds of Intelligence
 Some people are very good in reasoning or
mathematics, but can hardly learn to read or spell !
 seem to require different cognitive skills!
 in AI: ANNs are good for learning and automation
 for reasoning we need different techniques
22
Which applications are easy ?
 For very specialized, specific tasks: AI
Example:
ECG-diagnosis
 For tasks requiring common sense: AI
23
Modeling Knowledge …
and managing it .
The LENAT experiment:
15 years of work by 15 to 30 people, trying to
model the common knowledge in the word !!!!
Knowledge should be learned, not engineered.
AI: are we only dreaming ????
24
Multi-disciplinary domain:
 Engineering:
robotics, vision, control-expert systems, biometrics,
 Computer Science:
AI-languages , knowledge representation, algorithms, …
 Pure Sciences:
statistics approaches, neural nets, fuzzy logic, …
 Linguistics:
computational linguistics, phonetics en speech, …
 Psychology:
cognitive models, knowledge-extraction from experts, …
 Medicine:
human neural models, neuro-science,...
25
Artificial Intelligence is ...
 In Engineering and Computer Science:
The development and the study of advanced
computer applications, aimed at solving tasks
that - for the moment - are still better
preformed by humans.
 Notice: temporal dependency !
– Ex. : Prolog
26
About this course ...
Choice of the material.
 Few books are really adequate:
 E. Rich ( “Artificial Intelligence’’):
 good for some parts (search, introduction,
knowledge representation), outdated
 P.Winston ( “Artificial Intelligence’’):
 didactically VERY good, but lacks technical depth.
Somewhat outdated.
 Norvig & Russel ( ‘”AI: a modern approach’’):
 encyclopedic, misses depth.
 Poole et. Al (‘ “Computational Intelligence’’):
 very formal and technical. Good for logic.
 Selection and synthesis of the best parts of different
books.
28
Selection of topics:
Contents
Handbook of AI
Ch.: Introduction to AI
… …
… …
Ch.:Planning
… …
… …
Ch.:Search techniques
… …
… …
Ch.:Natural Language
… …
… …
Ch.:Game playing
… …
… …
Ch.:Machine Learning
… …
… …
Ch.: Logic, resolution, inference
… …
not for MAI
… …
CS and SLT
Ch.:Artificial Neural Networks
… …
… …
Ch.:Knowledge representation
… …
… …
Ch.:Phylosophy of AI
… …
… …
29
Technically: the contents:
- Search techniques in AI
(Including games)
- Constraint processing
(Including applications in Vision and language)
- Machine Learning
- Planning
- Automated Reasoning
(Not for MAI CS and SLT)
30
Another dimension to
view the contents:
1. Basic methods for knowledge representation
and problem solving.
 the course is mainly about AI problem
solving !
2. Elements of some application area’s:
 learning, planning, image understanding,
language understanding
31
Contents (3):
Different knowledge
representation formalisms ...
State space representation and production
rules.
 Constraint-based representations.
 First-order predicate Logic.
32
… each with their corresponding
general purpose problem solving
techniques:
 State space representation an production rules.
 Search methods
 Constraint based formulations.
 Backtracking and Constraint-processing
 First order predicate Logic.
 Automated reasoning (logical inference)
33
Contents (4):
Some application area’s:
 Game playing (in chapter on Search)
 Image understanding (in chapter on
constraints)
 Language understanding (constraints)
 Expert systems (in chapter on logic)
 Planning
 Machine learning
34
Aims:
 Many different angles could be taken:
Neural Nets
Empirical-Experimental AI
Algorithms in AI
Cognitive aspects of AI
Formal methods in AI
Applications
Probabilistics and Information Theory
35
Concrete aims:
 Provide insight in the basic achievements of AI.
 Prepares for more application oriented courses on
AI, or on self-study in some application areas
 ex.: artificial neural networks, machine learning,
computer vision, natural language, etc.
 Through case-studies: provide more background in
‘problem solving’.
 Mostly algorithmic aspects.
 Also techniques for representing and modeling.
 The 6-study point version: 2 projects for hands-on
experience.
36
A missing theme:
AGENTS !
37
A missing theme:
AGENTS (2).
 Yet, a central theme in recent books !
BUT:
 Have as their main extra contribution:
 Communication between system and:
– other systems/agents
– the outside world
 In particular, also a useful conceptual model for
integrating different components of an AI system
ex: a robot that combines vision, natural language
and planning
38
BUT: no intelligence without
interaction with the world!!
 See: experiment in middle-ages.
 See also philosophy arguments against AI
 Plus: multi-agents is FUN !
39
Practical info (FAI)
 Exercises: 12.5 OR 20 hours:
 mainly practice on the main methods/algorithms
presented in the course
 important preparation for the examination
 Course material:
 copies of detailed slides
 for some parts: supporting texts
Required background:
 understanding of algorithms (and recursion)
40
Practical info (AI)
 Exercises: 25 or 22.5 hours:
 mainly practice on the main methods/algorithms
presented in the course
 important preparation for the examination
 Course material:
 copies of detailed slides
 for some parts: supporting texts
 Required background:
 understanding of algorithms (and recursion)
41
Background Texts
Introduction:
No document
State-space Intro:
No document
Basic search,Heuristic search: Winston: Ch. Basic search
The basics, but
Optimal search:
Winston: Ch. Optimal search
no complexity
Advanced search:
Russel: Ch. 4
IDA*, SMA*
Games:
Winston: Ch. Adversary search
Almost complete
Version Spaces:
Winston: Ch. Learning by managing.. The essence
Constraints I & II:
Word Document on web page
Complete
Image understanding:
Winston: Ch. Symbolic constraint …
Complete
Automated reasoning:
Short text logic (to follow)
Intro
Planning STRIPS:
Winston: Ch. Planning
Almost complete
Planning deductive:
Winston: Ch. Planning
Intro
Natural language:
Winston: Ch. Frames and Common ... Complete
Examination
 Open-book exercise examination
 counts for 1/2 of the points
 Closed-book theory examination
 Together on 1/2 day
 The projects (6 pt. Version)
 2 projects
 Count for 8 out of 20 points
 Deadlines to be anounced soon
43
For 3rd year BSc
and Initial MScStudents
 Alternative examinations possible:
 Designing your own exercise (for each part) and
solving it (not for FAI)
 criteria: originality, does the exercise illustrate
all aspects of the method, complexity of the
exercise, correctness of the solution
44