Параллельный алгоритм прямого-обратного направления для скрытой марковской модели

В качестве побочного проекта я хочу реализовать Скрытую марковскую модель для своей видеокарты NVidia, чтобы она могла выполняться быстро и с использованием многих ядер.

Я смотрю на алгоритм Forward-Backward и мне интересно, что я могу сделать здесь параллельно? Например, если вы посмотрите на прямую часть алгоритма, матричные умножения можно разделить, чтобы выполнять их параллельно, но можно ли каким-либо образом распараллелить итерационные части алгоритма, зависящие от предыдущего шага? Можно ли здесь применить какой-то математический трюк?

Спасибо,

mj

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


parallel-processing math hidden-markov-models
person mj_    schedule 26.02.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Вы правы в своей оценке - вы можете распараллелить матричные умножения (т.е. между состояниями), но не можете распараллелить рекурсивные шаги. Я только что сделал запись в блоге о своей работе с HMM и графическими процессорами. Проверьте это здесь:

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

person sgmustadio    schedule 02.03.2012

arrow_upward
1
arrow_downward

Если вы все еще работаете над этим проектом, вы можете проверить HMMlib и parredHMMlib.

sgmustadio правильно указывает, что вы не можете распараллелить рекурсивные шаги, но кажется, что эти авторы придумали хитрый способ свести алгоритмы Форварда и Витерби к серии матричных умножений и сокращений.

person mortonjt    schedule 18.06.2013