The information bottleneck and geometric clustering
DJ Strouse David J Schwab
stat.ML cs.AI cs.IT cs.LG math.IT





The information bottleneck and geometric clustering
    DJ StrouseDepartment of Physics, Princeton University  & David J. SchwabInitiative for the Theoretical Sciences, CUNY Graduate Center
    December 30, 2023
=========================================================================================================================================


The information bottleneck (IB) approach to clustering takes a joint distribution P(X,Y) and maps the data X to cluster labels T which retain maximal information about Y <cit.>. This objective results in an algorithm that clusters data points based upon the similarity of their conditional distributions P(Y| X). This is in contrast to classic “geometric clustering” algorithms such as k-means and gaussian mixture models (GMMs) which take a set of observed data points {𝐱_i} _i=1:N and cluster them based upon their geometric (typically Euclidean) distance from one another. Here, we show how to use the deterministic information bottleneck (DIB) <cit.>, a variant of IB, to perform geometric clustering, by choosing cluster labels that preserve information about data point location on a smoothed dataset. We also introduce a novel method to choose the number of clusters, based on identifying solutions where the tradeoff between number of clusters used and spatial information preserved is strongest. We apply this approach to a variety of simple clustering problems, showing that DIB with our model selection procedure recovers the generative cluster labels. We also show that, in particular limits of our model parameters, clustering with DIB and IB is equivalent to k-means and EM fitting of a GMM with hard and soft assignments, respectively. Thus, clustering with (D)IB generalizes and provides an information-theoretic perspective on these classic algorithms.




§ INTRODUCTION


Unsupervised learning is a crucial component of building intelligent systems <cit.>, since such systems need to be able to leverage experience to improve performance even in the absence of feedback. One aspect of doing so is discovering discrete structure in data, a problem known as clustering <cit.>. In the typical setup, one is handed a set of data points {𝐱_i} _i=1^N, and asked to return a mapping from data point label i to a finite set of cluster labels c. The most basic approaches include k-means and gaussian mixture models (GMMs). GMMs cluster data based on maximum likelihood fitting of a probabilistic generative model. k-means can either be thought of as directly clustering data based on geometric (often Euclidean) distances between data points, or as a special case of GMMs with the assumptions of evenly sampled, symmetric, equal variance components.

The information bottleneck (IB) is an information-theoretic approach to clustering data X that optimizes cluster labels T to preserve information about a third “target variable” of interest Y. The resulting (soft) clustering groups data points based on the similarity in their conditional distributions over the target variable through the KL divergence, KL[p(y| x_i)| p(y| x_j)]. An IB clustering problem is fully specified by the joint distribution P(X,Y) and the tradeoff parameter β quantifying the relative preference for fewer clusters and more informative ones.

At first glance, it is not obvious how to use this approach to cluster geometric data, where the input is a set of data point locations {𝐱_i} _i=1^N. For example, what is the target variable Y that our clusters should retain information about? What should P(X,Y) be? And how should one choose the tradeoff parameter β?

<cit.> were the first to attempt to do geometric clustering with IB, and claimed an equivalence (in the large data limit) between IB and k-means. Unfortunately, while much of their approach is correct, it contained errors that nullify the main results. In the next section, we describe those errors and how to correct them. Essentially, their approach did not properly translate geometric information into a form that could be used correctly by an information-theoretic algorithm.

In addition to fixing this issue, we also choose to use a recently introduced variant of the information bottleneck called the deterministic information bottleneck (DIB) <cit.>. We make this choice due to the different way in which IB and DIB use the number of clusters provided to them. IB is known to use all of the clusters it has access to, and thus clustering with IB requires a search both over the number of clusters N_c as well as the the parsimony-informativeness tradeoff parameter β <cit.>. DIB on the other hand has a built-in preference for using as few clusters as it can, and thus only requires a parameter search over β. Moreover, DIB's ability to select the number of clusters to use for a given β leads to a intuitive model selection heuristic based on the robustness of a clustering result across β that we show can recover the generative number of clusters in many cases. 

