Spectral Top-Down Recovery of Latent Tree Models

• URL: http://arxiv.org/abs/2102.13276v1
• Date: Fri, 26 Feb 2021 02:47:42 GMT
• Title: Spectral Top-Down Recovery of Latent Tree Models
• Authors: Yariv Aizenbud, Ariel Jaffe, Meng Wang, Amber Hu, Noah Amsel, Boaz Nadler, Joseph T. Chang, Yuval Kluger
• Abstract summary: 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.
• Score: 13.681975313065477
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modeling the distribution of high dimensional data by a latent tree graphical model is a common approach in multiple scientific domains. A common task is to infer the underlying tree structure given only observations of the terminal nodes. Many algorithms for tree recovery are computationally intensive, which limits their applicability to trees of moderate size. For large trees, a common approach, termed divide-and-conquer, is to recover the tree structure in two steps. First, recover the structure separately for multiple randomly selected subsets of the terminal nodes. Second, merge the resulting subtrees to form a full tree. Here, we develop Spectral Top-Down Recovery (STDR), a divide-and-conquer approach for inference of large latent tree models. Unlike previous methods, 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 under certain conditions this partitioning is consistent with the tree structure. This, in turn leads to a significantly simpler merging procedure of the small subtrees. We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability. Using simulated data from several common tree models in phylogenetics, we demonstrate that STDR has a significant advantage in terms of runtime, with improved or similar accuracy.

Related papers

• Sharded Bayesian Additive Regression Trees [1.4213973379473654]
  We introduce a randomization auxiliary variable and a sharding tree to decide partitioning of data. By observing that the optimal design of a sharding tree can determine optimal sharding for sub-models on a product space, we introduce an intersection tree structure to completely specify both the sharding and modeling using only tree structures.
  arXiv  Detail & Related papers  (2023-06-01T05:41:31Z)
• 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)
• SETAR-Tree: A Novel and Accurate Tree Algorithm for Global Time Series Forecasting [7.206754802573034]
  In this paper, we explore the close connections between TAR models and regression trees. We introduce a new forecasting-specific tree algorithm that trains global Pooled Regression (PR) models in the leaves. In our evaluation, the proposed tree and forest models are able to achieve significantly higher accuracy than a set of state-of-the-art tree-based algorithms.
  arXiv  Detail & Related papers  (2022-11-16T04:30:42Z)
• Unbiased and Efficient Sampling of Dependency Trees [0.0]
  Most treebanks require that every valid dependency tree has a single edge coming out of the ROOT node. Zmigrod et al. have recently proposed algorithms for sampling with and without replacement from the single-root dependency tree distribution. We show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact biased.
  arXiv  Detail & Related papers  (2022-05-25T09:57:28Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  We introduce Hierarchical Shrinkage (HS), a post-hoc algorithm that does not modify the tree structure. HS substantially increases the predictive performance of decision trees, even when used in conjunction with other regularization techniques. All code and models are released in a full-fledged package available on Github.
  arXiv  Detail & Related papers  (2022-02-02T02:43:23Z)
• 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)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• 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)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• 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.