مدل مارکوف پنهان

مدل پنهان مارکوف در حالت گسسته جز خانوادهٔ مسائل ظرف‌ها قرار می‌گیرد. به‌طور مثال از ربینر ۱۹۸۹: ظروف x1،x2،x3... و توپهای رنگی y1,y2,y3… را در نظر می‌گیریم، که نفر مقابل دنباله‌ای از توپ‌ها را مشاهده کرده ولی اطلاعی از دنبالهٔ ظرف‌هایی که توپ‌ها از آن‌ها انتخاب‌شده ندارد. ظرف n ام با احتمالی وابسته به ظرف n-1 ام انتخاب می‌شود و چون به انتخاب ظرف‌های خیلی قبل‌تر وابسته نیست یک فرایند مارکوف است.

شکل زیر معماری کلی یک نمونه HMM را نشان می‌دهد. هر شکل بیضی یک متغیر تصادفی است که می‌تواند هر عددی از مقادیر را انتخاب کند. متغیر تصادفی ${\displaystyle x(t)}$

در مدل پنهان مارکوف دو نوع پارامتر وجود دارد:احتمال جابه‌جایی‌ها (بین حالات) و احتمال خروجی‌ها (یا مشاهدات). احتمال جابه‌جایی نحوهٔ انتقال از حالت t-1 به t را کنترل می‌کند.

فضای حالت پنهان شامل N مقدار ممکن برای حالات است. متغیر پنهان در زمان t می‌تواند هر یک از این مقادیر را اختیار کند. احتمال جابجایی احتمال این است که در زمان t در حالت k (یکی از حالات ممکن) و در زمان t+1 در حالت k1 باشیم. بنابرین در کل ${\displaystyle N^2}$

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

اگر تعداد اعضای مجموعهٔ متغیرهای مشاهده‌ای برابر M باشد، بنابراین مجموع تعداد احتمالات خروجی NM می‌باشد/

با توجه به پارامترهای مدل پنهان مارکوف، می‌توانیم مسایلی به صورت زیر را حل کنیم.

• Annotation: مدل را داریم به این معنی که احتمالات مربوط به انتقال از حالتی به حالت دیگر و همین‌طور احتمال تولید الفبا در هر حالت معلوم است. توالی از مشاهدات داده شده، می‌خواهیم محتمل‌ترین مسیری (توالی حالات) که توالی را تولید می‌کند را پیدا کنیم. الگوریتم viterbi می‌تواند این‌گونه مسایل را به صورت پویا (Dynamic) حل کند.
• classification: مدل را داریم، توالی از مشاهدات داده شده‌است، می‌خواهیم احتمال (کل) تولید شدن این توالی توسط این مدل را (جمع احتمالات تمامی مسیرهایی که این توالی را تولید می‌کنند) حساب کنیم. الگوریتم forward
• Consensus: مدل را داریم، می‌خواهیم بدانیم محتمل‌ترین توالی که توسط این مدل تولید می‌شود (توالی که بیشترین احتمال را داراست) چیست. الگوریتم Backward
• Training: ساختار مدل را داریم به این معنی که تعداد حالات و الفبای تولیدی در هر حالت معلوم است، تعدادی توالی داریم (داده‌های آموزش) می‌خواهیم احتمال انتقال بین حالات و همین‌طور احتمال تولید الفبا در هر حالت را محاسبه کنیم. الگوریتم Baum-Welch

وظیفه یادگیری در HMM، یافتن بهترین احتمالات جابجایی‌ها و خروجی‌ها بر اساس یک دنباله یا دنباله‌هایی از خروجی هاست. معمولاً این پارامترها به وسیله متد maximum likelihood بر اساس خروجی داده شده تخمین زده می‌شوند. هیچ الگوریتم قطعی برای حل این مسئله وجود ندارد ولی برای پیدا کردن maximum likelihood محلی می‌توان از الگوریتم‌های کارایی مانند Baum-welch algorithmو یا Baldi-chauvin algorithmاستفاده کرد. الگوریتم Baum-Welch نمونه‌ای از الگوریتم forward-backwardو به صورت خاص موردی از الگوریتم expectation-maximization می‌باشد.

