1 Introduction↩︎

There are two notions of redundancy explored in this paper. Within the fault tolerance literature, redundancy describes the desirable property of a system to be able to replicate its component services in the event of a fault [3]. This redundancy is typically implemented through physical or logical copies of the system’s fallible components. Fault tolerance describes the system’s ability to continue to operate despite faults. Classic results from the field prescribe the minimal level of redundancy needed to withstand a given number of faults, for a given task and fault type. For instance, one classic result considers \(n\) independent sensors measuring the same continuous value within a specified interval [4]. Depending on the nature of the faults, it was determined that the centralized algorithm provided could tolerate up to \(f={(n-1)/k}\) faults, where \(k=1,2,3\) for different fault types. Besides sensing, similar results exist for routing and control [3]. Redundancy, in the form of duplicated information assets, provides gaurantees on system performance up to a certain level of failure.

Separately, there is a recurrent interest in information theory to measure the redundant or common information content among multiple variables. Both total correlation [5] and interaction information [1], for instance, are different extensions to mutual information, and can both be considered as measures of redundancy or common randomness among many variables. When one of the variables is designated as a target, this question of redundancy can be interpreted as asking for the interactions among multiple sources regarding the target (see McGill’s original [1]). For three variables \(X,Y,Z\), interaction information takes the form: \[\label{eq:intxn95info} I(X ; Y ; Z) = I(X : Y | Z) - I(X; Y)\tag{1}\] The signed nature of the interaction suggests a rich structure: a positive interaction indicates synergy, while a negative one indicates redundancy among the variables. Interaction information found favor in the theoretical neuroscience community in the 90s/00s, both to measure synergy [6], [7] and redundancy[8] (see also [7]).

The partial information decomposition (PID) was introduced in the last decade to separate redundancy and synergy as distinct informational quantities [2]. Dispensing with the target-source symmetry of interaction information, PID seeks to decompose the information between a collection of source variables \(X_1, X_2, ..., X_n\) and a target \(T\) into those components that can be uniquely, redundantly, and/or synergistically attributed to each source. For instance, when \(n=2\), the so-called bivariate PID decomposes \(I(T;X_1,X_2)\) into four information atoms \(R+S+U_1+U_2\), satisfying: \[\label{eqs:bivariate95PID} \begin{gather} I(T;X_1) = R + U_1 \\ I(T;X_2) = R + U_2 \\ I(T;X_1,X_2) = R + U_1 + U_2 + S \end{gather}\tag{2}\] These equations are known as the PID equations, and these atoms are referred to as redundant (\(R\)), unique (\(U_1\), \(U_2\)), and synergistic (\(S\)) information. By applying the chain rule for mutual information, from (1 ) and (2 a-c) we have that \[\label{eq:intxn95info95PID} I(T; X_1 ; X_2) = S - R\tag{3}\] and thus recover the traditional interpretation of interaction information as measuring a synergy/redundancy trade-off. As (3 ) is an underdetermined system, one of the atoms needs to be specified in order to provide a proper PID definition. Many different PIDs have been proposed, satisfying different, often mutually exclusive axioms [2], [9]–[11].

PID has drawn great interest from researchers at the intersection of neuroscience and complex systems [11]. However, its application outside of biological and social science is less common, largely limited to theoretical machine learning [12], [13]. To our knowledge, there is no technical work examining what PID might be able to suggest about an information system’s robustness from a fault tolerance perspective. This work addresses itself to that question.

In this paper, we will develop a novel PID redundancy function \(I_{\texttt{ft}}\) that quantifies the minimal average information in the presence of crash faults — i.e. faults in which a source unambiguously fails and provides a null signal. We begin by presenting a simple distribution in Section 2 that demonstrates the type of redundancy we would like to capture. In Sec. 3, we review the fundamentals of the partial information decomposition, and introduce relevant notation and terminology. In Sec. 4, we introduce our fault tolerance-inspired PID redudndancy function \(I_{\texttt{ft}}\), and examine its mathematical properties. In the course of demonstrating that \(I_{\texttt{ft}}\) satisfies the common PID axioms from [2], [9], we show an insightful result: there is a order-reversing correspondence between the collections of sources on the PID lattice, over which PID redundancy is measured, and collections of source-fallible realizations of the system — i.e. garbled, fault-prone copies of \(X_1, ..., X_n\).

