THE DUAL INFORMATION BOTTLENECK
Year: 2019

Abstract:
The Information Bottleneck (IB) framework is a general characterization of optimal representations in large scale learning that suggests an intriguing interpretation of efficient representations in deep learning in particular. It is based on the optimal trade off between the representation complexity and accuracy, both of which are quantified by mutual information. The problem is solved by alternating projections between the encoder and decoder of the representation, which can be performed locally at each representation level. The non-parametric IB framework, however, has several drawbacks: (i) the difficult estimation of information measures in high dimensions; (ii) the inability to extend the encoder beyond the training data the need to to know the full joint distribution of the inputs and labels; (iii) the IB does not necessarily optimize the actual prediction of unseen labels, which can be critical when training the encoder from finite samples. Here we present a new framework, the Dual Information Bottleneck (dualIB), which improves all the above drawbacks. By switching the order in the KL-divergence between the representation decoder and data, formally the dual distortion, the optimal decoder becomes the geometric rather than the arithmetic mean of the input points. This conversion preserves exponential forms of the original distribution and consequently conserves the original features of the data. We show how to solve this new representation learning formulation and illustrate it’s favorable properties over the original IB when trained from a small sample. We also analyze the critical points of the dualIB and discuss their importance for the quality of this approach.

heading: 1 INTRODUCTION

heading: 1.1 THE INFORMATION BOTTLENECK METHOD
text: The Information Bottleneck (IB) method (Tishby et al., 1999), is an information-theoretic framework for describing efficient representations of a large scale “input” random variable X (input patterns), for predicting an “output” variable Y (desired label). In this setting the joint distribution of X and Y, p(x, y) defines the problem, or rule, and the training data are a finite sample from this distribution. In general, we assume that p(y | x) is strictly stochastic, and hence bounded away from {0, 1}1. The representation variable X̂ is in general a stochastic function of X which forms a Markov chain Y → X → X̂, and only depends on Y through the input X. We call the map p(x̂ | x) the encoder of the representation and denote by p(y | x̂) the Bayes optimal decoder for this representation; i.e., the best possible prediction of the desired label Y from the representation X̂.
The IB has direct successful applications for representation learning in various domains, from vision and speech processing (Ma et al., 2019), to neuroscience (Schneidman et al., 2001), and Natural Language Processing (Li & Eisner, 2019). Due to the notorious difficulty in estimating mutual information in high dimension, variational approximations to the IB have been suggested and applied also to Deep Learning (Alemi et al., 2016; Parbhoo et al., 2018).
For large scale learning, when almost all input patterns can be considered typical in the information theoretic sense (Cover & Thomas, 2006), the cardinality of the typical inputs is characterized by the pattern’s entropy, H(X) = −∑x p(x) log p(x). Under similar typicality assumption, the mutual
1This may seem like a limitation of the method, but it can be shown that in the deterministic limit the IB is well defined. This stochastic assumption simplifies the analysis but does not pose any real limitation.
information (MI) of the encoder, I(X; X̂) = ∑
x,x̂ p(x, x̂) log p(x|x̂) p(x) characterizes the cardinality of
the typical representations, X̂. On the other hand, the mutual information of the Bayes optimal decoder, I(Y; X̂) = ∑ y,x̂ p(y, x̂) log p(y|x̂) p(y) , is equivalent to the cross-entropy generalization error.
The IB trade off between the encoder and decoder mutual information values is defined by the minimization of the Lagrangian:
F [pβ(x̂ | x); pβ(x̂); pβ(y | x̂)] = I(X; X̂)− βI(Y; X̂) , (1) independently over the convex sets of the normalized distributions, {pβ(x̂ | x)}, {pβ(x̂)} and {pβ(y | x̂)}, given a positive Lagrange multiplier β. As shown in (Tishby et al., 1999; Shamir et al., 2010), this is a natural generalization of the classical concept of Minimal Sufficient Statistics (Cover & Thomas, 2006), where the estimated parameter is replaced by the output variable Y and exact statistical sufficiency is characterized by the mutual information equality: I(X̂;Y) = I(X;Y). The minimality of the statistics is captured by the minimization of I(X; X̂), due to the Data Processing Inequality (DPI). However, non-trivial minimal sufficient statistics only exist for very special parametric distributions known as exponential families (Brown, 1986). Thus in general, the IB relaxes the minimal sufficiency problem to a continuous family of representations X̂ which are characterized by the trade off between compression, I(X; X̂) ≡ IX, and accuracy, I(Y; X̂) ≡ IY, along a convex line in the Information-Plane (IY vs. IX). When the rule p(x, y) is strictly stochastic, the convex optimal line is smooth and each point along the line is uniquely characterized by the value of β. We can then consider the optimal representations x̂ = x̂(β) as encoder-decoder pairs: (pβ(x|x̂), pβ(y|x̂))2 - a point in the continuous manifold defined by the Cartesian product of these distribution simplexes. We also consider a small variation of these representations, δx̂, as an infinitesimal change in this (encoder-decoder) continuous manifold (not necessarily on the optimal line(s)).

heading: 1.2 IB AND RATE-DISTORTION THEORY
text: The IB optimization trade off can be considered as a generalized rate-distortion problem (Cover & Thomas, 2006) with the distortion function between a data point, x and a representation point x̂ taken as the KL-divergence between their predictions of the desired label y:
dIB(x, x̂) = D[p(y | x)||pβ(y|x̂)] = ∑
y
p(y | x) log p(y | x) pβ(y | x̂) . (2)
The expected distortion Epβ(x,x̂)[dIB(x, x̂)] for the optimal decoder is simply the label-information loss: I(X;Y) − I(X̂;Y), using the Markov chain condition. Thus minimizing the expected IB distortion is equivalent to maximizing I(X̂;Y), or minimizing equation 1. Minimizing this distortion is equivalent to minimizing the log-loss or the cross-entropy loss, as done in most deep learning applications, and it upper-bounds other loss functions such as the L1-loss (due to the Pinsker inequality, or (Painsky & Wornell, 2018)). The Pinsker inequality shows that both orders of the cross-entropy upper bound to the L1-loss, or total-variation distance, min{D[q||p], D[p||q]} ≥ 12 log 2‖p− q‖21 .

