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

X.05 / SHARED INSTRUMENTS
How does the attainable message length depend on the cost assigned to reconstruction errors?
Information theory, coding, and compression connect source structure to representations that can be stored or transmitted. Shannon's communication work provides the formal foundation, while his sampling paper addresses the representation of band-limited signals. A practical comparison must include the encoding convention, model overhead, reconstruction requirement, and channel conditions. Compression and sampling solve related representation problems with different assumptions.
Suppose a short document uses four words repeatedly. Replacing each word with a short symbol can shrink the body, but the decoder also needs the symbol-to-word dictionary. Count both components and compare the total with the original. Repeat with a much longer document to see how shared overhead changes the result.
Compare two encodings of one fixed dataset, including all metadata required to decode it, and state whether the reconstruction is exact or approximate.
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.
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.
Nokia Bell Labs · Communication entropy, coding, and noise; does not turn statistical information into a theory of semantic truth.
Claude E. Shannon / MIT-hosted original paper · Band-limited sampling and communication; sampling examples here are editorial calculations.
B09
When does shorter code length predict better classification on new examples?
B15
Which errors can each encoding recover, and what physical resources does recovery consume?