ch13 不确定性 人工智能课程 北大计算机研究所

1、第十三章、不确定性p不确定环境下的行动p不确定性推理的方法p概率公理p使用全概率分布进行推理p独立性p贝叶斯法则及其应用UncertaintyLet action At = leave for airport t minutes before flightWill At get me there on time?Problems:partial observability (road state, other drivers plans, etc.)noisy sensors (traffic reports)uncertainty in action outcomes (flat tire,

2、 etc.)immense complexity of modeling and predicting trafficHence a purely logical approach eitherrisks falsehood: “A25 will get me there on time”, orleads to conclusions that are too weak for decision making:“A25 will get me there on time if theres no accident on the bridge and it doesnt rain and my

3、 tires remain intact etc etc.”(A1440 might reasonably be said to get me there on time but Id have to stay overnight in the airport )关于不确定性的推理p必要性：处理智能体的精度和有效性的折中p理性决策的含义l假设A90是智能体该做的事，这意味着在给定所拥有的环境信息下，它是所有可以被执行的规划中被期望能够使智能体的性能度量达到最大的那个。及时赶上飞机、等待时间不长，第十三章、不确定性p不确定环境下的行动p不确定性推理的方法l概率p概率公理p使用全概率分布进行推理p

4、独立性p贝叶斯法则及其应用Methods for handling uncertaintypDefault or nonmonotonic logic (Section 10.7)lAssume my car does not have a flat tirelAssume A25 works unless contradicted by evidencepIssues: What assumptions are reasonable? How to handle contradiction?pRules with fudge factorslA25 |0.3 get there on tim

5、elSprinkler | 0.99 WetGrasslWetGrass | 0.7 RainpIssues: Problems with combination, e.g., Sprinkler causes Rain?pDempster-Shafer theorylUse interval-valued degrees of belief to represent an agents knowledge of the probability of a propositionlEx: coin flipping, the interval for Head is 0.1 before exp

6、ert testimony and 0.45,0.55 after.pFuzzy logic: an event can be “sort of”vagueness, different from uncertainty.Methods for handling uncertainty (contd)pProbabilitylModel agents degree of belieflEx: Given the available evidence,A25 will get me there on time with probability 0.04ProbabilityProbabilist

7、ic assertions summarize effects ofllaziness: failure to enumerate exceptions, qualifications, etc.lignorance: lack of relevant facts, initial conditions, etc.Subjective probability:pProbabilities relate propositions to agents own state of knowledgee.g., P(A25 | no reported accidents) = 0.06These are

8、 not assertions about the world, but the agents beliefs.Probabilities of propositions change with new evidence:e.g., P(A25 | no reported accidents, 5 a.m.) = 0.15客观主义者对概率的看法p概率是宇宙的真实方面：它是物体的行为表现为特定方式的倾向，而不仅仅是对观察者信心的描述l频率主义者的观点：断言“有牙洞的概率是0.1”意味着0.1是在无穷多样本的极限条件下能够被观察到的比例，但l即使是严格的频率主义者的见解也涉及到主观分析refere

9、nce class在许多情景下不可能进行重复试验Make decisions under uncertainty (rep by probability)Suppose I believe the following:P(A25 gets me there on time | ) = 0.04 P(A90 gets me there on time | ) = 0.70 P(A120 gets me there on time | ) = 0.95 P(A1440 gets me there on time | ) = 0.9999 pWhich action to choose?Depend

10、s on my preferences for missing flight vs. time spent waiting, etc.lUtility theory is used to represent and infer preferenceslDecision theory = probability theory + utility theory第十三章、不确定性p不确定环境下的行动p不确定性推理的方法l概率p概率公理p使用全概率分布进行推理p独立性p贝叶斯法则及其应用Axioms of probabilitypFor any propositions A, Bl0 P(A) 1lP

