人工智能贝叶斯网络

Bayesiannetworks

贝叶斯网络Frequentistvs.Bayesian客观vs.主观Frequentist（频率主义者）:概率是长期的预期出现频率.P(A)=n/N,wherenisthenumberoftimeseventAoccursinNopportunities.“某事发生的概率是0.1”意味着0.1是在无穷多样本的极限

条件下能够被观察到的比例

但是，在许多情景下不可能进行重复试验

发生第三次世界大战的概率是多少?Bayesian:degreeofbelief.Itisameasureoftheplausibility（似然性）ofaneventgivenincompleteknowledge.相信的程度，是在不确定知识的环境下对事件似然性的衡量Probability概率Probabilityisarigorousformalismforuncertainknowledge概率是对不确定知识一种严密的形式化方法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全联合概率分布指定了对随机变量的每种完全赋值，即每个原子事件的概率Queriescanbeansweredbysummingoveratomicevents可以通过把对应于查询命题的原子事件的条目相加的方式来回答查询Fornontrivialdomains,wemustfindawaytoreducethejointsize

IndependenceandconditionalindependenceprovidethetoolsIndependence

/ConditionalIndependenceAandBareindependentiff

P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)AisconditionallyindependentofBgivenC:

P(A|B,C)=P(A|C)在大多数情况下，使用条件独立性能将全联合概率的表示由n的指数关系减为n的线性关系。Conditionalindependenceisourmostbasicandrobustformofknowledgeaboutuncertainenvironments.ProbabilityTheoryProbabilitytheorycanbeexpressedintermsoftwosimpleequations概率理论可使用两个简单线性方程来表达–SumRule（加法规则）•变量的概率是通过边缘化或者求和其他变量获得的–ProductRule（乘法规则）•用条件表达联合概率所有的概率推理和学习相当于不断重复加法和乘法法则大纲Graphicalmodels（概率图模型）Bayesiannetworks

–Syntax（语法）

–Semantics（语义）Inference（推导）inBayesiannetworks

什么是图模型？概率分布的图表示

–概率论和图论的结合

•Alsocalled概率图模型•Theyaugmentanalysisinsteadofusingpure

algebra（代数）WhatisaGraph?•Consistsofnodes(alsocalledvertices)andlinks(alsocallededgesorarcs)•在概率图模型中

–每个节点表示一个随机变量(or一组随机变量)

–边表示变量间的概率关系GraphicalModelsinCS•处理不确定性和复杂性的天然工具

–贯穿整个应用数学和工程领域•图模型中最重要的思想是模块性概念

–acomplexsystemisbuiltbycombiningsimplerparts.WhyareGraphicalModelsuseful•概率理理论提提供了了“黏黏合剂剂”whereby––使每个个部分分连接接起来来,确保系系统作作为一一个整整体是是一致致的–提供模模型到到数据据的连连接方方法.•图理论论方面面提供供:––直观的的接口口•bywhichhumanscanmodelhighly-interactingsetsofvariables––数据结结构•thatlendsitselfnaturallytodesigningefficientgeneral-purpose（通用用的））algorithmsGraphicalmodels:统一的的框架架•考虑传传统的的多变变量的的概率率系统统作为为一般般基础础形式式的实实例–mixturemodels（混合合模型型）,factoranalysis（因子子分析析）,hiddenMarkovmodels,Kalmanfilters（卡尔尔曼滤滤波器器）,etc.––在系统统工程程，信信息论论，模模式识识别和和统计计力学学中被被用到到•优势:––在某一一领域域中的的专业业技术术能够够在该该领域域中相相互转转化并并被充充分利利用–Providesnaturalframeworkfordesigningnewsystems图模型在在机器学学习中的的角色形象化概概率模型型结构的的简单方方法InsightsintopropertiesofmodelConditionalindependencepropertiesbyinspectinggraph执行推理理和学习习表示为为图形化化操作需需要复杂杂的计算算图的方向向性•有向图模模型–方向取决决于箭头头•贝叶斯网网络–随机变量量间的因因果关系系•MorepopularinAIandstatistics•无向图模模型–边没有箭箭头•Markovrandomfields（马尔科科夫随机机场）–更适合表表达变量量之间的的软约束束•MorepopularinVisionandphysicsBayesiannetworks一种简单单的，图图形化的的数据结结构，用用于表示示变量之之间的依依赖关关系（条条件独立立性），，为任何何全联合合概率分分布提供供一种简简

