A two-step sequential approach for hyperparameter selection in finite context models

José Contente, Ana Martins, Armando J. Pinho, Sónia Gouveia · 2026

Read A two-step sequential approach for hyperparameter selection in finite context models by José Contente, Ana Martins, Armando J. Pinho, Sónia Gouveia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19736.txt.

Introduction

Contente and co-authors offer a cheaper way to tune finite-context models. These models compress symbol sequences such as DNA. Their skill hinges on context length and a smoothing value. Grid search over both is slow and scales badly. The two-step plan splits the search into two stages. First, dependence measures pick the context length. Then likelihood methods set the smoothing value. On simulated data the plan matched grid search compression at far lower cost.

Catalog record

CREATORJosé Contente, Ana Martins, Armando J. Pinho, Sónia Gouveia
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31628
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A two-step sequential approach for hyperparameter selection in finite context models José Contente, Ana Martins, Armando J. Pinho, Sónia Gouveia Abstract Finite-context models (FCMs) are widely used for compressing symbolic sequences such as DNA, where predictive performance depends critically on the context length k k and smoothing parameter α \alpha . In practice, these hyperparameters are typically selected through exhaustive search, which is computationally expensive and scales poorly with model complexity. This paper proposes a statistically grounded two-step sequential approach for efficient hyperparameter selection in FCMs. The key idea is to decompose the joint optimization problem into two independent stages. First, the context length k k is estimated using categorical serial dependence measures, including Cramér’s ν \nu , Cohen’s κ \kappa and partial mutual information (pami). Second, the smoothing parameter α \alpha is estimated via maximum likelihood conditional on the selected context length k k . Simulation experiments were conducted on synthetic symbolic sequences generated by FCMs across multiple ( k , α ) (k,\alpha) configurations, considering a four-letter alphabet and different sample sizes. Results show that the dependence measures are substantially more sensitive to variations in k k than in α \alpha , supporting the sequential estimation strategy. As expected, the accuracy of the hyperparameter estimation improves with increasing sample size. Furthermore, the proposed method achieves compression performance comparable to exhaustive grid search in terms of average bitrate (bits per symbol), while substantially reducing computational cost. Overall, the results on simulated data show that the proposed sequential approach is a practical and computationally efficient alternative to exhaustive hyperparameter tuning in FCMs. 1 Introduction Data compression, that is, reducing data digital size by encoding information using fewer bits, is an increasingly important task for efficient storage of information in a fast-moving data-driven world. Furthermore, compression techniques have underlying models that attempt to reproduce as closely as possible the information source to be compressed. Thus, these models are interesting on their own as they can provide insight into the statistical properties of the data. One such model are finite context models (FCMs), widely used in the compression of finite alphabet sequences, such as DNA or proteins [ 11 , 14 , 15 ] . Finite context models describe sequences from a finite alphabet, where the probability of observing the next symbol s depends only on the k previous symbols, i.e., the context. This probability is calculated for a fixed k context using the Lidstone estimator [ 8 ] , where \alpha is a smoothing factor. As such, FCMs are described by hyperparameters context ( k ) and smoothing factor (\alpha) . Current approaches to set these hyperparameters in compressors are based on exhaustive trial and error procedures (grid search), which implies that the compression technique must be employed at every trial, so that the “best” combination of hyperparameters in the search space is identified. Thus, the wide use of FCMs advocates for a timely manner to find the “best” set of hyperparameters, improving compressors time efficiency. Finite context models are, in fact, discrete-time Markov models, which, from a time series analysis perspective, have a close relation to autoregressive models, i.e., an observation at time t relies on the previous p observations. Thus, concepts commonly used in time series analysis to describe serial dependence are of high relevance in this setting. For real-valued time series, the autocorrelation function (acf) and partial autocorrelation (pacf) play an important role in the study of structural serial dependence [ 13 ] . The acf provides information on the correlation between two time points, whereas pacf provides this information, conditional on intermediate time points, meaning that, it provides a more accurate representation of the serial dependence [ 13 ] . In fact, pacf is used to identify the order p of autoregressive models [ 13 ] . Thus, given the categorical nature of FCMs, to bridge this knowledge into its domain requires the use of counterpart measures adequate for this type of data. The development of serial metrics for categorical time series faces several challenges, but continuous correlation measures such as Cohen’s \kappa and Cramer’s \nu have been adapted for categorical time series [ 17 ] . Another interesting measure, is the partial auto mutual information (pami, for short) proposed by Biswas and Gua (2009) [ 3 ] to deal with categorical data. The authors have shown that this measure behaves in a similar fashion to the pacf, which supports its use for model order identification. Although, this measure was proposed under a time series perspective, it makes use of the concept of mutual information, thus, relating to information theory and compressors. As such, pami is a very strong contester to aid identifying the hyperparameter k . The previous metrics allow only the selection of k , however, it is also necessary to set \alpha in the Lidstone estimator. This estimator requires that the size of the context ( k ) is previously fixed, which advocates for a sequential strategy where the value of \alpha is chosen after k has been set. Thus, the selection of \alpha can be framed within a principled probabilistic modelling perspective. Specifically, under the Lidstone formulation, the smoothed predictive probability corresponds to the posterior expectation of a multinomial distribution with a symmetric Dirichlet prior. Consequently, estimating \alpha becomes a hyperparameter inference problem. A natural approach is to adopt an empirical Bayes strategy, whereby the multinomial probability vectors associated with each context are treated as latent variables and integrated out, yielding a Dirichlet - multinomial marginal likelihood for the observed count vectors. Pooling information across all contexts of fixed order k enables the estimation, as each context provides an independent multinomial observation contributing to the likelihood of \alpha . The resulting estimator is obtained by maximizing the joint marginal likelihood over \alpha . This approach yields a data-driven estimate of \alpha , coherent with the probabilistic interpretation of Lidstone smoothing factor, and naturally adapts to the amount of information available in the collection of contexts. Therefore, the goal of this work is to introduce a two-step sequential approach for the selection of FCM hyperparameters (k,\alpha) . The first step of the approach consists in fixing k using categorical serial dependence measures as features. Then, \alpha is estimated via maximum likelihood conditional on the value of k . By separating the context length from the smoothing factor, the proposed approach reduces the dimensionality of the optimization problem and avoids the combinatorial search typically required for joint hyperparameter tuning. Hence, this approach will contribute to largely reduce the computational burden and time cost of compression tasks. The remaining of the paper is outlined as follows: section 2 provides background information finite context models and their hyperparameters, section 3 presents the methods used to develop the two-step sequential approach, including the simulation study design and performance evaluation. Section 4 presents the results of the experimental study and its discussion. Lastly, section 5 is devoted to the main conclusions and future work. 2 Finite context models and hyperparameters Finite context models are Markov models used in the modeling of serial dependence. In this particular case, the interest lies in modeling the serial dependence of a categorical process Y_{t} described by a finite alphabet \mathcal{A} with range \{a_{1},a_{2},\dots,a_{r}\}

Read the complete text