In the next section, we more formally define the geometric clustering problem, the IB approach of <cit.>, and our own DIB approach. In section <ref>, we show that our DIB approach to geometric clustering behaves intuitively and is able to recover the generative number of clusters with only a single free parameter (the data smoothing scale s). In section <ref>, we discuss the relationship between our approach and k-means/GMMs, showing that in particular limits, clustering with DIB and IB is equivalent to k-means/EM fitting of a GMM with hard and soft assignments, respectively. Our approach thus provides a novel information-theoretic approach to geometric clustering, as well as an information-theoretic perspective on these classic clustering methods.



§ GEOMETRIC CLUSTERING WITH THE (DETERMINISTIC) INFORMATION BOTTLENECK 


In a geometric clustering problem, we are given a set of N observed data points {𝐱_i} _i=1:N and asked to provide a weighting q(c| i) that categorizes data points into (possibly multiple) clusters such that data points “near” one another are in the same cluster. The definition of “near” varies by algorithm: for k-means, for example, points in a cluster are closer to their own cluster mean than to any other cluster mean.

In an information bottleneck (IB) problem, we are given a joint distribution P(X,Y) and asked to provide a mapping q(t| x) such that T contains the “relevant” information in X for predicting Y. This goal is embodied by the information-theoretic optimization problem


    q_IB^*(t| x)     =  I(X,T)-β I(T,Y),

subject to the Markov constraint T↔ X↔ Y. β is a free parameter that allows for setting the desired balance between the compression encouraged by the first term and the relevance encouraged by the second; at small values, we throw away most of X in favor of a succinct representation for T, while for large values of β, we retain nearly all the information that X has about Y.

This approach of squeezing information through a latent variable bottleneck might remind some readers of a variational autoencoder (VAE) <cit.>, and indeed IB has a close relationship with VAEs. As pointed out in <cit.>, a variational version of IB can essentially be seen as the supervised generalization of a VAE, which is typically an unsupervised algorithm.

We are interested in performing geometric clustering with the information bottleneck. For the purposes of this paper, we will focus on a recent alternative formulation of the IB, called the deterministic information bottleneck (DIB) <cit.>. We do this because the DIB's cost function more directly encourages the use of as few clusters as possible, so initialized with n_c^max clusters, it will typically converge to a solution with far fewer. Thus, it has a form of model selection built in that will prove useful for geometric clustering <cit.>. IB, on the other hand, will tend to use all n_c^max clusters, and thus requires an additional search over this parameter <cit.>. DIB also differs from IB in that it leads to a hard clustering instead of a soft clustering.

Formally, the DIB setup is identical to that of IB except that the mutual information term I(X;T) in the cost functional is replaced with the entropy H(T)


    q_DIB^*(t| x)     =  H(T)-β I(T,Y).

This change to the cost functional leads to a hard clustering with the form <cit.>


    q_DIB^*(t| x)     =δ(t-t^*(x))
    
    t^*    =  log q(t)-βKL[p(y| x)| q(y| t)]
    
    q(t)     =∑_xq(t| x)p(x)
    
    q(y| t)     =1/q(t)∑_xq(t| x)p(x)p(y| x),

where the above equations are to be iterated to convergence from some initialization. The IB solution <cit.> simply replaces the first two equations with

    q_IB^*(t| x)     =q(t)/Z(x,β)exp[-βKL[p(y| x)| q(y| t)]],

which can be seen as replacing the argmax in DIB with a soft max.

The (D)IB is referred to as a “distributional clustering” algorithm <cit.> due to the KL divergence term d(x,t)=KL[p(y| x)| q(y| t)], which can be seen as measuring how similar the data point conditional distribution p(y| x) is to the cluster conditional, or mixture of data point conditionals, q(y| t)=∑_xq(x| t)p(y| x). That is, a candidate point x^' will be assigned to a cluster based upon how similar its conditional p(y| x^') is to the conditionals p(y| x) for the data points x that make up that cluster. Thus, both DIB and IB cluster data points based upon the conditionals p(y| x).