明的的规范。。Syntax语法:

asetofnodes,onepervariable

adirected（有向））,acyclic（无环））graph(link≈≈"directinfluences")

aconditionaldistributionforeachnodegivenitsparents:P(Xi|Parents(Xi))—量化其父父节点对对该节点点的影响响Inthesimplestcase,conditionaldistributionrepresentedasaconditionalprobabilitytable条件概率率表(CPT)givingthe

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

–Aburglarcansetthealarmoff––Anearthquakecansetthealarmoff

–ThealarmcancauseMarytocall––ThealarmcancauseJohntocallExamplecontd.Compactness（紧致性性）ACPTforBooleanXiwithkBooleanparentshas2krowsforthecombinationsofparentvalues一个具有有k个布尔父父节点的的布尔变变量的条条件概率率表中有有2k个独立的的可指定定概率EachrowrequiresonenumberpforXi=true(thenumberforXi=falseisjust1-p)Ifeachvariablehasnomorethankparents,thecompletenetworkrequiresO(n··2k)numbersI.e.,growslinearlywithn,vs.O(2n)forthefulljointdistributionForburglarynet,1+1+4+2+2=10numbers(vs.25-1=31)Globalsemantics（全局语语义）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全联合概概率分布布可以表表示为贝贝叶斯网网络中的的条件概概率分布布的乘积积Globalsemantics（全局语语义）Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:全联合概概率分布布可以表表示为贝贝叶斯网网络中的的条件概概率分布布的乘积积LocalsemanticsLocalsemantics:eachnodeisconditionallyindependentofitsnondescendants（非后代代）givenitsparents给定父节节点，一一个节点点与它的的非后代代节点是是条件独独立的Theorem:LocalsemanticsglobalsemanticsCausalChains因果链一个基本本形式：：–IsXindependentofZgivenY?–Evidencealongthechain““blocks”theinfluenceCommonCause共同原因因另一个基基础的形形态:twoeffectsofthesamecause

–AreXandZindependent?

–AreXandZindependentgivenY?–Observingthecauseblocksinfluencebetweeneffects.CommonEffect共同影响响最后一种种配置形形态:twocausesofone

effect(v-structures)––AreXandZindependent?•Yes:remembertheballgameandtherain

causingtraffic,nocorrelation?–AreXandZindependentgivenY?•No:rememberthatseeingtrafficputtherainandtheballgameincompetition?–Thisisbackwardsfromtheothercases•Observingtheeffectenablesinfluencebetweencauses.构造贝叶斯斯网络Needamethodsuchthataseriesoflocallytestableassertionsofconditionalindependenceguaranteestherequiredglobalsemantics需要一种方方法使得局局部的条件件独立关系系能够保证证全局语义义得以成立立ChooseanorderingofvariablesX1,…,XnFori=1tonaddXitothenetworkselectparentsfromX1,…,Xi-1suchthatP(Xi|Parents(Xi))=P(Xi|X1,...Xi-1)该父亲选择择保证了全全局语义:构造贝叶斯斯网络要求网络的的拓扑结构构确实反映映了合适的的父节点集集对每个变变量的那些些直接影响响。添加节点的的正确次序序是首先添添加“根本本原因”节节点，然后后加入受它它们直接影影响的变量量，以此类类推。ExampleExampleExampleExampleExampleExamplecontd.在非因果方方向决定条条件独立性性是很难的的(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)Networkislesscompact:1+2+4+2+4=13numbersneeded因果关系?•当贝叶斯网网络反映真真正的因果果模式时:

