PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceWednesday, March 8, 2000Jincheng GaoDepartment of Geography, KSUReadings:“Learning Bayesian Network Structure from Massive Datasets: The ‘Sparse Candidate’ Algorithm” Friedman, Nachman, and PeerUncertainty Reasoning Presentation(2 of 4)Learning Bayesian Networks from DataLecture 22Lecture 22Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligencePresentation OutlinePresentation Outline•Paper–“Learning Bayesian Network Structure from Massive Datasets: The ‘Sparse Candidate’ Algorithm”–Author: Nir Friedman, Iftach Nachman and Dana Peer, Hebrew University, Israel•Overview–Introduction to Bayesian Network –Outline of “Sparse Candidate” Algorithm –How to Choose Candidate Sets–Learning with Small Candidate Sets–Experimental Evaluation •Goal–Introduces an algorithm that achieves a faster learning by restricting the search space•References–Machine learning, T. M. Mitchell–Artificial Intelligence: A Modern Approach, S. J. Russell and P. Norvig–Bayesian Networks without Tears, E. CharniakKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligencePresentation OutlinePresentation Outline•Issues–How to guarantee all available candidate parents are selected–What is the criteria to stop its iteration to get a maximum score of network–Strengths: It presents a very useful algorithm to restrict search space in BBN–Weaknesses: It doesn’t consider spurious dependent variables•Outline–Why learn a Bayesian network–Introduction to Bayesian networkºTerminology of Bayesian networkºWhat is Bayesian networkºHow to construct a Bayesian network–“Sparse Candidate” algorithmsºMaximize spanning tree structureº“Sparse candidate” algorithm–How to select candidate parents–How to find the maximize score of a Bayesian network–Experimental EvaluationKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceInduceE BRACRepresents:• P(E, B, R, A, C)• Independence Statements• CausalityIntroduction to Bayesian NetworkIntroduction to Bayesian Network• Why learn a Bayesian network? –Solves the uncertain problems that are difficult for logic inference–Combines knowledge engineering and statistical induction–Covers the whole spectrum from knowledge-intensive model construction to data-intensive model induction – More than a learning black-box– Causal representation, reasoning, and discovery– Increasing interests in AIKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceE(1)(2)(3)X Y(1) – Block Conditions Z is in E and Z has one arrow on the path leading in and one arrow out(2) Z is in E and Z has both path arrows leading out(3) Neither Z nor any descendant of Z is in E, and both arrows lead in to Z• Terminology of Bayesian network– Conditional Independence If every undirected path from a node in X to a node in Y is d-separated by E, then X and Y are conditionally independent given E. – D-separate A set of node E d-separates two sets of nodes X and Y if every undirected path from a node in X to a node in Y is blocked given E.Bayesian NetworksBayesian NetworksZZZKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial Intelligence•Bayesian Network A directed acyclic graph that represents a joint probability distribution for a set of random variables.–Vertices (nodes): denote events (each a random variable)–Edges (arcs, links): denote conditional dependencies –Conditional probability tables (CPT)–Assumptions - Each node is asserted to be conditionally dependent of its nondescendants, given its immediate parents •Chain Rule for (Exact) inference in Bayesian networks P(X1, X2, …, Xn) = ni=1 P(Xi | Pa(Xi))•ExampleBayesian NetworksBayesian NetworksFamily-out (fo)Bowel-problem (bp)Light-on (lo)Dog-out (do)Hear-bark (hb)P(fo) = .15P(bp) = .01P(lo |fo) = .6P(lo | ¬fo)= .05P(hb |do) = .7P(hb | ¬do) = .01P(do | fo bp) = .99P(do | fo ¬bp) = .90P(do | ¬fo bp) = .97P(do | ¬fo bp) = .3Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial Intelligence–Score-Based•Define scoring function (aka score) that evaluates how well (in)dependencies in a structure match observations, such as Bayesian score and MDL °Bayesian Score for Marginal Likelihood P(D|h)•Search for structure that maximizes score•Decomposability Score(G:D) = score(Xi | Par(Xi ) : Nxi, par( Xi) ) i –Common Properties•Soundness: with sufficient data and computation, both learn correct structure•Both learn structure from observations and can incorporate knowledge•Constrain-based is sensitive to errors in test                   ZiiiΓxParentsPaPa ,Xxx Pa ,xαΓPa ,xNPa ,xαΓ PaNPaαΓPaαΓh|DPihhhiijini xXhihihiPahhhikiiiiiihiiii for !1 of value particular of value particularwhere1,Bayesian NetworksBayesian NetworksKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLearning StructureLearning Structure•Learning Weights (Conditional Probability Tables)–Given training data and network structure to learn target variable•Naïve Bayesian network –Given network structure and some training data to estimate unobserved variable values.•Gradient ascent algorithm°Weight update rule–Given training data to build a network structure•Build structure of Bayesian networks–Constraint-Based•Perform tests of conditional independence•Search for network consistent with observed dependencies•Intuitive; closely follows definition of BBNs•Separates construction from form of CI tests Dxijkikijhijkijkwx |u,yPrwwKansas State UniversityDepartment of Computing and