# Generalized Probability Smoothing

@article{Mattern2018GeneralizedPS, title={Generalized Probability Smoothing}, author={Christopher Mattern}, journal={2018 Data Compression Conference}, year={2018}, pages={247-256} }

In this work we consider a generalized version of Probability Smoothing, the core elementary model for sequential prediction in the state of the art PAQ family of data compression algorithms. Our main contribution is a code length analysis that considers the redundancy of Probability Smoothing with respect to a Piecewise Stationary Source. The analysis holds for a finite alphabet and expresses redundancy in terms of the total variation in probability mass of the stationary distributions of a… Expand

#### Figures and Topics from this paper

#### References

SHOWING 1-10 OF 23 REFERENCES

On Probability Estimation by Exponential Smoothing

- Mathematics, Computer Science
- 2015 Data Compression Conference
- 2015

This work presents a probability estimation method based on exponential smoothing that satisfies the requirement that recent observations should receive a higher weight than older observations, and provides a theoretical analysis for various smoothing rate sequences. Expand

On Probability Estimation via Relative Frequencies and Discount

- Mathematics, Computer Science
- 2015 Data Compression Conference
- 2015

It is shown that Algorithm RFD performs almost as good as any piecewise stationary model with either bounded or unbounded letter probabilities, which theoretically confirms the recency effect of periodic frequency discount, which has often been observed empirically. Expand

Partition Tree Weighting

- Computer Science, Mathematics
- 2013 Data Compression Conference
- 2013

The order of the redundancy and the complexity of the algorithm matches those of the best competitors available in the literature, and the new algorithm exhibits a superior complexity-performance trade-off in the experiments. Expand

Universal finite memory machines for coding binary sequences

- Mathematics, Computer Science
- Proceedings DCC 2000. Data Compression Conference
- 2000

This work provides in most cases lower bounds and describes finite memory universal machines whose performance, in terms of the memory size, is compared to these bounds. Expand

Theoretical analysis of a zero-redundancy estimator with a finite window for memoryless source

- Medicine, Computer Science
- IEEE Information Theory Workshop, 2005.
- 2005

This work uses a weighted sum of Krichevsky-Trofimov sequential probability estimators to construct a finite window predictor for lossless data compressor, and shows that its average redundancy for memoryless source has optimal 1st order asymptotics. Expand

Context Tree Switching

- Computer Science, Mathematics
- 2012 Data Compression Conference
- 2012

It is proved that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and it is shown empirically that this new technique leads to consistent improvements over Context Tree weighting as measured on the Calgary Corpus. Expand

Prediction of Individual Sequences using Universal Deterministic Finite State Machines

- Mathematics, Computer Science
- 2006 IEEE International Symposium on Information Theory
- 2006

Numerical results show that the redundancy of the proposed FS predictor is close to that predicted by the lower bound, which is an improved lower bound on the redundancies of any finite state (FS) predictor with K states. Expand

Coding for a binary independent piecewise-identically-distributed source

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1996

Two weighting procedures are presented for compaction of output sequences generated by binary independent sources whose unknown parameter may occasionally change and it is proved that additional-transition redundancy is not more than 3/2 log T bits per transition. Expand

Combining Non-stationary Prediction, Optimization and Mixing for Data Compression

- Computer Science, Mathematics
- 2011 First International Conference on Data Compression, Communications and Processing
- 2011

An approach to modelling nonstationary binary sequences, i.e., predicting the probability of upcoming symbols, and a systematic approach to the parameter optimization of an individual model and the ensemble model are presented. Expand

Finite-memory universal prediction of individual sequences

- Mathematics, Computer Science
- IEEE Transactions on Information Theory
- 2004

Borders on the asymptotic achievable regret of these constrained universal predictors as a function of K, the number of their states, for long enough sequences are provided. Expand