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

در پاس اول، این الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که برای تمام ${\displaystyle k\in \{1,\dots ,t\}}$

${\displaystyle P(X_k|o_{1:t})=P(X_k|o_{1:k},o_{k+1:t})\propto P(o_{k+1:t}|X_k)P(o_{1:k},X_k)}$

در قدم آخر با استفاده از قضیهٔ بیز و استقلال مشروط ${\displaystyle o_{k+1:t}}$

همان‌طور که در بالا ذکر شده این الگوریتم شامل سه مرحله است:

1. محاسبه کردن احتمالات رو به جلو (پسین)
2. محاسبه کردن احتمالات رو به عقب (پیشین)
3. محاسبه کردن مقادیر «صاف شده».

الگوریتم پس‌رو-پیش‌رو می‌تواند محتمل‌ترین حالت را در هر نقطهٔ زمانی پیدا کند اما نمی‌تواند برای پیدا کردن محتمل‌ترین توالی حالت‌ها استفاده شود (به الگوریتم ویتربی رجوع کنید)

در توضیحات پیش رو به جای توزیع احتمالاتی، از ماتریس احتمالاتی استفاده می‌شود. در حالت عمومی از الگوریتم پس‌رو-پیش‌رو می‌توان هم در مدل‌های پیوسته و هم در مدل‌های گسستهٔ احتمالاتی استفاده کرد.

ما توزیعات احتمالاتی مربوط به مدل پنهان مارکف را به ماتریس احتمالاتی تبدیل می‌کنیم. احتمالات \${\displaystyle \mathbf{P}(X_t\mid X_{t-1})}$

در مدل مارکف معمولی ما حالت فعلی را در این ماتریس ضرب می‌کردیم تا احتمالات حالت بعدی را به دست آوریم. اما در مدل پنهان مارکف حالت فعلی پنهان است و در عوض ما وقایع مرتبط با حالت فعلی را مشاهده می‌کنیم. یک ماتریس وقایع به صورت زیر است که احتمال مشاهده شدن هر واقعه را در هر حالت خاص بیان می‌کند:

