人工智能的課件CH14Bayesiannetworkpart1

XIV.Bayesiannetworks

(section1-3)Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)XIV.Bayesiannetworks

(sectioOutlinesSyntaxSemanticsParameterizeddistributionsOutlinesSyntaxBayesiannetworksAsimple,graphicalnotationforconditionalindependenceassertionsandhenceforcompactspecificationoffulljointdistributionsSyntax:asetofnodes,onepervariableadirected,acyclicgraph(link≈"directlyinfluences")aconditionaldistributionforeachnodegivenitsparents:P(Xi|Parents(Xi))Inthesimplestcase,conditionaldistributionrepresentedasaconditionalprobabilitytable(CPT)givingthedistributionoverXiforeachcombinationofparentvaluesBayesiannetworksAsimple,graExampleTopologyofnetworkencodesconditionalindependenceassertions:WeatherisindependentoftheothervariablesToothacheandCatchareconditionallyindependentgivenCavityExampleTopologyofnetworkencExampleI'matwork,neighborJohncallstosaymyalarmisringing,butneighborMarydoesn'tcall.Sometimesit'ssetoffbyminorearthquakes.Isthereaburglar?Variables:Burglary,Earthquake,Alarm,JohnCalls,MaryCallsNetworktopologyreflects"causal"knowledge:AburglarcansetthealarmoffAnearthquakecansetthealarmoffThealarmcancauseMarytocallThealarmcancauseJohntocallExampleI'matwork,neighborJExamplecontd.Examplecontd.CompactnessACPTforBooleanXiwithkBooleanparentshas2krowsforthecombinationsofparentvaluesEachrowrequiresonenumberpforXi=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)CompactnessACPTforBooleanXSemanticsThesemanticsofBayesiannetworks:Arepresentationofthejointprobabilitydistribution. (Numericalsemantics)Anencodingofacollectionofconditionalindependencestatements. (Topologicalsemantics)SemanticsThesemanticsofBayeNumericalsemanticsThefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:NumericalsemanticsThefulljoNumericalsemanticsThefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:NumericalsemanticsThefulljoTopologicalsemanticsTopologicalsemantics:Eachnodeisconditionallyindependentofitsnon-descendantsgivenitsparentsTopologicalsemanticsTopologicMarkovblanketEachnodeisconditionallyindependentofallothersgivenitsMarkovblanket:parents+children+children'sparentsTheorem:TopologicalsemanticsNumericalsemanticsMarkovblanketEachnodeisconConstructingBayesiannetworks 1.ChooseanorderingofvariablesX1,…,Xn 2.Fori=1tonaddXitothenetworkselectparentsfromX1,…,Xi-1suchthat

P(Xi|Parents(Xi))=P(Xi|X1,...Xi-1)Thischoiceofparentsguarantees:P(X1,…,Xn)=πi=1

P(Xi|X1,…,Xi-1)(chainrule)

=πi=1P(Xi|Parents(Xi))(byconstruction)nnConstructingBayesiannetworksExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?P(B|A,J,M)=P(B)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?YesP(B|A,J,M)=P(B)?NoP(E|B,A,J,M)=P(E|A)?P(E|B,A,J,M)=P(E|A,B)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?No

P(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?YesP(B|A,J,M)=P(B)?NoP(E|B,A,J,M)=P(E|A)?NoP(E|B,A,J,M)=P(E|A,B)?YesExampleSupposewechoosetheoExamplecontd.Decidingconditionalindependenceishardinnoncausaldirections(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)Networkislesscompact:1+2+4+2+4=13numbersneededExamplecontd.CompactconditionaldistributionsCPTgrowsexponentiallywithnumberofparents(O(2k))CPTbecomesinfinitewithcontinuous-valuedparentorchildSolution:canonicaldistributionsthataredefinedcompactlyDeterministicnodesarethesimplestcase:CompactconditionaldistributiCompactconditionaldistributionscontd.Noisy-ORdistributionsmodelmultiplenoninteractingcauses

1)ParentsU1…Ukincludeallcauses(canaddleaknode) 2)Independentfailureprobabilityqiforeachcausealone Numberofparameterslinearinnumberofparents(O(k))CompactconditionaldistributiHybrid(discrete+continuous)networksDiscrete(Subsidy?andBuys?);continuous(HarvestandCost)

Option1:discretization——possiblylargeerrors,largeCPTs Option2:finitelyparameterizedcanonicalfamilies 1)Continuousvariable,discrete+continuousparents(e.g.,Cost) 2)Discretevariable,continuousparents(e.g.,Buys?)Hybrid(discrete+continuous)nContinuouschildvariablesNeedoneconditionaldensityfunctionforchildvariablegivencontinuousparents,foreachpossibleassignmenttodiscreteparentsMostcommonisthelinearGaussianmodel,e.g.,:MeanCostvarieslinearlywithHarvest,varianceisfixedLinearvariationisunreasonableoverthefullrange, butworksOKifthelikelyrangeofHarvestisnarrowContinuouschildvariablesNeedContinuouschildvariablesAll-continuousnetworkwithLGdistributions fulljointdistributionisamultivariateGaussianDiscrete+continuousLGnetworkisaconditionalGaussiannetworki.e.,amultivariateGaussianoverallcontinuousvariablesforeachcombinationofdiscretevariablevaluesContinuouschildvariablesDiscretevariablewithcontinuousparentsProbabilityofBuysgivenCostshouldbea“soft”threshold:ProbitdistributionusesintegralofGaussian:DiscretevariablewithcontinuWhytheprobit?1.It'ssortoftherightshape2.CanviewashardthresholdwhoselocationissubjecttonoiseWhytheprobit?1.It'ssortofDiscretevariablecontd.Sigmoid(orlogit)distributionalsousedinneuralnetworks:Sigmoidhassimilarshapetoprobitbutmuchlongertails:Discretevariablecontd.SigmoiSummaryBayesiannetworksprovideanaturalrepresentationfor(causallyinduced)conditionalindependenceTopology+CPTs=compactrepresentationofjointdistributionGenerallyeasyfordomainexpertstoconstructCanonicaldistributions(e.g.,noisy-OR)=compactrepresentationofCPTsContinuousvariablesparameterizeddistributions(e.g.,linearGaussian)SummaryBayesiannetworksproviXIV.Bayesiannetworks

