TY - GEN
T1 - Approximating discrete probability distributions with causal dependence trees
AU - Quinn, Christopher J.
AU - Coleman, Todd P.
AU - Kiyavash, Negar
PY - 2010
Y1 - 2010
N2 - Chow and Liu considered the problem of approximating discrete joint distributions with dependence tree distributions where the goodness of the approximations were measured in terms of KL distance. They (i) demonstrated that the minimum divergence approximation was the tree with maximum sum of mutual informations, and (ii) specified a low-complexity minimum-weight spanning tree algorithm to find the optimal tree. In this paper, we consider an analogous problem of approximating the joint distribution on discrete random processes with causal, directed, dependence trees, where the approximation is again measured in terms of KL distance. We (i) demonstrate that the minimum divergence approximation is the directed tree with maximum sum of directed informations, and (ii) specify a low-complexity minimum weight directed spanning tree, or arborescence, algorithm to find the optimal tree. We also present an example to demonstrate the algorithm.
AB - Chow and Liu considered the problem of approximating discrete joint distributions with dependence tree distributions where the goodness of the approximations were measured in terms of KL distance. They (i) demonstrated that the minimum divergence approximation was the tree with maximum sum of mutual informations, and (ii) specified a low-complexity minimum-weight spanning tree algorithm to find the optimal tree. In this paper, we consider an analogous problem of approximating the joint distribution on discrete random processes with causal, directed, dependence trees, where the approximation is again measured in terms of KL distance. We (i) demonstrate that the minimum divergence approximation is the directed tree with maximum sum of directed informations, and (ii) specify a low-complexity minimum weight directed spanning tree, or arborescence, algorithm to find the optimal tree. We also present an example to demonstrate the algorithm.
UR - http://www.scopus.com/inward/record.url?scp=78651302328&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78651302328&partnerID=8YFLogxK
U2 - 10.1109/ISITA.2010.5649470
DO - 10.1109/ISITA.2010.5649470
M3 - Conference contribution
AN - SCOPUS:78651302328
SN - 9781424460175
T3 - ISITA/ISSSTA 2010 - 2010 International Symposium on Information Theory and Its Applications
SP - 100
EP - 105
BT - ISITA/ISSSTA 2010 - 2010 International Symposium on Information Theory and Its Applications
T2 - 2010 20th International Symposium on Information Theory and Its Applications, ISITA 2010 and the 2010 20th International Symposium on Spread Spectrum Techniques and Applications, ISSSTA 2010
Y2 - 17 October 2010 through 20 October 2010
ER -