Knowledge-Based Expert Systems 2

Knowledge-Based Expert Systems 2

اسلاید 1: 1Knowledge-Based Expert SystemsA computer program which, with its associated data, embodies organised knowledge concerning some specific area of human activity. Such a system is expected to perform competently, skilfully and in a cost-effective manner; it may be thought of as a computer program which mimics the performance of a human expert.

اسلاید 2: 2Knowledge-Based Expert SystemsThe Nature of ExpertiseOne view of human expertise is that some people have spent so much time solving problems in one particular domain that they ‘know all there is to know’ (nearly) and are able to see any problem as an instance of a class of problems with which they have been confronted before.Once the expert has successfully classified or recognised a new problem as an instance of a previously experienced problem type, all the expert has to do is apply whatever solution proved successful in dealing with that type of problem in the past.

اسلاید 3: 3Knowledge-Based Expert SystemsThe Nature of ExpertiseThis model of human expertise that relies (a) on domain-specific knowledge and (b) experience-based recognition of solutions of problems and has served as the basis of numerous expert systems.The idea is that cognition is a ‘recognition’-based phenomenon. That is, when a medical doctor, say, examines a patient or hears what the patient has to say about his or her problem, the configuration of symptoms or signs suggests a particular illness with which the doctor is already completely familiar.

اسلاید 4: 4Knowledge-Based Expert SystemsThe Nature of ExpertiseThe ‘recognition-based’ phenomenon can be viewed as setting up a key goal in the problem solving process and then attempting to find out data that satisfies the goal. The goal is then broken up into sub-goals and data sought to prove each of the sub-goals. (The sub-goals can be broken into further sub-goals and so on and on).While proving a sub-goal, the experts suspend the goal and try and satisfy individual goals. Once all sub-goals are satisfied then the key goal is deemed to be satisfied and the problem solved!

اسلاید 5: 5Knowledge-Based Expert SystemsPneumonia Expert SystemConsider a small chunk of a medical experts knowledge about diagnosing pneumonia and feverrule pneumonia if ‘the patient has chest pain’ &‘the patient has a fever’ &‘the patient produces purulent sputum’then‘the patient has pneumonia’ rule fever if‘the patient has a temperature above 100’then‘the patient has a fever’.The nurse has just come in a with a patient with the following symptoms:‘the patient has a chest pain’ &‘the patient has a temperature above 100’& ‘the patient produces purulent sputum’ And the expert has to deduce whether or not the patient has pneumonia?

اسلاید 6: 6Knowledge-Based Expert SystemsPneumonia Expert SystemThe nurse has just come in a with a patient with the following symptoms:‘the patient has a chest pain’ &‘the patient has a temperature above 100’& ‘the patient produces purulent sputum’ And the expert has to deduce whether or not the patient has pneumonia?In order to prove whether or not the patient has pneumonia, the expert has to prove:prove ‘the patient has pneumonia’ GOALprove ‘the patient has a chest pain’  SUB-GOAL prove ‘the patient has a fever’ SUB-GOALprove ‘the patient produces purulent sputum’ SUB-GOAL

اسلاید 7: 7Knowledge-Based Expert SystemsIntelligent beings perceive, reason and act. Intelligent beings are creative, learn from their mistakes. Intelligent beings can learn from their environment. Intelligent beings can learn with the help of tutors. Intelligent beings can work on their own/form groups. Intelligent beings have a value system, an exchange system.

اسلاید 8: 8Knowledge-Based Expert SystemsMYCIN, microbial infection therapy system comprised over 400 rules of thumb such as below which help in microbial infection therapy, for example in the diagnosis and therapy of meningitis. IF:1) The stain of the organism is grampos, and2) The morphology of the organism is coccus, and3) The growth conformation of the organism is chainsTHEN:There is suggestive evidence (0.7) that the identity of the organism is streptococcus. Each of the antecedent clauses and the consequent clause is essentially a complex relationship between the terms of this subject: the stain, morphology and growth, conformation of an organism and its identity and the attributes of these = grampos, coccus, chains, streptococcus. The rules show the interrelationship between various domain objects (the stain etc.) and how such a relationship could be used to infer new facts. The objects and their attributes, (for example, morphology and its attribute coccus) viewed here as a data structure, are each viewed by the terminologist as terms representing concepts.

