Transcript Expert Systems and Artificial Intelligence

Expert Systems and Artificial Intelligence
Gerard Tel
World War II as the AI Big Bang
Development in 1940-45:
What to do after WWII?
Create Humanoid machines.
• AI is concerned with
programming computers to
perform tasks that are
presently better done by
humans. (Minsky)
• Games, Language, Vision,
Mathematics
Expert Systems 1
2
Music classification by Compression
• Music interpretation problem:
Assign unknown symphony to
composer.
• Human approach: extract style,
emotion, era…
• Compression by Lempel-Ziv
(as in ZIP):
After “training”, compactly code common patterns.
• Compress file B after training with A:
DAB = | Cp(AB) | - | Cp(A) |
Measure for similarity between A and B.
• From known musical scores Ai, select the one that
minimizes DAiB.
• Hmmm… Is this intelligent?
Outperforms the best human music experts!!
Expert Systems 1
3
Mathematics: Triangle Theorem
T
Isosceles triangles are equiangular:
if AT = BT then <(A) = <(B).
B
Reasoning steps of geometry:
• If Δ(xyz) = Δ(uvw)
then <(y) = <(v)
• Line bisection:
take m on xy st xm = my.
• Congruence rule SSS:
if xy=uv, yz=vw, zx=wu
then Δ(xyz) = Δ(uvw).
A
20-30 axioms, theorems, and steps.
Expert Systems 1
4
The Human Proof
Given AT = BT,
Prove that <(A) = <(B).
Proof (Euclid):
1. Take M to bisect AB.
2. AT = BT
3. TM = TM
4. MA = MB
5. Δ(MAT) = Δ(MBT)
6. <(A) = <(B)
T
B
(Given)
(Trivial)
(From 1)
(SSS)
(congruence)
M
A
Found in all textbooks for 2500 years
since Euclid.
Expert Systems 1
5
The Computer Proof
Clever trick: Use possibility of a nontrivial self-congruence.
T
Given AT = BT,
Prove that <(A) = <(B).
Proof:
1. AT = BT
2. TB = TA
3. BA = AB
4. Δ(BAT) = Δ(ABT)
5. <(A) = <(B)
B
(Given)
(Given)
(Trivial)
(SSS)
(congruence)
Expert Systems 1
A
6
The search for a proof: State Space Exploration
General Problem Solver
Start state
• Model problem:
states and transitions.
• Search in induced graph.
• Search Strategies:
• Depth-First
• Breadth-First
• Best-First
• Heuristic
QED
Expert Systems 1
7
Where Computers and Humans differ
Why couldn’t a human find
the short proof?
Why couldn’t the computer find
the long proof?
• Tendency to overlook
simple and special cases
• It it too complicated!!
• Combinatorial Explosion
Branching factor 13
5 steps: 402,234 nodes
9 steps: 11,488,207,654
• Exploring exponential spaces
is intractible.
• But humans dont work like
this… they understand math
Expert Systems 1
8
What does it mean to understand?
• Jackson: The Romantic period in Artificial Intelligence
Overdragen: Chinese Room argument
• Understanding is INTENTIONAL:
Computers and Humans work IN THE SAME WAY
Argument: make the same mistakes, etc
• Understanding is BEHAVIORAL:
Computers and Humans
produce the same results
Turing test
• Why is it difficult to
mimic human behavior
in a computer?
Expert Systems 1
9
Understanding in Expert Systems?
Understanding requires:
• Representation and
manipulation of
Domain Knowledge
• Perceive analogies
• Learn
Pragmatic view:
• Intentional intelligence
is not required
• Programs will work the
better if more human
domain knowledge is
encoded in them
Normative Descriptive
Limitive
Definition of Expert System:
An Expert System is a
computer program that
represents and reasons with
knowledge of some
specialist subject with a
view to solving problems or
giving advice
Expert Systems are a
subfield of Artificial
Intelligence.
Term:
Knowledge Based System
Expert Systems 1
10
Understanding Geometry: Represent knowledge
Mathematician solves proof:
• To conclude <(A) = <(B),
find Δ(xAy) and Δ(uBv);
prove congruence.
• To conclude <(A) = <(B),
construct <(C) = <(A);
prove <(C) = <(B).
• To prove congruence, use
SSS, ASA, SAS, …
• To construct …
• Triangle 1 is better than
triangle 2 because …
• I usually try SAS first
when…
Formalization of strategy:
• Consider triangle pairs
xAy and uBv
• Select a promising pair
• Select a promising rule R
• Prove antecedents of R
• Conclude congruence
• Conclude equality of
angles
Strategies can be
represented in STRIPS
Backtracking,
Ordering of alternatives,
Pruning,
Expert Systems 1
…
11
STRIPS Operator Tables
Robot moves object X from location Y to location Z:
Operator Table push(X, Y, Z)
• Pre:
at(robot, Y), at(X, Y)
• Post:
at(X, Z)
• Add list:
at(robot, Z), at(X, Z)
• Delete list:
at(robot, Y), at(X, Y)
STRIPS maintains a goal list.
Action:
• Pick goal G from goals
• Pick OT with G in Post
• Throw Pre of G in goals
Planning is at higher level than
individual actions.
Expert Systems 1
12
Uniform representation of facts
Synonyms:
1. Sam is the father of Bill
2. Sam is Bill’s father
3. Bill is Sam’s son
4. Sam is Bill’s mother’s
husband
Perceiving analogies
requires uniform
representation:
• sonOf(Sam, Bill)
SHRDLU World:
color(block1, red)
color(block2, green)
supports(table, block1)
supports(block1, block2)
Represent many facts with
simple fact structure
Expert Systems 1
13
Data representation: Relational Database
Define a relation in CLIPS
(deftemplate errand
(field name (type SYMBOL))
(field duration (type INTEGER) ) )
Relation errand with attributes name and duration.
Add tuples to relation errand:
(deffacts the-facts
(errand (name hospital) (duration 200) )
(errand (name doctor) (duration 100) ) )
CLIPS actions and rules as Database operations.
Update fact base when state is changed.
Expert Systems 1
14
Explicitation of Expert knowledge
Problem 1: What does it stand for in
• The ball hit the vase and it broke
• The vase hit the wall and it broke
Problem 2: Using hammer, string, and wrench, liberate
ball from tube in floor.
(Solution could never be found by computer!!)
Application of XS requires:
• restriction to a well-understood domain (ball?)
• someone who can perform the task
• knows how it is performed (it?)
• can explain how it is performed
• is willing to cooperate
Expert Systems 1
15
Characteristics of Expert Systems:
Expert systems: Knowledge Based Systems
• Separation of facts, knowledge, and inference
knowledge is explicit, not hidden in algorithm
• Simulates Human reasoning
Built from approach of Human Expert
• Uses approximate or heuristic search
Not the only approach to solving AI problems!
(Music classification, chess…)
Use: Legal, medical, scientific,
tech support, language, …
Expert Systems 1
16
Parties in XS world
• Human Expert
Can solve problems;
we desire to solve the problems without her.
• Knowledge Engineer
Can communicate with HE to obtain and
model the knowledge that we need in the system
• Programmer
Builds and maintains all the necessary computer
programs
• User
Wants to use expertise to solve problems
(better, cheaper)
Expert Systems 1
17
Explanation facilities
System makes explicit why the conclusion is reached
• For User:
increases confidence
increases transparance (legal domain!)
• For Human Expert/Knowledge Engineer:
see how knowledge is used, debug
• For Programmer:
Debug, Test, Improve
• For trainee:
have better understanding of expertise
Expert Systems 1
18
Main challenges in Expert Systems field
• Acquiring knowledge
Expert is unaware, uncommunicative, busy, unwilling
• Representing knowledge
Facts, Relations, Conclusions, Meta-knowledge
• Controlling reasoning
Selection between alternatives is guided by higher order
knowledge (meta rules)
• Explanation
• Sequence of reasoning steps?
• Interpretation at higher level
• Why were other steps NOT chosen?
• Quality evaluation; acceptance
Expert Systems 1
19
The Expert Systems course
• www.cs.uu.nl/docs/vakken/exp/
• Teacher: Gerard Tel
Practicals: Johan Kwisthout
• One or two papers per lecture
• Optional reading:
Peter Jackson, Introduction to Expert Systems
• Formal obligations: two exams,
two computer projects in teams of four.
MIN ≥ 4, WeightedAVG, 2nd chance.
• Prepare for working class:
read literature, try exercises (website)
• Prepare for tests:
Working class, previous tests (website)
Expert Systems 1
20