heading: 1.3 THE IB EQUATIONS
text: For discrete X and Y, a necessary condition for the IB (local) minimization is given by the three self-consistent equations for the optimal encoder-decoder pairs, known as the IB equations: (i) pβ(x̂ | x) = pβ(x̂)Z(x;β)e−βD[p(y|x)‖pβ(y|x̂)] (ii) pβ(x̂) = ∑ x pβ(x̂ | x)p(x)
(iii) pβ(y | x̂) = ∑ x p(y | x)pβ(x | x̂) , (3)
where Z(x;β) is the normalization function. Iterating these equations is a generalized, BlahutArimoto, alternating projection algorithm (Tusnady & Csiszar, 1984; Cover & Thomas, 2006) and it converges to a stationary point of the Lagrangian, equation 1 (Tishby et al., 1999). Notice that the minimizing decoder, (equation 3-(iii)), is precisely the Bayes optimal decoder for the representation x̂(β), given the Markov chain conditions.
2Here we use the inverse encoder, which is in the fixed dimension simplex of distributions over X.

heading: 1.4 CRITICAL POINTS AND CRITICAL SLOWING DOWN
text: One of the most interesting aspects of the IB equations is the existence of critical points along the optimal line of solutions in the Information-Plane (i.e. the information curve). At these points the representations change topology and cardinality (number of clusters) (Zaslavsky & Tishby, 2019; Parker et al., 2003) and they form the skeleton of the information curve and representation space. Under the strict stochastic assumption, the information-curve is a smooth function of the Lagrange multiplier β, but its derivative may not be smooth. Critical points are bifurcations of the solutions, which are values of β for which two different solutions (representations) co-exist. To identify such points we perform a perturbation analysis of the IB equations, as in (Zaslavsky & Tishby, 2019). Taking a small perturbation of the representation, denoted for brevity by δx̂, the changes in the log encoder and log decoder that satisfy equation 3 for a given β can be determined through the nonlinear eigenvalues problems3:[
I − βCIBxx′(x̂, β) ]∂ log pβ(x′ | x̂)
∂x̂ = 0 ,
[ I − βCIByy′(x̂, β) ]∂ log pβ(y′ | x̂) ∂x̂ = 0, (4)
with the two square matrices C defined by: CIBxx′(x̂, β) = ∑
y
p(y | x)pβ(x ′ | x̂)
pβ(y | x̂) p(y | x′) , CIByy′(x̂, β) = ∑ x p(y | x)pβ(x | x̂) pβ(y | x̂) p(y′ | x). (5)
As shown in (Zaslavsky & Tishby, 2019), these two matrices have the same eigenvalues and have non-trivial eigenvectors (i.e., different co-existing optimal representations) precisely at the critical values of β, the bifurcation points of the IB solution. At these points the cardinality of the representation X̂ (the number of “IB-clusters”) changes due to splits of clusters, resulting in topological phase transitions in the encoder. These critical points form the “skeleton” of the topology of the optimal representations. Between critical points the optimal representations change continuously (with β).
The important computational consequence of critical points is known as critical slowing down (Tredicce et al., 2004). For binary Y, near a critical point the convergence time, τβ , of the iterations of equation 3 scales like: τβ ∼ 1/(1− βλ2), where λ2 is the second eigenvalue of either CIByy′ or C IB xx′ . At criticality, λ2(x̂) = β
−1 and the number of iterations diverges. This phenomenon dominates any local minimization of equation 3 which is based on alternate encoder-decoder optimization.
To illustrate the importance of the critical points and the critical slowing-down we consider a lowdimensional problem that is easy to visualize. Taking the joint distribution, p(y, x) with a binary Y and only 5 possible inputs. For a given β, the Blahut-Arimoto iterations converge to a stationary solutions of the IB equations, which amounts to discrete points in the interval [0, 1] - the simplex of the p(y) distributions - for each value of the Lagrange multiplier, β.
The evolution of the optimal decoder, pβ(y = 0 | x̂), ∀x̂ ∈ X̂, as a function of β, is a bifurcation diagram (Figure 1(a)). The critical points of the IB equations correspond to bifurcations in the decoders’ graph. At these critical points the non-trivial eigenvalues of CIByy′(β) cross the β
−1 value (Figure 1(b)), and the number of iterations diverges (critical slowing down) (Figure 1(c)).

heading: 1.5 DRAWBACKS OF THE IB
text: The main theoretical and practical drawback of the IB is it’s apparent reliance on the explicit knowledge of the joint distribution p(x, y). In the context of representation learning this is often considered a major flaw, as we are always given only a sample from the distribution. While the generalization properties of the finite sample IB representations have been studied in the past (Shamir et al., 2010), the main problem remains the extension of the encoder, p(x̂ | x), when trained from a small sample, to new unobserved patterns x ∈ X. The standard approach in representation learning is to assume (at least implicitly) the existence of features of x with their topology, or a specific parametric form for the encoder. The original IB is completely non-parametric and does not assume any topology on the input space, beyond label similarity. A related drawback of the IB is it’s poor scalability with the size of the pattern-space X, which makes the reliable estimation of the encoder mutual information impractical for large learning problems.
3We ignore here the interactions between the representations, for simplicity.

