人工智能09贝叶斯网络

1、Bayesian networks贝叶斯网络Frequentistvs.Bayesian客观vs.主观Frequentist（频率主主义者）:概率是长长期的预预期出现现频率. P(A)=n/N, where nisthe numberoftimeseventA occursinN opportunities.“某事发生生的概率率是0.1” 意味味着0.1是在无穷穷多样本本的极限限条件件下能够够被观察察到的比比例但是，在在许多情情景下不不可能进进行重复复试验发生第三三次世界界大战的的概率是是多少?Bayesian:degreeofbelief.Itisa measureofthe plausib

2、ility（似然性性）ofaneventgivenincomplete knowledge.相信的程程度，是是在不确确定知识识的环境境下对事事件似然然性的衡衡量Probability概率Probabilityisa rigorous formalismforuncertain knowledge概率是对对不确定定知识一一种严密密的形式式化方法法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全联合概概率分布布指定了了对随机机变量的的每种完完全赋值值，即每每个原子事件件的概率Queries canbeanswer

3、edbysumming overatomic events可以通过过把对应应于查询询命题的的原子事事件的条条目相加加的方式式来回答答查询Fornontrivialdomains,wemust findawaytoreduce thejointsizeIndependenceandconditionalindependenceprovide thetoolsIndependence/Conditional IndependenceAandBareindependentiffP(A|B) =P(A)orP(B|A) =P(B)orP(A,B)=P(A)P(B)Aisconditionally in

4、dependentofBgivenC:P(A|B,C) =P(A|C)在大多数数情况下下，使用用条件独独立性能能将全联联合概率率的表示示由n的指数关关系减为为n的线性关关系。Conditionalindependenceisour mostbasicand robustform of knowledgeaboutuncertainenvironments.ProbabilityTheoryProbabilitytheorycan be expressedintermsoftwosimple equations概率理论论可使用用两个简简单线性性方程来来表达SumRule（加法规规则）变量的概概率

5、是通通过边缘缘化或者者求和其其他变量量获得的的Product Rule（乘法规规则）用条件表表达联合合概率所有的概概率推理理和学习习相当于于不断重重复加法法和乘法法法则大纲Graphicalmodels（概率图图模型）Bayesiannetworks Syntax（语法） Semantics（语义）Inference（推导）inBayesiannetworks什么是图图模型？概率分布布的图表表示概率论和和图论的的结合 Alsocalled概率图模模型 Theyaugmentanalysisinstead of using purealgebra（代数）What is aGraph? Consi

6、sts of nodes (also calledvertices)and links (also callededgesorarcs)在概率图图模型中中每个节点点表示一一个随机机变量(or一组随机机变量)边表示变变量间的的概率关关系GraphicalModels in CS处理不确确定性和和复杂性性的天然然工具贯穿整个个应用数数学和工工程领域域图模型中中最重要要的思想想是模块块性概念念 acomplexsystemisbuiltbycombining simplerparts.Whyare GraphicalModelsuseful概率理论论提供了了“黏合合剂”whereby使每个部部分连接

7、接起来,确保系统统作为一一个整体体是一致致的提供模型型到数据据的连接接方法.图理论方方面提供供:直观的接接口 by which humanscanmodelhighly-interacting setsofvariables数据结构构 thatlendsitself naturallytodesigningefficient general-purpose（通用的的）algorithmsGraphicalmodels:统一的框框架考虑传统统的多变变量的概概率系统统作为一一般基础础形式的的实例 mixturemodels（混合模模型）, factoranalysis（因子分分析）, hidden

8、Markovmodels,Kalmanfilters（卡尔曼曼滤波器器）, etc.在系统工工程，信信息论，模式识识别和统统计力学学中被用用到优势:在某一领领域中的的专业技技术能够够在该领领域中相相互转化化并被充充分利用用 Provides naturalframework fordesigningnew systems图模型在在机器学学习中的的角色形象化概概率模型型结构的的简单方方法Insightsinto propertiesofmodelConditionalindependence propertiesbyinspectinggraph执行推理理和学习习表示为为图形化化操作需需要复杂杂

9、的计算算图的方向向性有向图模模型方向取决决于箭头头贝叶斯网网络随机变量量间的因因果关系系 MorepopularinAIandstatistics无向图模模型边没有箭箭头 Markovrandomfields（马尔科科夫随机机场）更适合表表达变量量之间的的软约束束 MorepopularinVisionand physicsBayesiannetworks一种简单单的，图图形化的的数据结结构，用用于表示示变量之之间的依依赖关关系（条条件独立立性），为任何何全联合合概率分分布提供供一种简简明的的规范。Syntax语法:aset of nodes,oneper variableadirected（

