Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
- URL: http://arxiv.org/abs/2106.03969v1
- Date: Mon, 7 Jun 2021 21:09:29 GMT
- Title: Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
- Authors: Enric Boix-Adsera, Guy Bresler, Frederic Koehler
- Abstract summary: We introduce a new algorithm that combines elements of the Chow-Liu algorithm with tree metric reconstruction methods.
Our algorithm is robust to model misspecification and adversarial corruptions.
- Score: 30.62276301751904
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of learning a tree-structured Ising model from data,
such that subsequent predictions computed using the model are accurate.
Concretely, we aim to learn a model such that posteriors $P(X_i|X_S)$ for small
sets of variables $S$ are accurate. Since its introduction more than 50 years
ago, the Chow-Liu algorithm, which efficiently computes the maximum likelihood
tree, has been the benchmark algorithm for learning tree-structured graphical
models. A bound on the sample complexity of the Chow-Liu algorithm with respect
to the prediction-centric local total variation loss was shown in [BK19]. While
those results demonstrated that it is possible to learn a useful model even
when recovering the true underlying graph is impossible, their bound depends on
the maximum strength of interactions and thus does not achieve the
information-theoretic optimum. In this paper, we introduce a new algorithm that
carefully combines elements of the Chow-Liu algorithm with tree metric
reconstruction methods to efficiently and optimally learn tree Ising models
under a prediction-centric loss. Our algorithm is robust to model
misspecification and adversarial corruptions. In contrast, we show that the
celebrated Chow-Liu algorithm can be arbitrarily suboptimal.
Related papers
- Optimal estimation of Gaussian (poly)trees [25.02920605955238]
We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery)
The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently.
The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning.
arXiv Detail & Related papers (2024-02-09T12:58:36Z) - Scaling Structured Inference with Randomization [64.18063627155128]
We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states.
Our method is widely applicable to classical DP-based inference.
It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
arXiv Detail & Related papers (2021-12-07T11:26:41Z) - 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) - A cautionary tale on fitting decision trees to data from additive
models: generalization lower bounds [9.546094657606178]
We study the generalization performance of decision trees with respect to different generative regression models.
This allows us to elicit their inductive bias, that is, the assumptions the algorithms make (or do not make) to generalize to new data.
We prove a sharp squared error generalization lower bound for a large class of decision tree algorithms fitted to sparse additive models.
arXiv Detail & Related papers (2021-10-18T21:22: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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
We show that $n$-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance $epsilon$ from an optimal $O(n ln n/epsilon2)$ samples.
Our guarantees do not follow from known results for the Chow-Liu algorithm.
arXiv Detail & Related papers (2020-10-28T10:17:48Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models.
Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
arXiv Detail & Related papers (2020-08-29T14:58:26Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
We present a novel algorithm for learning optimal classification trees based on dynamic programming and search.
Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
arXiv Detail & Related papers (2020-07-24T17:06:55Z)
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.