heading: 1.6 CONTRIBUTIONS OF THIS WORK
text: Our main contribution is by providing a general formal framework resolving the encoder extension drawback of the IB. While the use of specific features and variational approximations to the IB are not new, here we take a different approach assuming that p(y | x) can be approximated by exponential families. This defines a new rate-distortion problem, the Dual Infromation Bottleneck (dualIB).
We show that the new dualIB formulation preserves the sufficient statistics of the original distribution for all values of the trade off parameter, β. A desired property upon predictions of a parametrized distribution. Furthermore, it obtains a significant improvement of the finite sample label prediction. We demonstrate numerically that the dualIB encoder-decoder pairs improve the prediction of unseen labels when trained from small samples, compared to the original IB. We also discuss in detail the critical points of the new formulation and their relation to those of the original IB. Interestingly, as we elaborate in the following sections, all these desirable properties are achieved by merely switching the order of the arguments in the KL-divergence of the IB distortion.
The remainder of the paper is organized as follows. We present and solve the dualIB problem in §2. We discuss the dualIB’s critical points in §2.1 and prove a general relation between the critical points of the dual and original IB in §2.2. In particular, we show that the dual critical points give the best approximation to the original IB information curve. In §3 we discuss the dualIB for exponential families, dualExpIB, and demonstrate the advantages of our framework in this case. We also demonstrate numerically the improvement in the label prediction of the dualIB when trained from a small sample. We conclude in §4 with further extensions and possible applications.

