Rule-Based Production Systems

• Production systems are rule-based and rely on IF... THEN... rules.
• Production systems consist of three components: production rules, working memory, and control structure.
• Production rules are condition-action pairs in the format "IF condition THEN action" that represent problem-solving knowledge.
• Working memory contains a description of the current state of problem-solving.
• The control structure implements search, enabling the production system to progress toward a goal within the rules. It is also called an interpreter or recognize-act cycle.

Production System Types

• Production systems are forward chaining and backward chaining.
• Forward chaining starts with initial facts and applies rules to draw new conclusions (or take actions). They are data-driven.
• Backward chaining begins with a hypothesis (or goal) and seeks rules to prove it, setting subgoals as needed, and are goal-driven.

Rule-Based Systems

• Rule-based systems consist of IF-THEN rules, facts, and an interpreter for applying rules.
• An expert system encodes knowledge into rules and performs similarly to an expert when exposed to the same data.
• These systems are simple models adaptable for various problems, but require knowledge to be expressed as if-then rules.
• Large sets of rules can make expert systems inefficient.

Elements of a Rule-Based System

• Rule-based systems consist of facts, rules, and a termination criterion.
• Facts are assertions relevant to the system's initial state.
• Rules contain all actions to be taken within the scope of a problem, specifying how to act on the assertion set and relate facts in the IF part to actions in the THEN part.
• Systems must only contain relevant rules, as the number of rules affects performance.
• A termination criterion is a condition that determines when a solution is found or doesn't exist, this is needed to prevent infinite loops.

Rules

• Rules contain an IF part (antecedent/premise/condition) and a THEN part (consequent/conclusion/action).
• A simple rule is expressed as "IF antecedent THEN consequent".
• The rule tests the logical expression in the premise and asserts a fact if the expression is true.
• General rules can have multiple antecedents joined by logical operators such as AND and OR.
• The antecedent of a rule has two parts: an object (linguistic object) and the object's value.

Forward Chaining Systems

• Forward chaining generates facts until the goal is attained, working from the beginning facts.
• IF parts of each rule is matched against the facts in working memory.
• Conflict resolution is used to select a rule to apply when multiple rules can be used (fire).
• Add new obtained facts to the working memory after the rule is applied.
• The system stops when the conclusion is added to working memory or a rule specifies to end.

Forward Chaining Example

• Expert system database includes facts A, B, C, D, and E, with rules provided.
• Rule 1: IF A and C are true, THEN B is true.
• Rule 2: IF C and D are true, THEN F is true.
• Rule 3: IF C, D, and E are true, THEN X is true.
• Rule 4: IF A, B, and X are true, THEN Y is true.
• Rule 5: IF D and Y are true, THEN Z is true.
• The database consists of facts A, B, C, D, and E, along with the knowledge base of five rules, to reach conclusion Z by forward chaining.
• First, fire an unfired rule when multiple rules can fire at a time.

Cycle 1

• Match IF parts of each rule against facts in working memory where rules 1, 2, and 3 are selected in the database.
  • Rule 1: IF A AND C THEN B
  • Rule 2: IF C AND D THEN F
  • Rule 3: IF C AND D AND E THEN X
• Rules 4 and 5 are not selected with unmatched IF parts
• Use Rule 1 since it can be applied and was not applied previously.

Cycle 2

• Rules 1, 2, and 3 follow the same rules as Cycle 1.
• Rule 2 is then selected since Rule 1 was already fired.
• F, which is not in the database, will be added.
• The database is now A, B, C, D, E, F.

Cycle 3

• Since Rules 1 and 2 are already fired, only Rule 3 will be selected.
• X is not in the database and will be added.

Cycle 4

• The database facts are A, B, C, D, E, F, and X, where the first four rules match.
• Only Rule 4 is selected to fire, since the first 3 rules are already fired.
  • Rule 4: IF A AND B AND X THEN Y
• Term Y is then added to the database.

Cycle 5

• Rule 5: IF D AND Y THEN Z is selected for use with all IF conditions that match.
• New fact, Z is obtained and represents the conclusion, ending the process.

Data-Driven Inference

• Forward chaining or data-driven inference matches rule premises (IF parts) and performs actions (THEN parts).
• The process updates the knowledge base or working memory until no more rules can be applied or until a cycle limit is met.

Disadvantages of Forward Chaining

• Determining which applicable rule to apply at each stage.
• Lacking a goal for the entire process where the stop time is unknown.

Backward Chaining Systems

• A hypothesis is stated. The system must find evidence to prove it. If that doesn't occur, start again with a new hypothesis. If the evidence matches, then the correct hypothesis is made.
• The backward chaining systems work backwards from a hypothesized goal, attempting to prove it by linking the goal to initial facts. Here are the steps to backward chain from a goal in the working memory
  • Select rules with conclusions matching the goal.
  • Replace the goal by the rule's premises which then becomes sub-goals.
  • Work backwards until all sub-goals are true.

Example

• Let us consider the same example of forward chaining: database includes facts A, B, C, D, and E, where the knowledge base is provided with the rules below.
  • Rule 1: IF A is true AND C is true THEN B is true
  • Rule 2: IF C is true AND D is true THEN F is true
  • Rule 3: IF C is true AND D is true AND E is true THEN X is true
  • Rule 4: IF A is true AND B is true AND X is true THEN Y is true
  • Rule 5: IF D is true AND Y is true THEN Z is true

Step 1

• The only rule with a conclusion matching the goal of Rule 5 is that D is in the database but we don't have Y.
• The first sub-goal is Y, and we will need to work backward until all sub-goals are true by back-chaining again.

Step 2

• The goal is Z but the sub-goal is Y therefore Rule 4 has Y as the conclusion.
• Among the Rule's 4 premises we have A and B in the database but we don't have X where the current sub-goal is X.

Step 3

• The goal is Z, though the sub-goals are Y and X, so the most recent is X, where Rule 3 has X as the conclusion.
• Rule 3 includes premises C, D, and E (can be found in the database) where the sub-goal X can be obtained by firing Rule 3 for the first time.
• The other sub-goals require to recursively back-chain to obtain the other sub-goals where, in this case, it is Y.
• With all premises for Rule 4 in place, Rule 4 can fire, and Y is obtained and added to the database.
• Going back to Step 1, having all premises for Rule 5 now means the conclusion is the desired goal, where firing Rule 5 and obtaining the goal is Z.

Goal-Driven Inference

• Backward chaining or goal-driven inference looks to the working memory to see if sub-goal states already exist.
• Identify the actions (THEN parts) of rules that will establish sub-goals, set up new sub-goals for achieving premises (IF parts) of those rules.

Advantages of Backward Chaining

• The search is goal directed which only applies the rules necessary to achieve it.

Disadvantages of Backward Chaining

• A goal has to be known which can be formed in a goal-based fashion for most AI systems.