Share Email Print
cover

Proceedings Paper

Efficient inference of hidden Markov models from large observation sequences
Author(s): Benjamin W. Priest; George Cybenko
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

The hidden Markov model (HMM) is widely used to model time series data. However, the conventional Baum- Welch algorithm is known to perform poorly when applied to long observation sequences. The literature contains several alternatives that seek to improve the memory or time complexity of the algorithm. However, for an HMM with N states and an observation sequence of length T, these alternatives require at best O(N) space and O(N2T) time. Given the preponderance of applications that increasingly deal with massive amounts of data, an alternative whose time is O(T)+poly(N) is desired. Recent research presents an alternative to the Baum-Welch algorithm that relies on nonnegative matrix factorization. This document examines the space complexity of this alternative approach and proposes further optimizations using approaches adopted from the matrix sketching literature. The result is a streaming algorithm whose space complexity is constant and time complexity is linear with respect to the size of the observation sequence. The paper also presents a batch algorithm that allow for even further improved space complexity at the expense of an additional pass over the observation sequence.

Paper Details

Date Published: 12 May 2016
PDF: 9 pages
Proc. SPIE 9825, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security, Defense, and Law Enforcement Applications XV, 98250V (12 May 2016); doi: 10.1117/12.2230587
Show Author Affiliations
Benjamin W. Priest, Thayer School of Engineering at Dartmouth (United States)
George Cybenko, Thayer School of Engineering at Dartmouth (United States)


Published in SPIE Proceedings Vol. 9825:
Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security, Defense, and Law Enforcement Applications XV
Edward M. Carapezza, Editor(s)

© SPIE. Terms of Use
Back to Top