Intelligent Systems Lecture Notes

18 November 2011 • Learning Belief Networks

---

Outline

• Learning belief networks.
• Sparse examples and belief.
• Unobserved variables.
• Missing data.
• Missing networks.
• Causality and general learning.

Belief Networks

• A belief network is
  • A set of random variables (features).
  • A total ordering of the variables indicating dependence, such that X_i may depend only on X_j if j < i.
  • A directed acyclic graph (DAG) indicating the dependence relations among the variables.
  • The consequent probability assignments.

Learning Belief Networks

• Given
  • the DAG,
  • an example set covering all variables, and
  • complete data for each example, then
• you can learn each conditional probability separately.
  • Using the probability definitions and the frequency interpretation.

Example

Network		Examples		Probabilities
	+	A B C D G t f t t f f t t t t t t f t f \(\vdots\)	=	Pr(A) Pr(B) Pr(G | A) Pr(C | G) Pr(D | G)

Probability Learning

• Each probability is learned with

  

• Each conditional probability is learned with:

  

• where c \(\leq\) c₁ reflect prior (expert) knowledge.

Sparse Examples

• Incomplete example sets may not have values for some random variables.
  • Those variables occur with probability zero (are impossible).
• Incomplete example sets may not have enough values for some random variables.
  • The resulting probabilities may not match the true (a priori) probabilities.
• The solution in either case is to put a thumb on the scales.

Sparse Belief

• Suppose
  • X_i is never observed as true (case 0).
  • X_i is observed true exactly once (case 1).
• How much more should X_i be believed for case 1 than for case 0?
  • For example, never, 10% more, twice as much.
• Prior or domain knowledge answers this question.

Pseudocounts

• The pseudocount (or prior count) c answers the question:

  Believe X_i for case 1 over case 0 in the ratio c + 1 : c (case 1 : case 0).

• For example:

  never		c = 0		1 : 0
  10%		c = 10		11 : 10
  twice as much		c = 1		2 : 1

Other Problems

• If
  • a node has many parents and
  • there is little or no data for the nodes,
• then calculating probabilities is inaccurate overkill.
• Use supervised learning (decision tree, neural network, \(\ldots\)) to represent the conditional probabilities.
  • A conditional probability doesn’t need to be represented as a table.

Unobserved Variables

A B C t f t f t t t t f \(\vdots\)

Pr(A) Pr(D | A) Pr(B | D) Pr(C | D)

• What if we had only observed values for A, B, and C?
  • D is a latent variable.

Soft Clustering

• Latent variables are essentially categories, turning this into a soft-clustering problem.

  A B C D count t f t t 0.7 t f t t 0.3 t f t f 0.9 f t t t 0.9 \(\vdots\) \(\vdots\)

  Pr(A) Pr(D | A) Pr(B | D) Pr(C | D)

• This brings in the EM algorithm.

EM Algorithm

• Repeat until stable:
  • E-Step: give the expected number of data points for the unobserved variables based on the given probability distribution.
  • M-Step: infer the maximum likelihood probabilities from the data.
• Start either with made-up data or make-up probabilities.
• EM converges to a local minimum.

Missing Data

A B C D G t f t t ? f t ? ? t t t ? t f \(\vdots\)

Pr(A) Pr(B) Pr(G | A) Pr(C | G) Pr(D | G)

• Data missing at random can be ignored.
  • But random absence is a strong requirement.

Correlated Absence

• Correlated absence mostly stop learning.
  • Sick patients dying make results look better.
  • Cured patients leaving make results look worse.
• Add extra random variables to represent the correlated absence.

Missing Network

• Suppose the belief network is unknown.

  ?

  A B C D G t f t t f f t t t t t t f t f \(\vdots\)

  ?

  • The data are complete, no variables are latent.
• What can be learned in this case?

Brute-Force Search

• There’s always brute force:
  • Totally order the variables.
  • Generate candidate parent() functions.
  • Learn on the generated DAG.
  • Compare the independence implied by the probabilities to the independence implied by the example set.
  • Repeat until satisfied.
• This is expensive and difficult.

Network Learning

• A model is a belief network.
• A bigger network fits the data better.
• Pr(model) encodes a preference for smaller networks (e.g., using the description length).
• You can search over networks, looking for the most likely model.

Network Learning.

• Search over feature total orderings.
• Use supervised learning on \(I\)₁, …, \(I\)_n to learn Pr(\(I\)_j | \(I\)₁).
• Return the network model found with minimum

  log Pr(examples | network) + log Pr(network)

  • log Pr(network) decomposes into the sum of the representations for each variable.

Network Learning..

• Test totally ordered features for independence.
• The XOR problem: individually uninformative features may be informative in combination.
• Search over variable total orderings.

Causality

• A causal model predicts intervention effects.
• A causal model obeys belief-network independence.
• Not all belief networks are causal.
• Conjecture: causal belief networks are more natural and concise than non-causal networks.
• Learning models from observational data requires modeling assumptions.
• Causal models can be learned from randomized experimentation.

General Learning

• A mix of observational data and data from random studies.
• The belief network is unknown.
• There may or may not be latent variables.
• There is missing data.
• This is too difficult for current techniques; punt.

Summary

References

• Learning Decision Trees (Section 16.3) in Intelligent Systems by Robert Schalkoff, Jones and Bartlett, 2011.
• Leaning with Hidden Variables: The EM Algorithm (Section 20.3) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.

---

This page last modified on 2011 November 16.