人工智能09贝叶斯网络

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图模型在机器学习中的角色形象化概率模型结构的简单方法Insightsintopropertiesofmodel

Conditionalindependencepropertiesbyinspectinggraph执行推理和学习表示为图形化操作需要复杂的计算图的方向性•有向图模型

–方向取决于箭头•贝叶斯网络

–随机变量间的因果关系•MorepopularinAIand

statistics•无向图模型

–边没有箭头•Markovrandomfields

（马尔科夫随机场）

–更适合表达变量之间的软约束•MorepopularinVisionandphysicsBayesiannetworks一种简单的，图形化的数据结构，用于表示变量之间的依赖

关系（条件独立性），为任何全联合概率分布提供一种简

明的规范。Syntax语法:

asetofnodes,onepervariable

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

aconditionaldistributionforeachnodegivenitsparents:

P(Xi|Parents(Xi))—量化其父节点对该节点的影响Inthesimplestcase,conditionaldistributionrepresentedasa

conditionalprobabilitytable条件概率表(CPT)givingthe

distributionoverXi

foreachcombinationofparentvaluesExampleTopology（拓扑结构）ofnetworkencodesconditionalindependenceassertions:

Weather独立于其他变量

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

–Aburglarcansetthealarmoff

–Anearthquakecansetthealarmoff

–ThealarmcancauseMarytocall

–ThealarmcancauseJohntocallExamplecontd.Compactness（紧致性）ACPTforBooleanXiwithkBooleanparentshas2k

rowsforthecombinationsofparentvalues一个具有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共同原因另一个基础的形态:two

effectsofthesamecause

–AreXandZindependent?

–AreXandZindependentgivenY?–Observingthecauseblocksinfluence

betweeneffects.CommonEffect共同影响最后一种配置形态:twocausesofone

effect(v-structures)

–AreXandZindependent?

•Yes:remembertheballgameandtherain

causingtraffic,nocorrelation?

–AreXandZindependentgivenY?

•No:rememberthatseeingtrafficputtherain

andtheballgameincompetition?

–Thisisbackwardsfromtheothercases

•Observingtheeffectenablesinfluencebetween causes.构造贝叶斯网络Needamethodsuchthataseriesoflocallytestableassertionsofconditionalindependenceguaranteestherequiredglobalsemantics需要一种方法使得局部的条件独立关系能够保证全局语义得以成立ChooseanorderingofvariablesX1,…,XnFori=1ton

addXi

tothenetwork

selectparentsfromX1,…,Xi-1

suchthat

P(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;probabilisticinferencerequiredfor

P(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（参数）islinearinn

Example:垃圾邮件检测想象一下试图去自动检测垃圾邮件的问题.一个简单的方案是只检测主题，然后根据邮件的标题检查一些简单的特征来尝试识别垃圾邮件.我们先考虑两个简单的特征:

Caps:是否标题是彻底大写的Free:是否标题中包含大写或小写的单词‘free’

e.g.:amessagewiththesubjectheader“NEWMORTGAGERATE“islikelytobespam.Similarly,for“MoneyforFree”,“FREElunch”,etc.Example:垃圾邮件检测模型的构建基于以下三个随机变量,

Caps,FreeandSpam,eachofwhichtakeonthevaluesY(forYes)orN(forNo)Caps=Yifandonlyifthesubjectofthemessagedoesnot

containlowercaselettersFree=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:Learningtoclassifytext

documents文本分类是在文档所包含的文本基础上，把给定的文档分配

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

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

，“结果”变量则是语言中每个词是否出现。我们假设文

档中的词的出现都是独立的，其出现频率由文档类别确定

。

a.准确地解释当给定一组类别已经确定的文档作为“训练数据”时，这样的模型是如何构造的。

b.准确地解释如何对新文档进行分类。

c.这里独立性假设合理吗？请讨论。Example:Learningtoclassifytext

documents模型包含先验概率P(Category)和

条件概率P(wordi|Category)•P(Category=c)isestimatedasthefractionofalldocumentsthatareofcategoryc•P(wordi=true|Category=c)isestimatedasthefractionofdocumentsofcategorycthatcontainwordiTwentyNewsgroupsGiven1000trainingdocumentsfromeachgroup.Learntoclassifynewdocumentsaccordingtowhichnewsgroupitcamefrom

NaïveBayes:89%classificationaccuracyLearningCurvefor20NewsgroupsExample:ADigitRe