Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Efficient Mixed-Order Hidden Markov Model Inference
Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : University of Stellenbosch
2008
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613827229548544 |
|---|---|
| access_status_str | Open Access |
| author | Schwardt, Ludwig |
| author2 | Du Preez, J. A. |
| author_browse | Du Preez, J. A. Schwardt, Ludwig |
| author_facet | Du Preez, J. A. Schwardt, Ludwig |
| author_sort | Schwardt, Ludwig |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/1340 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:42:19.474Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2008 |
| publishDateRange | 2008 |
| publishDateSort | 2008 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/1340 Efficient Mixed-Order Hidden Markov Model Inference Schwardt, Ludwig Du Preez, J. A. University of Stellenbosch. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. Theses -- Electronic engineering Dissertations -- Electronic engineering Hidden Markov models Electrical and Electronic Engineering Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007. 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. Doctoral 2008-04-10T10:08:18Z 2010-06-01T08:19:01Z 2008-04-10T10:08:18Z 2010-06-01T08:19:01Z 2007-12 Thesis http://hdl.handle.net/10019.1/1340 en University of Stellenbosch 2736542 bytes application/pdf application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Theses -- Electronic engineering Dissertations -- Electronic engineering Hidden Markov models Electrical and Electronic Engineering Schwardt, Ludwig Efficient Mixed-Order Hidden Markov Model Inference |
| title | Efficient Mixed-Order Hidden Markov Model Inference |
| title_full | Efficient Mixed-Order Hidden Markov Model Inference |
| title_fullStr | Efficient Mixed-Order Hidden Markov Model Inference |
| title_full_unstemmed | Efficient Mixed-Order Hidden Markov Model Inference |
| title_short | Efficient Mixed-Order Hidden Markov Model Inference |
| title_sort | efficient mixed order hidden markov model inference |
| topic | Theses -- Electronic engineering Dissertations -- Electronic engineering Hidden Markov models Electrical and Electronic Engineering |
| url | http://hdl.handle.net/10019.1/1340 |
| work_keys_str_mv | AT schwardtludwig efficientmixedorderhiddenmarkovmodelinference |