PyPhi: A toolbox for integrated information theory
William G. P. Mayner William Marshall Larissa Albantakis Graham Findlay Robert Marchman Giulio Tononi
q-bio.NC cs.AI q-bio.QM




PyPhi: A toolbox for integrated information theory



William G. P. Mayner1,2,*,
William Marshall2,
Larissa Albantakis2,
Graham Findlay1,2,
Robert Marchman2,
Giulio Tononi2,*





  1 Neuroscience Training Program, University of Wisconsin–Madison, Madison, WI, USA

  2 Department of Psychiatry, Wisconsin Institute for Sleep and Consciousness, University of Wisconsin–Madison, Madison, WI, USA

  * , *







  §.§.§ Abstract

Integrated information theory provides a mathematical framework to fully characterize the cause-effect structure of a physical system. Here, we introduce PyPhi, a Python software package that implements this framework for causal analysis and unfolds the full cause-effect structure of discrete dynamical systems of binary elements. The software allows users to easily study these structures, serves as an up-to-date reference implementation of the formalisms of integrated information theory, and has been applied in research on complexity, emergence, and certain biological questions. We first provide an overview of the main algorithm and demonstrate PyPhi's functionality in the course of analyzing an example system, and then describe details of the algorithm's design and implementation.

PyPhi can be installed with Python’s package manager via the command `' on Linux and macOS systems equipped with Python 3.4 or higher. PyPhi is open-source and licensed under the GPLv3; the source code is hosted on GitHub at . Comprehensive and continually-updated documentation is available at . The  mailing list can be joined at . A web-based graphical interface to the software is available at .

sec:introduction


§ INTRODUCTION



Integrated information theory () has been proposed as a theory of consciousness. The central hypothesis is that a physical system has to meet five requirements (`postulates') in order to be a physical substrate of subjective experience:
[label=(*)]
  
  * intrinsic existence (the system must be able to make a difference to itself); 
  
  * composition (it must be composed of parts that have causal power within the whole);
  
  * information (its causal power must be specific);
  
  * integration (its causal power must not be reducible to that of its parts); and
  
  * exclusion (it must be maximally irreducible)
 <cit.>.

From these postulates, develops a mathematical framework to assess the cause-effect structure () of a physical system that is applicable to discrete dynamical systems. This framework has proven useful not only for the study of consciousness but has also been applied in research on complexity <cit.>, emergence <cit.>, and certain biological questions <cit.>.

The main measure of cause-effect power, integrated information (denoted Φ), quantifies how irreducible a system's is to those of its parts. Φ also serves as a general measure of complexity that captures to what extent a system is both integrated <cit.> and differentiated (informative) <cit.>. 

Here we describe PyPhi, a Python software package that implements 's framework for causal analysis and unfolds the full of discrete dynamical systems of binary elements. The software allows users to easily study these s and serves as an up-to-date reference implementation of the formalisms of .

Details of the mathematical framework are published elsewhere <cit.>; in sec:results we describe the output and input of the software and give an overview of the main algorithm in the course of reproducing results obtained from an example system studied in <cit.>. In sec:design we discuss specific issues concerning the algorithm's implementation. Finally in sec:availability we describe how the software can be obtained and discuss new functionality planned for future versions.

sec:results


§ RESULTS



sec:output


 §.§ Output



The software has two primary functions:
[label=(*)]
  
  * to unfold the full of a discrete dynamical system of interacting elements and compute its Φ value, and
  
  * to compute the maximally-irreducible cause-effect repertoires of a particular set of elements within the system.

The first is function is implemented by , which returns a object (<ref>A). The system's is contained in the `' attribute and its Φ value is contained in `'. Other attributes are detailed in the https://pyphi.readthedocs.io/page/api/models.subsystem.html#pyphi.models.subsystem.SystemIrreducibilityAnalysisonline documentation.

The is composed of objects, which are the output of the second main function:  (<ref>B). Each is specified by a set of elements within the system (contained in its `' attribute). A contains a maximally-irreducible cause and effect repertoire (`' and `'), which are probability distributions that capture how the mechanism elements in their current state constrain the previous and next state of the system, respectively; a φ value (`'), which measures the irreducibility of the repertoires; and several other attributes discussed below and detailed in the https://pyphi.readthedocs.io/page/api/models.mechanism.html#pyphi.models.mechanism.Conceptonline documentation.

fig:object-hierarchy



sec:input


 §.§ Input



The starting point for the analysis is a discrete dynamical system S composed of n interacting elements. Such a system can be represented by a directed graph of interconnected nodes, each equipped with a Markovian function that outputs the node's state at the next timestep t+1 given the state of its parents at the previous timestep t (<ref>). At present, PyPhi can analyze both deterministic and stochastic systems consisting of elements with two states.

fig:tpm



Such a discrete dynamical system is completely specified by its transition probability matrix (), which contains the probabilities of all state transitions from t to t+1. It can be obtained from the graphical representation of the system by perturbing the system into each of its possible states and observing the following state at the next timestep (for stochastic systems, repeated trials of perturbation/observation will yield the probabilities of each state transition). In PyPhi, the is the fundamental representation of the system.

Formally, if we let S_t be the random variable of the system state at t, the specifies the conditional probability distribution over the next state S_t+1 given each current state s_t: 

    (S_t+1| S_t = s_t),   ∀  s_t ∈Ω_S,
 
where Ω_S denotes the set of possible states. Furthermore, given a marginal distribution over the previous states of the system, the fully specifies the joint distribution over state transitions. Here imposes uniformity on the marginal distribution of the previous states because the aim of the analysis is to capture direct causal relationships across a single timestep without confounding factors, such as influences from system states before t - 1 <cit.>. The marginal distribution thus corresponds to an interventional (causal), not observed, state distribution.

Moreover, assumes that there is no instantaneous causation; that is, it is assumed that the elements of the dynamical system influence one another only from one timestep to the next. Therefore we require that the system satisfies the following Markov condition, called the conditional independence property: each element's state at t+1 must be independent of the state of the others, given the state of the system at t <cit.>,

    (S_t+1| S_t = s_t)  = ∏_N  ∈  S(N_t+1| S_t = s_t)
         ,   ∀  s_t ∈ S.

For systems of binary elements, a that satisfies <ref> can be represented in state-by-node form (<ref>, right), since we need only store each element's marginal distribution rather than the full joint distribution.

In PyPhi, the system under analysis is represented by a  object. A  is created by passing its as the first argument:  (see sec:demo-setup). Optionally, a connectivity matrix () can also be provided, where 

    []_i,j =
        
          1    if there is an edge from element i to element j 
    
          0    ,

via the  keyword argument: . Because the completely specifies the system, providing a is not necessary; however, explicit connectivity information can be used to make computations more efficient, especially for sparse networks, because PyPhi can rule out certain causal influences a priori if there are missing connections (see sec:connectivity). Note that this means providing an incorrect can result in inaccurate output. If no is given, PyPhi assumes full connectivity; , it assumes each element may have an effect on any other, which guarantees correct results.

Once the  is created, a subset of elements within the system (called a candidate system), together with a particular system state, can be selected for analysis by creating a  object. Hereafter we refer to a candidate system as a subsystem.

sec:demonstration


 §.§ Demonstration



The mathematical framework of is typically formulated using graphical causal models as representations of physical systems of elements. The framework builds on the causal calculus of the do( · ) operator introduced by Pearl <cit.>. In order to assess causal relationships among the elements, interventions (manipulations, perturbations) are used to actively set elements into a specific state, after which the resulting state transition is observed.

