Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
Pedro F. Felzenszwalb, Daniel P. Huttenlocher, Jon M. Kleinberg · 2003
In applying Hidden Markov Models to the analysis of massive data streams, it is often necessary to use an artificially 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 parameter space. This type of state representation arises in many domains; in particular, we show an application to tra#c analysis at a high-volume Web site.