بسمه تعالي

دانشگاه صنعتي اميركبير (پلي تکنيک تهران)

دانشكده مهندسي كامپيوتر و فناوري اطلاعات

 

 

 

 

مدل مخفي مارکوف و الگوريتمهای آموزش

 

Hidden Markov Model and Training Algorithms

 

 

 

تهيه کننده:

محمد حسين معطر

moattar@ce.aut.ac.ir

 

 

 

 

 

 

ارديبهشت 1385

فهرست مطالب

1- مقدمه

2- فرآيند مارکوف گسسته

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

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

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

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

4- مدل مخفي مارکوف

5- يک مثال واقعي

6- سه مساله اصلي

7- انواع مدلهاي مخفي مارکوف و HMM پيوسته

8- مدل مخلوط گوسي

9- فرضيات تئوري مدل مخفي مارکوف

10- مساله ارزيابي و الگوريتم پيشرو (forward)

11- مساله کد گشايي و الگوريتم ويتربي (Viterbi Algorithm)

12- مساله يادگيري

12-1- معيار بيشترين شباهت(ML)

12-1-1- الگوريتم بام- ولش

12-1-2- الگوريتم حداکثر سازي اميد رياضي (Expectation Maximization)

12-1-3- روش مبتني بر گراديان

12-1-4- محاسبه گراديان برحسب پارامترهاي احتمال حالات

12-1-5- محاسبه گراديان برحسب پارامترهاي احتمال حالات

12-2- معيار ماکزيمم اطلاعات متقابل

12-2-1- محاسبه گراديان برحسب احتمالات انتقال

12-2-2- گراديان برحسب احتمالات مشاهدات

13- استفاده از مدل HMM در شناسايي گفتار

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

14-1- آموزش

14-2- شناسايي

15- استفاده از مدل HMM در شناسايي گفتار پيوسته

15-1- آموزش مدلهاي HMM براي کاربرد شناسايي گفتار پيوسته

15-1-1- آموزش ML

15-1-2- آموزش MMI

15-2- شناسايي با استفاده از شناسايي کننده گفتار پيوسته

15-2-1- شناسايي مبتني بر الگوريتم ويتربي

15-2-2- الگوريتم ساخت سطح Level Building

15-2-3- جستجوي N-best

16- برخي کاربردها

17- برخي مراجع مفيد در زمينه مدل مخفي مارکوف و ابزارهاي موجود

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1- مقدمه

يکي از مسائلي که در پردازش سيگنال توجهات را به خود معطوف نموده است، مدلسازي سيگنال است. انتخابهاي مختلفي براي مدل کردن سيگنال و خصوصيات آن وجود دارد. از يک ديدگاه مي توان مدلهاي سيگنال را به دو دسته مدلهاي معين[1] و مدلهاي آماري[2] تقسيم بندي نمود. مدلهاي معين عمدتا برخي خواص شناخته شده سيگنال را مورد استفاده قرار مي دهند. در اين حالت تشکيل مدل سيگنال سرراست است و تنها کافي ست مقادير پارامترهاي مدل تخمين زده شود. در مدلهاي آماري سعي در ايجاد مدل با استفاده از خواص آماري سيگنال است. مدلهاي گاوسي، زنجيره مارکوف و مدل مخفي مارکوف از جمله اين روشها هستند. فرض اساسي در مدلهاي آماري اين است که مي توان خواص سيگنال را به شکل يک فرآيند تصادفي پارامتري مدل نمود.

مدل مخفي مارکوف در اواخر دهه 1960 ميلادي معرفي گرديد و در حال حاضر به سرعت در حال گسترش دامنه کاربردها مي باشد. دو دليل مهم براي اين مساله وجود دارد. اول اينکه اين مدل از لحاظ ساختار رياضي بسيار قدرتمند است و به همين دليل مباني نظري بسياري از کاربردها را شکل داده است. دوم اينکه مدل مخفي مارکوف اگر به صورت مناسبي ايجاد شود مي تواند براي کاربردهاي بسياري مورد استفاده قرار گيرد.

[بازگشت به فهرست]

 


2- فرآيند مارکوف گسسته

يک سيستم مانند شکل زير را که در هر لحظه در يکي از حالت متمايز است در نظر بگيريد. در زمانهاي گسسته و با فواصل منظم، حالت سيستم با توجه به مجموعه اي از احتمالات تغيير مي کند. براي زمانهاي  حالت در لحظه t را با qt نشان مي دهيم. براي يک توصيف مناسب از سيستم فعلي نياز به دانستن حالت فعلي در کنار تمام حالات قبلي مي باشد. براي يک حالت خاص از زنجيره مارکوف مرتبه اول، توصيف احتمالاتي تنها با حالت فعلي و حالت قبلي مشخص مي شود.

شکل 1: يک زنجيره مارکوفي با 5 حالت [Rabiner 1989]

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

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

فرايند تصادفي فوق را مدل مارکوف قابل مشاهده[3] مي گويند زيرا خروجي مدل مجموعه اي از حالات است که قرار گرفتن در آنها متناظر با يک مشاهده مي باشد. ما مي توانيم دنباله مشاهدات مورد انتظار خود را توليد کنيم و احتمال وقوع آن در زنجيره مارکوف را محاسبه نماييم. براي مثال با داشتن دنباله مشاهدات احتمال وقوع آن به صورت زير بيان مي شود.

يکي ديگر از مواردي که مطرح مي شود اين است که اگر سيستم در حالت  باشد با چه احتمالي به حالت  مي رود و با چه احتمالي در همان حالت  باقي مي ماند.

[بازگشت به فهرست]

 


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

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

يک مدل مارکوف از مرتبه صفر هيچ حافظه اي ندارد و براي هر t و t' در دنباله سمبلها، pr(xt = Si) = pr(xt' = Si) خواهد بود.

مدل مارکوف از مرتبه صفر مانند يک توزيع احتمال چند جمله اي مي باشد. چگونگي تخمين پارامترهاي مدل مارکوف مرتبه صفر و همچنين پيچيدگي مدل در ]1968[ Wallace and Boulton  آماده است.

[بازگشت به فهرست]

 

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

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

pr(xt=Si | xt-1=Sj), for i = 1..k & j = 1..k

تعريف فوق مانند اين است که k مدل مارکوف در مرتبه صفر براي هر Sj داشته باشيم.

[بازگشت به فهرست]

 

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

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

 

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

pr(H)=0.6, pr(T)=0.4

 

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

1) فرض کنيد سکه X يکي از سکه هاي A و يا B باشد.

2) مراحل زير را تکرار مي کنيم.

