Efficient Learning of Optimal Markov Network Topology with k-Tree Modeling
This work addresses the problem of efficiently learning optimal Markov network topologies for higher-order correlations, offering a theoretical extension with practical algorithmic implications for domains like probabilistic modeling, though it is incremental relative to prior tree-based methods.
The paper generalizes the Chow-Liu result to Markov networks with tree width ≤ k, proving that minimum information loss is achieved with a maximum spanning k-tree topology, and provides a polynomial-time algorithm for learning optimal topology under a sufficient condition applicable to linear structures.
The seminal work of Chow and Liu (1968) shows that approximation of a finite probabilistic system by Markov trees can achieve the minimum information loss with the topology of a maximum spanning tree. Our current paper generalizes the result to Markov networks of tree width $\leq k$, for every fixed $k\geq 2$. In particular, we prove that approximation of a finite probabilistic system with such Markov networks has the minimum information loss when the network topology is achieved with a maximum spanning $k$-tree. While constructing a maximum spanning $k$-tree is intractable for even $k=2$, we show that polynomial algorithms can be ensured by a sufficient condition accommodated by many meaningful applications. In particular, we prove an efficient algorithm for learning the optimal topology of higher order correlations among random variables that belong to an underlying linear structure.