Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters

Elchanan Mossel; Sébastien Roch; Allan Sly

doi:10.1109/TIT.2013.2251927

Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters

Elchanan Mossel, Sébastien Roch, Allan Sly

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log²n) samples, where n is the number of nodes.

Original language	English (US)
Article number	6476722
Pages (from-to)	4357-4373
Number of pages	17
Journal	IEEE Transactions on Information Theory
Volume	59
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2013.2251927
State	Published - Jul 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Gaussian graphical models on trees
Kesten-Stigum (KS) reconstruction bound
Markov random fields on trees
Phase transitions

Access to Document

10.1109/TIT.2013.2251927

Cite this

@article{afcc2161802c4067b381c9f3a6cbae6e,

title = "Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters",

abstract = "Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log2n) samples, where n is the number of nodes.",

keywords = "Gaussian graphical models on trees, Kesten-Stigum (KS) reconstruction bound, Markov random fields on trees, Phase transitions",

author = "Elchanan Mossel and S{\'e}bastien Roch and Allan Sly",

year = "2013",

month = jul,

doi = "10.1109/TIT.2013.2251927",

language = "English (US)",

volume = "59",

pages = "4357--4373",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Robust estimation of latent tree graphical models

T2 - Inferring hidden states with inexact parameters

AU - Mossel, Elchanan

AU - Roch, Sébastien

AU - Sly, Allan

PY - 2013/7

Y1 - 2013/7

N2 - Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log2n) samples, where n is the number of nodes.

AB - Latent tree graphical models are widely used in computational biology, signal and image processing, and network tomography. Here, we design a new efficient, estimation procedure for latent tree models, including Gaussian and discrete, reversible models, that significantly improves on previous sample requirement bounds. Our techniques are based on a new hidden state estimator that is robust to inaccuracies in estimated parameters. More precisely, we prove that latent tree models can be estimated with high probability in the so-called Kesten-Stigum regime with O(log2n) samples, where n is the number of nodes.

KW - Gaussian graphical models on trees

KW - Kesten-Stigum (KS) reconstruction bound

KW - Markov random fields on trees

KW - Phase transitions

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

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

U2 - 10.1109/TIT.2013.2251927

DO - 10.1109/TIT.2013.2251927

M3 - Article

AN - SCOPUS:84897699286

SN - 0018-9448

VL - 59

SP - 4357

EP - 4373

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 6476722

ER -

Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this