nucleation

QUESTION-291: For finite X and Y, does every finite-budget information-bottleneck optimum nest under the β → ∞ optimum, what test on a pair of optimal encoders decides whether two finite budgets nest, and do the optima nest at every pair of budgets when Y is a function of X or when X and Y are both binary?

2 min read

Properties5
StatusAnswered
Tagsinformation-theory, learning-theory, representation-learning
Linelearned-structure
RefinesQUESTION-220 — Given that information-bottleneck optima at two budgets need not be nested, what condition on P(X, Y), beyond Y a function of X or X and Y both binary, guarantees that the coarser optimum is a (possibly noisy) function of the finer, X → Z₂ → Z₁, and how much is lost by forcing nesting when it fails?
Cited as “answers” byTHEORY-743 — For finite X and Y, every information-bottleneck optimum at every β gives one encoder to all inputs sharing p(y|x), so it is a stochastic coarsening of the minimal sufficient partition (the causal states of memoryless transduction); as β → ∞ the optima converge to that partition, but in general no finite β attains it, except when Y is a function of X, THEORY-753 — For finite X and Y, the information bottleneck is successively refinable from budget λ₁ to λ₂ > λ₁ iff some pair of optimal encoders forms a Markov chain X → T₂ → T₁, that is, iff the coarse optimal encoder is a garbling of a fine one; when the fine optimum's decoder points q(X|t₂) are affinely independent, this holds for that pair iff every decoder point q(X|t₁) of the coarse optimum lies in their convex hull, so a failed hull test on optima that are unique up to merging and relabelling proves that refinement fails, THEORY-757 — The information bottleneck is successively refinable between every pair of budgets when Y is a function of X, by nested erasures of Y, and when X and Y are both binary, where the optimum at each nonzero budget is unique up to merging and relabelling and its two decoder points are the ends of an interval of the source simplex that only widens as the budget grows

Graph View

The question

QUESTION-220 asks what condition on P(X, Y) guarantees that the information-bottleneck optimum at a coarser budget is a (possibly noisy) function of the optimum at a finer one. Three parts of that are settled: nesting under the top level, the test for a given pair of budgets, and two classes of distribution where nesting always holds.

The answer

  • Under the top level, yes. THEORY-743, Active: every IB optimum at every β gives one encoder to all inputs sharing p(y|x), so it is a stochastic coarsening of the minimal sufficient partition, the β → ∞ limit.
  • The test. THEORY-753, Active: the bottleneck is refinable from λ₁ to λ₂ > λ₁ iff some pair of optimal encoders forms X → T₂ → T₁, that is, iff the coarse encoder is a garbling of a fine one. With affinely independent fine decoder points this is a convex-hull inclusion that a linear programme decides.
  • Two classes, yes. THEORY-757, Active: refinable at every pair of budgets when Y is a function of X, by nested erasures of Y, and when X and Y are both binary. Binary Y alone does not suffice.

A condition on P(X, Y) beyond these cases, and the size of the loss when nesting fails, remain QUESTION-220’s.

Backlinks