نمایش مبدأ برای الگوریتم باوم-ولچ

در [[مهندسی برق]]، [[علوم کامپیوتر]]، محاسبات آماری و [[بیوانفورماتیک]]، الگوریتم باوم-ولچ برای محاسبه پارامترهای مجهول [[مدل پنهان مارکوف]] بکار می‌رود.
== مقدمه ==
این الگوریتم می‌تواند [[درست‌نمایی بیشینه]] (Maximum likelihood) را برای پارامترهای انتقال و انتشار یک [[مدل پنهان مارکوف]] محاسبه کند. این الگوریتم جزو الگوریتم‌های [[یادگیری ماشین]] دسته‌بندی می‌شود. یعنی یک مجموعه داده از مشاهدات به عنوان [[داده های آموزشی]] در دسترس است و الگوریتم از روی این داده‌ها، پارامترهای مدل را تخمین می‌زند.

این الگوریتم به داده‌هایی که توسط الگوریتم‌های Forward و Backward تولید می‌شوند نیاز دارد. پارامترهای مدل را به صورت زیر در نظر می‌گیریم:

<math>p_{kl}</math> : احتمال انتقال از حالت k به حالت l

<math>e_l(\alpha)</math> : احتمال مشاهده الفبای <math>\alpha</math> در حالت l

== الگوریتم forward ==
ایده الگوریتم اینگونه است که:

<math>P(X|M)=\sum_\pi P(X,\pi|M)</math>

یعنی احتمال دیده شدن توالی X در مدل M برابر است با جمع احتمال دیده شدن توالی به شرط تمامی مسیرها که آن هم برابر است با

<math>= \sum_\pi P(X|\pi,M)P(\pi|M)</math>

بنابر این می‌توانیم روابط بازگشتی زیر را حساب کنیم:

<math>f_k(i)=P(x_1\dots x_i,\pi_i=k)</math>

<math>f_k(i+1)=e_l(x_{i+1})\sum_{k\in Q}f_k(i)p_{kl}</math>

ورودی این الگوریتم: مدل M با الفبای <math>\Sigma</math> احتمال‌های انتفال p و احتمال تولید الفبای e همچنین توالی‌ای از نشانه‌ها X

خروجی: احتمال تولید این توالی توسط مدل

این الگوریتم به صورت پویا متغیر <math>f_l(i)</math> را می‌سازد، که به معنی احتمال زیرتوالی <math>X_1</math> تا <math>X_i</math> در حالت l است.

{{چپ‌چین}}Input: HMM M = (<math>\Sigma</math>، Q, P, e) and sequence of symbols X

Output: probability P(X|M)

Initialization: (i=0): <math>f_0(0)=1,f_k(0)=0 </math> for k>0.

For all <math>i=1\dots,L,l\in Q:</math>

<math>f_l(i)=e_l(x_i)\sum_{k\in Q}f_k(i-1)p_{kl}</math>

Termination:P(X|M)=<math>\sum_{k\in Q}f_k(L)p_{k0}</math>
{{پایان چپ‌چین}}

== الگوریتم backward ==
در الگوریتم backward [[رابطه بازگشتی]] برای محاسبه احتمال به صورت زیر است:

<math>b_k(i)=P(x_{i+1}\dots x_L,\pi_i=k)</math>
<math>b_k(i)=\sum_{l\in Q}e_l(x_{i+1})b_l(i+1)p_{kl}</math>

متغیر <math>b_k(i)</math> احتمال مشاهدی زیرتوالی <math>X_i</math> تا <math>X_L</math> است در صورتی که در حالت k قرار داشته باشیم.
{{چپ‌چین}}
Input: HMM M = (<math>\Sigma</math>، Q, P, e) and sequence of symbols X

Output: probability P(X|M)

Initialization: (i=L): <math>b_k(L)=p_{k0}</math> for all k.

For all i=<math>L-1\dots,1,k\in Q</math>:

<math>b_k(i)=\sum_{l\in Q}e_l(x_{i+1})b_l(i+1)p_{kl}</math>

