人工智能原理人工智能原理 (43).pdf

《人工智能原理人工智能原理 (43).pdf》由会员分享，可在线阅读，更多相关《人工智能原理人工智能原理 (43).pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Artificial IntelligenceBayesian NetworksArtificial Intelligence2 7.5.1 About Uncertain Knowledge 7.5.2 Rational Decisions 7.5.3 Algorithm of a Decision-theoretic Agent 7.5.4 Bayes Rule 7.5.5 Representing Full Joint Distribution 7.5.6 Constructing Bayesian NetworksContentsArtificial Intelligence3 7.5

2、.7 Compactness 7.5.8 Node Ordering 7.5.9 Conditional Independence RelationsContentsArtificial Intelligence:Reasoning:Reasoning by Knowledge4 Evolution of an intelligent agent:problem solving,reasoning,planning and learning.智能体的进化：问题求解、推理、规划以及学习。Agents may need to handle uncertainty,due to partial ob

3、servability and non-determinism.智能体可能需要处理不确定性，由于部分可观察性和不确定性问题。To make decision with uncertainty,we need在不确定性的情况下做出决策，我们需要 Probability theory,概率论，Utility theory,效用论，Decision theory.决策论。About Uncertain Knowledge 关于不确定性知识7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge5A90=

4、home to airport 90 minutes by taxi before flight departs.从家里打车在航班起飞前90分钟到机场 Question:问题“Will A90get me to the airport on time?”A90 能使我准时到达机场吗？Answer:答案The taxi agent concludes either:出租汽车公司给出两个结论中的一个：the risks falsehood:“A90will get us there in time”.有风险的谎言：A90将使我们及时到达机场。the weaker conclusion:“A90wi

5、ll get us there in time,if there is no traffic jam,I dont get into an accident,the car doesnt break down,and.”A90将使我们及时到达机场，如果没有交通堵塞、不出交通事故、汽车不出故障的话，Example:An uncertainty problem 一个不确定性问题7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge6 Probability theory 概率论for dealing

6、 with degrees of belief.是用于处理置信度的理论 Utility theory 效用论the quality of being useful.是有效性的质量 to represent and reason with preferences,every state has a degree of usefulness/utility.用偏好来表现和推理，每个状态都具有“有效性/效用”的度量值。Decision theory 决策论the general theory of rational decisions.是理性决策的通论 Decision theory=probabi

7、lity theory+utility theory决策论=概率论+效用论Rational Decisions 理性决策7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge7Algorithm of a Decision-theoretic Agent 一种决策论智能体的算法7.5.Bayesian NetworksA decision-theoretic agent that selects rational actions.一个选择理性动作的决策论智能体function DECISION-

8、THEORETIC-AGENT(percept)returns an actionpersistent:belief_state,probabilistic beliefs about the current state of the world action,the agents actionupdate belief_state based on action and perceptcalculate outcome probabilities for actions,given action descriptions and current belief_stateselect acti

9、on with highest expected utility,given probabilities of outcomes and utility informationreturn actionArtificial Intelligence:Reasoning:Reasoning by Knowledge8 Product rule 乘积规则 Two ways to factor a joint distribution over two variables:两个变量联合分布的两种计算方法：Bayes rule 贝叶斯规则Bayes Rule 贝叶斯规则7.5.Bayesian Net

10、worksP(b|a)=P(a|b)P(b)P(a)This rule underlies most modern AI for probabilistic inference.这个规则成为大多数现代人工智能概率推理的基础。Why is Bayes rule useful 为什么贝叶斯定理有用 Often we have good probability estimates for three terms to compute the fourth.我们常常需要根据三个项的概率估计值去计算第四个。P(a b)=P(a|b)P(b)and P(a b)=P(b|a)P(a)Artificial

11、Intelligence:Reasoning:Reasoning by Knowledge9 Often we perceive as evidence the effect of some unknown cause,and would like to determine that cause.In that case,Bayes rule becomes我们往往想根据一些未知原因的证据，来查明其原因。这样，贝叶斯定理就变成了Example:Inference with Bayes Rule 贝叶斯规则进行推理7.5.Bayesian Networks Knows P(symptoms|di

12、sease)and want to derive a diagnosis,P(disease|symptoms).已知 P(symptoms 症状|disease 疾病)，想要得出一个诊断 P(疾病|症状)。P(cause|effect)=P(effect|cause)P(cause)P(effect)/conditional probability that meningitis causes a stiff neck 脑膜炎导致颈部僵硬的条件概率/prior probability that a patient has meningitis 病人患脑膜炎的先验概率/prior probab

