Structure Learning:the good, the bad, the uglyAnnouncementsWhere are we?Learning the structure of a BNRemember: Obtaining a P-map?September 21st lecture… Independence testsIndependence tests and the constraint based approachScore-based approachInformation-theoretic interpretation of maximum likelihoodInformation-theoretic interpretation of maximum likelihood 2Decomposable scoreHow many trees are there?Scoring a tree 1: I-equivalent treesScoring a tree 2: similar treesChow-Liu tree learning algorithm 1Chow-Liu tree learning algorithm 2Can we extend Chow-Liu 1Can we extend Chow-Liu 2Maximum likelihood overfits!Bayesian scoreBayesian score and model complexityBayesian, a decomposable scoreBIC approximation of Bayesian scoreBIC approximation, a decomposable scoreConsistency of BIC and Bayesian scoresPriors for general graphsBDe priorScore equivalenceChow-Liu for Bayesian scoreStructure learning for general graphsUnderstanding score decompositionFixed variable order 1Fixed variable order 2Learn BN structure using local searchExploit score decomposition in local searchOrder search versus graph searchBayesian model averagingWhat you need to know about learning BN structuresKoller & Friedman Chapter 13Structure Learning:the good, the bad, the ugly Graphical Model – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 24th, 2005Announcements Project feedback by e-mail soonWhere are we? Bayesian networks Undirected models Exact inference in GMs Very fast for problems with low tree-width Can also exploit CSI and determinism Learning GMs Given structure, estimate parameters Maximum likelihood estimation (just counts for BNs) Bayesian learning MAP for Bayesian learning What about learning structure?Learning the structure of a BN Constraint-based approach BN encodes conditional independencies Test conditional independencies in data Find an I-map Score-based approach Finding a structure and parameters is a density estimation task Evaluate model as we evaluated parameters Maximum likelihood Bayesian etc. Data<x1(1),…,xn(1)>…<x1(M),…,xn(M)>FluAllergySinusHeadacheNoseLearn structure andparametersRemember: Obtaining a P-map?September 21stlecture… ☺ Given the independence assertions that are true for P Obtain skeleton Obtain immoralities From skeleton and immoralities, obtain every (and any) BN structure from the equivalence class Constraint-based approach: Use Learn PDAG algorithm Key question: Independence testIndependence tests Statistically difficult task! Intuitive approach: Mutual information Mutual information and independence: Xiand Xjindependent if and only if I(Xi,Xj)=0 Conditional mutual information:Independence tests and the constraint based approach Using the data D Empirical distribution: Mutual information: Similarly for conditional MI Use learning PDAG algorithm: When algorithm asks: (X⊥Y|U)? Must check if statistically-signifficant Choosing t See reading…Score-based approachLearn parametersScore structurePossible structuresData<x1(1),…,xn(1)>…<x1(M),…,xn(M)>FluAllergySinusHeadacheNoseInformation-theoretic interpretation of maximum likelihood Given structure, log likelihood of data:FluAllergySinusHeadacheNoseInformation-theoretic interpretation of maximum likelihood 2 Given structure, log likelihood of data:FluAllergySinusHeadacheNoseDecomposable score Log data likelihood Decomposable score: Decomposes over families in BN (node and its parents) Will lead to significant computational efficiency!!! Score(G: D) = ∑iFamScore(Xi|PaXi: D)How many trees are there?Nonetheless – Efficient optimal algorithm finds best treeScoring a tree 1: I-equivalent treesScoring a tree 2: similar treesChow-Liu tree learning algorithm 1 For each pair of variables Xi,XjCompute empirical distribution: Compute mutual information: Define a graph Nodes X1,…,Xn Edge (i,j) gets weightChow-Liu tree learning algorithm 2 Optimal tree BN Compute maximum weight spanning tree Directions in BN: pick any node as root, breadth-first-search defines directionsCan we extend Chow-Liu 1 Tree augmented naïve Bayes (TAN) [Friedman et al. ’97] Naïve Bayes model overcounts, because correlation between features not considered Same as Chow-Liu, but score edges with:Can we extend Chow-Liu 2 (Approximately learning) models with tree-width up to k [Narasimhan & Bilmes ’04] But, O(nk+1)…Maximum likelihood overfits! Information never hurts: Adding a parent always increases score!!!Bayesian score Prior distributions: Over structures Over parameters of a structure Posterior over structures given data:Bayesian score and model complexityXYTrue model: Structure 1: X and Y independent Score doesn’t depend on alpha Structure 2: X → Y Data points split between P(Y=t|X=t) and P(Y=t|X=f) For fixed M, only worth it for large α Because posterior of less diffuseP(Y=t|X=t) = 0.5 + αP(Y=t|X=f) = 0.5 - αBayesian, a decomposable score As with last lecture, assume: Local and global parameter independence Also, prior satisfies parameter modularity: If Xihas same parents in G and G’, then parameters have same prior Finally, structure prior P(G) satisfies structure modularity Product of terms over families E.g., P(G) ∝ c|G| Bayesian score decomposes along families!BIC approximation of Bayesian score Bayesian has difficult integrals For Dirichlet prior, can use simple Bayesinformation criterion (BIC) approximation In the limit, we can forget prior! Theorem: for Dirichlet prior, and a BN with Dim(G) independent parameters, as M→∞:BIC approximation, a decomposable score BIC: Using information theoretic formulation:Consistency of BIC and Bayesian scoresConsistency is limiting behavior, says nothing about finite sample size!!! A scoring function is consistent if, for true model G*, as M→∞, with probability 1 G*maximizes the score All structures not I-equivalent to G*have strictly lower score Theorem: BIC score is consistent Corollary: the Bayesian score is consistent What about maximum likelihood?Priors for general graphs For finite datasets, prior is important! Prior over structure satisfying prior modularity What about prior over parameters, how do we represent it? K2 prior: fix an α,
View Full Document
Unlocking...