Robust Estimation of Tree Structured Markov Random Fields
- URL: http://arxiv.org/abs/2102.08554v1
- Date: Wed, 17 Feb 2021 03:47:26 GMT
- Title: Robust Estimation of Tree Structured Markov Random Fields
- Authors: Ashish Katiyar, Soumya Basu, Vatsal Shah, Constantine Caramanis
- Abstract summary: 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 unknown noise.
We show that in a general noise model, the underlying tree structure can be recovered only up to an equivalence class where each of the leaf nodes is indistinguishable from its parent and siblings, forming a leaf cluster.
We provide a precise characterization of recoverability by deriving a necessary and sufficient condition for the recoverability of a leaf cluster.
- Score: 25.467380816216824
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 unknown noise. As the presence of noise in the observations
obfuscates the original tree structure, the extent of recoverability of the
tree-structured MRFs under noisy observations is brought into question.
We show that in a general noise model, the underlying tree structure can be
recovered only up to an equivalence class where each of the leaf nodes is
indistinguishable from its parent and siblings, forming a leaf cluster. As the
indistinguishability arises due to contrived noise models, we study the natural
k-ary symmetric channel noise model where the value of each node is changed to
a uniform value in the support with an unequal and unknown probability. Here,
the answer becomes much more nuanced. We show that with a support size of 2,
and the binary symmetric channel noise model, the leaf clusters remain
indistinguishable. From support size 3 and up, the recoverability of a leaf
cluster is dictated by the joint probability mass function of the nodes within
it. We provide a precise characterization of recoverability by deriving a
necessary and sufficient condition for the recoverability of a leaf cluster. We
provide an algorithm that recovers the tree if this condition is satisfied, and
recovers the tree up to the leaf clusters failing this condition.
Related papers
- Probabilistic Tree-of-thought Reasoning for Answering
Knowledge-intensive Complex Questions [93.40614719648386]
Large language models (LLMs) are capable of answering knowledge-intensive complex questions with chain-of-thought (CoT) reasoning.
Recent works turn to retrieving external knowledge to augment CoT reasoning.
We propose a novel approach: Probabilistic Tree-of-thought Reasoning (ProbTree)
arXiv Detail & Related papers (2023-11-23T12:52:37Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure.
We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance.
We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
arXiv Detail & Related papers (2023-05-24T11:05:12Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
We design and analyze an algorithm that boosts the error exponent by at least 40% when $rho$ is at least $0.8$.
Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph.
arXiv Detail & Related papers (2021-10-27T10:45:21Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG)
We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product.
We derive the first known instance-dependent impossibility result for structure learning of latent trees.
arXiv Detail & Related papers (2021-06-02T01:37:52Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM)
We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
arXiv Detail & Related papers (2021-05-11T03:39:08Z) - Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
Spectral Top-Down Recovery (STDR) is a divide-and-conquer approach for inference of large latent tree models.
STDR's partitioning step is non-random. Instead, it is based on the Fiedler vector of a suitable Laplacian matrix related to the observed nodes.
We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability.
arXiv Detail & Related papers (2021-02-26T02:47:42Z) - Robust estimation of tree structured models [0.0]
We show that it is possible to recover trees from noisy binary data up to a small equivalence class of possible trees.
We also provide a characterisation of when the Chow-Liu algorithm consistently learns the underlying tree from the noisy data.
arXiv Detail & Related papers (2021-02-10T14:58:40Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise.
Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure.
We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
arXiv Detail & Related papers (2021-01-22T01:57:35Z) - Robust Estimation of Tree Structured Ising Models [20.224160348675422]
We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities.
We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors.
arXiv Detail & Related papers (2020-06-10T01:32:45Z) - Spectral neighbor joining for reconstruction of latent tree models [5.229354894035374]
We develop Spectral Neighbor Joining, a novel method to recover the structure of latent tree graphical models.
We prove that SNJ is consistent, and derive a sufficient condition for correct tree recovery from an estimated similarity matrix.
We illustrate via extensive simulations that in comparison to several other reconstruction methods, SNJ requires fewer samples to accurately recover trees with a large number of leaves or long edges.
arXiv Detail & Related papers (2020-02-28T05:13:08Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.