Minimum description length estimation

Description

Estimates interface complexity as the length of the shortest description needed to specify it, approximated by compression, to compare designs' structural regularity objectively.

Kolmogorov complexity defines the complexity of an object as the length of the shortest program that produces it; it is uncomputable, but the minimum description length principle approximates it by the shortest two-part code (model plus data given model). In UX the object is a layout, a navigation structure or an interaction grammar. A design built from a few consistent rules has a short description; a design full of exceptions has a long one. Practically, analysts encode screens or task flows in a structured representation and use a general compressor (gzip, LZMA) or a hand-built grammar to estimate description length, then compare variants. The rigour lies in fixing the encoding scheme before comparing, using normalised compression distance for pairs, and treating results as relative rankings, not absolute truths.

Attributes

Loss type
Unmigrated
Effort
Days

Steps

  1. Choose the object to measure (screen layouts, navigation graph, command grammar) and define a fixed, documented serialisation format for it.
  2. Serialise each design variant identically, removing incidental noise such as IDs and timestamps.
  3. Compress each serialisation with at least two compressors (for example gzip and LZMA) and record compressed size; use the ratio compressed/raw as the description-length estimate.
  4. For pairs of designs or screens, compute normalised compression distance NCD = (C(xy) - min(C(x),C(y))) / max(C(x),C(y)) to quantify consistency across screens.
  5. Alternatively write a two-part MDL code: count the rules needed to generate the design plus the exceptions not covered by rules.
  6. Rank variants by estimated description length and test whether the ranking predicts learnability, for example via trials-to-criterion with 8-12 novice participants.

Sources

  • MacKay, D. J. C., Information Theory, Inference, and Learning Algorithms (2003)
  • Kolmogorov complexity literature (MIT Press)
  • Shannon, C. E., A Mathematical Theory of Communication (1948)
  • MacKay (Information Theory)
  • Kolmogorov via MIT Press
  • Shannon's works
  • The Inquiry Series, Ch 1 — Entropy, Complexity & the Information Architecture of Interaction

Also known as

  • MDL estimation
  • Description-length complexity estimate
  • Kolmogorov complexity approximation

Categories

  • Information Theory, Physics & Mathematics