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

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

الگوریتم پس‌رو-پیش‌رو یک الگوریتم استنباطی آماری برای مدل پنهان مارکف است که احتمال پسین توزیع حاشیه‌ای تمام متغیرهای حالت پنهان با توالی مشاهده‌شدهٔ $o_{1:t}:=o_{1},\dots ,o_{t}$ را محاسبه می‌کند؛ یعنی برای تمام متغیرهای حالت پنهان $X_{k}\in \{X_{1},\dots ,X_{t}\}$ توزیع $P(X_{k}\ |\ o_{1:t})$ را محاسبه می‌کند. به این عمل استنباطی معمولاً «صاف‌کردن» می‌گویند. این الگوریتم از اصل برنامه‌نویسی پویا برای محاسبه کارآمد مقادیر مورد نیاز برای به دست آوردن احتمال پسین توضیح حاشیه‌ای، در دو پاس استفاده می‌کند. اولین پاس به جلو (پس) حرکت می‌کند در حالی که پاس دوم در همان زمان به عقب (پیش) می‌رود. از این رو نام پس‌رو-پیش‌رو را برای این الگوریتم انتخاب کردند.

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

بررسی اجمالی

در پاس اول، این الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که برای تمام $k\in \{1,\dots ,t\}$، احتمال پایان یافتن در یکی k حالت مشاهده‌شدهٔ اول در توالی است؛ یعنی $P(X_{k}\ |\ o_{1:k})$. در پاس دوم، الگوریتم مجموعهٔ احتمالاتی را محاسبه می‌کند که احتمال مشاهده کردن مشاهدات باقی مانده با شروع از نقطه K را به ما می‌دهد؛ یعنی $P(o_{k+1:t}\ |\ X_{k})$. این دو مجموعهٔ توزیعات احتمالاتی با ترکیب شدن با هم می‌توانند توزیع هر حالتی در هر زمانی را با داشتن توالی آن به دست آورند:

$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})$

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

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

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

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

احتمالات رو به جلو (پسین)

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

ما توزیعات احتمالاتی مربوط به مدل پنهان مارکف را به ماتریس احتمالاتی تبدیل می‌کنیم. احتمالات \$\mathbf {P} (X_{t}\mid X_{t-1})$ (با متغیر تصادفی $X_{t}$) که تمامی حالات مدل پنهان مارکف را بیان می‌کند، به صورت ماتریس احتمالاتی $\mathbf {T}$ نشان داده خواهند شد که در آن ستون‌ها با شاخص $i$ نمایندهٔ حالت پایانی هستند و ردیف‌ها با شاخص $j$ نمایندهٔ حالت آغازین. گذار(انتقال) از حالت بردار ردیفی $\mathbf {\pi _{t}}$ به حالت بردار ردیفی افزایش یافته $\mathbf {\pi _{t+1}}$ به صورت $\mathbf {\pi _{t+1}} =\mathbf {\pi _{t}} \mathbf {T}$ نشان داده می‌شود. مثال زیر نشان دهندهٔ یک سیستم است که احتمال ماندن یک حالت در جای خودش بعد از هر مرحله ۷۰٪ و احتمال تبدیل شدن به حالت دیگر ۳۰٪ است. ماتریس انتقال به صورت زیر است:

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

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

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

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

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

ما می‌توانیم با جبر ماتریسی این عمل را به این صورت نشان بدهیم که بردار افقی $\mathbf {\pi }$ را در ماتریس مشاهده $\mathbf {O_{j}} =\mathrm {diag} (b_{*,o_{j}})$ ضرب کنیم. این ماتریس یک ماتریس قطری است یعنی به جز قطر اصلی تمامی درایه‌های آن صفر هستند و در درایه‌های قطر اصلی آن احتمال رویداد آن واقعه خاص در حالت مربوط به آن درایه وجود دارد. ماتریس مشاهدهٔ برای واقعهٔ یک به صورت زیر است:

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

