Week 3

Question 1

Key assumption of Naive bayes

Answer 1

Each effect only depends on cause

<=> effects don’t affect each other

Question 2

Why is conditional independence assumed for naive bayes

Answer 2

Preserve linearity in number of effects for P table

If we don’t do this, P table grows exponentially as new effects are introduced

Question 3

A bayesian network cant

Answer 3

Have any cycles

Question 4

Graph of Bayesian Network is

Answer 4

Directed Acyclic Graph (DAG)

Question 5

P of a selection of states of given variables
On a Bayesian network

Answer 5

Question 6

Local semantics of a node in a Bayesian network

Answer 6

A node X is independent of its non-descendants given its parents

Question 7

Markov Blanket

Answer 7

A node X is conditionally independent of all others given its Markov Blanket (parents, children, children’s parents)

Question 8

How to compress Markov blankets further

Answer 8

Boolean functions (eg NorthAmerican <=> Canadian v US v Mexican) (prior knowledge)

Numerical relationships eg(image)

Question 9

Simple queries

Answer 9

Question 10

Conjunctive Queries

Answer 10

Question 11

Sensitivity Analysis

Answer 11

Which P values are most critical

Question 12

4 ways to compute posterior marginal

Answer 12

Enumeration

Rejection sampling

Likelihood weighting

Gibbs Sampling

Question 13

Inference by enumeration: pro and con

Answer 13

Pro: deterministic

Con: inefficient

Question 14

Variable elimination for enumeration

Answer 14

Evaluate enumeration tree bottom up

Question 15

Time and space cost of variable elimination

Answer 15

Question 16

Exact inference is

Answer 16

P complete

NP - Hard

Question 17

NP Hard

Answer 17

Nondeterministic polynomial time hard

At least as hard as the hardest problems in NP. (The class of NP hard problems)

Question 18

What is “# P”

Answer 18

P is the class of difficulty in counting the solutions

Related to NP

NP Hard is a class of times to find solutions

Question 19

LLN

Answer 19

Question 20

Why Rejection sampling over prior sampling

Answer 20

Prior sampling has no notion of conditioning

Question 21

How does rejection sampling work

Answer 21

We do prior sampling and then reject those for which e doesn’t hold

Question 22

Likelihood weighting

Answer 22

Question 23

Summarise Gibbs sampling

Answer 23

Algorithm wanders randomly around state space… flipping one var at a time but keeping evidence variables fixed

Question 24

Steps for Gibbs sampling

Answer 24

Begin with a query with evidence vars fixed to obs vals

Randomly initialise non-evidence vars

With entire state now set sample first non-evidence var, if this causes it to change value , update state and save

Then move to next non-evidence var

Repeat until sample size reached

Question 25

Gibbs sampling pseudo code

Answer 25

Question 26

Chain rule

Answer 26

Question 27

Locally structured system

Answer 27

Each sub component interacts directly with only a bounded number of components

Question 28

Leak node

Answer 28

If causes for an effect may not be included, leak node can generally represent ‘miscellaneous causes’

Question 29

Nonparametric representation

Answer 29

(For continuous vars) Define conditional distribution implicitly with a collection of instances, each containing specific values (or ranges of) for all vars

Question 30

Hybrid Bayesian network

Answer 30

Network with both discrete and continuous RVs

Question 31

Difference between Probit and logit

Answer 31

Link function!
For Probit is CDF of standard N dist
For Logit is logistic function:

Question 32

Total set of variables in Bayesian Network and what are they

Answer 32

X is query variable
E is evidence variables
Y is hidden variables

Question 33

Enumeration algorithm pseudocode

Answer 33

Question 34

Calculating α for posterior marginal ?

Answer 34

When you have a final vector, just find ratio of 2 to get probabilities of each

Question 35

How to interpret CPT with random numbers

Answer 35

Eg 0.1 for A = True

Any random number less than 0.1 is True as this gives 10% chance of True

Question 36

How to do prior sampling

Answer 36

With random number generator
Starting from top, moving from left to right on each row
If random number < P then True

Question 37

How to rejection sampling

Answer 37

Same as prior sampling BUT
If conditions are not as in query, discard sample. Eg;
P( a | b, c) if sample has not b and/or not c, reject

Question 38

How to do likelihood sampling

Answer 38

For P(T|h, s)

h and s are fixed evidence variable.
Therefore when going through sampling multiply weight by the probability that we are fixing

At end, each sample has values and a weight associated to the sample