اسلاید 9: 9Knowledge-Based Expert SystemsThe expert system R1/XCON was used by DEC(now a part of COMPAQ) for configuring computer systems. This system was in routine commercial use and contains over 10,000 rules of the type shown belowIF:The most current active context is assigning a power supply &an sbi module of any type has been put in a cabinet &the position it occupies in the cabinet (its nexus) is known & there is space available in the cabinet for a power supply for that nexus & there is an available power supply THEN: put the power supply in the cabinet in the available space. The above rule is much more complex than the rule shown for MYCIN in that although we are talking about putting the power supply in the cabinet in the available space, each of the domain objects and its attributes is a complex entity in itself: for example an SBI module of any type, the power supply and the available space in the cabinet.

اسلاید 10: 10Knowledge-Based Expert SystemsKnowledge-Based SystemsInputsActionsGoalsEnvironmentMedical diagnosis systemSymptoms, findings, patient’s answersQuestions, tests, treatmentsHealthy patient, minimise costsPatient, hospitalSatellite image analysis systemPixels of varying intensity, colourPrint a categorisation of sceneCorrect categorisationImages from orbiting satellitePart-picking robotsPixels of varying intensityPick up parts and sort into binsPlace parts in correct binsConveyor belt with partsRefinery controllerTemperature, pressure readingsOpen, close valves; adjust temperatureMaximise purity, yield, safetyRefinery

اسلاید 11: 11Knowledge-Based Expert SystemsA conventional computing system C O M P U T E R S Y S T E MU S E R I N T E R F A C ECOMPUTER SYSTEMD A T A B A S EDataFactsA L G O R I T H M (S)

اسلاید 12: 12Knowledge-Based Expert SystemsA Knowledge-Based system C O M P U T E R S Y S T E MU S E R I N T E R F A C ECOMPUTER SYSTEMDataFactsH E U R I S T I C S & A L G O R I T H M (S) K N O W L E D G E B A S ERules Meta Rules

اسلاید 13: 13Knowledge BaseAn organised and structured repository of ‘human knowledge’ in a given specialist domain. This repository can be updated or deleted in parts. Usually the knowledge is encoded as conditional ‘if <antecedent> then <consequent>‘ statements (‘rules’ and ‘problem-solving tasks’) together with the so-called ‘domain objects’. The latter are descriptions of facts, including concrete and abstract facts, relating to the specialist domain.

اسلاید 14: 14Knowledge BaseKnowledge representation is about making things explicit, is about resolving ambiguities;Knowledge representation, in the context of artificial intelligence, is about describing a class of things to a computer system. This description should not be ambiguous either lexically or structurallyThis description should explicate shared knowledge

اسلاید 15: 15Reasoning StrategiesReasoning may be characterised as an attempt to combine elements of old information to form new information. Reasoning strategies refer to the rather long sequences of individual small inferences organised so as to address a main goal or problem. Reasoning strategies involve the representation of information and knowledge, the use of inference rules for manipulating that knowledge & information, and control mechanisms for making the variety of choices necessary in the search for solutions.

اسلاید 16: 16Problem SolvingProblem-solving is sometimes defined as a process that involves finding or constructing a solution to a problem.Human problem solving can be modelled as the exploration of different paths to a solution and involves ‘information processing’ which appears unique to human beings. Cognitive psychologists typically divide problems into two classes: ‘well defined’ or closed world problems including solutions of games or puzzles and ‘ill defined’ or open world problems.

اسلاید 17: 17Prevent the hi-jacking of airlinersPrevent hi-jackers from boarding the airlinersHeuristic techniqueAlgorithmic routePut passengers and luggage through a metal detector &Search only those who set off the detector Search those passengers that match a predetermined hi-jacker profile(inc. passengers, flight crews & mechanics)Strip search every person with access to the airlines &Search all luggageHeuristics or Rules of thumb

