Two new approaches for learning Hidden Markov Models
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/61287 |
| _version_ | 1811097802878484480 |
|---|---|
| author | Kim, Hyun Soo, M. Eng. Massachusetts Institute of Technology |
| author2 | Leslie P. Kaelbling. |
| author_facet | Leslie P. Kaelbling. Kim, Hyun Soo, M. Eng. Massachusetts Institute of Technology |
| author_sort | Kim, Hyun Soo, M. Eng. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T17:05:11Z |
| format | Thesis |
| id | mit-1721.1/61287 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:05:11Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/612872019-04-12T13:54:23Z Two new approaches for learning Hidden Markov Models 2 new approaches for learning HMMs Kim, Hyun Soo, M. Eng. Massachusetts Institute of Technology Leslie P. Kaelbling. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 99-100). Hidden Markov Models (HMMs) are ubiquitously used in applications such as speech recognition and gene prediction that involve inferring latent variables given observations. For the past few decades, the predominant technique used to infer these hidden variables has been the Baum-Welch algorithm. This thesis utilizes insights from two related fields. The first insight is from Angluin's seminal paper on learning regular sets from queries and counterexamples, which produces a simple and intuitive algorithm that efficiently learns deterministic finite automata. The second insight follows from a careful analysis of the representation of HMMs as matrices and realizing that matrices hold deeper meaning than simply entities used to represent the HMMs. This thesis takes Angluin's approach and nonnegative matrix factorization and applies them to learning HMMs. Angluin's approach fails and the reasons are discussed. The matrix factorization approach is successful, allowing us to produce a novel method of learning HMMs. The new method is combined with Baum-Welch into a hybrid algorithm. We evaluate the algorithm by comparing its performance in learning selected HMMs to the Baum-Welch algorithm. We empirically show that our algorithm is able to perform better than the Baum-Welch algorithm for HMMs with at most six states that have dense output and transition matrices. For these HMMs, our algorithm is shown to perform 22.65% better on average by the Kullback-Liebler measure. by Hyun Soo Kim. M.Eng. 2011-02-23T14:42:05Z 2011-02-23T14:42:05Z 2010 2010 Thesis http://hdl.handle.net/1721.1/61287 702644273 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 100 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kim, Hyun Soo, M. Eng. Massachusetts Institute of Technology Two new approaches for learning Hidden Markov Models |
| title | Two new approaches for learning Hidden Markov Models |
| title_full | Two new approaches for learning Hidden Markov Models |
| title_fullStr | Two new approaches for learning Hidden Markov Models |
| title_full_unstemmed | Two new approaches for learning Hidden Markov Models |
| title_short | Two new approaches for learning Hidden Markov Models |
| title_sort | two new approaches for learning hidden markov models |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/61287 |
| work_keys_str_mv | AT kimhyunsoomengmassachusettsinstituteoftechnology twonewapproachesforlearninghiddenmarkovmodels AT kimhyunsoomengmassachusettsinstituteoftechnology 2newapproachesforlearninghmms |