Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Efficient Decoding of High-order Hidden Markov Models
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_ | 1867613968423452673 |
|---|---|
| access_status_str | Open Access |
| author | Engelbrecht, Herman A. |
| author2 | Du Preez, J. A. |
| author_browse | Du Preez, J. A. Engelbrecht, Herman A. |
| author_facet | Du Preez, J. A. Engelbrecht, Herman A. |
| author_sort | Engelbrecht, Herman A. |
| 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/1095 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:44:34.165Z |
| 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/1095 Efficient Decoding of High-order Hidden Markov Models Engelbrecht, Herman A. Du Preez, J. A. University of Stellenbosch. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. Hidden Markov Model Decoding High-order Theses -- Electrical and electronic engineering Dissertations -- Electrical and electronic engineering Automatic speech recognition Electrical and Electronic Engineering Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007. Most speech recognition and language identification engines are based on hidden Markov models (HMMs). Higher-order HMMs are known to be more powerful than first-order HMMs, but have not been widely used because of their complexity and computational demands. The main objective of this dissertation was to develop a more time-efficient method of decoding high-order HMMs than the standard Viterbi decoding algorithm currently in use. We proposed, implemented and evaluated two decoders based on the Forward-Backward Search (FBS) paradigm, which incorporate information obtained from low-order HMMs. The first decoder is based on time-synchronous Viterbi-beam decoding where we wish to base our state pruning on the complete observation sequence. The second decoder is based on time-asynchronous A* search. The choice of heuristic is critical to the A* search algorithms and a novel, task-independent heuristic function is presented. The experimental results show that both these proposed decoders result in more time-efficient decoding of the fully-connected, high-order HMMs that were investigated. Three significant facts have been uncovered. The first is that conventional forward Viterbi-beam decoding of high-order HMMs is not as computationally expensive as is commonly thought. The second (and somewhat surprising) fact is that backward decoding of conventional, high-order left-context HMMs is significantly more expensive than the conventional forward decoding. By developing the right-context HMM, we showed that the backward decoding of a mathematically equivalent right-context HMM is as expensive as the forward decoding of the left-context HMM. The third fact is that the use of information obtained from low-order HMMs significantly reduces the computational expense of decoding high-order HMMs. The comparison of the two new decoders indicate that the FBS-Viterbi-beam decoder is more time-efficient than the A* decoder. The FBS-Viterbi-beam decoder is not only simpler to implement, it also requires less memory than the A* decoder. We suspect that the broader research community regards the Viterbi-beam algorithm as the most efficient method of decoding HMMs. We hope that the research presented in this dissertation will result in renewed investigation into decoding algorithms that are applicable to high-order HMMs. Doctoral 2008-03-26T11:56:12Z 2010-06-01T08:12:20Z 2008-03-26T11:56:12Z 2010-06-01T08:12:20Z 2007-12 Thesis http://hdl.handle.net/10019.1/1095 en University of Stellenbosch 984190 bytes application/pdf application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Hidden Markov Model Decoding High-order Theses -- Electrical and electronic engineering Dissertations -- Electrical and electronic engineering Automatic speech recognition Electrical and Electronic Engineering Engelbrecht, Herman A. Efficient Decoding of High-order Hidden Markov Models |
| title | Efficient Decoding of High-order Hidden Markov Models |
| title_full | Efficient Decoding of High-order Hidden Markov Models |
| title_fullStr | Efficient Decoding of High-order Hidden Markov Models |
| title_full_unstemmed | Efficient Decoding of High-order Hidden Markov Models |
| title_short | Efficient Decoding of High-order Hidden Markov Models |
| title_sort | efficient decoding of high order hidden markov models |
| topic | Hidden Markov Model Decoding High-order Theses -- Electrical and electronic engineering Dissertations -- Electrical and electronic engineering Automatic speech recognition Electrical and Electronic Engineering |
| url | http://hdl.handle.net/10019.1/1095 |
| work_keys_str_mv | AT engelbrechthermana efficientdecodingofhighorderhiddenmarkovmodels |