To apply (D)IB to a geometric clustering problem, we must choose how to map the geometric clustering dataset {𝐱_i} _i=1:N to an appropriate IB dataset P(X,Y). First, what should X and Y be? Since X is the data being clustered by IB, we'll choose that to be the data point index i. As for the target variable Y that we wish to maintain information about, it seems reasonable to choose the data point location 𝐱 (though we will discuss alternative choices later). Thus, we want to cluster data indices i into cluster indices c in a way that maintains as much possible info about the location 𝐱 as possible <cit.>.

Now, how should we choose the joint distribution p(i,𝐱)=p(𝐱| i)p(i)? At first glance, one might choose p(𝐱| i)=δ_𝐱𝐱_i, since data point i was observed at location 𝐱_i. The reason not to do this lies with the fact that (D)IB is a distributional clustering algorithm, as discussed two paragraphs above. Data points are compared to one another through their conditionals p(𝐱| i), and with the choice of a delta function, there will be no overlap unless two data points are on top of one another. That is, choosing p(𝐱| i)=δ_𝐱𝐱_i leads to a KL divergence that is either infinite for data points at different locations, or zero for data points that lie exactly on top of one another, i.e. KL[p(x| i)| p(x| j)]=δ_𝐱_i𝐱_j. Trivially, the resulting clustering would assign each data point to its own cluster, grouping only data points that are identical. Put another way, all relational information in an IB problem lies in the joint distribution P(X,Y). If one wants to perform geometric clustering with an IB approach, then geometric information must somehow be injected into that joint distribution, and a series of delta functions does not do that. A previous attempt at linking IB and k-means made this mistake <cit.>. Subsequent algebraic errors were tantamount to incorrectly introducing geometric information into IB, precisely in the way that such geometric information appears in k-means, and resulting in an algorithm that is not IB. We describe these errors in more detail in section <ref>.

Based on the problems identified with using delta functions, a better choice for the conditionals is something spatially extended, such as:

    p(𝐱| i)    ∝exp[-1/2s^2d(𝐱,𝐱_i)],

where s sets the geometric scale or units of distance, and d is a distance metric, such as the Euclidean distance d(𝐱,𝐱_i)=‖𝐱-𝐱_i‖ ^2. If we indeed use the Euclidean distance, then p(𝐱| i) will be (symmetric) gaussian (with variance s^2), and this corresponds to gaussian smoothing our data. In any case, the obvious choice for the marginal is p(i)=1/N, where N is the number of data points, unless one has a reason a priori to favor certain data points over others. These choices for p(i) and p(𝐱| i) determine completely our dataset p(i,𝐱)=p(𝐱| i)p(i). Figure <ref> contains an illustration of this data smoothing procedure. We will explore the effect of the choice of smoothing scale s throughout this paper.



With the above choices, we have a fully specified DIB formulation of a geometric clustering problem. Using our above notational choices, the equations for the n^th step in the iterative DIB solution is <cit.>


    q^(n)(c| i)     =δ(c-c^*(n)(i))
    
    c^*(n)(i)    ≡  log q^(n-1)(c)-βKL[p(𝐱| i)| q^(n-1)(𝐱| c)]
    
    q^(n)(c)     =n_c^(n)/N
    
    q^(n)(𝐱| c)     =∑_iq^(n)(i| c)p(𝐱| i) =1/n_c^(n)∑_i∈ S_c^(n)p(𝐱| i),

where S_c^(n)≡{ i: c^* (n)(i )=c } is the set of indices of data points assigned to cluster c at step n, and n_c^(n)≡| S_c^(n)| is the number of data points assigned to cluster c at step n. This process is summarized in algorithm <ref>.



