[jira] [Commented] (MAHOUT-1484) Spectral algorithm for HMMs

["Ted Dunning (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/MAHOUT-1484?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13944482#comment-13944482 ] 

Ted Dunning commented on MAHOUT-1484:
-------------------------------------

Cool algo.

I only skimmed the paper, but it isn't quite obvious to me whether a partial SVD would work for this.  The authors mention a bound on singular values, but I didn't read carefully enough to see whether it was an upper or lower bound.  

Also, it isn't clear if this will work well with large sparse matrices.

Do you know the answers to these questions?

If this does provide a practical non-iterative HMM algorithm that scales, then it would be interesting to have in Mahout, especially as we improve the performance of the math library.

My guess is that the first step to determining whether this is a good idea is to implement a prototype in R.  Have you already done this?


> Spectral algorithm for HMMs
> ---------------------------
>
>                 Key: MAHOUT-1484
>                 URL: https://issues.apache.org/jira/browse/MAHOUT-1484
>             Project: Mahout
>          Issue Type: New Feature
>            Reporter: Emaad Manzoor
>            Priority: Minor
>
> Following up with this [comment|https://issues.apache.org/jira/browse/MAHOUT-396?focusedCommentId=12898284&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-12898284] by [~isabel] on the sequential HMM [proposal|https://issues.apache.org/jira/browse/MAHOUT-396], is there any interest in a spectral algorithm as described in: "A spectral algorithm for learning hidden Markov models (D. Hsu, S. Kakade, T. Zhang)"?
> I would like to take up this effort.
> This will enable learning the parameters of and making predictions with a HMM in a single step. At its core, the algorithm involves computing estimates from triples of observations, performing an SVD and then some matrix multiplications.
> This could also form the base for an implementation of "Hilbert Space Embeddings of Hidden Markov Models (L. Song, B. Boots, S. Saddiqi, G. Gordon, A. Smola)".



--
This message was sent by Atlassian JIRA
(v6.2#6252)