10-601 Recitation Wednesday, October 19th, 2011Will BishopMarkov BlanketsMain idea: Want the simplest form we can express probability of a random variable conditioned on all other random variables in the graph. Very simple. Can simply condition on: 1) Parents2) Co-Parents3) ChildrenB CDA EFP(B|A,C,D,E,F) = ?Markov BlanketsMain idea: Want this simplest form we can express probability of a random variable conditioned on all other random variables in the graph. Very simple. Can simply condition on: 1) Parents2) Co-Parents3) ChildrenB CDA EFP(B|A,C,D,E,F) = ?Markov BlanketsMain idea: Want this simplest form we can express probability of a random variable conditioned on all other random variables in the graph. Very simple. Can simply condition on: 1) Parents2) Co-Parents3) ChildrenB CDA EFP(B|A,C,D,E,F) = ?Markov BlanketsMain idea: Want this simplest form we can express probability of a random variable conditioned on all other random variables in the graph. Very simple. Can simply condition on: 1) Parents2) Co-Parents3) ChildrenB CDA EFP(B|A,C,D,E,F) = ?Markov BlanketsMain idea: Want this simplest form we can express probability of a random variable conditioned on all other random variables in the graph. Very simple. Can simply condition on: 1) Parents2) Co-Parents3) ChildrenB CDA EFP(B|A,C,D,E,F) = P(B|A, C, D)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (N = 1) =2Xa=12Xf=12Xs=12Xh=1P (A = a, F = f,S = s, H = h, N = 1)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (N = 1) =2Xa=12Xf=12Xs=12Xh=1P (A = a, F = f,S = s, H = h, N = 1)Requires 2^4 = 16 calculations.Can we do better?Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (A, F, S, H, N)=P (A)P (F )P (S|A, F )P (H|S)P (N|S)Let’s think about how we can rearrange the sum. P (N = 1) =XAXFXSXHP (A, F, S, H, N = 1)=XAXFXSXHP (A)P (F )P (S|A, F )P (H|S)P (N =1|S)=XSXHP (H|S)P (N =1|S) XAXFP (A)P (F )P (S|A, F )!=XSXHP (H|S)P (N =1|S) P (S)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (A, F, S, H, N )=P (A)P (F )P (S|A, F )P (H|S)P (N|S)Let’s think about how we can rearrange the sum. P (N = 1) =XAXFXSXHP (A, F, S, H, N = 1)=XAXFXSXHP (A)P (F )P (S|A, F )P (H|S)P (N =1|S)=XSXHP (H|S)P (N =1|S) XAXFP (A)P (F )P (S|A, F )!=XSXHP (H|S)P (N =1|S) P (S)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (A, F, S, H, N )=P (A)P (F )P (S|A, F )P (H|S)P (N|S)Let’s think about how we can rearrange the sum. P (N = 1) =XAXFXSXHP (A, F, S, H, N = 1)=XAXFXSXHP (A)P (F )P (S|A, F )P (H|S)P (N =1|S)=XSXHP (H|S)P (N =1|S) XAXFP (A)P (F )P (S|A, F )!=XSXHP (H|S)P (N =1|S) P (S)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (A, F, S, H, N )=P (A)P (F )P (S|A, F )P (H|S)P (N|S)Let’s think about how we can rearrange the sum. P (N = 1) =XAXFXSXHP (A, F, S, H, N = 1)=XAXFXSXHP (A)P (F )P (S|A, F )P (H|S)P (N =1|S)=XSXHP (H|S)P (N =1|S) XAXFP (A)P (F )P (S|A, F )!=XSXHP (H|S)P (N =1|S) P (S)Inference7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b) From class: How do we calculate P(N = 1)?P (A, F, S, H, N )=P (A)P (F )P (S|A, F )P (H|S)P (N|S)Let’s think about how we can rearrange the sum. P (N = 1) =XAXFXSXHP (A, F, S, H, N = 1)=XAXFXSXHP (A)P (F )P (S|A, F )P (H|S)P (N =1|S)=XSXHP (H|S)P (N =1|S) XAXFP (A)P (F )P (S|A, F )!=XSXHP (H|S)P (N =1|S) P (S)4 Calculations4 CalculationsLearningAssume graph structure is known and all data is observed.Key Idea: Can just solve this with the standard MLE techniques we already know.LearningAssume graph structure is known and some data is unobserved.Key Idea: Pick parameters that make observed data the most probable.Expectation MaximizationE-Step:M-Step:Calculated usingˆ✓tRepeat until convergence :)Q(✓|ˆ✓t)=EP (Z|X,ˆ✓t)(log (P (X, Z|✓))ˆ✓t+1= argmax✓hQ(✓|ˆ✓t)iEM & Clustering: A simple exampleCan we draw a directed graph to represent this model? • Z can be either 0 or 1 but we do not know the prior probab i l ity of Z being0 or 1.• If Z is 0, then we pull a sample for X from a Normal distribution withunknown mean µ0and known variance 2.• If Z is 1, then we pull a sample for X from a Normal distribution withunknown
View Full Document