الگوریتم پس‌رو-پیش‌رو
الگوریتم پس‌رو-پیش‌رو یک الگوریتم استنباطی آماری برای مدل پنهان مارکف است که احتمال پسین توزیع حاشیه‌ای تمام متغیرهای حالت پنهان با توالی مشاهده‌شدهٔ formula_1 را محاسبه می‌کند؛ یعنی برای تمام متغیرهای حالت پنهان formula_2 توزیع formula_3 را محاسبه می‌کند. به این عمل استنباطی معمولاً "«صاف‌کردن»" می‌گویند. این الگوریتم از اصل برنامه‌نویسی پویا برای محاسبه کارآمد مقادیر مورد نیاز برای به دست آوردن احتمال پسین توضیح حاشیه‌ای، در دو پاس استفاده می‌کند. اولین پاس به جلو (پس) حرکت می‌کند در حالی که پاس دوم در همان زمان به عقب (پیش) می‌رود. از این رو نام پس‌رو-پیش‌رو را برای این الگوریتم انتخاب کردند.
در اصل اصطلاح "«پس‌رو-پیش‌رو»" به تمام الگوریتم‌هایی که به کلاس عمومی الگوریتم‌هایی که به صورت پس‌رونده-پیش‌رونده بر روی توالی‌ها عملیات انجام می‌دهند اطلاق می‌شود. در این مفهوم، توصیفات ارائه شده در باقی‌ماندهٔ این مقاله تنها به یک نمونهٔ خاص از این کلاس اشاره می‌کند.
در پاس اول، این الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که برای تمام formula_4، احتمال پایان یافتن در یکی k حالت مشاهده‌شدهٔ اول در توالی است؛ یعنی formula_5. در پاس دوم، الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که احتمال مشاهده کردن مشاهدات باقی مانده با شروع از نقطه K را به ما می‌دهد؛ یعنی formula_6. این دو مجموعهٔ توزیعات احتمالاتی با ترکیب شدن با هم می‌توانند توزیع هر حالتی در هر زمانی را با داشتن توالی آن به دست آورند: در قدم آخر با استفاده از قضیهٔ بیز و استقلال مشروط formula_8 و formula_9 مقادیر formula_10.
همان‌طور که در بالا ذکر شده این الگوریتم شامل سه مرحله است:
الگوریتم پس‌رو-پیش‌رو می‌تواند محتمل‌ترین حالت را در هر نقطهٔ زمانی پیدا کند اما نمی‌تواند برای پیدا کردن محتمل‌ترین توالی حالت‌ها استفاده شود (به الگوریتم ویتربی رجوع کنید)
در توضیحات پیش رو به جای توزیع احتمالاتی، از ماتریس احتمالاتی استفاده می‌شود. در حالت عمومی از الگوریتم پس‌رو-پیش‌رو می‌توان هم در مدل‌های پیوسته و هم در مدل‌های گسستهٔ احتمالاتی استفاده کرد.
ما توزیعات احتمالاتی مربوط به مدل پنهان مارکف را به ماتریس احتمالاتی تبدیل می‌کنیم. احتمالات \formula_11 (با متغیر تصادفی formula_12) که تمامی حالات مدل پنهان مارکف را بیان می‌کند، به صورت ماتریس احتمالاتی formula_13 نشان داده خواهند شد که در آن ستون‌ها با شاخص formula_14 نمایندهٔ حالت پایانی هستند و ردیف‌ها با شاخص formula_15 نمایندهٔ حالت آغازین. گذار(انتقال) از حالت بردار ردیفی formula_16 به حالت بردار ردیفی افزایش یافته formula_17 به صورت formula_18 نشان داده می‌شود. مثال زیر نشان دهندهٔ یک سیستم است که احتمال ماندن یک حالت در جای خودش بعد از هر مرحله ۷۰٪ و احتمال تبدیل شدن به حالت دیگر ۳۰٪ است. ماتریس انتقال به صورت زیر است: در مدل مارکف معمولی ما حالت فعلی را در این ماتریس ضرب می‌کردیم تا احتمالات حالت بعدی را به دست آوریم. اما در مدل پنهان مارکف حالت فعلی پنهان است و در عوض ما وقایع مرتبط با حالت فعلی را مشاهده می‌کنیم. یک ماتریس وقایع به صورت زیر است که احتمال مشاهده شدن هر واقعه را در هر حالت خاص بیان می‌کند: در این مثال احتمال مشاهده شدن واقعهٔ یک زمانی که در حالت اول هستیم ۹۰٪ است در حالی که احتمال مشاهده شدن واقعهٔ دو زمانی که در حالت اول هستیم ۱۰٪ می‌باشد. به همین ترتیب واقعهٔ یک تنها ۲۰٪ اوقات مشاهده می‌شود اگر در حالت دوم باشیم و واقعهٔ دو با احتمال ۸۰٪ در حالت دوم قابل مشاهده است. هر بردار افقی دلخواه نشان دهندهٔ یک حالت از سیستم است(formula_21) و احتمال مشاهدهٔ واقعه j به صورت زیر است: ما می‌توانیم با جبر ماتریسی این عمل را به این صورت نشان بدهیم که بردار افقی formula_21 را در ماتریس مشاهده formula_24 ضرب کنیم. این ماتریس یک ماتریس قطری است یعنی به جز قطر اصلی تمامی درایه‌های آن صفر هستند و در درایه‌های قطر اصلی آن احتمال رویداد آن واقعه خاص در حالت مربوط به آن درایه وجود دارد. ماتریس مشاهدهٔ برای واقعهٔ یک به صورت زیر است: این به ما اجازه می‌دهد تا با استفاده از قضیهٔ بیز بردار احتمالاتی غیرنرمال شدهٔ formula_26 را به دست آوریم. چون می‌دانیم احتمال این که هر عنصرformula_21 رویداد یک را تولید کند به صورت زیر است: اکنون ما می‌توانیم این روش کلی را به مجموعه ای از مشاهدات خود اختصاص دهیم. فرض می‌کنیم بردار حالت اولیه ما formula_29,>(که می‌تواند به صورت بازگشتی بهینه شود). به این صورت شروع می‌کنیم: این فرایند می‌تواند رو به جلو (پس) تکرار شود و از مشاهدات اضافی و جدید نیز استفاده شود: نتیجه یک بردار پسین غیرنرمال احتمالاتی است. i اُمین ورودی این بردار نتیجه می‌دهد: به‌طور معمول ما در هر مرحله این بردار را نرمال می‌کنیم (جمع ورودی‌ها را یک می‌کنیم) یک عامل مقیاس گذاری را در هر مرحله به صورت زیر معرفی می‌کنیم: که در آن formula_34 نشان دهنده بردار مقیاس‌پذیر از مرحله قبلی و formula_35 نشان دهنده عامل مقیاس است که باعث می‌شود مجموع ورودی‌ها یک شود. ضرب عوامل مقیاس احتمال کامل مشاهدهٔ وقایع را بدون در نظر گرفتن شرایط نهایی به ما می‌دهد: ای به ما اجازه می‌دهد که بردار احتمالاتی مقیاس‌پذیر را این‌گونه تفسیر کنیم: پس تا به حال نتیجه گرفتین که ضرب عوامل مقیاس، احتمال حقیقی مشاهدهٔ توالی مورد نظر تا زمان t را مهیا می‌کند و این که بردار احتمالاتی اسکیل شده به ما احتمال بودن در هر حالت را در زمان می‌دهد.
با یک روش مشابه می‌توان احتمالات پیشین را محاسبه کرد. به صورت زیر: حالا ما فرض می‌کنیم که در حالت خاصformula_39 هستیم و چون این حالت فرض شده‌است یعنی احتمال این حالت ۱۰۰٪ است پس به این صورت در می‌آید: توجه کنید که ما در حال حاضر از یک بردار عمودی استفاده می‌کنیم و بردارهای احتمالاتی پسین ما افقی بودند. پس می‌توانیم عملیات زیر را انجام دهیم: می‌توانیم این بردار را هم (مانند بخش قبل) نرمال کنیم اما معمولاً این کار را انجام نمی‌دهند. هر ورودی احتمال واقعه‌ای در آینده را نشان می‌دهد و نرمال کردن این بردار معادل استفاده از قضیهٔ بیز برای پیدا کردن احتمال هر حالت برای ایجاد کردن واقعه‌های آینده است. در این‌جا هم مانند قسمت پسین از همان formula_35 استفاده می‌کنیم تنها formula_43 اسکیل شده نیست. عملیات به صورت زیر است: که در آن formula_45 نشان دهنده بردار اسکیل شده قبلی است. از این معادله می‌توان نتیجه زیر را گرفت: این معادله برای این مفید است که اجازه می‌دهد تا احتمال کامل بودن در یک حالت در زمان داده شده t را داشته با ضرب کردن این مقادیر داشته باشیم: برای درک این موضوع توجه داشته باشید که formula_48 احتمال مشاهده کردن حالت داده شده را از طریق گذشتن از حالت formula_49 در زمان t مشخص می‌کند. این احتمال شامل احتمالات پسین است که که تمام وقایع تا زمان t را پوشش می‌دهد و همچنین احتمال‌های پیشین که شامل تمام وقایع آینده می‌شود. این همان شمارنده‌ای است که در معادله به دنبالش بودیم و بر احتمال حقیقی توالی مشاهده شده تقسیم می‌کنیم تا بردار را نرمال کنیم و تنها احتمال formula_39. این ارزش‌ها گاهی اوقات به نام "ارزش‌های هموار (صاف شده)" خوانده می‌شوند زیرا برای به دست آوردن آن‌ها از احتمالات پسین و پیشین استفاده شده‌است تا احتمال نهایی را محاسبه کند.
بنابراین مقادیر formula_51 احتمال بودن در هر حالت را در زمان t ارائه می‌کند. به این ترتیب آن‌ها برای تعیین محتمل‌ترین حالت به کار می‌روند. لازم است ذکر شود که اصطلاح «محتمل‌ترین حالت» تا حدودی مبهم است. برای توضیح باید گفت که محتمل‌ترین حالت، حالتی است که بیشترین احتمال برای درست بودن در یک نقطه معین را دارد اما محاسبه توالی احتمالات حالت‌ها احتمالاً نتواند به ما محتمل‌ترین توالی را بدهد. این به خاطر این هست که احتمال برای هر نقطه به صورت مستقل از یک‌دیگر محاسبه می‌شود و احتمال شرطی میان‌حالتی محاسبه نمی‌شود و این به این معنی است که احتمالات حالت‌ها در زمان‌های t و t+1 متفاوت هست و ما با این فرمول نمی‌توانیم یک توالی را برای زمان‌های جلوتر محاسبه کنیم. به زبان ریاضی: formula_52.
برای به دست آوردن محتمل‌ترین دنباله از حالت‌ها که دنبالهٔ مشاهدات را تولید می‌کنند، می‌توانید از الگوریتم ویتربی استفاده کنید
این مثال منشاءاش را از جهان چتری(umbrella world) در راسل و نوریگ ۲۰۱۰ فصل ۱۵, صفحات ۵۶۶ می‌آورد که در آن ما می‌خواهم با مشاهداتمان از چتر داشتن یا نداشتن یک مرد وضعیت آب و هوا را نتیجه‌گیری کنیم. ما دو حالت مختلف را برای آب و هوا فرض می‌کنیم: حالت اول = باران ببارد؛ حالت دوم = باران نبارد. ما فرض می‌کنیم که آب و هوا است ۷۰٪ شانس ماندن در همان وضعیت خودش را دارد و ۳۰٪ شانس برای تغییر حالت دادن. پس ماتریس تغییرات ما به شکل زیر خواهد شد: ما همچنین فرض کنیم که هر حالت دو واقعه را دربردارد: واقعه اول = مرد چتر بیاورد؛ واقعه دوم = مرد چتر نیاورد. پس احتمالات چتر آوردن و چتر نیاوردن را برای هر حالت (بارانی و غیر بارانی) در ماتریس احتمالات می‌نویسیم. فرض کنید احتمال این که بارانی باشد و چتر بیاورد ۹۰٪؛ بارانی باشد و چتر بیاورد ۱۰٪؛ بارانی نباشد و چتر بیاورد ۲۰٪؛ بارانی نباشد و چتر نیاورد ۸۰٪ است: با داشتن این اطلاعات بعد از آن که توالی وقایع را به‌ترتیب {چتر، چتر، بدون چتر، چتر، چتر} مشاهده کردیم می‌توانیم محاسبات خود را شروع کنیم: توجه داشته باشید که formula_56 متفاوت است چون مرد «بدون چتر» مشاهده شده و در بقیه موارد «با چتر» دیده شده‌است.
شروع می‌کنیم به محاسبهٔ احتمالات پیش‌رو، بنابراین یک بردار اولیه می‌گیریم: به این دلیل بردار اولیه را انتخاب می‌کنیم، چون نمی‌دانیم قبل از مشاهدات ما آب و هوا در چه حالتی بود (بارانی بود یا نبود). بردار اولیه ما باید یک بردار افقی باشد. برای راحت‌تر شدن محاسباتمان این بردار را ترانهاده می‌کنیم. معادلهٔ ما به صورت زیر می‌شود: به جای: توجه کنید که ماتریس انتقال نیز ترانهاده شده اما در مثال ما ترانهاده این ماتریس با خودش برابر است (چون ماتریس متقارن است). انجام این محاسبات و نرمال کردن این نتایج را فراهم می‌کند:
شروع می‌کنیم به محاسبهٔ احتمالات پس‌رو، بنابراین یک بردار اولیه می‌گیریم: و بعد از آن شروع می‌کنیم به انجام محاسبات (مثل قبل):
در نهایت، ما احتمالات صاف‌شده را محاسبه می‌کنیم. این نتایج باید نرمال هم بشوند (جمع ورودی‌ها یک شود) چون ما در احتمالات پیشین، احتمالات را با احتمالات پیشین و حالات‌های پایانی یکسان هستند و شامل تمامی مشاهدات ما هستند.
اگرچه، formula_77 تنها در زمانی برابر formula_78 است که تمامی بردارهای حالت اولیه یکسان داشته باشند (یعنی تمامی آن‌ها ورودی برابر داشته باشند). وقتی شرایط چنین نیست e formula_78 باید با بردار حالت اولیه ترکیب شود تا محتمل‌ترین حالت اولیه را پیدا کنیم. ما همچنان می‌دانیم که احتمالات پسین خودشان به اندازهٔ کافی اعتبار دارند تا محتمل‌ترین حالت پایانی را محاسبه کنند. به همین ترتیب احتمالات پسین هم می‌توانند با بردارهای حالات اولیه ترکیب شوند تا محتمل‌ترین حالت آغازین طبق مشاهدات را به ما بدهند. احتمالات پسین و پیشین با ترکیب با هم می‌توانند احتمال حالات محتمل آغازین و پایانی را محاسبه کنند.
محاسبات فوق نشان می‌دهند که محتمل‌ترین حالت آب و هوا برای هر روز به غیر از روز سوم، آب و هوای «بارانی» است. البته این محاسبات به ما بیشتر از این می‌گویند، چون آن‌ها می‌توانند احتمالات هر حالت را در زمان‌های مختلف به ما ارائه کنند. شاید مهمتر از همه بدست آوردن اطلاع دربارهٔ formula_79 حال ما با استفاده از این اطلاعات و محاسبات می‌توانیم حالات مختلف آب و هوای فردا را تنها با احتمال مشاهده کردن چتر پیش‌بینی کنیم.
با استفاده از الگوریتم جستجوی جامع برای حل این مسئله ما باید تمامی formula_87 تا توالی حالات را تولید کنیم و احتمال هر یک از حالات آن را با استفاده از توالی وقایع (رویدادها) محاسبه کنیم. این رویکرد دارای پیچیدگی زمانی formula_88 که در آن formula_89 طول دنباله (توالی) و formula_90 تعداد نمادهای استفاده شده در الفبای حالات است. این پیچیدگی زمانی برای مسائل کاربردی غیرقابل تحمل است زیرا تعداد توالی گره‌های حالات پنهان محتمل در عمل بسیار زیاد است. در این صورت، الگوریتم پس‌رو-پیش‌رو می‌تواند این مسئله را در پیچیدگی زمانی formula_91.
یک الگوریتم حافظه محور بهینه‌تر از الگوریتم پس‌رو-پیش‌رو وجود دارد به نام الگوریتم جزیره که استفادهٔ از حافظهٔ کمتر را با کشیدن زمان بیشتر تعویض کرده. این الگوریتم دارای پیچیدگی زمان formula_92 است اما تنها از پیچیدگی حافظهٔ formula_93 استفاده می‌کند. اما بر روی یک کامپیوتر با تعداد نامحدودی پردازنده (تعدادی زیادتر از حجم محاسبات) پیچیدگی زمانی این الگوریتم می‌تواند به formula_91 کاهش یابد درحالی که هنوز از پیچیدگی حافظه formula_93 استفاده می‌کند.
علاوه بر این، این الگوریتم‌ها طوری تکوین یافته‌اند تا با استفاده از الگوریتم‌های صاف کردن برخط(online smoothing) مانند الگوریتم fixed-lag smoothing (FLS) مقادیر formula_96 به صورت کارآمد محاسبه کنند راسل و نووریگ ۲۰۱۰ شکل ۱۵٫۶ صفحهٔ ۵۸۰.
با توجه HMM(مدل پنهان مارکف) (دقیقاً مانند الگوریتم ویتربی) در زبان برنامه‌نویسی پایتون نشان می‌دهیم: states = ('Healthy', 'Fever') end_state = 'E'
observations = ('normal', 'cold', 'dizzy')
transition_probability = {
emission_probability = { ما می‌توانیم پیاده‌سازی را بدین شکل بنویسیم: def fwd_bkw(observations, states, start_prob, trans_prob, emm_prob, end_st):
تابع codice_1 این ورودی‌ها را می‌گیرد: codice_2 دنبالهٔ مشاهدات ما است مثلاً codice_3; codice_4 همان مجموعه ما از حالات پنهان است؛ codice_5 احتمالات آغازین ما است؛ codice_6 احتمالات گذار ما است احتمالات و codice_7 احتمالات انتشار ما.
برای سادگی کد، ما فرض می‌کنیم که توالی مشاهدات ما codice_2 خالی نیست و codice_9 و codice_10 تعریف شده‌است برای تمام حالات i,j.
در مثال اجرا شده، الگوریتم پس‌رو-پیش‌رو به صورت زیر استفاده شده‌است: def example(): »> for line in example(): ... print(*line)