Transcript Expert Systems

Copyright 2004 R. Weber
ISYS 370
Fall 2004
Professor: Dr. Rosina Weber
Copyright 2004 R. Weber
Data, information, knowledge
and knowledge representation
ISYS 370
Dr. R. Weber
Decision Making and Problem Solving
gathering information
of alternate strategies
Copyright 2004 R. Weber
the best strategy
implement
monitor
Decision Making and Problem Solving
information
Copyright 2004 R. Weber
knowledge
knowledge ??
What is knowledge?
Copyright 2004 R. Weber
• procedural knowledge
• declarative knowledge
What is computational
knowledge?
Copyright 2004 R. Weber
Knowledge representation
formalisms
•
•
•
•
•
frames
rules
cases
semantic nets
neural nets
Copyright 2004 R. Weber
• Let’s play 20 questions?
Copyright 2004 R. Weber
Frame of ?
•
•
•
•
•
•
•
Name: ? (goal)
Activity: ?, yes
Profession: ?, yes
Age: ?, no
Financial status?, no
Marital status?, yes
Legal status:
Frames
• one representation formalism commonly used
in expert systems
• represents declarative knowledge
• first introduced by M. Minski in 1975,
Copyright 2004 R. Weber
– A frame is a data-structure for representing a stereotyped
situation, like being in a certain kind of living room, or
going to a child's birthday party. Attached to each frame
are several kinds of information. Some of this information
is about how to use the frame. Some is about what one can
expect to happen next. Some is about what to do if these
expectations are not confirmed.
Copyright 2004 R. Weber
(production) rules
•A logic sequence of an antecedent (premise,
condition) and a consequence (conclusion, action).
•Both antecedent and conclusion are, in essence,
facts.
•The antecedent attempts to verify if the fact is
true or false, when the fact composing the
antecedent is true, the conclusion is triggered.
•The antecedent can be composed of several facts
connected through operators such as and, or, and
not.
•Conclusions usually change or assign values to
attributes of an object, call methods or trigger other
rules.
Concepts, Objects and Facts
An object is a basic entity that can be instantiated.
A concept tells something about the object.
Copyright 2004 R. Weber
A concept can be represented as an abstraction of an
object when several objects can be grouped under the
same concept; or a concept can be an attribute, when it
tells something exclusively about this object or due to the
analysis it is not worthy to represent it as an abstraction.
When an object is associated to a valued attribute, it is a
fact. A fact can be either true or false (Durkin, 1994).
So, you can describe concepts in a computer program by
communicating only via Y/N or T/F statements.
Copyright 2004 R. Weber
Cases, similarity functions
• Forms of knowledge representation used in
case-based reasoning systems
• A description of an experience can be used as
a knowledge representation formalism
• A case has to describe the problem and the
solution
• The description should be such that the
engine is capable of solving similar problems
given a case
Copyright 2004 R. Weber
Semantic Networks
• used in logic-based expert systems
• directed graphs where nodes represent
objects and arcs represent relationships
between objects and attributes
• Quillian, 1968
• used to represent static elements of a
representation such as the class, the
instances and its features
• cannot represent all magnitude of data ( meal
varying from sandwich to 20 course meal)
Copyright 2004 R. Weber
Neural Networks
• inputs and outputs are
represented numerically
• a matrix of weights learns the
input/output behavior
• weights in the matrix are
information
• the learned matrix (for facts in the
same category as the inputs)
represents knowledge
Copyright 2004 R. Weber
Expert Systems
INSYS 370 Artificial Intelligence for Information Systems
College of Information Science and Technology
Professor Rosina Weber
Copyright 2004 R. Weber
Expert Systems
• ES are a methodology to develop
computer programs that manipulates
expertise in a knowledge base to solve
expert problems in specific and restricted
domains.
Copyright 2004 R. Weber
Expert Systems
• Computer systems that can perform
expert tasks.
(general, vague)
• A methodology that manipulates explicit
knowledge with an inference engine to
perform AI tasks.
the concept
knowledge
knowledge
base
Copyright 2004 R. Weber
(e.g.,frames
and methods)
reasoning
inference
engine
(agenda)
expert
solution
expert
problem
The complete methodology
Knowledge acquisition
working memory
(short-term mem/information)
knowledge
base
Copyright 2004 R. Weber
(e.g.,frames
and methods)
inference
engine
(agenda)
explanation
general
knowledge
user
I
n
t
e
r
f
a
c
e
expert
problem
expert
solution
How do expert systems represent
knowledge and reasoning?
Representation formalisms
knowledge
base
Copyright 2004 R. Weber
(e.g.,frames
and methods)
• (production) rules
• frames (concepts, objects,
facts)
• rules and frames
• methods
• object-oriented
• semantic nets
• logic
Inference Engines
• Forward chaining
–Analysis, many different
results
inference
engine
(agenda)
Copyright 2004 R. Weber
• Backward chaining
–Limited number of possible
outputs
ES: types
• Rule-Based Expert Systems
Copyright 2004 R. Weber
– backward-chaining or forward-chaining
•
•
•
•
Frame-Based Expert Systems
Hybrid Expert Systems (rules + frames)
Object-Oriented Expert Systems
Task performers, int. assistants, int. tutors
Copyright 2004 R. Weber
ES requirements
• high quality: system must perform equally or
better than a human expert
• response time should be adequate to the problem it
solves
• reliable: not prone to crashes & errors
• explanation capability should be present with the
purpose of justification and verification of
correctness (p. 9,10 for explanation styles)
• flexible: supported by good maintenance methods
Copyright 2004 R. Weber
Expert Systems: history
• began 1965 at Stanford
• DENDRAL: a system that uses heuristics to
generate structures of data to perform
chemical analysis of the Martian soil and
works as well as an expert chemist;
• the first program recognized to have
succeeded due to the knowledge it contained
instead of complex search techniques;
Copyright 2004 R. Weber
Necessary grounds for computer
understanding
• Ability to represent knowledge and reason
with it.
• Perceive equivalences and analogies
between two different representations of
the same entity/situation.
• Learning and reorganizing new knowledge.
– From Peter Jackson (1998) Introduction to Expert systems.
Addison-Wesley third edition. Chapter 2, page 27.
Copyright 2004 R. Weber
When do we need ES?
• ES are indicated to solve expert problems
in restricted domains without an efficient
algorithmic solution
• Is there an alternative method?
• Ill-structured problems
• Is the domain well-bounded?
• How available is the source of knowledge?
• Is the approach to the problem heuristic?
Copyright 2004 R. Weber
ES: domain areas
• agriculture, business, chemistry,
communications, computer systems,
education, electronics, engineering,
environment, geology, law,
manufacturing, mathematics, medicine,
mining, power systems, simulation,
transportation, etc.
ES and AI tasks
Copyright 2004 R. Weber
•From:
Durkin, J.
(1994). Expert
Systems:
design and
development.
Prentice-Hall,
Inc., New
Jersey.
Expert Systems: development
humans books
source of
facts
expertise
documents
Copyright 2004 R. Weber
knowledge
acquisition
knowledge
engineer
KNOWLEDGE
ENGINEERING
knowledge
representation
knowledge
base
+
inference
procedures
Knowledge engineering
humans books
source of
facts
expertise
documents
Copyright 2004 R. Weber
knowledge
acquisition
knowledge
engineer
KNOWLEDGE
ENGINEERING
Knowledge
knowledge
based
+
representation
system
Example
Copyright 2004 R. Weber
• Shell KAPPA-PC
• Let’s see an example of a frame-based
expert system
Copyright 2004 R. Weber
advantages (i)
• Permanence of knowledge - Expert systems do not
forget or retire or quit, but human experts may
• Breadth - One ES can (and should) entail knowledge
learned from an unlimited number of human experts.
• Reproducibility - Many copies of an expert system
can be made, but training new human experts is
time-consuming and expensive.
• Timeliness - Fraud and/or errors can be prevented.
Information is available sooner for decision making
• Entry barriers and differentiation - An ES can
differentiate a product or can help create entry
barriers for potential competitors
Copyright 2004 R. Weber
advantages (ii)
• Cost savings & efficiency - can increase throughput
and decrease costs, e.g., wages, minimize loan
loss, reduce customer support effort
• Although expert systems may be expensive to build
and maintain, they are inexpensive to operate
• Development and maintenance costs can be spread
over many users
• The overall cost can be quite reasonable when
compared to expensive and scarce human experts
• If there is a maze of rules (e.g. tax and auditing),
then the expert system can "unravel" the maze
Copyright 2004 R. Weber
advantages (iii)
• Documentation - An expert system can provide
permanent documentation of the decision process
• Increased availability: the mass production of
expertise
• Completeness - An expert system can review all the
transactions, a human expert can only review a
sample; an ES solution will always be complete and
deterministic
• Consistency - With expert systems similar
transactions handled in the same way. Humans are
influenced by recency effects and primacy effects
(early information dominates the judgment).
advantages (iv)
Copyright 2004 R. Weber
• Reduced danger: ES can be used in any environment
• Reliability: ES will keep working properly regardless
of of external conditions that may cause stress to
humans
• Explanation: ES can trace back their reasoning
providing justification, increasing the confidence that
the correct decision was made
• Indirect advantage is that the development of an ES
requires that knowledge and processes are verified
for correctness, completeness, and consistency.
Copyright 2004 R. Weber
disadvantages (i)
• Common sense - In addition to a great deal of
technical knowledge, human experts have
common sense. To program common sense in an
ES, you must acquire and represent rules.
• Creativity - Human experts can respond creatively
to unusual situations, expert systems cannot.
• Learning - Human experts automatically adapt to
changing environments; expert systems must be
explicitly updated.
Copyright 2004 R. Weber
disadvantages (ii)
• Complexity and interrelations of rules grow
exponentially as more rules are added.
• Sensory Experience - Human experts have
available to them a wide range of sensory
experience; expert systems are currently
dependent on symbolic input.
• Degradation - Expert systems are not good at
recognizing when no answer exists or when the
problem is outside their area of expertise. So, ES
may provide a solution that is not optimal like one
that is optimal
Copyright 2004 R. Weber
disadvantages (iii)
• High knowledge engineering requirements: In many
real world domains, the amount of knowledge
necessary to cover an expert problem is abundant
making ES development time-consuming and
complex
• Knowledge acquisition bottleneck
• Difficulty to deal with imprecision (I.e.,
incompleteness, , uncertainty, ignorance, ambiguity)
Advantages & Disadvantages partially obtained from O’Leary, D. webpage
Some resources
• slides about advantages and disadvantages are
adapted from Introduction to Artificial Intelligence and
Expert Systems Copyright 1993, 1994, 1995 by Carol
E. Brown and Daniel E. O'Leary (available online at:
http://accounting.rutgers.edu/raw/aies/www.bus.orst.edu/faculty/brownc/es_tutor/es_tutor.htm
#5-AD
Copyright 2004 R. Weber
• Interrante,L.D. & Biegel,J.E.. Design of knowledgebased systems: matching representations with
application requirements. Computers and Engineering,
v.19, n.1-4, p.92-96,1990.
• http://www.aaai.org/AITopics/html/expert.html#reado
n