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?
> ...
> 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 !
 ~ 130000 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
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 !
17
Artificial Intelligence
versus
Natural Flight
18
Is the case for most of the
successful applications !
 Deep blue
 Alice
 Data mining
 Computer vision
 ...
19
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.
20
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
21
Which applications are easy ?
 For very specialized, specific tasks: AI
Example:
ECG-diagnosis
 For tasks requiring common sense: AI
22
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 ????
23
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,...
24
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
25
About this course ...
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
… …
… …
Ch.:Artificial Neural Networks
… …
… …
Ch.:Knowledge representation
… …
… …
Ch.:Phylosophy of AI
… …
… …
27
Technically: the contents:
- Search techniques in AI
- Machine Learning
- Constraint Processing
- Artificial Neural Networks
- Planning
- Automated Reasoning
28
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
29
Contents (3):
Different AI problem solving
paradigms...
State space representation and production
rules.
 Constraint-based representations.
 First-order predicate Logic.
30
… 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)
31
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.
32
Practical info (FAI)
 Exercises: about 12 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)
33
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 and Norvig: 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
 Assignment – deliver a report – deadline end
November ([email protected]):
 Designing your own exercise (for 4 parts) and
providing a model solution for it
 criteria: originality, does the exercise illustrate
all aspects of the method, complexity of the
exercise, correctness of the solution
35