اسلاید 18: 18 Conventional ProgramsKBESRepresentationdataknowledgeReasoningalgorithmic & repetitiveheuristic & inferentialRetrieveslarge DBlarge KBKnowledgeencryptedrepresentedKnowledge Based Systems & Conventional Systems

اسلاید 19: 19There are recognised expertsThe experts are provably better than novicesThe tasks takes an expert a few minutes to a few hours (if it takes days - FORGET IT)The task is primarily cognitiveThe skill is routinely taught to novicesThe task requires no common senseThe task domain is important: economically, financially or sociallyKnowledge Based Systems & Applications

اسلاید 20: 20Knowledge EngineeringThe accumulation, codification and application of knowledge through the use of computer systems, specifically knowledge-based systems.

اسلاید 21: 21Knowledge Engineering

اسلاید 22: 22Rule-based SystemsA rule-based system helps us to codify the problem-solving knowledge of the human expert.It appears that experts typically express their knowledge as a set of situation-action rules.RBS research should address the need to capture, represent, store, distribute, reason about and apply human knowledge electronically.Hayes Roth, F. (1992). ‘Rule-Based Systems’ p.1426

اسلاید 23: 23Information Exchange & Natural LanguageNatural Language. A person’s native tongue.Natural Language interface. A system for communicating with a computer by using a natural language. Natural Language Processing. Processing of natural language (e.g., English) by a computer to facilitate communication with the computer or for other purposes, such as language translation.

اسلاید 24: 24Information Exchange and Visual I/ORecognising and reasoning about the visual environment something that people do extraordinarily well;In these abilities an average three year old makes the most sophisticated computer vision system look embarrassingly inept

اسلاید 25: 25Information Exchange and Visual I/O

اسلاید 26: 26Representation: Production SystemsProduction Systems are a modular knowledge representation scheme and are based on the notion of condition-action pairs, called production rules or just productions: If this condition occurs, then do this action. The utility of the production system formalism comes from the fact that the conditions in which each rule is applicable are made explicit and, in theory at least, the interactions between rules are minimised in the sense that the rules do not call each other.

اسلاید 27: 27Representation: Production SystemsConsider a knowledge-base containing the following rules:Rule#1:IFA&B&CTHENDRule#2:IFD&FTHENGRule#3:IFA&JTHENGRule#4:IFBTHENCRule#5:IFFTHENBRule#6:IFLTHENJRule#7:IFGTHENH.The knowledge-base also contains the following factsFact#1:A.(‘A’ is known to be true)Fact#2:F. (‘F’ is known to be true)

اسلاید 28: 28Representation: Production Systems

اسلاید 29: 29Representation: Production Systems1.Current goal is H 2.Check Database H is not in the database3Find appropriate ruleRule 7 has H as an implication4.Fire rule 7To prove that G is true5.Set G as the current goalStore this information in the Working Memory (WM)6.Cycle through the KB An Example Problem: To prove that H is true? Cycles of Production: FIRST CYCLE

اسلاید 30: 30Representation: Production Systems1.Current goal is G 2.Check Database G is not in the database3Find appropriate ruleRule 2 has G as an implication4.Fire rule 2To prove that D & F are true5.Set D as the current goalStore D (<-G<-H) in the WM & F is TRUE 6.Cycle through the KB An Example Problem: To prove that H is true? Cycles of Production: SECOND CYCLE

اسلاید 31: 31Representation: Production SystemsConsider a knowledge-base containing the following rules:Rule#1:IFA&B&CTHENDRule#2:IFD&FTHENGRule#3:IFA&JTHENGRule#4:IFBTHENCRule#5:IFFTHENBRule#6:IFLTHENJRule#7:IFGTHENH.The knowledge-base also contains the following factsFact#1:A.(‘A’ is known to be true)Fact#2:F. (‘F’ is known to be true)