10、有向）, acyclic（无环）graph(link directinfluences)aconditionaldistribution foreach nodegivenits parents:P(Xi| Parents(Xi)量化其父父节点对对该节点点的影响响Inthesimplestcase,conditionaldistribution represented as aconditionalprobabilitytable条件概率率表(CPT)givingthedistributionoverXiforeachcombinationofparentvaluesExampleTopolo

11、gy（拓扑结结构）ofnetwork encodesconditionalindependence assertions:Weather独立于其其他变量量ToothacheandCatchareconditionallyindependentgivenCavityExample我晚上在在单位上上班，此此时邻居居John给我打电电话说我我家警报报响了，但是邻邻居Mary没有给打打电话。有时轻轻微的地地震也会会引起警警报。那那么我家家真正遭遭贼了吗吗？Variables:Burglary（入室行行窃）,Earthquake,Alarm,JohnCalls,MaryCalls网络拓扑扑结构反反映出因

12、因果关系系:Aburglar cansetthe alarm off An earthquakecan setthealarmoffThe alarm cancauseMary to callThealarmcan cause JohntocallExample contd.Compactness（紧致性性）A CPTforBooleanXiwithkBoolean parentshas2krows forthecombinations of parentvalues一个具有有k个布尔父父节点的的布尔变变量的条条件概率率表中有有2k个独立的的可指定定概率Each rowrequiresonen

13、umberpforXi= true(the numberforXi=falseisjust1-p)Ifeach variable hasnomore thankparents,thecompletenetworkrequiresO(n2k)numbersI.e.,growslinearlywithn, vs.O(2n)forthe fulljointdistributionForburglarynet,1 +1+ 4+2 +2= 10 numbers(vs.25-1= 31)Globalsemantics（全局语语义）Thefulljointdistributionisdefinedasthe

14、productofthelocalconditionaldistributions:全联合概概率分布布可以表表示为贝贝叶斯网网络中的的条件概概率分布布的乘积积Globalsemantics（全局语语义）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全联合概概率分布布可以表表示为贝贝叶斯网网络中的的条件概概率分布布的乘积积LocalsemanticsLocalsemantics: eachnodeisconditionally independent of itsnondescend

15、ants（非后代代）givenitsparents给定父节节点，一一个节点点与它的的非后代代节点是是条件独独立的Theorem:LocalsemanticsglobalsemanticsCausalChains因果链一个基本本形式： Is XindependentofZgivenY?Evidencealongthechain“blocks”the influenceCommonCause共同原因因另一个基基础的形形态: twoeffects of thesame causeAre Xand Zindependent?Are Xand ZindependentgivenY?Observingth

16、e cause blocksinfluencebetweeneffects.CommonEffect共同影响响最后一种种配置形形态: twocausesofoneeffect(v-structures) AreX andZ independent? Yes:rememberthe ballgame andtheraincausingtraffic,nocorrelation? AreX andZ independent given Y? No:rememberthat seeingtraffic puttherainand theballgameincompetition?This is ba

17、ckwardsfrom theothercases Observingtheeffect enablesinfluence betweencauses.构造贝叶叶斯网络络Need amethod suchthata seriesoflocally testable assertionsofconditionalindependence guaranteesthe required globalsemantics需要一种种方法使使得局部部的条件件独立关关系能够够保证全全局语义义得以成成立ChooseanorderingofvariablesX1, ,XnFori= 1tonaddXitothen

18、etworkselect parentsfromX1, ,Xi-1such thatP(Xi| Parents(Xi)=P(Xi| X1, .Xi-1)该父亲选选择保证证了全局局语义:构造贝叶叶斯网络络要求网络络的拓扑扑结构确确实反映映了合适适的父节节点集对对每个变变量的那那些直接接影响。添加节点点的正确确次序是是首先添添加“根根本原因因”节点点，然后后加入受受它们直直接影响响的变量量，以此此类推。ExampleExampleExampleExampleExampleExample contd.在非因果果方向决决定条件件独立性性是很难难的(Causal modelsandconditional

19、independence seemhardwired forhumans!)Network is lesscompact:1+ 2+4 +2+ 4=13numbers needed因果关系系?当贝叶斯斯网络反反映真正正的因果果模式时时:Oftensimpler(nodeshavefewerparents) Often easiertothinkabout Often easiertoelicitfromexperts（专家） BNs不一定必必须是因因果有时无因因果关系系的网络络是存在在的(especiallyifvariablesare missing)箭头反映映相关性性，而不不是因果果关系箭

20、头的真真正含义义是什么么?Topologymay happentoencodecausal structureTopologyreallyencodesconditionalindependenceInferenceinBayesiannetworks推理任务务简单查询询:计算后验验概率P(Xi|E=e)e.g.,P(NoGas|Gauge油表=empty, Lights=on,Starts=false)联合查询询:P(Xi,Xj|E=e) =P(Xi|E=e)P(Xj|Xi,E=e)最优决策策: decision networks includeutilityinformation;prob

21、abilisticinferencerequiredforP(outcome|action, evidence)通过枚举举进行推推理上一章解解释了任任何条件件概率都都可以通通过将全全联合分分布表中中的某些些项相加加而计算算得到在贝叶斯斯网络中中可以通通过计算算条件概概率的乘乘积并求求和来回回答查询询。通过枚举举进行推推理上一章解解释了任任何条件件概率都都可以通通过将全全联合分分布表中中的某些些项相加加而计算算得到Evaluation tree变量消元元法Variableelimination（变量消消元）: carry outsummations right-to-left, storingi

22、ntermediate results(factors：因子) to avoid recomputation精确推理理的复杂杂度Singlyconnected networks单联通网网络(orpolytrees多树): anytwonodesare connectedbyatmost one(undirected)path timeand space costofvariableeliminationare O(dkn)多树上的的变量消消元的时时间和空空间复杂杂度都与与网络规规模呈线线性关系系。Multiplyconnectednetworks多联通网网络:can reduce3SAT to

23、 exact inference NP-hardequivalent to counting 3SATmodels #P-completeExample:NaveBayesmodel单一父亲亲变量和和一批孩孩子变量量，孩子子变量在在给定父父亲变量量下是相相互独立立的NaveBayesmodelTotalnumberofparameters（参数）islinearinnExample:垃圾邮件件检测想象一下下试图去去自动检检测垃圾圾邮件的的问题.一个简单单的方案案是只检检测主题题，然后后根据邮邮件的标标题检查查一些简简单的特特征来尝尝试识别别垃圾邮邮件.我们先考考虑两个个简单的的特征:Caps:

24、是否标题题是彻底底大写的的Free:是否标题题中包含含大写或或小写的的单词freee.g.:a messagewiththesubjectheader“NEWMORTGAGERATE“islikelytobespam.Similarly,for“Money forFree”,“FREElunch”,etc.Example:垃圾邮件件检测模型的构构建基于于以下三三个随机机变量,Caps,FreeandSpam, eachofwhichtakeonthevalues Y(forYes) or N(forNo)Caps= Yifand onlyifthe subjectofthe messagedo

25、esnotcontainlowercaselettersFree= Yifand onlyifthe wordfree appearsinthe subject(lettercase is ignored)Spam= Yifand onlyifthe messageisspamP(Free,Caps,Spam)=P(Spam )P(Caps|Spam) P(Free|Spam)Example:垃圾邮件件检测P(Free, Caps, Spam)=P(Spam)P(Caps|Spam)P(Free|Spam)Example:垃圾邮件件检测Example:垃圾邮件件检测Example:Learni

26、ngtoclassifytextdocuments文本分类类是在文文档所包包含的文文本基础础上，把把给定的的文档分分配到到固定类类别集合合中某一一个类别别的任务务。这个个任务中中常常用用到朴朴素贝叶叶斯模型型。在这这些模型型中，查查询变量量是文档档类别，“结结果”变变量则是是语言中中每个词词是否出出现。我我们假设设文档档中的词词的出现现都是独独立的，其出现现频率由由文档类类别确定定。a.准确地解解释当给给定一组组类别已已经确定定的文档档作为“训练数数据”时时，这样样的模型型是如何何构造的的。b.准确地解解释如何何对新文文档进行行分类。c.这里独立立性假设设合理吗吗？请讨讨论。Example:L

27、earningtoclassifytextdocuments模型包含含先验概概率P(Category)和条件概率率P(wordi|Category) P(Category=c)isestimated as thefractionofalldocuments thatare of category c P(wordi =true|Category=c)isestimatedasthe fraction of documentsofcategoryc thatcontainword iTwentyNewsgroupsGiven1000 training documentsfrom eachgroup. Learn to classify newdocumentsaccording to which newsgroupitcame fromNaveBayes:89% classification accuracyLearningCurvefor20Newsgrou