(a سکه X را پرتاب مي کنيم و نتيجه را مي نويسيم.

 (bسکه C را نيز پرتاب مي کنيم.

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

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

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

شکل 3: مدل مخفي مارکوف براي پرتاب سکه طبق راول فوق

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

[بازگشت به فهرست]

 


4- مدل مخفي مارکوف (HMM)

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

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

*       تعداد حالات ممکن: تعداد حالتها در موفقيت مدل نقش به سزايي دارد و در يک مدل مخفي مارکوف هر حالت با يک رويداد متناظر است. براي اتصال حالتها روشهاي متفاوتي وجود دارد که در عمومي ترين شکل تمام حالتها به يکديگر متصل مي شوند و از يکديگر قابل دسترسي مي باشند (مدل ارگوديک[4]).

*       تعداد مشاهدات در هر حالت: تعداد مشاهدات برابر است با تعداد خروجيهايي که سيستم مدل شده خواهد داشت.

*      تعداد حالتهاي مدل N

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

tex2html_wrap_inline2612

*      ماتريس انتقال حالت : يک مجموعه از احتمالات انتقال در بين حالتها

که در آن  بيانگر حالت فعلي مي باشد. احتمالات انتقال بايد محدوديتها طبيعي يک توزيع احتمال تصادفي را برآورده نمايند. اين محدوديتها شامل موارد زير مي گردند.

براي حالات مدل ارگوديک براي تمام  و ها مقدار بزرگتر از صفر است و در موردي که اتصالي بين حالات وجود ندارد .

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

tex2html_wrap_inline2622.

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

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

که در آن به ترتيب ضريب وزندهي، بردار ميانگين و ماتريس کواريانس مي باشند. در رابطه فوق مقادير بايد شرايط زير را ارضا نمايند:

*      توزيع احتمال حالت آغازين  که در آن

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

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

[بازگشت به فهرست]

 


5- يک مثال واقعي

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

شما قبول داريد که هوا مانند يک زنجيره مارکوف ( Markov chain) گسسته عمل مي کند. دو وضعيت ممکن است وجود داشته باشد: هوا باراني(rainy)  باشد و يا هوا آفتابي(sunny)  باشد. اما شما نمي توانيد آنها را مستقيما مشاهده کنيد زيرا آنها از شما مخفي هستند. هر روز اين شانس وجود دارد که دوست شما يکي از عمليت “walk”، “shop” و يا “clean” را با توجه به وضعيت هوا انجام دهد. دوست شما در مورد فعاليتي که انجام مي دهد به شما توضيحاتي مي دهد که به آنها مشاهدات مي گوييم. اينگونه سيستمها را مدل مخفي مارکوف مي گويند.  

شما وضعيت کلي هوا و اينکه دوستتان تمايل دارد چه کاري را انجام دهد مي دانيد. به بيان ديگر پارامترهاي مدل HMM مشخص است. مي توان مدل 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 چگونگي تغييرات آب و هوا را در زنجيره مارکوف مشخص مي نمايد. در مدل بالا تنها 30 درصد شانس وجود دارد که اگر هواي امروز باراني است هواي فردا آفتابي باشد. مقدار emission_probability تعيين مي کند که دوست شما به چه ميزان علاقه مند به انجام يک فعاليت خاص در يک روز است. اگر هوا باراني باشد 50 درصد شانس وجود دارد که او آپارتمان خود را تميز کند و اگر آفتابي باشد، به احتمال 60 درصد دوست شما براي پياده روي از منزل خارج مي شود.

[بازگشت به فهرست]

 


6- سه مساله اصلي

براي اينکه مدل HMM در دنياي واقعي قابل استفاده باشد بايد سه مساله مهم حل شود. اين سه مساله به قرار زيرند:

1- مساله ارزيابي(Evaluation Problem)

با داشتن دنباله مشاهدات  و مدل  چگونه، احتمال توليد دنباله مشاهدات توسط را محاسبه نماييم؟

2- مساله کدگشايي (Decoding problem)

با داشتن دنباله مشاهدات و مدل  چگونه دنباله حالات بهينه  براي توليدرا بدست آوريم؟

3- مساله آموزش (Learning problem)

چگونه پارامترهاي مدل،، را بدست آوريم؟

در کاربردي مانند شناسايي گفتار، مساله ارزيابي براي شناسايي کلمات جدا (isolated word recognition) استفاده مي شود. مساله کدگشايي با کاربردهايي مانند شناسايي گفتار پيوسته و تقطيع سر و کار دارد. مساله آموزش نيز براي اينکه ما بتوانيم مدل HMM را در کاربردهاي مختلف شناسايي استفاده نماييم، بايد حل شود.

براي حل مسأله اول روالهاي پيشرو و پسرو[5] پيشنهاد شده‌اند. در اين روش تمام دنباله حالتهاي با طول t در نظر گرفته مي شود. براي مثال احتمال توليد دنباله مشاهدات از دنباله حالات از مدل  به صورت زير محاسبه مي شود.

که مي توان آن را به شکل زير نيز نوشت:

احتمال وقوع دنباله حالتهاي نيز به شکل زير محاسبه مي شود:

حال احتمال اينکه هر دو رويداد  و همزمان رخ دهد را با  نشان مي دهيم:

در اينجا احتمال وقوعبا جمع احتمال براي تمام دنباله حالات ممکن بدست مي آيد.

 مسأله دوم که بدست آوردن رشته حالات بهينه است توسط الگوريتم جستجوي ويتربي[6] انجام مي‌شود و در فاز بازشناسي بكار مي‌آيد و مسأله سوم نيز مسأله تخمين بهينة پارامترهاي مدل يا همان مسأله آموزش مدل ماركف مي‌باشد و به يكي از دو روش ويتربي و يا بام- ولش[7] انجام مي‌گردد. البته آموزش مدل مي‌تواند تركيبي از اين دو روش نيز باشد. در عمل و در فاز پياده‌سازي، روشهايي براي حل مسائلي چون ناكافي بودن داده‌هاي آموزشي، مقدار دهي اوليه مدل براي شروع آموزش و كم كردن خطاي محاسباتي پيشنهاد شده است، كه بايد در پياده‌سازي عملي يك سيستم مبتني بر مدل ماركف لحاظ شوند. بررسي دقيق موارد فوق نياز به فرصت جداگانه دارد به همين دليل تا اين اندازه اکتفا مي شود. براي بررسي راه حلهاي ارائه شده براي مسائل فوق مي توانيد به [Rabiner 1989] مراجعه نماييد.

[بازگشت به فهرست]

 


7- انواع مدلهاي مخفي مارکوف و HMM پيوسته

همانطور که گفته شد نوع خاصي از HMM وجود دارد که در آن تمام حالات موجود با يکديگر متصل هستند. ليکن مدل مخفي مارکوف از لحاظ ساختار و اصطلاحا توپولوژي انواع مختلف دارد. همانطور که گفته شد براي مدل ارگوديک براي تمام و ها  است و ساختار مدل مثل يک گفتار کامل است که راسها در آن داراي اتصالات بازگشتي نيز مي باشند. ليکن براي کاربردهاي متفاوت و با توجه به پيچيدگي فرآيند نياز به ساختار متفاوتي وجود دارد. از جمله اين ساختارها که به شکل گسترده اي در کاربردهاي شناسايي گفتار مبتني بر واج و شناسايي گوينده مورد استفاده قرار مي گيرد، مدل چپ به راست[8] يا مدل بکيس[9] است. اين مدل که ساختار آن را در شکل 2 نيز مي بينيد، داراي اتصالات چپ به راست است و براي مدل کردن سيگنالهايي که خواص آنها با زمان تغيير مي کند مورد استفاده قرار ميگيرد. در مدل چپ به راست تنها يک حالت ورودي وجود دارد که همان حالت اول است و به اين ترتيب:

مدلهاي ارگوديک و چپ به راست مدلهاي HMM پايه هستند و در پردازش گفتار نيز بيشترين کاربرد را دارا مي باشند. هرچند مي توان با اتصال چندين مدل و يا تغيير در ساختار اتصالات آن مدلهايي با انعطاف پذيري بيشتري ايجاد نمود[Rabiner 1989]. شکل 2-ج يک نمونه از مدل موازي چپ به راست، که شامل دو مدل چپ به راست است، را نشان مي دهد.

شکل 2: سه ساختار براي مدل HMM (الف) مدل HMM ارگوديک

(ب) مدل چپ به راست (ج) مدل موازي چپ به راست [Rabiner 1989]

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

که در آن  ضريب مخلوط ام است و مي تواند هر تابع چگالي باشد. معمولا از تابع گاوسي براي اين منظور استفاده مي شود. ضرايب مخلوط فوق بايد محدوديتهاي زير را داشته باشند:

[بازگشت به فهرست]

 


8- مدل مخلوط گاوسي[10]

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

که در آن وزن مخلوط و به ترتيب بردار ميانگين و ماتريس کوواريانس توزيع نرمال هستند. ماتريس کوواريانس مدل GMM معمولاً به صورت قطري در نظر گرفته مي­شود، گرچه امکان استفاده از ماتريس کامل نيز وجود دارد. رابطه (15) را مي توان با استفاده از فرمول تابع چگالي احتمال نرمال به صورت زير نيز بيان نمود:

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

[بازگشت به فهرست]

 


9- فرضيات تئوري مدل مخفي مارکوف

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

1- فرض مارکوف

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

به بيان ديگر فرض مي شود که حالت بعدي تنها به حالت فعلي بستگي دارد. مدل حاصل  از فرض مارکوف يک مدل HMM مرتبه صفر مي باشد.

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

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

[بازگشت به فهرست]

2- فرض ايستايي(stationarity)

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

[بازگشت به فهرست]

2- فرض استقلال خروجي

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

آنگاه مطابق با اين فرض براي مدل HMM با نام خواهيم داشت:

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

[بازگشت به فهرست]

 


10- مساله ارزيابي و الگوريتم پيشرو (forward)

در اين حالت مساله اين است که با داشتن مدل  و دنباله مشاهدات  بايد مقدار  را پيدا نماييم. مي توانيم اين مقدار را با روشهاي آماري مبتني بر پارامترها محاسبه نماييم. البته اين کار به محاسباتي با پيچيدگي  احتياج دارد. اين تعداد محاسبات حتي براي مقادير متوسط t نيز بسيار بزرگ است. به همين دليل لازم است که راه ديگري براي اين محاسبات پيدا نماييم. خوشبختانه روشي ارائه شده است که پيچيدگي محاسباتي کمي دارد و از متغير کمکي  با نام متغير پيشرو استفاده مي کند.

متغير پيشرو به صورت يک احتمال از دنباله مشاهدات تعريف مي شود که در حالت i خاتمه مي يابد. به بيان رياضي:

آنگاه به سادگي مشاهده مي شود که رابطه بازگشتي زير برقرار است.

که در آن

 

شکل 4: احتمالات پيشرو

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

و آنگاه احتمال  به صورت زير محاسبه خواهد شد:

پيچيدگي محاسباتي روش فوق که به الگوريتم پيشرو معروف است برابر با  است، که در مقايسه با حالت محاسبه مستقيم که قبلا گفته شد، و داراي پيچيدگي نمايي بود، بسيار سريعتر است.

روشي مشابه روش فوق را مي توان با تعيين متغير پسرو، ، به عنوان احتمال جزئي دنباله مشاهدات  در حالت i تعريف نمود. متغير پيشرو را مي توان به شکل زير نمايش داد.

مانند روش پيشرو يک رابطه بازگشتي به شکل زير براي محاسبه  وجود دارد.

شکل 5: احتمالات پسرو

که در آن

مي توان ثابت کرد که

آنگاه مي توان با کمک هر دو روش پيشرو و پسرو مقدار احتمال  را محاسبه نمود. 

رابطه فوق بسيار مهم و مفيد است و بخصوص براي استخراج روابط آموزش مبتني بر گراديان لازم  مي باشد.

[بازگشت به فهرست]

 


11- مساله کد گشايي و الگوريتم ويتربي (Viterbi Algorithm)

در اين حالت مي خواهيم با داشتن دنباله مشاهدات  و مدل  دنباله حالات بهينه  براي توليدرا بدست آوريم.

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

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


 displaymath2770

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

که در آن

به همين دليل روال پيدا کردن دنباله حالات با بيشترين احتمال از محاسبه مقدار  و با کمک رابطه فوق شروع مي شود. در اين روش در هر زمان يک اشاره گر به حالت برنده قبلي خواهيم داشت. در نهايت حالت  را با داشتن شرط زير بدست مي آوريم.

و با شروع از حالت ، دنباله حالات به شکل بازگشت به عقب و با دنبال کردن اشاره گر به حالات قبلي بدست مي آيد. با استفاده از اين روش مي توان مجموعه حالات مورد نظر را بدست آورد. اين الگوريتم را مي توان به صورت يک جستجو در گراف که نودهاي آن برابر با حالتها مدل HMM در هر لحظه از زمان مي باشند نيز تفسير نمود.

[بازگشت به فهرست]

 


12- مساله يادگيري

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

[بازگشت به فهرست]

 

12-1- معيار بيشترين شباهت(Maximum Likelihood (ML))

در معيار ML ما سعي داريم که احتمال يک دنباله ورودي  که به کلاس w تعلق دارد را با داشتن مدل HMM همان کلاس بدست آوريم. اين ميزان احتمال برابر با نسبت شباهت کلي دنباله مشاهدات است و به صورت زير محاسبه مي شود.

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

اگر چه هيچ راه حل تحليلي مناسبي براي مدل  وجود ندارد که مقدار  را ماکزيمم نمايد، ليکن مي توانيم با استفاده از يک روال بازگشتي پارامترهاي مدل را به شکلي انتخاب کنيم که مقدار ماکزيمم بدست آيد. روش Baum-Welch و يا روش مبتني بر گراديان از جمله اين روشها هستند.

[بازگشت به فهرست]

 

12-1-1- الگوريتم بام- ولش

اين روش را مي توان به سادگي و با محاسبه احتمال رخداد پارامترها و يا با محاسبه حداکثر رابطه زير بر روي tex2html_wrap_inline2812 تعريف نمود.

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

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

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

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

شکل 6: بازتخمين احتمالات انتقال

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

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

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

اکنون مي توان الگوريتم آموزش بام – ولش را با ماکزيمم کردن مقدار بدست آورد. اگر مدل اوليه ما  باشد، مي توانيم متغيرهاي پسرو و پيشرو را به استفاده از روابط (18) و (21) و متغيرهاي  و را با استفاده از روابط (28) و (29) تعريف نمود. مرحله بعدي اين است که پارامترهاي مدل را با توجه به روابط بازتخمين زير بروزرساني نماييم.

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

[بازگشت به فهرست]

 

12-1-2- الگوريتم حداکثر سازي اميد رياضي (Expectation Maximization)

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

1) مرحله مقدار دهي اوليه: پارامترهاي اوليه مدل  را تعيين مي نماييم.

2) مرحله اميد رياضي(Expectation) : براي مدل  موارد زير را محاسبه مي کنيم.