Note that this solution contains β as a free parameter. As discussed above, it allows us to set our preference between solutions with fewer clusters and those that retain more spatial information. It is common in the IB literature to run the algorithm for multiple values of β and to plot the collection of solutions in the “information plane” with the relevance term I(Y;T) on the y-axis and the compression term I(X;T) on the x-axis <cit.>. The natural such plane for the DIB is with the relevance term I(Y;T) on the y-axis and its compression term H(T) on the x-axis <cit.>. The curve drawn out by (D)IB solutions in the information plane can be viewed as a Pareto-optimal boundary of how much relevant information can be extracted about Y given a fixed amount of information about X (IB) or representational capacity by T (DIB) <cit.>. Solutions lying below this curve are of course suboptimal, but a priori, the (D)IB formalism doesn't tell us how to select a single solution from the family of solutions lying on the (D)IB boundary. Intuitively however, when faced with a boundary of Pareto-optimality, if we must pick one solution, its best to choose one at the “knee” of the curve. Quantitatively, the “knee” of the curve is the point where the curve has its maximum magnitude second derivative. In the most extreme case, the second derivative is infinite when there is a “kink” in the curve, and thus the largest kinks might correspond to solutions of particular interest. In our case, since the slope of the (D)IB curve at any given solution is β^-1 (which can be read off from the cost functionals), kinks also indicate solutions that are valid over a wide range of β. So large kinks additionally correspond to solutions robust to model hyperparameters, in the sense that they optimize a wide range of (D)IB tradeoffs. Such robust solutions should correspond to ”real” structure in the data. Quantitatively, we can measure the size of a kink by the angle θ of the discontinuity it causes in the slope of the curve; see figure <ref> for details. We will show in the next section that searches for solutions with large θ result in recovering the generative cluster labels for geometric data, including the correct number of clusters.

Note that this model selection procedure would not be possible if we had chosen to use IB instead of DIB. IB uses all the clusters available to it, regardless of the choice of β. Thus, all solutions on the curve would have the same number of clusters anyway, so any knees or kinks cannot be used to select the number of clusters.


 


§ RESULTS: GEOMETRIC CLUSTERING WITH DIB


We ran the DIB as described above on four geometric clustering datasets, varying the smoothing width s (see eqn <ref>) and tradeoff parameter β, and measured for each solution the fraction of spatial information extracted Ĩ(c;𝐱)=I(c;𝐱)/I(i;𝐱)[Note that I(i;𝐱) is an upper bound on I(c;𝐱) due to the data processing inequality,<cit.> so Ĩ(c;𝐱) is indeed the fraction of potential geometric information extracted from the smoothed P(i,𝐱).] and the number of clusters used n_c , as well as the kink angle θ. We iterated the DIB equations above just as in <cit.> with one difference. Iterating greedily from some initialization can lead to local minima (the DIB optimization problem is non-convex). To help overcome suboptimal solutions, upon convergence, we checked whether merging any two clusters would improve the value L of the cost functional in eqn <ref>. If so, we chose the merging with the highest such reduction, and began the iterative equations again. We repeated this procedure until the algorithm converged and no merging reduced the value of L. We found that these “non-local” steps worked well in combination with the greedy “local” improvements of the DIB iterative equations. While not essential to the function of DIB, this improvement in performance produced cleaner information curves with less “noise” caused by convergence to local minima. Similar to <cit.>, the automated search over β began with an initial set of values, and then iteratively inserted more values where there were large jumps in H(c), I(c;𝐱), or the number of clusters used, or where the largest value of β did not lead to a clustering solution capturing nearly all of the available geometric information (that is, with I(c;𝐱)≈ I(i;𝐱). For more details, see our code repository at https://github.com/djstrouse/information-bottleneckhttps://github.com/djstrouse/information-bottleneck.



Results are shown in figure <ref>. Each large row represents a different dataset. The left column shows fractional spatial information Ĩ(c;𝐱) versus number of clusters used n_c,[Note that this is not the same as the n_c in eqns <ref> and <ref>, which was the number of data points assigned to a particular cluster c. Here we are using it to denote the number of clusters with at least one data point assigned to it.] stacked by smoothing width s.[Note that this is not the same as the information plane curve from figure <ref>. While the y-axes are the same (up to the normalization), the x-axes are different.] The center column shows the kink angle θ for each cluster number n_c, again stacked by smoothing width s. Finally, the right column shows example solutions.

In general, note that as we increase β, we move right along the plots in the left column, that is towards higher number of clusters n_c and more spatial information Ĩ(c;𝐱). Not all values of n_c are present because while varying the implicit parameter β, DIB will not necessarily “choose” to use all possible cluster numbers. For example, for small smoothing width s, most points won't have enough overlap in p(𝐱| i) with their neighbors to support solutions with few clusters, and for large smoothing width s, local spatial information is thrown out and only solutions with few clusters are possible. More interestingly, DIB may retain or drop solutions based on how well they match the structure of the data, as we will discuss for each dataset below. Additionally, solutions that match well the structure in the data (for example, ones with n_c matched to the generative parameters) tend to be especially robust to β, that is they have a large kink angle θ. Thus, θ can be used to perform model selection. For datasets with structure at multiple scales, the kink angle θ will select different solutions for different values of the smoothing width s. This allows us to investigate structure in a dataset at a particular scale of our choosing. We now turn to the individual datasets.

The first dataset (top row) consists of 3 equally spaced, equally sampled symmetric gaussian clusters (see solutions in right column). We see that the 3-cluster solution stands out in several ways. First, it is robust to spatial scale s. Second, the 3-cluster solution extract nearly all of the available spatial information; solutions with n_c≥4 extract little extra Ĩ(c;𝐱). Third and perhaps most salient, the 3-cluster solution has by far the largest value of kink angle θ across a wide range of smoothing scales. In the right column, we show examples of 3 and 4-cluster solutions. Note that while all 3-cluster solutions look exactly like this one, the 4-cluster solutions vary in how they chop one true cluster into two.

The second dataset (second row) consists of 3 more equally sampled symmetric gaussian clusters, but this time not equally spaced; two are much closer to one another than the third. This is a dataset with multiple scales present, thus we should expect that the number of clusters picked out by any model selection procedure, e.g. kink angle, should depend on the spatial scale of interest. Indeed, we see that to be true. The 3-cluster solution is present for all smoothing widths shown, but is only selected out as the best solution by kink angle for intermediate smoothing widths (s=2). For large smoothing widths] (s=8), we see that the 2-cluster solution is chosen as best. For smoothing widths in between (s=4), the 2 and 3-cluster solutions are roughly equally valid. In terms of spatial information, the 2 and 3-cluster solutions are also prominent, with both transitions from n_c=1→2 and n_c=2→3 providing significant improvement in Ĩ(c;𝐱) (but little improvement for more fine-grained clusterings).

