第 1 页
Lecture 3Lecture 3 Uncertainty management in rule-Uncertainty management in rule- based expert systemsbased expert systems Introduction, or what is uncertainty?Introduction, or what is uncertainty? Basic probability theoryBasic probability theory Bayesian reasoningBayesian reasoning Bias of the Bayesian methodBias of the Bayesian method Certainty factors theory and evidentialCertainty factors theory and evidential reasoningreasoning SummarySummary Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 1
第 2 页
Introduction, or what is uncertainty?Introduction, or what is uncertainty? Information can be incomplete, inconsistent,Information can be incomplete, inconsistent, uncertain, or all three. In other words, informationuncertain, or all three. In other words, information is often unsuitable for solving a problem.is often unsuitable for solving a problem. UncertaintyUncertainty is defined as the lack of the exactis defined as the lack of the exact knowledge that would enable us to reach a perfectlyknowledge that would enable us to reach a perfectly reliable conclusion. Classical logic permits onlyreliable conclusion. Classical logic permits only exact reasoning. It assumes that perfect knowledgeexact reasoning. It assumes that perfect knowledge always exists and thealways exists and the law of the excluded middlelaw of the excluded middle can always be applied:can always be applied: IFIF AA is trueis true IFIF AA is falseis false THENTHEN AA is not falseis not false THENTHEN AA is not trueis not true Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 2
第 3 页
Sources of uncertain knowledgeSources of uncertain knowledge Weak implicationsWeak implications.. Domain experts andDomain experts and knowledge engineers have the painful task ofknowledge engineers have the painful task of establishing concrete correlations between IFestablishing concrete correlations between IF (condition) and THEN (action) parts of the rules.(condition) and THEN (action) parts of the rules. Therefore, expert systems need to have the abilityTherefore, expert systems need to have the ability to handle vague associations, for example byto handle vague associations, for example by accepting the degree of correlations as numericalaccepting the degree of correlations as numerical certainty factors.certainty factors. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 3
第 4 页
Imprecise languageImprecise language.. Our natural language isOur natural language is ambiguous and imprecise. We describe facts withambiguous and imprecise. We describe facts with such terms assuch terms as oftenoften andand sometimessometimes,, frequentlyfrequently andand hardly everhardly ever. As a result, it can be difficult to. As a result, it can be difficult to express knowledge in the precise IF-THEN form ofexpress knowledge in the precise IF-THEN form of production rules. However, if the meaning of theproduction rules. However, if the meaning of the facts is quantified, it can be used in expert systems.facts is quantified, it can be used in expert systems. In 1944, Ray Simpson asked 355 high school andIn 1944, Ray Simpson asked 355 high school and college students to place 20 terms likecollege students to place 20 terms like oftenoften on aon a scale between 1 and 100. In 1968, Milton Hakelscale between 1 and 100. In 1968, Milton Hakel repeated this experiment.repeated this experiment. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 4
第 5 页
Quantification of ambiguous and impreciseQuantification of ambiguous and imprecise terms on a time-frequency scaleterms on a time-frequency scale Ray Simpson (1944) Milton Hakel (1968) Term Mean value Term Mean value Always 99 Always 100 Very often 88 Very often 87 Usually 85 Usually 79 Often 78 Often 74 Generally 78 Rather often 74 Frequently 73 Frequently 72 Rather often 65 Generally 72 About as often as not 50 About as often as not 50 Now and then 20 Now and then 34 Sometimes 20 Sometimes 29 Occasionally 20 Occasionally 28 Once in a while 15 Once in a while 22 Not often 13 Not often 16 Usually not 10 Usually not 16 Seldom 10 Seldom 9 Hardly ever 7 Hardly ever 8 Very seldom 6 Very seldom 7 Rarely 5 Rarely 5 Almost never 3 Almost never 2 Never 0 Never 0 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 5
第 6 页
Unknown dataUnknown data.. When the data is incomplete orWhen the data is incomplete or missing, the only solution is to accept the valuemissing, the only solution is to accept the value “unknown” and proceed to an approximate“unknown” and proceed to an approximate reasoning with this value.reasoning with this value. Combining the views of different expertsCombining the views of different experts.. LargeLarge expert systems usually combine the knowledge andexpert systems usually combine the knowledge and expertise of a number of experts. Unfortunately,expertise of a number of experts. Unfortunately, experts often have contradictory opinions andexperts often have contradictory opinions and produce conflicting rules. To resolve the conflict,produce conflicting rules. To resolve the conflict, the knowledge engineer has to attach a weight tothe knowledge engineer has to attach a weight to each expert and then calculate the compositeeach expert and then calculate the composite conclusion. But no systematic method exists toconclusion. But no systematic method exists to obtain these weights.obtain these weights. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 6
第 7 页
Basic probability theoryBasic probability theory The concept of probability has a long history thatThe concept of probability has a long history that goes back thousands of years when words likegoes back thousands of years when words like “probably”, “likely”, “maybe”, “perhaps” and“probably”, “likely”, “maybe”, “perhaps” and “possibly” were introduced into spoken languages.“possibly” were introduced into spoken languages. However, the mathematical theory of probabilityHowever, the mathematical theory of probability was formulated only in the 17th century.was formulated only in the 17th century. TheThe probabilityprobability of an event is the proportion ofof an event is the proportion of cases in which the event occurs. Probability cancases in which the event occurs. Probability can also be defined as aalso be defined as a scientific measure of chancescientific measure of chance.. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 7
第 8 页
Probability can be expressed mathematically as aProbability can be expressed mathematically as a numerical index with a range between zero (annumerical index with a range between zero (an absolute impossibility) to unity (an absoluteabsolute impossibility) to unity (an absolute certainty).certainty). Most events have a probability index strictlyMost events have a probability index strictly between 0 and 1, which means that each event hasbetween 0 and 1, which means that each event has at leastat least two possible outcomes: favourable outcometwo possible outcomes: favourable outcome or success, and unfavourable outcome or failure.or success, and unfavourable outcome or failure. ( ) the number of successes P success = the number of possible outcomes ( ) the number of failures P failure = the number of possible outcomes Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 8
第 9 页
IfIf ss is the number of times success can occur, andis the number of times success can occur, and ff is the number of times failure can occur, thenis the number of times failure can occur, then ( ) s P success = p = s + f ( ) f P failure = q = s + f andand p + q = 1 If we throw a coin, the probability of getting a headIf we throw a coin, the probability of getting a head will be equal to the probability of getting a tail. In awill be equal to the probability of getting a tail. In a single throw,single throw, ss == ff = 1, and therefore the probability= 1, and therefore the probability of getting a head (or a tail) is 0.5.of getting a head (or a tail) is 0.5. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 9
第 10 页
Conditional probabilityConditional probability LetLet AA be an event in the world andbe an event in the world and BB be another event.be another event. Suppose that eventsSuppose that events AA andand BB are not mutuallyare not mutually exclusive, but occur conditionally on the occurrence ofexclusive, but occur conditionally on the occurrence of the other. The probability that eventthe other. The probability that event AA will occur ifwill occur if eventevent BB occurs is called theoccurs is called the conditional probabilityconditional probability.. Conditional probability is denoted mathematically asConditional probability is denoted mathematically as pp((AA||BB) in which the vertical bar represents) in which the vertical bar represents GIVENGIVEN andand the complete probability expression is interpreted asthe complete probability expression is interpreted as “Conditional probability of event A occurring given“Conditional probability of event A occurring given that event B has occurred”that event B has occurred”.. ( ) the number of times Aand B canoccur p AB = the number of times B canoccur Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 10
第 11 页
The number of timesThe number of times AA andand BB can occur, or thecan occur, or the probability that bothprobability that both AA andand BB will occur, is calledwill occur, is called thethe joint probabilityjoint probability ofof AA andand BB. It is represented. It is represented mathematically asmathematically as pp((AA∩∩BB). The number of ways). The number of ways BB can occur is the probability ofcan occur is the probability of BB,, pp((BB), and thus), and thus ( ) p(A∩ B) p AB = ( ) p B Similarly, the conditional probability of eventSimilarly, the conditional probability of event BB occurring given that eventoccurring given that event AA has occurred equalshas occurred equals ( ) p(A∩ B) p AB = ( ) p B Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 11
第 12 页
Hence,Hence, p(B∩ A)= p(B A)× p( )A andand p(A∩ B)= p(B A)× p( )A Substituting the last equationSubstituting the last equation into the equationinto the equation ( ) p(A∩ B) p AB = ( ) p B yields theyields the Bayesian ruleBayesian rule:: Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 12
第 13 页
Bayesian ruleBayesian rule ( ) p(B A)× p( )A p AB = ( ) p B where: p(A|B) is the conditional probability that event A occurs given that event B has occurred; p(B|A) is the conditional probability of event B occurring given that event A has occurred; p(A) is the probability of event A occurring; p(B) is the probability of event B occurring. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 13
第 14 页
The joint probabilityThe joint probability n n ( ) ∑ p(A∩ Bi )= ∑ p ABi × p(Bi ) i=1 i=1 A B1 B4 B3 B2 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 14
第 15 页
If the occurrence of eventIf the occurrence of event AA depends on only twodepends on only two mutually exclusive events,mutually exclusive events, BB and NOTand NOT BB, we obtain:, we obtain: p(A) = p(A|B) × p(B) + p(A|¬B) × p(¬B) wherewhere ¬¬ is the logical function NOT.is the logical function NOT. Similarly,Similarly, p(B) = p(B|A) × p(A) + p(B|¬A) × p(¬A) Substituting this equation into the Bayesian rule yields:Substituting this equation into the Bayesian rule yields: ( ) p(B A)× p( )A p AB = ( ) ( ) ( ) ( ) p B A × p A + p B¬A × p ¬A Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 15
第 16 页
Bayesian reasoningBayesian reasoning Suppose all rules in the knowledge base areSuppose all rules in the knowledge base are represented in the following form:represented in the following form: IFIF HH is trueis true THENTHEN EE is true {with probabilityis true {with probability pp}} This rule implies that if eventThis rule implies that if event HH occurs, then theoccurs, then the probability that eventprobability that event EE will occur iswill occur is pp.. In expert systems,In expert systems, HH usually represents a hypothesisusually represents a hypothesis andand EE denotes evidence to support this hypothesis.denotes evidence to support this hypothesis. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 16
第 17 页
The Bayesian rule expressed in terms of hypothesesThe Bayesian rule expressed in terms of hypotheses and evidence looks like this:and evidence looks like this: ( ) p(E H)× p(H) p H E = ( ) ( ) ( ) ( ) p E H × p H + p E ¬H × p ¬H where:where: pp((HH) is the prior probability of hypothesis) is the prior probability of hypothesis HH being true;being true; pp((EE||HH) is the probability that hypothesis) is the probability that hypothesis HH being true willbeing true will result in evidenceresult in evidence EE;; pp((¬¬HH) is the prior probability of hypothesis) is the prior probability of hypothesis HH beingbeing false;false; pp((EE|¬|¬HH) is the probability of finding evidence) is the probability of finding evidence EE eveneven when hypothesiswhen hypothesis HH is false.is false. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 17
第 18 页
In expert systems, the probabilities required to solveIn expert systems, the probabilities required to solve a problem are provided by experts. An experta problem are provided by experts. An expert determines thedetermines the prior probabilitiesprior probabilities for possiblefor possible hypotheseshypotheses pp((HH) and) and pp((¬¬HH), and also the), and also the conditional probabilitiesconditional probabilities for observing evidencefor observing evidence EE if hypothesisif hypothesis HH is true,is true, pp((EE||HH), and if hypothesis), and if hypothesis HH is false,is false, pp((EE|¬|¬HH).). Users provide information about the evidenceUsers provide information about the evidence observed and the expert system computesobserved and the expert system computes pp((HH||EE) for) for hypothesishypothesis HH in light of the user-supplied evidencein light of the user-supplied evidence EE. Probability. Probability pp((HH||EE) is called the) is called the posteriorposterior probabilityprobability of hypothesisof hypothesis HH upon observingupon observing evidenceevidence EE.. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 18
第 19 页
We can take into account both multiple hypothesesWe can take into account both multiple hypotheses HH ,, HH ,...,,..., HH and multiple evidencesand multiple evidences EE ,, EE ,...,,..., EE .. 11 22 mm 11 22 nn The hypotheses as well as the evidences must beThe hypotheses as well as the evidences must be mutually exclusive and exhaustive.mutually exclusive and exhaustive. Single evidenceSingle evidence EE and multiple hypothesesand multiple hypotheses follow:follow: ( ) p(E H )× p(H ) p H E = i i i m ∑ p(E H )× p(H ) k k k=1 Multiple evidences and multiple hypothesesMultiple evidences and multiple hypotheses follow:follow: ( ) p(E E ...E H )× p(H ) p H E E ...E = 1 2 n i i i 1 2 n m ∑ p(E E ...E H )× p(H ) 1 2 n k k k=1 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 19
第 20 页
This requires to obtain the conditional probabilitiesThis requires to obtain the conditional probabilities of all possible combinations of evidences for allof all possible combinations of evidences for all hypotheses, and thus places an enormous burdenhypotheses, and thus places an enormous burden on the expert.on the expert. Therefore, in expert systems, conditionalTherefore, in expert systems, conditional independence among different evidences assumed.independence among different evidences assumed. Thus, instead of the unworkableThus, instead of the unworkable equationequation, we, we attain:attain: ( ) p(E H )× p(E H )×...× p(E H )× p(H ) p H E E ...E = 1 i 2 i n i i i 1 2 n m ∑ p(E H )× p(E H )×...× p(E H )× p(H ) 1 k 2 k n k k k=1 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 20
评论 (0)
暂无评论。快来抢沙发吧！