The problem of inferring dependency structures from random samples is a very fundamental topic in artificial intelligence and statistics. This paper reviews an early result from Chow and Liu on the approximation of unknown multinomial distributions by tree-dependency distributions, at the light of imprecise probabilities. Imprecision, arising here from Walley's imprecise Dirichlet model, generally makes many tree structures be plausible given the data. This paper focuses on the inference of the substructure common to all the possible trees. Such common pattern is a set of reliable dependencies. The problem of identifying the common pattern is abstracted and solved here in the general context of graph algorithms. On this basis, an algorithm is developed that infers reliable dependencies in time $O(k^{3})$, from a set of $k$ binary random variables, that converge to a tree as the sample grows. The algorithm works by computing bounds on the solutions of global optimization problems. There are a number of reasons why trees are a very important special case of dependence graphs. This work appears as a significant step in the direction of discovering dependency structures under the realistic assumption of imprecise knowledge.
Keywords. Tree dependencies, inference, imprecise Dirichlet model, mutual information, graphical model, Bayesian networks, robustness, multinomial distribution, maximum spanning tree
Format. PDF
Paper Download
The paper is availabe in the following sites:
Authors addresses:
Galleria 2
CH-6928 Manno
Switzerland
E-mail addresses:
| Marco Zaffalon | zaffalon@idsia.ch |