Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
Abstract
In applying Hidden Markov Models to the analysis of massive data streams, it is often necessary to use an arti(cid:12)cially reduced set of states; this is due in large part to the fact that the basic HMM estimation algorithms have a quadratic dependence on the size of the state set. We present algorithms that reduce this computational bottleneck to linear or near-linear time, when the states can be embedded in an underlying grid of parameters. This type of state representation arises in many domains; in particular, we show an application to tra(cid:14)c analysis at a high-volume Web site.
Cite
Text
Felzenszwalb et al. "Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis." Neural Information Processing Systems, 2003.Markdown
[Felzenszwalb et al. "Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis." Neural Information Processing Systems, 2003.](https://mlanthology.org/neurips/2003/felzenszwalb2003neurips-fast/)BibTeX
@inproceedings{felzenszwalb2003neurips-fast,
title = {{Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis}},
author = {Felzenszwalb, Pedro F. and Huttenlocher, Daniel P. and Kleinberg, Jon M.},
booktitle = {Neural Information Processing Systems},
year = {2003},
pages = {409-416},
url = {https://mlanthology.org/neurips/2003/felzenszwalb2003neurips-fast/}
}