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

الگوریتم پس‌رو-پیش‌رو یک الگوریتم استنباطی آماری برای مدل پنهان مارکف است که احتمال پسین توزیع حاشیه‌ای تمام متغییرهای حالت پنهان با توالی مشاهده‌شده را محاسبه می‌کند؛ یعنی برای تمام متغییرهای حالت پنهان توزیع را محاسبه می‌کند. به این عمل استنباطی معمولا «صاف‌کردن» می‌گویند. این الگوریتم از اصل برنامه‌نویسی پویا برای محاسبه کارآمد مقادیر مورد نیاز برای به دست آوردن احتمال پسین توضیح حاشیه‌ای، در دو پاس استفاده می‌کند. اولین پاس به جلو (پس) حرکت می‌کند در حالی که پاس دوم در همان زمان به عقب (پیش) می‌رود. از این رو نام پس‌رو-پیش‌رو را برای این الگوریتم انتخاب کردند.
در اصل اصطلاح «پس‌رو-پیش‌رو» به تمام الگوریتم‌هایی که به کلاس عمومی الگوریتم‌هایی که به صورت پس‌رونده-پیش‌رونده بر روی توالی‌ها عملیات انجام می‌دهند اطلاق می‌شود. در این مفهوم، توصیفات ارائه شده در باقی‌مانده این مقاله تنها به یک نمونه خاص از این کلاس اشاره می‌کند.
بررسی اجمالی
در پاس اول، این الگوریتم مجموعه احتمالاتی را محاسبه می‌کند که برای تمام ، احتمال پایان یافتن در یکی k حالت مشاهده‌شده اول در توالی است؛ یعنی . در پاس دوم، الگوریتم مجموعه احتمالاتی را محاسبه می‌کند که احتمال مشاهده کردن مشاهدات باقی مانده با شروع از نقطه K را به ما می‌دهد؛ یعنی . این دو مجموعه توزیعات احتمالاتی با ترکیب شدن با هم می‌توانند توزیع هر حالتی در هر زمانی را با داشتن توالی آن به دست آورند:
در قدم آخر با استفاده از قضیه بیز و استقلال مشروط و مقادیر .
همان‌طور که در بالا ذکر شده این الگوریتم شامل سه مرحله است:
محاسبه کردن احتمالات رو به جلو (پسین)
محاسبه کردن احتمالات رو به عقب (پیشین)
محاسبه کردن مقادیر «صاف شده».
الگوریتم پس‌رو-پیش‌رو می‌تواند محتمل‌ترین حالت را در هر نقطه زمانی پیدا کند اما نمی‌تواند برای پیدا کردن محتمل‌ترین توالی حالت‌ها استفاده شود (به الگوریتم ویتربی رجوع کنید)
احتمالات رو به جلو (پسین)
در توضیحات پیش رو به جای توزیع احتمالاتی، از ماتریس احتمالاتی استفاده می‌شود. در حالت عمومی از الگوریتم پس‌رو-پیش‌رو می‌توان هم در مدل‌های پیوسته و هم در مدل‌های گسسته احتمالاتی استفاده کرد.
ما توزیعات احتمالاتی مربوط به مدل پنهان مارکف را به ماتریس احتمالاتی تبدیل می‌کنیم. احتمالات \ (با متغیر تصادفی ) که تمامی حالات مدل پنهان مارکف را بیان می‌کند، به صورت ماتریس احتمالاتی نشان داده خواهند شد که در آن ستون‌ها با شاخص نماینده حالت پایانی هستند و ردیف‌ها با شاخص نماینده حالت آغازین. گذار(انتقال) از حالت بردار ردیفی به حالت بردار ردیفی افزایش یافته به صورت نشان داده می‌شود. مثال زیر نشان دهنده یک سیستم است که احتمال ماندن یک حالت در جای خودش بعد از هر مرحله ۷۰٪ و احتمال تبدیل شدن به حالت دیگر ۳۰٪ است. ماتریس انتقال به صورت زیر است:
\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
در این مثال احتمال مشاهده شدن واقعه یک زمانی که در حالت اول هستیم ۹۰٪ است در حالی که احتمال مشاهده شدن واقعه دو زمانی که در حالت اول هستیم ۱۰٪ می‌باشد. به همین ترتیب واقعه یک تنها ۲۰٪ اوقات مشاهده می‌شود اگر در حالت دوم باشیم و واقعه دو با احتمال ۸۰٪ در حالت دوم قابل مشاهده است. هر بردار افقی دلخواه نشان دهنده یک حالت از سیستم است( ) و احتمال مشاهده واقعه j به صورت زیر است:
ما می‌توانیم با جبر ماتریسی این عمل را به این صورت نشان بدهیم که بردار افقی را در ماتریس مشاهده ضرب کنیم. این ماتریس یک ماتریس قطری است یعنی به جز قطر اصلی تمامی درایه‌های آن صفر هستند و در درایه‌های قطر اصلی آن احتمال رویداد آن واقعه خاص در حالت مربوط به آن درایه وجود دارد. ماتریس مشاهده برای واقعه یک به صورت زیر است:
\mathbf{O_1 = \begin{pmatrix
0.9 - 0.0 \\
0.0 - 0.2
\end{pmatrix
این به ما اجازه می‌دهد تا با استفاده از قضیه بیز بردار احتمالاتی غیرنرمال شده را به دست آوریم. چون می‌دانیم احتمال این که هر عنصر رویداد یک را تولید کند به صورت زیر است:
\mathbf{\pi = \mathbf{\pi \mathbf{O_1
اکنون ما می‌توانیم این روش کلی را به مجموعه‌ای از مشاهدات خود اختصاص دهیم. فرض می‌کنیم بردار حالت اولیه ما ,>(که می‌تواند به صورت بازگشتی بهینه شود). به این صورت شروع می‌کنیم:
\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{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 )
حالا ما فرض می‌کنیم که در حالت خاص هستیم و چون این حالت فرض شده‌است یعنی احتمال این حالت ۱۰۰٪ است پس به این صورت در می‌آید:
\mathbf{b_{T:T = 1\ 1\ 1\ \dots^T
توجه کنید که ما در حال حاضر از یک بردار عمودی استفاده می‌کنیم و بردارهای احتمالاتی پسین ما افقی بودند. پس می‌توانیم عملیات زیر را انجام دهیم:
\mathbf{b_{t-1:T = \mathbf{T\mathbf{O_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(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)
برای درک این موضوع توجه داشته باشید که احتمال مشاهده کردن حالت داده شده را از طریق گذشتن از حالت در زمان t مشخص می‌کند. این احتمال شامل احتمالات پسین است که که تمام وقایع تا زمان t را پوشش می‌دهد و همچنین احتمال‌های پیشین که شامل تمام وقایع آینده می‌شود. این همان شمارنده‌ای است که در معادله به دنبالش بودیم و بر احتمال حقیقی توالی مشاهده شده تقسیم می‌کنیم تا بردار را نرمال کنیم و تنها احتمال . این ارزش‌ها گاهی اوقات به نام "ارزش‌های هموار (صاف شده)" خوانده می‌شوند زیرا برای به دست آوردن آن‌ها از احتمالات پسین و پیشین استفاده شده‌است تا احتمال نهایی را محاسبه کند.
بنابراین مقادیر احتمال بودن در هر حالت را در زمان t ارائه می‌کند. به این ترتیب آن‌ها برای تعیین محتمل‌ترین حالت به کار می‌روند. لازم است ذکر شود که اصطلاح «محتمل‌ترین حالت» تا حدودی مبهم است. برای توضیح باید گفت که محتمل‌ترین حالت، حالتی است که بیشترین احتمال برای درست بودن در یک نقطه معین را دارد اما محاسبه توالی احتمالات حالت‌ها احتمالا نتواند به ما محتمل‌ترین توالی را بدهد. این به خاطر این هست که احتمال برای هر نقطه به صورت مستقل از یک‌دیگر محاسبه می‌شود و احتمال شرطی میان‌حالتی محاسبه نمی‌شود و این به این معنی است که احتمالات حالت‌ها در زمان‌های t و t+1 متفاوت هست و ما با این فرمول نمی‌توانیم یک توالی را برای زمان‌های جلوتر محاسبه کنیم. به زبان ریاضی: .
برای به دست آوردن محتمل‌ترین دنباله از حالت‌ها که دنباله مشاهدات را تولید می‌کنند، می‌توانید از الگوریتم ویتربی استفاده کنید
مثال
این مثال منشاءاش را از جهان چتری(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{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix~~\mathbf{O_2 = \begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix~~\mathbf{O_3 = \begin{pmatrix0.1 - 0.0 \\ 0.0 - 0.8 \end{pmatrix~~\mathbf{O_4 = \begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix~~\mathbf{O_5 = \begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix
توجه داشته باشید که متفاوت است چون مرد «بدون چتر» مشاهده شده و در بقیه موارد «با چتر» دیده شده‌است.
شروع می‌کنیم به محاسبه احتمالات پیش‌رو، بنابراین یک بردار اولیه می‌گیریم:
\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{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.5000 \\ 0.5000 \end{pmatrix=
c_1^{-1\begin{pmatrix0.4500 \\ 0.1000\end{pmatrix=
\begin{pmatrix0.8182 \\ 0.1818 \end{pmatrix
(\mathbf{\hat{f_{0:2)^T =
c_2^{-1\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.8182 \\ 0.1818 \end{pmatrix=
c_2^{-1\begin{pmatrix0.5645 \\ 0.0745\end{pmatrix=
\begin{pmatrix0.8834 \\ 0.1166 \end{pmatrix
(\mathbf{\hat{f_{0:3)^T =
c_3^{-1\begin{pmatrix0.1 - 0.0 \\ 0.0 - 0.8 \end{pmatrix\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.8834 \\ 0.1166 \end{pmatrix=
c_3^{-1\begin{pmatrix0.0653 \\ 0.2772\end{pmatrix=
\begin{pmatrix0.1907 \\ 0.8093 \end{pmatrix
(\mathbf{\hat{f_{0:4)^T =
c_4^{-1\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.1907 \\ 0.8093 \end{pmatrix=
c_4^{-1\begin{pmatrix0.3386 \\ 0.1247\end{pmatrix=
\begin{pmatrix0.7308 \\ 0.2692 \end{pmatrix
(\mathbf{\hat{f_{0:5)^T =
c_5^{-1\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.7308 \\ 0.2692 \end{pmatrix=
c_5^{-1\begin{pmatrix0.5331 \\ 0.0815\end{pmatrix=
\begin{pmatrix0.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{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix1.0000 \\ 1.0000 \end{pmatrix=\alpha\begin{pmatrix0.6900 \\ 0.4100\end{pmatrix=\begin{pmatrix0.6273 \\ 0.3727 \end{pmatrix
\mathbf{\hat{b_{3:5 = \alpha\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix0.6273 \\ 0.3727 \end{pmatrix=\alpha\begin{pmatrix0.4175 \\ 0.2215\end{pmatrix=\begin{pmatrix0.6533 \\ 0.3467 \end{pmatrix
\mathbf{\hat{b_{2:5 = \alpha\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.1 - 0.0 \\ 0.0 - 0.8 \end{pmatrix\begin{pmatrix0.6533 \\ 0.3467 \end{pmatrix=\alpha\begin{pmatrix0.1289 \\ 0.2138\end{pmatrix=\begin{pmatrix0.3763 \\ 0.6237 \end{pmatrix
\mathbf{\hat{b_{1:5 = \alpha\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix0.3763 \\ 0.6237 \end{pmatrix=\alpha\begin{pmatrix0.2745 \\ 0.1889\end{pmatrix=\begin{pmatrix0.5923 \\ 0.4077 \end{pmatrix
\mathbf{\hat{b_{0:5 = \alpha\begin{pmatrix 0.7 - 0.3 \\ 0.3 - 0.7 \end{pmatrix\begin{pmatrix0.9 - 0.0 \\ 0.0 - 0.2 \end{pmatrix\begin{pmatrix0.5923 \\ 0.4077 \end{pmatrix=\alpha\begin{pmatrix0.3976 \\ 0.2170\end{pmatrix=\begin{pmatrix0.6469 \\ 0.3531 \end{pmatrix
در نهایت، ما احتمالات صاف‌شده را محاسبه می‌کنیم. این نتایج باید نرمال هم بشوند (جمع ورودی‌ها یک شود) چون ما در احتمالات پیشین، احتمالات را با
>> 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
الگوریتم باوم-ولچ
الگوریتم ویتربی
الگوریتم بی‌سی‌جی‌آر