The third dataset (third row) features even more multi-scale structure, with 5 symmetric, equally sampled gaussians, again with unequal spacing. Sensible solutions exist for n_c=2-5, and this can be seen by the more gradual rise of the fractional spatial information Ĩ(c;𝐱) with n_c in that regime. We also again see a transition in the model selection by θ from the 5-cluster solution at small smoothing widths (s=1,2) and the 2-cluster solution at larger smoothing widths (s=8), with intermediate n_c favoring those and intermediate solutions. Example clusters for n_c=2-5 are shown at right.

Finally, we wanted to ensure that DIB and our model selection procedure would not hallucinate structure where there is none, so we applied it to a single gaussian blob, with the hope that no solution with n_c>1 would stand out and prove robust to β. As can be seen in the fourth row of figure <ref>, that is indeed true. No solution at any smoothing width had particularly high kink angle θ, and no solution remained at the “knee” of the Ĩ(c;𝐱) versus n_c curve across a wide range of smoothing widths.

Overall, these results suggest that DIB on smoothed data is able to recover generative geometric structure at multiple scales, using built-in model selection procedures based on identifying robust, spatially informative solutions.




§ RELATIONSHIP BETWEEN (D)IB AND GMMS & K-MEANS



It is natural to wonder how the algorithm we introduce here, clustering with DIB, relates to classic approaches to clustering, including GMMs and k-means. We now establish the following equivalence: when the smoothing scale s is small, β=1, and q(𝐱| c) is approximated as a gaussian r(𝐱| c) whose parameters are chosen to minimize KL[p(𝐱| c)| r(𝐱| c)], DIB and IB correspond to EM-fitting of a GMM with hard and soft assignments, respectively. When s is small and r(𝐱| c) is chosen to be an isotropic gaussian with fixed variance across clusters, DIB and IB correspond to hard and soft k-means, respectively, with a logarithmic ”cluster size bonus” weighted by β^-1. In the β→∞ limit, the effect of the cluster size bonus vanishes and the correspondence with hard and soft k-means is exact. Thus, clustering with (D)IB can be viewed as a generalization of these approaches.

