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.9.3. # 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. ## 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.