Monotonicity
Nested models
For a given time series, the candidate VLMCs generated by the context algorithm follow a nested structure associated to the pruning operation: the most complete context tree is pruned recursively in order to generate less and less complex trees. A context in a small tree is also a suffix of context of a larger tree. The inclusion order is total unless some cut off values are identical.
A natural expected property of likelihood functions is to observe a decrease in likelihood for a given time series when switching from a model \(m_1\) to a simpler model \(m_2\) provided their parameters are estimated by maximum likelihood using this time series, in particular when \(m_2\) is nested in \(m_1\) in the sense of the likelihood-ratio test.
Theoretical analysis
Let us consider the case of two VLMC models \(m_1\) and \(m_2\) where \(m_2\) is obtained by pruning \(m_1\) (both estimated on \((x_i)_{1\leq i\leq n}\)). Let us first consider \((x_i)_{i>d}\) where \(d\) is the order of \(m_1\). The contexts of those values are well defined, both in \(m_1\) and \(m_2\). The corresponding probabilities can be factorised according to the contexts as follows (for \(m_1\)) \[ \mathbb{P}_{m_1}(X_{d+1}=x_{d+1},\ldots,X_n=x_n)=\prod_{c\in m_1}\prod_{k,\ ctx(m_1, x_k)=c}\mathbb{P}_{m_1}(X_k=x_k|ctx(m_1, x_k)=c), \] where with use \(ctx(m_1, x_k)\) to denote the context of \(x_k\) in \(m_1\) and \(c\in m_1\) to denote all contexts in \(m_1\). We have obviously a similar equation for \(m_2\).
As \(m_2\) is included in \(m_1\) we know that each \(c\in m_2\) is also the suffix of a context of \(m_1\). When \(c\) is a context in both models, they concern the same subset of the time series and use therefore the same estimated conditional probabilities, leading to identical values of \[\mathbb{P}_{m_1}(X_k=x_k|ctx(m_1, x_k)=c)=\mathbb{P}_{m2}(X_k=x_k|ctx(m_2, x_k)=c).\]
When \(c\) is the suffix of a context in \(m_1\), there is a collection of contexts \(c'\) for which \(c\) is also a suffix. We have then \[ \{k\mid ctx(m_2, x_k)=c\}=\bigcup_{c'\in m_1, c\text{ is a suffix of }c'}\{j\mid ctx(m_1, x_j)=c'\}. \] In words, the collection of observations whose context in \(m_1\) has \(c\) as a suffix is equal to the collection of observations chose context in \(m_2\) is \(c\). Because the conditional probabilities are estimated by maximum likelihood, we have then \[ \begin{multline*} \prod_{\{k\mid ctx(m_2, x_k)=c\}}\mathbb{P}_{m_2}(X_k=x_k|ctx(m_2, x_k)=c)\leq\\ \prod_{\{l\mid ctx(m_1, x_k)=c', c\text{ is a suffix of }c'\}}\mathbb{P}_{m_1}(X_l=x_l|ctx(m_1, x_k)=c'). \end{multline*} \] Thus overall, as expected, \[ \mathbb{P}_{m_2}(X_{d+1}=x_{d+1},\ldots,X_n=x_n)\leq \mathbb{P}_{m_1}(X_{d+1}=x_{d+1},\ldots,X_n=x_n). \] However, the models may not have the same order. Fortunately, as probabilities are not larger than 1, we have also \[ \mathbb{P}_{m_2}(X_{d_{m_2}+1}=x_{d_{m_2}+1},\ldots,X_n=x_n)\leq \mathbb{P}_{m_1}(X_{d_{m_1}+1}=x_{d_{m_1}+1},\ldots,X_n=x_n), \] where \(d_m\) denotes the order of model \(m\).
In conclusion, likelihood functions based on truncation or on specific contexts are non increasing when one moves from a VLMC to one of its pruned version.
The case of extended contexts is more complex. Using the hypotheses as above, the extended likelihood includes approximate contexts for observations \(x_{1},\ldots, x_{d_{m_1}}\) and for \(x_{1},\ldots, x_{d_{m_2}}\). Let us consider the case where \(d_{m_1}=d_{m_2}+1\) (without loss of generality). The only difference in the extended likelihoods is then \(\mathbb{P}_{m_1}(X_{d_{m_1}}=x_{d_{m_1}}|ectx(m_1, x_{d_{m_1}}))\) which is computed using the extended context \(ectx(m_1, X_{d_{m_1}})\) and \(\mathbb{P}_{m_2}(X_{d_{m_1}}=x_{d_{m_1}}|ctx(m_2, x_{d_{m_1}}))\) which is computed using the true context.
Notice that \[ (x_1,\ldots,x_{d_{m_1}-1},x_{d_{m_1}})=(x_1,\ldots,x_{d_{m_2}-1},x_{d_{m_2}}, x_{d_{m_1}}) \] Thus one computes the (extended) context of \(x_{d_{m_1}}\), the \(d_{m_2}\) first steps are obviously identical in \(m_1\) and in \(m_2\), as \(m_2\) has been obtained by pruning \(m_1\). Depending on the structure of the context tree, it may be possible possible to determine the true of context of \(x_{d_{m_1}}\) in both trees and thus the corresponding probabilities will be identical. The only non obvious situation is when the context of \(x_{d_{m_1}}\) cannot be determine in \(m_1\). This is only possible if the context in \(m_2\) is of length \(d_{m_2}\) and the corresponding leaf was an internal node in \(m_1\). Then we use as the extended context in \(m_1\) the normal context of \(m_2\) and therefore \[ \mathbb{P}_{m_1}(X_{d_{m_1}}=x_{d_{m_1}}|ectx(m_1, x_{d_{m_1}}))=\mathbb{P}_{m_2}(X_{d_{m_1}}=x_{d_{m_1}}|ctx(m_2, x_{d_{m_1}})). \]
Thus in all cases, in the extended context interpretation, moving from an extended context to a true context does not change the probability included in the likelihood. Therefore, the extended likelihood is also non increasing with the pruning operation.
Experimental illustration
We used the saving options of tune_vlmc() to keep all
the models considered during the model selection process in the
California earth quakes analysis. We can use them to illustrate non
decreasing behaviour of the likelihoods. For the extended
likelikood, we have:
CA_models <- c(
list(California_weeks_earth_quakes_model$saved_models$initial),
California_weeks_earth_quakes_model$saved_models$all
)
CA_extended <- data.frame(
cutoff = sapply(CA_models, \(x) x$cutoff),
loglikelihood = sapply(CA_models, loglikelihood,
initial = "extended"
)
)
ggplot(CA_extended, aes(cutoff, loglikelihood)) +
geom_line() +
xlab("Cut off (native scale)") +
ylab("Log likelihood") +
ggtitle("Extended log likelihood")
For the specific likelihood we have:
CA_specific <- data.frame(
cutoff = sapply(CA_models, \(x) x$cutoff),
loglikelihood = sapply(CA_models, loglikelihood,
initial = "specific"
)
)
ggplot(CA_specific, aes(cutoff, loglikelihood)) +
geom_line() +
xlab("Cut off (native scale)") +
ylab("Log likelihood") +
ggtitle("Specific log likelihood")
Notice that the time series contains 6417 observations and the maximum
order considered by tune_vlmc() is 29, thus we do not
expect to observe large differences between the different log
likelihoods. This is illustrated on the following figure:
CW_combined <- rbind(
CA_extended[c("cutoff", "loglikelihood")],
CA_specific[c("cutoff", "loglikelihood")]
)
CW_combined[["Likelihood function"]] <- rep(c("extended", "specific"), times = rep(nrow(California_weeks_earth_quakes_model$results), 2))
ggplot(
CW_combined,
aes(cutoff, loglikelihood, color = `Likelihood function`)
) +
geom_line() +
xlab("Cut off (native scale)") +
ylab("Log likelihood") +
ggtitle("Log likelihood")
The case of the truncated likelihood is more complex. As noted above, the numerical values of the truncated likelihood are identical to the values of the specific likelihood and thus the above graphical representations are also valid for it. However care must be exercised when using the truncated likelihood for model selection, as explained below.