Graphical models

Question 1

Describe the “Probabilistic Pipeline”

Answer 1

Build model -> Discovere patterns -> Predict and Explore -> Critisise Model -> Build model

Question 2

What is probabilistic inference?

Answer 2

Given latent variables and observed variables, propabilistic inference is learning about the unknown latent variables trough the posterior distrubution

Question 3

What can we do if the marginal likelihood is intractable?

Answer 3

We can approximate using e.g. sampling and markov chain monte carlo.

Question 4

What kind of graphs are used for:

1. Bayesiean networks
2. Markov random fields
3. Factor graphs

Answer 4

1. Directed
2. Undirected
3. Bipartite

Question 5

Why do we use graphical models?

Answer 5

1. Simple way to vizualise
2. Gives insights into properties of the model
3. Can be used to design/ motivate new models
4. Can be used to express complex computations

Question 6

What type of nodes do we have in Bayesian networks?

Answer 6

Shaded nodes: Observed random variables

Unshaded nodes: Latent random variables

Question 7

What kind of depenedens do we have in a Bayesian network if and arrow is drawn from node a to b

Answer 7

p(b|a)

Question 8

For Bayesian graphs, split into three sets, A,B,C, when can we say that A is conditional independent of B given C?

Answer 8

If all paths from A to B are blocked. A path is blocked if:

1 The arrows meet tail to tail or head to tail at a node and the node is in C
2. The arrows meet head to head at a node and neither the node nore it’s decendands are in C

Question 9

In a Markov Random field, how can we se if two variables are conditional independent given the rest of the variables?

Answer 9

They arn’t connected directly in the graph

Question 10

What is a clique in Markov random fields?

Answer 10

A fully connected subgraph

Question 11

What is the formula for factorizing the joint distrubution in Markov Random fields?

Answer 11

p(x) = (1/Z) prod_C phi_C(x_C)

Z is the normalizing constant
C are the maximum liques
phi is the clique potential

Question 12

What is the formula for the normalizing constant Z in markov random fields, and what is the complexity of calculating it?

Answer 12

sum_x prod_C phi_C(x_C) = Z

If the model has M nodes and each node has K states the complexity is M^K

Question 13

When do the clique potentials have a probabilistic interpretation?

Answer 13

If we convert a directed grap to a MRF.

Question 14

What is the problem factorizing using MRF for continues models?

Answer 14

We have to solve an integral for the normalizing constant Z, which is often intractable

Question 15

How can we see which variables are conditional independent in MRF?

Answer 15

For sets A, B, C, A and B are conditional independent if all paths from A to B go trough C.

Question 16

How is the clique potential related to energy functions?

Answer 16

phi_C(x_C) = exp(-E(x_c)) for some energy function E.

Question 17

What is the total energy regarding clique potentials?

Answer 17

total_energy = -log(p(x)) = sum -log (phi_C(x_C))

Question 18

Describe the MRF energy minimization model for image denoising

Answer 18

Let y_i be the observed variables and y_i be the latent variables.

E(yi, xi) = - axiyi
E(xi, xj) = -bxixj for neighbour pixels
E(xi) = cxi Bias term
E(x) = -asum(xiyi) - bsum(xixj) + csum(x_i)

Initialize xi to yi, calculate energy set xi to {-1, +1} minimizing the energy

Question 19

What does a link between a variable node and a factor node indicate in a factor graph?

Answer 19

That the factor depends on the variable

Question 20

How do we convert a Directed graph to a MRF?

Answer 20

1. Add undirected links between all pairs of parents for all nodes and consider the rest of the links undirected
2. Identify maximum cliques
3. Initialize clique potential to 1
4. Multiply each conditional distribution factor in the directed graph into one of the clique potentials

Question 21

Can a directed graph have ore than one representation as a factor graph?

Answer 21

Yes

Question 22

How can we create a factor graph from a MRF

Answer 22

Add a factor node for each clique

Question 23

What is one advantage of factor graphs over MRF graphs?

Answer 23

Can remove cycles

Question 24

What is the goal of the message passing algorithm?

Answer 24

Finding the (marginal) posterior distrubution

Question 25

How do we pass messages from variable to factor nodes?

Answer 25

Send the product of all incoming messages

Question 26

How do we send a message from factor nodes to variable nodes

Answer 26

marginalize out all incoming variables from

f(x1, x2, …, xM) prod incoming messages

Question 27

How do we initialize leaf nodes in factor graphs?

Answer 27

If the node is a variable, initialize to 1, if it is a factor initialize to f(x)

Question 28

How can we use observed results in the message passing algorithm to say something about the posterior?

Answer 28

If v_hat are the observerd variables, h are the unobserved variables and x are all variables, we have:

p(x)p(v=v_hat) = p(h,v=v_hat) prop. to p(h|v=v_hat)

Question 29

Name some applications of inferenec in graphical models

Answer 29

Ranking, Computer Vision, Coding Theory, Linear Algebra, Signal Processing

Question 30

If xi, xj are conditionally independent given everything else in a MRF (They don’t have a link) can they appear in a common factor in the factorization?

Answer 30

No