Decision Support via Expert Systems 6.872/HST950 Peter SzolovitsComponents of an Expert System • Knowledge – In various forms: associations, models, etc. • Strategy – Baconian, exhaustive enumeration, on-line, etc. • Implementation – Programs, pattern matching, rules, etc.Flowchart BI/Lincoln Labs Clinical Protocols 1978Codifying Human Knowledge • Decomposition into “chunks” of knowledge, chaining of inferences • Matching of case data to prototypical situations • Using causal models (pathophysiology) to figure out casesMycin—Rule-based Systems • Task: Diagnosis and prescription forbacterial infections of the blood (and latermeningitis) • Method: – Collection of modular rules – Backward chaining – Certainty factors RULE037 IF the organism1) stains grampos2) has coccusshape3) grows in chains THEN !There is suggestiveevidence (.7) that theidentity of theorganism isstreptococcus.Mycin consult --------PATIENT-1--------1) Patient's name: FRED SMITH 2) Sex: MALE 3) Age: 55 4) Have you been able to obtain positive cultures from a site at which FredSmith has an infection? YES --------INFECTION-1--------5) What is the infection? PRIMARY-BACTEREMIA 6) Please give the date when signs of INFECTION-1 appeared. 5/5/75The most recent positive culture associated with the primary-bacteremia will be referred to as: --------CULTURE-1--------7) From what site was the specimen for CULTURE-1 taken? BLOOD 8) Please give the date when this culture was obtained. 5/9/75The first significant organism from this blood culture will be called:--------ORGANISM-1--------9) Enter the identity of ORGANISM-1. UNKNOWN 10) Is ORGANISM-1 a rod or coccus (etc.)? ROD 11) The gram stain of ORGANISM-1: GRAMNEG . . . Davis, et al., Artificial Intelligence 8: 15-45 (1977)How Mycin Works • To find out a fact – If there are rules that can conclude it, try them – Ask the user • To “run” a rule – Try to find out if the facts in the premises are true – If they all are, then assert the conclusion(s), with a suitable certainty • Backward chaining from goal to given facts  Dynamically traces out behavior of (whatmight be) a flowchart  Information used everywhere appropriate  Single expression of any piece of knowledgeExplore Mycin’s Use of Knowledge ** Did you use RULE 163 to find out anything aboutORGANISM-1? RULE163 was tried in the context of ORGANISM-1, but it failedbecause it is not true that the patient has had a genito-urinary tractmanipulative procedure (clause 3).** Why didn't you consider streptococcus as a possibility?The following rule could have been used to determine that the identityof ORGANISM-1 was streptococcus: RULE033But clause 2 (“the morphology of the organism is coccus”) was alreadyknown to be false for ORGANISM-1, so the rule was never tried.Davis, et al., Artificial Intelligence 8: 15-45 (1977)Even Simpler Representation Disease s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s... Disease s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s...Diseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diagnosis by Card Selection Disease s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s...Diagnosis by Edge-Punched Cards Dx is intersection of sets of diseases that may cause all the observed symptoms Difficulties: Uncertainty Multiple diseases ~ “Problem-Knowledge Coupler” of WeedTaking the Present Illness—Diagnosis by Pattern Directed MatchingPIP's Theory of Diagnosis • From initial complaints, guess suitable hypothesis. • Use current active hypotheses to guide questioning • Failure to satisfy expectations is the strongest clueto a better hypothesis; differential diagnosis • Hypotheses are activated, de-activated, confirmed or rejected based on (1) logical criteria(2) probabilities based on: findings local to hypothesis causal relations to other hypotheses The Scientific MethodMemory Structure in PIP Triggers Logical Criteria Hypothesis Probabilistic ScoringFunction Differential DiagnosisHeuristicsCausally andAssociationallyRelated Hyp's ManifestationsPIP's Model of Nephrotic Syndrome NEPHROTIC SYNDROME, a clinical state FINDINGS: 1* Low serum albumin concentration 2. Heavy proteinuria 3* >5 gm/day proteinuria 4* Massive symmetrical edema 5* Facial or peri-orbital symmetric edema 6. High serum cholesterol7. Urine lipids presentIS-SUFFICIENT: Massive pedal edema & >5 gm/day proteinuriaMUST-NOT-HAVE: Proteinuria absent SCORING . . . MAY-BE-CAUSED-BY: AGN, CGN, nephrotoxic drugs, insect bite,idiopathic nephrotic syndrome, lupus, diabetes mellitusMAY-BE-COMPLICATED-BY: hypovolemia, cellulitisMAY-BE-CAUSE-OF: sodium retention DIFFERENTIAL DIAGNOSIS: neck veins elevated ➠ constrictive pericarditis ascites present ➠ cirrhosis pulmonary emboli present ➠ renal vein thrombosisQMR Partitioning M1 M2 M3 M4 M5 M6 H1 H2Competitors M1 M2 M3 M4 M5 M6 H1 H2Still Competitors M1 M2 M3 M4 M5 M6 H1 H2Probably Complementary M1 M2 M3 M4 M5 M6 H1 H2Multi-Hypothesis Diagnosis Set aside complementary hypotheses … and manifestations predicted by them Solve diagnostic problem among competitors Eliminate confirmed hypotheses and manifestations explained by them Repeat as long as there are coherent problems among the remaining dataInternist/QMR  Knowledge Base:  956 hypotheses  4090 manifestations (about 75/hypothesis)  Evocation like P(H|M)  Frequency like P(M|H)  Importance of each M  Causal relations between H’s  Diagnostic Strategy:  Scoring function  Partitioning  Several questioning strategiesQMR DatabaseQMR Scoring Positive Factors Evoking strength of observed Manifestations Scaled Frequency of causal links from confirmed Hypotheses Negative Factors Frequency of predicted but absent Manifestations Importance of unexplained Manifestations Various scaling parameters (roughly exponential)Example CaseInitial SolutionSymptom Clustering for Multi-Disorder Diagnosis — Tom Wu, Ph.D. 1991 Assume a bipartite graph representation of diseases/ symptoms Given a set of symptoms, how to proceed? If we could “guess” an appropriate clustering of thesymptoms so that each cluster has a single cause … … then the solution is (d5, d6) x (d3, d7, d8, d9) x (d1,d2, d4)Clustering Alternatives Symptom Possible Causes Fever TB, Hepatitis, Malaria Cough TB, Asthma, Bronchitis, Emphysema H1 H2 Fever, Cough Fever Cough TB Hep Asth Mal Bron Emph