Inference in Bayesian Nets - ecology lab

Inference in Bayesian Nets - ecology lab

Inference in Bayesian Nets Objective: calculate posterior prob of a variable x conditioned on evidence Y and marginalizing over Z (unobserved vars) Exact methods: Enumeration Factoring Variable elimination Factor graphs (read 8.4.2-8.4.4 in Bishop, p. 398-411) Belief propagation Approximate Methods: sampling (read Sec 14.5)

from: Inference in Bayesian Networks (DAmbrosio, 1999) Factors A factor is a multi-dimensional table, like a CPT fAJM(B,E) 2x2 table with a number for each combination of B,E Specific values of J and M were used A has been summed out p(j|a) p(j|a) p(j|a) p(j|a) f(J,A)=P(J|A) is 2x2: fJ(A)=P(j|A) is 1x2: {p(j|a),p(j|a)} Use of factors in variable elimination: Pointwise product given 2 factors that share some variables: f1(X1..Xi,Y1..Yj), f2(Y1..Yj,Z1..Zk)

resulting table has dimensions of union of variables, f1*f2=F(X1..Xi,Y1..Yj,Z1..Zk) each entry in F is a truth assignment over vars and can be computed by multiplying entries from f1 and f2 A B f1(A,B) B C f2(B,C) A

B C F(A,B,C) T T 0.3 T T 0.2 T

T T 0.3x0.2 T F 0.7 T F 0.8

T T F 0.3x0.8 F T 0.9 F T 0.6

T F T 0.7x0.6 F F 0.1 F F

0.4 T F F 0.7x0.4 F T T 0.9x0.2 F

T F 0.9x0.8 F F T 0.1x0.6 F F

F 0.1x0.4 Factor Graph Bipartite graph variable nodes and factor nodes one factor node for each factor in joint prob. edges connect to each var contained in each factor F(B) F(E) B E

F(A,B,E) A F(J,A) J F(M,A) M Message passing Choose a root node, e.g. a variable whose marginal prob you want, p(A) Assign values to leaves For variable nodes, pass =1 For factor nodes, pass prior: f(X)=p(X)

Pass messages from var node v to factor u Product over neighboring factors Pass messages from factor u to var node v sum out neighboring vars w Terminate when root receives messages from all neighbors or continue to propagate messages all the way back to leaves Final marginal probability of var X: product of messages from each neighboring factor; marginalizes out all variables in tree beyond neighbor Conditioning on evidence: Remove dimension from factor (sub-table) F(J,A) -> FJ(A)

Belief Propagation (this figure happens to come from http://www.pr-owl.org/basics/bn.php) see also: wiki, Ch. 8 in Bishop PR&ML Computational Complexity Belief propagation is linear in the size of the BN for polytrees Belief propagation is NP-hard for trees with cycles Inexact Inference Sampling Generate a (large) set of atomic events (joint variable assignments) <-e,b,a,j,m> ...

Answer queries like P(J=t|A=f) by averaging how many times events with J=t occur among those satisfying A=f Direct sampling create an independent atomic event for each var in topological order, choose a value conditionally dependent on parents 1. 2. 3. 4. sample from p(Cloudy)=<0.5,0.5>; suppose T

sample from p(Sprinkler|Cloudy=T)=<0.1,0.9>, suppose F sample from P(Rain|Cloudy=T)=<0.8,0.2>, suppose T sample from P(WetGrass|Sprinkler=F,Rain=T)=<0.9,0,1>, suppose T event: repeat many times in the limit, each event occurs with frequency proportional to its joint probability, P(Cl,Sp,Ra,Wg)= P(Cl)*P(Sp|Cl)*P(Ra|Cl)*P(Wg|Sp,Ra) averaging: P(Ra,Cl) = Num(Ra=T&Cl=T)/|Sample| Rejection sampling to condition upon evidence variables e, average over samples that satisfy e

P(j,m|e,b) <-e,b,a,j,m> <-e,-b,-a,-j,m> <-e,-b,a,-j,-m> <-e,-b,a,j,-m> ... Likelihood weighting sampling might be inefficient if conditions are rare P(j|e) earthquakes only occur 0.2% of the time, so can only use ~2/1000 samples to determine frequency of JohnCalls during sample generation, when reach an evidence variable ei, force it to be known value accumulate weight w= p(ei|parents(ei))

now every sample is useful (consistent) when calculating averages over samples x, weight them: P(j|e) = consistent w(x)= Gibbs sampling (MCMC) start with a random assignment to vars set evidence vars to observed values iterate many times... pick a non-evidence variable, X define Markov blanket of X, mb(X) parents, children, and parents of children re-sample value of X from conditional distrib. P(X|mb(X))=P(X|parents(X))* P(y|parents(X)) for ychildren(X) generates a large sequence of samples, where each might flip a bit from previous sample

in the limit, this converges to joint probability distribution (samples occur for frequency proportional to joint PDF) Other types of graphical models Hidden Markov models Gaussian-linear models Dynamic Bayesian networks Learning Bayesian networks known topology: parameter estimation from data structure learning: topology that best fits the data Software BUGS Microsoft

Recently Viewed Presentations

  • Becoming an Agent of Reconciliation

    Becoming an Agent of Reconciliation

    John 3:16-18 Is The Heart of God's Great News [or bad news] "For God so loved the world that he gave his one and only Son, that whoever believes in him shall not perish but have eternal life. 17For God...
  • Distracted Driving: Review of Current Needs, Efforts and ...

    Distracted Driving: Review of Current Needs, Efforts and ...

    A review of the nationally proposed driver education curriculum from ADTSEA and VAs new Driver Education Curriculum found no item or module addressing skills training for how to multitask of use In-Vehicle Information Systems while driving.
  • Poetry

    Poetry

    A tanka poem is similar to a haiku but has two additional lines. I love my kitten. She is so little and cute. She has a pink tongue, And lots of long whiskers too. She purrs when I stroke her...
  • Introduction to IaaS - National Tsing Hua University

    Introduction to IaaS - National Tsing Hua University

    Clos Network. Clos is a multistage circuit switching network, Formalized by Charles Clos in 1953. Example: 3 stage, 16 port Clos network. Each (input, output) has 4 paths. 12/13/2011. NTHU CS5421 Cloud Computing
  • The Role of Early Tertiary Underplating in Epeirogenesis on ...

    The Role of Early Tertiary Underplating in Epeirogenesis on ...

    Supported by the University of Leicester Teaching Enhancement Fund Department of Geology Student profile c. 70 students per year taking a variety of first degrees in Earth Sciences 15 % mature (22+) students 60% male 40% female 'Traditional' teaching Lectures...
  • 4.3.1 Heart of the Matter - avon-schools.org

    4.3.1 Heart of the Matter - avon-schools.org

    Think about each square in the box as a chamber of the heart. Label the right and left atria - "RA" and "LA." Label the right and left ventricle - "RV" and "LV." Remember: you are looking directly at a...
  • Origin of Solar System & 12.3 Asteroids and

    Origin of Solar System & 12.3 Asteroids and

    Origin of Solar System & 12.3 Asteroids and Comets. START. EXIT. Funded by Title V HIS Grant at LAMC and U.S Department of Education. Corresponds to Ch 12
  • PowerPoint to accompany Introduction to MATLAB 7 for

    PowerPoint to accompany Introduction to MATLAB 7 for

    PowerPoint to accompany Introduction to MATLAB 7 for Engineers William J. Palm III Chapter 10 Symbolic Processing with MATLAB Copyright © 2005. The McGraw-Hill ...