For reference, we define a set of graphical operations that are used during the analysis. To fix an element is to use system interventions to keep it in the same state for every observation. To noise an element is to use system interventions to set it into a state chosen uniformly at random. Finally, to cut a connection from a source element to a target element is to make the source appear noised to the target, while the remaining, uncut connections from the source still correctly transmit its state.

In this section we demonstrate some of the capabilities of the software by unfolding the of a small deterministic system of logic gates as described in <cit.> while describing how the algorithm is implemented in terms of manipulations, which we link to the graphical operations defined above. A schematic of the algorithm is shown in <ref> and <ref>, and a more detailed illustration is given in sup:presentation.

fig:algorithm-mechanism
 

fig:algorithm-system



sec:demo-setup


  §.§.§ Setup



The first step is to create the  object. Here we choose to provide the in 2-dimensional state-by-node form (see sec:2d-sbn-form). The is the only required argument, but we provide the as well, since we know that there are no self-loops in the system and PyPhi will use this information to speed up the computation. We also label the nodes A, B, and C to make the output easier to read.



  >>> import pyphi
  >>> import numpy as np
  >>> tpm = np.array([
  ...     [0.0, 0.0, 0.0],
  ...     [0.0, 0.0, 1.0],
  ...     [1.0, 0.0, 1.0],
  ...     [1.0, 0.0, 0.0],
  ...     [1.0, 0.0, 0.0],
  ...     [1.0, 1.0, 1.0],
  ...     [1.0, 0.0, 1.0],
  ...     [1.0, 1.0, 0.0]
  ... ])
  >>> cm = np.array([
  ...     [0, 1, 1],
  ...     [1, 0, 1],
  ...     [1, 1, 0],
  ... ])
  >>> network = pyphi.Network(tpm, cm=cm, node_labels=['A', 'B', 'C'])



We select a subsystem and a system state for analysis by creating a  object. System states are represented by tuples of s and s, with  meaning “ON” and  meaning “OFF.” In this case we will analyze the entire system, so the subsystem will contain all three nodes. The nodes to include can be specified with either their labels or their indices (note that in other PyPhi functions, nodes must be specified with their indices).



  >>> state = (1, 0, 0)
  >>> nodes = ('A', 'B', 'C')
  >>> subsystem = pyphi.Subsystem(network, state, nodes)



If there are nodes outside the subsystem, they are considered as background conditions for the causal analysis <cit.>. In the graphical representation of the system, the background conditions are fixed in their current state while the subsystem is perturbed and observed in order to derive its . In the representation, the equivalent operation is performed by conditioning the system on the state at t of the nodes outside the subsystem and then marginalizing out those nodes at t+1 (illustrated in sup:presentation). In PyPhi, this is done when the subsystem is created; the subsystem can be accessed with the  attribute, .

sec:demo-repertoire


  §.§.§ Cause/effect repertoires (mechanism-level information)



The lowest-level objects in the of a system are the cause repertoire and effect repertoire of a set of nodes within the subsystem, called a mechanism, over another set of nodes within the subsystem, called a purview of the mechanism. The cause (effect) repertoire is a probability distribution that captures the information specified by the mechanism about the purview by describing how the previous (next) state of the purview is constrained by the current state of the mechanism.

In terms of graphical operations, the effect repertoire is obtained by 
[label=(*)]
  
  * fixing the mechanism nodes in their state at t; 
  
  * noising the non-mechanism nodes at time t, so as to remove their causal influence on the purview; and 
  
  * observing the resulting state transition from t to t+1 while ignoring the state at t+1 of non-purview nodes, in order to derive a distribution over purview states at t+1.


The cause repertoire is obtained similarly, but in that case, the purview nodes at time t-1 are noised, and the resulting state transition from t-1 to t is observed while ignoring the state of non-mechanism nodes. Bayes' rule is then applied, resulting in a distribution over purview states at t-1. The corresponding operations on the are detailed in sec:repertoires and illustrated in sup:presentation.

Note that, operationally, we enforce that each input from a noised node conveys independent noise during the perturbation/observation step. In this way, we avoid counting correlations from outside the mechanism-purview pair as constraints due to the current state of the mechanism. Graphically, this process would correspond to replacing each noised node that is a parent of multiple purview nodes (for the effect repertoire) or mechanism nodes (for the cause repertoire) with multiple, independent “virtual nodes” (as in <cit.>). However, the equivalent definition of repertoires in <ref> obviates the need to actually implement virtual nodes in PyPhi.

With the  method of the , we can obtain the cause repertoire of, for example, mechanism A over the purview ABC depicted in Fig. 4 of <cit.>:



  >>> A, B, C = subsystem.node_indices
  >>> print(subsystem.state)
  (1, 0, 0)
  >>> mechanism = (A,)
  >>> purview = (A, B, C)
  >>> cr = subsystem.cause_repertoire(mechanism, purview)
  >>> print(cr)
  [[[ 0.          0.16666667]
    [ 0.16666667  0.16666667]]
  
   [[ 0.          0.16666667]
    [ 0.16666667  0.16666667]]]



We see that mechanism A in its current state, ON (), specifies information by ruling out the previous states in which B and C are OFF (). That is, the probability that either  or  was the previous state, given that A is currently ON, is zero:



  >>> print(cr[(0, 0, 0)])
  0.0
  >>> print(cr[(1, 0, 0)])
  0.0



Note that repertoires are returned in multidimensional form, so they can be indexed with state tuples as above. Repertoires can be reshaped to be 1-dimensional if needed, for plotting, but care must be taken that NumPy's FORTRAN (column-major) ordering is used so that PyPhi's little-endian convention for indexing states is respected (see sec:2d-sbn-form). PyPhi provides the  function for this:



  >>> flat_cr = pyphi.distribution.flatten(cr)
  >>> print(flat_cr)
  [ 0.          0.          0.16666667  0.16666667  0.16666667  0.16666667
    0.16666667  0.16666667]



sec:demo-mip


  §.§.§ Minimum-information partitions (mechanism-level integration)



Having assessed the information of a mechanism over a purview, the next step is to assess its integrated information (denoted φ) by quantifying the extent to which the cause and effect repertoires of the mechanism-purview pair can be reduced to the repertoires of its parts.

In terms of graphical operations, the irreducibility of a mechanism-purview pair is tested by partitioning it into parts and cutting the connections between them. By applying the perturbation/observation procedure after cutting the connections we obtain a partitioned repertoire. Since the partition renders the parts independent, in terms of manipulations, the partitioned repertoire can be calculated as the product of the individual repertoires for each of the parts. If the partitioned repertoire is no different than the original unpartitioned repertoire, then the mechanism as a whole did not specify integrated information about the purview. By contrast, if a repertoire cannot be factored in this way, then some of its selectivity is due to the causal influence of the mechanism as an integrated whole on the purview, and the repertoire is said to be irreducible.

The amount of irreducibility of a mechanism over a purview with respect to a partition is quantified as the distance between the unpartitioned repertoire and the partitioned repertoire (calculated with ). There are many ways to divide the mechanism and purview into parts, so the irreducibility is measured for every partition and the partition that yields the minimum irreducibility is called the minimum-information partition (). The integrated information (φ) of a mechanism-purview pair is the distance between the unpartitioned repertoire and the partitioned repertoire associated with the . PyPhi supports several distance measures and partitioning schemes (see sec:config).

