الگوریتم باوم-ولچ
در مهندسی برق، علوم کامپیوتر، محاسبات آماری و بیوانفورماتیک، الگوریتم باوم-ولچ برای محاسبه پارامترهای مجهول مدل پنهان مارکوف بکار میرود.
مقدمه
این الگوریتم میتواند درستنمایی بیشینه (Maximum likelihood) را برای پارامترهای انتقال و انتشار یک مدل پنهان مارکوف محاسبه کند. این الگوریتم جزو الگوریتمهای یادگیری ماشین دستهبندی میشود. یعنی یک مجموعه داده از مشاهدات به عنوان داده های آموزشی در دسترس است و الگوریتم از روی این دادهها، پارامترهای مدل را تخمین میزند.
این الگوریتم به دادههایی که توسط الگوریتمهای Forward و Backward تولید میشوند نیاز دارد. پارامترهای مدل را به صورت زیر در نظر میگیریم:
الگوریتم forward
ایده الگوریتم اینگونه است که:
یعنی احتمال دیده شدن توالی X در مدل M برابر است با جمع احتمال دیده شدن توالی به شرط تمامی مسیرها که آن هم برابر است با
بنابر این میتوانیم روابط بازگشتی زیر را حساب کنیم:
ورودی این الگوریتم: مدل M با الفبای
خروجی: احتمال تولید این توالی توسط مدل
این الگوریتم به صورت پویا متغیر
Output: probability P(X|M)
Initialization: (i=0):
For all
Termination:P(X|M)=
الگوریتم backward
در الگوریتم backward رابطه بازگشتی برای محاسبه احتمال به صورت زیر است:
متغیر
Input: HMM M = (
Output: probability P(X|M)
Initialization: (i=L):
For all i=
Termination:P(X|M)=
شبهشماره
وقتی با دادههای آموزش سر و کار داریم، گاهی اوقات داده ها همه حالات را پوشش نمیدهند مثلاً در مورد مسایل مدل پنهان مارکوف، احتمال دارد در مجموعه دادههای آموزشی ما به دلایل مختلف انتقال از حالت i به حالت j مشاهده نشود در صورتی که این یک انتقال ممکن باشد، بنابراین احتمال این انتقال صفر محاسبه میشود که میتواند الگوریتم را به سمت جواب غلط پیش ببرد.
برای رفع این مشکل از شبهشمارهها( Pseudocount s) استفاده میکنیم. به این صورت که یک عدد کوچک را جای احتمال صفر، جایگزین میکنیم.
الگوریتم baum-welch
الگوریتم باوم-ولچ یک الگوریتم تکرار شونده است. ابتدا پارامترهای مدل به صورت تصادفی انتخاب میشوند و سپس در هر تکرار سعی میشود این پارامترها طوری اصلاح شوند که مدل به دادههای آموزشی نزدیک شود. میتوان آنقدر الگوریتم را تکرار کرد که تغییر قابل ملاحظهای در پارامترهای بدست آمده رخ ندهد.
ورودی: مدل و دادههای آموزشی
خروجی: مدل با پارامترهای انطباق یافته
شروع: ماتریسهای P و E را به صورت دلخواه مقداردهی میکنیم.
بازگشت
قرار میدهیم:
برای تمامی توالیهای
- را محاسبه میکنیم
- را به صورت روبرو بهبود میبخشیم
- را نیز اینگونه بهبود میدهیم:
شبهشمارهها را در صورت لزوم اعمال میکنیم.
قرار میدهیم:
پایان: درجه درستنمایی بیشینه را محاسبه میکنیم، اگر تغییر چندانی نکرد یا اینکه به تعداد مشخصی از تکرار رسیدیم، به الگوریتم خاتمه میدهیم.
پیوند به بیرون
- An Interactive Spreadsheet for Teaching the Forward-Backward Algorithm (spreadsheet and article with step-by-step walkthrough)
- Formal derivation of the Baum-Welch algorithm بایگانیشده در ۲۸ فوریه ۲۰۱۲ توسط Wayback Machine
- Implementation of the Baum-Welch algorithm
منابع
- L. E. Baum, T. Petrie, G. Soules, and N. Weiss, <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.