On information-theoretic characterizations of markov random fields and subfields

Raymond W. Yeung, Ali Al-Bashabsheh, Chao Chen, Qi Chen, Pierre Moulin

Research output: Contribution to journalArticle

Abstract

Let X i , i ϵ V form a Markov random field (MRF) represented by an undirected graph G = (V,E) , and V′ be a subset of V. We determine the smallest graph that can always represent the subfield X i , i ϵ V′ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that X i , i ϵ V form a Markov chain, it is known that the I -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

Original languageEnglish (US)
Article number8444473
Pages (from-to)1493-1511
Number of pages19
JournalIEEE Transactions on Information Theory
Volume65
Issue number3
DOIs
StatePublished - Mar 2019

Fingerprint

Markov processes

Keywords

  • I-Measure
  • Markov random field
  • conditional independence
  • information diagram
  • subfield

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

On information-theoretic characterizations of markov random fields and subfields. / Yeung, Raymond W.; Al-Bashabsheh, Ali; Chen, Chao; Chen, Qi; Moulin, Pierre.

In: IEEE Transactions on Information Theory, Vol. 65, No. 3, 8444473, 03.2019, p. 1493-1511.

Research output: Contribution to journalArticle

Yeung, Raymond W. ; Al-Bashabsheh, Ali ; Chen, Chao ; Chen, Qi ; Moulin, Pierre. / On information-theoretic characterizations of markov random fields and subfields. In: IEEE Transactions on Information Theory. 2019 ; Vol. 65, No. 3. pp. 1493-1511.
@article{331876294b0e4c8497360cce44e74a3f,
title = "On information-theoretic characterizations of markov random fields and subfields",
abstract = "Let X i , i ϵ V form a Markov random field (MRF) represented by an undirected graph G = (V,E) , and V′ be a subset of V. We determine the smallest graph that can always represent the subfield X i , i ϵ V′ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that X i , i ϵ V form a Markov chain, it is known that the I -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).",
keywords = "I-Measure, Markov random field, conditional independence, information diagram, subfield",
author = "Yeung, {Raymond W.} and Ali Al-Bashabsheh and Chao Chen and Qi Chen and Pierre Moulin",
year = "2019",
month = "3",
doi = "10.1109/TIT.2018.2866564",
language = "English (US)",
volume = "65",
pages = "1493--1511",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3",

}

TY - JOUR

T1 - On information-theoretic characterizations of markov random fields and subfields

AU - Yeung, Raymond W.

AU - Al-Bashabsheh, Ali

AU - Chen, Chao

AU - Chen, Qi

AU - Moulin, Pierre

PY - 2019/3

Y1 - 2019/3

N2 - Let X i , i ϵ V form a Markov random field (MRF) represented by an undirected graph G = (V,E) , and V′ be a subset of V. We determine the smallest graph that can always represent the subfield X i , i ϵ V′ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that X i , i ϵ V form a Markov chain, it is known that the I -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

AB - Let X i , i ϵ V form a Markov random field (MRF) represented by an undirected graph G = (V,E) , and V′ be a subset of V. We determine the smallest graph that can always represent the subfield X i , i ϵ V′ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that X i , i ϵ V form a Markov chain, it is known that the I -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

KW - I-Measure

KW - Markov random field

KW - conditional independence

KW - information diagram

KW - subfield

UR - http://www.scopus.com/inward/record.url?scp=85052697986&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052697986&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2866564

DO - 10.1109/TIT.2018.2866564

M3 - Article

AN - SCOPUS:85052697986

VL - 65

SP - 1493

EP - 1511

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 3

M1 - 8444473

ER -