STRATA
Skip to study
XLVII

IV.15 / AI

Compression-based classification and contemporary reuse

How does the compression-based classifier reported in 2006 perform on a new corpus under the original evaluation conditions?

A source-led introduction1 source references1 related experiments

Start with the question.

Compression-based classification uses statistical regularities learned from data to help distinguish categories. Bratko and colleagues studied statistical compression models in spam filtering, where the evaluation includes a changing and adversarial text environment. The useful lesson is to specify exactly how a model becomes a class score, which data trained it, and how errors are priced in the intended use.

Compare two class-conditioned descriptions.

Train two illustrative text models on separate, labeled collections and score a held-out message under each. Record which model assigns the shorter effective description and whether headers or repeated templates dominate that difference. Split related messages together when forming training and test sets so that near-duplicates do not make the evaluation artificially easy.

What would you inspect?

  • Class-score definition, preprocessing, model training data, and temporal split.
  • False positives, false negatives, and performance on newly arriving text.

Take the next step.

Reproduce a small documented baseline with frozen data and compare its errors with a simple non-compression classifier under the same split.

Put part of the question to work.

These models isolate a mechanism you can vary. Their assumptions define the part of this topic they can illuminate.

Try entropy and compression.

Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.

Open its full page

Watch the quantities change.

12 seconds · Original model visualization · Silent

Entropy and compression

Compare symbol frequencies with the ordering that a code can exploit.

Read the explanation and method

The first sweep changes the probability of A while drawing each symbol independently. The other three symbols share the remaining probability.

As one symbol dominates, the observed symbol entropy falls. Huffman codes use short words for frequent symbols; the comparison excludes headers and the codebook.

The second sweep gives all four new draws equal probability and increases repetition. Long runs reward run-length coding, even when a symbol histogram cannot describe the dependence.

Method. The histogram gives an order-zero Shannon entropy. Huffman coding repeatedly joins the two least frequent branches to build a prefix code. The run-length format stores a two-bit symbol and an eight-bit count; counts run from 1 to 255, and a longer run uses another packet.

Read the supporting material.

  1. Spam Filtering Using Statistical Data Compression Models

    Andrej Bratko, Gordon V. Cormack, Bogdan Filipič, Thomas R. Lynam, and Blaž Zupan / JMLR · Compression-model-based spam classification and its evaluation setting.

Continue through the versioned study records.

Follow the comparisons.

Read the neighboring questions.