دو دوست به نام‌های آلیس و باب را در نظر بگیرید. آن‌ها دور از هم زندگی کرده و هر روز دربارهٔ کارهای روزمره‌شان با هم تلفنی صحبت می‌کنند. فعالیت‌های باب شامل "قدم زدن در پارک"،"خرید کردن" و "تمیز کردن آپارتمان" می‌شود. انتخاب اینکه هر روز کدام کار را انجام دهد منحصراً بستگی به هوای همان روز دارد. آلیس اطلاع دقیقی از هوای محل زندگی باب نداشته ولی از تمایلات کلی وی آگاه است (بنا به نوع هوا چه کاری را دوست دارد انجام دهد). بر اساس گفته‌های باب در پایان هر روز، آلیس سعی می‌کند هوای آن روز را حدس بزند. آلیس هوا را یک زنجیرهٔ گسستهٔ مارکوف می‌پندارد که دو حالت "بارانی" و "آفتابی" دارد. اما به‌طور مستقیم هوا را مشاهده نمی‌کند؛ بنابراین، حالات هوا بر او پنهان است. در هر روز احتمال اینکه باب به "قدم زدن"،"خرید کردن" و "تمیز کردن"بپردازد بستگی به هوا داشته و دارای یک احتمال مشخص است. مشاهدات مسئله شرح فعالیت‌هایی است که باب در انتهای هر روز به آلیس می‌گوید.

آلیس اطلاعات کلی دربارهٔ هوای محل زندگی باب و اینکه در هر نوع آب و هوا با چه احتمالی چه کار انجام می‌دهد را دارد. به عبارت دیگر پارامترهای مسئله HMM معلوم هستند که در کد زیر مشاهده می‌شوند:

states = ('Rainy', 'Sunny')

observations = ('walk', 'shop', 'clean')

start_probability = {'Rainy': 0.6, 'Sunny': 0.4}

transition_probability = {
   'Rainy': {'Rainy': 0.7, 'Sunny': 0.3},
   'Sunny': {'Rainy': 0.4, 'Sunny': 0.6},
  }

emission_probability = {
   'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
   'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
  }

در این کد start_probability نمایانگر احتمال رخ دادن هر یک از حالات HMM (بارانی یا آفتابی) در روز اولی که باب با آلیس صحبت می‌کند می‌باشد.transition_probability نمایانگر تغییر هوا بر اساس قواعد زنجیرهٔ مارکو است. به‌طور مثال اگر امروز بارانی باشد به احتمال ۳۰٪فردا آفتابی است.emition_probability نمایانگر این است که باب علاقه دارد که در هر هوایی چه کار کند به‌طور مثال در هوای بارانی با احتمال ۵۰٪ آپارتمانش را تمیز کرده یا در هوای آفتابی با احتمال ۶۰٪در پارک قدم می‌زند.

• بازشناسی گفتار
• ترجمه ماشینی
• پیش‌بینی ژن
• هم‌ترازسازی توالی
• تشخیص فعالیت
• تاشدگی پروتئین
• تشخیص چهره

مدل پنهان مارکوف برای اولین بار در مجموعه‌مقالات آماری leonard E.Baum و سایر نویسندگان در نیمه دوم دهه ۱۹۶۰ توضیح داده شد. یکی از اولین کاربردهای HMM تشخیص گفتار بوده که در اواسط دههٔ ۱۹۷۰ شروع شد. HMM در نیمهٔ دوم ۱۹۸۰ وارد حوزهٔ آنالیز دنباله‌های بیولوژیکی، به‌طور خاص DNA شد. از آن پس، کاربرد آن در بیوانفورماتیک گسترش یافت.

مدل پنهان مارکوف می‌تواند فرایندهای پیچیده مارکوف را که حالتها بر اساس توزیع احتمالی مشاهدات را نتیجه می‌دهند، مدل کند. به‌طور مثال اگر توزیع احتمال گوسین باشد در چنین مدل مارکوف پنهان خروجی حالتها نیز از توزیع گوسین تبعیت می‌کنند. علاوه بر این مدل پنهان مارکوف می‌تواند رفتارهای پیچیده‌تر را نیز مدل کند. جایی که خروجی حالت‌ها از ترکیب دو یا چند توزیع گوسین پیروی کند که در این حالت احتمال تولید یک مشاهده از حاصلضرب گوسین انتخاب شدهٔ اولی در احتمال تولید مشاهده از گوسین دیگر به دست می‌آید.

یک سیستم مانند شکل زیر را که در هر لحظه در یکی از حالت متمایز S1,... ,SN است در نظر بگیرید. در زمان‌های گسسته و با فواصل منظم، حالت سیستم با توجه به مجموعه‌ای از احتمالات تغییر می‌کند. برای زمان‌های… ,t=۱٬۲ حالت در لحظه t را با qt نشان می‌دهیم. برای یک توصیف مناسب از سیستم فعلی نیاز به دانستن حالت فعلی در کنار تمام حالات قبلی می‌باشد. برای یک حالت خاص از زنجیره مارکوف مرتبه اول، توصیف احتمالاتی تنها با حالت فعلی و حالت قبلی مشخص می‌شود.

