Ambiguity rate of hidden Markov processes

The $\epsilon$-machine is a stochastic process's optimal model—maximally predictive and minimal in size. It often happens that to optimally predict even simply defined processes, probabilistic models—including the $\epsilon$-machine—must employ an uncountably infinite set of features. To constructively work with these infinite sets we map the $\epsilon$-machine to a place-dependent iterated function system (IFS)—a stochastic dynamical system. We then introduce the ambiguity rate that, in conjunction with a process's Shannon entropy rate, determines the rate at which this set of predictive features must grow to maintain maximal predictive power over increasing horizons. We demonstrate, as an ancillary technical result that stands on its own, that the ambiguity rate is the (until now missing) correction to the Lyapunov dimension of an IFS's attracting invariant set. For a broad class of complex processes, this then allows calculating their statistical complexity dimension—the information dimension of the minimal set of predictive features.

Figure 1

(a) Equivocation: Same input sequence to a communication channel leads to different outputs. (b) Ambiguity: Two different inputs lead to same output. The strategy underlying Shannon's proof of his second coding theorem is to find channel inputs that are least ambiguous given the channel's distortion properties.

Figure 2

How a hidden Markov-DIFS generates a hidden Markov process: An initial state $\eta$—a distribution over three states: (0,0,1), (0,1,0), and (1,0,0)—in the 2-simplex is associated with a transition probability distribution over the alphabet $\mathcal{A}=\{\square ,▵\}$. If the emitted symbol selected from this distribution is $\square$, the next state is generated according to the associated mapping function $f^{(\square )}\left(\eta \right)$ and the probability distribution is updated accordingly. The same steps are followed if the symbol is $▵$ using $f^{\left(▵\right)}\left(\eta \right)$, resulting in an emitted process $\mathcal{P}$ over symbols $\mathcal{A}$.

Figure 3

The states and transitions of a hidden Markov-DIFS discussed in Sec. 7a embedded in the 1-simplex. In this case, the set $\mathcal{R}$ of states is countable and each subsequent application of $f^{\left(▵\right)}$ brings $\eta$ nearer to ${\eta }_{\infty }=(0,1)$. The latter is reached only after observing infinitely many $▵\mathrm{s}$. The countable nature of $\mathcal{R}$ arises from the fact that one of the mapping functions is a constant: $f^{(\square )}=(1,0)$.

Figure 4

Hidden Markov DIFSs may generate state sets with a wide variety of structures, many fractal in nature. Each subplot displays ${10}^5$ states of a different DIFS. The DIFSs themselves are specified in Appendix pp1.

Figure 5

Overlap problem on the 2-simplex ${\mathrm{\Delta }}^2$: Two distinct DIFSs (given in Appendix pp1) are considered, each with three mapping functions. Images of the mapping functions over the entire simplex are depicted as regions in red, blue, and green. (a) Images of the mapping functions $f^{\left(▵\right)}, f^{(\square )}$, and $f^{(\circ )}$ do not overlap—every possible state has a unique preimage. (b) Images of the mapping functions overlap—there exist ${\eta }_1,{\eta }_2\in {\mathrm{\Delta }}^2$ such that $f^{\prime \left(▵\right)}\left({\eta }_1\right)=f^{\prime (\square )}\left({\eta }_2\right)={\eta }_3$. This case is an overlapping DIFS.

Figure 6

Sources of ambiguity rate depicted in state machines: (a) $H\left[X_0\right|{\mathcal{R}}_0,{\mathcal{R}}_1]>0$—Previous state ${\mathcal{R}}_0$ is mapped to the next state ${\mathcal{R}}_1$ by two distinct symbols. This occurs when two symbols have identical mapping functions. (b) $I[X_0;{\mathcal{R}}_0|{\mathcal{R}}_1]>0$—Two distinct previous states ${\mathcal{R}}_0$ map to the same next state by distinct symbols, due to overlapping mapping functions. (c) $H\left[{\mathcal{R}}_0\right|X_0,{\mathcal{R}}_1]>0$—Two distinct previous states ${\mathcal{R}}_0$ map to the same next state by the same symbol. This occurs when a mapping function is noninvertible.

Figure 7

The entropy rate $h_{\mu }$, which in this case is equivalent to the ambiguity rate $h_a$, is plotted for the DIFS depicted in Fig. 3 for $p,q,\in (0,1)$.

Figure 8

One-dimensional attractor for the DIFS given in Eq. (19) with $x=0.25$ and horizontally varying $\alpha \in (0,1)$. State set $\eta \in \mathcal{R}$ plotted (red, blue, green) on top of the images of the mapping functions $\{f^{\left(▵\right)},f^{(\square )},f^{(\circ )}\}$ applied to $\mathcal{R}$. For $\alpha \in (0.07,0.78)$, there is overlap in the images of the maps.

Figure 9

Entropies and dimensions for the DIFS given in Eq. (19) with $\alpha \in (0,1)$ and $x=0.25$: (Top) Entropy rate $h_{\mu }$, ambiguity rate $h_a$, and $h_{\mu }-h_a$. (Bottom) Comparing $d_{\mathrm{\Gamma }}=h_{\mu }/{\lambda }_1$ to $d_{\mu }=(h_{\mu }-h_a)/{\lambda }_1$. The latter smoothly departs from the former. It is approximately 1 for much of the overlap region, except where it discontinuously jumps to zero at $\alpha =1/3$.

Figure 10

DIFS for $x=0.25$ and $\alpha =0.5$: (Top) Blackwell Measure ${\mu }_B$ approximated by Ulam's method with $k=400$. The two overlapping regions are overlaid and may be compared with Fig. 8. (Middle) Probability of each prior map is plotted. In nonoverlapping regions, only one prior map is possible. In the overlapping regions, there are complicated, fractal-like distributions over multiple prior maps. (Bottom) Shannon entropy over the prior map: Nonzero only in the overlapping regions.