Daniel T. Larsson, Dipankar Maity and Panagiotis Tsiotras (2022), Entropy 24(6):809 — DOI-10.3390/e24060809
Key takeaways
- A tree pruning is a deterministic encoder, and its information is a sum over nodes. With X the finest grid cells and T the leaves of a pruned quadtree, expanding a leaf t into children t′₁…t′₄ adds p(t)·JS_Π(p(y|t′₁), …, p(y|t′₄)) to I(T;Y), the same with Z to I(T;Z), and p(t)H(Π) to I(T;X), Π being the children’s shares of p(t). Starting from the single-node root (all terms zero), the objective of any pruning is the sum of these increments over its interior nodes (Eqs. 13–21).
- The exact optimum by one bottom-up pass. G(t) = max{ΔJ(t) + Σ_children G(t′), 0}, zero at the finest leaves. Expanding exactly the nodes with G > 0, from the root down, returns the optimal tree with the fewest leaves, for any non-negative weights (Theorem 11, via Lemmas 6–10). The cost is of order (n + m + 3) times the number of grid cells.
- Greedy splitting fails, and why. A node gains relevant information only when its children differ in what they predict about Y. In a 4 × 4 grid with one equally red cell in each quadrant, the root’s children are identical in p(y|·), so a greedy search never expands the root and keeps the trivial abstraction, though the grid holds relevant information at the next level (Figure 4). The recursion counts information to come.
- Plain IB and IB with side information as special cases, nested. The authors’ earlier Q-tree search (one relevance term, weight 1/β on compression) and an IBSI tree search are instances. For each β and γ, the IBSI tree is a subtree of the IB tree (Lemma 12, Corollary 13), and the IBSI recursion can be computed from the IB one plus the ΔI_Z terms alone (Proposition 15).
- Only pairwise marginals are used. Although the problem is stated over a joint p(x, y₁…y_n, z₁…z_m), every increment needs only p(x) and each p(y_i|x) or p(z_j|x) separately (§7). The objective is a weighted sum of separately computed mutual informations.
- The demonstration is one segmented 256 × 256 road image. Keeping the road class alone retains all its information with 1.42% of the finest nodes; keeping all six classes with no compression penalty retains every class with 5% (Figures 6 and 9). Irrelevant classes coarsen exactly the regions where they meet the relevant one.
Standing in the record
Filed on 2026-10-09 at the owner’s request, in the second part of the batch on hierarchy and hyperbolic geometry, which the owner asked for after the record opened QUESTION-025. That question asks whether correlated or hierarchical attributes in co-occurrence still give linear attribute directions, and a concept lattice that is not Boolean. It builds on THEORY-185 and LIT-863. The first part of the batch is Cagnetta et al.’s random hierarchy model (LIT-877), Krioukov et al. (2010, LIT-865), Sala et al. (2018, LIT-874), Lin et al. (2023, LIT-870), Zhang et al. (2023, LIT-876), Yang et al. (2023, LIT-871) and Ganea, Bécigneul and Hofmann (2018, LIT-866).
Like the random hierarchy model, and unlike the rest of the batch, it has no hyperbolic geometry. Its nearest siblings are the two built on coarse-graining across scales. Lin et al. recover an unknown tree from densities at dyadic scales. This paper takes the dyadic tree as given and asks which of its coarse-grainings to keep for a relevance variable. The renormalization paper of the second part (LIT-869) coarse-grains a network by blocks across scales. Here, one coarse-graining is chosen per region.
Read on 2026-10-09 (NOTE-676). It does not answer QUESTION-025: it has no embedding, no co-occurrence and no attributes, and the hierarchy is spatial and fixed in advance. It contributes two things the question can use. First, a level of a hierarchy carries relevant information only where siblings differ in what they predict, and information can sit deep in a tree while a top-down test at the root sees none. Second, it is a precedent outside translation for the designed objective of CLAIM-092, a weighted sum of separately computed mutual informations with several relevance variables, solved exactly over a structured encoder class. It is a third information-bottleneck reading beside Tishby, Pereira and Bialek (LIT-338) and Zaslavsky et al. on colour naming (LIT-810, THEORY-163).