AI - Lecture - Expert Systems

Source: Lecture 18 on Expert Systems

Expert systems (also known as knowledge-based systems, knowledge-based decision support systems, or rule-based systems) are computer systems designed to emulate the reasoning of a human expert in a specific domain. They constitute one of the classical applications of knowledge-based Artificial Intelligence (see AI - Lecture - Introduction and Agents and AI - Lecture - Logical Agents, Propositional Logic).

To emulate human expert reasoning, an expert system relies on three core elements:

Domain knowledge: specialist knowledge, usually provided by human experts, explicitly represented in a knowledge base.
Symbolic rules: often expressed in an IF-THEN format.
An inference mechanism: that applies rules to known facts to derive conclusions or recommendations.

Rather than replacing human experts, expert systems function as decision support systems to provide expert-level advice, diagnosis, classification, or decision support.

Foundations and Motivations

Expert systems emerged in the 1970s and saw widespread industrial application during the 1980s. They were developed to overcome the limitations of early general problem-solving systems:

General-purpose reasoning mechanisms were too weak to solve complex problems in real-world domains.
High performance in a specific task depends primarily on domain-specific knowledge rather than general reasoning procedures.
Domain knowledge can be separated from the general reasoning mechanism.

By separating the domain knowledge from the inference process, developers could encode expert knowledge explicitly in the form of rules, leaving the reasoning engine independent of the specific application domain.

Problem Domain vs. Knowledge Domain

An expert system does not attempt to model an entire academic or professional field. Instead, it models the knowledge required for a specific class of problems:

Problem Domain: The broad area in which the system is expected to solve problems (e.g., medical diagnosis, financial risk assessment, engineering).
Knowledge Domain: The specific, encoded expert knowledge within the system.

The knowledge domain is a subset of the problem domain ().

Typical Application Domains

Expert systems are deployed in domains where decisions rely on explicit, rule-based expert knowledge.

Typical application areas include:

Medical diagnosis and clinical decision support
Technical support and help-desk systems
Finance and risk assessment
Fault diagnosis and maintenance
Configuration and planning
Classification tasks, such as geological, botanical, or materials identification
Software engineering support, including design rules and code analysis

General Characteristics of Expert Systems

The characteristics of expert systems are grouped into aspects of knowledge representation and operational usability.

Knowledge and Reasoning

Symbolic representation: Domain knowledge is explicitly structured using representations such as rules, decision trees, frames, or ontologies.
Specialized domain: Focus is restricted to narrow, well-defined problem areas.
Separation of knowledge from inference: The knowledge base contains the domain expertise, while the inference engine applies reasoning strategies.

Performance and Usability

High-quality performance: The system must deliver accurate and reliable conclusions.
Timely answers: The reasoning process must produce results within operational deadlines, as late answers are often useless.
Explanation capability: The system can explain the reasoning steps and justifications for its conclusions.
Maintainability: The rules and knowledge base can be updated as the domain evolves.

Designing the Knowledge Base of an Expert System

The design and maintenance of an expert system involve two primary roles:

Domain Expert: Provides specialist knowledge and heuristic insight about the application domain.
Knowledge Engineer: Elicits, structures, and encodes the expert’s knowledge into the system.

The main design issues in building a knowledge base include representing case-specific facts in the working memory, encoding general domain knowledge in the rule base, choosing suitable data structures for rules and facts, and ensuring that the knowledge base remains maintainable.

Core Architecture


graph TD
    User([User]) <--> UI[User Interface]
    
    subgraph KB ["Knowledge Base"]
        WM["Facts (Working Memory)"]
        RM["Rules (Rule Memory)"]
    end
    
    DomainExpert["Domain Expert"] --> KE["Knowledge Engineer"]
    KE --> KB
    
    UI <--> WM
    UI <--> IE[Inference Engine]
    KB <--> IE
    IE --> EM[Explanation Module]
    EM --> UI

The system architecture consists of several key components:

Knowledge Base: The long-term memory containing domain rules, facts, heuristics, and constraints. See Knowledge Base.
Working Memory: The short-term memory containing case-specific facts about the current problem instance. It updates dynamically during inference. These facts can be provided directly by the user, obtained as answers to questions, loaded from external data sources, or derived during inference. To allow matching, facts must use the same representation format as the rules in the rule base.
Inference Engine: The reasoning component (or rule interpreter) that matches rule conditions against facts in the working memory and decides which rules to fire. It links the rule base and working memory to derive new conclusions.
User Interface: Manages interaction between the user and the system, enabling the user to enter facts, answer queries, submit goals, and receive conclusions, recommendations, and explanations. It connects the user to the working memory, question base, inference engine, and explanation facility in various forms, such as question-answer dialogues, menu-driven interfaces, graphical user interfaces, or natural-language interfaces.
Knowledge Base Editor (Knowledge Acquisition Facility): Supports the creation and maintenance of the knowledge base. It helps knowledge engineers and experts add rules and facts, edit existing knowledge, check consistency and syntax, document rule meanings, and update the knowledge base as the domain changes. Its goal is to simplify knowledge acquisition and reduce low-level coding.
Explanation Facility (Justifier): Explains the reasoning process to the user to improve trust, validation, and debugging. It answers specific operational questions:
- How was a conclusion reached? (which rules fired, which facts were used, and what intermediate conclusions were derived).
- Why is a fact or question needed? (which rule requires the fact and which goal it helps to prove).
- Why not another conclusion? (what required facts were missing and which rules failed to fire).

Knowledge Representation with Rules

In classical expert systems, knowledge is represented using IF-THEN rules.

Rule Form

A rule has the basic form:

The IF part is the antecedent (premise or condition). The THEN part is the consequent (conclusion, action, result, or consequent).

Rules examples

A simple rule:

A biomedical rule:

Characteristics of Rules

Characteristic	First Part (IF / Antecedent)	Second Part (THEN / Consequent)
Alternative Names	Premise, antecedent, condition, situation	Conclusion, consequence, action, consequent
Nature	Usually declarative conditions	Often procedural effect
Size	Often contains several conditions	Usually only one conclusion
Logical Statement	Conjoined by AND (all must be true for conclusion to be true) or OR (any condition makes conclusion true)	Defines the resulting conclusion, action, or relation

Rules can be formulated using different logical structures:

Antecedents: Specify the conditions that must be true for the rule to apply. In many systems, conditions are conjoined with AND, matching the structure of Horn clauses: General logical expressions containing OR can also be used. Rules containing OR in the antecedent () are often split into separate rules (, , ) to simplify pattern matching.
Consequents: Define the output when conditions are met. A consequent can express:
- Relations (e.g., )
  - Recommendations (e.g., )
  - Directives / Actions (e.g., )
  - Strategies (suggesting the next procedural step, e.g., )
  - Heuristics (expert judgment based on experience, e.g., )

Expressions and Relations

Simples rules with relations

Rules can include can include comparison operators (), such as:
These rules compare attribute values with constants (e.g., ).
They are still essentially propositional or attribute–value rules. Instead, simple attribute–value rules cannot easily express relationships between entities. These require a more expressive representation such as propositional logic rules.

Relations between attributes

Rules may compare two attributes of the same object:

This representation generalizes better than fixed thresholds but is computationally expensive to search. A simple alternative is to define a derived attribute (e.g., ).

Rules as Knowledge Base

Rule-based knowledge bases can be executed in two main ways:

Ordered rule sets: The engine evaluates rules in a fixed order (often called a decision list). The order of the rules is part of the system’s meaning, and the first matching rule determines the outcome.
Unordered rule sets: Evaluated without a fixed order. Multiple rules can be applicable simultaneously, requiring a conflict-resolution strategy to decide which to fire.

Rules as Knowledge Base: Default Rules A default rule is a fallback used when no more specific rule applies. Examples include:

Operational default:
Entity default:

First Order Rules

First-order rules: Explicitly represent relationships between distinct entities using variables:

These require first-order logic representations (see AI - Lecture - First Order Logic or Predicate Logic).

Rule Inference

Rule-based expert systems mainly use two inference strategies:

Forward Chaining: The system matches rule antecedents against facts in the working memory. A rule is activated if its conditions match the known facts. For example, given the rule , if the working memory contains , the rule is activated.
Backward Chaining: The system matches the current goal against rule consequents. If a rule can conclude the goal, its antecedents become new subgoals.

See Forward Chaining in FOL and Backward Chaining in FOL, similarly also in Propositional Logic.

There is no universally best strategy: the choice depends on the application

Rule Matching

Rule matching determines which rules are applicable in the current situation. A rule is activated when its conditions match the facts in working memory.

In forward chaining:

The system matches “rule antecedents against working memory” e.g. “IF fever cough THEN suspect_flu”
If working memory contains fever, cough then the rule is activated

In backward chaining:

The system matches: rules consequents against current goal
If a rule can conclude the goal, its antecedents become subgoals

Conflict Set and Rule Firing

Matching may activate several rules at the same time. The set of activated rule instances is called the conflict set. The inference engine must choose one rule using a conflict resolution strategy.

After a rule is selected, it is fired that means the consequent of the selected rule is executed.

In forward chaining, firing usually adds a new fact to working memory.

Knowledge Base

The knowledge base contains long-term domain knowledge.

Main elements:

Rule Base: IF–THEN rules that capture domain expertise
Fact Base: general facts that do not change frequently. May reference external databases or domain values.
Question Base: questions used to acquire missing case-specific facts from the user.

Case-specific facts are stored separately in working memory. They may be:

Provided by the user
Obtained as answers to questions
Loaded from data sources
Derived during inference

Rule base

Rule Base: A set of IF-THEN rules capturing domain expertise.

It is usually:

A largely unordered set of rules
Non-redundant, when possible
Developed for a specific task or domain
Composed of IF-THEN rules

For real-world problems, a rule base may contain hundreds or thousands of rules.

Example rule:

Handling OR Conditions in the Rule Base If a rule contains OR in the antecedent: , it can be rewritten as separate rules:

This makes rule matching simpler.

Fact Base

Fact Base: General, relatively static facts that do not change frequently (which may reference external databases or domain values).

Facts assign values to propositions, attributes, or predicates.

Examples:

𝑠𝑜𝑛_𝑜𝑓(𝑠𝑡𝑒𝑣𝑒,𝑗𝑜𝑒)
𝑠𝑜𝑛_𝑜𝑓(𝑏𝑖𝑙𝑙, 𝑑𝑎𝑣𝑒)

Facts must use the same representation used in the rule base, so that the inference engine can match facts with rule conditions.

Example Rule:

From the antecedent the system can infer the fact that

Question Base

Question Base: an unordered set of dynamic queries used during inference to acquire missing case-specific facts from the user. It is designed to provide a more natural, human-like user interaction.

It supports three response types:

Boolean: Yes/No, True/False.
Selection: Multiple-choice (single-select or multi-select).
Open Input: Primitive data types (integer, float, or text).

The user’s answers are added to working memory and may activate new rules.

Example

Rule/Predicate: ans)$
Prompt: Who is your father?
Response Type: (single choice)
1. Joe
2. Steve
3. Bill
4. Dave
5. I don’t know

The Inference Engine and Chaining

See also

There is a deep connection between inference in this note and in logic, see:

Forward chaining and Backward chaining for Propositional logic

Forward Chaining and Backward chaining for First Order Logic See at the end of this note

Rule-Based Expert Systems

Rules are the most common representation in classical expert systems. A typical rule has the form:

where are the antecedents and is the consequent

The inference engine matches rule antecedents against facts in working memory. The activation of one rule may enable the activation of other rules.

Inference Engine

The inference engine executes rules by matching rule conditions against facts in working memory. Its main functions are:

Match: Find all rules whose antecedents match facts in the working memory. Pattern matching is the search step of the inference engine. Because matching many rules against many facts is computationally expensive, activated rule instances are placed on a prioritized list called the agenda (or conflict set).
Identify applicable rules
Resolve: Select which rule to fire
Execute: fire the selected rule, executing its consequent.
Add new facts or conclusions to working memory
Ask the user for missing information when needed.