${\displaystyle P(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_k,...)=}$

${\displaystyle P(q_t=S_j|q_{t-1}=S_i)}$

حال تنها فرایندهایی را در نظر می‌گیریم که در آن‌ها سمت راست رابطه فوق مستقل از زمان است و به همین دلیل ما مجموعه‌ای از احتمالات انتقال بین حالت‌ها را خواهیم داشت.

${\displaystyle a_{ij}=P(q_t=S_j|q_{t-1}=S_i)i\ge 1,N\ge j}$

که در آن احتمال انتقال بین حالات دارای خواص زیر است.

${\displaystyle a_{ij}\ge 0}$

${\displaystyle \sum _{j=1}^N{a}_{ij}=1}$

فرایند تصادفی فوق را مدل مارکوف قابل مشاهده می‌گویند زیرا خروجی مدل مجموعه‌ای از حالات است که قرار گرفتن در آن‌ها متناظر با یک مشاهده می‌باشد. ما می‌توانیم دنباله مشاهدات مورد انتظار خود را تولید کنیم و احتمال وقوع آن در زنجیره مارکوف را محاسبه نماییم. برای مثال با داشتن دنباله مشاهدات ${\displaystyle O=q_1,...,q_t}$

${\displaystyle P(O|Model)=P(q_1,q_2,...,q_2|Model)}$

${\displaystyle P(q_1).P(q_2|q_1).P(q_3|q_2)...P(q_t|q_{t-1})}$

یکی دیگر از مواردی که مطرح می‌شود این است که اگر سیستم در حالت ${\displaystyle q_i}$

۱- مدل مارکوف مرتبه صفر

یک مدل مارکوف از مرتبه صفر هیچ حافظه‌ای ندارد و برای هر t و t' در دنباله سمبل‌ها، ${\displaystyle pr(X_t=S_i)=pr(X_{t^{\prime }}=S_i)}$

۲- مدل مارکوف مرتبه اول

یک مدل مارکوف مرتبه اول دارای حافظه‌ای با طول ۱ می‌باشد. توزیع احتمال در این مدل به صورت زیر مشخص می‌شود.

${\displaystyle pr(X_t=S_i|X_{t-1}=S_j),fori=\mathrm{1..}k,j=\mathrm{1..}k}$

تعریف فوق مانند این است که k مدل مارکوف در مرتبه صفر برای هر ${\displaystyle S_j}$

۳- مدل مارکوف مرتبه m ام

مرتبه یک مدل مارکوف برابر است با طول حافظه‌ای که مقادیر احتمال ممکن برای حالت بعدی به کمک آن محاسبه می‌شود. برای مثال، حالت بعدی در یک مدل مارکوف از درجه ۲ (مدل مارکوف مرتبه دوم) به دو حالت قبلی آن بستگی دارد.

