کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
536590 870569 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the memory complexity of the forward–backward algorithm
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر چشم انداز کامپیوتر و تشخیص الگو
پیش نمایش صفحه اول مقاله
On the memory complexity of the forward–backward algorithm
چکیده انگلیسی

The Forward–backward (FB) algorithm forms the basis for estimation of Hidden Markov Model (HMM) parameters using the Baum–Welch technique. It is however, known to be prohibitively costly when estimation is performed from long observation sequences. Several alternatives have been proposed in literature to reduce the memory complexity of FB at the expense of increased time complexity. In this paper, a novel variation of the FB algorithm – called the Efficient Forward Filtering Backward Smoothing (EFFBS) – is proposed to reduce the memory complexity without the computational overhead. Given an HMM with N states and an observation sequence of length T  , both FB and EFFBS algorithms have the same time complexity, O(N2T)O(N2T). Nevertheless, FB has a memory complexity of O(NT)O(NT), while EFFBS has a memory complexity that is independent of T  , O(N)O(N). EFFBS requires fewer resources than FB, yet provides the same results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Pattern Recognition Letters - Volume 31, Issue 2, 15 January 2010, Pages 91–99
نویسندگان
, , , ,