Microsoft Powerpoint 1 Introduction Fix
KBS : Material
KBS : Introduction
Introduction
Pattern Matching
Knowledge Representation
Variables, Functions,
Motivation
ES Technology
Expressions, Constraints
Semantic Nets, Frames, Logic
Objectives
ES Tools
Reasoning and Inference
Expert System Design
What is an Expert System
shells, languages
ES Life Cycle
Predicate Logic, Inference
(ES)?
ES Elements
Methods, Resolution
Expert System
knowledge, reasoning
facts, rules, inference
Reasoning with Uncertainty
Implementation
General Concepts and
mechanism
Probability, Bayesian Decision
Salience, Rete Algorithm
Characteristics of ES
Important Concepts and
Making
Expert System Examples
knowledge representation,
Terms
Conclusions and Outlook
inference, knowledge
Chapter Summary
acquisition, explanation
Introduction 1
Introduction 2
Textbooks
Motivation
Required
utilization of computers to deal with knowledge
[Giarratano & Riley 1998] Joseph Giarratano and Gary Riley. Expert Systems -
quantity of knowledge available increases rapidly
Principles and Programming. 4th ed., PWS Publishing, Boston, MA, 2004
Recommended for additional reading
relieve humans from tedious tasks
[Awad 1996] Elias Awad. Building Expert Systems - Principles, Procedures,
computers have special requirements for dealing
and Applications. West Publishing, Minneapolis/St. Paul, MN, 1996.
[Durkin 1994] John Durkin. Expert Systems - Design and Development.
with knowledge
Prentice Hall, Englewood Cliffs, NJ, 1994.
acquisition, representation, reasoning
[Jackson, 1999] Peter Jackson. Introduction to Expert Systems. 3rd ed.,
Addison-Wesley, 1999.
some knowledge-related tasks can be solved better
[Russell & Norvig 1995] Stuart Russell and Peter Norvig, Artificial Intelligence -
A Modern Approach. Prentice Hall, 1995.
by computers than by humans
[M. Arhami, 2005] Muhammad Arhami, Konsep Dasar Sistem Pakar, Andi,
cheaper, faster, easily accessible, reliable
Yogya, 2005.
Introduction 3
Introduction 4
Objectives
What is an Expert System (ES)?
to know and comprehend the main principles,
relies on internally represented knowledge to
components, and application areas for expert
perform tasks
systems
utilizes reasoning methods to derive appropriate new
to understand the structure of expert systems
knowledge
knowledge base, inference engine
usually restricted to a specific problem domain
to be familiar with frequently used methods for
some systems try to capture common-sense
knowledge representation in computers
knowledge
to evaluate the suitability of computers for specific
General Problem Solver (Newell, Shaw, Simon)
tasks
Cyc (Lenat)
application of methods to scenarios or tasks
Introduction 5
Introduction 6
Definitions “Expert System”
Main Components of an ES
a computer system that emulates the decision-
User
making ability of a human expert in a restricted
Expertise
domain [Giarratano & Riley 1998]
Knowledge Base
Edward Feigenbaum
“An intelligent computer program that uses knowledge and
inference procedures to solve problems that are difficult
Facts / Information
enough to require significant human expertise for their
solutions.”
[Giarratano & Riley 1998]
User Interface
the term knowledge-based system is often used
Inference Engine
Expertise
synonymously
Developer
Introduction 7
Introduction 8
General Concepts and Characteristics
Main ES Components
of ES
knowledge base
knowledge acquisition
contains essential information about the problem domain
transfer of knowledge from humans to computers
sometimes knowledge can be acquired directly from the environment
often represented as facts and rules
machine learning
inference engine
knowledge representation
mechanism to derive new knowledge from the knowledge
suitable for storing and processing knowledge in computers
base and the information provided by the user
inference
often based on the use of rules
mechanism that allows the generation of new conclusions from
existing knowledge in a computer
user interface
explanation
interaction with end users
illustrates to the user how and why a particular solution was generated
development and maintenance of the knowledge base
Introduction 9
Introduction 10
Development of ES Technology
Rules and Humans
strongly influenced by cognitive science and
rules can be used to formulate a theory of human
mathematics
information processing (Newell & Simon)
the way humans solve problems
rules are stored in long-term memory
formal foundations, especially logic and inference
temporary knowledge is kept in short-term memory
production rules as representation mechanism
sensory input or thinking triggers the activation of rules
IF … THEN type rules
activated rules may trigger further activation
reasonably close to human reasoning
a cognitive processor combines evidence from currently
active rules
can be manipulated by computers
appropriate granularity
this model is the basis for the design of many rule-
knowledge “chunks” are manageable both for humans and for
based systems
computers
also called production systems
Introduction 11
[Dieng et al. 1999]
Introduction 12
Early ES Success Stories
The Key to ES Success
DENDRAL
convincing ideas
identification of chemical constituents
rules, cognitive models
MYCIN
practical applications
diagnosis of illnesses
medicine, computer technology, …
PROSPECTOR
separation of knowledge and inference
analysis of geological data for minerals
expert system shell
discovered a mineral deposit worth $100 million
allows the re-use of the “machinery” for different domains
XCON/R1
concentration on domain knowledge
configuration of DEC VAX computer systems
saved lots of time and millions of dollars
general reasoning is too complicated
Introduction 13
Introduction 14
When (Not) to Use ESs
ES Tools
expert systems are not suitable for all types of
ES languages
domains and tasks
higher-level languages specifically designed for knowledge
conventional algorithms are known and efficient
representation and reasoning
the main challenge is computation, not knowledge
SAIL, KRL, KQML, DAML
knowledge cannot be captured easily
ES shells
users may be reluctant to apply an expert system to a
an ES development tool/environment where the user
critical task
provides the knowledge base
CLIPS, JESS, Mycin, Babylon, ...
Introduction 15
Introduction 16
ES Elements
ES Structure
knowledge base
inference engine
Knowledge Base
Knowledge
working memory
Acquisition
agenda
Facility
explanation facility
Inference Engine Agenda
knowledge acquisition facility
User Interface
user interface
Explanation
Facility
Working Memory
Introduction 17
Introduction 18
Rule-Based ES
Example Rules
IF … THEN Rules
knowledge is encoded as IF … THEN rules
Rule: Red_Light
antecedent
these rules can also be written as production rules
IF
the light is red
(left-hand-side)
the inference engine determines which rule
THEN
stop
antecedents are satisfied
Rule: Green_Light
the left-hand side must “match” a fact in the working
consequent
memory
IF
the light is green
(right-hand-side)
satisfied rules are placed on the agenda
THEN
go
rules on the agenda can be activated (“fired”)
Production Rules
antecedent (left-hand-side)
an activated rule may generate new facts through its right-
hand side
the light is red ==> stop
the activation of one rule may subsequently cause the
consequent
activation of other rules
(right-hand-side)
the light is green ==> go
Introduction 19
Introduction 20
MYCIN Sample Rule
Inference Engine Cycle
Human-Readable Format
describes the execution of rules by the inference engine
IF
the stain of the organism is gram negative
conflict resolution
AND
the morphology of the organism is rod
select the rule with the highest priority from the agenda
AND
the aerobiocity of the organism is gram anaerobic
execution
THEN the there is strongly suggestive evidence (0.8)
perform the actions on the consequent of the selected rule
remove the rule from the agenda
that the class of the organism is enterobacteriaceae
match
MYCIN Format
update the agenda
IF
(AND (SAME CNTEXT GRAM GRAMNEG)
☯ add rules whose antecedents are satisfied to the agenda
☯ remove rules with non-satisfied agendas
(SAME CNTEXT MORPH ROD)
the cycle ends when no more rules are on the agenda, or
(SAME CNTEXT AIR AEROBIC)
when an explicit stop command is encountered
THEN (CONCLUDE CNTEXT CLASS ENTEROBACTERIACEAE
TALLY .8)
[Durkin 94, p. 133]
Introduction 21
Introduction 22
Forward and Backward Chaining
Foundations of Expert Systems
different methods of rule activation
Rule-Based Expert Systems
forward chaining (data-driven)
reasoning from facts to the conclusion
Inference Engine
Knowledge Base
as soon as facts are available, they are used to match antecedents
of rules
a rule can be activated if all parts of the antecedent are satisfied
Pattern
often used for real-time expert systems in monitoring and control
Facts
Rules
Matching
Conflict
examples: CLIPS, OPS5
Resolution
backward chaining (query-driven)
Rete
Post
starting from a hypothesis (query), supporting rules and facts are
Production
sought until all parts of the antecedent of the hypothesis are
Algorithm
Action
Rules
satisfied
Execution
often used in diagnostic and consultation systems
Markov
examples: EMYCIN
Algorithm
Introduction 23
Introduction 24
Post Production Systems
Markov Algorithms
production rules were used by the logician Emil L.
in the 1950s, A. A. Markov introduced priorities as a
Post in the early 40s in symbolic logic
control structure for production systems
Post’s theoretical result
rules with higher priorities are applied first
any system in mathematics or logic can be written as a
allows more efficient execution of production systems
production system
but still not efficient enough for expert systems with large
basic principle of production rules
sets of rules
a set of rules governs the conversion of a set of strings into
another set of strings
these rules are also known as rewrite rules
simple syntactic string manipulation
no understanding or interpretation is required
also used to define grammars of languages
☯ e.g. BNF grammars of programming languages
Introduction 25
Introduction 26
Rete Algorithm
ES Advantages
developed by Charles L. Forgy in the late 70s for
economical
CMU’s OPS (Official Production System) shell
lower cost per user
availability
stores information about the antecedents in a network
accessible anytime, almost anywhere
in every cycle, it only checks for changes in the networks
response time
this greatly improves efficiency
often faster than human experts
reliability
can be greater than that of human experts
no distraction, fatigue, emotional involvement, …
explanation
reasoning steps that lead to a particular conclusion
intellectual property
can’t walk out of the door
Introduction 27
Introduction 28
ES Problems
Summary Introduction
limited knowledge
“shallow” knowledge
expert systems or knowledge based systems are used to represent and
process in a format that is suitable for computers but still understandable
no “deep” understanding of the concepts and their relationships
by humans
no “common-sense” knowledge
If-Then rules are a popular format
no knowledge from possibly relevant related domains
the main components of an expert system are
“closed world”
knowledge base
the ES knows only what it has been explicitly “told”
inference engine
it doesn’t know what it doesn’t know
ES can be cheaper, faster, more accessible, and more reliable than
mechanical reasoning
humans
may not have or select the most appropriate method for a particular
ES have limited knowledge (especially “common-sense”), can be difficult
problem
and expensive to develop, and users may not trust them for critical
some “easy” problems are computationally very expensive
decisions
lack of trust
users may not want to leave critical decisions to machines
Introduction 29
Introduction 30
Important Concepts and Terms
agenda
knowledge base
backward chaining
knowledge-based system
common-sense knowledge
knowledge representation
conflict resolution
Markov algorithm
expert system (ES)
matching
expert system shell
Post production system
explanation
problem domain
forward chaining
inference
production rules
inference mechanism
reasoning
If-Then rules
RETE algorithm
knowledge
rule
knowledge acquisition
working memory
Introduction 31
