# 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-