اسلاید 32: 32Representation: Production Systems1.Current goal is D 2.Check Database D is not in the database3Find appropriate ruleRule 1 has D as an implication4.Fire rule 1To prove that A&B&C are true5.Set A as the current goalStore A in the WM & B&C are to be proven later on 6.Cycle through the KB An Example Problem: To prove that H is true? Cycles of Production: THIRD CYCLE

اسلاید 33: 33Representation: Production Systems1.Current goal is A 2.Check Database A is in the database3Set B as the current goalStore B in the WM 4Cycle through the KB An Example Problem: To prove that H is true? Cycles of Production: FOURTH CYCLE

اسلاید 34: 34Representation: Production SystemsConsider a knowledge-base containing the following rules:Rule#1:IFA&B&CTHENDRule#2:IFD&FTHENGRule#3:IFA&JTHENGRule#4:IFBTHENCRule#5:IFFTHENBRule#6:IFLTHENJRule#7:IFGTHENH.The knowledge-base also contains the following factsFact#1:A.(‘A’ is known to be true)Fact#2:F. (‘F’ is known to be true)

اسلاید 35: 35Representation: Production Systems1.Current goal is B 2.Check Database B is not in the database3Find appropriate ruleRule 5 has B as an implication4.Fire rule 5To prove that F is true, hence B is true5.Set C as the current goalStore C in the WM 6.Cycle through the KB An Example Problem: To prove that H is true? Cycles of Production: FIFTH CYCLE

اسلاید 36: 36Representation: Production Systems1.Current goal is B 2.Check Database C is not in the database3Fire rule 4To prove that B is true, hence C is true4.Goal D is satisfiedHence goal G, and therefore goal H is satisfied 5.S T O P An Example Problem: To prove that H is true? Cycles of Production: SIXTH CYCLE

اسلاید 37: 37Representation: Production SystemsConflict Resolution Rule OrderingArrange rules in list with most important rules higher up the list. Fire rules according to their position in list (highest first).Context LimitingPlace rules in groups, and only have one group ‘active’ at any one time.SpecificityThe specificity principle states that if a number of rules are applicable to a given situation then the rule with the greatest number of condition premises (I.e. the most specific) should be selected to fire.

اسلاید 38: 38Representation: Production SystemsConflict Resolution RefractorinessRefractoriness is another conflict resolution strategy which states that if a rule has been applied on a previous cycle, then it should not be applied again to the same set of facts in data memories. This kind of strategy prevents a system from getting itself entwined in a loop.RecencyThe recency principle is a conflict resolution strategy which states that if more than one rule applies to a given situation, then choose the rule that applies to the most recently entered items in data memory.

اسلاید 39: 39Deduction KBSProblem: Elicit rules from the following descriptionJohnny is an amateur zookeeper and also keeps notes in his diary on the various animals and birds he comes in contact with. His diary contains the following entries: Jan 1, 1992: Mary told me that meat-eating animals with pointed teeth, forward pointing eyes and claws are called carnivores. Like other mammals they give milk. Feb. 15, 1992: I saw two tawny coloured carnivores today, but one had dark spots and the other black stripes. The dark spotted carnivore was called cheetah and the black striped was a tiger. March 20, 1992: We had two new animals delivered to the zoo, a zebra and a giraffe. These hoofed mammals are called ungulates. The zebra has white skin with black stripes on it. The giraffe had long legs and neck, and has the same tawny colour as the tiger but with black spots.

اسلاید 40: 40Deduction KBS

اسلاید 41: 41Deduction KBSHas long legsHas a long neckHas a tawny colourHas dark spotsGives milkHas hoofsFired 1stFired 2ndFired 3rdIs a mammalIs an ungulateIs a giraffeJohnny has been asked to identify a hoofed, long-necked hairy animal, Freddy, which has a tawny colour and dark spots. Use the forward chaining search strategy to draw the inference network which Johnny should use to identify the unknown animal.

اسلاید 42: 42Deduction KBS