Learning Bayesian Networks From Data An Efficient

1LearningBayesianNetworksfromData:AnEfficientApproachBasedonInformationTheoryJieChengDept.ofComputingScienceUniversityofAlbertaAlberta,T6G2H1Email:[e-mail],WeiruLiuFacultyofInformatics,UniversityofUlster,UKBT370QBEmail:{w.liu,da.bell}@ulst.ac.ukAbstractThispaperaddressestheproblemoflearningBayesiannetworkstructuresfromdatabyusinganinformationtheoreticdependencyanalysisapproach.Basedonourthree-phaseconstructionmechanism,twoefficientalgorithmshavebeendeveloped.Oneofouralgorithmsdealswithaspecialcasewherethenodeorderingisgiven,thealgorithmonlyrequire)(2NOCItestsandiscorrectgiventhattheunderlyingmodelisDAG-Faithful[Spirteset.al.,1996].Theotheralgorithmdealswiththegeneralcaseandrequires)(4NOconditionalindependence(CI)tests.ItiscorrectgiventhattheunderlyingmodelismonotoneDAG-Faithful(seeSection4.4).AsystembasedonthesealgorithmshasbeendevelopedanddistributedthroughtheInternet.Theempiricalresultsshowthatourapproachisefficientandreliable.1IntroductionTheBayesiannetworkisapowerfulknowledgerepresentationandreasoningtoolunderconditionsofuncertainty.ABayesiannetworkisadirectedacyclicgraph(DAG)withaprobabilitytableforeachnode.ThenodesinaBayesiannetworkrepresentpropositionalvariablesinadomain,andthearcsbetweennodesrepresentthedependencyrelationshipsamongthevariables.OnconstructingBayesiannetworksfromdatabases,weusenodestorepresentdatabaseattributes.Inrecentyears,manyBayesiannetworkstructurelearningalgorithmshavebeendeveloped.Thesealgorithmsgenerallyfallintotwogroups,search&scoringbasedalgorithmsanddependencyanalysisbasedalgorithms.AnoverviewofthesealgorithmsispresentedinSection6.Althoughsomeofthesealgorithmscangivegoodresultsonsomebenchmarkdatasets,therearestillseveralproblems:•Nodeorderingrequirement.Alotofpreviousworkassumesthatnodeorderingisavailable.Unfortunately,inmanytimesthisisnotthecase.•Lackofefficiency.Somerecentalgorithmsdonotneednodeordering,buttheyaregenerallynotveryefficient.AllpracticabledependencyanalysisbasedalgorithmsrequireexponentialnumbersofCItests.•Lackofpubliclyavailablelearningtools.Althoughtherearemanyalgorithmsforthistask,onlyafewBayesiannetworklearningsystemsarepubliclyavailableandonlyoneofthem(TETRADII[Spirtes,et.al.,1996])canbeappliedtoreal-worlddataminingapplicationswherethedatasetsoftenhavehundredsofvariablesandmillionsofrecords.ThismotivatesustodoresearchintheareaofBayesiannetworkstructurelearning.Wedevelopedtwoalgorithmsforthistask,AlgorithmAandAlgorithmB.AlgorithmAdealswithaspecialcasewherethenodeorderingisgiven,whichrequires)(2NOCItestsandiscorrectgiventhattheunderlyingmodelisDAGfaithful.AlgorithmBdealswiththegeneralcaseandrequires)(4NOCItests.ItiscorrectgiventhattheunderlyingmodelismonotoneDAGfaithful.Basedonthesetwoalgorithms,wehavedevelopedaBayesiannetworklearningsystem,calledBayesianNetworkPowerConstructor.ThesystemhasbeenavailableontheInternetsinceOctober1997andhasalreadyenjoyedoveronethousanddownloads.Duetotheveryencouragingexperimentalresultsandpositivefeedbackfromotherusers,weplantoexpandourworktoallowcontinuousandhiddenvariablesintheunderlyingmodels.Wealsoplantodevelopacommercialversionofoursystemandintegrateittolargedatamining,knowledgebaseanddecisionsupportsystems.2Theremainderofthepaperisorganizedasfollows.Section2introducesBayesiannetworklearningfromaninformationtheoreticperspective.InSection3wepresentaBayesiannetworklearningalgorithm(AlgorithmA)foraspecialcasewhennodeorderingisgiven.Thecorrectnessproofandcomplexityanalysisarealsogiven.Section4presentsanextensionofAlgorithmA(calledAlgorithmB),whichdoesnotrequirenodeordering.Then,wegiveitscorrectnessproofandcomplexityanalysis.InSection5,wefirstintroduceourBayesiannetworklearningsystem(BNPowerConstructor),whichimplementsbothofouralgorithms.Then,weanalyzetheexperimentalresultsofbothalgorithmsonreal-worlddatasets.Section6surveysthealgorithmsofBayesiannetworklearningalgorithms.Finally,weconcludeourworkandproposesomefutureresearchdirectionsinSection7.2LearningBayesianNetworksUsingInformationTheoryInthissection,wefirstgivesomebasicconceptsrelatedwithBayesiannetworklearning.Thenweintroduceavitalconceptusedinourapproach-d-separation,fromaninformationtheoreticperspective.2.1BasicConceptsDefinition2.1.AdirectedgraphGcanbedefinedasanorderedpairthatconsistsofafinitesetVofnodesandanirreflexiveadjacencyrelationEonV.ThegraphGisdenotedas),(EV.ForeachEyx∈),(wesaythatthereisanarc(directededge)fromnodextonodey.Inthegraph,thisisdenotedbyanarrowfromxtoyandxandyarecalledthestartpointandtheendpointofthearrowrespectively.Wealsosaythatnodexandnodeyareadjacentorxandyareneighborsofeachother.xisalsocalledaparentofyandyiscalledachildofx.Byusingtheconceptsofparentandchildrecursively,wecanalsodefinetheconceptofancestoranddescendent.Wealsocallanodethatdoesnothaveanyparentarootnode.ByirreflexiveadjacencyrelationwemeanthatforanyVx∈,Exx∉),(,i.e.,anarccannothaveanodeasbothitsstartpointandendpoint.Definition2.2.InBayesiannetworklearning,weoftenneedtofindapaththatconnectstwonodeswithoutconsideringthedirectionalityoftheedgesonthepath.Todistin