Nearly maximally predictive features and their dimensions

Scientific explanation often requires inferring maximally predictive features from a given data set. Unfortunately, the collection of minimal maximally predictive features for most stochastic processes is uncountably infinite. In such cases, one compromises and instead seeks nearly maximally predictive features. Here, we derive upper bounds on the rates at which the number and the coding cost of nearly maximally predictive features scale with desired predictive power. The rates are determined by the fractal dimensions of a process' mixed-state distribution. These results, in turn, show how widely used finite-order Markov models can fail as predictors and that mixed-state predictive features can offer a substantial improvement.

Figure 1

Mixed-state presentations $Y$ for three different generative models given in Appendix A of the Supplemental Materials [25]. To visualize the mixed-state simplex, the diagrams plot iterates $y_t$ such that the left vertex corresponds to the pure state $Pr(A,B,C)=(1,0,0)$ or HMM state $A$, the right to pure state $(0,1,0)$ or HMM state $B$, and the top to pure state $(0,0,1)$ or HMM state $C$. Left plot has 55 mixed states plotted in a $1\times 100$ bin histogram; middle plots 2,391,484 mixed states in a $1000\times 1000$ bin histogram; and right plots 21,523,360 mixed states in a $4000\times 4000$ bin histogram. Bin cell coloring is negative logarithm of the normalized bin counts. The box-counting dimensions are respectively ${\text{dim}}_0\left(Y\right)\approx 0.3$ at left, ${\text{dim}}_0\left(Y\right)\approx 1.8$ in the middle, and ${\text{dim}}_0\left(Y\right)\approx 1.9$ at right. Box-counting dimension calculated by estimating the slope of $ln(1/\epsilon )$ vs $ln{N}_{\epsilon }$ as described in Appendix A of the Supplemental Material [25].

Figure 2

Model-size scaling for the parametrized simple nonunifilar source (SNS). Top: Generative HMM for the SNS. Bottom: Scaling of $\langle \left|M\right|\rangle ={\sum }_M\left|M\right|P\left(M\right|x_{0:T})$ with $T$, with the posterior $P\left(M\right|x_{0:T})$ calculated using formulas from BSI [35] with $\alpha =1$ and the set of model topologies being the eventually Poisson $\epsilon$-machines described in Ref. [37]. Data generated from the SNS with $p=q=\frac{1}{2}$. Linear regression reveals a slope of $\approx 1$ for $\text{ln}\text{ln}T$ vs $ln\langle \left|M\right|\rangle$, confirming the expected $N_T\begin{array}{c}\propto \\ \sim \end{array}lnT$, where the proportionality constants depend on $\beta$. Curves from top to bottom: $\beta =1,4,8$ and blue, green, and red, respectively.