Efficient Mixed-Order Hidden Markov Model Inference
Date
2007-12
Authors
Schwardt, Ludwig
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
Higher-order Markov models are more powerful than first-order models, but
suffer from an exponential increase in model parameters with order, which leads
to data scarcity problems during training. A more efficient approach is to use
mixed-order Markov models, which model data sequences with contexts of different
lengths.
This study proposes two algorithms for inferring mixed-order Markov chains
and hidden Markov models (HMMs), respectively. The basis of these algorithms
is the prediction suffix tree (PST), an efficient representation of a mixed-order
Markov chain.
The smallest encoded context tree (SECT) algorithm constructs PSTs from
data, based on the minimum description length principle. It has no user-specifiable
parameters to tune, and will expand the depth of the resulting PST as far as
the data set allows it, making it a self-bounded algorithm. It is also faster than
the original PST inference algorithm.
The hidden SECT algorithm replaces the underlying Markov chain of an
HMM with a prediction suffix tree, which is inferred using SECT. The algorithm
is efficient and integrates well with standard techniques.
The properties of the SECT and hidden SECT algorithms are verified on synthetic
data. The hidden SECT algorithm is also compared with a fixed-order
HMM training algorithm on an automatic language recognition task, where the
resulting mixed-order HMMs are shown to be smaller and train faster than the
fixed-order models, for similar classification accuracies.
Description
Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007.
Keywords
Theses -- Electronic engineering, Dissertations -- Electronic engineering