1,744,249 research outputs found
On Minimum Elementary-Triplet Bases for Independence Relations
No full textA semi-graphoid independence relation is a set of independence statements, called triplets, and is typically exponentially large in the number of variables involved. For concise representation of such a relation, a subset of its triplets is listed in a so-called basis; its other triplets are defined implicitly through a set of axioms. An elementary-triplet basis for this purpose consists of all elementary triplets of a relation. Such a basis however, may include redundant information. In this paper we provide two lower bounds on the size of an elementary-triplet basis in general and an upper bound on the size of a minimum elementary-triplet basis. We further specify the construction of an elementary-triplet basis of minimum size for restricted relations
Naive Bayesian classifiers with extreme probability features
No full textDespite their popularity, naive Bayesian classifiers are not well suited for real-world applications involving extreme probability features. As will be demonstrated in this paper, methods used to forestall the inclusion of zero probability parameters in naive classifiers have quite counterintuitive effects. An elegant, principled solution for handling extreme probability events is available however, from coherent conditional probability theory. We will show how this theory can be integrated in standard naive Bayesian classifiers, and then present a computational framework that retains the classifiers’ efficiency in the presence of a limited number of extreme probability features
Propagation effects of model-calculated probability values in Bayesian networks
Full text linkProbabilistic causal interaction models have become quite popular among Bayesian-network engineers as elicitation of all probabilities required often proves the main bottleneck in building a real-world network with domain experts. The best-known interaction models are the noisy-OR model and its generalisations. These models in essence are parameterised conditional probability tables for which just a limited number of parameter probabilities are required. The models assume specific properties of intercausal interaction and cannot be applied uncritically. Given their clear engineering advantages however, they are subject to ill-considered use. This paper demonstrates that such ill-considered use can result in poorly calibrated output probabilities from a Bayesian network. By studying, in an analytical way, the propagation effects of noisy-OR calculated probability values, we identify conditions under which use of the model can be harmful for a network's performance. These conditions demonstrate that use of the noisy-OR model for mere pragmatic reasons is sometimes warranted, even when the model's underlying assumptions are not met in reality
Balanced sensitivity functions for tuning multi-dimensional Bayesian network classifiers
Full text linkMulti-dimensional Bayesian network classifiers are Bayesian networks of restricted topological structure, which are tailored to classifying data instances into multiple dimensions. Like more traditional classifiers, multi-dimensional classifiers are typically learned from data and may include inaccuracies in their parameter probabilities. We will show that the graphical properties and dedicated use of these classifiers induce higher-order sensitivity functions of a highly constrained functional form in these parameters. We then introduce the concept of balanced sensitivity function in which multiple parameters are functionally related by the odds ratios of their original and new values, and argue that these functions provide for a suitable heuristic for tuning multi-dimensional classifiers with guaranteed bounds on the effects on their output probabilities. We demonstrate the practicability of our heuristic by means of a classifier for a real-world application in the veterinary field
Concise representations and construction algorithms for semi-graphoid independency models
Full text linkThe conditional independencies from a joint probability distribution constitute a model which is closed under the semi-graphoid properties of independency. These models typically are exponentially large in size and cannot be feasibly enumerated. For describing a semi-graphoid model therefore, researchers have proposed a more concise representation. This representation is composed of a representative subset of the independencies involved, called a basis, and lets all other independencies be implicitly defined by the semi-graphoid properties. An algorithm is available for computing such a basis for a semi-graphoid independency model. In this paper, we identify some new properties of a basis in general which can be exploited for arriving at an even more concise representation of a semi- graphoid model. Based upon these properties, we present an enhanced algorithm for basis construction which never returns a larger basis for a given independency model than currently existing algorithms
Evidence evaluation: a study of likelihoods and independence
No full textIn the context of evidence evaluation, where the probability of evidence given a certain hypothesis is considered, different pieces of evidence are often combined in a naive way by assuming conditional independence. In this paper we present a number of results that can be used to assess both the importance of a reliable likelihood-ratio estimate and the impact of neglecting dependencies among pieces of evidence for the purpose of evidence evaluation. We analytically study the effect of changes in dependencies between pieces of evidence on the likelihood ratio, and provide both theoretical and empirical bounds on the error in likelihood occasioned by assuming independences that do not hold in practice. In addition, a simple measure of influence strength between pieces of evidence is proposed
Credal Sum-Product Networks
No full textSum-product networks are a relatively new and increasingly popular class of (precise) probabilistic graphical models that allow for marginal inference with polynomial effort. As with other probabilistic models, sum-product networks are often learned from data and used to perform classification. Hence, their results are prone to be unreliable and overconfident. In this work, we develop credal sum-product networks, an imprecise extension of sum-product networks. We present algorithms and complexity results for common inference tasks. We apply our algorithms on realistic classification task using images of digits and show that credal sum-product networks obtained by a perturbation of the parameters of learned sum-product networks are able to distinguish between reliable and unreliable classifications with high accuracy
Efficient learning of Bayesian networks with bounded tree-width
No full textLearning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [24,29] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. Finding the best k-tree, however, is computationally intractable. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an informative score function to characterize the quality of a k-tree. To further improve the quality of the k-trees, we propose a probabilistic hill climbing approach that locally refines the sampled k-trees. The proposed algorithm can efficiently learn a quality Bayesian network with tree-width at most k. Experimental results demonstrate that our approach is more computationally efficient than the exact methods with comparable accuracy, and outperforms most existing approximate methods
Entropy-based Pruning for Learning Bayesian Networks using BIC
Full text linkFor decomposable score-based structure learning of Bayesian networks, existing approaches first compute a collection of candidate parent sets for each variable and then optimize over this collection by choosing one parent set for each variable without creating directed cycles while maximizing the total score. We target the task of constructing the collection of candidate parent sets when the score of choice is the Bayesian Information Criterion (BIC). We provide new non-trivial results that can be used to prune the search space of candidate parent sets of each node. We analyze how these new results relate to previous ideas in the literature both theoretically and empirically. We show in experiments with UCI data sets that gains can be significant. Since the new pruning rules are easy to implement and have low computational costs, they can be promptly integrated into all state-of-the-art methods for structure learning of Bayesian networks
Bayesian networks: a combined tuning heuristic
No full textOne of the issues in tuning an output probability of a Bayesian network by changing multiple parameters is the relative amount of the individual parameter changes. In an existing heuristic parameters are tied such that their changes induce locally a maximal change of the tuned probability. This heuristic, however, may reduce the attainable values of the tuned probability considerably. In another existing heuristic parameters are tied such that they simultaneously change in the entire interval . The tuning range of this heuristic will in general be larger then the tuning range of the locally optimal heuristic. Disadvantage, however, is that knowledge of the local optimal change is not exploited. In this paper a heuristic is proposed that is locally optimal, yet covers the larger tuning range of the second heuristic. Preliminary experiments show that this heuristic is a promising alternative
- …
