Efficient sequence prediction balances speed and pattern complexity
Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity
Formal Languages and Automata TheoryData Structures and AlgorithmsMachine Learning
Summary
The paper looks at how to predict sequences of symbols using measurements of their complexity. The authors study a new, simpler measure that allows a faster prediction method consuming very little memory but works best on structured sequences. They compare this to a more complex measure they studied before which is more expressive but slower. This shows there is a tradeoff between how detailed the complexity measure is and how efficiently sequences can be predicted.
What this means in practice
- •For data compression engineers: Use layered zipline-based complexity measures to design faster sequence encoders for highly structured data streams.
- •For algorithm developers: Incorporate the tradeoff between efficiency and expressivity to optimize prediction algorithms for resource-constrained environments.
Authors
Vanessa Kosoy
Abstract
In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.