B09
Prediction, coding, and learning
When does shorter code length predict better classification on new examples?

IV.15 / AI
How does the compression-based classifier reported in 2006 perform on a new corpus under the original evaluation conditions?
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.
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.
Reproduce a small documented baseline with frozen data and compare its errors with a simple non-compression classifier under the same split.
These models isolate a mechanism you can vary. Their assumptions define the part of this topic they can illuminate.
Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.
Compare symbol frequencies with the ordering that a code can exploit.
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.
Andrej Bratko, Gordon V. Cormack, Bogdan Filipič, Thomas R. Lynam, and Blaž Zupan / JMLR · Compression-model-based spam classification and its evaluation setting.
B09
When does shorter code length predict better classification on new examples?
B29
At the same accuracy, how much memory and energy does each representation require?