We begin by establishing the correspondence between DIB and the E-step of fitting a GMM. Consider the KL divergence KL[p(𝐱| i)| q(𝐱| c)] that (D)IB uses to cluster data points. When the smoothing scale s is chosen to be small relative to the scale of q(𝐱| c), then we have

    KL[p(𝐱| i)| q(𝐱| c)]   =-∫ p(𝐱| i)log q(𝐱| c)d𝐱-H[p(𝐱| i)]
       ≈-log q(𝐱_i| c)∫ p(𝐱| i)d𝐱-H[p(𝐱| i)]
       =-log q(𝐱_i| c)-H[p(𝐱| i)],

where we have used the assumption about the scale of s in moving from the first to second line. Since H[p(𝐱| i)] is independent of the cluster assignments, minimizing KL[p(𝐱| i)| q(𝐱| c)] with respect to the cluster assignments is then equivalent to maximizing log q(𝐱_i| c), that is choosing a maximum likelihood assignment of points to clusters. Thus eqn <ref> becomes

    c^*(i)   =  log p(c)+βlog p(𝐱_i| c)
       =  log p(c)^1/β+log p(𝐱_i| c).

For β=1, the two log probabilities combine and lead to a maximum a posteriori (MAP) assignment of points to clusters

    c^*(i)   =  log p(𝐱_i,c)=  p(c|𝐱_i).

For 1 < β < ∞, the effect of β is to ”soften” the prior p(c) (eqn <ref>), leading to less aggressive cluster consolidation.

Of course, if we use the exact q(𝐱| c) defined in eqn <ref>, then the scales of p(𝐱| i) and q(𝐱| c) are similar, and so our assumption in this section is not valid. In order for it to be valid, we need to replace the exact q(𝐱| c) with an assumed parametric form that leads to further smoothing.

If we choose to replace q(𝐱| c) with a gaussian approximation r(𝐱| c)=𝒩(𝐱|μ_c,Σ_c), then eqn <ref> corresponds to the E-step in EM fitting of a GMM <cit.>. Note that ideally we would like for it to be true that KL[p(𝐱| i)| r(𝐱| c)]≥KL[p(𝐱| i)| q(𝐱| c)] so that the replacement of q(𝐱| c) by r(𝐱| c) leads to us maximizing a lower bound on our original objective (i.e. that which is maximized in eqn <ref>), however this is not generically true and KL[p(𝐱| i)| r(𝐱| c)] might be smaller or larger than KL[p(𝐱| i)| q(𝐱| c)].

The results in this section are only valid for a ”small” smoothing scale s, so let us now understand what that means in the particular case of gaussian r(𝐱| c). Consider the KL divergence in the assignment step (eqn <ref>), which in this case has a simple expression

    KL[p(𝐱| i)| r(𝐱| c)]   ∝s^2/(Σ_c)+(μ_c-𝐱_i)^TΣ_c^-1(μ_c-𝐱_i)+logΣ_c+k,

where k denotes terms not dependent on the assignment of points to clusters, and thus irrelevant for the objective. Compare to the maximum likelihood objective. The negative log likelihood of 𝐱_i under r(𝐱| c) is

    -log𝒩( 𝐱_i|μ_c, Σ_c)    ∝( μ_c - 𝐱_i)^TΣ_c^-1( μ_c - 𝐱_i) + log(Σ_c)+k,

where k again denotes terms independent of the assignment of points to clusters, and thus ignorable. Note that when s^2≪(Σ_c), the last two equations are the same, and thus the DIB cluster assignments correspond to maximum likelihood assignments. Thus, ”small” s means s^2≪(Σ_c) in this case. Of course, we don't know (Σ_c) until after we cluster our data, but it is set by the natural length scales in the data, so we can take it to mean that s needs to be small compared to those.