2 Motivating Example↩︎

Consider a scenario in which we need to know a one-bit variable \(T\) of great importance — say, who is entering a building tonight, an invited or an uninvited guest. The building has two entrances they may enter from: a front and a back. In ideal circumstances, both are monitored by a security camera, and so we have source variables \(X_1\) and \(X_2\) for the front and back cameras, respectively. We code the meanings derived from each video feed using the alphabet \(\mathcal{A}_{X_i} = \{ 1, 2, 3\}\), where \(1\) means that we observe no activity at that entrance, while \(2\) and \(3\) signify the invited and uninvited guest entering, respectively. Our target variable only takes values \(2\) and \(3\), since we have prior information that some visitor will be entering the building. Assuming our observation of the entrances is perfect and the visitor cannot use both entrances, the distribution for the system \((X_1,X_2,T)\) is given by Table (2A).

It is clear that, in this ideal scenario, \(I(T;X_1,X_2) = H(X_1) = 1\), i.e. \((X_1,X_2)\) contain all the information about \(T\). Moreover, each source \(X_i\) gives this full bit of information half of the time, i.e. \(I(T; X_i | X_i \neq 1) = 1\). However, when \(X_i=1\), we have gain no information from it, as \(H(T | X_i=1) = H(T) = 1\). Thus each pairwise MI is given as \(I(T;X_i) = 1/2\).

A

How, then, should we decompose this bit of mutual information into \(R+U_1+U_2+S\), the bivariate PID of this system (2 a-c)? Let’s assume that we want each atom to be non-negative, which would exclude several recent PIDs (e.g. [10], [14], [15]). Since the bivariate PID has one degree of freedom, we may consider the edge cases, corresponding to \(R=1/2\) and \(R=0\), respectively.

First, we might have \(R=S=1/2\), which would in turn imply \(U_1=U_2=0\). This decomposition would indicate that, on average, half a bit of information is redundant between the variables, and half a bit is synergistic. This is the PID that would be given by both the original \(I_{\texttt{min}}\) redundancy-based PID from [2] and the popular \(I_{\texttt{BROJA}}\) PID from [9]. However, does this decomposition make sense? In every realization \((x_1,y_1,t)\), only one of our two predictors is giving any pointwise information regarding the target, while the other is giving none. For instance, for the first two rows of Table 2A, \[\begin{align} \tag{4} \log \frac{p(x_1,t)}{p(x_1)p(t)} &= 0\\ \tag{5} \log \frac{p(x_2,t)}{p(x_2)p(t)} &= 1 \end{align}\] Thus, it is unclear in what sense there is redundancy (or synergy) between the information provided pointwise by these outcomes — at least if we take redundancy to mean information that can be provided reliably by either variable in the event that the other source fails.

Let us instead consider the other option, setting \(R=S=0\), which would in turn give us \(U_1=U_2=1/2\). This tells us that the information provided by \((X_1,X_2)\) about \(T\) can be divided into unique contributions from each, and that none of the information can be considered redundantly provided by both, or synergistically provided by their combination. One possible intuitive justification for this allocation could be that the supports of the pointwise informations given by the left-hand sides of Eqs (4 )-(5 ) are mutually exclusive: our sample space is partitionable between the events “only \(X_1\) is informative” and “only \(X_2\) is informative.”

