  Models for categorical sequences typically assume exchangeable or first-order
dependent sequence elements. These are common assumptions, for example, in
models of computer malware traces and protein sequences. Although such
simplifying assumptions lead to computational tractability, these models fail
to capture long-range, complex dependence structures that may be harnessed for
greater predictive power. To this end, a Bayesian modelling framework is
proposed to parsimoniously capture rich dependence structures in categorical
sequences, with memory efficiency suitable for real-time processing of data
streams. Parsimonious Bayesian context trees are introduced as a form of
variable-order Markov model with conjugate prior distributions. The novel
framework requires fewer parameters than fixed-order Markov models by dropping
redundant dependencies and clustering sequential contexts. Approximate
inference on the context tree structure is performed via a computationally
efficient model-based agglomerative clustering procedure. The proposed
framework is tested on synthetic and real-world data examples, and it
outperforms existing sequence models when fitted to real protein sequences and
honeypot computer terminal sessions.
