Algorithme parallèle vers l'avant-arrière pour le modèle de Markov caché

Question

En tant que projet parallèle, je souhaite implémenter un modèle de Markov caché pour ma carte graphique NVidia afin que je puisse l'exécuter rapidement et utiliser de nombreux cœurs.

Je regarde l'algorithme Forward-Backward et je me demandais ce que je peux faire en parallèle ici? Si vous regardez la partie avant de l'algorithme par exemple, les multiplications matricielles peuvent être divisées en parallèle, mais les parties itératives de l'algorithme qui dépendent de l'étape précédente peuvent-elles être parallélisées de quelque façon que ce soit? Y a-t-il une sorte de tour mathématique qui peut être appliqué ici?

Merci,

mj

http://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm#Example

Answer 1

Vous avez raison dans votre évaluation - vous pouvez paralléliser la matrice multiplications (à savoir dans les états), mais vous ne pouvez pas paralléliser les étapes récursives. Je viens de publier un article sur mon travail avec les HMM et les GPU. Check it out ici:

http://sgmustadio.wordpress.com/2012/02/27/hidden-markov-models-in-cuda-gpu/

Answer 2

Si vous travaillez toujours sur ce projet, vous pouvez consulter HMMlib et parredHMMlib. Sgmustadio a raison de souligner que vous ne pouvez pas paralléliser les étapes récursives, mais il semble que ces auteurs aient trouvé une manière astucieuse de réduire les algorithmes Forward et Viterbi à une série de multiplications et de réductions matricielles.