We favor this latter assignment. Taking our inspiration from the notion of redundancy as used in the fault tolerance literature, we conceptualize ‘redundant information’ as the expected bits that one can guarantee if at least one of the sources is available in every realization — or, equivalently, if we allow that all but one source may fail arbitrarily. With respect to this example, let us consider the garbled source tuple \((\tilde{X}_1, \tilde{X}_2)\), defined by \(\tilde{X}_i = \delta_{1}(X_i) \, X_i\). This new distribution is given by Table 2B. We can imagine this distribution as the worst-case failure mode in every instance, while still guaranteeing that one source will be available. Any decision-maker who has access to \(\tilde{X}_1,\tilde{X}_2\) always has access to the ground-truth of either \(X_1\) or \(X_2\), and thus, we argue, the information redundant to both of them. As we see, \(I(T; \tilde{X}_1,\tilde{X}_2) = 0\). Thus, it stands to reason that \(R=0\).

Our proposed redundancy function \(I_{\texttt{ft}}\) will be defined using such garblings, which we think of as source-fallible instantiations of the underlying ground-truth system. First, we review the partial information decomposition for the general case.

3 Partial Information Decomposition↩︎

PID concerns the system of random variables composed of a target \(T\) and a collection of source or predictor variables \(\boldsymbol{X} = (X_i)_{i=1}^n\). In this work we consider all variables, including the target \(T\) and predictors \(X_i\), to be discrete, with finite alphabets \(\mathcal{A}_T, \mathcal{A}_{X_i} \subset \mathbb{N}\). Note that we exclude ‘0’ from these alphabets, as we will be reserving it for source failure later. This collection of variables forms the base system that represents the ‘ground truth’ of both sensor and target variables, assuming no failures. We refer to this as the base system, to distinguish it from source-fallible systems later.

The PID framework was put forward as a method of decomposing the information in such systems — that is, decomposing the mutual information \(I(T;\boldsymbol{X})\) into constitutive parts attributable to each \(X_i\) and their combinations [2]. This attribution does not follow obviously from pairwise informations \(I(T;X_1)\), since information is non-additive in general.

In the introduction, we introduced the bivariate PID in (2 a-c), in which \(I(T;X_1, X_2)\) is decomposed into atoms \(R+U_1+U_2+S\). These atoms are typically given the following names and interpretations [11]

• Redundant or shared information (\(\boldsymbol{R}\)). The information regarding \(T\) common to both predictors, and in some sense available from either.

• Unique information (\(\boldsymbol{U_i}\)). The information re: \(T\) available from only one of the variables, independently of the other.

• Synergistic or complementary information (\(\boldsymbol{S}\)). The information re: \(T\) that is only available when both variables are known.

PID extends for \(n\geq 2\), though the number of distinct information atoms scales superexponentially. Moreover, the interpretation of higher-order information atoms is not straight-forward. As in the bivariate case above, in which there are 3 independent constraints for 4 unknowns, the PID equations for any \(n\) present us with an underdetermined system. Thus, a definition for one of the quantities must be provided. Typically, this is done by defining a redundancy, synergy, or unique information function, and allowing the other atoms to follow. Ours is a redundancy function \(I_{\texttt{ft}}\), and thus the recursive derivation of the full PID lattice follows exactly as it did for \(I_{\texttt{min}}\) in [2].

We will now review the construction of the PID for an arbitrary number of predictors \(n\). From here on, sources are subcollections of source variables, denoted here \(\boldsymbol{X}_I \subseteq \boldsymbol{X}\) for \(I \subseteq [n]\). PID can be summarized as a framework for measuring the redundancy and synergy among collections of information sources — specifically, their information with respect to the designated target. Note that we will sometimes treat both the full set \(\boldsymbol{X}\) and sources \(\boldsymbol{X}_{I} \subseteq \boldsymbol{X}\) as sets, and other times as tuples/vectors.

