موضوع مقاله: الگوریتم پس‌رو-پیش‌رو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم پس‌رو-پیش‌رو | مقدمه: این الگوریتم از اصل برنامه‌نویسی پویا برای محاسبه کارآمد مقادیر مورد نیاز برای به دست آوردن احتمال پسین توضیح حاشیه‌ای، در دو پاس استفاده می‌کند. | ## بخش 1: الگوریتم پس‌رو-پیش‌رو | اولین پاس به جلو (پس) حرکت می‌کند در حالی که پاس دوم در همان زمان به عقب (پیش) می‌رود. در اصل اصطلاح «پس‌رو-پیش‌رو» به تمام الگوریتم‌هایی که به کلاس عمومی الگوریتم‌هایی که به صورت پس‌رونده-پیش‌رونده بر روی توالی‌ها عملیات انجام می‌دهند گفته می‌شود. در این مفهوم، توصیفات ارائه شده در باقی‌ماندهٔ این مقاله تنها به یک نمونهٔ خاص از این کلاس اشاره می‌کند. بررسی اجمالی در پاس اول، این الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که برای تمام ، احتمال پایان یافتن در یکی k حالت مشاهده‌شدهٔ اول در توالی است؛ یعنی . در پاس دوم، الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که احتمال مشاهده کردن مشاهدات باقی مانده با شروع از نقطه K را به ما می‌دهد؛ یعنی . این دو مجموعهٔ توزیعات احتمالاتی با ترکیب شدن با هم می‌توانند توزیع هر حالتی در هر زمانی را با داشتن توالی آن به دست آورند: در قدم آخر با استفاده از قضیهٔ بیز و استقلال مشروط و مقادیر . همان‌طور که در بالا ذکر شده این الگوریتم شامل سه مرحله است: محاسبه کردن احتمالات رو به جلو (پسین) محاسبه کردن احتمالات رو به عقب (پیشین) محاسبه کردن مقادیر «صاف شده». الگوریتم پس‌رو-پیش‌رو می‌تواند محتمل‌ترین حالت را در هر نقطهٔ زمانی پیدا کند اما نمی‌تواند برای پیدا کردن محتمل‌ترین توالی حالت‌ها استفاده شود (به الگوریتم ویتربی رجوع کنید) احتمالات رو به جلو (پسین) در توضیحات پیش رو به جای توزیع احتمالاتی، از ماتریس احتمالاتی استفاده می‌شود. در حالت عمومی از الگوریتم پس‌رو-پیش‌رو می‌توان هم در مدل‌های پیوسته و هم در مدل‌های گسستهٔ احتمالاتی استفاده کرد. ما توزیعات احتمالاتی مربوط به مدل پنهان مارکف را به ماتریس احتمالاتی تبدیل می‌کنیم. احتمالات \ (با متغیر تصادفی ) که تمامی حالات مدل پنهان مارکف را بیان می‌کند، به صورت ماتریس احتمالاتی نشان داده خواهند شد که در آن ستون‌ها با شاخص نمایندهٔ حالت پایانی هستند و ردیف‌ها با شاخص نمایندهٔ حالت آغازین. گذار(انتقال) از حالت بردار ردیفی به حالت بردار ردیفی افزایش یافته به صورت نشان داده می‌شود. مثال زیر نشان دهندهٔ یک سیستم است که احتمال ماندن یک حالت در جای خودش بعد از هر مرحله ۷۰٪ و احتمال تبدیل شدن به حالت دیگر ۳۰٪ است. ماتریس انتقال به صورت زیر است: در مدل مارکف معمولی ما حالت فعلی را در این ماتریس ضرب می‌کردیم تا احتمالات حالت بعدی را به دست آوریم. اما در مدل پنهان مارکف حالت فعلی پنهان است و در عوض ما وقایع مرتبط با حالت فعلی را مشاهده می‌کنیم. یک ماتریس وقایع به صورت زیر است که احتمال مشاهده شدن هر واقعه را در هر حالت خاص بیان می‌کند: در این مثال احتمال مشاهده شدن واقعهٔ یک زمانی که در حالت اول هستیم ۹۰٪ است در حالی که احتمال مشاهده شدن واقعهٔ دو زمانی که در حالت اول هستیم ۱۰٪ می‌باشد. به همین ترتیب واقعهٔ یک تنها ۲۰٪ اوقات مشاهده می‌شود اگر در حالت دوم باشیم و واقعهٔ دو با احتمال ۸۰٪ در حالت دوم قابل مشاهده است. هر بردار افقی دلخواه نشان دهندهٔ یک حالت از سیستم است و احتمال مشاهدهٔ واقعه j به صورت زیر است: ما می‌توانیم با جبر ماتریسی این عمل را به این صورت نشان بدهیم که بردار افقی را در ماتریس مشاهده ضرب کنیم. این ماتریس یک ماتریس قطری است یعنی به جز قطر اصلی تمامی درایه‌های آن صفر هستند و در درایه‌های قطر اصلی آن احتمال رویداد آن واقعه خاص در حالت مربوط به آن درایه وجود دارد. | ## بخش 2: الگوریتم پس‌رو-پیش‌رو | ماتریس مشاهدهٔ برای واقعهٔ یک به صورت زیر است: این به ما اجازه می‌دهد تا با استفاده از قضیهٔ بیز بردار احتمالاتی غیرنرمال شدهٔ را به دست آوریم. چون می‌دانیم احتمال این که هر عنصر رویداد یک را تولید کند به صورت زیر است: اکنون ما می‌توانیم این روش کلی را به مجموعه ای از مشاهدات خود اختصاص دهیم. به این صورت شروع می‌کنیم: این فرایند می‌تواند رو به جلو (پس) تکرار شود و از مشاهدات اضافی و جدید نیز استفاده شود: نتیجه یک بردار پسین غیرنرمال احتمالاتی است. i اُمین ورودی این بردار نتیجه می‌دهد: به‌طور معمول ما در هر مرحله این بردار را نرمال می‌کنیم (جمع ورودی‌ها را یک می‌کنیم) یک عامل مقیاس گذاری را در هر مرحله به صورت زیر معرفی می‌کنیم: که در آن نشان دهنده بردار مقیاس‌پذیر از مرحله قبلی و نشان دهنده عامل مقیاس است که باعث می‌شود مجموع ورودی‌ها یک شود. ضرب عوامل مقیاس احتمال کامل مشاهدهٔ وقایع را بدون در نظر گرفتن شرایط نهایی به ما می‌دهد: ای به ما اجازه می‌دهد که بردار احتمالاتی مقیاس‌پذیر را این‌گونه تفسیر کنیم: پس تا به حال نتیجه گرفتین که ضرب عوامل مقیاس، احتمال حقیقی مشاهدهٔ توالی مورد نظر تا زمان t را مهیا می‌کند و این که بردار احتمالاتی اسکیل شده به ما احتمال بودن در هر حالت را در زمان می‌دهد. احتمالات رو به عقب (پیشین) با یک روش مشابه می‌توان احتمالات پیشین را محاسبه کرد. به صورت زیر: حالا ما فرض می‌کنیم که در حالت خاص هستیم و چون این حالت فرض شده‌است یعنی احتمال این حالت ۱۰۰٪ است پس به این صورت در می‌آید: توجه کنید که ما در حال حاضر از یک بردار عمودی استفاده می‌کنیم و بردارهای احتمالاتی پسین ما افقی بودند. پس می‌توانیم عملیات زیر را انجام دهیم: می‌توانیم این بردار را هم (مانند بخش قبل) نرمال کنیم اما معمولاً این کار را انجام نمی‌دهند. هر ورودی احتمال واقعه‌ای در آینده را نشان می‌دهد و نرمال کردن این بردار معادل استفاده از قضیهٔ بیز برای پیدا کردن احتمال هر حالت برای ایجاد کردن واقعه‌های آینده است. از این معادله می‌توان نتیجه زیر را گرفت: این معادله برای این مفید است که اجازه می‌دهد تا احتمال کامل بودن در یک حالت در زمان داده شده t را داشته با ضرب کردن این مقادیر داشته باشیم: برای درک این موضوع توجه داشته باشید که احتمال مشاهده کردن حالت داده شده را از طریق گذشتن از حالت در زمان t مشخص می‌کند. این احتمال شامل احتمالات پسین است که که تمام وقایع تا زمان t را پوشش می‌دهد و همچنین احتمال‌های پیشین که شامل تمام وقایع آینده می‌شود. این همان شمارنده‌ای است که در معادله به دنبالش بودیم و بر احتمال حقیقی توالی مشاهده شده تقسیم می‌کنیم تا بردار را نرمال کنیم و تنها احتمال . این ارزش‌ها گاهی اوقات به نام "ارزش‌های هموار (صاف شده)" خوانده می‌شوند زیرا برای به دست آوردن آن‌ها از احتمالات پسین و پیشین استفاده شده‌است تا احتمال نهایی را محاسبه کند. برای توضیح باید گفت که محتمل‌ترین حالت، حالتی است که بیشترین احتمال برای درست بودن در یک نقطه معین را دارد اما محاسبه توالی احتمالات حالت‌ها احتمالاً نتواند به ما محتمل‌ترین توالی را بدهد. این به خاطر این هست که احتمال برای هر نقطه به صورت مستقل از یک‌دیگر محاسبه می‌شود و احتمال شرطی میان‌حالتی محاسبه نمی‌شود و این به این معنی است که احتمالات حالت‌ها در زمان‌های t و t+1 متفاوت هست و ما با این فرمول نمی‌توانیم یک توالی را برای زمان‌های جلوتر محاسبه کنیم. برای به دست آوردن محتمل‌ترین دنباله از حالت‌ها که دنبالهٔ مشاهدات را تولید می‌کنند، می‌توانید از الگوریتم ویتربی استفاده کنید مثال این مثال منشاءاش را از جهان چتری(umbrella world) در راسل و نوریگ ۲۰۱۰ فصل ۱۵, صفحات ۵۶۶ می‌آورد که در آن ما می‌خواهم با مشاهداتمان از چتر داشتن یا نداشتن یک مرد وضعیت آب و هوا را نتیجه‌گیری کنیم. ما دو حالت مختلف را برای آب و هوا فرض می‌کنیم: حالت اول = باران ببارد؛ حالت دوم = باران نبارد. ما فرض می‌کنیم که آب و هوا است ۷۰٪ شانس ماندن در همان وضعیت خودش را دارد و ۳۰٪ شانس برای تغییر حالت دادن. پس ماتریس تغییرات ما به شکل زیر خواهد شد: ما همچنین فرض کنیم که هر حالت دو واقعه را دربردارد: واقعه اول = مرد چتر بیاورد؛ واقعه دوم = مرد چتر نیاورد. | ## بخش 3: الگوریتم پس‌رو-پیش‌رو | پس احتمالات چتر آوردن و چتر نیاوردن را برای هر حالت (بارانی و غیر بارانی) در ماتریس احتمالات می‌نویسیم. فرض کنید احتمال این که بارانی باشد و چتر بیاورد ۹۰٪؛ بارانی باشد و چتر بیاورد ۱۰٪؛ بارانی نباشد و چتر بیاورد ۲۰٪؛ بارانی نباشد و چتر نیاورد ۸۰٪ است: با داشتن این اطلاعات بعد از آن که توالی وقایع را به‌ترتیب {چتر، چتر، بدون چتر، چتر، چتر} مشاهده کردیم می‌توانیم محاسبات خود را شروع کنیم: توجه داشته باشید که متفاوت است چون مرد «بدون چتر» مشاهده شده و در بقیه موارد «با چتر» دیده شده‌است. شروع می‌کنیم به محاسبهٔ احتمالات پیش‌رو، بنابراین یک بردار اولیه می‌گیریم: به این دلیل بردار اولیه را انتخاب می‌کنیم، چون نمی‌دانیم قبل از مشاهدات ما آب و هوا در چه حالتی بود (بارانی بود یا نبود). معادلهٔ ما به صورت زیر می‌شود: به جای: توجه کنید که ماتریس انتقال نیز ترانهاده شده اما در مثال ما ترانهاده این ماتریس با خودش برابر است (چون ماتریس متقارن است). انجام این محاسبات و نرمال کردن این نتایج را فراهم می‌کند: شروع می‌کنیم به محاسبهٔ احتمالات پس‌رو، بنابراین یک بردار اولیه می‌گیریم: و بعد از آن شروع می‌کنیم به انجام محاسبات (مثل قبل): در نهایت، ما احتمالات صاف‌شده را محاسبه می‌کنیم. این نتایج باید نرمال هم بشوند (جمع ورودی‌ها یک شود) چون ما در احتمالات پیشین، احتمالات را با < اسکیل نکرده‌بودیم. این بدین دلیل است که هر دو و دارایاحتمالات پیشین و حالات‌های پایانی یکسان هستند و شامل تمامی مشاهدات ما هستند. اگرچه، تنها در زمانی برابر است که تمامی بردارهای حالت اولیه یکسان داشته باشند (یعنی تمامی آن‌ها ورودی برابر داشته باشند). وقتی شرایط چنین نیست e باید با بردار حالت اولیه ترکیب شود تا محتمل‌ترین حالت اولیه را پیدا کنیم. ما همچنان می‌دانیم که احتمالات پسین خودشان به اندازهٔ کافی اعتبار دارند تا محتمل‌ترین حالت پایانی را محاسبه کنند. به همین ترتیب احتمالات پسین هم می‌توانند با بردارهای حالات اولیه ترکیب شوند تا محتمل‌ترین حالت آغازین طبق مشاهدات را به ما بدهند. احتمالات پسین و پیشین با ترکیب با هم می‌توانند احتمال حالات محتمل آغازین و پایانی را محاسبه کنند. محاسبات فوق نشان می‌دهند که محتمل‌ترین حالت آب و هوا برای هر روز به غیر از روز سوم، آب و هوای «بارانی» است. البته این محاسبات به ما بیشتر از این می‌گویند، چون آن‌ها می‌توانند احتمالات هر حالت را در زمان‌های مختلف به ما ارائه کنند. شاید مهمتر از همه بدست آوردن اطلاع دربارهٔ حال ما با استفاده از این اطلاعات و محاسبات می‌توانیم حالات مختلف آب و هوای فردا را تنها با احتمال مشاهده کردن چتر پیش‌بینی کنیم. عملکرد با استفاده از الگوریتم جستجوی جامع برای حل این مسئله ما باید تمامی تا توالی حالات را تولید کنیم و احتمال هر یک از حالات آن را با استفاده از توالی وقایع (رویدادها) محاسبه کنیم. این رویکرد دارای پیچیدگی زمانی که در آن طول دنباله (توالی) و تعداد نمادهای استفاده شده در الفبای حالات است. این پیچیدگی زمانی برای مسائل کاربردی غیرقابل تحمل است زیرا تعداد توالی گره‌های حالات پنهان محتمل در عمل بسیار زیاد است. یک الگوریتم حافظه محور بهینه‌تر از الگوریتم پس‌رو-پیش‌رو وجود دارد به نام الگوریتم جزیره که استفادهٔ از حافظهٔ کمتر را با کشیدن زمان بیشتر تعویض کرده. | ## جمع‌بندی | اما بر روی یک کامپیوتر با تعداد نامحدودی پردازنده (تعدادی زیادتر از حجم محاسبات) پیچیدگی زمانی این الگوریتم می‌تواند به کاهش یابد درحالی که هنوز از پیچیدگی حافظه استفاده می‌کند.