heading: 2 THE DUALIB: MAXIMIZING THE PREDICTION INFORMATION
text: Supervised learning is generally separated into two phases: the training phase, where the internal representations are formed from the training data, and the prediction phase, where these representations are used to predict labels of new input patterns. We add to our Markov chain another variable, Ŷ, the predicted label which obtains the same values as Y, but distributed differently:
training︷ ︸︸ ︷ Y→ X→ X̂β → Ŷ︸ ︷︷ ︸
prediction
. (6)
The left-hand part of this chain describes the representation training, and the right-hand part is the Maximum Likelihood (ML) prediction using these representations (Slonim et al., 2006). So far the prediction variable Ŷ has not been part of the IB optimization problem. It has been implicitly assumed that the Bayes optimal decoder, pβ(y | x̂), which minimizes the IB distortion at a given β,
is also the best choice for making predictions of Ŷ from the representation X̂β through the righthand Markov chain. That is, denoting pβ(ŷ | x̂) ≡ pβ(y | x̂) the ML decoder is the mixture over the internal representations:
pβ(ŷ | x) ≡ ∑
x̂
pβ(ŷ | x̂)pβ(x̂ | x). (7)
This, however, is not necessarily optimal when the encoder and decoder are trained from finite samples (Shamir et al., 2010), or when the decoder is not Bayes optimal. We define the dualIB distortion by merely switching the order of the arguments in the KL-divergence of the original IB distortion, namely:
ddualIB(x, x̂) = D[pβ(y | x̂)||p(y | x)] = ∑
y
pβ(y | x̂) log pβ(y | x̂) p(y | x) , (8)
which in geometric terms is known as the dual distortion problem (Felice & Ay, 2019).
That is, given the “input” random variable X (input patterns), the ”output” random variable Y (desired label) and the “representation” X̂, the ML optimal “predicted label” Ŷ is given by the mixture distribution, equation 7.4
The dualIB optimization can be written as the following rate-distortion problem:
F∗[pβ(x̂ | x); pβ(x̂); pβ(y | x̂)] = I(X; X̂) + βEp(x,x̂)[ddualIB(x, x̂)] , (9)
with the average distortion given in terms of mutual information on Ŷ, I(X̂; Ŷ) and I(X; Ŷ):
Ep(x,x̂)[ddualIB(x, x̂)] = I(X̂; Ŷ)− I(X; Ŷ)︸ ︷︷ ︸ (a) +Ep(x)[D[pβ(ŷ | x)‖p(ŷ | x)]]︸ ︷︷ ︸ (b)
≥ I(X̂; Ŷ)− I(X; Ŷ) . (10)
This is similar to the known IB relation: Ep(x,x̂)[dIB(x, x̂)] = I(Y;X) − I(Y; X̂) with an extra positive term (b).
Both terms, (a) and (b), vanish precisely when X̂ is a sufficient statistic for X with respect to Ŷ, since we can then reverse the order of X and X̂ in the Markov chain (equation 6). This replaces the roles of Y and Ŷ as the variable for which X̂β are approximately minimally sufficient statistics. In that sense the dualIB shifts the emphasis from the training phase to the prediction phase. This implies that minimizing the dualIB functional maximizes the mutual information between Y and Ŷ, I(Y; Ŷ), as well as the mutual information I(X; Ŷ). This is illustrated in figure 4(b)-c.
The next theorem states the form of the solutions of the Dual Information Bottleneck:
Theorem 1. The minima of equation 9, can be obtained by generalized Blahut-Arimoto iterations between the encoder and the decoder as in the original IB, with the following modifications: (i) Replace the distortion by its dual in the encoder update; (ii) Update the decoder by the encoder’s ”geometric” mean of the data distributions p(y | x).
The proof is given in §A.2. The alternating projections between the encoder and decoder, which converge to a solution of the dualIB at a given value of the Lagrange multiplier β, are implemented by the following iterative algorithm5:
4We use the notation p(ŷ | x) ≡ p(y | x), when there is no β subscript. 5Unless stated otherwise, log = ln ≡ loge
Algorithm 1 dualIB iterative algorithm 1: while ∣∣∣pt+1β (y | x̂)− ptβ(y | x̂)∣∣∣ > do
2: Zt+1x̂|x (x;β) = ∑ x̂ p t β(x̂)e −βD[ptβ(y|x̂)‖p(y|x)] 3: pt+1β (x̂ | x) = ptβ(x̂)
Zt+1 x̂|x (x;β)
e−βD[p t β(y|x̂)‖p(y|x)]
4: pt+1β (x̂) = ∑ x p t+1 β (x̂ | x)p(x)
5: Zt+1y|x̂ (x̂;β) = ∑ y e ∑ x p t+1 β (x|x̂) log p(y|x)
6: pt+1β (y | x̂) = 1Zy|x̂(x̂;β)e ∑ x p t+1 β (x|x̂) log p(y|x) 7: return pβ(x̂), pβ(x̂ | x), pβ(y | x̂)
Here the Z’s are standard normalization factors (partition functions). As in the IB, the encoder update (row 3) and decoder update (row 6) are the core of the algorithm.
Figure 2 illustrates the behavior of the dualIB algorithm for the same distribution as in Figure 1. The overall behavior is very similar, but the critical points (representation splits) slightly change their location. In the following sections we provide a detailed analysis and comparison between the two frameworks.
2.1 THE CRITICAL POINTS OF THE dualIB
As discussed in §1.4 the skeleton of the IB optimal bound (the information curve) is constituted by the critical points in which the topology (cardinality) of the representation changes. A similar stability analysis of the dualIB equations reveals similar conditions for the critical points. Theorem 2. The dualIB critical points are detected by non-trivial solutions of the nonlinear eigenvalue problem:[
I − βCdualIBxx′ (x̂, β) ]∂ log pβ(x′ | x̂)
∂x̂ = 0 ,
[ I − βCdualIByy′ (x̂, β) ]∂ log pβ(y′ | x̂) ∂x̂ = 0, (11)
with the matrices CdualIB given by: CdualIBxx′ (x̂;β) = ∑ y,ỹ,x̃ pβ(y | x̂)pβ(x̃ | x̂) log p(y | x) p(y | x̃) · pβ(x ′ | x̂)pβ(ỹ | x̂) log p(y | x′) p(ỹ | x′)
CdualIByy′ (x̂;β) = ∑ x,x̃,ỹ pβ(x | x̂)pβ(ỹ | x̂) log p(y | x) p(ỹ | x) · pβ(y ′ | x̂)pβ(x̃ | x̂) log p(y′ | x) p(y′ | x̃) . (12)
The proof to theorem 2 is given in §A.3.
Lemma 3. The matrices CdualIBxx′ (x̂;β), CdualIByy′ (x̂;β) have the same eigenvalues {λi}, with λ1(x̂) = 0. With binary Y, the critical points are obtained at λ2(x̂) = β−1.
The proof of lemma 3 given in section §A.3.1. As in the IB, at the critical points, βdualIBc , the partial derivatives of the encoder and decoder with respect to β, ∂ log pβ(x | x̂)/∂β, ∂ log pβ(y | x̂)/∂β, have multiple (at least two) values. This results in discontinuities (cusps) in the encoder and decoder mutual information values as functions of β along the optimal line, with an undefined second derivative.
2.2 THE INFORMATION PLANE OF THE dualIB
The Information Plane, IX = I(X̂;X) vs. IY = I(X̂;Y), is the standard visualization of the compression-prediction trade off of the IB. It can be defined for any encoder once the decoder is the Bayes optimal (equation 3-(iii)), for which the IY is the actual information of the representation on the desired label (Tishby et al., 1999).
Comparing the dualIB information curve to the IB curve shows the quality of this approximation. Figure 3(a) depicts this comparison. While we know that IIBY (β) is always higher, the two curves are almost indistinguishable. To better understand the relationship between these two curves, we look at the values of IX and IY as functions of the corresponding β (Figure 3(b),(c)). The important role of the critical points is revealed as the corresponding cusps along these curves. As we argue below, the IB information values are strictly below those of the dualIB, but the distance between them is minimized precisely at the dual critical points.
Y (β) are monotonic and piece-wise concave. The relative
discrepancy between the information curves is clearly minimized at the dualIB critical points (inset). The functions approach each other for large β.
Lemma 4. IX(β) and IY(β), along the optimal lines, are non-decreasing piece-wise concave, functions of β. When their second derivative (with respect to β) is defined, it is strictly negative. Lemma 5. For any sub-optimal information curve (IX, IY), IIBX (β) ≤ IX(β) and IIBY (β) ≤ IY(β), for all values of β.
Proofs of the above are given in §A.4. The information plane properties are summarized by the following theorem. Theorem 6. (i) The critical points of the two algorithms alternate: for each critical point, βdualIBc ≤ βIBc . (ii) The distance between the two information curves is minimized precisely at the dualIB critical points βdualIBc . (iii) The two curves approach each other as β →∞.
Proof. The proof follows from lemmas 4 and 5, together with the critical points analysis above, and is only sketched here. As the encoder and decoder at the critical points, βIBc and β dualIB c , have
different left and right derivatives, they form cusps in the curves of the mutual information (IX and IY) as functions of β. These cusps can only be consistent with the optimality of the IB curves if βdualIBc < β IB c (this is true for any sub-optimal distortion), otherwise the curves intersect.
Moreover, at the dualIB critical points, the distance between the curves is minimized due to the strict concavity of the functions segments between the critical points. As the critical points imply discontinuity in the derivative, this results in a ”jump” in the information values. Therefore, at any βdualIBc the distance between the curves has a (local) minimum. This is depicted in Figure 3, comparing IX(β) and IY(β) and their differences for the two algorithms.
The two curves approach each other for large β since the two distortion functions become close in the low distortion limit (as long as p(y | x) is bounded away from 0).
3 THE EXPONENTIAL FAMILY dualIB
As discussed in §1, one of the major drawbacks of the IB is the extension of the decoder inputs from an empirical sample to new unseen patterns. To address this issue we can assume the existence of features, or statistics of the pattern, Ar(x), which are sufficient or approximately sufficient for the prediction of the label Y. That is, we consider the rule’s distribution, p(y | x), to be an exponential family with these features. Exponential families form the elegant theoretical core of parametric statistics and often emerge as maximum entropy (Jaynes, 1957) or stochastic equilibrium distributions, subject to observed expectation constraints. They also form the class of parametric distributions for which exact, finite dimensional and additive, Minimal Sufficient Statistics exist (Kullback, 1959). Such distributions should also best match the rational behind the IB as extracting approximate sufficient statistics.
A key property of exponential families is their invariance under geometric averages. For this technical reason the dualIB encoder and decoder preserve the exponential form of the original data distribution for all values of β. Furthermore, the new (assumed limited to a finite dimension d) set of features/statistics are precisely the empirical expectations of these features. These d empirical averages are the only numbers needed for predicting the label at the required accuracy, hence their advantage in reducing the encoder’s computational complexity.
Assuming that the rule distribution is of the form:
p(y | x) = e− ∑d r=0 λ r(y)Ar(x) = e−λ(y)·A(x)−logZy|x(x) = d∏ r=0 e−λ r(y)Ar(x) , (13)
where Ar(x) are d linearly independent functions of the input x and λr(y) are functions of the label y, or the parameters of this exponential family. The λ(y) can also be considered Lagrange multipliers associated with the constraints conditional expectations Ep(x|y)[Ar(x)] in entropy maximization. The normalization factors, Zy|x(x), are written, for brevity, as λ0x ≡ log( ∑ y ∏d r=1 e −λr(y)Ar(x)) with A0(x) ≡ 1. We do not constrain the marginal p(x). The important fact about the exponential form is that all the mutual information, I(X;Y), is fully captured by the d conditional expectations, Ep(x|y)[Ar(x)], since these are the (minimal) sufficient statistics for the parameters. This means that all the relevant information (in the training sample) is captured solely by d-dimensional empirical expectations. This can lead to a huge reduction in computational complexity (from dim(X) to d).
We next show that for the dualIB, this dimension reduction is preserved or improved along the dual information curve, for all values of β.
Theorem 7. (dualExpIB) For data from an exponential family, equation 13, the optimal decoder of the dualIB, at a given β, is given by:
pβ(y | x̂) = e− ∑d r=1 λ r(y)Ar,β(x̂)−λ0β(x̂) , λ0β(x̂) = log( ∑
y
e− ∑d r=1 λ r(y)Ar,β(x̂)) , (14)
and the respective encoder:
pβ(x̂ | x) = pβ(x̂)e−βλ 0 β(x̂)
Zx̂|x(x;β) e−β
∑d r=1 λ r β(x̂)[Ar(x)−Ar,β(x̂)] , (15)
with the constraints and multipliers expectations, Ar,β(x̂) ≡ ∑
x
pβ(x | x̂)Ar(x) , λrβ(x̂) ≡ ∑
y
pβ(y | x̂)λr(y) , 1 ≤ r ≤ d . (16)
The complete derivations for this section are given in §A.5. This defines a simplified iterative algorithm to solve the dualExpIB problem, since we can replace the decoders’ update rule at each iteration in the dualIB algorithm (Algorithm 1, row 6) with the simplified expression given in equation 14.
As a concrete illustration to the performance of the dualExpIB we examine a problem in which the rule distribution is given by an exponential family, p(y | x) ∼ N (0, a+ b|sin(cπx)|), as in Globerson & Tishby (2003). Setting the constants a, b, c we produce a sample S (of size N = 1000) on which we calculate the empirical distribution, p̂(y | x) and the empirical sufficient statistics Âr(x). Given the assumption on the rule we assess the exponential form empirical distribution, p̂exp(y | x; Âr(x)). We then evaluate the IB on both empirical distributions, p̂ and p̂exp, and compare it to the dualExpIB given Âr(x), λr(y)6.
The comparison between the IB and the dualExpIB, is given in Figure 4(a) as function of the continuous ŷ for a fixed x̂. It can be seen that the dualExpIB better captures the structure of the original data and is much less affected by the sampling noise. Next, we consider the Information Plane with respect to Ŷ, where the expected maximization by the dualExpIB is observed, Figure 4(b). To evaluate the prediction ability of the dualExpIB we consider the L1-expected loss with respect to the original distribution. Looking at Figure 4(c) it is apparent that for all values of the trade off parameter, β, the dualExpIB minimizes the loss providing the superiority in prediction.

