A Family of LZ78-based Universal Sequential Probability Assignments

detalle del documento

IDENTIFICACIÓN

oai:arXiv.org:2410.06589

Tema

Computer Science - Information The... 94A12 (Primary), 94A29, 94A17 (Sec... H.1.1

Autor

Sagan, Naomi Weissman, Tsachy

Categoría

Computer Science

Año

2024

fecha de cotización

16/10/2024

Palabras clave

family models

Métrico

Resumen

We propose and study a family of universal sequential probability assignments on individual sequences, based on the incremental parsing procedure of the Lempel-Ziv (LZ78) compression algorithm.

We show that the normalized log loss under any of these models converges to the normalized LZ78 codelength, uniformly over all individual sequences.

To establish the universality of these models, we consolidate a set of results from the literature relating finite-state compressibility to optimal log-loss under Markovian and finite-state models.

We also consider some theoretical and computational properties of these models when viewed as probabilistic sources.

Finally, we present experimental results showcasing the potential benefit of using this family -- as models and as sources -- for compression, generation, and classification.

;Comment: 31 pages, 5 figures, submitted to IEEE Transactions on Information Theory

Sagan, Naomi,Weissman, Tsachy, 2024, A Family of LZ78-based Universal Sequential Probability Assignments