–Oftensimpler(nodeshavefewerparents)––Ofteneasiertothinkabout––Ofteneasiertoelicitfromexperts（专家））•BNs不一定必必须是因因果–有时无因因果关系系的网络络是存在在的(especiallyifvariablesaremissing)

–箭头反映映相关性性，而不不是因果果关系•箭头的真真正含义义是什么么?

–Topologymayhappentoencodecausalstructure––TopologyreallyencodesconditionalindependenceInferenceinBayesiannetworks推理任务务简单查询询:计算后验验概率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)最优决策策:decisionnetworksincludeutilityinformation;probabilisticinferencerequiredforP(outcome|action,evidence)通过枚举举进行推推理上一章解解释了任任何条件件概率都都可以通通过将全全联合分分布表中中的某些些项相加加而计算算得到在贝叶斯斯网络中中可以通通过计算算条件概概率的乘乘积并求求和来回回答查询询。通过枚举举进行推推理上一章解解释了任任何条件件概率都都可以通通过将全全联合分分布表中中的某些些项相加加而计算算得到Evaluationtree变量消元元法Variableelimination（变量消消元）:carryoutsummationsright-to-left,storingintermediateresults(factors：因子)toavoidrecomputation精确推理理的复杂杂度Singlyconnectednetworks单联通网网络(orpolytrees多树):——anytwonodesareconnectedbyatmostone(undirected)path——timeandspacecostofvariableeliminationareO(dkn)多树上的的变量消消元的时时间和空空间复杂杂度都与与网络规规模呈线线性关系系。Multiplyconnectednetworks多联通网网络:

—canreduce3SATtoexactinference⇒⇒NP-hard——equivalenttocounting3SATmodels⇒#P-completeExample:NaïveBayesmodel单一父亲亲变量和和一批孩孩子变量量，孩子子变量在在给定父父亲变量量下是相相互独立立的NaïveBayesmodelTotalnumberofparameters（参数））islinearinnExample:垃圾邮件件检测想象一下下试图去去自动检检测垃圾圾邮件的的问题.一个简单单的方案案是只检检测主题题，然后后根据邮邮件的标标题检查查一些简简单的特特征来尝尝试识别别垃圾邮邮件.我们先考考虑两个个简单的的特征:Caps:是否标题是彻彻底大写的Free:是否标题中包包含大写或小小写的单词‘‘free’e.g.:amessagewiththesubjectheader““NEWMORTGAGERATE“islikelytobespam.Similarly,for“MoneyforFree”,““FREElunch”,etc.Example:垃圾邮件检测测模型的构建基基于以下三个个随机变量,Caps,FreeandSpam,eachofwhichtakeonthevaluesY(forYes)orN(forNo)Caps=YifandonlyifthesubjectofthemessagedoesnotcontainlowercaselettersFree=Yifandonlyiftheword`free'appearsinthesubject

(lettercaseisignored)Spam=YifandonlyifthemessageisspamP(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:Learningtoclassifytextdocuments文本分类是在在文档所包含含的文本基础础上，把给定定的文档分配配

到固定类类别集合中某某一个类别的的任务。这个个任务中常常常用

到朴素素贝叶斯模型型。在这些模模型中，查询询变量是文档档类别

，““结果”变量量则是语言中中每个词是否否出现。我们们假设文档档中的词的出出现都是独立立的，其出现现频率由文档档类别确定。。a.准确地解释当当给定一组类类别已经确定定的文档作为为“训练数据据”时，这样样的模型是如如何构造的。。b.准确地解释如如何对新文档档进行分类。。c.这里独立性假假设合理吗？？请讨论。Example:Learningtoclassifytextdocuments模型包含先验验概率P(Category)和条件概率P(wordi|Category)•P(Category=c)isestimatedasthefractionofalldocumentsthatareofcategoryc•P(wordi=true|Category=c)isestimatedasthefractionofdocumentsofcategorycthatcontainwordiTwentyNewsgroupsGiven1000trainingdocumentsfromeachgroup.LearntoclassifynewdocumentsaccordingtowhichnewsgroupitcamefromNaïv