Description

Sheet No.1
Bernt Schiele
Hand in: by 11:59pm by email to Apratim Bhattacharyya (abhattac at mpiinf mpg de). Begin the subject of your e-mails with [PGM Exercise1]. Both scanned copies or typed (e.g. LATEX ) are allowed. You should specify your first and last name as well matriculation number on submission.
1 Probabilities
Points: 8
In this excercise, you will prove some basic, but very important rules in probability theory.
1. For any two events E1 and E2, prove
p(E1 ∪ E2) = p(E1) + p(E2) − p(E1 ∩ E2) (1)
what if E1 and E2 are two disjoint events?
2. (Bayes’ law) Given the Kolmogorov definition for conditional probabilities
(2)
derive Bayes’ law:
(3)
3. (Law of total probability) Let E1, …, En be mutually disjoint events in the probability space Ω such that Ω = . Then for any event B in the same space Ω show that
) (4)
4. (Linearity of expectation) For any finite collection of discrete random variables X1,…,Xn with finite expectations, show that
n n
E[XXi] = XE[Xi] (5)
i=1 i=1
5. Let X, Y , Z be three disjoint subsets of random variables. We say X and Y are conditionally independent given Z if and only if
pX,Y |Z(x,y | z) = pX|Z(x | z)pY |Z(y | z) (6)
Show that X and Y are conditionally independent given Z if and only if the joint distribution for the three subsets of random variables factors in the following form:
pX,Y,Z(x,y,z) = h(x,z)g(y,z) (7)
(Be careful to prove both directions!)
2 Complexity analysis
Points: 6
Consider the three random variables X,Y,Z all of which are binary.
• How many states do you need in general to fully specify the joint distribution p(x,y,z)?
• How many states are needed if the distribution does factorize in p(x,y,z) = p(x | y)p(y | z)p(z)?
• How many states do you need, if the variables are not binary but can take values in {1,2,…,N}; consider both previous cases.
• How many states do you need to specify a distribution over all 8bit grayscale images of size 1000 × 1000 pixels? There are random variables x1,x2,…,x1M with xi ∈ {0,…,255} for i = 1,…M.
• Do you have an idea of how to represent the distribution more compactly?
Provide the number of states needed by your method.
3 Chest Clinic Network

The chest clinic network above concerns the diagnosis of lung disease (tuberculosis,lung cancer, or both, or neiter). In this model a visit to asia is assumed to increase the probability of lung cancer. We have the following binary variables.
xpositive X-ray dDyspnea (shortness of breath) eEither Tuberculosis or Lung Cancer tTuberculosis lLung cancer bBronchitis aVisited Asia sSmoker
1. (Points: 1) Write down the factorization of the distribution implied by the graph.
2. (Points: 4) Are the following independence statements implied by the graph? (And how do you conclude this?)
(a) tuberculosis⊥⊥smoking|shortness of breath
(b) tuberculosis⊥⊥smoking|bronchitis
(c) lung cancer⊥⊥bronchitis|smoking
(d) visit to Asia⊥⊥smoking|lung cancer
(e) visit to Asia⊥⊥smoking|lung cancer,shortness of breath
3. (Bonus Points: 3) Calculate by hand the values for p(d). The Conditional Probability Table (CPT) is:
p(a = 1) = 0.01, p(s = 1) = 0.5
p(t = 1 | a = 1) = 0.05, p(t = 1 | a = 0) = 0.01
p(l = 1 | s = 1) = 0.1, p(l = 1 | s = 0) = 0.01
p(b = 1 | s = 1) = 0.6, p(b = 1 | s = 0) = 0.3
p(x = 1 | e = 1) = 0.98, p(x = 1 | e = 0) = 0.05
p(d = 1 | e = 1,b = 1) = 0.9, p(d = 1 | e = 1,b = 0) = 0.7
p(d = 1 | e = 0,b = 1) = 0.8, p(d = 1 | e = 0,b = 0) = 0.1
and
= 0,
.