heading: 4 CONCLUSION
text: We presented here the Dual Information Bottleneck (dualIB), a framework to preform the Information Bottleneck (IB) compression in a parametric setting. We have shown that the dualIB has several interesting properties: (i) it provides a good approximation to the original IB while using the low relevant dimensions of the original data. This can significantly reduce the complexity of finding good IB representations; (ii) it optimizes the information between the representation and the predicted label rather than the desired label as in the original IB. As we have shown, this can improve
6λr(y) are defined by the specific exponential family.
the generalization error when trained on small samples since the predicted label is the one used in practice; (iii) It preserves the exponential form of data from exponential families, while reducing the dimensionality of the compressed representations. This important property was known to be satisfied by the Gaussian IB (Chechik et al., 2005) but not known for other distributions. The Gaussian case is self-dual in that sense. Generalizing this property to other exponential families was an open problem for many years; (iv) The exponential form of the optimal encoder-decoder pairs allows for the application to distributions with special symmetries, which can be naturally expressed in this form.
We conclude that the exponential Dual Information Bottleneck (dualExpIB) framework allows us now to approach problems previously considered intractable by the IB. Furthermore, it may allow better predictions to IB applications using finite samples or data with low internal dimensionality or special symmetries.

heading: A APPENDIX

heading: A.1 DUALIB MATHEMATICAL FORMULATION
text: As presented in §1.6 the dualIB is solved with respect to the full Markov chain (equation 6) in which we introduce the new variable, Ŷ, the predicted label. Thus, in analogy to the IB we want to write the optimization problem in term of Ŷ.
Developing the expected distortion we find: Epβ(x,x̂)[ddualIB(x, x̂)] = ∑ x,x̂ pβ(x, x̂) ∑ ŷ pβ(ŷ | x̂) log pβ(ŷ | x̂) p(ŷ | x)
= ∑ x̂,ŷ pβ(x̂)pβ(ŷ | x̂) log pβ(ŷ | x̂) pβ(ŷ) − ∑ x,ŷ p(x)pβ(ŷ | x) log pβ(ŷ | x) pβ(ŷ)
+ ∑ x,ŷ p(x)pβ(ŷ | x) log pβ(ŷ | x) p(ŷ | x)
= I(X̂; Ŷ)− I(X; Ŷ) + Ep(x)[D[pβ(ŷ | x)‖p(ŷ | x)]].
Allowing the dual optimization problem to be written as: F∗[p(x̂ | x); p(x̂); p(y | x̂)] = I(X; X̂)− β { I(X; Ŷ)− I(X̂; Ŷ)− Ep(x)[D[pβ(ŷ | x)‖p(ŷ | x)]] } .

