CInet::Base - The basis for computations on CI structures
# Imports CInet::{Cube,Relation,Symmetry,Seq}
use CInet::Base;This document describes CInet::Base v0.10.2.
This module imports all modules of the CInet::Base distribution. Here we given an overview of what and why these modules are and how they interact. For more information, see the specific documentation of each module.
Conditional independence structures are combinatorial abstractions of the ternary relations of stochastic conditional independence on a vector of finitely many random variables. If the vector is indexed by a set N and we have three disjoint subsets I, J and K, then this relation is usually written
I ⫫ J | Kor abbreviated as (I,J|K). Such ternary symbols are referred to as global CI statements. It is well-known that under the semigraphoid axioms, local CI statements suffice to completely describe a CI structure. That is to say: semigraphoids are uniquely given by their subset of local CI statements. Such a local statement has I = i and J = j be singletons and they are written (ij|K) where the first component ij is taken as a two-element subset of N.
Because of this equivalence and because the semigraphoid axioms are a very weak assumption, we work only with CI structures in the local world in this module.
A CInet::Cube object represents a ground set N and contains related methods. Imagine the unit cube in a space whose coordinates are indexed by the set N. We also say that the axes of the cube are labeled by the elements of N.
The face lattice of this cube stores different combinatorial data related to N, all accessible through one common abstraction -- the cube:
The vertices of the cube are in bijection to the subsets of
N,The edges encode elementary functional dependence statements on a random vector whose coordinates are indexed by
N,The squares (2-dimensional faces) encode local CI statements on such a random vector.
In addition to this data, the cube object implements transformations on the face lattice which are induced by symmetries of the cube: permutation of axes (implementing isomorphy of CI structures) or reflection over selected axes.
The cube structure imposes an order on each stratum (of fixed dimensional faces) of the face lattice. This order is necessary to translate an object represented by a face (as described in the list above) to a unique integer number and back. These serializations of parts of the lattice are required to formulate decision problems for properties of CI structures in formats that external solvers understand. For example, some properties can be computed using solvers for the Boolean satisfiability problem SAT where one Boolean variable must be allocated for every CI statement. This allocation is provided by the proper ordering of 2-face of the cube.
The cube is a kind of domain object which must be associated to a CInet::Relation objects in order for it to work properly.
A CInet::Relation object represents a CI structure. It associates to every 2-face of its domain CInet::Cube a coefficient. Usually these coefficients are Boolean: does the statement (ij|K) encoded by the 2-face assert a dependence or an independence? Since we take the point of view of conditional independence, the independence assertion receives the true value and the dependence assertion the false value.
Other coefficients one can use are orientations: is the dependence positive or negative? Or one can mark a CI statement as undefined.
Every action on the cube over which a relation is defined induces a lifted action on the relation. CInet::Relation therefore has methods which mirror corresponding CInet::Cube methods and execute the lifted action. It contains additional combinatorial operations for passing between cubes of different dimensions like taking minors or embedding. Minors correspond to a fusion of marginalization and conditioning from the statistical perspective.
CInet::Relation is the main class of the CInet modules. The other topical CInet::* modules extend this class with methods for deciding properties of CI structures with the methods of that module, for example Boolean satisfiability, graphical, polyhedral, algebraic or semidefinite optimization methods. To read about these methods, refer to the documentation of these other modules.
Three symmetry groups are commonly used on CI structures. They are all subgroups of the symmetry group of the cube, which is the hyperoctahedral group. The largest symmetry group implemented in CInet::Symmetry is exactly this group. Not all properties of interested are invariant under this action.
The smallest group is the symmetric group on the ground set. Every reasonable property of CI structures is invariant under this group.
In the middle between these two groups is the twisted symmetric group, which adds one hyperoctahedral involution (called duality) to the standard symmetric group.
The CInet::Symmetry module provides these three groups in a form that is suitable to reduce a collection of CInet::Relation objects modulo each group in bulk. See CInet::Seq::Modulo for how to do this.
Collections of CInet::Relation or related objects are dealt with en masse using objects of type CInet::Seq. Such an object stands for a sequence of objects that are lazily produced. They can be filtered and transformed lazily. The CInet::Seq package is a role which topical modules in the CInet::* namespace specialize when certain transformations on collections with a specific backing representation of relations can be implemented more efficiently.
This mix of composable topical specializations and inherent laziness leads to "self-clocking" pipelines which can be used to enumerate structures with a specific set of properties or non-properties, and in particular search for counterexamples to conjectures.
Implementations of the CInet::Seq role included in this distribution are
CInet::Seq::List wrapping a CInet::Seq interface around an array,
CInet::Seq::Map a
mapon a sequence,CInet::Seq::Grep a
grepon a sequence,CInet::Seq::Uniq a stringy
uniqon a sequence,CInet::Seq::Modulo reducing a sequence of relations modulo one of the symmetry groups from CInet::Symmetry.
Tobias Boege <[email protected]>
This software is copyright (C) 2020 by Tobias Boege.
This is free software; you can redistribute it and/or modify it under the terms of the Artistic License 2.0.