11、(true) = 1 and P(false) = 0lP(A B) = P(A) + P(B) - P(A B)Axioms of probability (traditional)pFor any propositions A, 0 P(A) pP(true) = 1pFor infinitely many mutual disjoint propositions A1, A2, An, )()(11iiiiAPAP为什么概率公理是合理的？p例如，为什么智能体可以不支持如下的信度集合:P(A)=0.4, P(B)=0.3, P(AB) =0.8, and P(AB) =0.pBruno d

12、e Finetti的论点（1931）：如果智能体1表达了一组违反概率理论公理的信度，那么存在一个赌局的组合保证智能体2每次都能赢智能体1的钱。l例子：图13.2第十三章、不确定性p不确定环境下的行动p不确定性推理的方法l概率p概率公理p使用全概率分布进行推理p独立性p贝叶斯法则及其应用Inference by enumerationpStart with the joint probability distribution:l表中catch是指由于牙医的钢探针不洁而导致的牙龈感染pFor any proposition , sum the atomic events where it is t

13、rue: P() = : P()Inference by enumerationpStart with the joint probability distribution:pFor any proposition , sum the atomic events where it is true: P() = : P()pP(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2Inference by enumeration Start with the joint probability distribution: Can also compute

14、 conditional probabilities:P(cavity | toothache) = P(cavity toothache)P(toothache)= 0.016+0.064 0.108 + 0.012 + 0.016 + 0.064= 0.4NormalizationDenominator can be viewed as a normalization constant P(Cavity | toothache) = P(Cavity,toothache) = P(Cavity,toothache,catch) + P(Cavity,toothache, catch)= +

15、 = = General idea: compute distribution on query variable by fixing evidence variables and summing over hidden variablesInference by enumeration (contd)Typically, we are interested in the posterior joint distribution of the query variables Y given specific values e for the evidence variables ELet th

16、e hidden variables be H = X - Y - EThen the required summation of joint entries is done by summing out the hidden variables:P(Y | E = e) = P(Y,E = e) = hP(Y,E= e, H = h)pThe terms in the summation are joint entries because Y, E and H together exhaust the set of random variablespObvious problems:Wors

17、t-case time complexity O(dn) where d is the largest aritySpace complexity O(dn) to store the joint distribution1.How to find the numbers for O(dn) entries?第十三章、不确定性p不确定环境下的行动p不确定性推理的方法l概率p概率公理p使用全概率分布进行推理p独立性p贝叶斯法则及其应用IndependenceA and B are independent iffP(A|B) = P(A) or P(B|A) = P(B) or P(A, B) =

18、 P(A) P(B)P(Toothache, Catch, Cavity, Weather)= P(Toothache, Catch, Cavity) P(Weather)32 entries reduced to 12 (weather has 4 possible values); for n independent biased coins, O(2n) O(n)Absolute independence powerful but rareDentistry is a large field with hundreds of variables, none of which are in

19、dependent. What to do?Conditional independenceP(Toothache, Cavity, Catch) has 23 1 = 7 independent entriesIf I have a cavity, the probability that the probe catches in it doesnt depend on whether I have a toothache:(1) P(catch | toothache, cavity) = P(catch | cavity)The same independence holds if I

20、havent got a cavity:(2) P(catch | toothache,cavity) = P(catch | cavity)Catch is conditionally independent of Toothache given Cavity:P(Catch | Toothache,Cavity) = P(Catch | Cavity)Equivalent statements:P(Toothache | Catch, Cavity) = P(Toothache | Cavity)P(Toothache, Catch | Cavity) = P(Toothache | Ca

21、vity) P(Catch | Cavity)Conditional independence contd. Write out full joint distribution using chain rule:P(Toothache, Catch, Cavity)= P(Toothache | Catch, Cavity) P(Catch, Cavity)= P(Toothache | Catch, Cavity) P(Catch | Cavity) P(Cavity)= P(Toothache | Cavity) P(Catch | Cavity) P(Cavity)I.e., 2 + 2

22、 + 1 = 5 independent numbers In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n. Conditional independence is our most basic and robust form of knowledge about uncertain environments.第十三章、不确定性p不确定环境下

23、的行动p不确定性推理的方法l概率p概率公理p使用全概率分布进行推理p独立性p贝叶斯法则及其应用Bayes RulepProduct rule P(ab) = P(a | b) P(b) = P(b | a) P(a) Bayes rule: P(a | b) = P(b | a) P(a) / P(b)por in distribution form P(Y|X) = P(X|Y) P(Y) / P(X) = P(X|Y) P(Y)pUseful for assessing diagnostic probability from causal probability:lP(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect)lE.g., let M be meningi