Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 22

How much context does an autoregressive model need?

The chain rule writes the likelihood of a sequence as a product of conditionals \(p(x_t\mid x_{1:t-1})\). Restricting each conditional to the last \(k\) symbols gives the order-\(k\) Markov model, fitted here by counting. The sequence is \(x_t=x_{t-2}\oplus x_{t-5}\oplus\) noise, so a model needs five symbols of context; the best possible score is the noise entropy \(h_2(\varepsilon)\) (green line). Blue: bits per symbol on the training sequence; red: on a fresh test sequence. The golden marker is the order you select.

Source (flip probability ε)

Training symbols (N)

Model

Try these

Orders 0 to 4 cannot see the symbol \(x_{t-5}\), so the conditional given the last \(k\le4\) symbols is a fair coin: one bit per symbol. At \(k=5\) the dependence is captured and the score drops to the noise entropy. Beyond it the number of contexts, \(2^k\), grows while the number of observations per context shrinks: the training score keeps improving but the test score worsens; moderate smoothing limits the damage but cannot remove it, and no smoothing at all is worst. The estimate of each conditional is \((n_{c,v}+\alpha)/(n_c+2\alpha)\).

In the lecture notes