heading: A.2 THE DUALIB SOLUTIONS
text: To prove theorem 1 we want to obtain the normalized distributions minimizing the dualIB ratedistortion problem.
Proof. (i) Given that the problem is formulated as a rate-distortion problem the encoder’s update rule must be the known minimizer of the distortion function (Cover & Thomas, 2006). Thus the IB encoder with the dual distortion is plugged in. (ii) For the decoder, by considering a small perturbation in the distortion ddualIB(x, x̂), with α(x̂) the normalization Lagrange multiplier, we obtain:
δddualIB(x, x̂) = δ (∑ y pβ(y | x̂) log pβ(y | x̂) p(y | x) + α(x̂) (∑ y pβ(y | x̂)− 1 ))
δddualIB(x, x̂) δpβ(y | x̂) = log pβ(y | x̂) p(y | x) + 1 + α(x̂).
Hence, minimizing the expected distortion becomes: 0 = ∑
x
pβ(x | x̂) [ log
pβ(y | x̂) p(y | x) + 1
] + α(x̂)
= log pβ(y | x̂)− ∑
x
pβ(x | x̂) log p(y | x) + 1 + α(x̂),
which yields Algorithm 1, row 6.
Considering the dualIB encoder-decoder, Algorithm 1, we find that Epβ(x,x̂)[ddualIB(x, x̂)] reduces to the expectation of the decoder’s log partition function:
Epβ(x,x̂)[ddualIB(x, x̂)] = ∑ x,x̂ pβ(x, x̂) ∑ y pβ(y | x̂) log pβ(y | x̂) p(y | x)
= −Epβ(x̂) [ logZy|x̂(x̂;β) ] + ∑ x̂,y pβ(x̂) [∑ x′ pβ(x′ | x̂) log p(y | x′)− ∑ x pβ(x | x̂) log p(y | x) ]
= −Epβ(x̂) [ logZy|x̂(x̂;β) ] .

heading: A.3 STABILITY ANALYSIS
text: Here we provide the detailed stability analysis allowing the definition of the matrices CdualIBxx′ , C dualIB yy′ (equation 12) and which allows us to claim that they obey the same rules as the C matrices (equation 5) in equation 4. Considering a variation in x̂ we get: ∂ log pβ(x | x̂)
∂x̂ =β ∑
y
pβ(y | x̂) ( log
p(y | x) pβ(y | x̂)
− 1 ) ∂ log pβ(y | x̂)
∂x̂
=β ∑
y
pβ(y | x̂) [ log p(y | x)−
∑ x̃
pβ(x̃ | x̂) log p(y | x̃) ] ∂ log pβ(y | x̂)
∂x̂
+β ∑
y
logZy|x̂(x̂;β) ∂pβ(y | x̂)
∂x̂
=β ∑ y,x̃ pβ(y | x̂)pβ(x̃ | x̂) log p(y | x) p(y | x̃) ∂ log pβ(y | x̂) ∂x̂ , (17)
∂ log pβ(y | x̂) ∂x̂ =− 1 Zy|x̂(x̂;β) ∂Zy|x̂(x̂;β) ∂x̂
+ ∑
x
pβ(x | x̂) log p(y | x) ∂ log pβ(x | x̂)
∂x̂
=− ∑
ỹ
pβ(ỹ | x̂) ∑
x
pβ(x | x̂) log p(ỹ | x) ∂ log pβ(x | x̂)
∂x̂
+ ∑
x
pβ(x | x̂) log p(y | x) ∂ log pβ(x | x̂)
∂x̂
= ∑ x,ỹ pβ(x | x̂)pβ(ỹ | x̂) log p(y | x) p(ỹ | x) ∂ log pβ(x | x̂) ∂x̂ . (18)
Substituting equation 18 into equation 17 and vice versa one obtains: ∂ log pβ(x | x̂)
∂x̂ = β ∑ x′,y,ỹ,x̃ pβ(y | x̂)pβ(x̃ | x̂) log p(y | x) p(y | x̃)
· pβ(x′ | x̂)pβ(ỹ | x̂) log p(y | x′) p(ỹ | x′) ∂ log pβ(x′ | x̂) ∂x̂
∂ log pβ(y | x̂) ∂x̂
= β ∑
x,y′,x̃,ỹ
pβ(x | x̂)pβ(ỹ | x̂) log p(y | x) p(ỹ | x)
· pβ(y′ | x̂)pβ(x̃ | x̂) log p(y′ | x) p(y′ | x̃) ∂ log pβ(y′ | x̂) ∂x̂ .
We now define the CdualIB matrices as follows: CdualIBxx′ (x̂;β) = ∑ y,ỹ,x̃ pβ(y | x̂)pβ(x̃ | x̂) log p(y | x) p(y | x̃) · pβ(x ′ | x̂)pβ(ỹ | x̂) log p(y | x′) p(ỹ | x′)
CdualIByy′ (x̂;β) = ∑ x,x̃,ỹ pβ(x | x̂)pβ(ỹ | x̂) log p(y | x) p(ỹ | x) · pβ(y ′ | x̂)pβ(x̃ | x̂) log p(y′ | x) p(y′ | x̃) .
Using the above definition we have an equivalence to equation 4 in the form of:[ I − βCdualIBxx′ (x̂, β) ]∂ log pβ(x′ | x̂) ∂x̂ = 0 , [ I − βCdualIByy′ (x̂, β) ]∂ log pβ(y′ | x̂) ∂x̂ = 0. Note that for the binary case, the matrices may be simplified to:
CdualIBxx′ (x̂;β) = ∑ y,x̃ pβ(y | x̂)pβ(x̃ | x̂) log p(y | x) p(y | x̃) · pβ(x ′ | x̂)(1− pβ(y | x̂)) log p(y | x′) 1− p(y | x′)
CdualIByy′ (x̂;β) = ∑ x,x̃ pβ(x | x̂)(1− pβ(y | x̂)) log p(y | x) 1− p(y | x) · pβ(y ′ | x̂)pβ(x̃ | x̂) log p(y′ | x) p(y′ | x̃) .