*      مقادير  با استفاده از الگوريتم پيشرو

*      مقادير و  با استفاده از الگوريتم پسرو

3) مرحله ماکزيمم سازي (Maximization): مدل  را با استفاده از الگوريتم باز تخمين محاسبه مي نماييم.

4) مرحله بروز رساني

5) بازگشت به مرحله اميد رياضي

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

[بازگشت به فهرست]

 

12-1-3- روش مبتني بر گراديان

در روش مبتني بر گراديان هر پارامتر  از مدل  با توجه به رابطه زير تغيير داده مي شود.

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

از آنجا که مينيمم کردن J معادل است با مينيمم کردن ، نياز است است تا معيار ML بهينه بدست آيد. آنگاه مساله، يافتن مقدار مشتق  براي تمام پارامترهاي از مدل است. اين کار را مي توان به سادگي با استفاده از مقدار  انجام داد. به عنوان که گام کليدي، با استفاده از روابطه (23) و (25) خواهيم داشت.

با مشتق گرفتن از رابطه (36) بر حسب پارامتر  خواهيم داشت.

از آنجا که در رابطه فوق مقدار بر حسب  بدست مي آيد، مي توان  را به کمک رابطه (37) بدست آورد. در روش مبتني بر گراديان، مقدار  را بايد براي پارامترهاي  (احتمال انتقال) و  (احتمال مشاهدات) بدست آورد.