The search procedure is implemented by the  and  methods. Each returns a object that contains the , as well as the φ value, mechanism, purview, temporal direction (cause or effect), unpartitioned repertoire, and partitioned repertoire. For example, we compute the effect of mechanism ABC over purview ABC from Fig. 6 of <cit.> as follows:



  >>> mechanism = (A, B, C)
  >>> purview = (A, B, C)
  >>> mip = subsystem.effect_mip(mechanism, purview)
  >>> print(mip)
  Repertoire irreducibility analysis
    φ = 1/4
    Mechanism: [A, B, C]
    Purview = [A, B, C]
    Direction: EFFECT
    Partition:
       ∅    A,B,C
      — × —–
       B     A,C 
    Repertoire:
      +————–+
      |  S     P(S)  |
      | ———— |
      | 000    0     |
      | 100    0     |
      | 010    0     |
      | 110    0     |
      | 001    1     |
      | 101    0     |
      | 011    0     |
      | 111    0     |
      +————–+
    Partitioned repertoire:
      +————–+
      |  S     P(S)  |
      | ———— |
      | 000    0     |
      | 100    0     |
      | 010    0     |
      | 110    0     |
      | 001    3/4   |
      | 101    0     |
      | 011    1/4   |
      | 111    0     |
      +————–+



Here we can see that the attempts to factor the repertoire of ABC over ABC into the product of the repertoire of ABC over AC and the repertoire of the empty mechanism ∅ over B. However, the repertoire cannot be factored in this way without information loss; the distance between the unpartitioned and partitioned repertoire is nonzero (φ = 1/4). Thus mechanism ABC over the purview ABC is irreducible.

sec:demo-mice


  §.§.§ Maximally-irreducible cause-effect repertoires (mechanism-level exclusion)



Next, we apply 's postulate of exclusion at the mechanism level by finding the maximally-irreducible cause () and maximally irreducible effect () specified by a mechanism. This is done by searching over all possible purviews for the object with the maximal φ value. The  and  methods implement this search procedure; they return a  and a  object, respectively. The of mechanism BC, for example, is the purview AB (Fig. 8 of <cit.>). This is computed like so:



  >>> mechanism = (B, C)
  >>> mic = subsystem.mic(mechanism)
  >>> print(mic)
  Maximally-irreducible cause
    φ = 1/3
    Mechanism: [B, C]
    Purview = [A, B]
    Direction: CAUSE
    MIP:
       B     C 
      — × —
       ∅    A,B
    Repertoire:
      +————-+
      | S     P(S)  |
      | ———– |
      | 00    2/3   |
      | 10    0     |
      | 01    0     |
      | 11    1/3   |
      +————-+
    Partitioned repertoire:
      +————-+
      | S     P(S)  |
      | ———– |
      | 00    1/2   |
      | 10    0     |
      | 01    0     |
      | 11    1/2   |
      +————-+



sec:demo-concepts


  §.§.§ Concepts



If the mechanism's has φ_cause > 0 and its has φ_effect > 0, then the mechanism is said to specify a concept. The φ value of the concept as a whole is the minimum of φ_cause and φ_effect.

