Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models

Understand

We consider the problem of learning a tree-structured Ising model from data, such that subsequent predictions computed using the model are accurate.

• Concretely, we aim to learn a model such that posteriors $P(X_i|X_S)$ for small sets of variables $S$ are accurate.
• Since its introduction more than 50 years ago, the Chow-Liu algorithm, which efficiently computes the maximum likelihood tree, has been the benchmark algorithm for learning tree-structured graphical models.
• A bound on the sample complexity of the Chow-Liu algorithm with respect to the prediction-centric local total variation loss was shown in [BK19].