مثال ۱: برای مثال اگر یک سکه معیوب A داشته باشیم که احتمالات شیر یا خط آمدن برای آن یکسان نباشد، می‌توان آن را با یک مدل مارکوف درجه صفر با استفاده از احتمالات (pr(H و (pr(H توصیف نمود.

pr(H)=0.6, pr(T)=۰٫۴

مثال ۲: حال فرض کنید که سه سکه با شرایط فوق در اختیار داریم. سکه‌ها را با اسامی B, A و C نام‌گذاری می‌نماییم. آنگاه برای توصیف روال زیر به یک مدل مارکوف مرتبه اول نیاز داریم:

1. فرض کنید سکه X یکی از سکه‌های A یا B باشد.
2. مراحل زیر را تکرار می‌کنیم.

a) سکه X را پرتاب می‌کنیم و نتیجه را می‌نویسیم.

b) سکه C را نیز پرتاب می‌کنیم.

c) اگر سکه C خط آمد، آنگاه سکه X را تغییر می‌دهیم (A را با B یا B را با A جایگزین می‌کنیم) و در غیر این صورت تغییری در سکه‌ها نمی‌دهیم.

انجام روال فوق مدل مارکوف مرتبه اول زیر را نتیجه خواهد داد.

یک پردازش مارکوفی مانند نمونه فوق در طول پیمایش احتمالات، یک خروجی نیز خواهد داشت. یک خروجی نمونه برای پردازش فوق می‌تواند به شکل HTHHTHHttthtttHHTHHHHtthtthttht باشد.

مدل مارکوف فوق را می‌توان به صورت نموداری از حالات و انتقال‌ها نیز نشان داد. کاملاً مشخص است که این‌گونه بازنمایی از مدل مارکوف مانند بازنمایی یک ماشین انتقال حالت محدود است که هر انتقال با یک احتمال همراه می‌باشد

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

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

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

N تعداد حالتهای مدل M تعداد سمبلهای مشاهده در الفبا، اگر مشاهدات گسسته باشند آنگاه M یک مقدار نا محدود خواهد داشت.

${\displaystyle A=a_{ij}}$

${\displaystyle A=[a_{ij}]}$

${\displaystyle a_{ij}=p(q_{t+1}=j|q_t=i),i\ge 1,N\ge j}$

که در آن ${\displaystyle q_t}$

${\displaystyle a_{ij}\ge 0,i\ge 1,N\ge j}$

${\displaystyle \sum _{j=1}^N{a}_{ij}=1,1\le i\le N}$

برای حالات مدل ارگودیک برای تمامi وjها مقدار${\displaystyle a_{ij}}$

توزیع احتمال مشاهدات: یک توزیع احتمال برای هر یک از حالتها

${\displaystyle B=b_j(k)}$

${\displaystyle b_j(k)=p{o}_t=v_k|q_t=j,1\le j\le N,1\le k\le M}$

که در آن ${\displaystyle v_k}$

${\displaystyle b_j(k)1\le j\le N,1\le K\le M}$

${\displaystyle \sum _{K=1}^M{b}_j(k)=1,1\le j\le N}$

اگر مشاهدات به صورت پیوسته باشند، باید به جای احتمالهای گسسته از یک تابع چگالی احتمال پیوسته استفاده شود. معمولاً چگالی احتمال به کمک یک مجموع وزندار از M توزیع نرمال μ تخمین زده می‌شود.

${\displaystyle b_j(o_t)={\mathrm{\Sigma }}_{m=1}^M{c}_{jm}\mu ({\mu }_{jm},{\mathrm{\Sigma }}_{jm},o_t)}$

که در آن ${\displaystyle {\mu }_{jm}}$

${\displaystyle c_{jm},1\le j\le N,1\le m\le M}$

${\displaystyle \sum _{m=1}^M{c}_{jm}(k)=1,j\ge 1,N\ge j}$

توزیع احتمال حالت آغازین

${\displaystyle \pi =({\pi }_i)}$

${\displaystyle {\pi }_i=p(q_1=i),1\le i\le N}$

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

${\displaystyle \lambda =(\mathrm{A},\mathrm{B},\pi )}$

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

${\displaystyle \lambda =(\mathrm{A},C_{jm},{\mu }_{jm},{\mathrm{\Sigma }}_{jm},\pi )}$

همان‌طور که گفته شد نوع خاصی از HMM وجود دارد که در آن تمام حالات موجود با یکدیگر متصل هستند. لیکن مدل مخفی مارکوف از لحاظ ساختار و اصطلاحاً توپولوژی انواع مختلف دارد. همان‌طور که گفته شد برای مدل ارگودیک برای تمام i و jها ${\displaystyle a_{ij}>0}$

در قسمت‌های قبل مدل‌های HMM برای مجموعه مشاهدات گسسته را مورد بررسی قرار دادیم. اگر چه می‌توان با چندی‌سازی تمام فرایندهای پیوسته را به فرایندهای با دنباله مشاهدات گسسته تبدیل نمود، اما این کار ممکن است باعث افت مدل شود. در مدل HMM پیوسته احتمال قرار گرفتن مشاهدات در یک حالت را با توابع چگالی احتمال نشان می‌دهند. در این شرایط برای هر حالت i و ورودی O، احتمال مشاهده ${\displaystyle b_t(O)}$

${\displaystyle b_t(O)=\sum _{m=1}^M{c}_{im}R(O,{\mu }_{im},U_{im})}$

${\displaystyle c_{im}\ge 0,1\le i\le N,1\le m\le M}$

مدل مخلوط گوسی یکی از مهمترین روش‌های مدل کردن سیگنال است که در واقع شبیه یک HMM یک حالته است که تابع چگالی احتمال آن حالت دارای چندین مخلوط نرمال می‌باشد. احتمال تعلق بردار آزمایشیd به یک مدل مخلوط گاوسی دارای M مخلوط به شکل زیر بیان می‌شود:

${\displaystyle P(x|GMM)=\sum _{t=1}^M{c}_t.N({\mu }_t,{\mathrm{\Sigma }}_t),}$

که در آن ${\displaystyle c_t}$

برای به‌دست آوردن پارامترهای مدل GMM، شامل وزن مخلوط‌های گاوسی و میانگین و کواریانس توزیع‌ها، از الگوریتم ماکزیمم نمودن امید ریاضی(EM)استفاده می‌شود. باید توجه داشت که تعداد مخلوطهای گاوسی با تعداد نمونه‌های موجود آموزشی رابطه مستقیم دارند و نمی‌توان با مجموعه داده‌ای ناچیز یک مدل GMM دارای تعداد بیش از حد از مخلوطها را آموزش داد. در تشکیل و آموزش مدل GMM مانند تمام روش‌های تشکیل مدل رعایت نسبت میزان پیچیدگی مدل و نمونه‌های آموزشی الزامی می‌باشد.

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

۱- فرض مارکوف

با داشتن یک مدل پنهان مارکوف، احتمال انتقال از حالت i به حالت j به صورت زیر تعریف می‌شود:

${\displaystyle a_{ij}=p(q_{t+1}|q_t=i)}$

به بیان دیگر فرض می‌شود که حالت بعدی تنها به حالت فعلی بستگی دارد. مدل حاصل از فرض مارکوف یک مدل HMM مرتبه صفر می‌باشد. در حالت کلی، حالت بعدی می‌تواند با k حالت قبلی وابسته باشد. این مدل که مدل HMM مرتبه k ام گفته می‌شود، با استفاده از احتمالات انتقال به صورت زیر تعریف می‌گردد.

${\displaystyle a_{i1}{a}_{i2}{a}_{i3}ai4...=p(q_{t+1}=j|q_t=i_1,q_{t-1}=i_2....,q_{t-k+1}=i_k,1\le i_1,i_2,...i_k,j\le N))}$