heading: A.3.1 PROOF OF LEMMA 3
text: We show that the CdualIB matrices share the same eigenvalues with λ1(x̂) = 0.
Proof. The matrices, CdualIBxx′ (x̂;β), C dualIB yy′ (x̂;β), are given by:
CdualIBxx′ (x̂;β) = Axy(x̂;β)Byx′(x̂;β) , C dualIB yy′ (x̂;β) = Byx(x̂;β)Axy′(x̂;β),
with: Axy(x̂;β) = pβ(y | x̂) ∑
x̃
pβ(x̃ | x̂) log p(y | x) p(y | x̃) , Byx(x̂;β) = pβ(x | x̂) ∑ ỹ pβ(ỹ | x̂) log p(y | x) p(ỹ | x) .
Given that the matrices are obtained by the multiplication of the same matrices, it follows that they have the same eigenvalues {λi(x̂;β)}. To prove that λ1(x̂;β) = 0 we show that det(CdualIByy′ ) = 0. We present the exact calculation for a binary label Y ∈ {y0, y1} (the argument for general Y follows by encoding the label as a sequence of bits and discussing the first bit only, as a binary case): det(CdualIByy′ (x̂;β)) = ∑ x,x̃ pβ(x | x̂)pβ(y1 | x̂) log p(y0 | x) p(y1 | x) · pβ(y0 | x̂)pβ(x̃ | x̂) log p(y0 | x) p(y0 | x̃)
· ∑ x′,x̃′, pβ(x′ | x̂)pβ(y0 | x̂) log p(y1 | x′) p(y0 | x′) · pβ(y1 | x̂)pβ ( x̃′ | x̂ ) log p(y1 | x′) p ( y1 | x̃′
) − ∑ x,x̃ pβ(x | x̂)pβ(y0 | x̂) log p(y1 | x) p(y0 | x) · pβ(y0 | x̂)pβ(x̃ | x̂) log p(y0 | x) p(y0 | x̃)
· ∑ x′,x̃′ pβ(x′ | x̂)pβ(y1 | x̂) log p(y0 | x′) p(y1 | x′) · pβ(y1 | x̂)pβ ( x̃′ | x̂ ) log p(y1 | x′) p ( y1 | x̃′
) = ∑
x,x′,x̃,x̃′ pβ(x | x̂)pβ(x′ | x̂)p2β(y0 | x̂)p2β(y1 | x̂)pβ(x̃ | x̂) log p(y0 | x) p(y0 | x̃)
pβ ( x̃′ | x̂ ) log
p(y1 | x′) p ( y1 | x̃′ ) · [ log
p(y0 | x) p(y1 | x) log p(y1 | x′) p(y0 | x′) − log p(y0 | x) p(y1 | x) log p(y1 | x′) p(y0 | x′)
] = 0.
Given that the determinant is 0 implies that λ1(x̂) = 0.
For a binary problem we can describe the non-zero eigenvalue using λ2(x̂) = Tr(CdualIByy′ (x̂;β)). That is:
λ2(x̂) = ∑ x,x̃ pβ(x | x̂)pβ(y1 | x̂) log p(y0 | x) p(y1 | x) · pβ(y0 | x̂)pβ(x̃ | x̂) log p(y0 | x) p(y0 | x̃)
+ ∑ x,x̃ pβ(x | x̂)pβ(y0 | x̂) log p(y1 | x) p(y0 | x) · pβ(y1 | x̂)pβ(x̃ | x̂) log p(y1 | x) p(y1 | x̃)
=pβ(y1 | x̂)pβ(y0 | x̂) ∑ x,x̃ pβ(x | x̂)pβ(x̃ | x̂) log p(y0 | x) p(y1 | x) [ log p(y0 | x) p(y0 | x̃) − log p(y1 | x) p(y1 | x̃) ] .
A.4 INFORMATION PLANE ANALYSIS
We rely on known results for the rate-distortion problem and the information plane:
Lemma 8. I(X; X̂) is a non-increasing convex function of the distortion Epβ(x,x̂)[d(x, x̂)] with a slope of −β.
We emphasis that this is a general result of rate-distortion thus holds for the dualIB as well.
Lemma 9. For a fixed encoder pβ(x̂ | x) and the Bayes optimal decoder pβ(y | x̂):
E[dIB(x, x̂)] = I(X;Y)− I(X̂;Y). Thus, the information curve, IY vs. IX, is a non-decreasing concave function with a positive slope, β−1. The concavity implies that β increases along the curve.
(Cover & Thomas, 2006; Gilad-bachrach et al., 2003).

