Learning observable operator models via the ES algorithm 1
Hidden Markov Models (HMMs) today are the method of choice for blackbox modelling of symbolic, stochastic time series with memory. HMMs are usually trained using the expectation-maximization (EM) algorithm. This learning algorithm is note entirely satisfactory due to slow convergence and the presence of many globally suboptimal solutions. Observable operator models (OOMs) present an alternative. At the surface OOMs appear almost like HMMs: both can be expressed in structurally identical matrix formalisms. However, the matrices and state vectors of OOMs may contain negative components, whereas the corresponding components in the world of HMMs are non-negative probabilities. This freedom in sign gives OOMs algebraic properties that radically differ from HMMs, and leads to novel learning algorithms that are fast and yield asymptotically correct model estimates. Unfortunately, the basic versions of these algorithms are statistically inefficient, which has so far precluded a widespread use of OOMs. This chapter gives, first, a tutorial introduction to OOMs, and second, introduces a novel approach to OOM estimation called efficiency sharpening (ES). The ES method is iterative. In each iteration, the model estimated in the previous round is used to construct an estimator with a better statistical efficiency than the previous one. The computational load per iteration is comparable to one EM iteration, but only 2 to 5 iterations are typically needed. The chapter gives an analytical derivation of the ES principle and describes two learing algorithms that build on this principle, a simple “poor man’s” version and a more complicated but superior version which is based on a suffix-tree representation of the training string. The quality of the latter algorithm is demonstrated on a task of learning a model of a long belletristic text, where OOM models markedly outperform HMM models in quality, requiring only a fraction of learning time.