Biomedical Engineering Reference
In-Depth Information
than one suffix, adding expressive power and allowing them to give compact
representations of a wider range of processes. (See (105) for more on this point,
with examples.)
All three techniques—CSMs, OOMs and PSRs—are basically equivalent,
though they differ in their formalisms and their emphases. CSMs focus on repre-
senting states as classes of histories with the same conditional distributions, i.e.,
as suffixes sharing a single context. (They also feature in the "statistical fore-
casting" approach to measuring complexity, discussed in §8.3.2 below.) OOMs
are named after the operators that update the state; there is one such operator for
each possible observation. PSRs, finally, emphasize the fact that one does not
actually need to know the probability of every possible string of future observa-
tions, but just a restricted subset of key trajectories, called "tests." In point of
fact, all of them can be regarded as special cases of more general prior construc-
tions due to Salmon ("statistical relevance basis") (106,107) and Knight ("meas-
ure-theoretic prediction process") (48,49), which were themselves independent.
(This area of the literature is more than usually tangled.)
Efficient
reconstruction algorithms
or
discovery procedures
exist for
building CSMs (105) and OOMs (103) directly from data. (There is currently no
such discovery procedure for PSRs, though there are parameter-estimation algo-
rithms (108).) These algorithms are reliable, in the sense that, given enough
data, the probability that they build the wrong set of states becomes arbitrarily
small. Experimentally, selecting an HMM architecture through cross-validation
never does better than reconstruction, and often much worse (105).
While these models are more powerful than VLMMs, there are still many
stochastic processes that cannot be represented in this form; or, rather, their rep-
resentation requires an infinite number of states (109,110). This is mathemati-
cally unproblematic, though reconstruction will then become much harder. (For
technical reasons, it seems likely to be easier to carry through for OOMs or
PSRs than for CSMs.) In fact, one can show that these techniques would work
straightforwardly on continuous-valued, continuous-time processes, if only we
knew the necessary conditional distributions (48,111). Devising a reconstruction
algorithm suitable for this setting is an extremely challenging and completely
unsolved problem; even parameter estimation is difficult, and currently only
possible under quite restrictive assumptions (112).
3.6.4.
Generating Partitions
So far, everything has assumed that we are either observing truly discrete
quantities, or that we have a fixed discretization of our continuous observations.
In the latter case, it is natural to wonder how much difference the discretization
makes. The answer, it turns out, is
quite a lot
; changing the partition can lead to
