Lecture 2: Bayesian Networks and Prediction

How are BNs related to prediction systems?

Bayesian networks are not designed for doing prediction, although they can be used for prediction. If prediction is your main goal, BN is not likely your best choice.

We will have a look at two prediction methods(?):

  • Optimal Bayes approach
  • Naive Bayes

It's also a model of data is supposed to be generated.

We use two default examples:

  1. Keeping Our Lawn Wet
  2. Diagnosing Lung Cancer

Review lecture notes for these examples.

Poll: what method would you use right now to take these prediction/classification problems?

Winners:

  • Logistic Regression (popular in statistics due to interpretability)
  • Random Forest (popular in data science)

Optimal Bayes

If we pick the "best" (read as: most likely) hypothesis, we have:

$$argmax_{h \in H} P(h|e)$$

Which gives with Bayes' rule

$$argmax_{h \in H} \frac{P(e|h)P(h)}{P(e)}$$

We do not care about P(e) because it's a constant:

$$argmax_{h \in H} P(e|h)P(h)$$

So our classification task is a matter of finding the argmax of the join probability:

$$argmax_{h \in H} P(e,h)$$

For the lung cancer example, we need 2^7*3-1 parameters.

For logistic regression we need... 8 parameters.

In Optimal Bayes we represent a probability as a table of numbers where everything is linked to everything else.

This is a huge "blanket" assumption.

So even though this MAP solution is optimal, it is also infeasible in practice.

Naive Bayes

Factors become independent when conditioned upon the hypotheses. This allows us to store more but smaller tables instead of the one huge table where everything is connected with everything. This is because we can factorize the formula.

Now for three evidence variables and one hypothesis, we only need to explicitly store 7 parameters. With optimal Bayes here we would need 16-1=15, so we've halved the complexity.

The obvious downside is that we make very simplifying assumptions, so we deviate from the true distribution.

For the lung cancer example, we would need to store 17 values.

Numbers required for variables with parents:

(p)x(m-1) with:

  • p: number of possible combinations of "parent" variables
  • m: number of values of the child variable

If no parents, just m-1.

Do this for all nodes and sum up.

With naive Bayes, this scales linearly rather than exponentially.

In practice we use a logarithm for naive Bayes to avoid numerical underflow. Logarithm is monotone so the outcome of the argmax does not differ.

The probabilities $P(e_i|h)$ can be estimated with counting.

  • Log regression: discriminative classifier.
  • Naive Bayes: generative classifier.

Naive Bayes is only expected to perform better for small datasets. So it may be a good baseline if you have a dataset that is too smal for logistic regression.

Graphs, DAGs, networks

Where to Bayesian networks come in?

One weird convention in BNs is that in DAGs each node is a trivial ancestor and descendant of itself. Strictly speaking, this doesn't fit the definition of the DAG, but we repair this by stating that a cycle requires "arrows" in the graph.

$P(x1,..,xn)=\prod_i{x_i|pa_G{x_i}}$ with $pa_G$ being the parents.

This does not hold in general; this formula factorizes according to a specific graph.

With Bayesian Network, we have more control

We can also compute each variable from the values of others. So we have more flexibility in what is the hypothesis. This is a difference w.r.t. the other methods where the structure is fixed and "asymmetric".

Bayesian Inference

Once we have the complex representation of a BN, computing a marginal probability for cancer is a more complex problem. Before, it was a matter of adding everything in the huge table where we have cancer=1. Now, we have the smaller tables with more "local" information. Now, we need to use the network structure to smartly sum out variables. That is why this problem is called Bayesian inference.

For C, we care only about the ancestors (remember: includes C itself!) for this step.

But whether this is efficient enough depends heavily on the structure of the network and what we query. If we query a "bottom" note, the ancestral network is just the whole network.