For any set \(A\), allow \(\mathcal{P}'(A) = \mathcal{P}(A) \setminus \{ \emptyset \}\) to denote the collection of all non-empty subsets, where \(\mathcal{P}\) is the standard powerset. The collection \(\mathcal{P}'(\boldsymbol{X})\) forms a partially ordered set (‘poset’) under inclusion, denoted \((\mathcal{P}'(\boldsymbol{X}), \subseteq)\). We let \(I(T; \boldsymbol{X}_I)\) denote source-target mutual information. For a fixed base system \(\mathfrak{s}\), \(I(T; \cdot)\) can be thought of as a functional on \(\mathcal{P}'(\boldsymbol{X})\) that is monotonically increasing with respect to the partial order ‘\(\subseteq\).’ PID assigns information value to collections of sources interpretable as redundant, synergistic, and/or contributions from the underlying variables. In order to avoid trivial cases, only the antichains of \((\mathcal{P}'(\boldsymbol{X}), \subseteq)\) are considered. An antichain of a poset is a collection of its elements such that no two are directly comparable. Let \(\mathcal{A}(\boldsymbol{X})\) denote the antichains of \((\mathcal{P}'(\boldsymbol{X}), \subseteq)\), defined formally by \[\begin{align} \nonumber \mathcal{A}(\boldsymbol{X}) \triangleq \bigg\{ & \alpha \in \mathcal{P}'(\mathcal{P}'(\boldsymbol{X})) \; \bigg| \\ & \forall \boldsymbol{A},\boldsymbol{A}' \in \alpha, \; \boldsymbol{A} \neq \boldsymbol{A}' \Rightarrow \boldsymbol{A} \not\subseteq \boldsymbol{A} '\bigg\} \end{align}\] The idea here is that any \(\alpha \in \mathcal{A}(\boldsymbol{X})\) is a collection of sources within which one source will never trivially dominate another by inclusion. For a counter-example, consider that in any system \(\mathfrak{s}\), \((X_1,X_2)\) will always provide no less information pointwise than \(X_1\) alone, and so any sensible redundancy function will identify the redundancy of the non-antichain \(\{ \{X_1, X_2\}, \{X_1\} \}\) with \(I(T;X_1)\). There are multiple partial orderings that may be assigned to the antichains themselves [16]. In PID, the following is used [2]: \[\begin{align} \label{eq:PID95lattice95order} \forall \alpha, \beta \in \mathcal{A}(\boldsymbol{X}), \quad \alpha \preceq \beta \Leftrightarrow \forall \boldsymbol{B} \in \beta, \exists \boldsymbol{A} \in \alpha, \boldsymbol{A} \subseteq \boldsymbol{B} \end{align}\tag{6}\] Although every antichain \(\alpha\) is a set of sets of indexed predictors, we will typically exclude the outer brackets from notation where possible, i.e. \(\{X_1\}\{X_2\}\) in place of \(\{\{X_1\},\{X_2 \}\}\). Moreover, we will let \(\mathop{\mathrm{ind}}(\alpha)\) denote the collection of index sets for \(\alpha\), i.e. \(\mathop{\mathrm{ind}}(\alpha) = \{ I_j \}_j\) when \(\alpha = \{\boldsymbol{X}_{I_j}\}_j\).

A PID function \(\Pi\) assigns an information value to each \(\alpha\) in \(\mathcal{A}(\boldsymbol{X})\), while satisfying the PID equations: \[\forall \boldsymbol{X}_I \in \mathcal{P}'(\boldsymbol{X}), \quad I(T;\boldsymbol{X}_I) = \sum_{\alpha \preceq \{X_I\}} \Pi(\alpha)\] In the bivariate case where \(\boldsymbol{X} = (X_1, X_2)\), these resolve to Eqs. (2 a-c), which in our more general notation take the form: \[\begin{align} I(T;X_1) & = \Pi(\{ X_1\} \{X_2\}) + \Pi(\{ X_1\}) \\ I(T;X_2) &= \Pi(\{ X_1\} \{X_2\}) + \Pi(\{ X_2\}) \\ \nonumber I(T;X_1, X_2) & = \Pi(\{ X_1\} \{X_2\}) + \Pi(\{ X_1\}) \\ & \quad + \Pi(\{ X_2\}) + \Pi(\{ X_1, X_2\}) \end{align}\] We refer the reader to [2] for visualizations of the PID lattice for \(n \leq 3\).

The original [2] and most common approach to defining \(\Pi\) is by first defining a redundancy function \(I_{\cap}\) on \(\mathcal{A}(\boldsymbol{X})\), which measures the redundant information among all the sources in \(\alpha\). The PID function \(\Pi\) is then derived as the Möbius inverse of \(I_{\cap}\): \[\Pi(\alpha) = I_{\cap}(\alpha) - \sum_{\beta \preceq \alpha} I_{\cap}(\beta)\]

It has often be considered desirable for a proposed PID to satisfy a set of properties first mentioned in [2], which have sometimes been referred to as the Williams-Beer (WB) axioms [10].

1. Symmetry. \(I_{\cap}(\boldsymbol{X}_{I_1}, ..., \boldsymbol{X}_{I_k}) = I_{\cap}(\boldsymbol{X}_{I_{\sigma(1)}}, ..., \boldsymbol{X}_{I_{\sigma(k)}})\) for any permutation \(\sigma\).

2. Self-Redundancy. \(I_{\cap}(\boldsymbol{X}_I) = I(T;\boldsymbol{X}_I)\)

3. Monotonicity. \(\alpha \preceq \beta \Rightarrow I_{\cap}(\alpha) \leq I_{\cap}(\beta)\)

The symmetry axiom is usually trivial, and we ignore it in this work. The monotonicity axiom is typically stated in its weaker form \(\alpha \subseteq \beta \Rightarrow I_{\cap}(\alpha) \leq I_{\cap}(\beta)\), since inclusion is a weaker ordering for antichains than that from (6 ). However, the stronger form here was demonstrated in the original PID [2], and follows naturally from our main theorem in the next section.

4 A Measure of Redundant Information in Source-Fallible Systems↩︎

In Sec. 2, we gave an example of the kind of redundancy we aim to quantify. In the fault tolerance literature, redundancy is provided as the number of nodes \(n\) we would need in order to maintain system functionality if we allow for up to \(\ell\) failures [3]. Here, we ask a slightly different question. Suppose we have \(n\) sources of information \(X_1, ..., X_n\), and we want to know whether we may tolerate \(\ell\) source failures while still having enough information regarding \(T\). That determination may be made by considering \(I(T;\tilde{\boldsymbol{X}})\), for some \(\tilde{\boldsymbol{X}} = (\tilde{X}_i)_i\) analagous to that in Table 2B, earlier. We begin by formally defining such source-fallible instantiations for a system of interest.

The idea here is that our notion of redundancy deals with censored copies of our predictors, where for fixed \(\mathfrak{s}\) there’s a one-to-one correspondence between the failure distribution \(\boldsymbol{F}\) and the censored source vector \(\boldsymbol{\tilde{X}}\). Clearly, the least informative \(\tilde{\boldsymbol{X}}\) in \(\mathfrak{F}\) will be given by \(\boldsymbol{F} \equiv \boldsymbol{0}\), i.e. when all sources fail all the time. Then \(\tilde{\boldsymbol{X}} \equiv \boldsymbol{0}\). The SFS’s we’re interested in, though, are those that have limited failures while still providing one of the sources of information, as in Table 2B. We now have the notation to make this condition precise in the general case. We will allow for a fairly unconstrained distribution of source failures \(\boldsymbol{F}\), i.e. we need not assume \(\boldsymbol{F}\) has any particular independence with respect to \(T\) and/or \(\boldsymbol{X}\).

Intuitively, (?? ) means that always at least one source \(X_I \in \alpha\) is fully available from observing \(\tilde{\boldsymbol{X}}\). We posit that the information redundant among the sources in an antichain should be available from any SFS that redundantly satisfies that antichain. From this postulate, the definition that should follow for redundant information becomes clear. We merely minimize over all such SFS’s redundantly satisfying the given antichain.

There is one aspect of this definition that may seem a little strange. For any antichain, we are minimizing over SFS’s constructed from the full system \((X_1, ..., X_n, T)\). For the redundancy of \(\alpha = \{ X_1\} \{X_2\}\), surely we should only be concerned with \((X_1, X_2, T)\). In fact, the minimum in (?? ) for such a case can be achieved for an SFS where \(F_i \equiv 0\) for \(i>2\),. This is indistinguishable from considering only the system \((X_1,X_2, T)\) from the start. Although we retain Def. 4 as our preferred formulation, in the following two propositions, we make precise the equivalence of our definition to this reduced form.

We may thus identify \(\mathfrak{F}_I\) with its image \(g_I(\mathfrak{F}_I)\) as a subset of \(\mathfrak{F}\). The following proposition shows that we may compute \(I_{\texttt{ft}}(\alpha)\) within the reduced space \(\mathfrak{F}_I\) for the smallest \(\boldsymbol{X}_I\) capturing all sources in \(\alpha\).

From the preceding two propositions, the demonstration of the self-redundancy PID axiom for \(I_{\texttt{ft}}\) reduces to one line.

Our main result in this section elucidates the structure of the \(I_{\texttt{ft}}\) redundancy function, including its satisfaction of the monotonicity PID axiom, by establishing a close correspondence between source antichains \(\alpha \in \mathcal{A}(\boldsymbol{X})\), on the one hand, and these collections of source-fallible systems \(\mathfrak{R}(\alpha) \subset \mathfrak{F}(\mathfrak{s})\) that we have been examining. Let \(\mathcal{F}(\mathfrak{s}) = \{ \mathfrak{R}(\alpha) \}_{\alpha \in \mathcal{A}(\boldsymbol{X})}\). Insofar as each family \(\mathfrak{R}(\alpha)\) is a subset of \(\mathfrak{F}\), it follows that we can consider \(\mathcal{F}(\mathfrak{s})\) as a finite poset under inclusion, i.e. \((\mathcal{F}(\mathfrak{s}), \subseteq)\). As we will now demonstrate, this poset is the mirror image of the PID lattice \((\mathcal{A}(\boldsymbol{X}), \preceq)\).

An immediate consequence of this result is the monotonicity PID axiom. As one adds sources to an antichain, the set of fallible instantiations of the system grows: there are more ways for things to go wrong. Conversely, by removing sources or concatenating them, we reduce that range of possibilities.

To conclude, let us revisit the scenario we introduced at the start of this section. Given \(n\) sources of information (predictor variables) for a system regarding its target \(T\), we asked how that system might tolerate up to \(\ell\) failures at a time. Let us further add that these failures may be arbitrarily (even adversarially) distributed. Let \(\mathcal{P}_{n - \ell}'(\boldsymbol{X})\) be the set of all sources \(\boldsymbol{X}_I\) with \(|I| = n - \ell\). There will be \({n \choose \ell}\) of these sources. Then, letting \(\alpha_{\ell} = \mathcal{P}_{n - \ell}'(\boldsymbol{X})\), we can answer that the expected amount of information we can guarantee regarding \(T\) is given by \(I_{\texttt{ft}}(\alpha)\), as defined in this section. Moreover, as a special case of the monotonicity axiom demonstrated above, we have that \[\begin{align} \nonumber 0 &= I_{\texttt{ft}}(\alpha_n) \leq I_{\texttt{ft}}(\alpha_{n-1}) \leq ... \\ &\leq I_{\texttt{ft}}(\alpha_{1}) \leq I_{\texttt{ft}}(\alpha_{0}) = I(T; \boldsymbol{X}) \end{align}\] where we extended \(I_{\texttt{ft}}\) naturally to take \(\alpha_n = \emptyset\) as an argument.

References↩︎