逻辑推理人工智能.pptx

,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,逻辑推理人工智能,不确定性,不确定环境下得行动,概率公理,使用全概率分布进行推理,独立性,贝叶斯法则及其应用,不确定性(,Uncertainty,),定义行动,A,t,=,航班起飞前,t,分钟启程前往机场;,问:,A,t,能不能及时使,agent,赶上飞机？,A,180,就是一个可靠得行动,如果所选路线上没有交通事故、没有交通管制、汽车没有出故障、没有沙尘暴,等等,等等。,(,A,1440,或许就是个一定不会耽误飞机得计划,不过要在机场过夜,),逻辑方法使得,Agent,在得到关于环境得足够多事实时,使得行动计划得到保证。,但就是,没有任何,agent,能够获得关于其环境得全部事实。,FOL,与不确定性,FOL,能够处理不确定性吗？,医学专家系统:,p,Symptom(p,Toothache),Disease(p,Cavity)?,引起牙痛得原因:牙洞？穷举,牙洞与牙痛有必然联系吗？,失败得原因:,懒惰,(laziness):failure to enumerate exceptions,qualifications,etc、,无知,(ignorance):lack of relevant facts,initial conditions,etc、,不确定环境下得决策,基本思想:,精确度和有效性得折中,理性决策,得含义,既依赖于各种目标得相对重要性,也依赖于这些目标将被实现得可能性(程度)。,假设,A,180,理性决策,这意味着在给定所处得环境信息下,她就是所有可执行得规划中智能体得性能度量期望达到最大得那个。,性能度量:及时赶上飞机、等待时间不长,不确定环境下得决策,例如:给出行动及其成功得概率如下,:,P(A,25,gets me there on time|,)=0、04,P(A,90,gets me there on time|,)=0、70,P(A,120,gets me there on time|,)=0、95,P(A,1440,gets me there on time|,)=0、9999,该选哪一个行动,?,例如,取决于成功得几率以及等待时间得折中。,必须考虑效用理论(,Utility theory,),决策论概率论效用论,Decision theory=probability theory+utility theory,不确定性,不确定环境下得行动,概率公理,使用全概率分布进行推理,独立性,贝叶斯法则及其应用,概率理论(,Probability theory,),Agent,得知识提供得最多就是关于语句得信度(,degree of belief,)。,概率论可以处理我们得惰性和无知。,概率就是宇宙得真实方面:她就是物体得行为表现为特定方式得倾向,而不仅仅就是对观察者信心得描述。,概率与证据:,在评估语句得概率时,必须指出有关证据。,Agent,获得新得信息后,其概率评估应该更新。,先验概率、后验概率,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,先验概率,与命题,a,相关得无条件概率,在没有任何其她信息存在得情况下,关于命题得信度,记为:,P,(,a,)。,例如,用,P,(,weather,)表示天气得概率:,P,(,weather,sunny,),0、7,P,(,weather,rain,),0、2,P,(,weather,cloudy,),0、08,P,(,weather,snow,),0、02,先验概率分布:,P,(,weather,),联合概率分布,全联合概率分布,概率密度函数,后验(条件)概率,得到与命题,a,相关得变量得证据,先验概率失效,需要以后验概率替代,记为:,P,(,a|b,),例如:,P,(,cavity|toothache,),0、7,乘法规则:,P,(,a,b,),P,(,b,|,a,),P,(,a,),概率公理(,Axioms of probability,),对任意命题,A,B:,0,P(,A,),1,P(,true,)=1,P(,false,)=0,P(,A,B,)=P(,A,)+P(,B,)-P(,A,B,),Kolmogorov,公理,不确定性,不确定环境下得行动,概率公理,使用全概率分布进行推理,独立性,贝叶斯法则及其应用,联合概率分布,联合概率分布(,joint,probability,distribution,),:,表中,catch,就是指由于牙医得钢探针不洁而导致得牙龈感染,对任何命题,其概率就是所有原子证据事件概率得和:,P(,)=,:,P(,),联合概率分布(枚举),Start with the joint probability distribution:,For any proposition,sum the atomic events where it is true:P(,)=,:,P(,)P(,toothache,)=0、108+0、012+0、016+0、064=0、2,Start with the joint probability distribution,Can also pute conditional probabilities:,P(,cavity,|,toothache,)=P(,cavity,toothache,),P(,toothache,),=0、016+0、064,0、108+0、012+0、016+0、064,=0、4,联合概率分布(枚举),归一化(,Normalization,),(Denominator),-1,normalization constant,P,(,Cavity|toothache,)=,P,(,Cavity,toothache,),=,P,(,Cavity,toothache,catch,)+,P,(,Cavity,toothache,catch,),=,+,=,General idea:pute distribution on query variable by fixing evidence variables and summing over hidden variables、,不确定性,不确定环境下得行动,概率公理,使用全概率分布进行推理,独立性,贝叶斯法则及其应用,独立性(,Independence,),A,与,B,独立,当且仅当,P,(,A|B,)=,P,(,A,)or,P,(,B|A,)=,P,(,B,)or,P,(A,B)=,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(2,n,),O(n),绝对独立很好但很少见,例如牙科中可能涉及几百相互关联得变量,这时候如何处理？,条件独立(,Conditional independence,),已知有一个牙洞,钻具感染与牙疼得概率相互独立:,钻具感染与牙痛在给定牙洞得情况下就是条件独立得,conditionally independent,P,(,Toothache,Catch|Cavity,),=,P,(,Toothache|Cavity,),P,(,Catch|Cavity,),条件独立,推导联合分布,将全联合分布分解成很多更小得分布,:,P,(,Toothache,Catch,Cavity,),=,P,(,Toothache,Catch|Cavity,),P,(,Cavity,),乘法法则,=,P,(,Toothache|Cavity,),P,(,Catch|Cavity,),P,(Cavity),条件独立,I、e、,2+2+1=5 independent numbers,条件分布将联合分布得表示空间由指数级降到线性。,条件概率就是处理不确定信息得基础和最鲁棒得形式。,不确定性,不确定环境下得行动,概率公理,使用全概率分布进行推理,独立性,贝叶斯法则及其应用,贝叶斯法则(,Bayes,Rule,),由乘法法则,P(a,b)=P(a|b)P(b)=P(b|a)P(a),Bayes rule:P(a|b)=P(b|a)P(a)/P(b),一般形式:,P,(Y|X)=,P,(X|Y),P,(Y)/,P,(X)=,P,(X|Y),P,(Y),例子:用于从病因(,causal,)中找到诊断(,diagnostic,)结论,:,P(Cause|Effect)=P(Effect|Cause)P(Cause)/P(Effect),E、g、,let,M,be meningitis,S,be stiff neck:,P(m|s)=P(s|m)P(m)/P(s)=0、8,0、0001/0、1=0、0008,贝叶斯法则与条件独立,P,(,Cavity|toothache,catch,),=,P,(,toothache,catch|Cavity,),P,(,Cavity,),=,P,(,toothache|Cavity,),P,(,catch|Cavity,),P,(,Cavity,),This is an example of a na,ve Bayes,(朴素贝叶斯),model:,P,(Cause,Effect,1,Effect,n,)=,P,(Cause),i,P,(Effect,i,|Cause),Total number of parameters is linear in,n,贝叶斯网络,1,贝叶斯网络概述,2,贝叶斯网络得语义,3,贝叶斯网络中得精确推理,4,贝叶斯网络得近似推理,概率公式,条件概率公式,乘法公式,全概率公式,边缘化与条件化,联合概率分布,边缘化(求和消元),P(,toothache,)=0、108+0、012+0、016+0、064=0、2,条件化:,贝叶斯法则,由乘法法则,P(a,b)=P(a|b)P(b)=P(b|a)P(a),Bayes rule:P(a|b)=P(b|a)P(a)/P(b),一般形式:,更通用版本(条件化):,贝叶斯网络得由来,随机方法？,每个状态值取决于前面有限个状态,如,Markov,链。,在现实生活中,很多事物相互得关系并不能用一条链来串起来;她们之间得关系可能就是交叉得、错综复杂得。,如疾病得起因,故障得原因等。,贝叶斯网络得由来,全联合概率计算复杂性十分巨大;,变量之间得独立性和条件独立性能大大减少为了定义全联合概率分布所需得概率数目。,需要一种自然、有效得方式来根据不确定性知识推理,贝叶斯网络;,贝叶斯网络得定义,贝叶斯网络,(Bayesian network),就是一个有向图,其中每个节点都标注了定量概率信息:,一个随机变量集合组成网络节点,变量可以就是离散得或者连续得;,一个连接节点对得有向边或者箭头得集合,如果存在从节点,X,指向节点,Y,得有向边,则称,X,就是,Y,得一个父节点;,每个节点都存在一个条件概率分布,P(Xi|Parent(Xi),量化父节点对该节点得影响;,图中不存在有向环,(,就是有向无环图,DAG),。,简单例子,表示前例中条件独立得拓扑网络,:,Weather,is independent of the other variables,Toothache,and,Catch,are conditionally independent given,Cavity,贝叶斯网络得表示,防盗网,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,0.95,0.94,0.29,0.001,t t,t f,f t,f f,P(A),B E,0.90,0.05,t,f,P(J),A,0.70,0.01,t,f,P(M),A,0.001,P(B),0.002,P(E),条件概率表,每个节点旁得条件概率表,(,简称,CPT,),中得值对应一个条件事件得概率,如,P(A)=0、94=P(A|Burglary,Earthquake,),;,条件事件就是父节点取值得一个可能组合;,每行得概率之和应为,1(,表中只给出了为真得情况,为假得概率应为,1-p),;,一个具有,k,个布尔父节点得布尔变量得条件概率表中有,2,k,个独立得可指定得概率,(,注意概率值就是独立得,),;,没有父节点得节点得概率只有,1,行,为先验概率。,0、70,0、01,t,f,P(M),A,贝叶斯网络得概率解释,任何完整得概率模型必须具有表示(直接或间接)该领域变量联合分布得能力,完全得枚举需要指数级得规模(相对于领域变量个数);,贝叶斯网络提供了这种联合概率分布得紧凑表示:分解联合分布为几个局部分布得乘积:,贝叶斯网络得概率解释,从公式可以看出,需要得参数个数随网络中节点个数呈线性增长,而联合分布得计算呈指数增长。,网络中变量间独立性得指定就是实现紧凑表示得关键。,独立性在通过人类专家构造贝叶斯网中特别有效。,贝叶斯网络,1,贝叶斯网络概述,2,贝叶斯网络得语义,3,贝叶斯网络中得精确推理,4,贝叶斯网络得近似推理,贝叶斯网络得语义,贝叶斯网络给出了关于相关事件得完整描述,通过计算全联合概率分布求取,联合分布中得某项就是对每个变量赋予一个特定值情况下得合取概率,就就是条件概率表中适当元素得乘积,例子,P(j,ma,b,e,)=P(j|a)P(m|a)P(a|,b,e,)P(,b,)P(,e,)=0、90*0、70*0、001*0、999*0、998=0、00062,一种贝叶斯网络构建方法,乘法规则,:,P(x,1,x,2,x,n,)=P(x,n,|x,n-1,x,1,)P(x,n-1,x,1,),链式法则,(chain rule),:,P(X,i,|X,i-1,X,1,)=P(X,i,|Parent(X,i,),Parent(X,i,),X,i-1,X,1,初始得合取概率化为更小得条件概率和更小得合取式,这些条件概率得合取式实际上就就是父节点到子节点得概率乘积。,父子节点得关系使得贝叶斯网络具有局部结构化得特性,即每个节点只和数量有限得其她部分产生直接得相互作用,贝叶斯网络得构造,防盗网,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,P(m|j,a,b,e,)=P(m|a),紧致性与节点顺序,贝叶斯网络得局部结构化,(,locally structed,),每个随机变量可以至多受到,k,个其她随机变量得影响,(k=,常数,),;,设网络中有,n,个节点,(,随机变量,),指定每个条件概率表所需信息量至多为,2,k,个数据,则整个网络可以用,n2,k,个数据完全描述,/,而全联合概率分布需要,2,n,个数据,、,比较:,n=30,k=5、,构造贝叶斯网络得次序:添加节点首先从“根本原因”开始,然后加入受其直接影响得变量,直到叶节点,(,不影响任何其她节点,),。,Suppose we choose the ordering,M,J,A,B,E,P,(J|M)=,P,(J)?,Example,Suppose we choose the ordering,M,J,A,B,E,P,(J|M)=,P,(J)?,No,P,(A|J,M)=,P,(A|J),?,P,(A|J,M)=,P,(A),?,Example,Suppose we choose the ordering,M,J,A,B,E,P,(J|M)=,P,(J)?,No,P,(A|J,M)=,P,(A|J),?,P,(A|J,M)=,P,(A),?,No,P,(B|A,J,M)=,P,(B|A),?,P,(B|A,J,M)=,P,(B),?,Example,Suppose we choose the ordering M,J,A,B,E,P,(B|A,J,M)=,P,(B|A),?,Yes,(JohnCalls and MaryCalls increase the chance of alarm、),P,(B|A,J,M)=,P,(B),?,No,P,(E|B,A,J,M)=,P,(E|B),?,P,(E|B,A,J,M)=,P,(E|A,B),?,Example,Suppose we choose the ordering M,J,A,B,E,P,(J|M)=,P,(J)?,No,P,(A|J,M)=,P,(A|J),?,P,(A|J,M)=,P,(A),?,No,P,(B|A,J,M)=,P,(B|A),?,Yes,P,(B|A,J,M)=,P,(B),?,No,P,(E|B,A,J,M)=,P,(E|B),?,No,P,(E|B,A,J,M)=,P,(E|B,A),?,Yes,(,P,(E|B,A),P,(E|A),P,(E|B,A,J,M)=,P,(E|A),?,No,Example,Example contd、,Network is less pact:1+2+4+2+4=13 numbers needed,Deciding conditional independence is hard in noncausal directions(Causal models and conditional independence seem hardwired for humans!),条件独立关系,贝叶斯网络中节点相互独立,(,下面两个定义等价,),:,(1),给定父节点,一个节点与她得非后代节点就是条件独立得;,(2),给定一个节点得父节点、子节点以及子节点得父节点,(Markov blanket),这个节点对于其她节点都就是条件独立得。,图示,例子,条件独立关系图示,U1,Um,X,Z1j,Znj,Y1,Yn,U1,Um,X,Z1j,Znj,Y1,Yn,给定父节点,一个节点与,她得非后代节点就是条件独立得,JohnCall,给定一个节点得父节点、子节点以及,子节点得父节点,这个节点对于,其她节点都就是条件独立得。,Burglary,条件分布得有效表达:,noisy-OR,贝叶斯网络中尽管父节点个数,k,很小,但就是要完成条件概率表仍需要,O(2,k,),数据;,如果找到了变量依赖得某种关系,则可以用,O(k),个参数完成条件概率表,噪声或,(noisy-OR),关系用于刻画不确定关系,(,逻辑或得推广,),;,噪声或关系考虑到每个父节点引起子节点为真得能力得不确定性,:,父节点条件为真但子节点得结果未必为真。,噪声或关系(,1,),例子:,发烧,(fever),为真,当且仅当以下三者之一为真:感冒,(cold)/,流感,(flu)/,疟疾,(malaria),但就是可能病人得了以上疾病却没有发烧症状,这就就是父节点为真其子节点未必真得不确定性,即父子关系被抑制,此时可以认为:,fever,为假当且仅当所有为真得,父节点被抑制,其概率为每个父节点被抑制得概率得乘积,两条假设,所有原因已经列出,每个父节点得抑制独立于其她父节点得抑制,噪声或关系(,2,),假设每个单独抑制得概率如下,P(,fever,|cold,flu,malaria,)=0、6P(,fever,|,cold,flu,malaria,)=0、2P(,fever,|,cold,flu,malaria,)=0、1,目得:,为建立一个完整得条件概率表,大大减少所需参数,如:,P(,fever,|,cold,flu,malaria,)=0、2*0、1=0、02 P(,fever,|cold,flu,malaria,)=0、6*0、2*0、1=0、012 P(,fever,|cold,flu,malaria,)=1-0、012=0、988,噪声或关系(,3,),Cold Flu Malaria,P(Fever),P(,Fever),F F F,0、0,1、0,F F T,0、9,1-0、9=0、1,F T F,0、8,1-0、8=0、2,T F F,0、4,1-0、4=0、6,F T T,1-0、02=0、98,0、1*0、2=0、02,T F T,1-0、06=0、94,0、1*0、6=0、06,T T F,1-0、12=0、88,0、2*0、6=0、12,T T T,1-0、012=0、988,0、1*0、2*0、6=0、012,448,节点,906,边,8254,个数据,而不就是,133,931,430,贝叶斯网络,1,贝叶斯概率基础,2,贝叶斯网络得表示,3,贝叶斯网络中得精确推理,4,贝叶斯网络得近似推理,贝叶斯网络中得精确推理,基本任务就是计算被查询变量得后验概率:,设,X,为待查询变量,e,为观察到得证据,E=E1,Em,证据变量集合,Y=Y1,Yn,非证据变量集合,(,也称隐变量,),全部变量集合,=X,E,Y,推理得任务就是:求后验概率,P(X|e),实际上,根据边缘化规则可得,P(X|e)=,P(X,e)=,y,P(X,e,y),查询实例(,1,),回答查询:,在贝叶斯网络中计算条件概率得乘积并求和,。,以防盗警报为例,求,P(B|J=T,M=F),证据,JohnCalls=True/MaryCalls=False,查询变量,Burglary=True,隐含变量,Earthquake/Alarm,用首字母简化式有:,P(b|j,m,)=,P(b,j,m)=,E,A,P(b,E,A,j,m),查询实例(,2,),进一步代入条件概率:,P(b|j,m),=,E,A,P(b)P(E)P(A|b,e)P(j|A)P(,m|A,),上式最坏复杂度,O(n2,n,),将相对常数移到求和符号以外:,P(b|j,m),=,P(b),E,P(E),A,P(A|b,E)P(j|A)P(,m|A,),计算过程,(,遍历,A=a/,a,和,E=e/,e),P(j|a)=0、90P(,m|a,)=0、30,P(j|,a,)=0、05P(,m,|,a,)=0、99,P(a|b,e)=0、95P(,a|b,e)=0、05,P(,a|b,e,)=0、94 P(,a|b,e,)=0、06,查询实例(,3,),乘积求和过程:,E,P(E),A,P(A|b,E)P(j|A)P(,m|A,),=P(e)*,A,P(A|b,e)P(j|A)P(,m|A,)+P(,e,)*,A,P(A|b,e)P(j|A)P(,m|A,),=P(e)*P(a|b,e)*P(j|a)*P(,m|a,)+P(,a|b,e)*P(j|,a)*P(,m|a,),+P(,e,)*P(a|b,e)*P(j|a)*P(,m|a,)+P(,a|b,e)*P(j|,a)*P(,m|a,),=0、002*0、95*0、90*0、30+0、05*0、05*0、99+0、998*0、94*0、90*0、30+0、06*0、05*0、99,=0、002*0、2565+0、0025+0、998*0、2538+0、0030,=0、002*0、2590+0、998*0、2568=0、2568,查询实例(,4,),相应地有:,P(b|j,m),=,P(b)*0、2568=,0、001*0、2568=,*0、0002568,类似地有:,P(,b|j,m),=,*P(,b,),E,P(E),A,P(A|,b,E)P(j|A)P(,m|A,),=,*P(,b,)*0、002*(0、0783+0、0351)+0、998*(0、0003+0、0495),=,*0、999*0、0499=,*0、0499,归一化以后有,:,P(B|j,m)=,只有,John,打电话而出现盗贼得概率小于,1/100,计算,P,(,B,|,j,m,),得枚举树,变量消元法(,1,),在计算中我们发现,P(j|a)*P(,m|a,),和,P(j|,a)*P(,m|a,),重复计算了两次,如何消除重复？,只要保留一次计算结果既可。,按照从右到左得次序计算。,例子:,例子:,对,M,和,J,用二元向量表示保存每个给定得,a,下得概率:,A,得因子,P(a|B,e),就是一个,2 x 2 x 2,得矩阵,f,A,(A,B,E)、,首先对,A,求和消去,得到一个只有,B,和,E,得,2 x 2,得矩阵:,A,上加一横表示已经通过求和消去。,使用乘法得过程称为点积,(pointwise product),例子:,对,E,求和消去:,最后,可以简单得将,B,得因子与上述累积矩阵相乘来计算答案:,点积(,pointwise product,),变量消元法(,2,),在这样得计算中只要做:,计算两个因子得点积,在因子乘积中对一个变量求和消元,在计算中,消除以下无关节点:,删除不就是查询变量也非证据变量得叶节点,删除所有不就是查询变量,祖先也不就是证据变量得节点,P(JohnCalls l Burglary=true)、,精确推理得复杂度,单连通结构,贝叶斯网络中任何两个节点都至多只有一条无向路径相连;,此时,单连通上得精确推理得时间和空间复杂度都和网络规模呈线性关系;,而对于多连通结构,(,见下图,),最坏情况下变量消元法可能具有指数级得时空复杂度,此时贝叶斯网络得推理就是一个,NP,问题;,所以要寻找多连通网络中得近似算法。,多连通网络,S R P(W),T T .99,T F .90,F T .90,F F .00,C P(R),T .80,F .20,sprinkler,Rain,Wet grass,C P(S),T .10,F .50,P(C)=.5,cloudy,贝叶斯网络,1,贝叶斯概率基础,2,贝叶斯网络得表示,3,贝叶斯网络中得精确推理,4,贝叶斯网络得近似推理,贝叶斯网络得近似推理,大规模多连通网络得精确推理就是不可操作得,所以要考虑近似得推理方法,、,采用随机采样方法,也称蒙特卡罗算法,(Monte Carlo algorithm),:,给出近似解答,近似得精度依赖于所生成采样点得多少。,例如:求积分。,此处近似得含义:,不就是通过计算求出网络中某个点得条件概率,(,因为复杂度高,),而就是对该事件进行采样而获得概率,后验概率计算得采样方法,有两类采样方法,直接采样方法:计算样本得频率,马尔科夫链采样方法:根据马尔科夫覆盖中得变量当前值来采样,直接采样方法,依据已知概率来生成样本,拒绝采样算法,/,似然加权算法,马尔科夫链采样方法,证据变量概率固定条件下随机生成样本,采样方法得要素,任何采样算法中最基本得要素就是根据已知概率分布生成样本。,例如:一个无偏差得硬币,就是一个随机变量,Coin,其可能取值为,、,先验概率就是,P(Coin)=、,直接采样方法,直接采样方法就是按照拓扑结构次序依次对每个变量进行采样,被采样变量值得概率分布依赖于父节点已取得得赋值。,具体实现:,采样样本与概率分布,样本得向量表示,cloudy,sprinkler,rain,wetGrass F/T,或者,0/,1,表示为假或为真,/,如,T,F,T,T,采样按照已知概率分布进行,但不就是等于这个概率分布值,而就是说分布与之相符,cloudy=0、5,0、5/,第,1,次采样,49/51,第,2,次采样,52/48,如此等等,每次采样应该在一定得条件下,(,这就就是条件概率,),进行,不满足条件得样本不再考虑,采样过程举例(,1,),通过例子说明采样过程,/,算法均省略,(1),因为,P(cloudy)=,故,cloudy,得采样样本,T/F,各占,50%,假设,(,不妨,),返回,T,(2)P(sprinkler|cloudy=T)=,故,sprinkler,得采样样本,T/F,各占,10%,和,90%,应该返回,F,(注意:此时采样样本均为,形式,其中,占,10%,占,90%,),(3)P(rain|cloudy=T)=,故,rain,得采样样本,T/F,各占,80%,和,20%,应该返回,T/,样本形式类似于,(2),采样过程举例(,2,),(4)P(wetGrass|sprinkler=F,rain=T)=,则返回,T/,采样样本形式,占,90%,占,10%,实际上如此生成得样本完全符合先验概率,即,对于上例,cloudy sprinkler rain wetGrass,=T F T T=0、5*0、9*0、8*0、9=0、324,拒绝采样方法,从已知分布得采样出发,(,其计算如上,),通过去掉不满足证据条件得样本来计算,(,估计,),那些未知分布得事件得概率,例子:,P(Rain|Sprinkler=T),未知其概率,采样,100,个样本:,其中,73,个为,不满足前提条件,余下得,27,个中,8,个为,rain=T/19,个为,rain=F,P(Rain|Sprinkler=T)=,=,拒绝采样方法得最大问题就就是效率比较低,(,相当一部分样本被拒绝了,),一致得估计,拒绝采样方法能产生真实概率得一致估计,估计得概率在无限多,(,大量样本得极限,),条件下成为精确值,这样得估计称为一致得,(consistent),即,似然加权方法(,1,),只生成与证据,e,一致得事件,避免拒绝采样得低效率。,对证据节点得概率进行似然加权,即按照先验概率得乘积进行计算,/,对非证据节点进行采样,采样样本服从先验概率分布,例子:求,P(rain|sprinkler=T,wetGrass=T),得概率,采样过程如下:,(1),权值,w=1、0,(2)P(cloudy)=,据此采样,返回,T,(3)Sprinkler,就是证据变量,取值,T,则,ww*P(sprinkler=T|cloudy=T)=1、0*0、1=0、1,似然加权方法(,2,),(4)P(rain|cloudy=T)=,据此进行采样,假设,=T,(5)wetGrass,就是证据变量,取值,T,则有,ww*P(wetGrass=T|sprinkler=T,rain=T)=0、1*0、99=0、099,此即,cloudy sprinkler rain wetGrass=T T T T=0、099、,解释:,sprinkler=T&wetGrass=T,条件下,rain=T,得概率很低,似然加权方法也得到对于真实概率得一致估计,从采样与加权得乘积去理解联合分布概率得计算,依然就是全部条件概率得乘积,、,小权值得样本占到大多数,马尔科夫链采样(,1,),直接采样法按照先验概率去采样,马尔科夫链采样对证据变量以外得变量每次随机地采样,举例:考虑求,P(rain|sprinkler=T,wetGrass=T),证据变量固定:,sprinkler=T/wetGrass=T,隐变量,cloudy/rain,则随机采样:初始值不妨假设,cloudy=T/rain=F,初始状态,=,证据变量固定下,状态空间内得随机走动,马尔科夫链采样(,2,),然后反复按照以下,2,个步骤采样,(1),当前条件下,对,cloudy,随机采样,结果,=,(2),当前条件下,对,rain,随机采样,结果,=,最后得到若干样本,例如,rain=T=20/rain=F=60,则,P(rain|sprinkler=T,wetGrass=T)=,=,马尔科夫链采样得合理性(,1,),马尔科夫链,采样过程最终会进入,“,动态平衡,”,状态,被采样变量服从马尔科夫覆盖下得条件概率分布,且,“,稳态分布,”,=,真实后验概率,P(x|e),我们所需要求解得正就是给定证据变量,e,下某个变量得概率值,P(x|e),证明过程:,转移概率,状态,x,到状态,x,q(x,x,),时刻,t,处于状态,x,得概率,t,(x),马尔科夫链采样得合理性(,2,),下一时刻处于状态,x,得概率,t+1,(x,)=,x,t,(x),q(x,x,),稳态分布,(stationary distribution),:当,t+1,(x,)=,t,(x,),时,马尔科夫链达到稳态分布,即,(,省略,t),(x,)=,x,(x),q(x,x,),对于所有,x,细致平衡,任意两个状态间沿两个方向转换概率相等,(x),q(x,x,)=,(x,),q(x,x),对于所有,x,x,简单公式推导,(,求和,),可证明细致平衡中蕴含着稳态分布,几点总结,贝叶斯网络得特点:,双向推理能力(预测和诊断),快速得调试和重构能力,具有较强得概率统计基础,用于人工智能和专家系统得不确定推理(优于早期得基于规则得模式)。,这种网络支持任何变量子集相对于另一子集得条件概率计算。,贝叶斯网络就是域中变量关系得直接表示,而不就是推理过程。网络中得方向表示变量间真正得因果关系而不就是推理过程得信息流向。,因此在贝叶斯推理过程中,推理过程可以沿任何方向进行(预测、诊断、解释)。,BN,定性描述,贝叶斯网络中每个圆圈表示一个状态。状态之间得连线表示她们得因果关系。,和马尔可夫链类似,贝叶斯网络中得每个状态值取决于前面有限个状态。不同得就是,贝叶斯网络比马尔可夫链灵活,她不受马尔可夫链得链状结构得约束,因此可以更准确地描述事件之间得相关性。,可以讲,马尔可夫链就是贝叶斯网络得特例,而贝叶斯网络就是马尔可夫链得推广。,发展历史(,1,),贝叶斯(,Reverend Thomas Bayes 1702-1761,)学派奠基性得工作就是贝叶斯得论文,“,关于几率性问题求解得评论,”,。,著名得数学家拉普拉斯(,Laplace P、S、1749-1827,)用贝叶斯得方法导出了重要得,“,相继律,”,贝叶斯得方法和理论逐渐被人理解和重视起来。,但由于当时贝叶斯方法在理论和实际应用中还存在很多不完善得地方,因而在十九世纪并未被普遍接受。,发展历史(,2,),二十世纪初,意大利得菲纳特(,B、de Finetti,)以及英国得杰弗莱(,Jeffreys H、,)都对贝叶斯学派得理论作出重要得贡献。,第二次世界大战后,瓦尔德(,Wald A、,)提出了统计得决策理论,在这一理论中,贝叶斯解占有重要得地位;信息论得发展也对贝叶斯学派做出了新得贡献。,1958,年英国最悠久得统计杂志,Biometrika,全文重新刊登了贝叶斯得论文,20,世纪,50,年代,以罗宾斯(,Robbins H、,)为代表,提出了经验贝叶斯方法和经典方法相结合,引起统计界得广泛注意,这一方法很快就显示出她得优点,成为很活跃得一个方向。,发展历史(,3,),1986 Pearl,将贝叶斯网络引入了专家系统,(were revived and reintroduced to expert systems)、,1988 Lauritzen&Spiegelhalter,提出了贝叶斯高效算法,(,tractable calculations,)、,1995In Windows95,for printer-trouble shooting and Office assistance(,“,the paper clip,”,)、,1999BN is getting more and more used、Ex、Gene expression analysis,Busine