13、ility that any patient has a stiff neck 任何病人患有颈部僵硬的先验概率P(s|m)=0.7P(m)=1/50000P(s)=0.01P(m|s)=P(s|m)P(m)P(s)=0.71/50000.01=0.0014 /a stiff neck to have meningitis 颈部僵硬患有脑膜炎的概率Artificial Intelligence:Reasoning:Reasoning by Knowledge10 A probabilistic graphical model(a type of statistical model)一种概率图模型

14、（一种统计模型的类型）With a directed acyclic graph(DAG),it represents:a set of random variables,and conditional dependencies between the variables.采用一种有向无环图(DAG)，它表示：一组随机变量，以及变量之间的条件相关性。Its specification:它的规范如下：1)a set of nodes,each corresponds to a random variable,2)a set of directed links to those nodes,and

15、 3)a conditional probability distribution for each node given its parents:1)一组节点，每个节点对应于一个随机变量，2)一组这对这些节点的有向连接，以及 3)每个节点在给定双亲下的条件概率分布:About Bayesian Networks 贝叶斯网络7.5.Bayesian NetworksP(Xi|Parents(Xi)Artificial Intelligence:Reasoning:Reasoning by Knowledge11 The name of Bayesian networks is the most

16、 common one,but there are many synonyms,including:贝叶斯网络这个名称是最常用的，但还有许多同义词，包括：belief network,信念网络 probabilistic network,概率网络 causal network.因果网络 A Bayesian network represents a set of random variables and their conditional dependencies.一个贝叶斯网络表示一组随机变量和他们的条件依赖关系。E.g.,it could represent the probabilist

17、ic relationships between diseases and symptoms.例如：它可以表示疾病与症状之间的概率关系。About Bayesian Networks 贝叶斯网络7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge12 The two views to understand semantics of Bayesian networks:理解贝叶斯网络语义的两个观点：1st:to view the network as a representation of th

18、e joint probability distribution.第一、将该网络视为一种联合概率分布的表示。2nd:to view it as an encoding of a collection of conditional independence statements.第二、将其视为一组条件独立语句的一种编码。The two views are equivalent,but:这两个观点是等价的，但是：1stview:helpful in understanding how to construct networks,第一种观点：有助于理解如何构建网络，2ndview:helpful i

19、n designing inference procedures.第二种观点：有助于设计推理过程。Two Views 两个观点7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge13 A burglar alarm installed at home,used to detect a burglary or minor earthquakes.房子里安装了一个防盗报警器，用于检测被盗或地震。Two neighbors,John and Mary,who have promised to cal

20、l you at work when they hear the alarm.有两个邻居，John和Mary，他们已答应当听到报警时，就给你的办公室打电话。Variables变量:Burglar,Earthquake,Alarm,JohnCalls,MaryCalls.Network topology reflects the knowledge:网络的拓扑结构要反应如下知识:A Burglar or an Earthquake can set the Alarm.盗窃或者地震会导致报警。The Alarm can cause Mary or John to call.报警会引起Mary或Jo

21、hn打电话。Example:A typical Bayesian network 一个典型的贝叶斯网络7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge14Example:A typical Bayesian network 一个典型的贝叶斯网络7.5.Bayesian NetworksA Bayesian network with the conditional probability tables(CPTs).一个具有条件概率表(CPTS)的贝叶斯网络。Where其中 B,E,A,J,M

22、 stand for Burglary,Earthquake,Alarm,JohnCalls,MaryCalls;B,E,A,J,M 代表Burglary,Earthquake,Alarm,JohnCalls,MaryCalls t and f stand for true and false;t 与 f 代表 true 和 false Each row shows one number p for Xi=t,(the number for Xi=f is just 1p).每一行显示 Xi=t 的概率值 p，Xi=f 时概率值则为 1-pArtificial Intelligence:Rea

23、soning:Reasoning by Knowledge15 By the product of the elements of conditional distributions:采用条件分布元素的乘积：Representing Full Joint Distribution 表征全联合分布7.5.Bayesian Networks To illustrate this,we can calculate the probability:Alarm has sounded,but neither a Burglary nor an Earthquake has occurred,and bo

24、th John and Mary call.为了说明，我们可以计算概率：报警响起，但盗窃和地震都未发生，而John和Mary打电话。We multiply entries from the joint distribution:我们依据联合分布，将这些项相乘：where j,m,a,b,e stand for JohnCalls,MaryCalls,Alarm,Burglary,Earthquake.其中 j,m,a,b,e 代表 JohnCalls,MaryCalls,Alarm,Burglary,Earthquake.P(x1,xn)=1P(xi|parents(Xi)P(j,m,a,b,

25、e)=P(j|a)P(m|a)P(a|b e)P(b)P(e)=0.900.700.0010.9990.998=0.000628Artificial Intelligence:Reasoning:Reasoning by Knowledge16 First,rewrite joint distribution in terms of conditional probability,using product rule:首先，用条件概率公式对联合概率进行改写，使用如下乘积规则：Constructing Bayesian Networks 构建贝叶斯网络7.5.Bayesian Networks

26、Then,repeat the process,reducing each conjunctive probability to a conditional probability and a smaller conjunction.We end up with one big product.然后，重复这个过程，将每个合取概率缩减为条件概率和较小的合取。最终得到一个大的乘积。This is called chain rule,for any set of random variables.这被称为对任意一组随机变量的链式法则。P(a b)=P(a|b)P(b)P(x1,xn)=P(xn|xn

27、-1,x1)P(xn-1,x1)P(x1,xn)=P(xn|xn-1,x1)P(xn-1|xn-2,x1)P(x2|x1)P(x1)=1P(xi|xi1,x1)Artificial Intelligence:Reasoning:Reasoning by Knowledge17 The specification of the joint distribution is equivalent to the general assertion that,for every variable Xiin the network,联合分布的规格等同于一般性断言，即：对于网络中的每个变量Xi，Constr

28、ucting Bayesian Networks 构建贝叶斯网络7.5.Bayesian Networksprovided that 假设 The equation says:Bayesian network is a correct representation of domain,only if each node is conditionally independent of its other predecessors in the node ordering,given its parents.该等式说明：贝叶斯网络是域的一个正确表示，仅当给定其父节点，每个节点条件独立于节点序中其它

29、前趋节点时。P(Xi|Xi-1,X1)=P(Xi|Parents(Xi)Parents(Xi)Xi-1,X1XiX1X2Xi-1P(Xi|Xi-1,X1)Artificial Intelligence:Reasoning:Reasoning by Knowledge18 We can satisfy this condition with this methodology:我们可以用如下方法来满足该条件：1.Nodes:First determine the set of variables to model the domain,X1,.,Xn.节点：先确定要对域建模的变量集，X1,.,Xn

30、。2.Links:For i=1 to n do:链接：从i=1至n，做：Choose,from X1,.,Xi-1,a minimal set of parents for Xi.从 X1,.,Xi-1中选择 Xi的父节点的最小集。For each parent insert a link from the parent to Xi.对每个父节点插入一个从该父节点至 Xi的链接。Write down the conditional probability table(CPT),记录 该条件概率表(CPT)，Constructing Bayesian Networks 构建贝叶斯网络7.5.B

31、ayesian NetworksThe parents of node Xishould contain all nodes in X1,.,Xi-1that directly influence Xi.节点 Xi的父辈应该包含直接影响 Xi的 X1,.,Xi-1中的所有节点。P(Xi|Parents(Xi).Artificial Intelligence:Reasoning:Reasoning by Knowledge19 Suppose we have completed the network,except for the choice of parents for MaryCalls.

32、假设除了MaryCalls父节点的选择之外，我们已经完成了该网络。MaryCalls is not directly influenced by a Burglary or an Earthquake.Her calling behavior only through their effect on the alarm.MaryCalls并非直接受盗窃或地震的支配，她打电话的行为只受它们对报警器的影响。Also,given the alarm state,whether John calls has no influence on Marys calling.并且，给定报警状态，John打电话

33、与否并不影响Mary的电话。Therefore,the following conditional independence statement holds:因此，如下条件独立语句成立：Example:A typical Bayesian network 一种典型的贝叶斯网络7.5.Bayesian NetworksP(MaryCalls|JohnCalls,Alarm,Earthquake,Burglary)=P(MaryCalls|Alarm)Artificial Intelligence:Reasoning:Reasoning by Knowledge20 A Bayesian netw

34、ork is far more compact than full joint distribution.Its compactness is a general property of locally structured(also called sparse)systems.贝叶斯网络远比全联合分布紧凑。它的紧凑性是局部结构化（也称为稀疏）系统的一般特性。Compactness 紧凑性7.5.Bayesian Networks In a locally structured system,each subcomponent interacts directly with only a bo

35、unded number of other components.在局部结构化系统中，每个子成分仅直接与其它成分的有限数量打交道。In Bayesian networks,a CPT(conditional probability table)for a Boolean variable with k parents has 2krows.贝叶斯网络中，具有k个父节点的布尔变量的CPT（条件概率表）有2k行。Artificial Intelligence:Reasoning:Reasoning by Knowledge21 Assume there are n Boolean variable

36、s:假设有n个布尔变量：Bayesian networks:贝叶斯网络if each variable has no more than k parents,then the complete network can be specified by n2knumbers.如果每个变量的父节点不超过k个，则全部网络可以用 n2k个数指定。Full joint distribution:全联合分布it contains 2nnumbers.它包含 2n个数。E.g.,suppose n=30 nodes,each with k=5 parents,then例如：设节点n=30，每个具有 k=5 个

37、父节点，则 Bayesian network:n2k=3025=960.Full joint distribution:2n=230=1,073,741,824.Compactness 紧凑性7.5.Bayesian NetworksArtificial Intelligence:Reasoning:Reasoning by Knowledge22 We will get a compact Bayesian network only if choose node ordering well(Fig.a).只有当选择一个好的节点排序（图a），我们才会得到一个紧凑的贝叶斯网络。What happ

38、ens if we choose the wrong order(Fig.b and c).如果我们选择一个差的排序会发生什么（图b和c）。Node Ordering 节点排序7.5.Bayesian Networks(a)A typical Bayesian network.一个典型的贝叶斯网络(b)A bad node ordering 一个差的节点排序：MaryCalls,JohnCalls,Alarm,Burglary,Earthquake.(c)A very bad node ordering一个更差的节点排序：MaryCalls,JohnCalls,Earthquake,Burgl

39、ary,Alarm.(a)(b)(c)Artificial Intelligence:Reasoning:Reasoning by Knowledge23 Numerical semantics:数值语义a node is conditionally independent of its other predecessors,given its parents.一个节点，给定其父节点后，条件独立于其它前趋节点。Conditional Independence Relations 条件独立关系7.5.Bayesian NetworksP(x1,xn)=1P(xi|parents(Xi)Examp

40、le举例where j,m,a,b,e stand for 其中j,m,a,b,e代表JohnCalls,MaryCalls,Alarm,Burglary,Earthquake.P(j,m,a,b,e)=P(j|a)P(m|a)P(a|b e)P(b)P(e)=0.900.700.0010.9990.998=0.000628Artificial Intelligence:Reasoning:Reasoning by Knowledge24 Topological semantics:拓扑语义each node is conditionally independent of its non-de

41、scendants,given its parents.每个节点，给定其父节点后，条件独立于它的非后继节点。Conditional Independence Relations 条件独立关系7.5.Bayesian NetworksNumerical semantics Topological semantics数值语义 拓扑语义A node X is conditionally independent of its non-descendants Zij,given its parents Ui(shown in the gray area).节点X，给定其父节点Ui（灰色区域所示）后，条件

42、独立于它的非后继节点Zij。Artificial Intelligence:Reasoning:Reasoning by Knowledge25 Markov blanket 马尔科夫覆盖a node is conditionally independent of all other nodes in the network,given its Markov blanket(i.e.parents,children,and childrens parents).一个节点，给定其马尔科夫覆盖后，条件独立于网络中的所有其它节点（即：父节点、子节点、以及子节点的其它父节点）。Conditional Independence Relations 条件独立关系7.5.Bayesian NetworksA node X is conditionally independent of all other nodes in the network given its Markov blanket(the gray area).一个节点X，给定马尔科夫覆盖（灰色区域）后，条件独立于网络中的所有其它节点。