(section1-3)Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)XIV.Bayesiannetworks

(sectioOutlinesSyntaxSemanticsParameterizeddistributionsOutlinesSyntaxBayesiannetworksAsimple,graphicalnotationforconditionalindependenceassertionsandhenceforcompactspecificationoffulljointdistributionsSyntax:asetofnodes,onepervariableadirected,acyclicgraph(link≈"directlyinfluences")aconditionaldistributionforeachnodegivenitsparents:P(Xi|Parents(Xi))Inthesimplestcase,conditionaldistributionrepresentedasaconditionalprobabilitytable(CPT)givingthedistributionoverXiforeachcombinationofparentvaluesBayesiannetworksAsimple,graExampleTopologyofnetworkencodesconditionalindependenceassertions:WeatherisindependentoftheothervariablesToothacheandCatchareconditionallyindependentgivenCavityExampleTopologyofnetworkencExampleI'matwork,neighborJohncallstosaymyalarmisringing,butneighborMarydoesn'tcall.Sometimesit'ssetoffbyminorearthquakes.Isthereaburglar?Variables:Burglary,Earthquake,Alarm,JohnCalls,MaryCallsNetworktopologyreflects"causal"knowledge:AburglarcansetthealarmoffAnearthquakecansetthealarmoffThealarmcancauseMarytocallThealarmcancauseJohntocallExampleI'matwork,neighborJExamplecontd.Examplecontd.CompactnessACPTforBooleanXiwithkBooleanparentshas2krowsforthecombinationsofparentvaluesEachrowrequiresonenumberpforXi=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)CompactnessACPTforBooleanXSemanticsThesemanticsofBayesiannetworks:Arepresentationofthejointprobabilitydistribution. (Numericalsemantics)Anencodingofacollectionofconditionalindependencestatements. (Topologicalsemantics)SemanticsThesemanticsofBayeNumericalsemanticsThefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:NumericalsemanticsThefulljoNumericalsemanticsThefulljointdistributionisdefinedastheproductofthelocalconditionaldistributions:NumericalsemanticsThefulljoTopologicalsemanticsTopologicalsemantics:Eachnodeisconditionallyindependentofitsnon-descendantsgivenitsparentsTopologicalsemanticsTopologicMarkovblanketEachnodeisconditionallyindependentofallothersgivenitsMarkovblanket:parents+children+children'sparentsTheorem:TopologicalsemanticsNumericalsemanticsMarkovblanketEachnodeisconConstructingBayesiannetworks 1.ChooseanorderingofvariablesX1,…,Xn 2.Fori=1tonaddXitothenetworkselectparentsfromX1,…,Xi-1suchthat

P(Xi|Parents(Xi))=P(Xi|X1,...Xi-1)Thischoiceofparentsguarantees:P(X1,…,Xn)=πi=1

P(Xi|X1,…,Xi-1)(chainrule)

=πi=1P(Xi|Parents(Xi))(byconstruction)nnConstructingBayesiannetworksExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?P(B|A,J,M)=P(B)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?NoP(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?YesP(B|A,J,M)=P(B)?NoP(E|B,A,J,M)=P(E|A)?P(E|B,A,J,M)=P(E|A,B)?ExampleSupposewechoosetheoExampleSupposewechoosetheorderingM,J,A,B,EP(J|M)=P(J)?No

P(A|J,M)=P(A|J)?

P(A|J,M)=P(A)?NoP(B|A,J,M)=P(B|A)?YesP(B|A,J,M)=P(B)?NoP(E|B,A,J,M)=P(E|A)?NoP(E|B,A,J,M)=P(E|A,B)?YesExampleSupposewechoosetheoExamplecontd.Decidingconditionalindependenceishardinnoncausaldirections(Causalmodelsandconditionalindependenceseemhardwiredforhumans!)Networkislesscompact:1+2+4+2+4=13numbersneededExamplecontd.CompactconditionaldistributionsCPTgrowsexponentiallywithnumberofparents(O(2k))CPTbecomesinfinitewithcontinuous-valuedparentorchildSolution:canonicaldistributionsthataredefinedcompactlyDeterministicnodesarethesimplestcase:CompactconditionaldistributiCompactconditionaldistributionscontd.Noisy-ORdistributionsmodelmultiplenoninteractingcauses

1)ParentsU1…Ukincludeallcauses(canaddleaknode) 2)Independentfailureprobabilityqiforeachcausealone Numberofparameterslinearinnumberofparents(O(k))CompactconditionaldistributiHybrid(discrete+continuous)networksDiscrete(Subsidy?andBuys?);continuous(HarvestandCost)

Option1:discretization——possiblylargeerrors,largeCPTs Option2:finitelyparameterizedcanonicalfamilies 1)Continuousvariable,discrete+continuousparents(e.g.,Cost) 2)Discretevariable,continuousparents(e.g.,Buys?)Hybrid(discrete+continuous)nContinuouschildvariablesNeedoneconditionaldensityfunctionforchildvariablegivencontinuousparents,foreachpossibleassignmenttodiscreteparentsMostcommonis