[بازگشت به فهرست]

 

12-1-4- محاسبه گراديان برحسب پارامترهاي احتمال حالات

با استفاده از قانون زنجيره اي داريم:

با مشتقگيري از رابطه (37) بر حسب  خواهيم داشت:

همچنين با مشتقگيري از رابطه (18) برحسب  داريم:

روابط (39)، (40) و (41) مقدار  را نتيجه مي دهيم و با جايگزيني آن در رابطه (38) ما به نتيجه مورد نظر دست مي يابيم.

[بازگشت به فهرست]

 

 12-1-5- محاسبه گراديان برحسب پارامترهاي احتمال حالات

با استفاده از قانون زنجيره اي داريم:

با مشتقگيري از رابطه (18) بر حسب  خواهيم داشت:

آنگاه مي توان با استفاده از روابط (44)، (40) و (43) مقدار  را بدست آورد.

رابطه فوق را مي توان به صورت زير نيز بيان نمود.

در نهايت مي توان مقدار احتمال مورد نظر را با جايگزيني  در رابطه (38) بدست آورد. اگر براي احتمال مشاهدات توابع چگالي پيوسته مورد استفاده قرار گرفته باشند، مي توان مقادير  را براي پارامترهاي اين توابع چگالي بدست آورد.

[بازگشت به فهرست]

 

12-2- معيار ماکزيمم اطلاعات متقابل

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

در مقابل معيار يادگيري MMI در هر لحظه تمام مدلهاي مربوط به کلاسها را مورد آموزش قرار مي دهد. در اين حالت پارامترهاي مدل اصلي براي بازنمايي مناسب داده ها بروز رساني مي شوند در حالي که پارامترهاي ساير مدلها به شکلي تغيير مي کنند که به ميزان کمتري نمونه هاي آموزشي را بازنمايي نمايند. اين روال باعث مي شود که تمايز بين مدلها افزايش يابد و به همين دليل است که روش يادگيري  MMI به گروه روشهاي يادگيري تمايزي تعلق دارد. حال فرض کنيد که يک مجموعه از مدلهاي HMM را در اختيار داريم:

مساله اين است که عدم قطعيت شرطي کلاس  را با داشتن دنباله مشاهدات حداقل نماييم. اين مساله معادل است با کم کردن اطلاعات شرطي کلاس بر حسب  و به صورت زير بيان مي شود:

در چهارچوب تئوري اطلاعات مساله فوق مانند حداقل کردن آنتروپي شرطي است.

که در آن  بيانگر مجموعه تمام کلاسها است و دنباله مشاهدات را نشان مي دهد. آنگاه اطلاعات متقابل بين کلاسها و دنباله مشاهدات

بايد حداکثر شود،  ثابت است. به همين دليل است که اين روش را روش حداکثر سازي اطلاعات متقابل گويند. اين روش با نام حداکثر سازي احتمال پسين يا (MAP) نيز شناخته مي شود زيرا در رابطه (47) مقدار احتمال بايد حداکثر شود. رابطه (47) را مي توان به کمک تئوري بيز به شکل زير نيز بيان نمود.

که در آن w يکي از کلاسهاي آموزشي را نشان مي دهد. رابطه (50) را مي توان به کمک روابط زير نيز بيان نمود. 

