Kolmogorov Complexity Estimation

Description

Estimates the irreducible complexity of an interface or interaction by its shortest description, using compression or rule-length proxies to separate essential from accidental complexity.

Kolmogorov complexity is the length of the shortest program that produces a given object. It is uncomputable in general, but practical estimates use compression ratios or the minimum description length of a structure. In UX the idea is to ask how short a complete description of an interface's behaviour or layout can be. A screen governed by a few consistent rules compresses well; one full of exceptions does not. The method estimates complexity from serialised layouts, design-system rule sets or interaction state models, for example by compressing a structured description or counting rules and exceptions needed to specify behaviour. Rigour comes from using a consistent representation across compared designs and correlating estimates with user performance, since compressibility is a proxy for learnability rather than a direct user measure.

Attributes

Loss type
Latent
Effort
Days

Steps

  1. Choose a consistent representation: serialised layout trees, a state machine of interactions, or a rule-and-exception specification.
  2. Encode each design variant in that representation at the same level of detail.
  3. Estimate complexity via compressed size (e.g. gzip or LZMA) or by counting rules plus exceptions needed for a full description.
  4. Separate essential complexity (required by the domain) from accidental complexity (inconsistencies and exceptions).
  5. Compare variants and correlate estimates with learnability or error data from users where available.
  6. Target the exceptions that contribute most to description length for simplification.

Sources

  • Information Theory Inference and Learning Algorithms
  • MacKay (Information Theory)
  • Kolmogorov via MIT Press
  • Shannon's works
  • An Introduction to Kolmogorov Complexity and Its Applications (Li & Vitányi)
  • The Inquiry Series, Ch 1 — Entropy, Complexity & the Information Architecture of Interaction

Also known as

  • Kolmogorov Complexity
  • Kolmogorov complexity measurement
  • Minimum description length analysis
  • Compression-based complexity

Categories

  • Information Theory, Physics & Mathematics