Unformatted text preview:

Representations for KBS:Uncertainty & Decision SupportOutlineA Problem with MycinMore ProblemsSome Representations of UncertaintyBackgroundReviewing Bayes TheoremUnderstanding Bayes TheoremIndependence, Conditional IndependenceExamplesNaïve Bayes ModelSequential Bayesian InferenceBipartite GraphsNoisy ORPolytreesBayes NetsExampleComputing with Partial InformationOdds Likelihood FormulationDecision MakingA Decision Making ProblemDecision Flow DiagramsExpected Monetary ValueAveraging Out and Folding BackThe Effect of ObservationCalculating the Updated ProbabilitiesIllustrating EvaluationFinal Value of Decision Flow DiagramMaximum EntropyMaximum EntropySummaryRepresentations for KBS:Uncertainty & Decision Support6.871 -- Lecture 106.871 - Lecture 101Outline• A Problem with Mycin• Brief review of history of uncertainty in AI• Bayes Theorem• Some tractable Bayesian situations• Bayes Nets • Decision Theory and Rational Choice• A recurring theme: battling combinatorics through model assumptions6.871 - Lecture 102A Problem with Mycin• Its notion of uncertainty seems broken– In Mycin the certainty factor for OR is Max• CF (OR A B) = (Max (Cf A) (Cf B))• Consider – Rule-1 IF A then C, certainty factor 1– Rule-2 If B then C, certainty factor 1 – This is logically the same asIf (Or A B) then C, certainty factor 16.871 - Lecture 103More Problems• If CF(A) = .8 and CF(B) = .3AÆCBÆCA or BÆC•IF A Æ B, A Æ C, B Æ D, C Æ D there will also be a mistake: (why?)BCAD6.871 - Lecture 10Then CF (C ) = .8 + .3 * (1 - .8) = .8 + .06 = .86CF (OR A B) = (Max .8 .3) = .8 and CF(C ) = .84Some Representations of Uncertainty• Standard probability– too many numbers• Focus on logical, qualitative– reasoning by cases– non-monotonic reasoning• Numerical approaches retried– Certainty factors– Dempster-Schafer–Fuzzy• Bayes Networks6.871 - Lecture 105BackgroundDSDConditional Probability of S given DP(S | D) =P(S & D)P(D)U)(*)|()&( DPDSPDSP=6.871 - Lecture 106Reviewing Bayes TheoremSymptom S1)()( =∑iiiDPthatsuchDstateshealthDiseasesConditional Probability of S given DDSDUP(S | D) =P(S & D)P(D)P(D| S) =P(S&D)P(S)P(S) = P(S & D) + P(S & D)P(S) = P(D)P(S | D)+P(D)P(S | D)P(D| S) =P(S | D)P(D)P(S)6.871 - Lecture 10P(Di|S)=P(S| Di)×P(Di)P(S)P(S) = P(Dj) × P(S|Dj)j∑7Understanding Bayes TheoremHas it and tests for it10 • .95 = 9.5Has Cancer?Test?Test?Yes: 10No: 990Positive: .95Has it and doesn’t test for itDoesn’t have it but tests for it990 • .05 = 49.5Doesn’t have it and doesn’t test for itNumber that test positive If you test positive your probability of having cancer is?6.871 - Lecture 108Independence, Conditional Independence• Independence: P(A&B) = P(A) • P(B)– A varies the same within B as it does in the universe• Conditional independence within CP(A&B|C) = P(A|C) • P(B|C)– When we restrict attention to C, A and B are independent6.871 - Lecture 109ExamplesBA’DACBA and B are independentA’ and B are dependentA and B are conditionallydependent, given CA’ and B are conditionallyindependent, given C.6.871 - Lecture 1010Naïve Bayes ModelDS1SK• Single disease, multiple symptoms• N symptoms means how many probabilities?• Assume symptoms conditionally independent– now P(S1,S2|D) = P(S1|D) * P(S2|D)•Now?6.871 - Lecture 1011Sequential Bayesian Inference• Consider symptoms one by one– Prior probabilities P(Di)– Observe symptom Sj– Updates priors using Bayes Rule:– Repeat for other symptoms using the resulting posterior as the new prior• If symptoms are conditionally independent, same as doing it all at once• Allows choice of what symptom to observe (test to perform) next in terms of cost/benefit.P(Di) =P(Sj|Di)×P(Di)P(Sj)6.871 - Lecture 1012Bipartite GraphsD1D2D3S1S2S3S4• Multiple symptoms, multiple diseases• Diseases are probabilistically independent• Symptoms are conditionally independent• Symptom probabilities depend only the diseases causing them• Symptoms with multiple causes require joint probabilities P(S2|D1,D2,D3)6.871 - Lecture 1013Noisy ORAnother element in the modeling vocabularyAssumption: only 1 disease is present at a time• Probability that all diseases cause the symptom is just the probability that at least 1 does• Therefore: Symptom is absent only if no disease caused it.• Reduces probability table size: if n diseases and k symptoms, from k2^n to nk1 - P(S2|D1,D2,D3) = (1 - P(S2|D1)) * (1 - P(S2|D2)) * (1 - P(S2|D3)) 6.871 - Lecture 1014Polytrees• What if diseases do cause or influence each other?• Are there still well behaved versions?• Polytrees: At most one path between any two nodes– Don’t have to worry about “double-counting”• Efficient sequential updating is still possibleD1D2D3S1S5S2S4S36.871 - Lecture 1015Bayes NetsBAEDC• Directed Acyclic Graphs• Absence of link Æconditional independence• P(X1,...,Xn) = Product P(Xi|{parents (Xi)})• Specify joint probability tables over parents for each nodeProbability A,B,C,D,E all true:P(A,B,C,D,E) = P(A) * P(B|A) * P(C|A) * P(D|B,C) * P(E|C)Probability A,C,D true; B,E false:P(A,B’,C,D,E’) = P(A) * P(B’|A) * P(C|A) * P(D|B’,C) * P(E’|C)6.871 - Lecture 1016ExampleBurglary EarthquakeAlarmRadio ReportPhone CallP(Call|Alarm)tftf.9 .01.1 .99P(RadioReport|Earthquake)tftf1001P(Alarm|B,E)t,t t,ftf.8 .99.2 .01f,tf,f.6 .01.4 .9916 vs. 32 probabilites6.871 - Lecture 1017Computing with Partial Information• Probability that A true and E false:BAEDC• Graph separators (e.g. C) correspond to factorizations• General problem of finding separators is NP-hardP(A, E) = P( A,B,C, D, EB,C, D∑)= P( A)P(B | A)P(C | A)P(D | B,C)P(E| C)B,C, D∑= P(A) P(C | A)P(E|C) P(B| A) P(D | B,C)D∑B∑C∑Normally have to do 2^3 computations of the entire formula.By factoring can do 2^3 computations of last term, 2 of second 2, 2 of firstSum over c doesn’t change when D changes, etc.6.871 - Lecture 1018Odds Likelihood Formulation• Define odds as• Define likelihood as:O(D) =P(D)P(D)=P(D)1− P(D)L(S | D) =P(S | D)P(S | D)Derive complementary instances of Bayes Rule:P(D| S) =P(D)P(S | D)P(S)P(D| S) =P(D)P(S | D)P(S)P(D| S)P(D| S)=P(D)P(S | D)P(D)P(S | D)O(D|S)=O(D)L(S|D)Bayes Rule is Then:6.871 - Lecture 10In Logarithmic Form: Log Odds = Log Odds + Log Likelihood19Decision Making• So far: how to use evidence to evaluate a situation.– In many cases, this is only the beginning• Want to take actions to improve the


View Full Document

MIT 6 871 - Uncertainty & Decision Support

Download Uncertainty & Decision Support
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Uncertainty & Decision Support and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Uncertainty & Decision Support 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?