Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise

Understand

We study the problem of learning tree-structured Markov random fields (MRF) on discrete random variables with common support when the observations are corrupted by a $k$-ary symmetric noise channel with unknown probability of error.

• For Ising models (support size = 2), past work has shown that graph structure can only be recovered up to the leaf clusters (a leaf node, its parent, and its siblings form a leaf cluster) and exact recovery is impossible.
• No prior work has addressed the setting of support size of 3 or more, and indeed this setting is far richer.
• As we show, when the support size is 3 or more, the structure of the leaf clusters may be partially or fully identifiable.