کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950920 | 1441044 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fully polynomial-time computation of maximum likelihood trajectories in Markov chains
ترجمه فارسی عنوان
محاسبات به طور کامل چندجملهای حداکثر مسیرهای احتمال در زنجیره مارکوف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زنجیره مارکوف، الگوریتم های گراف، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a Markov chain with n states, the initial state, the final state, and the trajectory length t, we consider the problem of finding the most likely trajectory of length t that the chain traversed. This is a well known problem typically addressed by a special case of the Viterbi algorithm, whose computational complexity depends linearly on t, and thus exponentially in the number of bits needed to specify t. In this work, we propose a particular decomposition of the Markov chain into a collection of cycles and walks, computable in polynomial time independent of t. For sufficiently large values of t (>n2+12n(n+1)), the most probable trajectory has a convenient characterization in terms of the above decomposition, and can be computed in time O(nlogâ¡t).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 118, February 2017, Pages 53-57
Journal: Information Processing Letters - Volume 118, February 2017, Pages 53-57
نویسندگان
Yuri Grinberg, Theodore J. Perkins,