We can compute the concept depicted in Fig. 9 of <cit.> using the  method, which takes a  and returns a object containing the φ value, the (in the `' attribute), and the (in the `' attribute):



  >>> mechanism = (A,)
  >>> concept = subsystem.concept(mechanism)
  >>> print(concept)
                                                          
             Concept: Mechanism = [A], φ = 1/6            
                                                          
              MIC                         MIE             
  +————————–++————————–+
  |  φ = 1/6                 ||  φ = 1/4                |
  |  Purview = [B, C]        ||  Purview = [B]           |
  |  MIP:                    ||  MIP:                    |
  |     ∅     A              ||    ∅     A              |
  |    — × —             ||    — × —             |
  |     B     C              ||     B     ∅              |
  |  Repertoire:             ||  Repertoire:             |
  |    +————-+       ||    +————+        |
  |    | S     P(S)  |       ||    | S    P(S)  |        |
  |    | ———– |       ||    | ———- |        |
  |    | 00    0     |       ||    | 0    1/2   |        |
  |    | 10    1/3   |       ||    | 1    1/2   |        |
  |    | 01    1/3   |       ||    +————+        |
  |    | 11    1/3   |       ||  Partitioned repertoire: |
  |    +————-+       ||    +————+        |
  |  Partitioned repertoire: ||    | S    P(S)  |        |
  |    +————-+       ||    | ———- |        |
  |    | S     P(S)  |       ||    | 0    3/4   |        |
  |    | ———– |       ||    | 1    1/4   |        |
  |    | 00    1/6   |       ||    +————+        |
  |    | 10    1/6   |       |+————————–+
  |    | 01    1/3   |       |
  |    | 11    1/3   |       |
  |    +————-+       |
  +————————–+



Note that in PyPhi, the repertoires are distributions over purview states, rather than system states. Occasionally it is more convenient to represent repertoires as distributions over the entire system. This can be done with the  and  methods of the object, which assume the unconstrained (maximum-entropy) distribution over the states of non-purview nodes:



  >>> full_cr = concept.expand_cause_repertoire()
  >>> print(pyphi.distribution.flatten(full_cr))
  [ 0.          0.          0.16666667  0.16666667  0.16666667  0.16666667
    0.16666667  0.16666667]
  >>> full_er = concept.expand_effect_repertoire()
  >>> print(pyphi.distribution.flatten(full_er))
  [ 0.0625  0.1875  0.0625  0.1875  0.0625  0.1875  0.0625  0.1875]



Also note that  will return a object when φ = 0 even though these are not concepts, strictly speaking. For convenience,  evaluates to  if φ > 0 and  otherwise.

sec:demo-ces


  §.§.§ Cause-effect structures (system-level information)



The next step is to compute the , the set of all concepts specified by the subsystem. The characterizes all of the causal constraints that are intrinsic to a physical system. This is implemented by the  function, which simply calls  for every mechanism M ∈𝒫(S), where 𝒫(S) is the power set of subsystem nodes. It returns a object containing those for which φ > 0.

We see that every mechanism in 𝒫(S) except for AC specifies a concept, as described in Fig. 10 of <cit.>: 



  >>> ces = pyphi.compute.ces(subsystem)
  >>> print(ces.labeled_mechanisms)
  (['A'], ['B'], ['C'], ['A', 'B'], ['B', 'C'], ['A', 'B', 'C'])



sec:demo-ices


  §.§.§ Irreducible cause-effect structures (system-level integration)



At this point, the irreducibility of the subsystem's is evaluated by applying the integration postulate at the system level. As with integration at the mechanism level, the idea is to measure the difference made by each partition and then take the minimal value as the irreducibility of the subsystem.

We begin by performing a system cut. Graphically, the subsystem is partitioned into two parts and the edges going from one part to the other are cut, rendering them causally ineffective. This is implemented as an operation on the as follows: Let E_ denote the set of directed edges in the subsystem that are to be cut, where each edge e ∈ E_ has a source node a and a target node b. For each edge, we modify the individual of node b (<ref>) by marginalizing over the states of a at t. The resulting specifies the function implemented by b with the causal influence of a removed. We then combine the modified node s to recover the full of the partitioned subsystem. Finally, we recalculate the of the subsystem with this modified (the partitioned CES).

The irreducibility of a with respect to a partition is the distance between the unpartitioned and partitioned s (calculated with ; several distances are supported; see sec:config). This distance is evaluated for every partition, and the minimum value across all partitions is the subsystem's integrated information Φ, which measures the extent to which the specified by the subsystem is irreducible to the under the minimal partition.

This procedure is implemented by the function, which returns a object (<ref>). We can verify that the Φ value of the example system in <cit.> is 1.92 and the minimal partition is that which removes the causal connections from AB to C:



  >>> sia = pyphi.compute.sia(subsystem)
  >>> print(sia.phi)
  1.916665
  >>> print(sia.cut)
  Cut [0, 1] –/ /–> [2]



sec:demo-complexes


  §.§.§ Complexes (system-level exclusion)


The final step in unfolding the of the system is to apply the postulate of exclusion at the system level. We compute the  of each subset of the network, considered as a subsystem (that is, fixing the external nodes as background conditions), and find the with maximal Φ, called the maximally-irreducible cause-effect structure () of the system. The subsystem giving rise to it is called the major complex; any overlapping subsets with lower Φ are excluded. Non-overlapping subsets may be further analyzed to find additional complexes within the system.

In this example, we find that the whole system ABC is the system's major complex, and all proper subsets are excluded: 



  >>> state = (1, 0, 0)
  >>> major_complex = pyphi.compute.major_complex(network, state)
  >>> print(major_complex.subsystem)
  Subsystem(A, B, C)



Note that since is a function of the , rather than a particular , it is necessary to specify the state in which the system should be analyzed.

sec:design


§ DESIGN AND IMPLEMENTATION



PyPhi was designed to be easy to use in interactive, exploratory research settings while nonetheless remaining suitable for use in large-scale simulations or as a component in larger applications. It was also designed to be efficient, given the high computational complexity of the algorithms in . Here we describe some implementation details and optimizations used in the software.

sec:tpm


 §.§ Representation of the and probability distributions



PyPhi supports three different representations: 2-dimensional state-by-node, multidimensional state-by-node, and state-by-state. The state-by-node form is the canonical representation in PyPhi, with the 2-dimensional form used for input and visualization and the multidimensional form used for internal computation. The state-by-state representation is given as an input option for those accustomed to this more general form. If the is given in state-by-state form, PyPhi will raise an error if it does not satisfy <ref> (conditional independence).

sec:2d-sbn-form


  §.§.§ 2-dimensional state-by-node form



A in state-by-node form is a matrix where the entry (i, j) gives the probability that the j^th node will be ON at t+1 if the system is in the i^th state at t. This representation has the advantage of being more compact than the state-by-state form, with 2^n  n entries instead of 2^n  2^n, where n is the number of nodes. Note that the admits this representation because in PyPhi the nodes are binary; both (N_t+1 = ON) and (N_t+1 = OFF) can be specified by a single entry, in our case (N_t+1 = ON), since the two probabilities must sum to 1.

Because the possible system states at t are represented implicitly as row indices in 2-dimensional s, there must be an implicit mapping from states to indices. In PyPhi this mapping is achieved by listing the state tuples in lexicographical order and then interpreting them as binary numbers where the state of the first node corresponds to the least-significant bit, so that the state  is mapped to the row with index 8 (the ninth row, since Python uses zero-based indexing <cit.>). Designating the first node's state as the least-significant bit is analogous to choosing the little-endian convention in organizing computer memory. This convention is preferable because the mapping is stable under the inclusion of new nodes: including another node in a subsystem only requires concatenating new rows and a new column to its rather than interleaving them. Note that this is opposite convention to that used in writing numbers in positional notation; care must be taken when converting between states and indices and between different representations (the  module provides convenience functions for these purposes).

sec:nd-form


  §.§.§ Multidimensional state-by-node form



When a state-by-state is provided to PyPhi by the user, it is converted to state-by-node form and the conditional independence property (<ref>) is checked. Note that any in state-by-node form necessarily satisfies <ref>. For internal computations, the is then reshaped so that it has n+1 dimensions rather than two: the first n dimensions correspond to the states of each of the n nodes at t, while the last dimension corresponds to the probabilities of each node being ON at t+1. In other words, the indices of the rows (current states) in the 2-dimensional are “unraveled” into n dimensions, with the i^th dimension indexed by the i^th bit of the 2-dimensional row index according to the little-endian convention. Because the is stored in a NumPy array, this multidimensional form allows us to take advantage of NumPy indexing <cit.> and use a state tuple as an index directly, without converting it to an integer index:



  >>> state = (0, 1, 1)
  >>> print(tpm[state])
  [ 1.    0.25  0.75]



The first entry of this array signifies that if the state of the system is  at t, then the probability of the first node N_0 being ON at t+1 is (N_0, t+1 = ON) = 1. Similarly, the second entry means (N_1, t+1 = ON) = 0.25 and the third entry means (N_2, t+1 = ON) = 0.75. 

Most importantly, the multidimensional representation simplifies the calculation of marginal and conditional distributions and cause/effect repertoires, because it allows efficient “broadcasting” <cit.> of probabilities when multiplying distributions. Specifically, the Python multiplication operator `' acts as the tensor product when the operands are NumPy arrays  and  of equal dimensionality such that for each dimension , either  or .

sec:repertoires


 §.§ Calculation of cause/effect repertoires from the 



The cause and effect repertoires of a mechanism over a purview describe how the mechanism nodes in a particular state at t constrain the possible states of the purview nodes at t-1 and t+1, respectively. Here we describe how they are derived from the in PyPhi.



  §.§.§ The effect repertoire


We begin with the simplest case: calculating the effect repertoire of a mechanism M ⊆ S over a purview consisting of a single element P_i ∈ S. This is defined as a conditional probability distribution over states of the purview element at t+1 given the current state of the mechanism,

    (M, P_i)   (P_i,t+1| M_t = m_t).

It is derived from the by conditioning on the state of the mechanism elements, marginalizing over the states of non-purview elements P' = S ∖ P_i (these states correspond to columns in the state-by-state ), and marginalizing over the states of non-mechanism elements M' = S ∖ M (these correspond to rows):

    (P_i,t+1| M_t = m_t)  = 
    1|Ω_M'| ∑_m'_t ∈ Ω_M' 1|Ω_P'| ∑_p'_t+1 ∈ Ω_P' (P_i,t+1,  p'_t+1| M = m_t,  M' = m'_t).


This operation is implemented in PyPhi by several subroutines. First, in a pre-processing step performed when the  object is created, a  object is created for each element in the subsystem. Each  contains its own individual , extracted from the subsystem's ; this is a 2^s  2 matrix where s is the number of the node's parents and the entry (i, j) gives the probability that the node is in state j ( or ) at t + 1 given that its parents are in state i at t. This node TPM is represented internally in multidimensional state-by-node form as usual, with singleton dimensions for those subsystem elements that are not parents of the node. The effect repertoire is then calculated by conditioning the purview node's on the state of the mechanism nodes that are also parents of the purview node, via the  function, and marginalizing out non-mechanism nodes, with .

In cases where there are mechanism nodes that are not parents of the purview node, the resulting array is multiplied by an array of ones that has the desired shape (dimensions of size two for each mechanism node, and singleton dimensions for each non-mechanism node). Because of NumPy's broadcasting feature, this step is equivalent to taking the tensor product of the array with the maximum-entropy distribution over mechanism nodes that are not parents, so that the final result is a distribution over all mechanism nodes, as desired.

The effect repertoire over a purview of more than one element is given by the tensor product of the effect repertories over each individual purview element,

    (M, P)   ⊗_P_i  ∈  P(M, P_i).

Again, because PyPhi s and repertoires are represented as tensors (multidimensional arrays), with each dimension corresponding to a node, the NumPy multiplication operator between distributions over different nodes is equivalent to the tensor product. Thus the effect repertoire over an arbitrary purview is trivially implemented by taking the product of the effect repertoires over each purview node with .



  §.§.§ The cause repertoire


The cause repertoire of a single-element mechanism M_i ∈ S over a purview P ⊆ S is defined as a conditional probability distribution over the states of the purview at t-1 given the current state of the mechanism,

    (M_i, P)   (P_t-1| M_i,t = m_i,t).

As with the effect repertoire, it is obtained by conditioning and marginalizing the . However, because the gives conditional probabilities of states at t+1 given the state at t, Bayes' rule is first applied to express the cause repertoire in terms of a conditional distribution over states at t - 1 given the state at t, 

    (P_t-1| M_i,t = m_i,t)
       = (m_i,t| P_t-1)  (P_t-1) (m_i,t) .

where the marginal distribution (P_t-1) over previous states is the uniform distribution. In this way, the analysis captures how a mechanism in a state constrains a purview without being biased by whether certain states arise more frequently than others in the dynamical evolution of the system <cit.>. Then the cause repertoire can be calculated by marginalizing over the states of non-mechanism elements M' = S ∖ M_i (now corresponding to columns in the state-by-state ) and non-purview elements P' = S ∖ P (now corresponding to rows),

    (m_i,t| P_t-1)  (P_t-1) (m_i,t) 
        = ( 1/|Ω_P'| ∑_p'_t-1 ∈ Ω_P' 1/|Ω_M'| ∑_m'_t ∈ Ω_M' (m_i,t,  m'_t | P_t-1,  P'_t-1 = p'_t-1) ) (P_t-1) 1/|Ω_M'| ∑_m'_t ∈ Ω_M' (m_i,t,  m'_t) 
        = ( 1/|Ω_P'| ∑_p'_t-1 ∈ Ω_P' ∑_m'_t ∈ Ω_M' (m_t,  m'_t | P_t-1,  P'_t-1 = p'_t-1) ) (P_t-1) ∑_m'_t ∈ Ω_M' (m_i,t,  m'_t) .
 

In PyPhi, the “backward” conditional probabilities (m_i,t| P_t-1) for a single mechanism node are obtained by indexing into the last dimension of the node's with the state m_i,t and then marginalizing out non-purview nodes via . As with the effect repertoire, the resulting array is then multiplied by an array of ones with the desired shape in order to obtain a distribution over the entire purview. Finally, because in this case the probabilities were obtained from columns of the , which do not necessarily sum to 1, the distribution is normalized with .

The cause repertoire of a mechanism with multiple elements is the normalized tensor product of the cause repertoires of each individual mechanism element, 

    (M, P)  = 1/K ⊗_M_i  ∈  M(M_i, P),
 
where 

    K  = ∑_p_t-1 ∈ Ω_P ∏_m_i,t ∈ Ω_M(P_t-1 = p_t-1| M_i,t = m_i,t)
 
is a normalization factor that ensures that the distribution sums to 1. This is implemented in PyPhi via  and . For a more complete illustration of these procedures, see sup:presentation.

sec:organization


 §.§ Code organization and interface design



The postulates of induce a natural hierarchy of computations <cit.>, and PyPhi's implementation mirrors this hierarchy by using object-oriented programming (<ref>) and factoring the computations into compositions of separate functions where possible. One advantage of this approach is that each level of the computation can be performed independently of the higher levels; for example, if one were interested only in the of certain mechanisms rather than the full , then one could simply call  on those mechanisms instead of calling and extracting them from the resulting object (this is especially important in the case of large systems where the full calculation is infeasible). Separating the calculation into many subroutines and exposing them to the user also has the advantage that they can be easily composed to implement functionality that is not already built-in.



sec:config


 §.§ Configuration



Many aspects of PyPhi's behavior may be configured via the  object. The configuration can be specified in a YAML file <cit.>; an https://github.com/wmayner/pyphi/blob/master/pyphi_config.ymlexample is available in the GitHub repository. When PyPhi is imported, it checks the current directory for a file named  and automatically loads it if it exists. Configuration settings can also be loaded on the fly from an arbitrary file with the  function.

Alternatively,  can load configuration settings from a Python dictionary. Many settings can also be changed by directly assigning them a new value.

Default settings are used if no configuration is provided. A full description of the available settings and their default values is available in the https://pyphi.readthedocs.io/page/configuration“Configuration” section of the online documentation. 

sec:optimizations


 §.§ Optimizations and approximations



Here we describe various optimizations and approximations used by the software to reduce the complexity of the calculations (see sec:limitations). Memoization and caching optimizations are described in sup:caching.

sec:connectivity


  §.§.§ Connectivity optimizations



As mentioned in sec:input, providing connectivity information explicitly with a can greatly reduce the time complexity of the computations, because in certain cases missing connections imply reducibility a priori.

For example, at the system level, if the subsystem is not strongly connected then Φ is necessarily zero. This is because a unidirectional cut between one system part and the rest can always be found that will not actually remove any edges, so the s with and without the cut will be identical (see sup:strong-connectivity for proof). Accordingly, PyPhi immediately excludes these subsystems when finding the major complex of a system.

Similarly, at the mechanism level, PyPhi uses the to exclude certain purviews from consideration when computing a or by efficiently determining that repertoires over those purviews are reducible without needing to explicitly compute them. Suppose there are two sets of nodes X and Y for which there exist partitions X = (X_1,  X_2) and Y = (Y_1,  Y_2) such that there are no edges from X_1 to Y_2 and no edges from X_2 to Y_1. Then the effect repertoire of mechanism X over purview Y can be factored as 

    (X, Y)  = 
    (X_1, Y_1)  ⊗ (X_2, Y_2),
 
and the cause repertoire of mechanism Y over purview X can be factored as 

    (Y, X)  = 
    (Y_1, X_1)  ⊗ (Y_2, X_2).
 
Thus in these cases the mechanism is reducible for that purview and φ = 0 (see sup:block-factorable for proof).

sec:emd


  §.§.§ Analytical solution to the earth mover's distance



One of the repertoire distances available in PyPhi is the earth mover's distance (), with the Hamming distance as the ground metric. Computing the between repertoires is a costly operation, with time complexity O(n 2^3n) where n is the number of nodes in the purview <cit.>. However, when comparing effect repertoires, PyPhi exploits a theorem that states that the between two distributions p and q over multiple nodes is the sum of the s between the marginal distributions over each individual node, if p and q are independent. This analytical solution has time complexity O(n), a significant improvement over the general algorithm (note that this estimate does not include the cost of computing the marginals, which already have been computed to obtain the repertoires). By the conditional independence property (Eq. <ref>), the conditions of the theorem hold for calculations between effect repertoires, and thus the analytical solution can be used for half of all repertoire calculations performed in the analysis. The theorem is formally stated and proved in sup:emd.

sec:approximations


  §.§.§ Approximations



Currently, two approximate methods of computing Φ are available. These can be used via settings in the PyPhi configuration file (they are disabled by default):


enumi.

  *  (the “cut one” approximation), and

  *  (the “no new concepts” approximation).


In both cases, the complexity of the calculation is greatly reduced by replacing the optimal partitioned by an approximate solution. The system's Φ value is then computed as usual as the difference between the unpartitioned and the approximate partitioned .



  
*Cut one. 
The “cut one” approximation reduces the scope of the search for the over possible system cuts. Instead of evaluating the partitioned for each of the 2^n unidirectional bipartitions of the system, only those 2n bipartitions are evaluated that sever the edges from a single node to the rest of the network or vice versa. Since the goal is to find the minimal Φ value across all possible partitions, the “cut one” approximation provides an upper bound on the exact Φ value of the system.



  
*No new concepts. 
For most choices of mechanism partitioning schemes and distance measures, it is possible that the of the partitioned system contains concepts that are reducible in the unpartitioned system and thus not part of the unpartitioned . For this reason, PyPhi by default computes the partitioned from scratch from the partitioned . Under the “no new concepts” approximation, such new concepts are ignored. Instead of repeating the entire computation for each system partition, which requires reevaluating all possible candidate mechanisms for irreducibility, only those mechanisms are taken into account that already specify concepts in the unpartitioned . In many types of systems, new concepts due to the partition are rare. Approximations using the “no new concepts” option are thus often accurate. Note, however, that this approximation provides neither a theoretical upper nor lower bound on the exact Φ value of the system.

sec:limitations


 §.§ Limitations



PyPhi's main limitation is that the algorithm is exponential time in the number of nodes, O(n 53^n). This is because the number of states, subsystems, mechanisms, purviews, and partitions that must be considered each grows exponentially in the size of the system. This limits the size of systems that can be practically analyzed to ~10–12 nodes. For example, calculating the major complex of systems of three, five, and seven stochastic majority gates, connected in a circular chain of bidirectional edges, takes ~1 s, ~16 s, and ~2.75 h respectively (parallel evaluation of system cuts, 32×3.1GHz CPU cores). Using the “cut one” approximation, these calculations take ~1 s, ~12 s, and ~0.63 h. In practice, actual execution times are substantially variable and depend on the specific network under analysis, because network structure determines the effectiveness of the optimizations discussed above.

Another limitation is that the analysis can only be meaningfully applied to a system that is Markovian and satisfies the conditional independence property. These are reasonable assumptions for the intended use case of the software: analyzing a causal derived using the calculus of perturbations <cit.>. However, there is no guarantee that these assumptions will be valid in other circumstances, such as s derived from observed time series (, EEG recordings). Whether a system has the Markov property and conditional independence property should be carefully checked before applying the software in novel contexts.

sec:availability


§ AVAILABILITY AND FUTURE DIRECTIONS



PyPhi can be installed with Python's package manager via the command `' on Linux and macOS systems equipped with Python 3.4 or higher. It is open-source and licensed under the GNU General Public License v3.0. The source code is version-controlled with  and hosted in a public repository on GitHub at . Comprehensive and continually-updated documentation is available online at . The  mailing list can be joined at . A web-based graphical interface to the software is available at .

Several additional features are in development and will be released in future versions. These include a module for calculating Φ over multiple spatial and temporal scales, as theoretically required by the exclusion postulate (in the current version, the  is assumed to represent the system at the spatiotemporal timescale at which Φ is maximized <cit.>), and a module implementing a calculus for “actual causation” as formulated in <cit.> (preliminary versions of these modules are available in the current release). The software will also be updated to reflect developments in and further optimizations in the algorithm.




§ ACKNOWLEDGMENTS


We thank Andrew Haun, Leonardo Barbosa, Sabrina Streipert, and Erik Hoel for their valuable feedback as early users of the software.

WGPM, WM, LA, RM and GT received funding from the Templeton World Charities Foundbtion (Grant #TWCF 0067/AB41). WGPM and GF were also supported by National Research Service Award (NRSA) T32 GM007507.

10

tononi2016integrated
Tononi G, Boly M, Massimini M, Koch C.
Integrated information theory: from consciousness to its physical
  substrate.
Nature Reviews Neuroscience. 2016;17(7):450–461.
https://doi.org/10.1038/nrn.2016.44doi:10.1038/nrn.2016.44.

tononi2015integrated
Tononi G.
Integrated information theory.
Scholarpedia. 2015;10(1):4164.
https://doi.org/10.4249/scholarpedia.4164doi:10.4249/scholarpedia.4164.

oizumi2014phenomenology
Oizumi M, Albantakis L, Tononi G.
From the Phenomenology to the Mechanisms of Consciousness: Integrated
  Information Theory 3.0.
PLoS computational biology. 2014;10(5):e1003588.
https://doi.org/10.1371/journal.pcbi.1003588doi:10.1371/journal.pcbi.1003588.

balduzzi2008integrated
Balduzzi D, Tononi G.
Integrated information in discrete dynamical systems: motivation and
  theoretical framework.
PLoS computational biology. 2008;4(6):e1000091.
https://doi.org/10.1371/journal.pcbi.1000091doi:10.1371/journal.pcbi.1000091.

tononi2004information
Tononi G.
An information integration theory of consciousness.
BMC neuroscience. 2004;5(1):42.
https://doi.org/10.1186/1471-2202-5-42doi:10.1186/1471-2202-5-42.

albantakis2015intrinsic
Albantakis L, Tononi G.
The Intrinsic Cause-Effect Power of Discrete Dynamical Systems—From
  Elementary Cellular Automata to Adapting Animats.
Entropy. 2015;17(8):5472.
https://doi.org/10.3390/e17085472doi:10.3390/e17085472.

albantakis2014evolution
Albantakis L, Hintze A, Koch C, Adami C, Tononi G.
Evolution of Integrated Causal Structures in Animats Exposed to
  Environments of Increasing Complexity.
PLoS computational biology. 2014;10(12):e1003966.
https://doi.org/10.1371/journal.pcbi.1003966doi:10.1371/journal.pcbi.1003966.

oizumi2016unified
Oizumi M, Tsuchiya N, Amari S.
Unified framework for information integration based on information
  geometry.
Proceedings of the National Academy of Sciences.
  2016;113(51):14817–14822.
https://doi.org/10.1073/pnas.1603583113doi:10.1073/pnas.1603583113.

albantakis2017automata
Albantakis L, Tononi G.
Chapter 14: Automata and Animats.
From Matter to Life: Information and Causality. 2017; p. 334.
https://doi.org/10.1017/9781316584200.014doi:10.1017/9781316584200.014.

hoel2016can
Hoel EP, Albantakis L, Marshall W, Tononi G.
Can the macro beat the micro? Integrated information across
  spatiotemporal scales.
Neuroscience of Consciousness. 2016;2016(1):niw012.
https://doi.org/10.1093/nc/niw012doi:10.1093/nc/niw012.

hoel2013quantifying
Hoel EP, Albantakis L, Tononi G.
Quantifying causal emergence shows that macro can beat micro.
Proceedings of the National Academy of Sciences. 2013;110(49):19790–19795.
https://doi.org/10.1073/pnas.1314922110doi:10.1073/pnas.1314922110.

marshall2016black
Marshall W, Albantakis L, Tononi G.
Black-boxing and cause-effect power.
PLoS computational biology. 2018;14(4):e1006114.
doi:10.1371/journal.pcbi.1006114.

marshall2017how
Marshall W, Kim H, Walker SI, Tononi G, Albantakis L.
How causal analysis can reveal autonomy in models of biological
  systems.
Philosophical Transactions of the Royal Society of London A:
  Mathematical, Physical and Engineering Sciences. 2017;375(2109).
https://doi.org/10.1098/rsta.2016.0358doi:10.1098/rsta.2016.0358.

marshall2016integrated
Marshall W, Gomez-Ramirez J, Tononi G.
Integrated Information and State Differentiation.
Frontiers in Psychology. 2016;7:926.
https://doi.org/10.3389/fpsyg.2016.00926doi:10.3389/fpsyg.2016.00926.

albantakis2017actual
Albantakis L, Marshall W, Tononi G.
What caused what? An irreducible account of actual causation.
https://arxiv.org/abs/1708.06716arXiv:1708.06716 [cs.AI]. 2017.

ay2008information
Ay N, Polani D.
Information flows in causal networks.
Advances in complex systems. 2008;11(01):17–41.
https://doi.org/10.1142/S0219525908001465doi:10.1142/S0219525908001465.

pearl2009causality
Pearl J.
Causality.
Cambridge university press; 2009.

dijkstra1982numbering
Dijkstra EW. Why numbering should start at zero (EWD 831); 1982.
Available from:
  <https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html>.

walt2011numpy
Walt Svd, Colbert SC, Varoquaux G.
The NumPy array: a structure for efficient numerical computation.
Computing in Science & Engineering. 2011;13(2):22–30.
https://doi.org/10.1109/MCSE.2011.37doi:10.1109/MCSE.2011.37.

yaml
Ben-Kiki O, Evans C, Net Id. YAML specification; 2009.
Available from: <http://yaml.org/spec/>.

pele2009fast
Pele O, Werman M.
Fast and robust earth mover's distances.
In: 2009 IEEE 12th International Conference on Computer Vision.
  IEEE; 2009. p. 460–467.
https://doi.org/10.1109/ICCV.2009.5459199doi:10.1109/ICCV.2009.5459199.






§ SUPPORTING INFORMATION






  
*S1 Calculating Φ.
Illustration of the algorithm.



  
*S2 Appendix.
Memoization and caching optimizations.



  
*S3 Appendix.
Proof of the strong connectivity optimization.



  
*S4 Appendix.
Proof of the block-factorable optimization.



  
*S5 Appendix.
Proof of an analytical solution to the between effect repertoires.



/sup2last


 §.§ S2 Appendix



  §.§.§ Memoization and caching optimizations.


During the course of computing a , several functions in PyPhi are called multiple times with the same input. For example, calculating  and  both require calculating . Similarly,  is both the unpartitioned repertoire of the candidate MIP of mechanism A over purview BC and the first term in the expression for the partitioned repertoire of the candidate MIP of mechanism AB over purview ABC under the partition 

    A/BC×B/A.

In such situations, a natural optimization technique to reduce expensive re-computation of these functions is memoization: when a function is computed for a given input, the input-output pair is stored in a lookup table; if the function is called again with that input, the output is simply looked up in the table and returned, without computing the function again.

In PyPhi, memoization is applied to various functions at different levels of the algorithm, listed here:

  
  *  and , the un-normalized cause repertoire of a single-node mechanism and the effect repertoire over a single-node purview, respectively (note that these functions are meant to be called internally by other PyPhi functions and not by the user, as indicated by the leading underscore);
  
  *  and , the cause and effect repertoires of arbitrary mechanism-purview pairs;
  
  *  and , the and of a mechanism;
  
  * , the purviews which are not necessarily reducible based on the ;
  
  * Various utility functions such as ; and
  
  * , the full analysis of a .


At the highest level, is memoized such that the object is stored persistently on the filesystem, rather than in memory, in a directory named  (which is automatically created in the directory where the Python session was started). This means that the objects are automatically saved across Python sessions and can be quickly retrieved simply by running the same code, which is useful for interactive, exploratory work. This behavior can be controlled with the  configuration setting. Note, however, that this feature is primarily for convenience and is not intended to replace explicit data management. Additionally, care must be taken to erase or disable the cache when upgrading to new versions of PyPhi, as changes to the algorithm may invalidate previously computed output. A final caveat: because the results are stored on the filesystem, they can accumulate and occupy a large amount of disk space if the  directory is not periodically removed.




/sup3last


 §.§ S3 Appendix



  §.§.§ Proof of the strong connectivity optimization.


[strong connectivity]
If G = (V, E) is a directed graph that is not strongly connected, then Φ(G) = 0.




Since G is not strongly connected, G contains n ≥ 2 strongly connected components, which we arbitrarily label 

    G_1, G_2, …, G_n  =  (V_1, E_1), (V_2, E_2), …, (V_n, E_n).

Let E_j,k denote the set of directed edges from nodes in component G_j to those in component G_k, {(a, b) ∈ E | a ∈ V_j  and  b ∈ V_k}.

Consider the first component G_1. For every other component G_i,  i ≠ 1, either E_1,i = ∅ or E_i,1 = ∅, because otherwise G_1 and G_i would not be distinct connected components. Now let G_1 be the indices of components that receive no edges from G_1, {i ∈1,…,n| E_1,i = ∅}. Then let Y be the union of the nodes in these components, 
    Y = ⋃_i ∈ G_1 V_i ,
 and let X = V ∖ Y. Then X and Y form a partition of V such that there are no edges from any nodes in X to any nodes in Y.

Now consider the system cut c(X, Y) that cuts edges from nodes in X to nodes in Y. Because there are no such edges, none of the node s are changed after applying the cut, and thus the subsystem is unchanged because it is the product of the node s. Since the cause-effect structure of a system is a function of the subsystem's , the cause-effect structure C_c(X,Y) of the partitioned subsystem and the cause-effect structure C of the unpartitioned subsystem are identical.

Let Φ_c(X,Y)(G) be the Φ value of G with respect to c(X,Y). By definition, this is the  between C and C_c(X,Y). The  function is a metric, so since C_c(X,Y) = C we have that 

    (C, C_c(X,Y))  =  0
 
by non-negativity of metrics, and thus Φ_c(X,Y)(G) = 0. Now, by definition, 
    Φ(G)  = min_c  ∈ ℂ Φ_c(G)
 where ℂ is the set of all system cuts. Since Φ_c(X,Y)(G) = 0, by non-negativity we have Φ(G) = 0.






/sup4last


 §.§ S4 Appendix



  §.§.§ Proof of the block-factorable optimization.


[block diagonal]
An n  m matrix 𝐀_n,m is said to be block diagonal if it can be written as 

    𝐀_n,m = [l]
            𝐁_s,t   0_s, m - t
    0_n - s, t   𝐂_n - s, m - t,
 
where 1 ≤ s < n and 1 ≤ t < m.


We consider sub-matrices of the connectivity matrix  of the form (π_row, π_col), where 

    [(π_row, π_col)]_i, j = []_π_row(i), π_col(j).


[block factorable]
A mechanism-purview pair (M, P) is said to be block factorable if there exists a permutation π_M of the mechanism indices and a permutation π_P of the purview indices such that (π_M, π_P) is block diagonal (for effect purviews) or (π_P, π_M) is block diagonal (for cause purviews).


[block reducibility]
If a mechanism-purview pair is block factorable, then it is reducible (φ = 0).




Consider a mechanism M constituted of n elements and a purview P constituted of m elements. Assume without loss of generality that P is an effect purview. Since (M, P) is block factorable, there exist permutations π_M and π_P such that (π_M, π_P) is block diagonal, i.e., 

    (π_M, π_P)  = [l]
          𝐁_s,t   0_s, m - t
    0_n - s, t   𝐂_n - s, m - t,
 
where 1 ≤ s < n and 1 ≤ t < m.

We define a mechanism-purview partition 

    c   M_1/P_1×M_2/P_2
 
that cuts edges from M_1 to P_2 and from M_2 to P_1, where 

  M_1     =  {      π_M(i)    |     1         ≤     i    <     s      +  1      } 

  M_2     =  {      π_M(i)    |     s + 1     ≤     i    <     n      +  1      } 

  P_1     =  {      π_P(i)    |     1         ≤     i    <     t      +  1      } 

  P_2     =  {      π_P(i)    |     t + 1     ≤     i    <     m      +  1      }
 
Note that [(π_M, π_P)]_i,j = 0 if either i ∈ M_1 and j ∈ P_2 or i ∈ M_2 and j ∈ P_1. Thus there are no edges cut by c, and it leaves the subsystem's unchanged. Since the effect repertoire of a mechanism-purview combination is a function of the subsystem's , the unpartitioned effect repertoire, (M, P) and the partitioned repertoire _c(M, P) are identical.

By definition, φ_c(M, P) is the distance between (M, P) and _c(M, P), so φ_c(M, P) = 0. Now, by definition, 
    φ(M, P) = min_p  ∈ ℙ φ_p(M, P),
 where ℙ is the set of all partitions of (M, P). Since φ_c(M, P) = 0, by the non-negativity of metrics we have φ(M, P) = 0. 






/sup5last


 §.§ S5 Appendix



  §.§.§ Proof of an analytical solution to the between effect repertoires.


[analytical ]
Consider two random variables X_1, X_2 with corresponding state
spaces Ω_1, Ω_2 and an `additive' metric D, 

    D((i_1, i_2),  (j_1, j_2))  = 
        D(i_1, j_1) + D(i_2, j_2)   ∀ (i_1, i_2) and (j_1, j_2) ∈Ω_1 ×Ω_2.
 
Let p_1 and q_1 be two probability distributions on X_1, and let p_2 and q_2 be probability distributions on X_2. If X_1 and X_2 are independent, then the between the joint distributions p = p_1p_2 and q = q_1q_2, with D as the ground metric, is equal to the sum of the s between the marginal distributions: 

    (p, q)  = (p_1, q_1) + (p_2, q_2).





First, we demonstrate that 

    (p, q)  ≤ (p_1, q_1) + (p_2, q_2).

To do this, we define a third probability distribution as an intermediate point, 

    r    q_1p_2.

We define the following flow from p to r, 

    f_p,r(i_1, i_2, j_1, j_2)   
          p_2(i_2)f_p_1,q_1^*(i_1, j_1)    if i_2 = j_2 
    
          0                                 ,
 
where f^*_p_1,q_1 is the optimal flow for the between p_1 and q_1. With this flow, we have 

    (p, r)     ≤ ∑_i_1, i_2, j_1, j_2 f_p,r(i_1, i_2, j_1, j_2)D((i_1, i_2),  (j_1, j_2)) 
       = ∑_i_1, i_2, j_1 p_2(i_2)f^*_p_1,q_1(i_1, j_1)D(i_1, j_1) 
       = ∑_i_2 p_2(i_2) ∑_i_1, j_1 f^*_p_1,q_1(i_1, j_1)D(i_1, j_1) 
       = (p_1, q_1)
 
We next define a flow from r to q, 

    f_r,q(i_1, i_2, j_1, j_2)   
          q_1(i_1)f_p_2,q_2^*(i_2, j_2)    if i_1 = j_1 
     
          0                                 ,
 
where f^*_p_2,q_2 is the optimal flow for the between p_2 and q_2. With this flow, we have 

    (r, q)      ≤ ∑_i_1, i_2, j_1, j_2 f_r,q(i_1, i_2, j_1, j_2)D((i_1, i_2),  (j_1, j_2)) 
       = ∑_i_1, i_2, j_2 q_1(i_1)f^*_p_2,q_2(i_2, j_2)D(i_2, j_2) 
       = ∑_i_1 q_1(i_1) ∑_i_2, j_2 f^*_p_2,q_2(i_2, j_2)D(i_2, j_2) 
       = (p_2, q_2)
 
Then using the triangle inequality (the is a metric), we have 

    (p, q)  ≤ (p, r) + (r, q)  ≤ (p_1, q_1) + (p_2, q_2).
 
To complete the proof, we next demonstrate that 

    (p, q)  ≥ (p_1, q_1) + (p_2, q_2).
 
If f_p,q^* is the optimal flow for (p, q), then define a flow between p_1 and q_1, 

    f_1(i_1,j_1)   ∑_i_2, j_2 f_p,q^*(i_1, i_2, j_1, j_2),
 
and a flow between p_2 and q_2 

    f_2(i_2, j_2)   ∑_i_1, j_1 f_p,q^*(i_1, i_2, j_1, j_2).
 
Then using the additive property of the ground metric D, 

    (p, q) 
          = ∑_i_1, i_2, j_1, j_2 f_p,q^*(i_1, i_2, j_1, j_2)D((i_1, i_2),  (j_1, j_2)) 
        = ∑_i_1, i_2, j_1, j_2 f_p,q^*(i_1, i_2, j_1, j_2)D(i_1, j_1) + ∑_i_1, i_2, j_1, j_2 f_p,q^*(i_1, i_2, j_1, j_2)D(i_2, j_2) 
       
            = ∑_i_1, j_1(∑_i_2, j_2 f_p,q^*(i_1, i_2, j_1, j_2) )D(i_1, j_1) 
     + ∑_i_2, j_2(∑_i_1, j_1 f_p,q^*(i_1, i_2, j_1, j_2) )D(i_2, j_2)
          
        = ∑_i_1, j_1 f_1(i_1,j_1)D(i_1, j_1) + ∑_i_2, j_2 f_2(i_2,j_2)D(i_2, j_2) 
        ≥ (p_1, q_1) + (p_2, q_2).
 
Therefore (p, q) = (p_1, q_1) + (p_2, q_2).



Perhaps it is worth demonstrating that the flows f_1, f_2, f_p,r and f_r,q satisfy the requirements. Consider f_p,r, 

    f_p,r(i_1, i_2, j_1, j_2)  =  
          p_2(i_2)f_p_1,q_1^*(i_1, j_1)    if i_2 = j_2 
    
          0                                  ,
 
where f^*_p_1,q_1 is the optimal flow for the between p_1 and q_1.

Since p_2(i_2) ≥ 0 (probability) and f_p_1,q_1^*(i_1, j_1) ≥ 0 (definition of optimal flow), 

    f_p,r(i_1, i_2, j_1, j_2) ≥ 0.
 
Next, 

    ∑_j_1, j_2 f_p,r(i_1, i_2, j_1, j_2) 
          = ∑_j_1 p_2(i_2)f_p_1,q_1^*(i_1, j_1) 
        =  q_1(i_1)p_2(i_2) 
        =  r(i_1, i_2),

and 

    ∑_i_1, i_2 f_p,r(i_1, i_2, j_1, j_2) 
          = ∑_i_1 p_2(j_2)f_p_1,q_1^*(i_1, j_1) 
        =  q_1(j_1)p_2(i_2) 
        =  r(j_1, j_2).

Finally, 

    ∑_i_1, i_2, j_1, j_2 f_p,r(i_1, i_2, j_1, j_2) 
          = ∑_i_2 p_2(i_2) ∑_i_1, j_1 f_p_1,q_1^*(i_1, j_1) 
        = ∑_i_1, j_1 f_p_1,q_1^*(i_1, j_1) 
        =  1
 
Thus f_p,r satisfies the criteria for a potential flow. The others follow similarly.