heading: A.4.1 PROOF OF LEMMA 4
text: In the following section we provide a proof to lemma 4, for the IB and dualIB problems.
Proof. We want to analyze the behavior of IX(β), IY(β), that is the change in each term as a function of the corresponding β. From lemma 9, the concavity of the information curve, we can deduce that both are non-decreasing functions of β. As the two β derivatives are proportional it’s enough to discuss the first one.
Next, we focus on their behavior between two critical points. That is, where the cardinality of X̂ is fixed (clusters are ”static”). For ”static” clusters, the β derivative of IX, along the optimal line is given by:
∂I(X; X̂) ∂β = − ∂ ∂β ∑ x,x̂ pβ(x, x̂) ( logZx̂|x(x;β) + βd(x, x̂) ) = −β 〈 d(x, x̂)
∂ log pβ(x̂ | x) ∂β 〉 pβ(x,x̂)
≈ β 〈 d(x, x̂) [ ∂ logZx̂|x(x;β)
∂β + d(x, x̂) ]〉 pβ(x,x̂)
≈ β 〈〈 d2(x, x̂) 〉 pβ(x̂|x)
− 〈d(x, x̂)〉2pβ(x̂|x)︸ ︷︷ ︸ Var(d(x)) 〉 p(x) .
This first of all reassures that the function is non-decreasing as Var(d(x)) ≥ 0. The piece-wise concavity follows from the fact that when the number of clusters is fixed (between the critical points) - increasing β decreases the clusters conditional entropy H(X̂ | X), as the encoder becomes more deterministic. The mutual information is bounded by H(X̂) and it’s β derivative decreases. Further, between the critical points there are no sign changes in the second β derivative.

heading: A.4.2 PROOF OF LEMMA 5
text: Proof. The information curve has a positive slope, β−1, with β increasing along it, lemma 9. That is, given a value of β, there exists a pair IIBY (β), I IB X (β) such that ∂I IB Y (β)/∂I IB X (β) = β
−1. Now, consider a sub-optimal information curve, I∗Y, I ∗ X. There exist values β ′, β′′ such that:
I∗X(β ′) = IIBX (β) , I ∗ Y(β ′′) = IIBY (β).
The optimality of the IB implies that sub-optimal curves lie below it; i.e, the IB slope is steeper:
β−1 > β′−1 , β−1 > β′′−1.
Thus, given that β increases along the information curve, it holds that:
I∗X(β) > I ∗ X(β ′) = IIBX (β) , I ∗ Y(β) > I ∗ Y(β ′′) = IIBY (β).

heading: A.5 DERIVATION OF THE DUALEXPIB
text: We provide elaborate derivations to theorem 7; that is, we obtain the dualIB optimal encoder-decoder under the exponential assumption over the data. We use the notations defined in §3.
• The decoder, equation 14. Substituting the exponential assumption into the dualIB log-decoder yields:
log pβ(y | x̂) = ∑
x
pβ(x | x̂) log p(y | x)− logZy|x̂(x̂;β)
= − ∑
x d∑ r=0 pβ(x | x̂)λr(y)Ar(x)− logZy|x̂(x̂;β)
= − d∑ r=1 λr(y)Ar,β(x̂)− Epβ(x|x̂) [ λ0x ] − logZy|x̂(x̂;β).
Taking a closer look at the normalization term: Zy|x̂(x̂;β) = ∑
y
e ∑ x pβ(x|x̂) log p(y|x) = e −Epβ(x|̂x)[λ 0 x] ∑
y
e− ∑d r=1 λ r(y)Ar,β(x̂)
logZy|x̂(x̂;β) = −Epβ(x|x̂) [ λ0x ] + log (∑ y e− ∑d r=1 λ r(y)Ar,β(x̂) ) .
From which it follows that λ0β(x̂) is given by:
λ0β(x̂) = log (∑ y e− ∑d r=1 λ r(y)Ar,β(x̂) ) ,
and we can conclude that the dualExpIB decoder takes the form:
log pβ(y | x̂) = − d∑ r=0 λr(y)Ar,β(x̂).
• The encoder, equation 15. The core of the encoder is the dual distortion function which may now be written as:
ddualIB(x, x̂) = ∑
y
pβ(y | x̂) log pβ(y | x̂) p(y | x)
= ∑
y
pβ(y | x̂) [( λ0x − λ0β(x̂) ) + d∑ r=1 λr(y)(Ar(x)−Ar,β(x̂)) ]
= λ0x − λ0β(x̂) + d∑ r=1 λrβ(x̂)(Ar(x)−Ar,β(x̂)),
substituting this into the encoder’s definition we obtain:
pβ(x̂ | x) = pβ(x̂)
Zx̂|x(x;β) e−β[λ 0 x−λ 0 β(x̂)+
∑d r=1 λ r β(x̂)[Ar(x)−Ar,β(x̂)]]
= pβ(x̂)eβλ
0 β(x̂)
Zx̂|x(x;β) e−β
∑d r=1 λ r β(x̂)[Ar(x)−Ar,β(x̂)].

Review summaries:
The information bottleneck (IB) is an information theoretic principle for optimizing a mapping (encoding, e.g. clustering) of an input, to trade off two kinds of mutual information: minimize mutual information between the original input and the mapped version (to compress the input), and maximize mutual information between the mapped input and an output variable. It is related to a minimization of an (expected) Kullback-Leibler divergence betwen conditional distributions of an output variable.

This paper proposes a new "dual" variant of the Information Bottleneck framework. The IB framework has been the subject of many papers in past years, with a focus on understanding the inner workings of deep learning. The framework poses machine learning as optimizing an internal representation to tradeoff between retaining less information about the input features and retaining more information about the output label (prediction). The existing framework measures the retained information about the prediction via mutual information, which can be expressed as a KL divergence. The new dual framework reverses the arguments of this divergence.