این به ما اجازه می‌دهد تا با استفاده از قضیهٔ بیز بردار احتمالاتی غیرنرمال شدهٔ $\mathbf {\pi '}$ را به دست آوریم. چون می‌دانیم احتمال این که هر عنصر$\mathbf {\pi }$ رویداد یک را تولید کند به صورت زیر است:

$\mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}}$

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

$\mathbf {f_{0:0}} =\mathbf {\pi _{0}} \mathbf {T} \mathbf {O_{o(0)}}$

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

$\mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o(t)}}$

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

$\mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } )$

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

$\mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o(t)}}$

که در آن $\mathbf {{\hat {f}}_{0:t-1}}$ نشان دهنده بردار مقیاس‌پذیر از مرحله قبلی و $c_{t}$ نشان دهنده عامل مقیاس است که باعث می‌شود مجموع ورودی‌ها یک شود. ضرب عوامل مقیاس احتمال کامل مشاهدهٔ وقایع را بدون در نظر گرفتن شرایط نهایی به ما می‌دهد:

$\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } )=\prod _{s=1}^{t}c_{s}$

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

$\mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } )}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } )$

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

احتمالات رو به عقب (پیشین)

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

$\mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})$

حالا ما فرض می‌کنیم که در حالت خاص$X_{t}=x_{i}$ هستیم و چون این حالت فرض شده‌است یعنی احتمال این حالت ۱۰۰٪ است پس به این صورت در می‌آید:

$\mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}$

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

$\mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}}$

می‌توانیم این بردار را هم (مانند بخش قبل) نرمال کنیم اما معمولاً این کار را انجام نمی‌دهند. هر ورودی احتمال واقعه‌ای در آینده را نشان می‌دهد و نرمال کردن این بردار معادل استفاده از قضیهٔ بیز برای پیدا کردن احتمال هر حالت برای ایجاد کردن واقعه‌های آینده است. در این‌جا هم مانند قسمت پسین از همان $c_{t}$ استفاده می‌کنیم تنها $\mathbf {b_{T:T}}$ اسکیل شده نیست. عملیات به صورت زیر است:

$\mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}}$

که در آن $\mathbf {{\hat {b}}_{t:T}}$ نشان دهنده بردار اسکیل شده قبلی است. از این معادله می‌توان نتیجه زیر را گرفت:

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

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

$\mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } )={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } )}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)$

برای درک این موضوع توجه داشته باشید که $\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)$ احتمال مشاهده کردن حالت داده شده را از طریق گذشتن از حالت $x_{i}$ در زمان t مشخص می‌کند. این احتمال شامل احتمالات پسین است که که تمام وقایع تا زمان t را پوشش می‌دهد و همچنین احتمال‌های پیشین که شامل تمام وقایع آینده می‌شود. این همان شمارنده‌ای است که در معادله به دنبالش بودیم و بر احتمال حقیقی توالی مشاهده شده تقسیم می‌کنیم تا بردار را نرمال کنیم و تنها احتمال $X_{t}=x_{i}$. این ارزش‌ها گاهی اوقات به نام "ارزش‌های هموار (صاف شده)" خوانده می‌شوند زیرا برای به دست آوردن آن‌ها از احتمالات پسین و پیشین استفاده شده‌است تا احتمال نهایی را محاسبه کند.