That establishes the correspondence for the E-step of EM fitting of a GMM, but what about the M-step? Note that we haven't yet specified how to fit the approximation r(𝐱| c)≈ q(𝐱| c). One reasonable way that appears often in the variational inference literature (e.g. <cit.>) is to choose the parameters of r(𝐱| c) (μ_c and Σ_c) that minimize KL[p(𝐱| c)| r(𝐱| c)]. We choose this direction of the KL divergence because it encourages a ”mean-seeking” approximation of p(𝐱| c) that tries better to approximate the full distribution than the other, ”mode-seeking” direction. While this is again a generally intractable KL divergence between a mixture of gaussians and a gaussian, fortunately in the s^2≪(Σ_c) limit that we consider, it simplifies to

    KL[p(𝐱| c)| r(𝐱| c)]   =-∫ p(𝐱| c)log r(𝐱| c)d𝐱-H[p(𝐱| c)]
       =-1/n_c∫∑_i∈ S_c𝒩(𝐱;𝐱_i,s^2)log r(𝐱| c)d𝐱-H[p(𝐱| c)]
       ≈-1/n_c∑_i∈ S_clog r(𝐱_i| c)∫𝒩(𝐱;𝐱_i,s^2)d𝐱-H[p(𝐱| c)]
       =-1/n_c∑_i∈ S_clog r(𝐱_i| c)-H[p(𝐱| c)],

where we move from the second to third line using the small s approximation (so that r(𝐱| c)≈ r(𝐱_i| c) in the region of 𝐱 where the bulk of 𝒩(𝐱;𝐱_i,s^2) is). Minimizing eqn <ref> with respect to μ_c and Σ_c again corresponds to maximum likelihood assignments, this time of the model parameters rather than cluster assignments. This corresponds to the M-step of EM fitting of a GMM <cit.>.

Thus, for β=1, small s, and a gaussian approximation of p(𝐱| c) (with parameters chosen to minimize the KL divergence in eqn <ref>), clustering with DIB is equivalent to EM fitting of a GMM with hard assignments (of data points to clusters). For β > 1, the effect of the cluster prior p(c) is muted; that is, it is replaced with p(c)^1/β.

If we set all cluster conditional approximations to have the same isotropic covariance Σ_c=diag(σ^2), then c^*(i) becomes (plugging eqn <ref> into eqn <ref>)

    c^*(i)   =  σ^2/βlog p(c)-‖𝐱_i-μ_c‖ ^2
       =  σ^2/βlog n_c-‖𝐱_i-μ_c‖ ^2,

which corresponds to (hard) k-means with a cluster size bonus log n_c (where n_c≡| S_c| is the number of points assigned to cluster c, as introduced in section <ref>). In the β→∞ limit, the log n_c term can be ignored and the correspondence with (hard) k-means is exact.

To see the correspondence between GMMs/k-means and IB, consider that IB can be viewed as DIB with the hard max replaced by a soft max (see eqn <ref>.) Thus, the same correspondences we drew between DIB and GMMs/k-means with hard assignments hold for IB and GMMs/k-means with soft assignments.

The correspondence between clustering with (D)IB and GMMs yields new interpretations of both. From this perspective, clustering with (D)IB can be viewed as a generalization of GMMs that 1) uses a more flexible, nonparametric representation of the clusters, 2) includes an extra parameter β for controlling the tradeoff between the prior and likelihood, and 3) includes an extra parameter s for setting the length scale of interest. In the other direction, GMMs can be viewed as mapping data points to cluster labels that maximally preserve spatial information.

This is not the first correspondence between IB in a particular setting and another probabilistic model. In the discrete setting, IB has been shown to be related to EM fitting of a multinomial mixture model <cit.>. In the time series setting (where X=x_t and Y=x_t+1), IB is related to canonical correlation analysis <cit.>, and therefore linear gaussian models <cit.> and slow feature analysis <cit.>. Under a variational approximation, IB applied to unsupervised learning is related to a variational autoencoder (VAE) <cit.>.



































§ DISCUSSION


