Source
Larsson, Maity & Tsiotras (2022), “A Generalized Information-Theoretic Framework for the Emergence of Hierarchical Abstractions”, Entropy, LIT-868, read in full in NOTE-676 from the PMC copy. Algorithms 1 and 2 are images and were not seen; they are known from the prose.
What was actually shown
Setting. X lives on the finest cells of a d-dimensional grid of side 2^ℓ; the encoder T is a deterministic pruning of the full quadtree, so I(T;X) = H(T). The objective weights relevant variables Y_i by β_i ≥ 0, irrelevant variables Z_j by γ_j ≥ 0, and compression by α ≥ 0.
Decomposition (Eqs. 13–21). Splitting a cell t adds p(t)·JS of the children’s conditionals p(y|t′) to the information about each variable, and p(t)·H(Π) to the rate. So the objective of any pruning is the sum of ΔJ over its interior nodes.
Recursion (Eq. 22, Lemmas 6–10, Theorem 11). G(t) = max{ΔJ(t) + Σ_children G(t′), 0}. Expanding a leaf iff G > 0 returns the optimal tree, every strict subtree of which is strictly worse, and that tree is unique. Cost is of order (n + m + 3) times the number of finest cells.
Greedy failure (§6.1, Fig. 4). A greedy search expands t only when β exceeds H(Π)/JS. In a symmetric 4 × 4 example JS = 0 at the root, so the greedy tree is the root alone for every β, although the grid holds relevant information below.
Nesting (Lemma 12, Corollary 13). For fixed β, every node the information-bottleneck-with-side-information search expands, the plain IB search also expands. NOTE-676 derives, by the same induction, that the trees are also nested across α.
What could have come out otherwise: the optimum over prunings could have needed a search over all subtrees. The decomposition makes it a single pass.
What this does not say
- That hierarchy is found in data. The quadtree is fixed in advance; the objective chooses only how deep to go in each region. Partitions that cut across its cells are excluded.
- That the objective respects shared or synergistic information. Each relevant variable’s information is counted separately, from pairwise marginals, so shared information is double counted and synergy among the Y_i is invisible. Penalising I(T;Z₁) and I(T;Z₂) separately does not bound I(T;Z₁,Z₂), so the privacy reading guarantees less than §4 suggests (NOTE-676’s observation).
- That the abstractions are useful for planning. One segmented road image, no baseline, no downstream task (C6, weak).
- How to choose the weights. They are set by hand.
- That it extends to general trees as proved. The authors say it “applies straightforwardly”; the proofs use only parent–child structure, but that is asserted, not shown.
Connections
- QUESTION-025 asks whether correlated or hierarchical attributes still give linear directions in an embedding. NOTE-676 judges this no answer, but one point carries: a level carries information about Y exactly where sibling cells differ, weighted by their mass, and it can sit below a level that carries none, so a test of recovered hierarchy should score each level, not only the first split.
- In colour naming (THEORY-163), annealing β finds a hierarchy by bifurcation with soft encoders; here the hierarchy is imposed and the nesting holds by construction.
- Saxe et al.’s tree case (THEORY-186) and CLAIM-119’s cross-cutting attributes mark what a partition hierarchy cannot represent.
- CLAIM-092’s designed objective, a weighted sum of separately computed mutual informations, has a precedent here, solved exactly over a structured encoder class.