Information-theoretic characterizations of Markov random fields and subfields

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

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

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 [3]. We prove that Markov chain is essentially the only MRF that possesses this property. Our work is built on the set-theoretic characterization of an MRF in [4]. Unlike most works in the literature, we do not make the standard assumption that the underlying probability distribution is factorizable with respect to the graph representing the MRF.

Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory, ISIT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3040-3044
Number of pages5
ISBN (Electronic)9781509040964
DOIs
StatePublished - Aug 9 2017
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany
Duration: Jun 25 2017Jun 30 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2017 IEEE International Symposium on Information Theory, ISIT 2017
CountryGermany
CityAachen
Period6/25/176/30/17

Fingerprint

Subfield
Markov processes
Random Field
Probability distributions
Markov chain
Graph in graph theory
Undirected Graph
Probability Distribution
Non-negative
Necessary Conditions
Path
Subset
Sufficient Conditions

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

Yeung, R. W., Al-Bashabsheh, A., Chen, C., Chen, Q., & Moulin, P. (2017). Information-theoretic characterizations of Markov random fields and subfields. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 3040-3044). [8007088] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8007088

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

2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 3040-3044 8007088 (IEEE International Symposium on Information Theory - Proceedings).

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

Yeung, RW, Al-Bashabsheh, A, Chen, C, Chen, Q & Moulin, P 2017, Information-theoretic characterizations of Markov random fields and subfields. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8007088, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 3040-3044, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 6/25/17. https://doi.org/10.1109/ISIT.2017.8007088
Yeung RW, Al-Bashabsheh A, Chen C, Chen Q, Moulin P. Information-theoretic characterizations of Markov random fields and subfields. In 2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 3040-3044. 8007088. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2017.8007088
Yeung, Raymond W. ; Al-Bashabsheh, Ali ; Chen, Chao ; Chen, Qi ; Moulin, Pierre. / Information-theoretic characterizations of Markov random fields and subfields. 2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 3040-3044 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{5673b51189624d478d6554114b463335,
title = "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 [3]. We prove that Markov chain is essentially the only MRF that possesses this property. Our work is built on the set-theoretic characterization of an MRF in [4]. Unlike most works in the literature, we do not make the standard assumption that the underlying probability distribution is factorizable with respect to the graph representing the MRF.",
author = "Yeung, {Raymond W.} and Ali Al-Bashabsheh and Chao Chen and Qi Chen and Pierre Moulin",
year = "2017",
month = "8",
day = "9",
doi = "10.1109/ISIT.2017.8007088",
language = "English (US)",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "3040--3044",
booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",
address = "United States",

}

TY - GEN

T1 - 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 - 2017/8/9

Y1 - 2017/8/9

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 [3]. We prove that Markov chain is essentially the only MRF that possesses this property. Our work is built on the set-theoretic characterization of an MRF in [4]. Unlike most works in the literature, we do not make the standard assumption that the underlying probability distribution is factorizable with respect to the graph representing the MRF.

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 [3]. We prove that Markov chain is essentially the only MRF that possesses this property. Our work is built on the set-theoretic characterization of an MRF in [4]. Unlike most works in the literature, we do not make the standard assumption that the underlying probability distribution is factorizable with respect to the graph representing the MRF.

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

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

U2 - 10.1109/ISIT.2017.8007088

DO - 10.1109/ISIT.2017.8007088

M3 - Conference contribution

AN - SCOPUS:85034042959

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 3040

EP - 3044

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

ER -