Exact Inference - 07

Question 1

What is marginal inference?

Answer 1

We ask the question ‘What is the probability of a given variable in our model (possibly conditioned on evidence)?’.

Question 2

What is maximum a posteriori (MAP) inference?

Answer 2

We ask the question ‘What is the most likely assignment to the variables in the model (possibly conditioned on evidence)?’

Question 3

Inference is not challenging. True or False?

Answer 3

False

Question 4

Chains and trees are ______________. Loopy graphs are not.

Answer 4

tractable

Question 5

If a problem is intractable, we are still able to obtain useful answers via _______________ inference methods.

Answer 5

approximate

Question 6

Which are the methods for inference in graphical models?

Answer 6

1. Variable elimination
2. Belief propagation (aka message passing algorithms)
3. Approximate inference methods (aka Monte Carlo techniques)
4. Variational inference

Question 7

What is dynamic programming?

Answer 7

Dynamic programming ”inverts” the order of computation, performing it inside out instead of outside in.

Question 8

What are the 2 ideas that help us address the exponential blowup of the joint distribution in the variable elimination method?

Answer 8

1. Because of the structure of the Bayesian network, some subexpressions in the joint depend only on a small number of variables.
2. By computing these expressions once and caching the results, we can avoid generating them exponentially many times.

Question 9

Why does the order of elimination matter?

Answer 9

!= elimination orders –> != intermediate factor sizes –> != complexity

Question 10

What is the naïve approach in the variable elimination method?

Answer 10

First, evaluate the joint distribution and then perform the summation explicitly.

Question 11

Define tree in an undirected graph.

Answer 11

In an undirected graph, a tree is defined as a graph in which there is one path between any pair of nodes.

Question 12

Trees have loops. True or False?

Answer 12

False

Question 13

Define tree in a directed graph.

Answer 13

In directed graphs, a tree is defined such that there is a single node, called the root, which has no parents, and all other nodes have one parent.

Question 14

If there are nodes in a directed graph that have more than one parent, but there is still one path between any two nodes, then the graph is called a _____________.

Such a graph will have more than one node with the property of having ____ ___________, and the corresponding moralized undirected graph will have __________.

Answer 14

polytree; no parents; loops

Question 15

______________ algorithm is used for marginal inference.

_______________ algorithm is used for MAP inference.

Answer 15

Sum-product; Max-product

Question 16

Marginal is proportional to the product of the incoming messages. True or False?

Answer 16

True

Question 17

In the sum-product algorithm, if the factor graph is derived from a directed graph, then the joint distribution is already correctly ________________, and so the marginals obtained will be normalized correctly.

If the factor graph is derived from an undirected graph, then we have the _______________ _________ Z and in this case we just need to marginalize over a single ____________ rather than the entire set of variables.

Answer 17

normalized; normalization factor; variable

Question 18

We can use the messages to compute the marginals of all variables in the graph. True or False?

Answer 18

True

Question 19

If each edge has a message in both directions, we can compute the marginals of all variables in the graph. True or False?

Answer 19

True

Question 20

The correspondence between messages and effective __________ allows us to find the joint distribution for variables connected to the same factor node (_____________).

Answer 20

factors; neighbors

Question 21

From a leaf variable node to a factor node, the message is _____.

Answer 21

1

Question 22

From a leaf factor node to a variable node, the message is the _____.

Answer 22

factor

Question 23

In the sum-product algorithm, the factor graph must be a _______.

Answer 23

tree

Question 24

The sum-product algorithm can be used to compute _______________.

This can be viewed as defining a new __________ ________ on the non-evidential variables.

Or, one can keep the original factor graph, but for factor-to-variable messages, the sum is only taken over _______________ variables; any evidential variables in the potential are set to their evidential states.

Answer 24

conditionals; factor graph; non-evidential

Question 25

The sum-product algorithm may be used for ______________ random variables. All stays the same, but we replace sums with ___________. In special cases, integral can be computed in closed form (e.g., Gaussian family). If not, need for ________________. ________________ are also needed for discrete random variables when K is _________.

Answer 25

continuous; integrals; approximations; approximations; large

Question 26

What do we need to do if our factor graph is not a tree?

Answer 26

If factor graph is NOT a tree: - Group variables together so that the factor becomes a tree (called junction tree or clique tree) - Pretend the factor graph is a tree and use message passing (loopy belief propagation)

Question 27

What is the max-sum algorithm?

Answer 27

The max-sum algorithm is the message passing algorithm by replacing sum with max, products with sums, and factors with log-factors.

Question 28

In the max-sum algorithm, from a leaf variable node to a factor node, the message is ____.

Answer 28

0

Question 29

In the max-sum algorithm, from a leaf factor node to a variable node, the message is the ________________ of the _________.

Answer 29

logarithm; factor

Question 30

The message passing framework can be generalized to arbitrary graph topologies, giving an exact inference procedure known as the _____________ ________ algorithm. If the starting point is a directed graph, it is first converted to an undirected graph by ______________, whereas if starting from an undirected graph, this step is not required. Next, the graph is ________________, which involves finding chordless cycles containing four or more nodes and adding extra links to eliminate such chordless cycles. Next, the triangulated graph is used to construct a new tree-structured undirected graph called a join tree (or clique tree), whose nodes correspond to the maximal _________ of the triangulated graph, and whose links connect pairs of cliques that have variables in common.

Answer 30

junction tree; moralization; triangulated; cliques

Question 31

Understanding approximate inference gives a deeper context for why and how exact inference was needed. True or False?

Answer 31

False. It's the opposite.

Question 32

Distinguish variable elimination and belief propragation.

Answer 32

Variable Elimination: Bayesian/Markov network; Expensive for many queries; Exact for all DAGs; Difficult parallelism Belief Propagation: Factor graph; Reuses computation via message; Exact only for trees, approximate for loopy graphs; Naturally parallelizable

Question 33

A variable is conditionally independent of everything else given its Markov blanket. For a factor graph, the Markov blanket of a variable x is all ________ nodes adjacent to x , and all ___________ nodes adjacent to those _________.

Answer 33

factor; variable; factors