Problem Solving Paradigms: Causal Reasoning 6.871 – Lecture 14Outline • Problem Solving Paradigms – What are they and what are they good for • Causal reasoning as a PSP – ABEL • Causal reasoning + rules + debugging – GORDIUS 6.871 - Lecture 14A Recipe • Study how experts characterize problems and solution methods, especially their technical vocabulary • Mimic their representation, capture the abstractions • Mimic their problem solving mechanism 6.871 - Lecture 14This Works Because • There are generic task types that span many domains • There are a modest number of problem solving paradigms and their knowledge representations • Each generic task has a variety of appropriate problem solving paradigms • Representations indicate how to look at the world: capture the important abstractions of the problemdomain. • Problem solving paradigms organize representational,inferential and computational processes; indicate when and how to draw conclusions. 6.871 - Lecture 14Caveats • A problem solving paradigm suggests control structures and inference mechanisms – but is not synonymous with them. • A knowledge representation suggests certain data-structures and control structures – but it is not synonymous with them. • Problem solving paradigms and knowledge representations are knowledge level constructs, not mechanisms or data structures. 6.871 - Lecture 14What’s In A PSP? • A representation for factual knowledge. • Inferential methods • A control structure dictating when to employ the inferential methods and with what purpose. 6.871 - Lecture 14Why Concentrate on Paradigms? • Special purpose programming languages for the paradigm can be created and reused. • Knowledge acquisition tools specific to the paradigm can be designed and reused. • Maintainability is improved. • Need for "programming hacks" reduced. • Emphasizes the search for the right level of abstraction. 6.871 - Lecture 14A Basic Paradigm: Means Ends Analysis Current Detect Differences Achieve Goal Preconditions Reduce Remaining Differences Apply Relevant Operator Operator Difference Table Walk Bike Taxi Bus <1 x x x x x x x x Choose Relevant Operator 1-5 5-50 50-500 6.871 - Lecture 14Diagnosis: A Classic Generic Task •PSPs – Bayesian statistics • Naïve Bayes’ rule • Sequential Bayesian diagnosis – Frequency and invoking strength: Internist – Empirical associations: Mycin – Causal: ABEL 6.871 - Lecture 14The Intuition • A flooded basement • An auto accident 6.871 - Lecture 14ABEL • Domain? • Representation? 6.871 - Lecture 14ABEL Representations low bicarb low potassium high chlorine causes Lower-GI-fluid-loss high sodium low water volume water-loss constituent-of bicarb-loss sodium-loss Lower-GI-fluid-loss potassium-loss chloride-loss 6.871 - Lecture 14Lower GI Fluid Plasma Fluid Na 100-110 138-148 K 30-40 4-5 Cl 60-90 100-110 HCO3 30-60 24-28 Compared to plasma: Lower GI Fluid is rich in HCO3 and K; low in NA and Cl Loss of GI Fluid results in reduced fluid in (hypovolemia) reduced K (hypokalemia) reduced HCO3 (hypobicarbonatemia) increased Cl (hyperchloremia) increased Na (hypernatremia) 6.871 - Lecture 14ABEL • Causal knowledge represented at multiple levels of description • Each causal relation characterized by constraints among severity, duration, etc. between cause and effect • Each causal relation described at next more detailed level • Each disease node described using network of nodes and causal links at next more detailed level • Goal: assemble a causal explanation of all findings using a network of causal relations at many levels of detail. • Models interactions between the hypothesized diseases 6.871 - Lecture 14Multiple Levels Aggregate Level X Composite node Focus Link causes causes causes causes causescauses Focus Link causes causes causescauses causes Elaboration Structure Focus Link Aggregate Level Detailed LevelDetailed Level Focus Node Focus Node Focus Node Elaboration Structure 6.871 - Lecture 14ABEL: Multiple Levels Clinical Level dehydration diarrhea causes focus focus dehydration diarrheaLower-GI-Loss causes causes focus focusfocus Intermediate Level dehydration diarrheaLower-GI-Loss causesPathophysiological Level const-of Sodium-Loss causes water-Loss 6.871 - Lecture 14Accounting For Multiple Causes causes Metabolic causes Acidosis-1 Shock-1diarrhea-1 focus focus focus Metabolic Acidosis-1 Component of Component of causes causesMetabolic Metabolic Acidosis-2 Acidosis-3 Shock-1diarrhea-1 6.871 - Lecture 14ABEL: Modeling Feedback causes Low pH-1Increased Respiration Rate component of component of causes Low pCO2-1 Hi pH-3 Low pH-2 Low HCO3-1 causes causes 6.871 - Lecture 14ABEL Operations • Elaboration : Makes connections across levels of detail by filling in the structure below • Aggregation: Makes connections across levels of detail by filling in the structure above • Component Decomposition: Relates disorders at the same level of detail by breaking up a nodeinto component parts • Component Summation: Relates disorders at the same level of detail by summing (arithmetically)contributions of components parts. • Projection: Forges causal links at the same level of detail in the search for etiologic explanation 6.871 - Lecture 146.871 - Lecture 14Combining Paradigms • Gordius: – Generate – test – debug – Rules + Causal Models • What’s generate and test as a PSP? – Dendral as an example – What did Dendral’s tester tell you? 6.871 - Lecture 14GORDIUS • Domain/task? 6.871 - Lecture 14Processes • Deposition • Intrusion • Fault • Uplift/subsidence • Tilt 6.871 - Lecture 14Rules Model Interactions Pattern constraints R1 IGN R2 Igneous(IGN) Same-type(R1, R2) Parallel(e1,e2) e1 e2 Events: create rock1 intrude IGN through rock1 6.871 - Lecture 14Local Matching 6.871 - Lecture 14Debugging • Dependency maintenance – height affected by: • shale is produced underwater • shale deposit depth • height is unchanged since deposition • sea level unchanged since deposition • Repair strategies – “unchanged” assumption – parameter value assumption – time ordering assumption 6.871 - Lecture 14Summary • Problem Solving Paradigms – What are they and what are they good for • Causal reasoning as a PSP – ABEL • Causal reasoning + rules + debugging – GORDIUS 6.871 - Lecture