PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceWednesday, March 15, 2000William H. HsuDepartment of Computing and Information Sciences, KSUhttp://www.cis.ksu.edu/~bhsuReadings:“The Lumière Project: Inferring the Goals and Needs of Software Users”, Horvitz et al(Reference) Chapter 15, Russell and NorvigUncertain Reasoning Discussion (3 of 4):Bayesian Network ApplicationsLecture 25Lecture 25Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLecture OutlineLecture Outline•Readings–Chapter 15, Mitchell–References: Pearl and Verma; tutorials (Heckerman, Friedman and Goldszmidt)•More Bayesian Belief Networks (BBNs)–Inference: applying CPTs–Learning: CPTs from data, elicitation–In-class demo: Hugin (CPT elicitation, application)•Learning BBN Structure–K2 algorithm–Other probabilistic scores and search algorithms•Causal Discovery: Learning Causality from Observations•Next Class: Last BBN Presentation (Yue Jiao: Causality)•After Spring Break–KDD–Genetic Algorithms (GAs) / Programming (GP)Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceBayesian Networks:Bayesian Networks: Quick Review Quick ReviewX1X2X3X4Season:SpringSummerFallWinterSprinkler: On, OffRain: None, Drizzle, Steady, DownpourGround-Moisture:Wet, DryX5Ground-Slipperiness:Slippery, Not-SlipperyP(Summer, Off, Drizzle, Wet, Not-Slippery) = P(S) · P(O | S) · P(D | S) · P(W | O, D) · P(N | W) •Recall: Conditional Independence (CI) Assumptions•Bayesian Network: Digraph Model–Vertices (nodes): denote events (each a random variable)–Edges (arcs, links): denote conditional dependencies•Chain Rule for (Exact) Inference in BBNs–Arbitrary Bayesian networks: NP-complete–Polytrees: linear time•Example (“Sprinkler” BBN)•MAP, ML Estimation over BBNs    niiin21Xparents |XPX , ,X,XP1 h|DPmaxarghHhMLKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLearning Distributions in BBNs:Learning Distributions in BBNs:Quick ReviewQuick Review•Learning Distributions–Shortcomings of Naïve Bayes–Making judicious CI assumptions–Scaling up to BBNs: need to learn a CPT for all parent sets–Goal: generalization•Given D (e.g., {1011, 1001, 0100})•Would like to know P(schema): e.g., P(11**)  P(x1 = 1, x2 = 1)•Variants–Known or unknown structure–Training examples may have missing values•Gradient Learning Algorithm–Weight update rule–Learns CPTs given data points D Dxijkikijhijkijkwx |u,yPrwwKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLearning StructureLearning Structure•Problem Definition–Given: data D (tuples or vectors containing observed values of variables)–Return: directed graph (V, E) expressing target CPTs (or commitment to acquire)•Benefits–Efficient learning: more accurate models with less data - P(A), P(B) vs. P(A, B)–Discover structural properties of the domain (causal relationships)•Acccurate Structure Learning: Issues–Superfluous arcs: more parameters to fit; wrong assumptions about causality–Missing arcs: cannot compensate using CPT learning; ignorance about causality•Solution Approaches–Constraint-based: enforce consistency of network with observations–Score-based: optimize degree of match between network and observations•Overview: Tutorials–[Friedman and Goldszmidt, 1998] http://robotics.Stanford.EDU/people/nir/tutorial/–[Heckerman, 1999] http://www.research.microsoft.com/~heckermanKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial Intelligence•Constraint-Based–Perform tests of conditional independence–Search for network consistent with observed dependencies (or lack thereof)–Intuitive; closely follows definition of BBNs–Separates construction from form of CI tests–Sensitive to errors in individual tests•Score-Based–Define scoring function (aka score) that evaluates how well (in)dependencies in a structure match observations–Search for structure that maximizes score–Statistically and information theoretically motivated–Can make compromises•Common Properties–Soundness: with sufficient data and computation, both learn correct structure–Both learn structure from observations and can incorporate knowledgeLearning Structure:Learning Structure:Constraints Versus ScoresConstraints Versus ScoresKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLearning Structure:Learning Structure:MMaximum aximum WWeight eight SSpanning panning TTree (Chow-Liu)ree (Chow-Liu)•Algorithm Learn-Tree-Structure-I (D)–Estimate P(x) and P(x, y) for all single RVs, pairs; I(X; Y) = D(P(X, Y) || P(X) · P(Y))–Build complete undirected graph: variables as vertices, I(X; Y) as edge weights–T  Build-MWST (V  V, Weights) // Chow-Liu algorithm: weight function  I–Set directional flow on T and place the CPTs on its edges (gradient learning)–RETURN: tree-structured BBN with CPT values•Algorithm Build-MWST-Kruskal (E  V  V, Weights: E  R+)–H  Build-Heap (E, Weights) // aka priority queue (|E|)–E’  Ø; Forest  {{v} | v  V} // E’: set; Forest: union-find (|V|)–WHILE Forest.Size > 1 DO (|E|)•e  H.Delete-Max() // e  new edge from H (lg |E|)•IF ((TS  Forest.Find(e.Start))  (TE  Forest.Find(e.End))) THEN (lg* |E|)E’.Union(e) // append edge e; E’.Size++ (1)Forest.Union (TS, TE) // Forest.Size-- (1)–RETURN E’ (1)•Running Time: (|E| lg |E|) = (|V|2 lg |V|2) = (|V|2 lg |V|) = (n2 lg n)Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial Intelligence•General-Case BBN Structure Learning: Use Inference to Compute Scores•Recall: Bayesian Inference aka Bayesian Reasoning–Assumption: h  H are mutually exclusive and exhaustive–Optimal strategy: combine predictions of