در اين حالت مي توان مقدار  را با استفاده از روش مبتني بر  گراديان يا روش بازتخمين ML حداقل نمود. براي مثال روش مبتني بر گراديان را مي توان به صورت زير تعريف نمود. اين روش با تلاش براي مينيمم کردن رابطه زير شروع مي شود.

آنگاه مي توان مساله فوق را به صورت مساله محاسبه  که در آن  يکي از پارامترهاي مدلهاي  است، ساده نمود.

تکنيک مشابهي مانند آنچه در يادگيري ML استفاده شد مي تواند در اينجا نيز مورد استفاده قرار گيرد. در قدم اول رابطه هاي (52) و (53) را با کمک متغيرهاي پيشرو و پسرو به صورت زير و با کمک رابطه (23) مي نويسيم.

آنگاه مقدار گراديان مورد نظر از تفاضل دو مشتق (55) و (56) حاصل مي شود. مانند روش ML اين محاسبات را بايد براي بدست آوردن هر دو پارامتر احتمال انتقالات و احتمال مشاهدات انجام داد.

[بازگشت به فهرست]

 

12-2-1- محاسبه گراديان برحسب احتمالات انتقال

با استفاده از قانون زنجيره اي داريم:

با مشتقگيري از روابط (55) و (56) بر حسب  و استفاده از نتايج رابطه (41) مي توانيم سمت راست رابطه (57) را بدست آوريم. اين جايگزيني دو نتيجه جداگانه را براي حالتهاي clamped و free خواهد داشت.

در رابطه فوق مقدار دلتاي کرونيکر(Kronecker) است.

با جايگزيني روايط (58) و (59) در رابطه (54)، با توجه به اينکه  ، خواهيم داشت:

[بازگشت به فهرست]

 

12-2-2- گراديان برحسب احتمالات مشاهدات

با استفاده از قانون زنجيره اي داريم:

با مشتقگيري از روابط (55) و (56) بر حسب  و استفاده از نتايج رابطه (44) مي توانيم سمت راست رابطه (61) را بدست آوريم. اين جايگزيني دو نتيجه جداگانه را براي حالتهاي clamped و free خواهد داشت.

در رابطه فوق مقدار دلتاي کرونيکر(Kronecker) است.

با جايگزيني روابط (62) و (63) در رابطه (54)، خواهيم داشت:

روابطه فوق را مي توان به شکل خوش فرم زير نيز تبديل نمود:

با استفاده از تعاريف فوق مي توان رابطه (64) را بصورت زير نيز بيان نمود.

رابطه زير به صورت کامل چگونگي بروز رساني احتمال مشاهدات را نشان مي دهد. اگر به جاي توابع چگالي احتمال گسسته، توابع چگالي احتمال پيوسته مورد استفاده قرار گيرند، مي توان با استفاده از قانون زنجيره اي اين مشتقها را در مدل HMM منتشر نمود. 

[بازگشت به فهرست]

 


13- استفاده از مدل HMM در شناسايي گفتار

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

1-           از جنبه توليد گفتار

2-           از جنبه فهم و دريافت گفتار

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

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

[بازگشت به فهرست]

 


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

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

براي اين کاربرد راه حلهاي مختلفي وجود دارد زيرا معيارهاي بهينه سازي متفاوتي را براي اين منظور معرفي شده است و الگوريتمهاي پياده سازي شده مختلفي نيز براي هر معيار موجود است. از بين اين روشها روش مبتني بر گراديان و معيار بهينه سازي MMI به شکل مختصر توضيح داده شده اند. اين مساله را از دو جنبه آموزش و شناسايي مورد بررسي قرار مي دهيم.

[بازگشت به فهرست]

 

14-1- آموزش

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

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

اين پارامترها را مي توان با استفاده از رابطه (35) و در حالي که گراديان مورد نظر از روابط (60) و (64) بدست مي آيند، بروز رساني نمود. البته براي اين کاربرد خاص (شناسايي جداگانه) مقادير نسبت شباهت در دو رابطه آخر به شکل خاصي محاسبه مي شوند.

در آغاز اين مساله را براي حالت clamped  در نظر بگيريد. از آنجايي که ما براي هر کلاس از واحدها يک HMM داريم، مي توانيم مدل از کلاس l را که دنباله مشاهدات فعلي به آن مربوط مي شود، را انتخاب نماييم. آنگاه با کمک رابطه (55) خواهيم داشت.

که در رابطه فوق، خط دوم از رابطه (19) نتيجه شده است. براي حالت free نيز به مانند حالت قبل مي توان مقدار نسبت شباهت را به کمک رابطه (55) بدست آورد.

که در آن  بيانگر ميزان شباهت دنباله مشاهدات فعلي به کلاس l در مدل  است. با کمک مقادير نسبت شباهت (68) و (69) مقدار گراديان به شکل زير خواهد بود.

با توجه به موارد فوق، روال آموزش با استفاده از روش مبتني بر گراديان و معيار MMI را مي توان به شکل زير خلاصه نمود.

1) هر يک از مدلهاي HMM، ، را با يکي از دو روش تصادفي يا خوشه بندي K-means مقداردهي اوليه مي کنيم.

2) با داشتن دنباله مشاهدات

*      مقادير احتمال پيشرو و پسرو هر HMM را با استفاده از روابط (21) و (18) محاسبه مي کنيم.

*      مقدار نسبت شباهت را با استفاده از روابط (68)  و (69) محاسبه مي کنيم.

*      بااستفاده از روابط (70) و (71) مقدار گراديان را بر حسب پارامترهاي هر مدل محاسبه مي نماييم.

*      با کمک رابطه (35) پارامترهاي مدل را بروز رساني مي کنيم.

3)اگر همه نمونه هاي آموزشي استفاده نشده اند به گام 2 بر مي گرديم.

4) مراحل 2 و 3 را تا رسيدن به شرط همگرايي ادامه مي دهيم.

اين مراحل را مي توان به سادگي براي مدلهاي HMM داراي چگالي پيوسته نيز تغيير داد. اين کار با انتشار گراديان با استفاده از قانون زنجيره اي انجام مي شود.

[بازگشت به فهرست]

 

14-2- شناسايي

در مقايسه با آموزش، روال شناسايي بسيار ساده تر است.

1) الگوريتم دنباله مشاهدات مورد نظر را دريافت مي کند.

*      مقادير احتمالات پيشرو و پسرو را براي هر يک از مدلها و با استفاده از روابط (21) و (18) محاسبه مي کنيم.

*      با استفاده از رابطه (69) مقدار احتمال را براي تمام مدلها محاسبه مي کنيم.