Here, we have shown how to use the formalism of the information bottleneck to perform geometric clustering. A previous paper <cit.> claimed to contribute similarly, however for the reasons discussed in sections <ref> and <ref>, their approach contained fundamental flaws. We amend and improve upon that paper in four ways. First, we show to fix the errors they made in their problem setup (with the data preparation). Second, we argue for using DIB over IB in this setting for its preference for using as few clusters as it can. Third, we introduce a novel form of model selection for the number of clusters based on discontinuities (or “kinks”) in the slope of the DIB curve, which indicate solutions that are robust across the DIB tradeoff parameter β. We show that this information-based model selection criterion allows us to correctly recover generative structure in the data at multiple spatial scales. Finally, we establish the correct correspondence between clustering with (D)IB and k-means/GMMs, thus providing both a generalization and information-theoretic interpretation of these classic approaches.

We have introduced one way of doing geometric clustering with the information bottleneck, but we think it opens avenues for other ways as well. First, the uniform smoothing we perform above could be generalized in a number of ways to better exploit local geometry and better estimate the “true” generative distribution of the data. For example, one could do gaussian smoothing with mean centered on each data point but the covariance estimated by the sample covariance of neighboring data points around that mean. Indeed, our early experiments with this alternative suggest it may be useful for certain datasets. Second, while choosing spatial location as the relevant variable for DIB to preserve information about seems to be the obvious first choice to investigate, other options might prove interesting. For example, preserving information about the identity of neighbors, if carefully formulated, might make fewer implicit assumptions about the shape of the generative distribution, and enable the extension of our approach to a wider range of datasets.

Scaling the approach introduced here to higher-dimensional datasets is non-trivial because the tabular representation used in the original IB <cit.> and DIB <cit.> algorithms leads to an exponential scaling with the number of dimensions. Recently, however, <cit.> introduced a variational version of IB, in which one parameterizes the encoder q(t| x) (and “decoder” q(y| t)) with a function approximator, e.g. a deep neural network. This has the advantage of allowing scaling to much larger datasets. Moreover, the choice of parameterization often implies a smoothness constraint on the data, relieving the problem encountered above of needing to smooth the data. It would be interesting to develop a variational version of DIB, which could then be used to perform information-theoretic clustering as we have done here, but on larger problems and perhaps with no need for data smoothing.



§ APPENDIX: ERRORS IN <CIT.>


A previous attempt was made to draw a connection between IB and k-means <cit.>. Even before reviewing the algebraic errors that lead their result to break down, there are two intuitive reasons why such a claim is unlikely to be true. First, IB is a soft clustering algorithm, and k-means is a hard clustering algorithm. Second, the authors made the choice not to smooth the data and to set p(𝐱| i)=δ_𝐱𝐱_i. As discussed in section <ref>, (D)IB clusters data points based on these conditionals, and delta functions trivially only overlap when they are identical.

The primary algebraic mistake appears just after eqn 14, in the claim that p_n(𝐱| c)∝ p_n-1(𝐱| c)^1/λ. Combining the previous two claims in that proof, we obtain:

    p_n(𝐱| c)     =1/N∑_iδ_𝐱𝐱_i/Z_n(i,λ)p_n-1(𝐱_i| c)^1/λ.


Certainly, this does not imply that p_n(𝐱| c)∝ p_n-1(𝐱| c)^1/λ everywhere, because of the δ_𝐱𝐱_i factor which picks out only a finite number of points.

One might wonder why with these mistakes, the authors still obtain an algorithm that looks and performs like k-means. The reason is because their sequence of mistakes leads to the result in eqn 15 that effectively assumes that IB has access to geometric information it should not, namely the cluster centers at step n. Since these are exactly what k-means uses to assign points to clusters, it is not surprising that the behavior then resembles k-means.



§ ACKNOWLEDGEMENTS


We would like to thank Lon Bottou and Arthur Szlam for useful discussions. We would also like to acknowledge financial support from the NSF, through the Center for the Physics of Biological Function (PHY-1734030) (Schwab), the Simons Foundation (Schwab), and the Hertz Foundation (Strouse).

apa


