Efficient Mixed-Order Hidden Markov Model Inference

Simple item page
dc.contributor.advisorDu Preez, J. A.
dc.contributor.authorSchwardt, Ludwigen_ZA
dc.contributor.otherUniversity of Stellenbosch. Faculty of Engineering. Dept. of Electrical and Electronic Engineering.
dc.date.accessioned2008-04-10T10:08:18Zen_ZA
dc.date.accessioned2010-06-01T08:19:01Z
dc.date.available2008-04-10T10:08:18Zen_ZA
dc.date.available2010-06-01T08:19:01Z
dc.date.issued2007-12
dc.descriptionThesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007.
dc.description.abstractHigher-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.en_ZA
dc.format.extent2736542 bytesen_ZA
dc.format.mimetypeapplication/pdfen_ZA
dc.identifier.urihttp://hdl.handle.net/10019.1/1340
dc.language.isoenen_ZA
dc.publisherStellenbosch : University of Stellenbosch
dc.rights.holderUniversity of Stellenbosch
dc.subjectTheses -- Electronic engineeringen_ZA
dc.subjectDissertations -- Electronic engineeringen_ZA
dc.subject.lcshHidden Markov modelsen_ZA
dc.subject.otherElectrical and Electronic Engineeringen_ZA
dc.titleEfficient Mixed-Order Hidden Markov Model Inferenceen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
schwardt_efficient_2007.pdf
Size:
2.35 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.72 KB
Format:
Plain Text
Description:
Download
Collections
Doctoral Degrees (Electrical and Electronic Engineering)