人工智能09贝叶斯网络.pptx

人工智能09贝叶斯网络.pptx

《人工智能09贝叶斯网络.pptx》由会员分享，可在线阅读，更多相关《人工智能09贝叶斯网络.pptx（57页珍藏版）》请在冰点文库上搜索。

Bayesiannetworks贝叶斯网络,Frequentistvs.Bayesian,客观vs.主观Frequentist（频率主义者）:

概率是长期的预期出现频率.P（A）=n/N,wherenisthenumberoftimeseventAoccursinNopportunities.“某事发生的概率是0.1”意味着0.1是在无穷多样本的极限条件下能够被观察到的比例但是，在许多情景下不可能进行重复试验发生第三次世界大战的概率是多少?

Bayesian:

degreeofbelief.Itisameasureoftheplausibility（似然性）ofaneventgivenincompleteknowledge.相信的程度，是在不确定知识的环境下对事件似然性的衡量,Probability概率,Probabilityisarigorousformalismforuncertainknowledge概率是对不确定知识一种严密的形式化方法Jointprobabilitydistributionspecifiesprobabilityofeveryatomicevent全联合概率分布指定了对随机变量的每种完全赋值，即每个原子事件的概率Queriescanbeansweredbysummingoveratomicevents可以通过把对应于查询命题的原子事件的条目相加的方式来回答查询Fornontrivialdomains,wemustfindawaytoreducethejointsizeIndependenceandconditionalindependenceprovidethetools,Independence/ConditionalIndependence,AandBareindependentiffP（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.,ProbabilityTheory,Probabilitytheorycanbeexpressedintermsoftwosimpleequations概率理论可使用两个简单线性方程来表达SumRule（加法规则）变量的概率是通过边缘化或者求和其他变量获得的ProductRule（乘法规则）用条件表达联合概率所有的概率推理和学习相当于不断重复加法和乘法法则,大纲,Graphicalmodels（概率图模型）BayesiannetworksSyntax（语法）Semantics（语义）Inference（推导）inBayesiannetworks,什么是图模型？

概率分布的图表示概率论和图论的结合Alsocalled概率图模型Theyaugmentanalysisinsteadofusingpurealgebra（代数）,WhatisaGraph?

Consistsofnodes（alsocalledvertices）andlinks（alsocallededgesorarcs）在概率图模型中每个节点表示一个随机变量（or一组随机变量）边表示变量间的概率关系,GraphicalModelsinCS,处理不确定性和复杂性的天然工具贯穿整个应用数学和工程领域图模型中最重要的思想是模块性概念acomplexsystemisbuiltbycombiningsimplerparts.,WhyareGraphicalModelsuseful,概率理论提供了“黏合剂”whereby使每个部分连接起来,确保系统作为一个整体是一致的提供模型到数据的连接方法.图理论方面提供:

直观的接口bywhichhumanscanmodelhighly-interactingsetsofvariables数据结构thatlendsitselfnaturallytodesigningefficientgeneral-purpose（通用的）algorithms,Graphicalmodels:

统一的框架,考虑传统的多变量的概率系统作为一般基础形式的实例mixturemodels（混合模型）,factoranalysis（因子分析）,hiddenMarkovmodels,Kalmanfilters（卡尔曼滤波器）,etc.在系统工程，信息论，模式识别和统计力学中被用到优势:

在某一领域中的专业技术能够在该领域中相互转化并被充分利用Providesnaturalframeworkfordesigningnewsystems,图模型在机器学习中的角色,形象化概率模型结构的简单方法InsightsintopropertiesofmodelConditionalindependencepropertiesbyinspectinggraph执行推理和学习表示为图形化操作需要复杂的计算,图的方向性,有向图模型方向取决于箭头贝叶斯网络随机变量间的因果关系MorepopularinAIandstatistics,无向图模型边没有箭头Markovrandomfields（马尔科夫随机场）更适合表达变量之间的软约束MorepopularinVisionandphysics,Bayesiannetworks,一种简单的，图形化的数据结构，用于表示变量之间的依赖关系（条件独立性），为任何全联合概率分布提供一种简明的规范。

Syntax语法:

asetofnodes,onepervariableadirected（有向）,acyclic（无环）graph（linkdirectinfluences）aconditionaldistributionforeachnodegivenitsparents:

P（Xi|Parents（Xi）量化其父节点对该节点的影响Inthesimplestcase,conditionaldistributionrepresentedasaconditionalprobabilitytable条件概率表（CPT）givingthedistributionoverXiforeachcombinationofparentvalues,Example,Topology（拓扑结构）ofnetworkencodesconditionalindependenceassertions:

Weather独立于其他变量ToothacheandCatchareconditionallyindependentgivenCavity,Example,我晚上在单位上班，此时邻居John给我打电话说我家警报响了，但是邻居Mary没有给打电话。

有时轻微的地震也会引起警报。

那么我家真正遭贼了吗？

Variables:

Burglary（入室行窃）,Earthquake,Alarm,JohnCalls,MaryCalls网络拓扑结构反映出因果关系:

AburglarcansetthealarmoffAnearthquakecansetthealarmoffThealarmcancauseMarytocallThealarmcancauseJohntocall,Examplecontd.,Compactness（紧致性）,ACPTforBooleanXiwithkBooleanparentshas2krowsforthecombinationsofparentvalues一个具有k个布尔父节点的布尔变量的条件概率表中有2k个独立的可指定概率EachrowrequiresonenumberpforXi=true（thenumberforXi=falseisjust1-p）Ifeachvariablehasnomorethankparents,thecompletenetworkrequiresO（n2k）numbersI.e.,growslinearlywithn,vs.O（2n）forthefulljointdistributionForburglarynet,1+1+4+2+2=10numbers（vs.25-1=31）,Globalsemantics（全局语义）,Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:

全联合概率分布可以表示为贝叶斯网络中的条件概率分布的乘积,Globalsemantics（全局语义）,Thefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:

全联合概率分布可以表示为贝叶斯网络中的条件概率分布的乘积,Localsemantics,Localsemantics:

eachnodeisconditionallyindependentofitsnondescendants（非后代）givenitsparents给定父节点，一个节点与它的非后代节点是条件独立的Theorem:

Localsemanticsglobalsemantics,CausalChains因果链,一个基本形式：

IsXindependentofZgivenY?

Evidencealongthechain“blocks”theinfluence,CommonCause共同原因,另一个基础的形态:

twoeffectsofthesamecauseAreXandZindependent?

AreXandZindependentgivenY?

Observingthecauseblocksinfluencebetweeneffects.,CommonEffect共同影响,最后一种配置形态:

twocausesofoneeffect（v-structures）AreXandZindependent?

Yes:

remembertheballgameandtheraincausingtraffic,nocorrelation?

AreXandZindependentgivenY?

No:

rememberthatseeingtrafficputtherainandtheballgameincompetition?

ThisisbackwardsfromtheothercasesObservingtheeffectenablesinfluencebetweencauses.,构造贝叶斯网络,Needamethodsuchthataseriesoflocallytestableassertionsofconditionalindependenceguaranteestherequiredglobalsemantics需要一种方法使得局部的条件独立关系能够保证全局语义得以成立ChooseanorderingofvariablesX1,XnFori=1tonaddXitothenetworkselectparentsfromX1,Xi-1suchthatP（Xi|Parents（Xi）=P（Xi|X1,.Xi-1）该父亲选择保证了全局语义:

构造贝叶斯网络,要求网络的拓扑结构确实反映了合适的父节点集对每个变量的那些直接影响。

添加节点的正确次序是首先添加“根本原因”节点，然后加入受它们直接影响的变量，以此类推。

Example,Example,Example,Example,Example,Examplecontd.,在非因果方向决定条件独立性是很难的（Causalmodelsandconditionalindependenceseemhardwiredforhumans!

）Networkislesscompact:

1+2+4+2+4=13numbersneeded,因果关系?

当贝叶斯网络反映真正的因果模式时:

Oftensimpler（nodeshavefewerparents）OfteneasiertothinkaboutOfteneasiertoelicitfromexperts（专家）BNs不一定必须是因果有时无因果关系的网络是存在的（especiallyifvariablesaremissing）箭头反映相关性，而不是因果关系箭头的真正含义是什么?

TopologymayhappentoencodecausalstructureTopologyreallyencodesconditionalindependence,InferenceinBayesiannetworks,推理任务,简单查询:

计算后验概率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）pathtimeandspacecostofvariableeliminationareO（dkn）多树上的变量消元的时间和空间复杂度都与网络规模呈线性关系。

Multiplyconnectednetworks多联通网络:

canreduce3SATtoexactinferenceNP-hardequivalenttocounting3SATmodels#P-complete,Example:

NaveBayesmodel,单一父亲变量和一批孩子变量，孩子变量在给定父亲变量下是相互独立的,NaveBayesmodel,Totalnumberofparameters（参数）islinearinn,Example:

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

Caps:

是否标题是彻底大写的Free:

是否标题中包含大写或小写的单词freee.g.:

amessagewiththesubjectheader“NEWMORTGAGERATE“islikelytobespam.Similarly,for“MoneyforFree”,“FREElunch”,etc.,Example:

垃圾邮件检测,模型的构建基于以下三个随机变量,Caps,FreeandSpam,eachofwhichtakeonthevaluesY（forYes）orN（forNo）Caps=YifandonlyifthesubjectofthemessagedoesnotcontainlowercaselettersFree=Yifandonlyifthewordfreeappearsinthesubject（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）isestimatedasthefractionofalldocumentsthatareofcategorycP（wordi=true|Category=c）isestimatedasthefractionofdocumentsofcategorycthatcontainwordi,TwentyNewsgroups,Given1000trainingdocumentsfromeachgroup.LearntoclassifynewdocumentsaccordingtowhichnewsgroupitcamefromNaveBayes:

89%classificationaccuracy,LearningCurvefor20Newsgroups,Example:

ADigitRecognizer,NaveBayesforDigits,简单版本:

一种特征Fijforeachgridposition可能的特征值是on/off,基于图像中像素的亮度是否大于或小于0.5每一个输入映射到一个特征向量,e.g.Here:

lotsoffeatures,eachisbinaryNaveBayesmodel:

Whatdoweneedtolearn?

Examples:

CPTs,CommentsonNaveBayes,Makesprobabilisticinferencetractablebymakingastrongassumptionofconditionalindependence.Tendstoworkfairlywelldespitethisstrongassumption.Experimentsshowittobequitecompetitivewithotherclassificationmethodsonstandarddatasets.Particularlypopularfortextcategorization,e.g.spamfiltering.,Summary,Bayesiannetworksprovideanaturalrepresentationfor（causallyinduced）conditionalindependenceTopology+CPTs=compactrepresentationofjointdistributionGenerallyeasyfordomainexpertstoconstructExactinferencebyvariableelimination:

polytimeonpolytrees,NP-hardongeneralgraphsspace=time,verysensitivetotopologyNaveBayesmodel,作业,14.3（a,b,c），14.4，14.7（a,b,c）（不交）,