Semantic Compression with Information Lattice Learning

Haizi Yu, Lav R. Varshney

Researchers at the University of Illinois Urbana-Champaign have revisited Claude Shannon's 1953 work on information theory to address a contemporary challenge: semantic compression. Unlike traditional methods that focus on bit-level reconstruction, Information Lattice Learning (ILL) provides a framework for compressing data based on its underlying meaning.

The Shift Toward Semantic Communication

Standard compression algorithms like ZIP or JPEG prioritize minimizing error in bit or pixel reconstruction. However, the emerging paradigm of "semantic communication," particularly relevant for 6G systems, aims to transmit the core intent or proposition of a message. Defining "meaning" mathematically has historically been difficult. While Large Language Models (LLMs) can compress text, they often operate as "black boxes." ILL offers a transparent, mathematically grounded alternative by treating abstraction as a formal operation.

Shannon’s Lattice Theory of Information

The ILL framework is built upon Shannon’s concept of "information elements"—equivalence classes of variables that convey the same information. These elements are organized into a lattice based on a partial order of "coarseness."

  • Projection (Down): Moving to lower lattice levels to extract coarser, summarized signals (lossy compression).
  • Lifting (Up): Moving to higher levels to reconstruct finer details (decompression).

The authors demonstrate that these lattices are isomorphic to subgroup lattices in group theory, allowing the use of permutation source codes to achieve rate-distortion optimality.

Experimental Validation

The paper evaluates the ILL framework across two structured domains: geometric shapes and music theory.

Geometric Shapes

The system categorizes polygons based on attributes like color, convexity, and the number of sides. The lattice structure allows for hierarchical abstraction, where a specific red convex trigon can be progressively coarsened into a general "red shape" or a "trigon."

Hierarchical abstraction of geometric shapes based on color, convexity, and side count.

Music Theory

Using 370 Bach chorales for training, the researchers demonstrated hierarchical compression on an excerpt from Mozart’s Piano Sonata No. 16. By traversing the lattice, the system can selectively drop information—such as pitch, arpeggiation, or key—while retaining the fundamental harmonic or rhythmic structure.

Semantic compression of a Mozart sonata excerpt by progressively dropping specific musical features.

Key Insights

  • Meaning as Equivalence: A proposition is defined as a point in a lattice. Different expressions of the same idea map to the same mathematical element.
  • Abstraction as Compression: Abstraction is the physical act of projecting a signal onto a coarser lattice element. This framework makes the process explicit and measurable.
  • Interpretability: Unlike neural networks, ILL's compression paths are human-readable. One can explicitly observe the system deciding which features (like musical inversions) to discard while preserving others (like harmonic function).
  • Progressive Transmission: The authors proved that sending a coarse summary followed by refinements is as efficient as sending the full data at once, with no "rate loss."

Results and Future Directions

The ILL process successfully recovered standard music theory laws from the Bach dataset in a human-interpretable form. Mathematically, the paper proves that using sub-permutation codes for successive refinement achieves the optimal rate-distortion limit.

While highly effective for structured data like music and geometry, scaling ILL to unstructured data (e.g., natural language or video) remains a significant engineering challenge. Future work will focus on defining underlying symmetries for more complex, abstract human concepts to build broader information lattices.

Summary updated

Abstract

Data-driven artificial intelligence (AI) techniques are becoming prominent for learning in support of data compression, but are focused on standard problems such as text compression. To instead address the emerging problem of semantic compression, we argue that the lattice theory of information is particularly expressive and mathematically precise in capturing notions of abstraction as a form of lossy semantic compression. As such, we demonstrate that a novel AI technique called information lattice learning, originally developed for knowledge discovery and creativity, is powerful for learning to compress in a semantically-meaningful way. The lattice structure further implies the optimality of group codes and the successive refinement property for progressive transmission.
BibTeX
@inproceedings{yu2024semantic,
  author = {Haizi Yu and Lav R. Varshney},
  title = {{Semantic Compression with Information Lattice Learning}},
  booktitle = {LCW @ ISIT},
  year = {2024},
  url = {https://openreview.net/forum?id=Me4WnG7YXc},
}
Figure