Robust inference of trees

DOI10.1007/S10472-005-9007-9zbMATH Open1177.68217DBLPjournals/amai/ZaffalonH05arXivcs/0511087OpenAlexW3098934517WikidataQ58012461 ScholiaQ58012461MaRDI QIDQ819944FDOQ819944

Authors: M. Zaffalon, Marcus Hutter 

Publication date: 4 April 2006

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0511087

Recommendations

• Approximating discrete probability distributions with dependence trees
• scientific article; zbMATH DE number 67622
• Epistemic irrelevance in credal nets: the case of imprecise Markov trees
• Distribution of mutual information from complete and incomplete data
• On identifying tree-structured perfect maps

zbMATH Keywords

spanning treesintervalsdependencegraphical modelsmutual informationimprecise Dirichlet modelimprecise probabilitiesrobust inference

Mathematics Subject Classification ID

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)

Cites Work

• Bayesian data analysis.
• Title not available (Why is that?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On Information and Sufficiency
• Title not available (Why is that?)
• Approximating discrete probability distributions with dependence trees
• Exact credal treatment of missing data
• Partial identification of probability distributions.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An invariant form for the prior probability in estimation problems
• Bayesian network classifiers
• The robust spanning tree problem with interval data
• On the complexity of the robust spanning tree problem with interval data
• A Benders decomposition approach for the robust spanning tree problem with interval data
• Robust learning with missing data
• Interaction in multidimensional contingency tables: an information theoretic approach
• An introduction to the imprecise Dirichlet model for multinomial data
• THE PRECISION OF OBSERVED VALUES OF SMALL FREQUENCIES
• Title not available (Why is that?)
• Distribution of mutual information from complete and incomplete data
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences

Cited In (9)

• Testing for dependence on tree structures
• Tree models for difference and change detection in a complex environment
• Title not available (Why is that?)
• Distribution of mutual information from complete and incomplete data
• An introduction to the imprecise Dirichlet model for multinomial data
• Practical robust estimators for the imprecise Dirichlet model
• On identifying tree-structured perfect maps
• Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact Parameters
• Approximating discrete probability distributions with dependence trees

Uses Software

• BayesDA

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)