1Decision Supportvia Expert Systems6.872/HST950Components of an Expert System• Knowledge– In various forms: associations, models, etc.• Strategy– Baconian, exhaustive enumeration, on-line,etc.• Implementation– Programs, pattern matching, rules, etc.FlowchartBI/Lincoln LabsClinical Protocols1978Codifying Human Knowledge• Decomposition into “chunks” of knowledge,chaining of inferences• Matching of case data to prototypicalsituations• Using causal models (pathophysiology) tofigure out casesMycin—Rule-based Systems• Task: Diagnosis and prescription forbacterial infections of the blood (and latermeningitis)• Method:– Collection of modularrules– Backward chaining– Certainty factorsRULE037IF the organism1) stains grampos2) has coccusshape3) grows in chainsTHENThere is suggestiveevidence (.7) that theidentity of theorganism isstreptococcus.Mycin consult--------PATIENT-1--------1) Patient's name: FRED SMITH2) Sex: MALE3) Age: 554) 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-BACTEREMIA6) 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? BLOOD8) 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. UNKNOWN10) Is ORGANISM-1 a rod or coccus (etc.)? ROD11) The gram stain of ORGANISM-1: GRAMNEG. . .Davis, et al., Artificial Intelligence 8: 15-45 (1977)2How 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 everywhereappropriate Single expression of any piece ofknowledgeExplore Mycin’s Use ofKnowledge** Did you use RULE 163 to find out anything about ORGANISM-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 RepresentationDiseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diagnosis by Card SelectionDiseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diseases1s2s3s4s5s6s7s8s9s10s...Diagnosis byEdge-Punched Cards Dx is intersection of sets of diseases thatmay cause all the observed symptoms Difficulties: Uncertainty Multiple diseases~ “Problem-Knowledge Coupler” of WeedTaking the Present Illness—Diagnosisby Pattern Directed MatchingHypothesisFacts aboutPatient3PIP'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 orrejected based on(1) logical criteria(2) probabilities based on:findings local to hypothesiscausal relations to other hypothesesThe Scientific MethodMemory Structure in PIPHypothesisLogical CriteriaProbabilisticScoringFunctionDifferentialDiagnosisHeuristicsTriggersCausally andAssociationallyRelated Hyp'sManifestationsPIP's Model of Nephrotic SyndromeNEPHROTIC SYNDROME, a clinical stateFINDINGS:1* Low serum albumin concentration2. Heavy proteinuria3* >5 gm/day proteinuria4* Massive symmetrical edema5* Facial or peri-orbital symmetric edema6. High serum cholesterol7. Urine lipids presentIS-SUFFICIENT: Massive pedal edema & >5 gm/day proteinuriaMUST-NOT-HAVE: Proteinuria absentSCORING . . .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 retentionDIFFERENTIAL DIAGNOSIS:neck veins elevated  constrictive pericarditisascites present  cirrhosispulmonary emboli present  renal vein thrombosisQMR PartitioningM1M2M3M4M5M6H1 H2CompetitorsM1M2M3M4M5M6H1 H2Still CompetitorsM1M2M3M4M5M6H1 H24Probably ComplementaryM1M2M3M4M5M6H1 H2Multi-Hypothesis DiagnosisSet aside complementary hypotheses… and manifestations predicted by themSolve diagnostic problem amongcompetitorsEliminate confirmed hypotheses andmanifestations explained by themRepeat as long as there are coherentproblems 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 fromconfirmed HypothesesNegative FactorsFrequency of predicted but absentManifestationsImportance of unexplained ManifestationsVarious scaling parameters (roughlyexponential)Example Case5Initial Solution— Tom Wu, Ph.D. 1991Assume a bipartite graph representation ofdiseases/symptomsGiven 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)d1 d2 … dks1 s2 s3 … sn(s2, s3, s7) (s1) (s5, s9)d5 d6d3 d7 d8 d9d1 d2 d4Symptom Clustering forMulti-Disorder DiagnosisClustering AlternativesTB, Asthma, Bronchitis,EmphysemaCoughTB, Hepatitis, MalariaFeverPossible CausesSymptomTBHepMalAsthBronEmphTBHepMalAsthBronEmphTBFever, CoughAsthBronEmphHepMalCoughFeverH1H2Synopsis in Renal Disease• Diseases– Hypertension (HTN)– Acute glomerulonephritis (AGN)– IgA nephropathy