This website uses Javascript to render markdown documents in your browser, apply syntax highlighting to code fragments and render $\LaTeX$ formulas. Below is the markdown source code of this page. You can either read that or enable Javascript to have it rendered to HTML.
# NAME
CInet::Base - The basis for computations on CI structures
# SYNOPSIS
# Imports CInet::{Cube,Relation,Symmetry,Seq}
use CInet::Base;
## VERSION
This document describes CInet::Base v0.10.2.
# DESCRIPTION
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.
## Brief introduction
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 | K
or 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.
## CInet::Cube
A [CInet::Cube](/doc/CInet%3A%3ACube) 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](/doc/CInet%3A%3ARelation) objects in order for it to work properly.
### The canonical ordering of faces
To facilitate storage, search and retrieval objects which assign data to
`CInet::Cube` faces, we use the conventions from [https://gaussoids.de](https://gaussoids.de)
for how to order the faces of a fixed dimension. A face of the cube is
represented by a pair of disjoint sets written in the form `(I|K)`.
The set `I` indexes all coordinates which are allowed to vary; its
cadinality is the dimension of the face. The set `K` indexes all
coordinates which are fixed to 1. The other coordinates are zero.
This uniquely defines a face of the cube.
Let the dimension `d` be fixed. The enumeration of all faces of this
dimension, proceeds in blocks. First, order all `d`-subsets of the ground
set lexicographically. For each such subset `I`, a block is formed by
emitting all faces `(I|K)` where `K` runs through all subsets of the
complement of `I`, stratified by cardinality and within each cardinality
again lexicographically.
For example, this produces all 2-faces in the canonical ordering
(displayed block by block):
say join ", ", map { "(".FACE.")" } Cube(4)->squares;
#= (12|), (12|3), (12|4), (12|34),
#= (13|), (13|2), (13|4), (13|24),
#= (14|), (14|2), (14|3), (14|23),
#= (23|), (23|1), (23|4), (23|14),
#= (24|), (24|1), (24|3), (24|13),
#= (34|), (34|1), (34|2), (34|12)
## CInet::Relation
A [CInet::Relation](/doc/CInet%3A%3ARelation) object represents a CI structure. It associates to
every 2-face of its domain [CInet::Cube](/doc/CInet%3A%3ACube) 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](/doc/CInet%3A%3ARelation) therefore has methods
which mirror corresponding [CInet::Cube](/doc/CInet%3A%3ACube) 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](/doc/CInet%3A%3ARelation) 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.
## CInet::Symmetry
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](/doc/CInet%3A%3ASymmetry) 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](/doc/CInet%3A%3ASymmetry) module provides these three groups in a form that
is suitable to reduce a collection of [CInet::Relation](/doc/CInet%3A%3ARelation) objects modulo
each group in bulk. See [CInet::Seq::Modulo](/doc/CInet%3A%3ASeq%3A%3AModulo) for how to do this.
## CInet::Seq
Collections of [CInet::Relation](/doc/CInet%3A%3ARelation) or related objects are dealt with _en masse_
using objects of type [CInet::Seq](/doc/CInet%3A%3ASeq). Such an object stands for a _sequence_
of objects that are lazily produced. They can be filtered and transformed lazily.
The [CInet::Seq](/doc/CInet%3A%3ASeq) 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](/doc/CInet%3A%3ASeq) role included in this distribution are
- [CInet::Seq::List](/doc/CInet%3A%3ASeq%3A%3AList) wrapping a [CInet::Seq](/doc/CInet%3A%3ASeq) interface around an array,
- [CInet::Seq::Map](/doc/CInet%3A%3ASeq%3A%3AMap) a `map` on a sequence,
- [CInet::Seq::Grep](/doc/CInet%3A%3ASeq%3A%3AGrep) a `grep` on a sequence,
- [CInet::Seq::Uniq](/doc/CInet%3A%3ASeq%3A%3AUniq) a stringy `uniq` on a sequence,
- [CInet::Seq::Modulo](/doc/CInet%3A%3ASeq%3A%3AModulo) reducing a sequence of relations modulo one
of the symmetry groups from [CInet::Symmetry](/doc/CInet%3A%3ASymmetry).
# AUTHOR
Tobias Boege <tobs@taboege.de>
# COPYRIGHT AND LICENSE
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.