The quality of tree approximation from AUC bounds
Navid Tafaghodi Khajavi, Anthony Kuh · 2016
This paper looks at graphical models and discusses the quality of tree approximations by formulating the problem as a detection problem. One of the widely used algorithms for tree-structured approximation and modeling is the Chow-Liu algorithm. While this algorithm is optimal for Gaussian distributions in the sense of the Kullback-Leibler (KL) divergence, it is not optimal when compared with other information divergences and criteria such as Area Under the Curve (AUC). In this paper, we discuss the quality of tree approximation using the AUC. We define the correlation approximation matrix (CAM) and show that the KL divergence and AUC depend on the eigenvalues of the CAM. Examples show that the quality of tree approximations is in general not good for both information divergences and AUC when the number of nodes is large.