Estimating accuracy limits for processes with unknown memory length
Universal Estimation of the Fisher Information for Processes with Memory
Information Theory
Summary
Knowing how well we can estimate something complicated depends on measuring its Fisher information. The authors developed a way to estimate this Fisher information rate for processes that remember past events (have memory), even if you only have a simulation to work with and don't know how long the memory is. They use a clever technique involving measuring differences between probabilities and reconstruct the information from these measurements. Their method works well in theory and practice, including for processes that don’t have a fixed memory length.
What this means in practice
- •For signal processing engineers: Determine sampling budgets to achieve desired estimation precision for signals with complex dependencies without knowing exact process memory.
- •For machine learning practitioners: Estimate the Fisher information matrix for modeled processes where the underlying memory is unknown and only simulation data is available.
Authors
Yibo Shi, Cristian R. Rojas
Abstract
The Fisher information matrix (FIM) determines the accuracy attainable in an estimation problem. For a parametric process with memory, it has a closed form only for narrow classes of models, and it cannot be computed when the model is available only as a simulator. This paper estimates the Fisher information rate of such a process, the per-observation limit of its FIM, from simulator output alone and without knowledge of the memory length. The construction uses the identity between the FIM and the local curvature of the Kullback--Leibler (KL) divergence. Directional divergence rates are estimated by context-tree weighting (CTW), and the matrix is recovered from them by least squares. We establish strong consistency in an iterated limit and a finite-sample bound, uniform over every working depth at least as large as the true memory length, which gives a mean error of order $n^{-1/3}$. The analysis also delivers a finite-sample rate for CTW-based estimation of the KL divergence rate. Experiments confirm the predicted exponents, show that the accuracy does not degrade as the working depth grows, and use the estimate to plan a sampling budget that attains a prescribed precision. The estimator stays accurate on a hidden-state source that has no finite memory length.