(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.
- Click on "Preview" to see the videos.
→ 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)
→ 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
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation