الگوریتم پس‌رو-پیش‌رو

الگوریتم پس‌رو-پیش‌رو یک الگوریتم استنباطی آماری برای مدل پنهان مارکف است که احتمال پسین توزیع حاشیه‌ای تمام متغیرهای حالت پنهان با توالی مشاهده‌شدهٔ     را محاسبه می‌کند؛ یعنی برای تمام متغیرهای حالت پنهان  توزیع  را محاسبه می‌کند. به این عمل استنباطی معمولاً «صاف‌کردن» می‌گویند. این الگوریتم از اصل برنامه‌نویسی پویا برای محاسبه کارآمد مقادیر مورد نیاز برای به دست آوردن احتمال پسین توضیح حاشیه‌ای، در دو پاس استفاده می‌کند. اولین پاس به جلو (پس) حرکت می‌کند در حالی که پاس دوم در همان زمان به عقب (پیش) می‌رود. از این رو نام پس‌رو-پیش‌رو را برای این الگوریتم انتخاب کردند.
در اصل اصطلاح «پس‌رو-پیش‌رو» به تمام الگوریتم‌هایی که به کلاس عمومی الگوریتم‌هایی که به صورت پس‌رونده-پیش‌رونده بر روی توالی‌ها عملیات انجام می‌دهند اطلاق می‌شود. در این مفهوم، توصیفات ارائه شده در باقی‌ماندهٔ این مقاله تنها به یک نمونهٔ خاص از این کلاس اشاره می‌کند.

عملکرد

با استفاده از الگوریتم جستجوی جامع برای حل این مسئله ما باید تمامی  تا توالی حالات را تولید کنیم و احتمال هر یک از حالات آن را با استفاده از توالی وقایع (رویدادها) محاسبه کنیم. این رویکرد دارای پیچیدگی زمانی  که در آن  طول دنباله (توالی) و  تعداد نمادهای استفاده شده در الفبای حالات است. این پیچیدگی زمانی برای مسائل کاربردی غیرقابل تحمل است زیرا تعداد توالی گره‌های حالات پنهان محتمل در عمل بسیار زیاد است. در این صورت، الگوریتم پس‌رو-پیش‌رو می‌تواند این مسئله را در پیچیدگی زمانی .
یک الگوریتم حافظه محور بهینه‌تر از الگوریتم پس‌رو-پیش‌رو وجود دارد به نام الگوریتم جزیره که استفادهٔ از حافظهٔ کمتر را با کشیدن زمان بیشتر تعویض کرده. این الگوریتم دارای پیچیدگی زمان  است اما تنها از پیچیدگی حافظهٔ  استفاده می‌کند. اما بر روی یک کامپیوتر با تعداد نامحدودی پردازنده (تعدادی زیادتر از حجم محاسبات) پیچیدگی زمانی این الگوریتم می‌تواند به  کاهش یابد درحالی که هنوز از پیچیدگی حافظه  استفاده می‌کند.
علاوه بر این، این الگوریتم‌ها طوری تکوین یافته‌اند تا با استفاده از الگوریتم‌های صاف کردن برخط(online smoothing) مانند الگوریتم fixed-lag smoothing (FLS) مقادیر  به صورت کارآمد محاسبه کنند راسل و نووریگ ۲۰۱۰ شکل ۱۵٫۶ صفحهٔ ۵۸۰.

شبه کد

Backward(guessState, sequenceIndex):
  if sequenceIndex is past the end of the sequence, return 1
  if (guessState, sequenceIndex) has been seen before, return saved result
  result = ۰
  for each neighboring state n:
  result = result + (transition probability from guessState to
  n given observation element at sequenceIndex)
  * Backward(n, sequenceIndex+1)
  save result for (guessState, sequenceIndex)
  return result

مثال با زبان پایتون

با توجه HMM(مدل پنهان مارکف) (دقیقاً مانند الگوریتم ویتربی) در زبان برنامه‌نویسی پایتون نشان می‌دهیم:
states = ('Healthy', 'Fever')end_state = 'E'observations = ('normal', 'cold', 'dizzy')start_probability = {'Healthy': 0.6, 'Fever': 0.4}transition_probability = {
   'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E': 0.01},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E': 0.01},
   }emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }
ما می‌توانیم پیاده‌سازی را بدین شکل بنویسیم:
def fwd_bkw(observations, states, start_prob, trans_prob, emm_prob, end_st):
    # forward part of the algorithm
    fwd = []
    f_prev = {}
    for i, observation_i in enumerate(observations):
        f_curr = {}
        for st in states:
            if i == 0:
                # base case for the forward part
                prev_f_sum = start_prob[st]
            else:
                prev_f_sum = sum(f_prev[k]*trans_prob[k][st] for k in states)

            f_curr[st] = emm_prob[st][observation_i] * prev_f_sum

        fwd.append(f_curr)
        f_prev = f_curr

    p_fwd = sum(f_curr[k] * trans_prob[k][end_st] for k in states)

    # backward part of the algorithm
    bkw = []
    b_prev = {}
    for i, observation_i_plus in enumerate(reversed(observations[1:]+(None,))):
        b_curr = {}
        for st in states:
            if i == 0:
                # base case for backward part
                b_curr[st] = trans_prob[st][end_st]
            else:
                b_curr[st] = sum(trans_prob[st][l] * emm_prob[l][observation_i_plus] * b_prev[l] for l in states)

        bkw.insert(0,b_curr)
        b_prev = b_curr

    p_bkw = sum(start_prob[l] * emm_prob[l][observations[0]] * b_curr[l] for l in states)

    # merging the two parts
    posterior = []
    for i in range(len(observations)):
        posterior.append({st: fwd[i][st] * bkw[i][st] / p_fwd for st in states})

    assert p_fwd == p_bkw
    return fwd, bkw, posterior
تابع fwd_bkw این ورودی‌ها را می‌گیرد:
observations دنبالهٔ مشاهدات ما است مثلاً ['normal', 'cold', 'dizzy'];
states همان مجموعه ما از حالات پنهان است؛
start_prob احتمالات آغازین ما است؛ trans_prob احتمالات گذار ما است احتمالات و emm_prob احتمالات انتشار ما.
برای سادگی کد، ما فرض می‌کنیم که توالی مشاهدات ما observations خالی نیست و trans_prob[i][j] و [i][j]emm_prob تعریف شده‌است برای تمام حالات i,j.

در مثال اجرا شده، الگوریتم پس‌رو-پیش‌رو به صورت زیر استفاده شده‌است:
def example():
    return fwd_bkw(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability,
                   end_state)
>>> for line in example():...     print(*line)...{'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997}{'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01}{'Healthy': 0.8770110375573259, 'Fever': 0.1229889624426741} {'Healthy': 0.623228030950954, 'Fever': 0.3767719690490461} {'Healthy': 0.2109527048413057, 'Fever': 0.7890472951586943}