Kybernetika 56 no. 6, 1022-1044, 2020

Characterisation of conditional independence structures for polymatroids using vanishing sets

Terence Chan, Qi Chen and Raymond YeungDOI: 10.14736/kyb-2020-6-1022

Abstract:

In this paper, we characterise and classify a list of full conditional independences via the structure of the induced set of vanishing atoms. Construction of Markov random subfield and minimal characterisation of polymatroids satisfying a MRF will also be given.

Keywords:

full conditional independence, markov random field, polymatroids

Classification:

62B10, 62-09

paper.pdf

References:

  1. A. Blake, P. Kohli and C. Rother: Markov random fields for vision and image processing. MIT Press, 2011.   DOI:10.7551/mitpress/8579.001.0001
  2. T. H. Chan, S. Thakor and A. Grant: Minimal characterisation of Shannon-type inequalities under functional dependence and full conditional independence structures. IEEE Trans. Inform. Theory 65 (2019), 7, 4041-4051.   DOI:10.1109/tit.2019.2900669
  3. M. Chen, J. Cho and H. Zhao: Incorporating biological pathways via a Markov random field model in genome-wide association studies. PLOS Genetics 7 (2011), 1-13.   DOI:10.1371/journal.pgen.1001353
  4. L. E. {Doyle}, A. C. {Kokaram}, S. J. {Doyle} and T. K. {Forde}: Ad hoc networking, {M}arkov random fields, and decision making. IEEE Signal Process. Mag. 23 (2006), 63-73.   DOI:10.1109/msp.2006.1708413
  5. D. Geiger and J. Pearl: Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 (1993), 4, 2001-2021.   DOI:10.1214/aos/1176349407
  6. F. Malvestuto: A unique formal system for binary decompositions of database relations, probability distributions, and graphs. Inform. Sci. 59 (1992), 1, 21-52.   DOI:10.1016/0020-0255(92)90042-7
  7. T. A. Snijders: Statistical models for social networks. Ann. Rev. Sociology 37 (2011), 1, 131-153.   DOI:10.1146/annurev.soc.012809.102709
  8. T. Wang, H. Krim and Y. Viniotis: A generalized Markov graph model: Application to social network analysis. IEEE J. Selected Topics Signal Process. 7 (2013), 318-332.   DOI:10.1109/jstsp.2013.2246767
  9. R. W. Yeung: A new outlook on Shannon's information measures. IEEE Trans. Inform. Theory 37 (1991), 466-474.   DOI:10.1109/18.79902
  10. R. W. Yeung: Information Theory and Network Coding. Springer, 2008.   CrossRef
  11. R. W. Yeung, A. Al-Bashabsheh, C. Chen, Q. Chen and P. Moulin: On information-theoretic characterizations of Markov random fields and subfields. IEEE Trans. Inform. Theory 65 (2019), 1493-1511.   DOI:10.1109/tit.2018.2866564
  12. R. W. Yeung, T. T. Lee and Z. Ye: Information-theoretic characterizations of conditional mutual independence and markov random fields. IEEE Trans. Inform. Theory 48 (2002), 1996-2011.   DOI:10.1109/tit.2002.1013139