Robust inference of trees
From MaRDI portal
Publication:819944
spanning treesintervalsdependencegraphical modelsmutual informationimprecise Dirichlet modelimprecise probabilitiesrobust inference
Nonparametric robustness (62G35) Measures of association (correlation, canonical correlation, etc.) (62H20) Programming involving graphs or networks (90C35) Trees (05C05) Reasoning under uncertainty in the context of artificial intelligence (68T37) Series expansions (e.g., Taylor, Lidstone series, but not Fourier series) (41A58)
Abstract: This paper is concerned with the reliable inference of optimal tree-approximations to the dependency structure of an unknown distribution generating data. The traditional approach to the problem measures the dependency strength between random variables by the index called mutual information. In this paper reliability is achieved by Walley's imprecise Dirichlet model, which generalizes Bayesian learning with Dirichlet priors. Adopting the imprecise Dirichlet model results in posterior interval expectation for mutual information, and in a set of plausible trees consistent with the data. Reliable inference about the actual tree is achieved by focusing on the substructure common to all the plausible trees. We develop an exact algorithm that infers the substructure in time O(m^4), m being the number of random variables. The new algorithm is applied to a set of data sampled from a known distribution. The method is shown to reliably infer edges of the actual tree even when the data are very scarce, unlike the traditional approach. Finally, we provide lower and upper credibility limits for mutual information under the imprecise Dirichlet model. These enable the previous developments to be extended to a full inferential method for trees.
Recommendations
Cites work
- scientific article; zbMATH DE number 3647917 (Why is no real title available?)
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 48344 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 845703 (Why is no real title available?)
- scientific article; zbMATH DE number 3048061 (Why is no real title available?)
- A Benders decomposition approach for the robust spanning tree problem with interval data
- An introduction to the imprecise Dirichlet model for multinomial data
- An invariant form for the prior probability in estimation problems
- Approximating discrete probability distributions with dependence trees
- Bayesian data analysis.
- Bayesian network classifiers
- Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
- Distribution of mutual information from complete and incomplete data
- Exact credal treatment of missing data
- Interaction in multidimensional contingency tables: an information theoretic approach
- On Information and Sufficiency
- On the complexity of the robust spanning tree problem with interval data
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Partial identification of probability distributions.
- Robust learning with missing data
- THE PRECISION OF OBSERVED VALUES OF SMALL FREQUENCIES
- The robust spanning tree problem with interval data
Cited in
(10)- scientific article; zbMATH DE number 67622 (Why is no real title available?)
- On identifying tree-structured perfect maps
- An introduction to the imprecise Dirichlet model for multinomial data
- Learning a tree-structured Ising model in order to make predictions
- Approximating discrete probability distributions with dependence trees
- Tree models for difference and change detection in a complex environment
- Practical robust estimators for the imprecise Dirichlet model
- Testing for dependence on tree structures
- Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact Parameters
- Distribution of mutual information from complete and incomplete data
This page was built for publication: Robust inference of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819944)