*      سپس کلاس دنباله مشاهدات ورودي با استفاده از رابطه زير تعيين مي شود.

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

[بازگشت به فهرست]

 


15- استفاده از مدل HMM در شناسايي گفتار پيوسته

در حالت شناسايي کلمات جداگانه ما براي هر واحد از يک HMM استفاده نموديم. در حالت شناسايي گفتار پيوسته اين کار قابل انجام نيست زيرا در اين حالت بايد مجوعه اي جملات پيوسته شناسايي شوند که اگر مدلها بر حسب جملات باشد با تعداد بسيار زيادي مدل احتياج داريم. علاوه بر اين دو مشکل اساسي ديگر نيز وجود دارد.

1)                  ما از نقطه پاياني واحدهاي گفتاري در هر جمله اطلاعي نداريم.

2)                  نمي دانيم که چه تعداد واحد گفتاري در هر جمله وجود دارد.

به دليل همين دو مشکل شناسايي گفتار پيوسته از شناسايي واحدهاي گفتاري جداگانه پيچيده تر است. البته HMM شرايط مناسبي را براي شناسايي گفتار پيوسته بوجود مي آورد. در اين حالت ما مدلهاي HMM هر واحد گفتاري را به هم متصل مي کنيم تا مدل HMM يک جمله را تشکيل دهد. اگر اتصال مدلهاي HMM به هم و ترتيب آنها از هيچ محدوديتي برخوردار نباشد، اصطلاحا گفته مي شود که شناسايي مستقل از گرامر (Grammar free) انجام مي شود. در مقابل مي توان تواليهاي معتبر مدلها را به کمک يک مدل زباني که گرامر زبان را تعيين مي کند، مشخص نمود. در اين حالت نيز به مانند شناسايي واحدهاي گفتاري چگونگي انجام دو مرحله آموزش و آزمايش بايد تعيين گردد.

[بازگشت به فهرست]

 

15-1- آموزش مدلهاي HMM براي کاربرد شناسايي گفتار پيوسته

مي توان يک شناسايي کننده گفتار پيوسته را به هر يک از روشهاي ML و يا MMI آموزش داد.

15-1-1- آموزش ML

اگر از تکنيک مبتني بر گراديان استفاده نماييم روال آموزش به صورت زير خواهد بود.

1) هر يک از مدلهاي HMM، ، را با يکي از دو روش تصادفي يا خوشه بندي K-means مقداردهي اوليه مي کنيم.

2) دنباله مشاهدات ورودي را براي هر جمله آموزشي دريافت مي کنيم.

*      مدل متناظر با جمله ورودي را با استفاده از مدل HMM واحدهاي گفتاري جمله ورودي تشکيل مي دهيم.

*      مقادير احتمال پيشرو و پسرو هر HMM را با استفاده از روابط (21) و (18) محاسبه مي کنيم.

*      مقدار نسبت شباهت را با استفاده از رابطه (37)  براي مدل جمله آموزشي محاسبه مي کنيم.

*      بااستفاده از روابط (42) و (45) مقدار گراديان را بر حسب پارامترهاي مدل محاسبه مي نماييم.

*      با کمک رابطه (35) پارامترهاي مدل را بروز رساني مي کنيم.

3)اگر همه نمونه هاي آموزشي استفاده نشده اند به گام 2 بر مي گرديم.

4) مراحل 2 و 3 را تا رسيدن به شرط همگرايي ادامه مي دهيم.

[بازگشت به فهرست]

 

15-1-2- آموزش MMI

براي آموزش بر حسب معيار MMI به فرمهاي مناسب روابط (55) و (56) نياز داريم. در آغاز حالت clamped را در نظر بگيريد. از آنجا که ما شناسايي را در سطح جمله انجام مي دهيم، يک مدل  HMM مانند  را با اتصال مدلهاي HMM واحدهاي گفتاري تشکيل مي دهيم که با دنباله آموزشي ورودي متناظر است. آنگاه با داشتن رابطه (55) خواهيم داشت.

خط دوم رابطه فوق از رابطه (19) نتيجه شده است.

در حالت free ، ما تنها يک مدل HMM مانند tex2html_wrap_inline2942 داريم که تمام زبان را بازنمايي مي نمايد. آنگاه رابطه (56) به صورت زير تغيير مي کند. 

با توجه به روابط فوق روال آموزش MMI به صورت زير خواهد بود:

1) هر يک از مدلهاي HMM، ، را با يکي از دو روش تصادفي يا خوشه بندي K-means مقداردهي اوليه مي کنيم.

2) دنباله مشاهدات ورودي را براي هر جمله آموزشي دريافت مي کنيم.

*      مدل متناظر با جمله ورودي را با استفاده از مدل HMM واحدهاي گفتاري جمله ورودي تشکيل مي دهيم.

*      مقادير احتمال پيشرو و پسرو هر HMM را با استفاده از روابط (21) و (18) محاسبه مي کنيم.

*      مقدار نسبت شباهت دنباله مشاهدات به مدل  را با استفاده از روابط (72) و (73) براي مدل جمله آموزشي محاسبه مي کنيم.

*      بااستفاده از روابط (64) و (60) مقدار گراديان را بر حسب پارامترهاي مدل براي مدلهاي واحدهاي گفتاري محاسبه مي نماييم. مقدار  در روابط فوق با مقدار زير جايگزين مي شود.

*      با کمک رابطه (35) پارامترهاي مدل را بروز رساني مي کنيم.

3)اگر همه نمونه هاي آموزشي استفاده نشده اند به گام 2 بر مي گرديم.

4) مراحل 2 و 3 را تا رسيدن به شرط همگرايي ادامه مي دهيم.

[بازگشت به فهرست]

 

15-2- شناسايي با استفاده از شناسايي کننده گفتار پيوسته

با فرض اينکه مدل تمام واحدهاي گفتار موجود باشند، عمل شناسايي گفتار پيوسته به معناي يافتن دنباله واحدهاي گفتاري است که با دنباله مشاهدات براي يک جمله نا مشخص مطابق است.  اين مساله را مي توان به صورت زير نيز بيان نمود:

که در آن يک دنباله از واحدهاي گفتاري با طول  است. از آنجا که  توسط مدل زباني تعيين مي شود تنها کاري که بايد براي تعيين   انجام گيرد، محاسبه  براي تمام انتخابهاي ممکن  است. واضح است که اين روال از لحاظ محاسباتي بسيار پيچيده است، زيرا حتي براي يک مجموعه کوچک از کلمات زبان تعداد جملات بسيار زياد خواهد بود. يک راه حل ساده تر اين است که بهترين دنباله حالات را در مدل زباني بدست آوريم. براي اين کار کافي ست رابطه زير را محاسبه کنيم.