بنابراین مقادیر $\mathbf {\gamma _{t}} (i)$ احتمال بودن در هر حالت را در زمان t ارائه می‌کند. به این ترتیب آن‌ها برای تعیین محتمل‌ترین حالت به کار می‌روند. لازم است ذکر شود که اصطلاح «محتمل‌ترین حالت» تا حدودی مبهم است. برای توضیح باید گفت که محتمل‌ترین حالت، حالتی است که بیشترین احتمال برای درست بودن در یک نقطه معین را دارد اما محاسبه توالی احتمالات حالت‌ها احتمالاً نتواند به ما محتمل‌ترین توالی را بدهد. این به خاطر این هست که احتمال برای هر نقطه به صورت مستقل از یک‌دیگر محاسبه می‌شود و احتمال شرطی میان‌حالتی محاسبه نمی‌شود و این به این معنی است که احتمالات حالت‌ها در زمان‌های t و t+1 متفاوت هست و ما با این فرمول نمی‌توانیم یک توالی را برای زمان‌های جلوتر محاسبه کنیم. به زبان ریاضی: $\mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})$.

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

مثال

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

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

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

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

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

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

توجه داشته باشید که $\mathbf {O_{3}}$ متفاوت است چون مرد «بدون چتر» مشاهده شده و در بقیه موارد «با چتر» دیده شده‌است.

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

$\mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}$

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

$(\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}$

به جای:

$\mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}}$

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

$(\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

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

$\mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}$

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

$\mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}$

$\mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}$

$\mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}$

$\mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}$

$\mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

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

$(\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

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

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

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

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

دقت داشته باشید که ارزش $\mathbf {\gamma _{0}}$ دقیقاً برابر است با $\mathbf {{\hat {b}}_{0:5}}$ و همچنین ارزش $\mathbf {\gamma _{5}}$ دقیقاً برابر است با $\mathbf {{\hat {f}}_{0:5}}$. این بدین دلیل است که هر دو $\mathbf {{\hat {f}}_{0:5}}$ و $\mathbf {{\hat {b}}_{0:5}}$ دارایاحتمالات پیشین و حالات‌های پایانی یکسان هستند و شامل تمامی مشاهدات ما هستند.

اگرچه، $\mathbf {\gamma _{0}}$ تنها در زمانی برابر $\mathbf {{\hat {b}}_{0:5}}$ است که تمامی بردارهای حالت اولیه یکسان داشته باشند (یعنی تمامی آن‌ها ورودی برابر داشته باشند). وقتی شرایط چنین نیست e $\mathbf {{\hat {b}}_{0:5}}$ باید با بردار حالت اولیه ترکیب شود تا محتمل‌ترین حالت اولیه را پیدا کنیم. ما همچنان می‌دانیم که احتمالات پسین خودشان به اندازهٔ کافی اعتبار دارند تا محتمل‌ترین حالت پایانی را محاسبه کنند. به همین ترتیب احتمالات پسین هم می‌توانند با بردارهای حالات اولیه ترکیب شوند تا محتمل‌ترین حالت آغازین طبق مشاهدات را به ما بدهند. احتمالات پسین و پیشین با ترکیب با هم می‌توانند احتمال حالات محتمل آغازین و پایانی را محاسبه کنند.

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

عملکرد

با استفاده از الگوریتم جستجوی جامع برای حل این مسئله ما باید تمامی $N^{T}$ تا توالی حالات را تولید کنیم و احتمال هر یک از حالات آن را با استفاده از توالی وقایع (رویدادها) محاسبه کنیم. این رویکرد دارای پیچیدگی زمانی $O(T\cdot N^{T})$ که در آن $T$ طول دنباله (توالی) و $N$ تعداد نمادهای استفاده شده در الفبای حالات است. این پیچیدگی زمانی برای مسائل کاربردی غیرقابل تحمل است زیرا تعداد توالی گره‌های حالات پنهان محتمل در عمل بسیار زیاد است. در این صورت، الگوریتم پس‌رو-پیش‌رو می‌تواند این مسئله را در پیچیدگی زمانی $O(N^{2}T)\,$.

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

علاوه بر این، این الگوریتم‌ها طوری تکوین یافته‌اند تا با استفاده از الگوریتم‌های صاف کردن برخط(online smoothing) مانند الگوریتم fixed-lag smoothing (FLS) مقادیر $\mathbf {f_{0:t+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 و رو به جلو–رو به عقب الگوریتم)