در این مثال احتمال مشاهده شدن واقعهٔ یک زمانی که در حالت اول هستیم ۹۰٪ است در حالی که احتمال مشاهده شدن واقعهٔ دو زمانی که در حالت اول هستیم ۱۰٪ می‌باشد. به همین ترتیب واقعهٔ یک تنها ۲۰٪ اوقات مشاهده می‌شود اگر در حالت دوم باشیم و واقعهٔ دو با احتمال ۸۰٪ در حالت دوم قابل مشاهده است. هر بردار افقی دلخواه نشان دهندهٔ یک حالت از سیستم است(${\displaystyle \pi }$

${\displaystyle \mathbf{P}(O=j)=\sum _i{\pi }_i{b}_{j,i}}$

ما می‌توانیم با جبر ماتریسی این عمل را به این صورت نشان بدهیم که بردار افقی ${\displaystyle \pi }$

این به ما اجازه می‌دهد تا با استفاده از قضیهٔ بیز بردار احتمالاتی غیرنرمال شدهٔ ${\displaystyle {\pi }^{\prime }}$

${\displaystyle {\pi }^{\prime }=\pi {\mathbf{O}}_{\mathbf{1}}}$

اکنون ما می‌توانیم این روش کلی را به مجموعه ای از مشاهدات خود اختصاص دهیم. فرض می‌کنیم بردار حالت اولیه ما ${\displaystyle {\pi }_{\mathbf{0}}}$

${\displaystyle {\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{0}}={\pi }_{\mathbf{0}}\mathbf{T}{\mathbf{O}}_{\mathbf{o}\mathbf{(}\mathbf{0}\mathbf{)}}}$

این فرایند می‌تواند رو به جلو (پس) تکرار شود و از مشاهدات اضافی و جدید نیز استفاده شود:

${\displaystyle {\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}}={\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{T}{\mathbf{O}}_{\mathbf{o}\mathbf{(}\mathbf{t}\mathbf{)}}}$

نتیجه یک بردار پسین غیرنرمال احتمالاتی است. i اُمین ورودی این بردار نتیجه می‌دهد:

${\displaystyle {\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)=\mathbf{P}(o_1,o_2,\dots ,o_t,X_t=x_i|\pi )}$

به‌طور معمول ما در هر مرحله این بردار را نرمال می‌کنیم (جمع ورودی‌ها را یک می‌کنیم) یک عامل مقیاس گذاری را در هر مرحله به صورت زیر معرفی می‌کنیم:

${\displaystyle {\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}}=c_t^{-1}{\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{T}{\mathbf{O}}_{\mathbf{o}\mathbf{(}\mathbf{t}\mathbf{)}}}$

که در آن ${\displaystyle {\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{-}\mathbf{1}}}$

${\displaystyle \mathbf{P}(o_1,o_2,\dots ,o_t|\pi )=\prod _{s=1}^t{c}_s}$

ای به ما اجازه می‌دهد که بردار احتمالاتی مقیاس‌پذیر را این‌گونه تفسیر کنیم:

${\displaystyle {\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)=\frac{{\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)}{\prod _{s=1}^t{c}_s}=\frac{\mathbf{P}(o_1,o_2,\dots ,o_t,X_t=x_i|\pi )}{\mathbf{P}(o_1,o_2,\dots ,o_t|\pi )}=\mathbf{P}(X_t=x_i|o_1,o_2,\dots ,o_t,\pi )}$

پس تا به حال نتیجه گرفتین که ضرب عوامل مقیاس، احتمال حقیقی مشاهدهٔ توالی مورد نظر تا زمان t را مهیا می‌کند و این که بردار احتمالاتی اسکیل شده به ما احتمال بودن در هر حالت را در زمان می‌دهد.

با یک روش مشابه می‌توان احتمالات پیشین را محاسبه کرد. به صورت زیر:

${\displaystyle {\mathbf{b}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)=\mathbf{P}(o_{t+1},o_{t+2},\dots ,o_T|X_t=x_i)}$

حالا ما فرض می‌کنیم که در حالت خاص${\displaystyle X_t=x_i}$

${\displaystyle {\mathbf{b}}_{\mathbf{T}\mathbf{:}\mathbf{T}}=[111\dots {]}^T}$

توجه کنید که ما در حال حاضر از یک بردار عمودی استفاده می‌کنیم و بردارهای احتمالاتی پسین ما افقی بودند. پس می‌توانیم عملیات زیر را انجام دهیم:

${\displaystyle {\mathbf{b}}_{\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{:}\mathbf{T}}=\mathbf{T}{\mathbf{O}}_{\mathbf{t}}{\mathbf{b}}_{\mathbf{t}\mathbf{:}\mathbf{T}}}$

می‌توانیم این بردار را هم (مانند بخش قبل) نرمال کنیم اما معمولاً این کار را انجام نمی‌دهند. هر ورودی احتمال واقعه‌ای در آینده را نشان می‌دهد و نرمال کردن این بردار معادل استفاده از قضیهٔ بیز برای پیدا کردن احتمال هر حالت برای ایجاد کردن واقعه‌های آینده است. در این‌جا هم مانند قسمت پسین از همان ${\displaystyle c_t}$

${\displaystyle {\hat{\mathbf{b}}}_{\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{:}\mathbf{T}}=c_t^{-1}\mathbf{T}{\mathbf{O}}_{\mathbf{t}}{\hat{\mathbf{b}}}_{\mathbf{t}\mathbf{:}\mathbf{T}}}$

که در آن ${\displaystyle {\hat{\mathbf{b}}}_{\mathbf{t}\mathbf{:}\mathbf{T}}}$

${\displaystyle {\hat{\mathbf{b}}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)=\frac{{\mathbf{b}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)}{\prod _{s=t+1}^T{c}_s}}$

این معادله برای این مفید است که اجازه می‌دهد تا احتمال کامل بودن در یک حالت در زمان داده شده t را داشته با ضرب کردن این مقادیر داشته باشیم:

${\displaystyle {\gamma }_{\mathbf{t}}(i)=\mathbf{P}(X_t=x_i|o_1,o_2,\dots ,o_T,\pi )=\frac{\mathbf{P}(o_1,o_2,\dots ,o_T,X_t=x_i|\pi )}{\mathbf{P}(o_1,o_2,\dots ,o_T|\pi )}=\frac{{\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)\cdot {\mathbf{b}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)}{\prod _{s=1}^T{c}_s}={\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)\cdot {\hat{\mathbf{b}}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)}$

برای درک این موضوع توجه داشته باشید که ${\displaystyle {\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}}(i)\cdot {\mathbf{b}}_{\mathbf{t}\mathbf{:}\mathbf{T}}(i)}$

