Learning Trees (cont)

Algorithm:

• Construct graph with vertices: 1, 2, …

• Set w(i?j) be Score( Xj | Xi ) - Score(Xj)

• Find tree (or forest) with maximal weight

  • This can be done using standard algorithms in low-order polynomial time by building a tree in a greedy fashion(Kruskal’s maximum spanning tree algorithm)

Theorem: This procedure finds the tree with maximal score

When score is likelihood, then w(i?j) is proportional to I(Xi; Xj) this is known as the Chow & Liu method

Previous slide

Next slide

Back to first slide

View graphic version