به نظر می‌رسد که یک مدل HMM از مرتبه بالاتر باعث افزایش پیچیدگی مدل می‌شود. علی‌رغم اینکه مدل HMM مرتبه اول متداول‌ترین مدل است، برخی تلاشها برای استفاده از مدل‌های دارای مرتبه بالاتر نیز در حال انجام می‌باشد.

۲- فرض ایستایی (stationarity)

در اینجا فرض می‌شود که احتمال انتقال در بین حالات از زمان واقعی رخداد انتقال مستقل است. در این صورت می‌توان برا ی هر ${\displaystyle t_1,t_2}$

${\displaystyle p(q_{t_1+1}=j|q_{t_1}=i)=p(q_{t_2+1}=j|q_{t_2}=i}$

۳- فرض استقلال خروجی

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

${\displaystyle O=o_1,o_2,....o_T}$

آنگاه مطابق با این فرض برای مدل HMM با نام${\displaystyle \lambda }$

${\displaystyle p(O|q_1,q_2,..q_T,\lambda )=\begin{array}{c}\prod _{t=1}^{T}p(O_t|q_t,\lambda )\end{array}}$

اگر چه بر خلاف دو فرض دیگر این فرض اعتبار کمتری دارد. در برخی حالات این فرضیه چندان معتبر نیست و موجب می‌شود که مدل HMM با ضعفهای عمده‌ای مواجه گردد.

در این حالت مسئله این است که با داشتن مدل ${\displaystyle \lambda =(A,B,\pi )}$

متغیر پیشرو به صورت یک احتمال از دنباله مشاهدات ${\displaystyle O=\{O_1,O_2,...,O_t\}}$

${\displaystyle {\alpha }_t(i)=p\{O_1,O_2,...,O_t,q_t=i|\lambda \}}$

${\displaystyle a_{t+1}(j)=b_j(O_{t+1}\sum _{i=1}^N)a_t(i)a_{ij},1\le j\le N,1\le t\le T-1}$

که در آن

${\displaystyle a_1(j)={\pi }_j{b}_j(O_1),1\le j\le N}$

با داشتن این رابطه بازگشتی می‌توانیم مقدار زیر را محاسبه نماییم.

${\displaystyle a_T(i),1\le i\le N}$

و آنگاه احتمال ${\displaystyle P(O|\lambda )}$

${\displaystyle p\{O|\lambda \}=\sum _{i=1}^N{a}_T(i)}$

پیچیدگی محاسباتی روش فوق که به الگوریتم پیشرو معروف است برابر با ${\displaystyle O(N^{2}T)}$

روشی مشابه روش فوق را می‌توان با تعیین متغیر پسرو، ${\displaystyle {\beta }_t(i)}$

${\displaystyle {\beta }_t(i)=p\{O_{t+1},O_{t+2},...,O_T|q_t=i,\lambda \}}$

مانند روش پیشرو یک رابطه بازگشتی به شکل زیر برای محاسبه ${\displaystyle {\beta }_t(i)}$

${\displaystyle {\beta }_t(i)=\sum _{i=1}^N{\beta }_{t+1}(j)a_{ij}{b}_j(O_{t+1}),1\le i\le N,1\le t\le T-1}$

که در آن

${\displaystyle {\beta }_t(i)=1,1\le i\le N}$

می‌توان ثابت کرد که

${\displaystyle a_t(i){\beta }_t(i)=p\{O,q_t=i|\lambda \},1\le i\le N,1\le t\le T}$

آنگاه می‌توان با کمک هر دو روش پیشرو و پسرو مقدار احتمال ${\displaystyle P(O|\lambda )}$

${\displaystyle p\{O|\lambda \}=\sum _{i=1}^{N}p\{O,q_t=i|\lambda \}=\sum _{i=1}^N{a}_t(i){\beta }_t(i)}$

در این حالت می‌خواهیم با داشتن دنباله مشاهدات ${\displaystyle O=\{O_1,...,O_t\}}$

یک راه حل این است که محتمل‌ترین حالت در لحظه t را به‌دست آوریم و تمام حالات را به این شکل برای دنبالهٔ ورودی به‌دست آوریم. اما برخی مواقع این روش به ما یک دنبالهٔ معتبر و بامعنا از حالات را نمی‌دهد. به همین دلیل، باید راهی پیدا کرد که یک چنین مشکلی نداشته باشد.

در یکی از این روش‌ها که با نام الگوریتم Viterbi شناخته می‌شود، دنباله حالات کامل با بیشترین مقدار نسبت شباهت پیدا می‌شود. در این روش برای ساده کردن محاسبات متغیر کمکی زیر را تعریف می‌نماییم.

${\displaystyle {\delta }_t(i)=maxp\{q_1,q_2,...,q_{t-1},q_t=t,o_1,o_2,...,o_{t-1}|\lambda \}}$

که در شرایطی که حالت فعلی برابر با i باشد، بیشترین مقدار احتمال برای دنباله حالات و دنباله مشاهدات در زمان t را می‌دهد. به همین ترتیب می‌توان روابط بازگشتی زیر را نیز به‌دست‌آورد.

${\displaystyle {\delta }_{t+1}(j)=b_j(o_{t+1})[max{\delta }_t(i)a_{ij}],1\le i\le N,1\le t\le T-1}$

که در آن

${\displaystyle {\delta }_1(j)={\pi }_j{b}_j(o_1),1\le i\le N}$

به همین دلیل روال پیدا کردن دنباله حالات با بیشترین احتمال از محاسبهٔ مقدار ${\displaystyle {\delta }_j(i),i\le j\le N}$

${\displaystyle j^{\ast }=argmax{\delta }_T(i),}$

و با شروع از حالت ${\displaystyle j^{\ast }}$

به‌طور کلی مسئله یادگیری به این موضوع می‌پردازد که چگونه می‌توان پارامترهای مدل HMM را تخمین زد تا مجموعه داده‌های آموزشی به بهترین نحو به کمک مدل HMM برای یک کاربرد مشخص بازنمایی شوند. به همین دلیل می‌توان نتیجه گرفت که میزان بهینه بودن مدل HMM برای کاربردهای مختلف، متفاوت است. به بیان دیگر می‌توان از چندین معیار بهینه‌سازی متفاوت استفاده نمود، که از این بین یکی برای کاربرد مورد نظر مناسب تر است. دو معیار بهینه‌سازی مختلف برای آموزش مدل HMM وجود دارد که شامل معیار بیشترین شباهت (ML) و معیار ماکزیمم اطلاعات متقابل (Maximum Mutual Information (MMI)) می‌باشند. آموزش به کمک هر یک از این معیارها در ادامه توضیح داده شده‌است.

معیار بیشترین شباهت((Maximum Likelihood (ML)

در معیار ML ما سعی داریم که احتمال یک دنباله ورودی ${\displaystyle O^w}$

${\displaystyle L_{tot}=p\{O^w|{\lambda }_w\}}$

با توجه به رابطه فوق در حالت کلی معیار ML به صورت زیر تعریف می‌شود.

${\displaystyle L_{tot}=p\{O|\lambda \}}$

اگر چه هیچ راه حل تحلیلی مناسبی برای مدل ${\displaystyle \lambda =\{A,B,\pi \}}$

الگوریتم بام- ولش

این روش را می‌توان به سادگی و با محاسبه احتمال رخداد پارامترها یا با محاسبه حداکثر رابطه زیر بر روی ${\displaystyle \overline{\lambda }}$

${\displaystyle Q(\lambda ,\overline{\lambda })=\sum _{q}p\{q|O,\lambda \}log[p\{O,q,\overline{\lambda }\}]}$

یکی از ویژگی‌های مخصوص این الگوریتم این است که همگرایی در آن تضمین شده‌است. برای توصیف این الگوریتم که به الگوریتم پیشرو- پسرو نیز معروف است، باید علاوه بر متغیرهای کمکی پیشرو و پسرو که قبلاً تعریف شده‌اند، متغیرهای کمکی بیشتری تعریف شود. البته می‌توان این متغیرها را در قالب متغیرهای پیشرو و پسرو نیز تعریف نمود.

اولین متغیر از این دست احتمال بودن در حالت i در زمان t و در حالت j در زمان t+1 است، که به صورت زیر تعریف می‌شود.

${\displaystyle {\xi }_t(i,j)=p\{qt=i,q_{t+1}=j|O,\lambda \}}$

این تعریف با تعریف زیر معادل است.

${\displaystyle {\xi }_t(i,j)=\frac{p\{q_t=i,q_{t+1}=j,O|\lambda \}}{p\{O|\lambda \}}}$

می‌توان این متغیر را با استفاده از متغیرهای پیشرو و پسرو به صورت زیر تعریف نمود.

${\displaystyle {\xi }_t(i,j)=\frac{{\alpha }_t(i)a_{ij}{\beta }_{t+1}(j)b_j(o_{t+1})}{\sum _{i=1}^N\sum _{j=1}^N{\alpha }_t(i)a_{ij}{\beta }_{t+1}(j)b_j(o_{t+1})}}$

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

${\displaystyle {\gamma }_t(i)=p\{q_t=i|O,\lambda \}}$

این متغیر را نیز می‌توان در قالب متغیرهای پیشرو و پسرو تعریف نمود.

${\displaystyle {\gamma }_t(i)=\left[\frac{{\alpha }_t(i){\beta }_t(i)}{\sum _{i=1}^N{\alpha }_t(i){\beta }_t(i)}\right]}$

رابطه بین دو متغیر فوق به صورت زیر بیان می‌شود.

${\displaystyle {\gamma }_t(i)=\sum _{i=1}^N{\xi }_t(i,j),1\le i\le N,1\le t\le M}$

اکنون می‌توان الگوریتم آموزش بام – ولش را با ماکزیمم کردن مقدار به‌دست‌آورد. اگر مدل اولیهٔ ما باشد، می‌توانیم متغیرهای پسرو و پیشرو و متغیرهای ${\displaystyle \xi }$

${\displaystyle {\overline{\pi }}_i={\gamma }_1(i),1\le i\le N}$

${\displaystyle {\overline{a}}_{ij}=\frac{\sum _{t=1}^{T-1}{\xi }_t(i,j)}{\sum _{t=1}^{T-1}{\gamma }_t(i)},1\le i\le N,1\le j\le N}$

${\displaystyle {\overline{b}}_j(k)=\frac{\sum _{t=1}^T{\gamma }_t(j)}{\sum _{t=1}^T{\gamma }_t(j)},1\le j\le N,1\le k\le M}$

فرمول‌های بازتخمین را می‌توان به‌راحتی به شکلی تغییر داد که با توابع چگالی پیوسته نیز قابل استفاده باشند.

الگوریتم حداکثرسازی امید ریاضی (Expectation Maximization)

الگوریتم حداکثرسازی امید ریاضی یا EM به عنوان یک نمونه از الگوریتم بام – ولش در آموزش مدل‌های HMM مورد استفاده قرار می‌گیرد. الگوریتم EM دارای دو فاز تحت عنوان Expectation و Maximization است. مراحل آموزش مدل در الگوریتم EM به صورت زیر است.

1. مرحله مقدار دهی اولیه: پارامترهای اولیه مدل ${\displaystyle \lambda }$
   را تعیین می‌نماییم.
2. مرحله امید ریاضی(Expectation): برای مدل ${\displaystyle \lambda }$
   موارد زیر را محاسبه می‌کنیم.

• ${\displaystyle \alpha }$
  مقادیر با استفاده از الگوریتم پیشرو
• مقادیر ${\displaystyle \beta }$
  و ${\displaystyle \gamma }$
  با استفاده از الگوریتم پسرو

1. مرحله ماکزیمم‌سازی (Maximization): مدل ${\displaystyle \lambda }$
   را با استفاده از الگوریتم باز تخمین محاسبه می‌نماییم.
2. مرحله بروزرسانی ${\displaystyle \lambda \leftarrow \acute{\lambda }}$
3. بازگشت به مرحله امید ریاضی

روال فوق تا زمانی که میزان نسبت شباهت نسبت به مرحله قبل بهبود مناسبی داشته باشد ادامه می‌یابد.

روش مبتنی بر گرادیان

در روش مبتنی بر گرادیان هر پارامتر${\displaystyle \mathrm{\Theta }}$

${\displaystyle {\mathrm{\Theta }}^{new}={\mathrm{\Theta }}^{old}-\eta \left[\frac{\mathrm{\partial }j}{\mathrm{\partial }\mathrm{\Theta }}\right]}$

که در آن مقدار J با ید مینیمم شود. در این حالت خواهیم داشت.

${\displaystyle J=E_{ML}=-\log (PO|\lambda )=-\log L_{tot}}$

از آنجا که مینیمم کردن J معادل است با مینیمم کردن${\displaystyle L_{tot}}$

${\displaystyle L_{tot}=\sum _{i=1}^{N}p(O,q_t=i|\lambda )=\sum _{i=1}^N{\alpha }_t(i){\mathrm{B}}_t(i)}$

با مشتق گرفتن از رابطهٔ قبل به این نتیجه دست می‌یابیم:

${\displaystyle \left(\frac{\mathrm{\partial }J}{\mathrm{\partial }\mathrm{\Theta }}\right)=-\left(\frac{1}{L_{tot}}\right)\left(\frac{\mathrm{\partial }{L}_{tot}}{\mathrm{\partial }\mathrm{\Theta }}\right)}$

از آنجا که در رابطهٔ فوق مقدار ${\displaystyle \left(\frac{\mathrm{\partial }J}{\mathrm{\partial }\mathrm{\Theta }}\right)}$

در روش مبتنی بر گرادیان، مقدار ${\displaystyle \left(\frac{\mathrm{\partial }{L}_{tot}}{\mathrm{\partial }\mathrm{\Theta }}\right)}$

استفاده از مدل HMM در شناسایی گفتار

بحث شناسایی اتوماتیک گفتار را می‌توان از دو جنبه مورد بررسی قرار داد.

1. از جنبه تولید گفتار
2. از جنبه فهم و دریافت گفتار

مدل پنهان مارکوف (HMM) تلاشی است برای مدل‌سازی آماری دستگاه تولید گفتار و به همین دلیل به اولین دسته از روش‌های شناسایی گفتار تعلق دارد. در طول چندین سال گذشته این روش به عنوان موفقترین روش در شناسایی گفتار مورد استفاده قرار گرفته‌است. دلیل اصلی این مسئله این است که مدل HMM قادر است به شکل بسیار خوبی خصوصیات سیگنال گفتار را در یک قالب ریاضی قابل فهم تعریف نماید.

در یک سیستم ASR مبتنی بر HMM قبل از آموزش HMM یک مرحله استخراج ویژگی‌ها انجام می‌گردد. به این ترتیب ورودی HMM یک دنباله گسسته از پارامترهای برداری است. بردارهای ویژگی می‌تواند به یکی از دو طریق بردارهای چندی‌سازی شده یا مقادیر پیوسته به مدل HMM آموزش داده شوند. می‌توان مدل HMM را به گونه‌ای طراحی نمود که هر یک از این انواع ورودیها را دریافت نماید. مسئله مهم این است که مدل HMM چگونه با طبیعت تصادفی مقادیر بردار ویژگی سازگاری پیدا خواهد کرد.

استفاده از HMM در شناسایی کلمات جداگانه

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

آموزش

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

${\displaystyle O=(o_1,o_2,....,o_N)}$

پارامترهای اولیه تمام مدل‌های HMM را با یک مجموعه از مقادیر مشخص مقدار دهی می‌نماییم.

${\displaystyle {\lambda }_i,1\le i\le N}$

در آغاز این مسئله را برای حالت clamped در نظر بگیرید. از آنجایی که ما برای هر کلاس از واحدها یک HMM داریم، می‌توانیم مدل${\displaystyle {\lambda }_i}$

${\displaystyle L_{tot}^{clamped}=\sum _{i\in {\lambda }_i}{\alpha }_t(i){\mathrm{B}}_t(i)=\sum _{i\in {\lambda }_i}{\alpha }_T(i)}$

برای حالت free نیز به مانند حالت قبل می‌توان مقدار نسبت شباهت را به‌دست‌آورد. ${\displaystyle L_{tot}^{free}=\sum _{m=1}^N{L}_m^I=\sum _{m=1}^N[\sum _{i\in {\lambda }_m}{\alpha }_t(i){\mathrm{B}}_t(i)]\sum _{m=1}^N\sum _{i\in {\lambda }_i}{\alpha }_T(i)}$

که در آن ${\displaystyle L_m^I}$

شناسایی

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

${\displaystyle I^{\ast }\arg max{L}_m^I}$

${\displaystyle 1\le m\le N}$

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

مشارکت‌کنندگان ویکی‌پدیا. «Hidden Markov model». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۷ ژوئن ۲۰۱۱.