DCIT 313
Introduction to Artificial
Intelligence
Session 2 – Knowledge and Rule-based Expert
Systems
Course Writer: Dr Kofi Sarpong Adu-Manu
Contact Information: [email protected]
CBAS
School of Physical and Mathematical Sciences
2020/2021 – 2022/2023
Subsets of Artificial Intelligence
Contents
• What is Knowledge?
• What is Knowledge Acquisition?
• The Expert Systems Development Team.
• Rules and Knowledge Representation
• Rule-based Expert Systems.
• Characteristics of Expert Systems.
3
Motivation
• utilization of computers to deal with knowledge
– quantity of knowledge available increases rapidly
– relieve humans from tedious tasks
• computers have special requirements for dealing with
knowledge
– acquisition, representation, reasoning
• some knowledge-related tasks can be solved better by
computers than by humans
– cheaper, faster, easily accessible, reliable
Objectives
• to know and comprehend the main principles,
components, and application areas for expert systems
• to understand the structure of expert systems
– knowledge base, inference engine
• to be familiar with frequently used methods for
knowledge representation in computers
• to evaluate the suitability of computers for specific tasks
– application of methods to scenarios or tasks
Terminology
• Data
• Information
• Knowledge
What is Knowledge?
• Knowledge is a theoretical or practical understanding of a subject
or a domain. Knowledge is also the sum of what is currently
known, and apparently knowledge is power.
• Those who possess knowledge are called experts.
• Anyone can be considered a domain expert if he or she has deep
knowledge (of both facts and rules) and strong practical experience
in a particular domain. The area of the domain may be limited.
• In general, an expert is a skilful person who can do things other
people cannot.
Acquiring Knowledge
• Knowledge acquisition can be regarded as a method by
which a knowledge engineer gathers information mainly
from experts, but also from text books, technical manuals,
research papers and other authoritative sources for
ultimate translation into a knowledge base,
understandable by both machines and humans.
• The person undertaking the knowledge acquisition, the
knowledge engineer, must convert the acquired
knowledge into an appropriate structured format that a
computer program can utilise.
Acquiring Knowledge
• An important characteristic of knowledge is that it is constantly
changing.
• The lack of documentation and the fact that experts carry a lot of
information in their heads, makes it difficult to gain access to their
knowledge for developing information systems in general and
expert systems in particular.
• Therefore, knowledge engineers have devised specialised
techniques to extract and store this information in an efficient and
expedient manner.
Characteristics of Knowledge Acquisition
• Knowledge acquisition (KA) is a labour and time intensive
process.
• Currently knowledge bases for knowledge based systems are
crafted by hand; this is a severe limitation on the rapid deployment
of such systems.
• Biggest ‘bottleneck’ in system development.
• Most expensive part (money, time & labour).
• Automating KA the ultimate goal.
Players in the Development Team
• There are five members of the expert system development
team:
– the domain expert
– the knowledge engineer
– the programmer
– the project manager
– the end-user.
• The success of their expert system entirely depends on
how well the members work together.
Players in the Development Team
Expert System
Development Team
Project Manager
Domain Expert Knowledge Engineer Programmer
Expert System
End-user
Domain Expert
• The domain expert is a knowledgeable and skilled person capable
of solving problems in a specific area or domain.
• This person has the greatest expertise in a given domain.
• This expertise is to be captured in the expert system.
• Therefore, the expert must:
– be able to communicate his or her knowledge
– be willing to participate in the expert system development
– commit a substantial amount of time to the project.
• The domain expert is the most important player in the expert system
development team.
Knowledge Engineer
• The knowledge engineer is someone who is capable of designing,
building and testing an expert system.
• The knowledge engineer's main tasks are:
– to interview the domain expert to find out how a particular problem is solved.
– to establish what reasoning methods the expert uses to handle facts and rules,
and decide how to represent them in the expert system.
– to choose some development software or an expert system shell, or look at
programming languages for encoding the knowledge.
– responsible for testing, revising and integrating the expert system into the
workplace.
Programmer
• The programmer is the person responsible for the actual
programming, describing the domain knowledge in terms that a
computer can understand.
• The programmer needs to have skills in symbolic programming
such AI languages as LISP, Prolog and OPS5 and also some
experience in the application of different types of expert system
shells.
• In addition, the programmer should know conventional
programming languages like Java, C, Matlab, Pascal, FORTRAN,
etc.
Project Manager
• The project manager is the leader of the expert system
development team, responsible for keeping the project on
track.
• The project manager makes sure that all deliverables and
milestones are met, interacts with the expert, knowledge
engineer, programmer and end-user.
End-User
• The end-user, often called just the user, is a person who
uses the expert system when it is developed.
• The user must not only be confident in the expert system
performance but also feel comfortable using it.
• Therefore, the design of the user interface of the expert
system is also vital for the project’s success; the end-
user’s contribution here can be crucial.
Knowledge and Rules
• The human mental process is internal, and it is too
complex to be represented as an algorithm. However,
most experts are capable of expressing their knowledge in
the form of rules for problem solving.
IF the ‘traffic light’ is green
THEN the action is go
IF the ‘traffic light’ is red
THEN the action is stop
Rules and Knowledge Representation
• The term rule in AI, which is the most commonly used type of
knowledge representation, can be defined as an IF-THEN structure
that relates given information or facts in the IF part to some action
in the THEN part.
• A rule provides some description of how to solve a problem. Rules
are relatively easy to create and understand.
• Any rule consists of two parts:
– the IF part, called the antecedent (premise or condition)
– and the THEN part called the consequent (conclusion or action).
Rules and Knowledge Representation
• A rule can have multiple antecedents joined by the keywords AND
(conjunction), OR (disjunction) or a combination of both.
IF <antecedent 1> IF <antecedent 1>
AND <antecedent 2> OR <antecedent 2>
. .
. .
. .
AND <antecedent n> OR <antecedent n>
THEN <consequent> THEN <consequent>
Rules and Knowledge Representation
• The antecedent of a rule incorporates two parts: an object
(linguistic object) and its value. The object and its value are linked
by an operator.
• The operator identifies the object and assigns the value. Operators
such as is, are, is not, are not are used to assign a symbolic value to
a linguistic object.
• Expert systems can also use mathematical operators to define an
object as numerical and assign it to the numerical value.
OBJECT OPERATOR VALUE
IF ‘age of the customer’ < 18
AND ‘cash withdrawal’ > 1000
THEN ‘signature of the parent’ is required
Rules and Knowledge Representation
• Rules can represent relations, recommendations, directives, strategies and
heuristics:
• Relation
IF the ‘fuel tank’ is empty
THEN the car is dead
• Recommendation
IF the season is autumn
AND the sky is cloudy
AND the forecast is drizzle
THEN the advice is ‘take an umbrella’
• Directive
IF the car is dead
AND the ‘fuel tank’ is empty
THEN the action is ‘refuel the car’
Rules and Knowledge Representation
• Strategy
IF the car is dead
THEN the action is ‘check the fuel tank’;
step1 is complete
IF step1 is complete
AND the ‘fuel tank’ is full
THEN the action is ‘check the battery’;
step2 is complete
• Heuristic
IF the spill is liquid
AND the ‘spill pH’ < 6
AND the ‘spill smell’ is vinegar
THEN the ‘spill material’ is ‘acetic acid’
Knowledge-Based Expert Systems
• In the early seventies, Newell and Simon from Carnegie-Mellon
University proposed a production system model, the foundation of
the modern rule-based expert systems.
• The production model is based on the idea that humans solve
problems by applying their knowledge (expressed as production
rules) to a given problem represented by problem-specific
information.
• The production rules are stored in the long-term memory and the
problem-specific information or facts in the short-term memory.
Production System Model
Long-term Memory Short-term Memory
Production Rule Fact
REASONING
Conclusion
Basic Rule-Based Expert System
Knowledge Base Database
Rule: IF-THEN Fact
Inference Engine
Explanation Facilities
User Interface
User
Structure of a Rule-based Expert System
• The knowledge base contains the domain knowledge
useful for problem solving. In a rule-based expert system,
the knowledge is represented as a set of rules. Each rule
specifies a relation, recommendation, directive, strategy or
heuristic and has the IF (condition) THEN (action)
structure. When the condition part of a rule is satisfied,
the rule is said to fire and the action part is executed.
• The database includes a set of facts used to match against
the IF (condition) parts of rules stored in the knowledge
base.
Structure of a Rule-based Expert System
• The inference engine carries out the reasoning whereby the expert
system reaches a solution. It links the rules given in the knowledge
base with the facts provided in the database.
• The explanation facilities enable the user to ask the expert system
how a particular conclusion is reached and why a specific fact is
needed. An expert system must be able to explain its reasoning and
justify its advice, analysis or conclusion.
• The user interface is the means of communication between a user
seeking a solution to the problem and an expert system.
Common Rule-Based Expert System
External
Database External Program
Expert System
Knowledge Base Database
Rule: IF-THEN Fact
Inference Engine
Explanation Facilities
User Interface Developer
Interface
User
Knowledge Engineer
Expert
Data Pyramid and Computer-Based Systems
IS
Strategy makers apply morals, principles, and Wisdom (experience)
experience to generate policies WBS
Higher management generates knowledge by KBS Knowledge (synthesis)
synthesizing information
Middle management uses reports/info. generated
though analysis and acts accordingly DSS, MIS Information (analysis)
Basic transactions by operational staff TPS Data (processing of raw observations )
using data processing
Volume Sophistication and
complexity
Figure 1: Data pyramid: Managerial perspectives
Data Pyramid and Computer Based Systems
Heuristics
and models
Wisdom
Novelty
Rules Knowledge
Information Experience
Concepts
Data
Raw data through Understanding
fact finding
Researching Absorbing Doing Interacting Reflecting
Figure 2: Convergence from data to intelligence
What is an Expert System (ES)?
• relies on internally represented knowledge to perform
tasks
• utilizes reasoning methods to derive appropriate new
knowledge
• usually restricted to a specific problem domain
• some systems try to capture common-sense knowledge
– General Problem Solver (Newell, Shaw, Simon)
– Cyc (Lenat)
Definitions “Expert System”
• a computer system that emulates the decision-making
ability of a human expert in a restricted domain
[Giarratano & Riley 1998]
• Edward Feigenbaum
– “An intelligent computer program that uses knowledge and
inference procedures to solve problems that are difficult enough
to require significant human expertise for their solutions.”
[Giarratano & Riley 1998]
• the term knowledge-based system is often used
synonymously
Characteristics of an Expert System
• An expert system is built to perform at a human expert level in a
narrow, specialised domain. Thus, the most important
characteristic of an expert system is its high-quality performance.
• No matter how fast the system can solve a problem, the user will
not be satisfied if the result is wrong!
• On the other hand, the speed of reaching a solution is very
important. Even the most accurate decision or diagnosis may not be
useful if it is too late to apply, for instance, in an emergency, when a
patient dies or a nuclear power plant explodes.
Characteristics of an Expert System
• Expert systems apply heuristics to guide the reasoning
and thus reduce the search area for a solution.
• A unique feature of an expert system is its explanation
capability. It enables the expert system to review its own
reasoning and explain its decisions.
• Expert systems employ symbolic reasoning when solving
a problem. Symbols are used to represent different types
of knowledge such as facts, concepts and rules.
Characteristics of an Expert System
• We should be aware that an expert is only a human and thus can
make mistakes, and therefore, an expert system built to perform at
a human expert level also should be "allowed" to make mistakes.
• In expert systems, knowledge is separated from its processing
(knowledge base and inference engine are split up). A conventional
program is a mixture of knowledge and the control structure to
process this knowledge.
• When an expert system shell is used, a knowledge engineer or an
expert simply enters rules in the knowledge base. Each new rule
adds some new knowledge and makes the expert system smarter.
Expert Systems Comparison
Human Experts Expert Systems Conventional Programs
Use knowledge in the Process knowledge Process data and use
form of rules of thumb or expressed in the form of algorithms, a series of
heuristics to solve rules and use symbolic well-defined operations,
problems in a narrow reasoning to solve to solve general numerical
domain. problems in a narrow problems.
domain.
In a human brain, Provide a clear Do not separate
knowledge exists in a separation of knowledge knowledge from the
compiled form. from its processing. control structure to
process this knowledge.
Capable of explaining a Trace the rules fired Do not explain how a
line of reasoning and during a problem-solving particular result was
providing the details. session and explain how a obtained and why input
particular conclusion was data was needed.
reached and why specific
data was needed.
Expert Systems Comparison
Human Experts Expert Systems Conventional Programs
Use inexact reasoning and Permit inexact reasoning Work only on problems
can deal with incomplete, and can deal with where data is complete
uncertain and fuzzy incomplete, uncertain and and exact.
information. fuzzy data.
Can make mistakes when Can make mistakes when Provide no solution at all,
information is incomplete data is incomplete or or a wrong one, when data
or fuzzy. fuzzy. is incomplete or fuzzy.
Enhance the quality of Enhance the quality of Enhance the quality of
problem solving via years problem solving by problem solving by
of learning and practical adding new rules or changing the program
training. This process is adjusting old ones in the code, which affects both
slow, inefficient and knowledge base. When the knowledge and its
expensive. new knowledge is processing, making
acquired, changes are changes difficult.
easy to accomplish.
Main Components of an ES
User
Expertise
Knowledge Base
Facts / Information User Interface
Expertise
Inference Engine
Developer
Components of KBS
Knowledge base is a repository of
domain knowledge and Enriches the
metaknowledge.
system with
Inference engine is a software program self-learning
that infers the knowledge available in capabilities
the knowledge base.
Knowledge Inference
Explanation base engine
Self-
and
learning
reasoning
User interface
Provides
explanation and
reasoning Friendly
facilities interface to
users
working in
their native
language
Figure 4: General structure of KBS
Main ES Components
• knowledge base
– contains essential information about the problem domain
– often represented as facts and rules
• inference engine
– mechanism to derive new knowledge from the knowledge base
and the information provided by the user
– often based on the use of rules
• user interface
– interaction with end users
– development and maintenance of the knowledge base
General Concepts and Characteristics
of ES
• knowledge acquisition
– transfer of knowledge from humans to computers
– sometimes knowledge can be acquired directly from the environment
• machine learning
• knowledge representation
– suitable for storing and processing knowledge in computers
• inference
– mechanism that allows the generation of new conclusions from existing
knowledge in a computer
• explanation
– illustrates to the user how and why a particular solution was generated
Development of ES Technology
• strongly influenced by cognitive science and mathematics
– the way humans solve problems
– formal foundations, especially logic and inference
• production rules as representation mechanism
– IF … THEN type rules
– reasonably close to human reasoning
– can be manipulated by computers
– appropriate granularity
• knowledge “chunks” are manageable both for humans and for
computers
Rules and Humans
• rules can be used to formulate a theory of human
information processing (Newell & Simon)
– rules are stored in long-term memory
– temporary knowledge is kept in short-term memory
– sensory input or thinking triggers the activation of rules
– activated rules may trigger further activation
– a cognitive processor combines evidence from currently active
rules
• this model is the basis for the design of many rule-based
systems
– also called production systems
Early ES Success Stories
• DENDRAL
– identification of chemical constituents
• MYCIN
– diagnosis of illnesses
• PROSPECTOR
– analysis of geological data for minerals
– discovered a mineral deposit worth $100 million
• XCON/R1
– configuration of DEC VAX computer systems
– saved lots of time and millions of dollars
The Key to ES Success
• convincing ideas
– rules, cognitive models
• practical applications
– medicine, computer technology, …
• separation of knowledge and inference
– expert system shell
• allows the re-use of the “machinery” for different domains
• concentration on domain knowledge
– general reasoning is too complicated
When (Not) to Use ESs
• expert systems are not suitable for all types of domains
and tasks
– conventional algorithms are known and efficient
– the main challenge is computation, not knowledge
– knowledge cannot be captured easily
– users may be reluctant to apply an expert system to a critical
task
ES Tools
• ES languages
– higher-level languages specifically designed for knowledge
representation and reasoning
– SAIL, KRL, KQML, DAML, OWL (Web Ontology Language)
• ES shells
– an ES development tool/environment where the user provides
the knowledge base
– CLIPS, JESS, Mycin, Babylon, G2, ...
Related Developments
• Semantic Web
– extension of the World Wide Web
– includes knowledge representation and reasoning capabilities
• Decision Support Systems
– less emphasis on autonomy
• Data Mining
– extraction of knowledge from large quantities of data
• Sensemaking
– computer support for quicker, easier understanding of complex
domains or situations
ES Elements
• knowledge base
• inference engine
• working memory
• agenda
• explanation facility
• knowledge acquisition facility
• user interface
ES Structure
Knowledge Base
Knowledge
Acquisition
Facility
User Interface
Inference Engine Agenda
Explanation
Facility
Working Memory
Rule-Based ES
• knowledge is encoded as IF … THEN rules
– these rules can also be written as production rules
• the inference engine determines which rule antecedents
are satisfied
– the left-hand side must “match” a fact in the working memory
• satisfied rules are placed on the agenda
• rules on the agenda can be activated (“fired”)
– an activated rule may generate new facts through its right-hand
side
– the activation of one rule may subsequently cause the activation
of other rules
Example Rules
IF … THEN Rules antecedent
(left-hand-side)
Rule: Red_Light
IF the light is red
THEN stop
consequent
Rule: Green_Light (right-hand-side)
IF the light is green
THEN go
Production Rules antecedent (left-hand-side)
the light is red ==> stop
consequent
(right-hand-side)
the light is green ==> go
MYCIN Sample Rule
Human-Readable Format
IF the stain of the organism is gram negative
AND the morphology of the organism is rod
AND the aerobiocity of the organism is gram anaerobic
THEN the there is strongly suggestive evidence (0.8)
that the class of the organism is enterobacteriaceae
MYCIN Format
IF (AND (SAME CNTEXT GRAM GRAMNEG)
(SAME CNTEXT MORPH ROD)
(SAME CNTEXT AIR AEROBIC)
THEN (CONCLUDE CNTEXT CLASS ENTEROBACTERIACEAE
TALLY .8)
Inference Engine Cycle
• describes the execution of rules by the inference engine
– conflict resolution
• select the rule with the highest priority from the agenda
– execution
• perform the actions on the consequent of the selected rule
• remove the rule from the agenda
– match
• update the agenda
– add rules whose antecedents are satisfied to the agenda
– remove rules with non-satisfied agendas
• the cycle ends when no more rules are on the agenda, or when an
explicit stop command is encountered
Forward and Backward Chaining
• different methods of rule activation
– forward chaining (data-driven)
• reasoning from facts to the conclusion
• 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
• often used for real-time expert systems in monitoring and
control
• examples: CLIPS, OPS5
– backward chaining (query-driven)
• starting from a hypothesis (query), supporting rules and facts
are sought until all parts of the antecedent of the hypothesis
are satisfied
Foundations of Expert Systems
Rule-Based Expert Systems
Inference Engine Knowledge Base
Pattern
Conflict Facts Rules
Matching
Resolution
Post
Rete
Production
Algorithm Action Rules
Execution
Markov
Algorithm
Post Production Systems
• production rules were used by the logician Emil L. Post in
the early 40s in symbolic logic
• Post’s theoretical result
– any system in mathematics or logic can be written as a
production system
• basic principle of production 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
ES Advantages
• economical
– lower cost per user
• availability
– accessible anytime, almost anywhere
• response time
– 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
ES Problems
• limited knowledge
– “shallow” knowledge
• no “deep” understanding of the concepts and their relationships
– no “common-sense” knowledge
– no knowledge from possibly relevant related domains
– “closed world”
• the ES knows only what it has been explicitly “told”
• it doesn’t know what it doesn’t know
• mechanical reasoning
– may not have or select the most appropriate method for a particular
problem
– some “easy” problems are computationally very expensive
• lack of trust
– users may not want to leave critical decisions to machines
Summary Introduction
• expert systems or knowledge based systems are used to represent
and process in a format that is suitable for computers but still
understandable by humans
– If-Then rules are a popular format
• the main components of an expert system are
– knowledge base
– inference engine
• ES can be cheaper, faster, more accessible, and more reliable than
humans
• ES have limited knowledge (especially “common-sense”), can be
difficult and expensive to develop, and users may not trust them for
critical decisions
Try these Exercises
Check Sakai for Expert System Exercise using the
KnowledgeWright
Reference
Ertel, W., & Black, N. T. (2011). Introduction to
Artificial Intelligence. Berlin: Springer.
Acknowledgement