Termination:P(X|M)=<math>\sum_{l\in Q}(p_{0l}.e_l(x_1).b_l(1))</math>
{{پایان چپ‌چین}}
== شبه‌شماره ==
وقتی با داده‌های آموزش سر و کار داریم، گاهی اوقات [[داده ها]] همه حالات را پوشش نمی‌دهند مثلاً در مورد مسایل مدل پنهان مارکوف، احتمال دارد در مجموعه داده‌های آموزشی ما به دلایل مختلف انتقال از حالت i به حالت j مشاهده نشود در صورتی که این یک انتقال ممکن باشد، بنابراین احتمال این انتقال صفر محاسبه می‌شود که می‌تواند الگوریتم را به سمت جواب غلط پیش ببرد.

برای رفع این مشکل از شبه‌شماره‌ها( Pseudocount s) استفاده می‌کنیم. به این صورت که یک عدد کوچک را جای احتمال صفر، جایگزین می‌کنیم.
== الگوریتم baum-welch ==
الگوریتم باوم-ولچ یک الگوریتم تکرار شونده است. ابتدا پارامترهای مدل به صورت تصادفی انتخاب می‌شوند و سپس در هر تکرار سعی می‌شود این پارامترها طوری اصلاح شوند که مدل به داده‌های آموزشی نزدیک شود. می‌توان آنقدر الگوریتم را تکرار کرد که تغییر قابل ملاحظه‌ای در پارامترهای بدست آمده رخ ندهد.

'''ورودی: ''' مدل و داده‌های آموزشی <math>x^1,x^2,\dots,x^n</math>

'''خروجی: '''مدل با پارامترهای انطباق یافته

'''شروع: '''ماتریس‌های P و E را به صورت دلخواه مقداردهی می‌کنیم.

== بازگشت ==

قرار می‌دهیم: <math>P_{kl}=0 , E_k(b)=0</math> یا اینکه با شبه‌شماره جایگزین می‌کنیم

برای تمامی توالی‌های <math>x^j</math>:

:<math>f^j , b^j , P(x^j)</math> را محاسبه می‌کنیم
:<math>P_{kl}</math> را به صورت روبرو بهبود می‌بخشیم <math>\frac{1}{P(x^j)}\sum_if_k^j(i)p_{lk}e_l(x^j_{i+1})b_l^j(i+1)</math>
:<math>E_k(b)</math> را نیز اینگونه بهبود می‌دهیم: <math>\frac{1}{P(x^j)}\sum_{\{i|x_i^j=b}f_k^j(i)b_l^j(i)</math>

شبه‌شماره‌ها را در صورت لزوم اعمال می‌کنیم.

قرار می‌دهیم: <math>p_{kl}=\frac{P_{kl}}{\sum_{q\in Q}P_{kq}} , e_k(b)=\frac{E_k(b)}{\sum_{s\in \Sigma}E_k(s)}</math>

'''پایان:''' درجه درست‌نمایی بیشینه را محاسبه می‌کنیم، اگر تغییر چندانی نکرد یا اینکه به تعداد مشخصی از تکرار رسیدیم، به الگوریتم خاتمه می‌دهیم.
== پیوند به بیرون ==
* [http://www.cs.jhu.edu/~jason/papers/#tnlp02 An Interactive Spreadsheet for Teaching the Forward-Backward Algorithm] (spreadsheet and article with step-by-step walkthrough)
* [http://pandamatak.com/people/anand/771/html/node26.html Formal derivation of the Baum-Welch algorithm] {{Webarchive|url=https://web.archive.org/web/20120228202329/http://pandamatak.com/people/anand/771/html/node26.html |date=۲۸ فوریه ۲۰۱۲ }}
* [http://www.kanungo.com/software/software.html#umdhmm Implementation of the Baum-Welch algorithm]
== منابع ==
{{پانویس}}
* L. E. Baum, T. Petrie, G. Soules, and N. Weiss, [http://www.jstor.org/sici?sici=0003-4851(197002)41:1<164:AMTOIT>2.0.CO;2-V "A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains"], Ann. Math. Statist., vol. 41, no. 1, pp. 164–171, 1970.

[[رده:الگوریتم‌های آماری]]
[[رده:الگوریتم‌های بیوانفورماتیک]]
[[رده:الگوریتم‌های تصادفی]]
[[رده:مدل‌های مارکوف]]