Approximating discrete probability distributions with causal dependence trees

Christopher J. Quinn, Todd P. Coleman, Negar Kiyavash

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationISITA/ISSSTA 2010 - 2010 International Symposium on Information Theory and Its Applications
Pages100-105
Number of pages6
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 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 - Taichung, Taiwan, Province of China
Duration: Oct 17 2010Oct 20 2010

Publication series

NameISITA/ISSSTA 2010 - 2010 International Symposium on Information Theory and Its Applications

Other

Other2010 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
Country/TerritoryTaiwan, Province of China
CityTaichung
Period10/17/1010/20/10

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Information Systems

Fingerprint

Dive into the research topics of 'Approximating discrete probability distributions with causal dependence trees'. Together they form a unique fingerprint.

Cite this