Learning a tree-structured Ising model in order to make predictions (Q2196190)

The objective of this paper is to show that learning a model that makes accurate predictions is possible even when structure learning is not. For realizing of this objective, the authors introduced a loss function to evaluate learning algorithms based on the accuracy of low-order marginals. The small-set total variation between true distribution \(P\) and learned distribution \(Q\) is used. The main result gives lower and upper bounds on the number of samples needed to learn a tree Ising model to ensure small \(L^{(2)}\) loss, which in this setting is equivalent to accurate pairwise marginals. In fact, the main result concerns the maximum likelihood tree (also called Chow-Liu tree, see [\textit{C. K. Chow} and \textit{C. N. Liu}, IEEE Trans. Inf. Theory 14, 462--467 (1968; Zbl 0165.22305)]. At the end of the paper, some interesting numerical simulations to demonstrate the performance of the Chow-Liu algorithm in terms of both the probability of incorrect recovery of underlying structure (zero-one loss) and the \(L^{(2)}\) loss are presented.