سپس مي توان از طريق دنباله حالات دنباله واحدهاي گفتاري را بدست آورد. براي محاسبه مي توان مستقيما از الگوريتم ويتربي استفاده نمود يا از روش ديگري تحت عنوان Level building Viterbi استفاده کرد. ازآنجا که الگوريتم شناسايي ويتربي نيمه بهينه است، روشهاي موثري براي محاسبه ميزان نسبت شباهت جمله ارائه شده است که الگوريتم N-best از جمله اين روشها مي باشد. در ادامه به الگوريتم شناسايي ويتربي و الگوريتمهاي بهينه سازي شده Level Building و N-best نيز خواهيم پرداخت.

[بازگشت به فهرست]

 

15-2-1- شناسايي مبتني بر الگوريتم ويتربي

در الگوريتم ويتربي، امتياز ويتربي، ، براي همه حالتهاي مدل زباني در زمان t محاسبه مي شود و آنگاه محاسبه امتياز ويتربي در زمان t+1 با کمک رابطه (34) ادامه مي يابد. اين روال از آن جهت که پردازش را در زمان t کاملا انجام مي دهد و آنگاه به زمان t+1 مي رود، تحت عنوان جستجوي ويتربي همگام با زمان(time synchronous Viterbi search) شناخته مي شود. در نهايت برگشت به عقب در جهت حالتهاي داراي بيشترين امتياز، دنباله حالات بهينه را نتيجه مي دهد. البته اگر تعداد حالات زياد باشد جستجوي ويتربي بسيار پر هزينه خواهد بود. در اين حالت تنها تعدادي از حالات که داراي بيشترين امتياز هستند نگهداري مي شوند و از نگهداري بقيه حالات صرف نظر مي گردد. اين روال جستجو با نام جستجوي پرتويي يا beam search نيز ناميده مي شود.

[بازگشت به فهرست]

 

15-2-2- الگوريتم ساخت سطح Level Building

در اين الگوريتم بر خلاف الگوريتم جستجوي ويتربي، مدلهاي HMM هر واحد گفتاري به صورت جداگانه مدنظر قرارمي گيرد. جستجو در سطوح مختلفي با استفاده از الگوريتم ويتربي انجام مي شود، که در آن هر سطح با محل يک واحد گفتاري در جملات محتملتر متناظر است. بعد از جستجو در هر سطح، ما بيشترين مقدار امتياز ويتربي را براي تمام مدلهاي واحدهاي گفتاري در هر فريم زماني t بدست مي آوريم. جستجو در سطوح بعدي با بيشتين امتياز سطح قبلي در فريم زماني قبلي آغاز مي شود. بعد از انجام جستجوي در  سطح، دنباله مدلهاي گفتاري برنده، گفتار شناسايي شده داراي بيشترين احتمال را تعيين مي کند.

[بازگشت به فهرست]

 

15-2-3- جستجوي N-best

الگوريتم جستجوي N-best بسيار به الگوريتم جستجوي همگام با زمان ويتربي شبيه است. از آنجا که هدف جستجوي N-best يافتن دنباله واحدهاي بهينه به جاي دنباله حالات بهينه است، به جاي عمليات يافتن مقدار ماکزيمم بايد يک عمليات جمع بندي بر روي دنباله حالات انجام شود. در اين حالات علاوه بر عمليات هرسي که براي حذف حالات داراي کمترين امتياز انجام مي شود، يک عمليات هرس نيز براي يافتن بهترين N مسير موجود با بيشترين امتياز انجام مي گردد. در پايان اين اگوريتم N بهترين جمله را نتيجه مي دهد.

[بازگشت به فهرست]

 


16- برخي کاربردها

مدلهاي مارکوف مي توانند کاربردهاي مختلفي در زمينه مدل سازي و يادگيري داشته باشند. چند نمونه از اين کاربردها به قرار زيرند:

*      شناسايي گفتار

*      شناسايي کاراکترهاي نوري

*      ترجمه ماشيني

*      بيوانفورماتيک و ژنشناسي

*      K. F. Lee And H. W. Hon, “Speaker-Independent Phone Recognition Using Hidden Markov Models,” IEEE Transactions On Acoustics, Speech, And Signal Processing, Vol. 31, No. 11, 1989.

در اين مقاله مدل مخفي مارکوف براي يک کاربرد شناسايي واج مستقل از گوينده پيشنهاد شده است. از اين مقاله از چندين کتاب کد از پارامترهاي  LPC و مدلهاي مخفي مارکوف استفاده شده است. در نهايت اين روش با توجه به ويژگيهاي اکوستيکي دادگان گفتاري و همچنين مدل زباني مورد استفاده راندمان شناسايي بين 58.8  تا 73.8  داشته است.

*      T. Vinar, “Enhancements to Hidden Markov Models for Gene Finding and Other Biological Applications,” Thesis presented to the University of Waterloo in fulfilment of requirement for the degree of Doctor of Philosophy in Computer Science, Waterloo, Ontario, Canada, 2005.

در اين تز استفاده از مدل مخفي مارکوف براي مساله يافتن ژنها در ساختارهاي DNA پيشنهاد شده است. يافتن ژنها يکي از قدمهاي اصلي در مساله تحليل مولکولهاي DNA است. در اين مطالعه يک روش براي افزايش قابليتهاي مدل مخفي مارکوف به منظور بهبود پارامترهاي آماري مدل ييشنهاد شده است. در اين پايان نامه اشاره شده است که استفاده از مدلهاي HMM داراي ساختارهاي پيچيده باعث کاهش دقت مدل مي شود و براي حل آن تنها بايد روشهاي پيش بيني و آموزش مدل پيچيده تري را مورد استفاده قرار داد.

*      D. O. Tanguay, “Hidden Markov Models for Gesture Recognition,” Department of Electrical Engineering and Computer Science, In Partial Fulfillment of the Requirements for the Degree of Master of Engineering in Electrical Engineering and Computer Science, August , 1995.

در اين مقاله روشي براي درک و دريافت حرکات بدن انسان با استفاده از مدل مخفي مارکوف پيشنهاد شده است. اين مساله از جمله ممترين مسائل در بينايي ماشين و همچنين طراحي سيستمهاي داراي ارتباط متقابل با کاربر مي باشد.

*      H. Lee and A. Y. Ng, “Spam Deobfuscation using a Hidden Markov Model”.

در اين مقاله از مدل مخفي مارکوف براي شناسايي و رفع ابهام از هرزنامه ها استفاده شده است. آزمايشات انجام شده نشان مي دهد که اين روش نسبت به تمام انواع هرزنامه ها موثر است.

