Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
This work addresses the challenge of efficient and robust model learning for prediction tasks in graphical models, representing an incremental improvement over existing methods by optimizing sample complexity.
The authors tackled the problem of learning tree-structured Ising models to ensure accurate predictions, such as posteriors for small variable sets, and introduced a new algorithm that achieves optimal sample complexity under a prediction-centric loss, outperforming the classic Chow-Liu algorithm which can be arbitrarily suboptimal.
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]. While those results demonstrated that it is possible to learn a useful model even when recovering the true underlying graph is impossible, their bound depends on the maximum strength of interactions and thus does not achieve the information-theoretic optimum. In this paper, we introduce a new algorithm that carefully combines elements of the Chow-Liu algorithm with tree metric reconstruction methods to efficiently and optimally learn tree Ising models under a prediction-centric loss. Our algorithm is robust to model misspecification and adversarial corruptions. In contrast, we show that the celebrated Chow-Liu algorithm can be arbitrarily suboptimal.