Develops a new method for decision trees using categorical variable structure.
problem Lack of structure in treating categorical variables as predictors.
method Introduces a mathematical framework to represent categorical structure and generalizes decision trees to utilize this structure.
result Improves prediction accuracy on weather data using the new method.
The paper uses tensor decompositions to improve neural network models for tree data.
problem Encoding structural knowledge from tree-structured data efficiently.
method Introduces new aggregation functions using Canonical and Tensor-Train decompositions.
result Proposed models outperform traditional methods on tree classification tasks.
We introduce the concept of community trees that summarizes topological structures within a network. A community tree is a tree structure representing clique communities from the clique percolation method (CPM). The community tree also generates a persistent diagram. Community trees and persistent diagrams reveal topol…
New algorithm efficiently learns sparse staged trees.
problem Scalability issue in existing structural learning algorithms for staged trees.
method Searches over a space of models with limited dependencies.
result First scalable structural learning algorithm for staged trees.
The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error…
We define the beta diffusion tree, a random tree structure with a set of leaves that defines a collection of overlapping subsets of objects, known as a feature allocation. A generative process for the tree structure is defined in terms of particles (representing the objects) diffusing in some continuous space, analogou…
Hierarchical structure is ubiquitous in data across many domains. There are many hierarchical clustering methods, frequently used by domain experts, which strive to discover this structure. However, most of these methods limit discoverable hierarchies to those with binary branching structure. This limitation, while com…
PolyILR: A Tree-Structured Orthonormal Decomposition of Compositional Data
problem Representing compositional data with hierarchical structure
method PolyILR: A canonical orthonormal decomposition of the Aitchison tangent space aligned with any tree topology
result PolyILR yields stable, interpretable features and enables inference at multiscale tree resolution
Paper presents a new method for learning hyperbolic representations using tree structures.
problem Learning faithful low-dimensional hyperbolic embeddings of data.
method Metric-first approach to learn tree structure, then embed into hyperbolic manifold.
result Novel fast algorithm TreeRep learns tree approximating original metric.
Width trees link link invariants and bridge number.
problem Understanding link invariants through geometric structures.
method Associate width trees to links and use their geometric properties to bound link invariants.
result Width trees uniquely realize certain link invariants under specific conditions.
New tree structure for pseudo-Anosovs from interval maps.
problem Understanding pseudo-Anosovs from interval maps.
method Tree structure on pseudo-Anosovs using rational numbers.
result Deepened dictionary between invariants.
R package stagedtrees learns staged tree structures from data.
problem Learning the structure of staged trees from data.
method Score-based and clustering-based algorithms implemented.
result Illustrated capabilities using two datasets.
This work considers the problem of learning the structure of multivariate linear tree models, which include a variety of directed tree graphical models with continuous, discrete, and mixed latent variables such as linear-Gaussian models, hidden Markov models, Gaussian mixture models, and Markov evolutionary trees. The …
Develops a new method to recover large latent tree models efficiently.
problem Inference of large latent tree structures from terminal node observations.
method Spectral Top-Down Recovery (STDR) using Fiedler vector partitioning.
result Proves statistical consistency and sample complexity for accurate tree recovery.
Decision Machines embeds decision trees into vector spaces for improved optimization.
problem Overfitting and difficulty in finding optimal decision tree structure.
method Embedding Boolean tests into a binary vector space and representing tree structure as matrices.
result Optimized decision trees with enhanced predictive power.
Researchers improve tree model recovery from noisy data.
problem Learning tree structured models from corrupted data.
method Linear latent tree models and continuous corruption model.
result Chow-Liu algorithm consistently learns tree from noisy data.
Study a risk model with tree-structured Poisson-Markov random field for rainfall events.
problem Dependence between rainfall frequencies in insurance portfolios.
method Tree-structured Markov random field with Poisson marginals.
result Asymptotic results for portfolio risk and risk allocation.
The task of translating between programming languages differs from the challenge of translating natural languages in that programming languages are designed with a far more rigid set of structural and grammatical rules. Previous work has used a tree-to-tree encoder/decoder model to take advantage of the inherent tree s…
New clustering method recovers hidden tree structure from data.
problem Recovering hidden hierarchical structure in data.
method Maximum average dot product for merging clusters in hierarchical clustering.
result The algorithm produces a tree that accurately represents the underlying generative hierarchical structure.
A recently proposed clustering method, called the Nearest Descent (ND), can organize the whole dataset into a sparsely connected graph, called the In-tree. This ND-based Intree structure proves able to reveal the clustering structure underlying the dataset, except one imperfect place, that is, there are some undesired …
SBT model uses randomized sharding and sub-models to improve Bayesian Additive Regression Trees.
problem Improving efficiency and accuracy of Bayesian Additive Regression Trees.
method Randomized sharding, sub-models, intersection tree structure, optimal design.
result Theoretical optimal weights and worst-case complexity of SBT model.
Energy trees handle complex data structures with multiple variable types.
problem Handling intricate data structures with various types of covariates.
method Energy trees, a regression and classification model, use energy statistics to accommodate structured covariates of different types.
result Energy trees maintain statistical foundations, interpretability, and robustness to overfitting.
Additive models, such as produced by gradient boosting, and full interaction models, such as classification and regression trees (CART), are widely used algorithms that have been investigated largely in isolation. We show that these models exist along a spectrum, revealing never-before-known connections between these t…
This paper introduces TNTK to study infinite soft tree ensembles.
problem Understanding the behavior of infinite soft tree ensembles.
method Introduced Tree Neural Tangent Kernel (TNTK) to analyze infinite soft tree ensembles.
result Identified several non-trivial properties of infinite soft tree ensembles.
Graph-to-Tree Neural Networks improve structured input-output translation in tasks like semantic parsing and math word problems.
problem Improving performance on tasks like semantic parsing and math word problem solving.
method Graph-to-Tree Neural Networks, consisting of a graph encoder and a hierarchical tree decoder.
result Graph2Tree model outperforms or matches state-of-the-art models on neural semantic parsing and math word problem tasks.
We introduce the Pitman Yor Diffusion Tree (PYDT) for hierarchical clustering, a generalization of the Dirichlet Diffusion Tree (Neal, 2001) which removes the restriction to binary branching structure. The generative process is described and shown to result in an exchangeable distribution over data points. We prove som…
Tree-AMP simplifies inference in complex tree-structured models.
problem Inference in high-dimensional tree-structured models.
method Approximate Message Passing algorithms for various machine learning tasks.
result Theoretical performance predictions and automated entropy estimation.
Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees…
New trees-based models handle correlated data better.
problem Standard trees-based models ignore correlation structure.
method Explicitly accounts for correlation structure in splitting criterion, stopping rules, and fitted values.
result New approach superior to standard models in simulations and real data.
Improved algorithm for partial recovery of tree-structured graphs with noisy data.
problem Learning Ising tree models with noisy observations.
method Symmetrized Geometric Averaging (SGA) algorithm with improved sample complexity.
result Significantly better sample complexity for partial tree recovery.
LDTA expands LDA's topic modeling capacity with tree-structured priors.
problem Limited expressiveness of Dirichlet priors in LDA for complex topic relationships.
method Introduces Latent Dirichlet-Tree Allocation (LDTA) with Dirichlet-Tree (DT) priors, and develops universal mean-field variational inference and Expectation Propagation.
result LDTA enables expressive, tree-structured priors over topic proportions, expanding modeling capacity of LDA.
Paper proposes an algorithm to reconstruct optimal model structure from graph adjacency matrix.
problem Optimal model structure reconstruction from weighted colored graph adjacency matrix.
method Uses prize-collecting Steiner tree algorithm to reconstruct minimum spanning tree.
result Demonstrates the effectiveness of the prize-collecting Steiner tree algorithm for model structure reconstruction.
New algorithms learn staged trees from incomplete data.
problem Handling missing data in staged tree learning.
method Characterized likelihood and pseudo-likelihoods for missing data, implemented structural expectation-maximization algorithm.
result It is feasible to account for different missingness patterns when learning staged trees.
Many common sequential data sources, such as source code and natural language, have a natural tree-structured representation. These trees can be generated by fitting a sequence to a grammar, yielding a hierarchical ordering of the tokens in the sequence. This structure encodes a high degree of syntactic information, ma…
Paper proposes a VB method for TS-SBP mixture models with reduced computational cost.
problem Efficiently learning tree-structured stick-breaking process mixture models.
method Utilizes Bayes coding algorithm for context tree models to calculate sums over all possible trees.
result Proposes a learning algorithm with less computational cost for TS-SBP mixture of Gaussians.
Optimal transport for measures on noisy tree metrics is solved with robust approach.
problem Optimal transport problem for measures on noisy tree metrics.
method Max-min robust optimal transport approach considering uncertainty sets of tree metrics.
result Robust optimal transport admits a closed-form expression for fast computation.
TES-AE uses tree grammars to speed up autoencoding for tree data.
problem Challenges in autoencoding tree data due to its non-vectorial and discrete nature.
method TES-AE combines reservoir computing with tree grammars for faster training.
result TES-AE outperforms D-VAE in speed and accuracy for tree data.
A new algorithm converts staged trees into Chain Event Graphs.
problem Creating explicit representations of structural zeros and conditional independences.
method Iterative backward algorithm transforming a staged tree into a CEG.
result No information is lost in the transformation from staged tree to CEG.
Symmetric TSP is structurally equivalent to a constrained Group Steiner Tree Problem.
problem Finding the shortest tour in a symmetric TSP.
method Structural equivalence between symmetric TSP and constrained Group Steiner Tree Problem.
result Maximizing net weight in the cGSTP is equivalent to minimizing the TSP tour length.
We introduce a new spatial data structure for high dimensional data called the \emph{approximate principal direction tree} (APD tree) that adapts to the intrinsic dimension of the data. Our algorithm ensures vector-quantization accuracy similar to that of computationally-expensive PCA trees with similar time-complexity…
The main goal of this paper is to study the geometric structures associated with the representation of tensors in subspace based formats. To do this we use a property of the so-called minimal subspaces which allows us to describe the tensor representation by means of a rooted tree. By using the tree structure and the d…
New algorithms learn simple staged trees from data, improving model fit.
problem Complex conditional independences in categorical data vectors.
method Structural learning algorithms for simple staged trees, coalescing the underlying tree.
result Data-learned simple staged trees often outperform Bayesian networks in model fit.
While learning models are typically studied for inputs in the form of a fixed dimensional feature vector, real world data is rarely found in this form. In order to meet the basic requirement of traditional learning models, structural data generally have to be converted into fix-length vectors in a handcrafted manner, w…
A new metric for comparing measures on tree systems reduces computational burden.
problem Heavy computation in Optimal Transport problems.
method Introducing tree systems and a novel metric (Tree-Sliced Wasserstein distance on Systems of Lines, TSW-SL).
result TSW-SL performs favorably compared to Sliced Wasserstein and its variants.
The problem of maximum-likelihood (ML) estimation of discrete tree-structured distributions is considered. Chow and Liu established that ML-estimation reduces to the construction of a maximum-weight spanning tree using the empirical mutual information quantities as the edge weights. Using the theory of large-deviations…
HS improves tree-based models' accuracy and interpretability without changing their structure.
problem Overfitting in tree-based models.
method Hierarchical Shrinkage (HS) post-hoc algorithm that shrinks tree predictions towards ancestor means.
result HS significantly improves predictive performance and interpretability of decision trees and RFs.
Bayesian learning for forests and trees improves graph detection and structure learning.
problem Learning graph structures in non-decomposable graphs.
method Adapted MCMC and SSS algorithms for forests and trees, using the Chow-Liu algorithm and Matrix Tree Theorem.
result SSS with trees or forests outperforms SSS with decomposable graphs in certain cases.
This paper introduces a new method to cluster qualitative attribute data using tree structures.
problem Clustering qualitative attribute data, especially when values are not in Euclidean space.
method Developed a joint learning mechanism to iteratively learn trees representing qualitative values' order relationships.
result The joint learning mechanism successfully clusters qualitative attribute data, yielding accurate results.