Chow-Liu trees

(55 minutes to learn)

Summary

While the problem of learning Bayes net structures is intractable in general, there is a polynomial time algorithm for learning the optimal tree-structured graph under various scoring criteria. In particular, it can be formulated as a maximum weight spanning tree problem. The maximum likelihood trees are known as Chow-Liu trees, after their original inventors.

Context

This concept has the prerequisites:

Goals

  • Be able to formulate the problem of learning tree-structured graphical models as a maximum spanning tree problem.
    • What assumptions does this require on the scoring function?
  • The algorithm only applies to trees (where a node has at most one parent) rather than polytrees (where a node can have multiple parents). Why does it fail for polytrees?
  • Why is the maximum likelihood score an acceptable scoring criterion for tree-based networks, unlike for general Bayes nets?
  • Show that the problem can be equivalently viewed as learning the structure of a tree-structured MRF.

Core resources (read/watch one of the following)

-Free-

Coursera: Probabilistic Graphical Models (2013)
An online course on probabilistic graphical models.
Author: Daphne Koller
Other notes:
  • Click on "Preview" to see the videos.

-Paid-

Supplemental resources (the following are optional, but you may find them useful)

-Paid-

See also

-No Additional Notes-