It links: 𝑅𝑢𝑙𝑒 𝐵𝑎𝑠𝑒 + 𝑊𝑜𝑟𝑘𝑖𝑛𝑔 𝑀𝑒𝑚𝑜𝑟𝑦 → 𝑁𝑒𝑤 𝐶𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛

This cycle is repeated continuously using the following execution loop:

while there is at least one activated rule do:
    select one active rule (using conflict resolution strategies)
    fire the selected rule
    execute the actions of the selected rule
    update the working memory

Inference Engine Components

The inference engine can be expressed with the following cycle:

Match: find rules whose antecedents match facts in working memory
Resolve: choose one rule from the conflict set
Act: fire the selected rule and execute its consequent

The result updates the working memory.

Variable Binding

During rule matching, variables in rules acquire values. This process is called variable binding.

A rule may contain variables in both the antecedent and the consequent.

Given the rule: If the working memory contains , the engine matches under forward chaining. This establishes the bindings: Upon firing, the instantiated consequent is executed, adding to the working memory.

Once a variable is bound, the binding is applied consistently across all occurrences of that variable in the rule instance. Substituting variables with their bindings is called instantiation.

In forward chaining, the instantiated consequent is added to working memory.
In backward chaining, variable bindings are often temporary while the system attempts to prove a subgoal.

Inference Strategies

Inference engines employ two primary reasoning strategies. The choice depends on the application, as there is no universally best strategy.

Feature	Forward Chaining	Backward Chaining
Reasoning Type	Data-driven reasoning	Goal-driven reasoning
Starting Point	Known facts in the working memory	A user-entered goal or hypothesis
Matching Direction	Matches rule antecedents against known facts	Matches the goal against rule consequents
Derived Action	Fires rules to derive new facts	Creates subgoals from rule antecedents
Termination	Continues until no rule applies or a goal is reached	Continues until the goal is proved or fails

Conflict Resolution Strategies

Conflict Resolution: pattern matching may activate more than one rule instance.

The activated rules are placed on the agenda, also called the conflict set. When several rules are applicable, the inference engine must decide which rule should fire next. This decision is called conflict resolution.

Common resolution strategies include:

Rule order: Selects the first matching rule according to its order in the rule base. This strategy is simple to implement and useful for ordered rule sets or decision lists, but its selections can be arbitrary in large rule bases.
Specificity: Selects the most specific rule (the one with the most restrictive conditions). For example, is more specific than ; if both rules match, the engine fires .
Lexical order: Selects rules based on alphabetical or dictionary order. This is simple but arbitrary, and is useful only when no better priority criterion is available.
Importance or Priority: Rules are defined with explicit priority scores, and the engine fires the rule with the highest score. However, this strategy is generally discouraged because setting up priority scores precisely is difficult in large rule bases.
- Example:
  - Rule A:
  - Rule B:
Recency: Prioritizes rules matching facts (or containing antecedents) that were most recently added or modified. This strategy requires time tags on facts or rule activations, and is useful when newly derived facts indicate the current reasoning direction.
Refactoriness: Prevents the same rule instance from firing repeatedly on the exact same variable bindings.

Act Phase - Executing the Consequent

Once a rule instance has been selected from the agenda, it fires. The consequent may:

add new facts to working memory
modify or remove existing facts
trigger an external action or recommendation.

After firing: the rule instance is removed from the agenda, working memory is updated, the inference cycle starts again.

The cycle stops when:

no more rules are applicable
a goal has been reached
an explicit stop condition is encountered.

Forward Chaining Walkthroughs

Forward chaining with rules starts from the facts currently stored in working memory and repeatedly applies rules.

Algorithm:

Match rule antecedents against current facts
Select and fire an applicable rule
Add the derived fact to working memory
Repeat until:
- no new facts can be derived
- a goal is reached
- a stop condition is met

Goal: Prove
Initial Working Memory:

The forward chaining execution proceeds in cycles:

Cycle 1:
- Match: The antecedents of Rule 3 (requires ) and Rule 4 (requires ) match the initial facts.
- Conflict Set: .
- Resolve/Act: The engine selects and fires Rule 3, adding to working memory.
- New Working Memory: .
Cycle 2:
- Match: The antecedents of Rule 4 (requires ) and Rule 2 (requires ) match.
- Conflict Set: .
- Resolve/Act: The engine selects and fires Rule 2, adding to working memory.
- New Working Memory: .
Cycle 3:
- Match: The antecedents of Rule 4 (requires ) and Rule 1 (requires ) match.
- Conflict Set: .
- Resolve/Act: The engine selects and fires Rule 1, adding to working memory.
- Result: The goal is added to working memory. The execution terminates successfully.

Forward chaining produces a chain of derived facts:

Backward Chaining Walkthrough

Backward Chaining with rules starts from a goal and works backward to find supporting facts.

Algorithm:

Start with a goal to prove
Check whether the goal is already in working memory
If not, find rules whose consequent matches the goal
Treat the antecedents of those rules as new subgoals
Repeat until:
- all subgoals are supported by known facts; or
- no rule or fact can support some subgoal

The backward chaining execution proceeds by setting subgoals recursively:

Pass 1: The initial goal is . Since is not in the working memory, the engine searches for rules concluding . It finds Rule 1 (). To prove , the engine establishes and as new subgoals.
Pass 2: Subgoal is matched against working memory and is immediately satisfied (since is an initial fact). The engine then addresses subgoal . Since is not in the working memory, it searches for rules concluding and finds Rule 2 (). The antecedents , , and become the next subgoals.
Pass 3: Subgoals and are matched against working memory and are satisfied (initial facts). The engine addresses subgoal . Since is not in the working memory, it searches for rules concluding and finds Rule 3 (). The antecedent becomes a subgoal.
Pass 4: Subgoal is matched against working memory and is satisfied (initial fact).
Pass 5: Since the condition is satisfied, Rule 3 fires, and is added to working memory, satisfying the subgoal .
Pass 6: Since subgoals , , and are satisfied, Rule 2 fires, and is added to working memory, satisfying the subgoal .
Pass 7: Since subgoals and are satisfied, Rule 1 fires, adding to working memory. The goal is proven.

Query Failures and Loop Prevention

Negation as Failure

In a rule-based systems we assume the closed-world assumption: a query fails if it cannot be proved from the available facts. This principle is also called negation as failure.

However, failure to prove does not equal proof of falsehood (). A query failure may also mean that:

The fact base is incomplete.
The rule base is incomplete.
The required information was not asked or provided.
The system reached a search or time limit.

Loop Prevention

Backward chaining is susceptible to infinite search loops when rules contain cyclic dependencies. For example, if the rule base contains: To prove , the system tries to prove , which requires proving , leading to an infinite search.

To prevent infinite loops, inference engines employ termination criteria:

Remembering visited goals.
Enforcing a maximum search depth.
Implementing time limits.
Defining explicit failure conditions.

Mixed Chaining

Combines both strategies. It starts with forward chaining to derive initial conclusions, switches to backward chaining to prove a specific hypothesis, asks the user for missing facts if necessary, and returns to forward chaining once new facts are added.

Mixed chaining is useful when many facts are available but a specific goal must be tested, when the system must both explore conclusions and verify hypotheses, or when user interaction is required to complete missing information.

Expert System Shells and CLIPS

An expert system shell is a software environment that provides the generic reasoning infrastructure so that developers only need to supply the domain-specific knowledge:

A shell simplifies development because the reasoning infrastructure is already available. It provides generic components such as:

Inference engine
User interface
Explanation facility
Knowledge base editor
Rule language or knowledge representation format

Common expert system shells include CLIPS, PyCLIPS, PyKE, Knowledge Pro, Jess, Drools, and Prolog-based shells.

CLIPS (C Language Integrated Production System)

CLIPS is one of the most widely used expert system shells (see clipsrules.net):

Origin: Developed by NASA’s Johnson Space Center (1985-1996); currently maintained independently as public-domain, free, open-source software.
Portability: Written entirely in C, making it highly portable and easy to embed or interface with other programming languages.
Features:
- Inference Engine: Employs a forward-chaining rule engine using pattern matching.
- Paradigm Support: Rule-based programming (built on facts and production rules), procedural programming (native support), and object-oriented programming (extended via the CLIPS Object-Oriented Language, COOL).

