Inference in a chain_Assignment 3

. Assignment3 
3.1 Inferenceinachain
XT-2 XTX 2 X3X 1 XT-1 • • •
Consider thebelief network shown above withrandom variables Xt2{1,2,...,m}. Suppose thatthe CPT ateachnon-rootnodeisgivenbythesame m⇥m matrix;thatis,forall t1,wehave: Aij = P(Xt+1=j|Xt=i). (a) Provethat P(Xt+1=j|X1=i)=[At]ij,where At isthe tth powerofthematrix A. Hint: useinduction. (b) Considerthecomputationalcomplexityofthisinference. Deviseasimplealgorithm,basedonmatrixvectormultiplication,thatscalesas O(m2t). (c) Showalternativelythattheinferencecanalsobedonein O(m3 log2 t). (d) SupposethatthetransitionmatrixAij issparse,withatmosts⌧mnon-zeroelementsperrow. Show thatinthiscasetheinferencecanbedonein O(smt). (e) Showhowtocomputetheposteriorprobability P(X1=i|XT+1=j) intermsofthematrix A andthe priorprobability P(X1=i). Hint: useBayesruleandyouranswerfrompart(a).
3.2 Moreinferenceinachain
Y1
X0 X1
Considerthesimplebeliefnetworkshowntotheright,withnodes X0, X1,and Y1. Tocomputetheposteriorprobability P(X1|Y1),wecanuseBayesrule: P(X1|Y1)= P(Y1|X1)P(X1) P(Y1) (a) Show how to compute the conditional probability P(Y1|X1) that appears in the numerator of Bayes rulefromtheCPTsofthebeliefnetwork. (b) Show how to compute the marginal probability P(Y1) that appears in the denominator of Bayes rule fromtheCPTsofthebeliefnetwork.
Next you will show how to generalize these simple computations when the basic structure of this DAG is repeatedtoformanextendedchain. Likethepreviousproblem,thisisanotherinstanceofefficientinference inpolytrees.
1
Y1
X0 X1
Y2
X2 Xn-1
Yn
Xn
. . .
. . .
Yn-1
Consider how to efficiently compute the posterior probability P(Xn|Y1,Y2,...,Yn) in the above belief network. OneapproachistoderivearecursionfromtheconditionalizedformofBayesrule
P(Xn|Y1,Y2,...,Yn)=
P(Yn|Xn,Y1,Y2,...,Yn1)P(Xn|Y1,Y2,...,Yn1) P(Yn|Y1,...,Yn1) where the nodes Y1,Y2,...,Yn1 are treated as background evidence. In this problem you will express the conditionalprobabilitiesontherighthandsideofthisequationintermsoftheCPTsofthenetworkandthe probabilitiesP(Xn1=x|Y1,Y2,...,Yn1),whichyoumayassumehavebeencomputedatapreviousstep oftherecursion. Youranswersto(a)and(b)shouldbehelpfulhere.
(c) Simplifytheterm P(Xn|Y1,Y2,...,Yn1) thatappearsinthenumeratorofBayesrule. (d) Show how to compute the conditional probability P(Yn|Xn,Y1,Y2,...,Yn1) that appears in the numerator of Bayes rule. Express your answer in terms of the CPTs of the belief network and the probabilities P(Xn1=x|Y1,Y2,...,Yn1),whichyoumayassumehavealreadybeencomputed. (e) Show how to compute the conditional probability P(Yn|Y1,Y2,...,Yn1) that appears in the denominator of Bayes rule. Express your answer in terms of the CPTs of the belief network and the probabilities P(Xn1=x|Y1,Y2,...,Yn1),whichyoumayassumehavealreadybeencomputed.
3.3 Nodeclusteringandpolytrees
In the figure below, circle the DAGs that are polytrees. In the other DAGs, shade two nodes that could be clusteredsothattheresultingDAGisapolytree.
2
3.4 Cutsetsandpolytrees
Clearlynotallproblemsofinferenceareintractableinloopybeliefnetworks. Asatrivialexample,consider thequery P(Q|E1,E2) inthenetworkshownbelow:
Q
E2
E1
Inthiscase,because E1 and E2 aretheparentsof Q,thequery P(Q|E1,E2) canbeanswereddirectlyfrom theconditionalprobabilitytableatnode Q.
As a less trivial example, consider how to compute the posterior probability P(Q|E1,E2) in the belief networkshownbelow:
E2
Q
E1
In this belief network, the posterior probability P(Q|E1,E2) can be correctly computed by running the polytreealgorithmonthesubgraphofnodesthatareenclosedbythedottedrectangle:
E2
Q
E1
Inthisexample,theevidencenodesd-separatethequerynodefromtheloopypartsofthenetwork. Thusfor thisinferencethepolytreealgorithmwouldterminatebeforeencounteringanyloops.
(continued)
3
For each of the five loopy belief networks shown below, consider how to compute the posterior probability P(Q|E1,E2). If the inference can be performed by running the polytree algorithm on a subgraph, enclose this subgraph byadottedlineasshownonthepreviouspage. (Thesubgraphshouldbeapolytree.) On the other hand, if the inference cannot be performed in this way, shade one node in the belief network thatcanbeinstantiatedtoinduceapolytreebythemethodofcutsetconditioning.
E2
Q
E1
E2
Q
E1
E2QE 1
E2E 1 Q
E2QE 1
4
3.5 Nodeclustering
Considerthebeliefnetworkshownbelowoverbinaryvariables X, Y1, Y2, Y3, Z1,and Z2. Thenetworkcan be transformed into a polytree by clustering the nodes Y1, Y2, and Y3 into a single node Y. From the CPTs intheoriginalbeliefnetwork,fillinthemissingelementsoftheCPTsforthepolytree.
X P(Y1 =1 |X) P(Y2 =1 |X) P(Y3 =1 |X)0 0.75 0.50 0.25 1 0.50 0.25 0.75
Y1 Y2 Y3 P(Z1 =1 |Y1,Y2,Y3) P(Z2 =1 |Y1,Y2,Y3)0 0 0 0.9 0.1 1 0 0 0.8 0.2 0 1 0 0.7 0.3 0 0 1 0.6 0.4 1 1 0 0.5 0.5 1 0 1 0.4 0.6 0 1 1 0.3 0.7 1 1 1 0.2 0.8
Y1 Y2 Y3 Y P(Y|X=0) P(Y|X=1) P(Z1=1|Y ) P(Z2=1|Y ) 0 0 0 1 1 0 0 2 0 1 0 3 0 0 1 4 1 1 0 5 1 0 1 6 0 1 1 7 1 1 1 8
X
Y1 Y2 Y3
Z1 Z2
X
Y
Z1 Z2
5
3.6 Likelihoodweighting Considerthebeliefnetworkshownbelow,withnbinaryrandomvariablesBi2{0,1}andanintegerrandom variable Z. Let f(B)=Pn i=1 2i1Bi denote the nonnegative integer whose binary representation is given by BnBn1 ...B2B1. Supposethateachbithaspriorprobability P(Bi=1) = 1 2,andthat P(Z|B1,B2,...,Bn)=✓1↵ 1+↵◆↵|Zf(B)| where 0 < ↵ < 1 is a parameter measuring the amount of noise in the conversion from binary to decimal. (Largervaluesof ↵ indicategreaterlevelsofnoise.)
bits Bi
integer Z
...
(a) Show that the conditional distribution for binary to decimal conversion is normalized; namely, that Pz P(Z=z|B1,B2,...,Bn)=1,wherethesumisoverallintegers z 2[1,+1]. (b) Consider a network with n=10 bits and noise level ↵=0.1. Use the method of likelihood weighting toestimatetheprobability P(Bi=1|Z=128) for i2{2,5,8,10}. (c) Plot your estimates in part (b) as a function of the number of samples. You should be confident from theplotsthatyourestimateshaveconvergedtoagooddegreeofprecision(say,atleasttwosignificant digits). (d) Submit a hard-copy printout of your source code. You may program in the language of your choice, andyoumayuseanyprogramatyourdisposaltoplottheresults.
6
3.7 Evenmoreinference
Showhowtoperformthedesiredinferenceineachofthebeliefnetworksshownbelow. Justifybrieflyeach stepinyourcalculations.
(a) Markovblanket Showhowtocomputetheposteriorprobability P(B|A,C,D) intermsoftheCPTsofthisbeliefnetwork—namely, P(A), P(B|A), P(C),and P(D|B,C).
A B D
C
(b) Conditionalindependence Thisbeliefnetworkhasconditionalprobabilitytables for P(F|A) and P(E|C) inadditiontothoseofthe previousproblem. Assumingthatallthesetablesare given,showhowtocomputetheposteriorprobability P(B|A,C,D,E,F) intermsoftheseadditionalCPTsand youranswertopart(a).
A B D
C E
F
(c) Moreconditionalindependence Assumingthatalltheconditionalprobabilitytablesin thisbeliefnetworkaregiven,showhowtocompute theposteriorprobability P(B,E,F|A,C,D). Express youranswerintermsoftheCPTsofthenetwork,as wellasyourearlieranswersforparts(a)and(b).
A B D
C E
F
7
3.8 Morelikelihoodweighting (a) Singlenodeofevidence
QX
ZY
E
Suppose that T samples {qt,x t,y t,z t}T t=1 are drawn from the CPTs of the belief network shown above (with fixed evidence E = e). Show how to estimate P(Q=q|E=e) from these samples using the method of likelihood weighting. Express your answer in terms of sums over indicator functions, suchas: I(q,q0)=( 1 if q = q0 0 otherwise In addition, all probabilities in your answer should be expressed in terms of CPTs of the belief network(i.e.,probabilitiesthatdonotrequireanyadditionalcomputation).
(b) Multiplenodesofevidence SupposethatT samples{q1t,q2t,x t,y t,z t}T t=1 aredrawnfromtheCPTsofthenetworkshownbelow (with fixed evidence E1=e1 and E2=e2). Show how to estimate P(Q1=q1,Q2=q2|E1=e1,E2= e2) from these samples using the method of likelihood weighting. Express your answer in terms of indicatorfunctionsandCPTsofthebeliefnetwork.
XQ 1
ZE 1
E2
Y
Q2