Stanford EE274: Data Compression I 2023 I Lecture 9 - Context-based AC & LLM Compression

Markov Chains and Entropy Rate

• A recap of key concepts is provided, including Markov chains, stationary processes, conditional entropy, and the entropy rate.
• A given Markov chain is analyzed, and its properties, such as entropy of U1, entropy of U2, stationarity, and entropy rate, are calculated.
• The concept of achieving the entropy rate is introduced, and it is explained that for a first-order Markov source, the entropy rate is equal to the entropy of U2 given U1.

Text Data Compression

• The lecture concludes with a brief introduction to text data compression and an overview of the Lempel-Ziv-Welch (LZW) compression technique, which will be discussed in detail in the next lecture.

Arithmetic Coding

• Arithmetic coding works by dividing intervals into symbols and splitting the sub-interval corresponding to each symbol.
• The length of the interval at the end of the encoding is the product of the probabilities of each symbol.
• The code length for each symbol is roughly the logarithm of the inverse of the interval length.
• Context-based arithmetic coding is a modified version of arithmetic coding that uses the knowledge of the past symbols to split the intervals.
• The expected bits per symbol for context-based arithmetic coding is equal to the conditional entropy, which is the entropy rate in the case of a first-order Markov source.
• The code length for context-based arithmetic coding is the logarithm of the product of the conditional probabilities.
• A better predictor gives higher probabilities, resulting in shorter code lengths.
• Better prediction leads to smaller code length and better compression in arithmetic coding.
• The number of bits used to encode a symbol is approximately the negative logarithm of its probability.
• A good model can predict the next symbol with high probability, resulting in fewer bits required for encoding.
• Providing more context to a good model improves its prediction accuracy and reduces the number of bits needed for encoding.
• Arithmetic decoding is symmetric to arithmetic encoding and requires the same model to split intervals and decode symbols.
• If a model is not available, the empirical distribution of the input data can be used to build a model for compression.

Adaptive Arithmetic Coding

• There are two approaches to modeling: building a model from data before encoding (used in Homework 1) and building an adaptive model as data is processed.
• Adaptive arithmetic coding updates the model at every step based on the data seen so far.
• The decoder needs to update its model accordingly to stay in sync with the encoder.
• It's crucial for the encoder and decoder to share the same state at every step to avoid breakdowns.
• Don't provide zero probability to any symbol, as it can break the arithmetic coder.
• Two-pass encoding learns the model from the entire data and can be parallelized, but requires storing the model in the compressed file and may not be suitable for streaming data.
• Adaptive encoding doesn't need to store the model and is good for streaming, but the initial model is weak and compression may be slightly worse initially.
• Prediction and compression are essentially the same problem, with the cost function for arithmetic coding matching the prediction loss function.
• A good predictor can be used as a compressor, and vice versa, although this can be trickier.

Kth-Order Adaptive Arithmetic Coding

• Kth-order adaptive arithmetic coding aims to learn a k-order model for the data as it's processed.
• Adaptive arithmetic coding is a data compression technique that uses past symbols to predict future symbols.
• The order of the model refers to the number of past symbols used to make predictions.
• Higher-order models can make more accurate predictions but require more memory and can suffer from sparse counts, especially with limited data.
• The example of the Hound of Baskerville was used to compare zeroth, first, second, and third-order adaptive arithmetic coding, as well as gzip and bzip2 compression.
• Higher-order models did not perform as well as expected due to the limited size of the data, which resulted in sparse counts and poor predictions.
• Adaptive arithmetic coding has limitations, including slow performance, exponentially growing memory requirements, and sparse counts for large orders, which can lead to worse performance.
• A two-pass approach using conditional entropy showed promising results, particularly for higher-order models.
• Adaptive K-order modeling involves adjusting the order of the model based on the input data to improve compression efficiency.
• Increasing the order of the model can lead to sparse counts and make it harder to predict symbols accurately.

Advanced Prediction Models

• Advanced prediction models, such as neural network-based models and context mixing models, can achieve better compression but are computationally expensive.
• Recent progress in text compression has surpassed Shannon's estimate of the entropy rate of English using large language models (LLMs) as predictors.
• LLMs are trained as predictors and their loss function is the cross-entropy loss, making them effective compressors.
• Deploying large models as predictors can be practical in certain settings where everyone has access to the same model, such as compressing large amounts of similar data.
• Exploring the limits of compression and experimenting with different models is valuable for understanding text prediction and compression techniques.
• LLMs achieve remarkable compression results, surpassing bzip2 but not as impressive as gzip or arithmetic coding.
• Smaller LLMs perform better with longer contexts, approaching the optimal Shannon bound.
• LLMs struggle with data that differs from their training distribution, such as ancient languages like Pali.
• LLMs perform exceptionally well on data they were trained on, like Sherlock Holmes novels, due to memorization.
• Caution is needed when evaluating compression results to avoid using data from the training set.
• LLMs are currently slow and computationally intensive, but smaller models show promise for practical applications.
• Overfitting can be beneficial for compression, as long as the model is shared for specific datasets.

Resources and Next Lecture

• Resources mentioned: tsz notebook for experiments and DeepMind's paper "Language Modeling is Compression."
• Next lecture will cover LZ77 and practical aspects of lossless compression.