Additional Insights - Expert Systems vs Propositional/First Order Logic

Relevant notes:

In propositional logic, inference is defined semantically: a conclusion is valid if it holds in all models of the knowledge base. Mechanisms such as model checking or resolution are just procedures that try to approximate or guarantee this semantic condition.

In expert systems, inference is operational: it is the controlled execution of rules over a changing working memory. The system is not primarily checking model validity but evolving a state until a goal is reached or no rules apply.

So logical inference is model-oriented. Expert system inference is state-transition-oriented.

Core computational object In propositional logic inference, the core object is the set of models or the syntactic structure of formulas. Even when using resolution, the system manipulates clauses as logical objects whose correctness is guaranteed by soundness with respect to models.

In expert systems, the core object is the working memory. It is a dynamic set of facts that changes after each rule firing. Inference is therefore a sequence of state updates rather than a proof over static sentences.

This difference is crucial: logic explores truth conditions; expert systems evolve a database of facts.

Forward chaining In propositional logic, forward chaining appears mainly in Horn-clause fragments. It starts with known facts, apply Modus Ponens repeatedly and then derive all the reachable consequences. It is monotonic: once a fact is derived, it remains true. The process converges to a closure of the knowledge base under entailment.

In expert systems, forward chaining is a production system cycle:

match → resolve → fire → update working memory.

Key differences are:

in expert systems rules are continuously re-evaluated after each update
There is a conflict set (agenda)
Control strategies decide which rule fires next
Facts may trigger actions, not only logical conclusions

So while logically it still resembles Horn closure computation, operationally it is an event-driven system reacting to changes in state.

Backward chaining In propositional logic, backward chaining starts from a query, reduce it into subgoals and then recursively prove subgoals using rules. It is equivalent to depth-first search in a proof space (often AND-OR structure in Horn logic).

One note (and difference with forward chaining) is that it does not change the knowledge base; it only searches for a derivation.

In expert systems, backward chaining is also goal-driven but it is integrated with interaction and working memory:

goal activates rules whose consequents match it
subgoals are generated from antecedents
missing facts may trigger user questions
bindings are maintained dynamically

So in expert systems, backward chaining is a query-driven interaction mechanism with possible data acquisition.

It is also useful to consider the following differences.

Control strategy

In logical inference, control is implicit, the choice of clauses affects efficiency but not meaning.
In expert systems control is explicit and essential, it consider explicitly: rule order, specificity, recency, priority and so on. Changing control strategy changes the system behaviour even if the rule base is identical.

The output:

In logical inference the output is truth value or proof of entailment (epistemic, about truth)
in expert systems the output is an action, recommendation or derived fact in working memory. (procedural, what to do)

Obsidian + 🪴 Quartz 4.0

Explorer

AI - Lecture - Expert Systems

AI - Lecture - Expert Systems

Foundations and Motivations

Problem Domain vs. Knowledge Domain

Typical Application Domains

General Characteristics of Expert Systems

Knowledge and Reasoning

Performance and Usability

Designing the Knowledge Base of an Expert System

Core Architecture

Knowledge Representation with Rules

Rule Form

Characteristics of Rules

Expressions and Relations

Simples rules with relations

Relations between attributes

Rules as Knowledge Base

First Order Rules

Rule Inference

Rule Matching

Conflict Set and Rule Firing

Knowledge Base

Rule base

Fact Base

Question Base

The Inference Engine and Chaining

Rule-Based Expert Systems

Inference Engine

Inference Engine Components

Variable Binding

Inference Strategies

Conflict Resolution Strategies

Act Phase - Executing the Consequent

Forward Chaining Walkthroughs

Backward Chaining Walkthrough

Query Failures and Loop Prevention

Negation as Failure

Loop Prevention

Mixed Chaining

Expert System Shells and CLIPS

CLIPS (C Language Integrated Production System)

Additional Insights - Expert Systems vs Propositional/First Order Logic

Graph View

Table of Contents

Backlinks