Chow-Liu tree from mutual information

Learn the strongest tree of pairwise dependencies

A tree-structured Bayesian network is a cheap model of a joint distribution over discrete variables. The Chow-Liu algorithm picks the tree that maximizes the total pairwise mutual information between connected variables. It is a maximum spanning tree problem where each edge weight is a mutual information.

Implement two functions.

• mutual_information(a, b): the mutual information in bits between two 1-D discrete arrays of the same length. Use the empirical joint distribution.
• chow_liu_tree(X): X is an n by d array of discrete columns. Return a sorted list of (i, j) tuples with i < j for the edges of a maximum spanning tree over the d columns.

Constraints

• mutual_information raises ValueError if the inputs are not 1-D with the same length.
• chow_liu_tree raises ValueError if X is not 2-D. It returns [] when d = 1.
• Return exactly d - 1 edges for d >= 1.
• Do not modify the inputs.

Hints