بنابراین مقادیر ${\displaystyle {\gamma }_{\mathbf{t}}(i)}$

برای به دست آوردن محتمل‌ترین دنباله از حالت‌ها که دنبالهٔ مشاهدات را تولید می‌کنند، می‌توانید از الگوریتم ویتربی استفاده کنید

این مثال منشاءاش را از جهان چتری(umbrella world) در راسل و نوریگ ۲۰۱۰ فصل ۱۵, صفحات ۵۶۶ می‌آورد که در آن ما می‌خواهم با مشاهداتمان از چتر داشتن یا نداشتن یک مرد وضعیت آب و هوا را نتیجه‌گیری کنیم. ما دو حالت مختلف را برای آب و هوا فرض می‌کنیم: حالت اول = باران ببارد؛ حالت دوم = باران نبارد. ما فرض می‌کنیم که آب و هوا است ۷۰٪ شانس ماندن در همان وضعیت خودش را دارد و ۳۰٪ شانس برای تغییر حالت دادن. پس ماتریس تغییرات ما به شکل زیر خواهد شد:

ما همچنین فرض کنیم که هر حالت دو واقعه را دربردارد: واقعه اول = مرد چتر بیاورد؛ واقعه دوم = مرد چتر نیاورد. پس احتمالات چتر آوردن و چتر نیاوردن را برای هر حالت (بارانی و غیر بارانی) در ماتریس احتمالات می‌نویسیم. فرض کنید احتمال این که بارانی باشد و چتر بیاورد ۹۰٪؛ بارانی باشد و چتر بیاورد ۱۰٪؛ بارانی نباشد و چتر بیاورد ۲۰٪؛ بارانی نباشد و چتر نیاورد ۸۰٪ است:

با داشتن این اطلاعات بعد از آن که توالی وقایع را به‌ترتیب {چتر، چتر، بدون چتر، چتر، چتر} مشاهده کردیم می‌توانیم محاسبات خود را شروع کنیم:

توجه داشته باشید که ${\displaystyle {\mathbf{O}}_{\mathbf{3}}}$

شروع می‌کنیم به محاسبهٔ احتمالات پیش‌رو، بنابراین یک بردار اولیه می‌گیریم:

به این دلیل بردار اولیه را انتخاب می‌کنیم، چون نمی‌دانیم قبل از مشاهدات ما آب و هوا در چه حالتی بود (بارانی بود یا نبود). بردار اولیه ما باید یک بردار افقی باشد. برای راحت‌تر شدن محاسباتمان این بردار را ترانهاده می‌کنیم. معادلهٔ ما به صورت زیر می‌شود:

${\displaystyle ({\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}}{)}^T=c_t^{-1}{\mathbf{O}}_{\mathbf{t}}(\mathbf{T}{)}^T({\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{-}\mathbf{1}}{)}^T}$

به جای:

${\displaystyle {\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}}=c_t^{-1}{\hat{\mathbf{f}}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{-}\mathbf{1}}\mathbf{T}{\mathbf{O}}_{\mathbf{t}}}$

توجه کنید که ماتریس انتقال نیز ترانهاده شده اما در مثال ما ترانهاده این ماتریس با خودش برابر است (چون ماتریس متقارن است). انجام این محاسبات و نرمال کردن این نتایج را فراهم می‌کند:

شروع می‌کنیم به محاسبهٔ احتمالات پس‌رو، بنابراین یک بردار اولیه می‌گیریم:

${\displaystyle {\mathbf{b}}_{\mathbf{5}\mathbf{:}\mathbf{5}}=\left(\begin{array}{c}1.0\\ 1.0\end{array}\right)}$

و بعد از آن شروع می‌کنیم به انجام محاسبات (مثل قبل):

در نهایت، ما احتمالات صاف‌شده را محاسبه می‌کنیم. این نتایج باید نرمال هم بشوند (جمع ورودی‌ها یک شود) چون ما در احتمالات پیشین، احتمالات را با <${\displaystyle c_t}$

${\displaystyle ({\gamma }_{\mathbf{0}}{)}^T=\alpha \left(\begin{array}{c}0.5000\\ 0.5000\end{array}\right)\circ \left(\begin{array}{c}0.6469\\ 0.3531\end{array}\right)=\alpha \left(\begin{array}{c}0.3235\\ 0.1765\end{array}\right)=\left(\begin{array}{c}0.6469\\ 0.3531\end{array}\right)}$

