1Bayesian Networks –Structure Learning (cont.) Machine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityApril 3rd, 2006Koller & Friedman Chapters (handed out):Chapter 11 (short)Chapter 12: 12.1, 12.2, 12.3 (covered in the beginning of semester)12.4 (Learning parameters for BNs)Chapter 13: 13.1, 13.3.1, 13.4.1, 13.4.3 (basic structure learning)Learning BN tutorial (class website):ftp://ftp.research.microsoft.com/pub/tr/tr-95-06.pdfTAN paper (class website):http://www.cs.huji.ac.il/~nir/Abstracts/FrGG1.html2Learning Bayes netsMissing dataFully observable dataUnknown structureKnown structurex(1)…x(m)Datastructure parametersCPTs –P(Xi| PaXi)3Learning the CPTsx(1)…x(M)DataFor each discrete variable XiWHY??????????4Information-theoretic interpretation of maximum likelihood Given structure, log likelihood of data:FluAllergySinusHeadacheNose5Maximum likelihood (ML) for learning BN structureData<x1(1),…,xn(1)>…<x1(M),…,xn(M)>FluAllergySinusHeadacheNosePossible structuresScore structureLearn parametersusing ML6Information-theoretic interpretation of maximum likelihood 2 Given structure, log likelihood of data:FluAllergySinusHeadacheNose7Information-theoretic interpretation of maximum likelihood 3 Given structure, log likelihood of data:FluAllergySinusHeadacheNose8Mutual information → Independence 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:9Decomposable score Log data likelihood10Scoring a tree 1: equivalent trees11Scoring a tree 2: similar trees12Chow-Liu tree learning algorithm 1 For each pair of variables Xi,Xj Compute empirical distribution: Compute mutual information: Define a graph Nodes X1,…,Xn Edge (i,j) gets weight13Chow-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 directions14Can 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:15Can we extend Chow-Liu 2 (Approximately learning) models with tree-width up to k [Narasimhan & Bilmes ’04] But, O(nk+1)…16Scoring general graphical models –Model selection problemData<x_1^{(1)},…,x_n^{(1)}>…<x_1^{(m)},…,x_n^{(m)}>FluAllergySinusHeadacheNoseWhat’s the best structure?The more edges, the fewer independence assumptions,the higher the likelihood of the data, but will overfit…17Maximum likelihood overfits! Information never hurts: Adding a parent always increases score!!!18Bayesian score avoids overfitting Given a structure, distribution over parameters Difficult integral: use Bayes information criterion (BIC) approximation (equivalent as M→ ∞) Note: regularize with MDL scoreBest BN under BIC still NP-hard19How many graphs are there?20Structure learning for general graphs In a tree, a node only has one parent Theorem: The problem of learning a BN structure with at most dparents is NP-hard for any (fixed) d≥2 Most structure learning approaches use heuristics Exploit score decomposition (Quickly) Describe two heuristics that exploit decomposition in different ways21Learn BN structure using local searchStarting from Chow-Liu treeLocal search,possible moves:• Add edge• Delete edge• Invert edgeScore using BIC22What you need to know about learning BNs Learning BNs Maximum likelihood or MAP learns parameters Decomposable score Best tree (Chow-Liu) Best TAN Other BNs, usually local search with BIC score23Unsupervised learning or Clustering –K-meansGaussian mixture modelsMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityApril 3rd, 200624Some Data25K-means1. Ask user how many clusters they’d like. (e.g. k=5)26K-means1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations27K-means1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations3. Each datapoint finds out which Center it’s closest to. (Thus each Center “owns”a set of datapoints)28K-means1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations3. Each datapoint finds out which Center it’s closest to.4. Each Center finds the centroid of the points it owns29K-means1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations3. Each datapoint finds out which Center it’s closest to.4. Each Center finds the centroid of the points it owns…5. …and jumps there6. …Repeat until terminated!30Unsupervised Learning You walk into a bar.A stranger approaches and tells you:“I’ve got data from k classes. Each class produces observations with a normal distribution and variance σ2·I . Standard simple multivariate gaussian assumptions. I can tell you all the P(wi)’s .” So far, looks straightforward.“I need a maximum likelihood estimate of the µi’s .“ No problem:“There’s just one thing. None of the data are labeled. I have datapoints, but I don’t know what class they’re from (any of them!) Uh oh!!31Gaussian Bayes Classifier Reminder)()()|()|(xxxpiyPiypiyP====( ) ( ))(21exp||||)2(1)|(2/12/xµxΣµxΣxppiyPiikiTikim−−−==πHow do we deal with that?32Predicting wealth from age33Predicting wealth from age34Learning modelyear , mpg ---> maker=mmmmm2212221211212σσσσσσσσσLMOMMLLΣ35General: O(m2)parameters=mmmmm2212221211212σσσσσσσσσLMOMMLLΣ36Aligned: O(m)parameters=−mm21232221200000000000000000000σσσσσLLMMOMMMLLLΣ37Aligned: O(m)parameters=−mm21232221200000000000000000000σσσσσLLMMOMMMLLLΣ38Spherical: O(1)cov parameters=2222200000000000000000000σσσσσLLMMOMMMLLLΣ39Spherical: O(1)cov parameters=2222200000000000000000000σσσσσLLMMOMMMLLLΣ40Next… back to Density EstimationWhat if we want to do density
View Full Document
Unlocking...