Sequential universal modeling for non-binary sequences with constrained distributions

DOI10.4310/CIS.2022.V22.N1.A1MaRDI QIDQ2155950zbMATH OpenFDO

Authors Gil I. Shamir, Wojciech Szpankowski, Michael Drmota

Publication date 15 July 2022

Published in Communications in Information and Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.10320

zbMATH Keywords

analytic combinatoricsconstrained distributioninformation theoryminimax redundancy

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information theory (general) (94A15)

Abstract: Sequential probability assignment and universal compression go hand in hand. We propose sequential probability assignment for non-binary (and large alphabet) sequences with empirical distributions whose parameters are known to be bounded within a limited interval. Sequential probability assignment algorithms are essential in many applications that require fast and accurate estimation of the maximizing sequence probability. These applications include learning, regression, channel estimation and decoding, prediction, and universal compression. On the other hand, constrained distributions introduce interesting theoretical twists that must be overcome in order to present efficient sequential algorithms. Here, we focus on universal compression for memoryless sources, and present precise analysis for the maximal minimax and the average minimax for constrained distributions. We show that our sequential algorithm based on modified Krichevsky-Trofimov (KT) estimator is asymptotically optimal up to $O(1)$ for both maximal and average redundancies. This paper follows and addresses the challenge presented in cite{stw08} that suggested "results for the binary case lay the foundation to studying larger alphabets".

Recommendations

• On the MDL principle for i.i.d. sources with large alphabets
• A universal algorithm for sequential data compression
• Universal Lossless Compression With Unknown Alphabets—The Average Case
• A sequential algorithm for the universal coding of finite memory sources
• Universal sequential coding of single messages

Cited in

(3)

• Convergence and loss bounds for bayesian sequence prediction
• Universal schemes for sequential decision from individual data sequences
• Minimax optimal Bayes mixtures for memoryless sources over large alphabets

This page was built for publication: Sequential universal modeling for non-binary sequences with constrained distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155950)