Chow-Liu trees

(55 minutes to learn)


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.


This concept has the prerequisites:


  • 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)


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


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


See also

-No Additional Notes-