9expert.doc EE 4524 Page 1ECpE 4524Knowledge-BasedSystemsoften calledExpert Systems9expert.doc EE 4524 Page 2Knowledge-based systems(textbook, chapter 20)Goal:Try to solve the kinds of problemsthat normally require human expertsTypical examples:medical diagnosis, financial analysis,factory production schedulingWhy study knowledge-based systems?To understand human reasoningmethodsHuman experts tend to takevacations, get hired by othercompanies, ask for raises, retire,become ill, die, . . .Lots of commercial successes!9expert.doc EE 4524 Page 3Expert system overview:KNOWLEDGEBASEREASONINGMECHANISMProblemdescriptionAnalysis andjustificationThe knowledge base . . .● contains "domain knowledge,"normally provided by human experts● is typically very specialized for aparticular problem domain● is often encoded as IF-THEN rules● may incorporate heuristics orprobabilities● is a valuable commodity9expert.doc EE 4524 Page 4Building, validating, and maintaininga knowledge base is a skill (art)called knowledge engineeringThe reasoning mechanism . . .●takes descriptions from the userabout the problem to be solved●requests additional informationfrom the user as needed●interprets the knowledge base tomake inferences, drawconclusions, and ultimately giveadvice●explains its reasoning to the user(how were the conclusionsreached?)●is sometimes called aninference engine9expert.doc EE 4524 Page 5An example:PUFF (1979)Pulmonary function analysisPhysician refers patient topulmonary testing labPatient inhales/exhales throughtube connected to computerizedinstrument which measures flowrates and air volumesPUFF accepts this data along withauxiliary data (age, sex,smoking history), and printsdiagnosis in EnglishNow used on a routine basis (?)9expert.doc EE 4524 Page 6Building PUFF's knowledge base:A knowledge engineer sat downwith an expert pulmonaryphysiologist at the PacificMedical Center in SanFrancisco and developed rules(64 in all)IF 1. ----------2. ----------3. ----------. . .THEN 1. ----------2. ----------. . .(A more recent version had about400 rules.)9expert.doc EE 4524 Page 7Example PUFF rule:RULE31IF:1. The severity of obstructive airwaysdisease of the patient is greater than or equalto mild, and2. the degree of diffusion defect of thepatient is greater than or equal to mild, and3. the TLC observed/predicted of the patientis greater than or equal to 110, and4. the observed/predicted difference inRV/TLC of the patient is greater than orequal to 10THEN:1. There is strongly suggestive evidence(0.9) that the subtype of obstructive airwaysdisease is emphysema, and2. It is definite (1.0) that "OAD, DiffusionDefect, elevated TLC, and elevated RVtogether indicate emphysema" is one of thefindings9expert.doc EE 4524 Page 8Sample PUFF session:PATIENT DATA:The degree of dyspnea: MODERATELY-SEVEREThe severity of coughing: MILDSputum production: MODERATELY-SEVEREThe number of pack-years of smoking: 48Referal diagnosis: BRONCHITISIVC/IVC-predicted: 80RV/RV-predicted: 191FVC/FVC-predicted: 87TLC observed/predicted: 127Predicted FEV1/FVC: 83TLC(DLCO) observed/predicted: 83FEV1/FVC ratio: 50RV/TLC observed/predicted: 21MMF/MMF-predicted: 19DLCO/DLCO-predicted: 48The slope of (F50obs-F25obs)/FVCobs: 19DEGREE OF OBSTRUCTIVE AIRWAYS DISEASE:OAD degree by slope: MODERATELY-SEVERE 700OAD degree by MMF: SEVERE 900OAD degree by FEV1: MODERATELY-SEVERE 700Final OAD degree: MODERATELY-SEVERE 910SEVERE 9009expert.doc EE 4524 Page 9INTERPRETATION:Obstruction is indicated by curvature of the flow-volumeloop.Forced Vital Capacity is normal and peak flow rates arereduced, indicating severe airway obstruction.Change in expired flow rates following bronchodilationshows that there is reversibility of airwayobstruction.Elevated lung volumes indicate overinflation.Air trapping is indicated by the elevated differencebetween observed and predicted RV/TLC ratios.Airway obstruction is consistent with the patient'ssmoking history.The airway obstruction accounts for the patient's dyspnea.Although bronchodilators were not useful in this onecase, prolonged use may prove to be beneficial.Obstructive Airways Disease of mixed types.9expert.doc EE 4524 Page 10How were the rules produced?100 cases (previously diagnosedpatients) were selectedThe cases were chosen to span thevariety of known disease statesThe pulmonary function expert posedhypothetical rules for diagnosingthe illnessThe knowledge engineer encodedthe rules (in LISP) and testedthem with the test cases.The expert reviewed the test resultsand modified or added rules tohandle the cases that wereincorrectly diagnosedLooping continued until the expertwas satisfied9expert.doc EE 4524 Page 11How to test PUFF's performance?150 additional different cases wereanalyzed1) by human experts and2) by PUFFThe diagnoses were compared:90% matched to same degree ofseverity100% matched to within onedegree of severityEffort:50 hours by the expert400 hours by the knowledgeengineerThe 64 rules were "popped into" anexisting expert system9expert.doc EE 4524 Page 12OBSERVATIONSHuman experts are often unaware ofhow they reach conclusionsThe expert usually knows more thanhe/she is aware of knowingThe knowledge brought to bear by theexpert is often experiential, heuristic,and uncertainGeneral problem-solvers (domain-independent) are too weak forbuilding real-world, high-performance systemsThe behavior of the best problem-solvers (humans) is weak andshallow except in areas ofspecializationExpertise in one specialization areausually does not transfer well to otherareas9expert.doc EE 4524 Page 13Recall weak vs. strong methods:Weak methodsdomain-independent, general-purpose(example: GPS)Strong methodsdomain-specific, knowledge-rich(examples: knowledge-basedsystems)9expert.doc EE 4524 Page 14Example expert systemsMedicineMYCIN (1976)Identification of bacteria in blood andurine samples; prescription ofantibioticsINTERNIST / CADUCEUS (1970s /1984)Diagnosis of majority of diseases in fieldof internal medicinePUFF (1979)Interpretation of respiratory tests fordiagnosis of pulmonary disordersBABY (19??)Patient monitoring in a newbornintensive care unitQMR (1988) (Quick Medical Record)Assists physicians in diagnosis of over4000 disease manifestations (usesthe INTERNIST knowledge base)9expert.doc EE 4524 Page 15CHEMISTRYDENDRAL (1960s and 1970s)Identification of molecular structureof organic compoundsCRYSALIS (19??)Interpretation of electron densitymaps in protein