*      S. M. Thede and M. P. Harper, “A Second-Order Hidden Markov Model for Part-of-Speech Tagging,” School of Electrical and Computer Engineering, Purdue University.

*      در اين مقاله يک نوسعه بر مدل مخفي مارکوف با استفاده از تخمين مرتبه دوم براي برچسبگذاري جملات مورد استفاده قرار گرفته است. نتايج اين مقاله حاکي از بهبود برچسبگذاري به نسبت برخي ديگر از روشهاي ارائه شده در اين زمينه مي باشد.

 

*      T. Yang and Y. Xu, “Hidden Markov Model for Gesture Recognition,” The Robotics Institute Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1994.

*      در اين مقاله روشي مبتني بر مدل مخفي مارکوف به منظور توسعه يک سيستم مبتني بر حرکات بدن ارائه شده است. به جاي استفاده از ويژگيهاي هندسي در اين روش از دنباله اي از سمبلها استفاده شده است. براي آموزش اين دنباله از سمبلهاي ورودي از مدل مخفي مارکوف استفاده شده است. راندمان بدست آمده براي اين سيستم براي تشخيص حرکات جداگانه 99.78 درصد بوده است و البته نتايج مناسبي نيز براي کاربردهاي شناسايي حرکات پيوسته بدست آمده است.

*      بازنمايي و استنتاج گرامر يک زبان ساده

C. S. Wallace & M. P. Georgeff. A General Objective for Inductive Inference. [TR32 (HTML)], March 1983, Department of Computer Science, Monash University, Australia.
Also:
M. P. Georgeff & C. S. Wallace. A General Selection Criterion for Inductive Inference. European Conference on Artificial Intelligence (ECAI, ECAI84),
Pisa, pp473-482, September 1984.

 

*      مدلسازي ساختار سريهاي زماني و يا ساير دنباله هايي از داده هاي چند متغيره

T. Edgoose, L. Allison & D. L. Dowe. An MML classification of protein structure that knows about angles and sequence. Pacific Symposium on Biocomputing '98, pp585-596, Jan. 1998 [paper]

T. Edgoose & L. Allison. Minimum message length hidden Markov modelling. IEEE Data Compression Conf., Snowbird UT, pp169-178, March 1998

T. Edgoose & L. Allison. MML Markov classification of sequential data. Stats. and Comp. 9(4) pp269-278, Sept. 1999

 

*      مدل سازي ارتباط بين جفتهاي DNA

L.Allison, C.S.Wallace and C.N.Yee. Inductive Inference over Macro-Molecules. [90/148 (HTML)], CSSE, Monash University, 1990

L.Allison, C.S.Wallace & C.N.Yee. Finite-State Models in the Alignment of Macro-Molecules. J.Molec.Evol. 35(1) pp77-89, 1992

L.Allison. Normalization of Affine Gap Costs Used in Optimal Sequence Alignment. J.Theor.Biol. 161 pp263-269, 1993 [www inc' pdf paper]

C. N. Yee & L. Allison. Reconstruction of Strings Past. CABIOS 9(1) pp1-7 (now J. Bioinformatics) 1993

 

*      انطباق زوج دنباله هاي از مقادير غير تصادفي، مانند مقادير مدل شده توسط يک مدل با حالات محدود يا يک مدل چپ به راست

D. R. Powell, L. Allison, T. I. Dix, D. L. Dowe. Alignment of low information sequences. Australian Comp. Sci. Theory Symp. (CATS98), Perth, pp215-230, Springer Verlag isbn:981-3083-92-1, Feb. 1998

L.Allison. Information-Theoretic Sequence Alignment. [98/14 (HTML)] CSSE Monash University, 1998

L. Allison, D. Powell & T. I. Dix. Compression and Approximate Matching, Computer Journal, 42(1), pp1-10, 1999

D. R. Powell, L. Allison, T. I. Dix. Modelling-Alignment for Non-Random Sequences, AI2004, Springer Verlag, LNCS/LNAI 3339, pp.203-214, Dec. 2004

 

*      مدلسازي ارتباط بين چندين دنباله از مقادير با استفاده از درختهاي تکاملي

L. Allison and C. S. Wallace. The Posterior Probability Distribution of Alignments and its Application to Estimation of Evolutionary Trees and Optimisation of Multiple Alignments. Jrnl. Molec. Evol. 39 pp418-430, 1994

 

*      کشف الگوهاي ضعيف در دنباله هاي DNA

L. Allison, T. Edgoose, T. I. Dix. Compression of Strings with Approximate Repeats. Intelligent Systems in Molecular Biology ISMB98 pp8-16, Montreal, 28 June - 1 July 1998

L. Allison, L. Stern, T. Edgoose & T. I. Dix. Sequence Complexity for Biological Sequence Analysis. Computers and Chemistry 24(1), pp43-55, Jan. 2000

L. Stern, L. Allison, R. L. Coppel, T. I. Dix. Discovering patterns in Plasmodium falciparum genomic DNA. Molecular and Biochemical Parasitology, 118(2) pp175-186, 2001

[بازگشت به فهرست]

 


17- برخي مراجع مفيد در زمينه مدل مخفي مارکوف و ابزارهاي موجود

*      Hidden Markov Model (HMM) Toolbox for Matlab (by Kevin Murphy)

*      Hidden Markov Model Toolkit (HTK) (a portable toolkit for building and manipulating hidden Markov models)

*      Hidden Markov Models (an exposition using basic mathematics)

*      GHMM Library (home page of the GHMM Library project)

*      Jahmm Java Library (Java library and associated graphical application)

*      A step-by-step tutorial on HMMs (University of Leeds)

*      Software for Markov Models and Processes (TreeAge Software)

*      Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

*      Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1999. ISBN 0521629713.

*      Kristie Seymore, Andrew McCallum, and Roni Rosenfeld. Learning Hidden Markov Model Structure for Information Extraction. AAAI 99 Workshop on Machine Learning for Information Extraction, 1999. (also at CiteSeer: [1])

*      http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

*      J. Li, A. Najmi, R. M. Gray, Image classification by a two dimensional hidden Markov model, IEEE Transactions on Signal Processing, 48(2):517-33, February 2000.

[بازگشت به فهرست]

 



[1] Deterministic Model

[2] Statistical Model

[3] Observable

[4] Ergodic Model

[5] Forward Backward Procedure

[6] Viterbi Search

[7] Baum Welch

[8] Left to Right

[9] Bakis

[10] Gaussian Mixture Model(GMM)

[11] Expectation Maximization(EM)