We introduce an algebraic concept of the frame for abstract conditional independence (CI) models, together with basic operations with respect to which such a frame should be closed: copying and marginalization. Three standard examples of such frames are (discrete) probabilistic CI structures, semi-graphoids and structural semi-graphoids. We concentrate on those frames which are closed under the operation of set-theoretical intersection because, for these, the respective families of CI models are lattices. This allows one to apply the results from lattice theory and formal concept analysis to describe such families in terms of implications among CI statements. The central concept of this paper is that of self-adhesivity defined in algebraic terms, which is a combinatorial reflection of the self-adhesivity concept studied earlier in context of polymatroids and information theory. The generalization also leads to a self-adhesivity operator defined on the meta-level of CI frames. We answer some of the questions related to this approach and raise other open questions. The core of the paper is in computations. The combinatorial approach to computation might overcome some memory and space limitation of software packages based on polyhedral geometry, in particular, if SAT solvers are utilized. We characterize some basic CI families over 4 variables in terms of canonical implications among CI statements. We apply our method in information-theoretical context to the task of entropic region demarcation over 5 variables.

Probabilistic independence is a key concept in probability theory and statistics. For probabilistic independence a set of well known qualitative rules exists, the so-called semi-graphoid rules, which can be summarized into a single semi-graphoid rule. This rule system was conjectured to be complete, it is however incomplete and an additional five rules were formulated. The generalization of one of those rules subsequently showed that no finite rule system exists and in recent work even all five additional rules were (further) generalized. In this paper, two new generalized rules are stated, both involving n, n≥1 variable sets Ci. These rules generalize the semi-graphoid rule for n is odd and generalize one of the additional rules for n is even. Furthermore two new rules of probabilistic independence are given. The paper thereby contributes to the insights into the structural properties of probabilistic independence and provides an enhanced description of probabilistic independence by means of rules.

A Bayesian network is a concise representation of a joint probability distribution, which can be used to compute any probability of interest for the represented distribution. Credal networks were introduced to cope with the inevitable inaccuracies in the parametrisation of such a network. Where a Bayesian network is parametrised by defining unique local distributions, in a credal network sets of local distributions are given. From a credal network, lower and upper probabilities can be inferred. Such inference, however, is often problematic since it may require a number of Bayesian network computations exponential in the number of credal sets. In this paper we propose a preprocessing step that is able to reduce this complexity. We use sensitivity functions to show that for some classes of parameter in Bayesian networks the qualitative effect of a parameter change on an outcome probability of interest is independent of the exact numerical specification. We then argue that credal sets associated with such parameters can be replaced by a single distribution.

One-dimensional Bayesian network classifiers (OBCs) are popular tools for classification [2]. An OBC is a Bayesian network [4] consisting of just a single class variable and several feature variables. Multi-dimensional Bayesian network classifiers (MBCs) were introduced to generalise OBCs to multiple class variables [1, 6]. Classification performance of OBCs is known to be rather good. Experimental results that support this observation were substantiated by a study of the sensitivity properties of naive OBCs [5]. In this paper we investigate the sensitivity of MBCs. We present sensitivity functions for the outcome probabilities of interest of an MBC and use these functions to study the sensitivity value. This value captures the sensitivity of an output probability to small changes in a parameter. We compare MBCs to OBCs in this respect and conclude that an MBC will on average be even more robust to parameter changes than an OBC.