Production Systems PDF

Chapters 5, 6. Production Systems and expert systems Based on Prof. Nadim Obeid’s Lecture notes By Dr. Tahani Khatib Definition A production system is used for implementing search algorithms and for modelling human problem solving. It...

Chapters 5, 6. Production Systems and expert systems Based on Prof. Nadim Obeid’s Lecture notes By Dr. Tahani Khatib Definition A production system is used for implementing search algorithms and for modelling human problem solving. It solves problems by applying a set of rules step-by-step, updating the state, and repeating until a solution is reached or no rules apply. A production system consists of: 1. Production rules: o A set of "if-then" rules (called productions) that guide problem-solving. o The condition part defines when the rule applies. o The action part specifies what to do when the condition is met. 2. Working Memory: o A temporary storage area that holds the current state of the problem. o It compares the conditions of rules to decide which action should be taken. 3. Recognize–Act Cycle: o A loop that runs the system: ▪ Match the conditions of the rules with the current state in working memory. ▪ Select one of the matching rules (conflict resolution). ▪ Execute the action of the selected rule, which updates working memory. ▪ Repeat until no rules apply. Key Concepts Firing a Rule: When a rule is executed, it updates working memory with new information. Conflict Resolution: If multiple rules match, the system decides which rule to execute. Strategies can be simple (e.g., pick the first match) or complex (e.g., prioritize certain rules). Conflict Resolution strategies Simplest strategy choose the first rule that matches the working memory. Conflict resolution Strategies: 1. Ordering on rules such as O1: R1 ≥ R2 ≥ R3 ≥ R4 O2: R4 ≥ R3 ≥ R2 ≥ R1 2. Refraction: Once a rule is fired, it may not fire again until the working memory that match its conditions have been modified. Discourage looping. Example: - Ref(1): a rule that has been selected in the previous cycle, it will not be considered for selection in this cycle. - Ref(2): rules that have been selected in the previous two cycles, will not be considered for selection in this cycle. 3. Recency: Prefer rules that matches the pattern that most recently added to the working memory. Focuses on a single line of reasoning. 4. Specificity: Use more specific problem-specific rule than to use more general once. More specific rules have more conditions (matches fewer rules). match, select, apply Example1 Consider the following system where WM ={-2}. List of Rules: (R1) if X in WM then add X+1 to WM. (R2) if X in WM and X is odd then add X+4 to WM. (R3) if X in WM and X is odd and X > 0 then add X-3 to WM. (R4) if 5 in WM then print “Hi”. (R5) if 7 in WM then Stop. Cycle No. Applicable rules Selected rule WM 1. R1 R1 {-2,-1} 2. R1,R2 R1 {-2,-1,0} 3. R1 R1 {-2,-1,0,1} 4. R1,R2,R3 S1? WM1? Given the following conflict Resolution Strategies in the following: a) Ordering on rules such as O1: R1 ≥ R2 ≥ R3 ≥ R4 ≥ R5 O2: R5 ≥ R4 ≥ R3 ≥ R2 ≥ R1 b) Refraction: Ref(1): a rule that has been selected in the previous cycle, it will not be considered for selection in this cycle. Ref(2): rules that have been selected in the previous two cycles, will not be considered for selection it this cycle. c) Recency: Prefer rules that matches the pattern that most recently added to the working memory. Another way of saying it, prefer rules that have recently become applicable. d) Specificity: Use more specific problem-specific rule than to use more general once. More specific rules have more conditions (matches fewer rules). Question: What are the values of (S1) and working memory (WM1) in iteration 4 in the previous example in each of the following cases: a) O2 is used in cycle 4 as a conflict resolution strategy b) O1 is used in cycle 4 as a conflict resolution strategy c) Refractoriness (once) together with O1 in cycle 4 as a conflict resolution strategy, i.e., we have now. d) Refractoriness (once) together with O2 in cycle 4 as a conflict resolution strategy, i.e., we have now. e) Recency is used in cycle 4 as a conflict resolution strategy f) Specificity is used in cycle 4 as a conflict resolution strategy Notice that: 1. In the cycles 1, 2, and 3, we have always selected R1, However, I applied R1 on the newest data. 2. When the same rule is applicable to different data, the more recent data in WM is selected. 3. The table above is another representation of the match, select, apply cycle, and WM reflects the modifications/updates to resulting from applying the selected rule. 4. Applicable rules are determined by the interpreter 5. Selected rule is determined by the conflict resolution strategies 6. “0” is an even number Solution a) O2 is used in cycle 4 as a conflict resolution strategy - If we use O2, then we will prefer R3. - R3 applied to 1 allows me to add 1-3 to WM = {-2,-1,0,1} yielding {-2,-1,0,1,-2} Answer: S1 = R3 WM1 = {-2,-1,0,1, -2} b) O1 is used in cycle 4 as a conflict resolution strategy - If we use O1, then we will prefer R1. - R1 applied to 1 allows me to add 1+1 to WM = {-2,-1,0,1,2} yielding {-2,-1,0,1,2} Answer: S1 = R1 WM1 = {-2,-1,0,1, 1} Important note: If from cycle 4 onwards we employ O1, then in cycle 5, 6, 7, …, we will always select R1 !! In such a case, we have an infinite loop!! One way to break this loop will be to employ refraction/ Refractoriness (once). c) Refractoriness (once) together with O1 in cycle 4 as a conflict resolution strategy, i.e., we have now. - Ref(1) says that since R1 has been selected in cycle 3, then ignore R1. I will be left with R2 and R3. - O1 tells me, we prefer R2. - R2 applied to 1 allows me to add 1+4 to WM = {-2,-1,0,1} yielding {-2,-1,0,1,5} Answer: S1 = R2 WM1 = {-2,-1,0,1,5} d) Refractoriness (once) together with O2 in cycle 4 as a conflict resolution strategy, i.e., we have now. - Ref(1) says that since R1 has been selected in cycle 3, then ignore R1. I will be left with R2 and R3. - If we use O2, then we will prefer R3. - R3 applied to 1 allows me to add 1-3 to WM = {-2,-1,0,1} yielding {-2,-1,0,1,-2} Answer: S1 = R3 WM1 = {-2,-1,0,1,-2}  Note that: Ref(1) tells me to look at the rule that has been selected in the previous cycle to ignore in this cycle. Ref(2) tells me to look at the rules that has been selected in the previous two cycles to ignore in this cycle. e) Recency is used in cycle 4 as a conflict resolution strategy R3 applied to 1 allows me to add 1-3 to WM = {-2,-1,0,1} yielding {-2,-1,0,1,-2} Answer: S1 = R3 WM1 = {-2,-1,0,1,-2} Note that: Recency tells me to look at the rules that have recently been applicable. o In cycle 1, R1 is applicable o In cycles 2 and 3, R1 and R2 are applicable, Therefore R2 is more recent than R1 o In cycles 4, R1, R2 and R3 are applicable, Therefore R3 is the most recent in comparison with R1 and R2 f) Specificity is used in cycle 4 as a conflict resolution strategy R3 applied to 1 allows me to add 1-3 to WM = {-2,-1,0,1} yielding {-2,-1,0,1,-2} Answer: S1 = R3 WM1 = {-2,-1,0,1,-2} Note that: o It is clear that R3 is more specific than R2 as it contains more conditions in the If- part of the rule, and R2 is more specific than R1 as it contains more conditions in, the If-part of the rule. Example2 Consider the following system where WM ={0}. List of Rules: (R1) if X in WM then add X+1 to WM. (R2) if 2 in WM then print “hi” (R3) if 3 in WM then print “good luck” (R4) if 4 in WM then Stop. Cycle No. Applicable rules Selected rule WM 1. R1 R1 {0, 1} 2. R1 R1 {0, 1, 2} 3. R1,R2 R1 {0, 1, 2, 3} 4. R1,R2,R3 S1? WM1? Question: What are the values of (S1) and working memory (WM1) in iteration 4 in the previous example in each of the following cases: a) O2 is used in cycle 4 as a conflict resolution strategy Answer: S1 = R3 WM1 = {0, 1, 2, 3} good luck b) O1 is used in cycle 4 as a conflict resolution strategy Answer: S1 = R1 WM1 = {0, 1, 2, 3, 4} c) Refractoriness (once) together with O1 in cycle 4 as a conflict resolution strategy, i.e., we have now. Answer: S1 = R2 WM1 = {0, 1, 2, 3} hi d) Refractoriness (once) together with O2 in cycle 4 as a conflict resolution strategy, i.e., we have now. Answer: S1 = R3 WM1 = {0, 1, 2, 3} good luck e) Recency is used in cycle 4 as a conflict resolution strategy Answer: S1 = R3 WM1 = {0, 1, 2, 3} good luck f) Specificity is used in cycle 4 as a conflict resolution strategy Answer: S1 = R2 WM1 = {0, 1, 2, 3} good luck Exercise Consider the following system where WM ={0}. List of Rules: (R1) if X in WM then add X+1 to WM. (R2) if X in WM and X is even then add X*2 to WM (R3) if 3 in WM then print “OK” (R4) if 4 in WM then print “HELP” (R5) if 5 in WM then Stop. Cycle No. Applicable rules Selected rule WM 1. R1 R1 {0, 1} 2. R1 R1 {0, 1, 2} 3. R1,R2 R1 {0, 1, 2, 3} 4. R1,R2, R3 R1 {0, 1, 2, 3, 4} 5. R1,R2,R3, R4 S1? WM1? Question: What are the values of (S1) and working memory (WM1) in iteration 4 in the previous example in each of the following cases: a) O2 is used in cycle 4 as a conflict resolution strategy b) O1 is used in cycle 4 as a conflict resolution strategy c) Refractoriness (once) together with O1 in cycle 4 as a conflict resolution strategy, i.e., we have now. d) Refractoriness (once) together with O2 in cycle 4 as a conflict resolution strategy, i.e., we have now. e) Recency is used in cycle 4 as a conflict resolution strategy f) Specificity is used in cycle 4 as a conflict resolution strategy Advantages of production systems for artificial intelligence Separation of Knowledge and Control A Natural Mapping onto State Space Search Modularity of Production Rules Pattern-Directed Control Opportunities for Heuristic Control of Search Tracing and Explanation Language Independence A Plausible Model of Human Problem-Solving Limitations of production systems: 1. A basic production system doesn't recover from mistakes or dead ends. Advanced systems can include backtracking to revisit earlier states. 2. Production system not necessarily assumed to actually model human problem- solving behaviour, but it is an ideal tool for designing and building expert systems because it provides: – modularity of rules. – Separation of knowledge and control – Separation of working memory and problem-solving knowledge. Application of production rules Expert systems Expert systems: An expert system is a computer program that is designed to solve complex problems and to provide decision-making ability like a human expert. Techniques for reasoning in expert systems are as follows: 1. rules-based, 2. model-based, 3. case-based reasoning Production systems are the core computational frameworks in expert systems that use rules-based reasoning Expert systems: Use knowledge specific to a problem domain to provide expert-quality performance in an application area. They emulate human’s expert methodology and performance. They are not general, i.e. Do not know everything. They usually focus on a narrow set of problems. They are knowledge-intensive and use heuristics, therefore they allow inspection of the reasoning process, presenting about intermediate process and answering questions about the solution process. They allow easy modifications by adding or deleting skills from the knowledgebase. They use heuristics using (imperfect) knowledge to get useful solutions. Expert system designers (AI specialist or engineer): acquire the theoretical and practical knowledge with the help of human domain expert. Human experts usually augment theoretical understanding with tricks (rules of thumb), shortcuts and heuristics to use the knowledge through problem-solving experience. Expert systems can give explanations of their outcomes: Explanation and justification are important if the user is to accept a recommendation from a computer. To allow giving explanations, expert systems should be easily prototyped, tested, and changed. Example easily modification of rules in a production system. Easy modification of the knowledge-base is a major factor in producing a successful program. Areas of expert systems are in wide range including: Medicine, mathematics, engineering, chemistry, geology, computer science, business, law, defence, and education. Expert system architecture 1. Knowledge can be if then rules in rule-based systems. 2. Inference engine applies the knowledge to the solution of actual problem. It is an interpreter for the knowledge-base. 3. Case specific data contains knowledge about the case under consideration such as data given in a problem instance, partial conclusions, dead ends in the search 4. Explanation subsystem allows programs to explain its reasoning to the user. a. Justification for the system conclusions (How). b. Explanation of why the system needs specific data (Why). 5. Knowledge-based editor helps programmer: a. locate and correct bugs in the program’s performance. b. Addition of new knowledge, maintaining correct syntax. The advantages of rule-based approaches The advantages of rule -based approach used in expert systems include: 1. They directly use human expert knowledge, helping in domains with complexity or missing data. 2. Rules can support debugging by mapping into structured state spaces.  3. Knowledge is separate from control, simplifying the development and testing of expert systems. 4. They perform well in specific domains where enough knowledge is available. 5. They offer clear explanations, though the quality depends on the structure and content of the rules. The disadvantages of rule-based approaches The disadvantages of rule -based approach used in expert systems include: 1. Rules rely on human input and often miss deeper knowledge. 2. They are brittle—they struggle with incomplete or unexpected data. 3. They fail to adapt when faced with new or edge-case problems. 4. Explanations are shallow, focusing on symptoms, not deeper reasoning. 5. Rules are very task-specific and lack flexibility, unlike human reasoning.