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:
- Bayes net structure learning (Chow-Liu trees are a method of Bayes net structure learning.)
- Markov random fields (Chow-Liu trees can be viewed as MRFs.)
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.
Other notes:
- Click on "Preview" to see the videos.
-Paid-
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location:
Section 26.3, "Learning tree structures," pages 910-914
Supplemental resources (the following are optional, but you may find them useful)
-Paid-
→ Probabilistic Graphical Models: Principles and Techniques
A very comprehensive textbook for a graduate-level course on probabilistic AI.
Location:
Section 18.4.1, "Learning tree-structured networks," pages 808-809
See also
-No Additional Notes-