${\displaystyle ({\gamma }_{\mathbf{1}}{)}^T=\alpha \left(\begin{array}{c}0.8182\\ 0.1818\end{array}\right)\circ \left(\begin{array}{c}0.5923\\ 0.4077\end{array}\right)=\alpha \left(\begin{array}{c}0.4846\\ 0.0741\end{array}\right)=\left(\begin{array}{c}0.8673\\ 0.1327\end{array}\right)}$

${\displaystyle ({\gamma }_{\mathbf{2}}{)}^T=\alpha \left(\begin{array}{c}0.8834\\ 0.1166\end{array}\right)\circ \left(\begin{array}{c}0.3763\\ 0.6237\end{array}\right)=\alpha \left(\begin{array}{c}0.3324\\ 0.0728\end{array}\right)=\left(\begin{array}{c}0.8204\\ 0.1796\end{array}\right)}$

${\displaystyle ({\gamma }_{\mathbf{3}}{)}^T=\alpha \left(\begin{array}{c}0.1907\\ 0.8093\end{array}\right)\circ \left(\begin{array}{c}0.6533\\ 0.3467\end{array}\right)=\alpha \left(\begin{array}{c}0.1246\\ 0.2806\end{array}\right)=\left(\begin{array}{c}0.3075\\ 0.6925\end{array}\right)}$

${\displaystyle ({\gamma }_{\mathbf{4}}{)}^T=\alpha \left(\begin{array}{c}0.7308\\ 0.2692\end{array}\right)\circ \left(\begin{array}{c}0.6273\\ 0.3727\end{array}\right)=\alpha \left(\begin{array}{c}0.4584\\ 0.1003\end{array}\right)=\left(\begin{array}{c}0.8204\\ 0.1796\end{array}\right)}$

دقت داشته باشید که ارزش ${\displaystyle {\gamma }_{\mathbf{0}}}$

اگرچه، ${\displaystyle {\gamma }_{\mathbf{0}}}$

محاسبات فوق نشان می‌دهند که محتمل‌ترین حالت آب و هوا برای هر روز به غیر از روز سوم، آب و هوای «بارانی» است. البته این محاسبات به ما بیشتر از این می‌گویند، چون آن‌ها می‌توانند احتمالات هر حالت را در زمان‌های مختلف به ما ارائه کنند. شاید مهمتر از همه بدست آوردن اطلاع دربارهٔ ${\displaystyle {\gamma }_{\mathbf{5}}}$

با استفاده از الگوریتم جستجوی جامع برای حل این مسئله ما باید تمامی ${\displaystyle N^T}$

یک الگوریتم حافظه محور بهینه‌تر از الگوریتم پس‌رو-پیش‌رو وجود دارد به نام الگوریتم جزیره که استفادهٔ از حافظهٔ کمتر را با کشیدن زمان بیشتر تعویض کرده. این الگوریتم دارای پیچیدگی زمان ${\displaystyle O(N^{2}T\log T)}$

علاوه بر این، این الگوریتم‌ها طوری تکوین یافته‌اند تا با استفاده از الگوریتم‌های صاف کردن برخط(online smoothing) مانند الگوریتم fixed-lag smoothing (FLS) مقادیر ${\displaystyle {\mathbf{f}}_{\mathbf{0}\mathbf{:}\mathbf{t}\mathbf{+}\mathbf{1}}}$

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}

• الگوریتم باوم-ولچ
• الگوریتم ویتربی
• الگوریتم بی‌سی‌جی‌آر

• Lawrence R. Rabinerآموزش در مخفی مارکوف و مدل‌های انتخاب شده در برنامه‌های کاربردی در گفتار. مجموعه مقالات IEEE, 77 (2), p. 257-286 فوریه 1989. ۱۰٫۱۱۰۹/۵٫۱۸۶۲۶
• Lawrence R. Rabiner, B. H. Juang (January 1986). "An introduction to hidden Markov models". IEEE ASSP Magazine: 4–15.
• Eugene Charniak (1993). Statistical Language Learning. Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-53141-2.

• تعاملی گسترده برای آموزش به جلو–رو به عقب الگوریتم (صفحه گسترده و مقاله با گام به گام از طریق راه رفتن)
• آموزش پنهان مارکوف مدل از جمله رو به جلو–رو به عقب الگوریتم
• مجموعه ای از الگوریتم‌های هوش مصنوعی اجرا در جاوا (از جمله HMM و رو به جلو–رو به عقب الگوریتم)