Compressed representations generalize better (Shamir et al., 2010), which may be crucial when learning from limited or noisy labeled data. The Information Bottleneck (IB) method (Tishby et al. (2000)) provides an insightful and principled approach for balancing compression and prediction in representation learning. The IB objective I(X; Z) − βI(Y ; Z) employs a Lagrange multiplier β to tune this trade-off. However, there is little theoretical guidance for how to select β. There is also a lack of theoretical understanding about the relationship between β, the dataset, model capacity, and learnability. In this work, we show that if β is improperly chosen, learning cannot happen: the trivial representation P(Z|X) = P(Z) becomes the global minimum of the IB objective. We show how this can be avoided, by identifying a sharp phase transition between the unlearnable and the learnable which arises as β varies. This phase transition defines the concept of IB-Learnability. We prove several sufficient conditions for IB-Learnability, providing theoretical guidance for selecting β. We further show that IB-learnability is determined by the largest confident, typical, and imbalanced subset of the training examples. We give a practical algorithm to estimate the minimum β for a given dataset. We test our theoretical results on synthetic datasets, MNIST, and CIFAR10 with noisy labels, and make the surprising observation that accuracy may be non-monotonic in β. Compressed representations generalize better (Shamir et al., 2010) , which is likely to be particularly important when learning from limited or noisy labels, as otherwise we should expect our models to overfit to the noise. Tishby et al. (2000) introduced the Information Bottleneck (IB) objective function which learns a representation Z of observed variables (X, Y ) that retains as little information about X as possible, but simultaneously captures as much information about Y as possible:min IB β (X, Y ; Z) = min I(X; Z) − βI(Y ; Z)I(X; Y ) = dx dy p(x, y)log p(x,y) p(x)p(y ) is the mutual information. The hyperparameter β controls the trade-off between compression and prediction, in the same spirit as Rate-Distortion Theory (Shannon, 1948) , but with a learned representation function P (Z|X) that automatically captures some part of the "semantically meaningful" information, where the semantics are determined by the observed relationship between X and Y .The IB framework has been extended to and extensively studied in a variety of scenarios, including Gaussian variables BID6 ), meta-Gaussians (Rey & Roth (2012) ), continuous variables via variational methods BID3 ; BID5 BID8 ), deterministic scenarios (Strouse & Schwab (2017a) ; BID12 ), geometric clustering (Strouse & Schwab (2017b) ), and is used for learning invariant and disentangled representations in deep neural nets BID0 b) ). However, a core issue remains: how should we select β? In the original work, the authors recommend sweeping β > 1, which can be prohibitively expensive in practice, but also leaves open interesting theoretical questions around the relationship between β, P (Z|X), and the observed data, P (X, Y ). For example, under how much label noise will IB at a given β still be able to learn a useful representation?This work begins to answer some of those questions by characterizing the onset of learning. Specifically:• We show that improperly chosen β may result in a failure to learn: the trivial solution P (Z|X) = P (Z) becomes the global minimum of the IB objective, even for β 1.• We introduce the concept of IB-Learnability, and show that when we vary β, the IB objective will undergo a phase transition from the inability to learn to the ability to learn.• Using the second-order variation , we derive sufficient conditions for IB-Learnability, which provide theoretical guidance for choosing a good β.• We show that IB-learnability is determined by the largest confident, typical, and imbalanced subset of the training examples, reveal its relationship with the slope of the Pareto frontier at the origin on the information plane I(Y ; Z) vs. I(X; Z), and discuss its relation with model capacity.We use our main results to demonstrate on synthetic datasets, MNIST (LeCun et al., 1998) , and CIFAR10 BID13 ) under noisy labels that the theoretical prediction for IB-Learnability closely matches experiment. We present an algorithm for estimating the onset of IB-Learnability, and demonstrate that it does a good job of estimating the theoretical predictions and the empirical results. Finally, we observe discontinuities in the Pareto frontier of the information plane as β increases, and those dicontinuities correspond to accuracy decreasing as β increases. In this paper, we have presented theoretical results for predicting the onset of learning, and have shown that it is determined by the largest confident, typical and imbalanced subset of the examples. We gave a practical algorithm for predicting the transition, and showed that those predictions are accurate, even in cases of extreme label noise. We have also observed a surprising non-monotonic relationship between β and accuracy, and shown its relationship to discontinuities in the Pareto frontier of the information plane. We believe these results will provide theoretical and practical guidance for choosing β in the IB framework for balancing prediction and compression. Our work also raises other questions, such as whether there are other phase transitions in learnability that might be identified. We hope to address some of those questions in future work.Mélanie Rey and Volker Roth. Meta-gaussian information bottleneck. In Advances in Neural Information Processing Systems, pp. 1916 Systems, pp. -1924 Systems, pp. , 2012 .Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. The structure of the Appendix is as follows. In Appendix A , we provide preliminaries for the first-order and secondorder variations on functionals. Then we prove Theorem 1 in Appendix B. In Appendix C, we state and prove Sufficient Condition 1 for IB β -learnability. In Appendix D , we calculate the first and second variations of IB β [p(z|x)] at the trivial representation p(z|x) = p(z), which is used in proving the Sufficient Condition 2 IB β -learnability (Appendix F). After these preparations, we prove the key result of this paper, Theorem 2, in Appendix G. Then two important corollaries 2.1, 2.2 are proved in Appendix H. We provide additional discussions and insights for Theorem 2 in Appendix I, and Algorithm 1 for estimation of an upper boundβ 0 ≥ β 0 in Appendix J. Finally in Appendix K, we provide details for the experiments. Similarity to information measures. The denominator of Eq. (2) is closely related to mutual information. Using the inequality x − 1 ≥ log(x ) for x > 0, it becomes: DISPLAYFORM0 whereĨ(Ω x ; Y ) is the mutual information "density" at Ω x ⊂ X . Of course, this quantity is also D KL [p(y|Ω x )||p(y) ], so we know that the denominator of Eq. FORMULA2 is non-negative. Incidentally , E y∼p (y|Ωx) p (y|Ωx) p(y) − 1 is the density of "rational mutual information" BID15 DISPLAYFORM1 Similarly, the numerator is related to the self-information of Ω x : DISPLAYFORM2 so we can estimate the phase transition as: DISPLAYFORM3 Since Eq. (22) uses upper bounds on both the numerator and the denominator, it does not give us a bound on β 0 .Multiple phase transitions. Based on this characterization of Ω x , we can hypothesize datasets with multiple learnability phase transitions. Specifically, consider a region Ω x0 that is small but "typical", consists of all elements confidently predicted as y 0 by p(y|x), and where y 0 is the least common class. By construction , this Ω x0 will dominate the infimum in Eq. (2), resulting in a small value of β 0 . However, the remaining X − Ω x0 effectively form a new dataset, X 1 . At exactly β 0 , we may have that the current encoder, p 0 (z|x), has no mutual information with the remaining classes in X 1 ; i.e., I(Y 1 ; Z 0 ) = 0. In this case, Definition 1 applies to p 0 (z|x) with respect to I(X 1 ; Z 1 ). We might expect to see that , at β 0 , learning will plateau until we get to some β 1 > β 0 that defines the phase transition for X 1 . Clearly this process could repeat many times, with each new dataset X i being distinctly more difficult to learn than X i−1 . The end of Appendix F gives a more detailed analysis on multiple phase transitions.Estimating model capacity. The observation that a model can't distinguish between cluster overlap in the data and its own lack of capacity gives an interesting way to use IB-Learnability to measure the capacity of a set of models relative to the task they are being used to solve. Learnability and the Information Plane. Many of our results can be interpreted in terms of the geometry of the Pareto frontier illustrated in FIG1 , which describes the trade-off between increasing I(Y ; Z) and decreasing I(X; Z). At any point on this frontier that minimizes IB min β ≡ min I(X; Z) − βI(Y ; Z), the frontier will have slope β −1 if it is differentiable. If the frontier is also concave (has negative second derivative), then this slope β −1 will take its maximum β −1 0 at the origin, which implies IB β -Learnability for β > β 0 , so that the threshold for IB β -Learnability is simply the inverse slope of the frontier at the origin. More generally, as long as the Pareto frontier is differentiable, the threshold for IB β -learnability is the inverse of its maximum slope. Indeed, Theorem 2 gives lower bounds of the slope of the Pareto frontier at the origin. This means that we lack IB β -learnability for β < β 0 , which makes the origin the optimal point. If the frontier is convex, then we achieve optimality at the upper right endpoint if β > β 1 , otherwise on the frontier at the location between the two endpoints where the frontier slope is β −1 .
Theory predicts the phase transition between unlearnable and learnable values of beta for the Information Bottleneck objective
{"src": "scitldr-AIC_train", "paper_id": "SJePKo5HdV"}