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

 (Hidden Markov Models)

مدلهای مخفی مارکوف
معرفی

مدلهای مارکوف مخفی اولین بار در یک سری از مقالات آماری توسط Leonard E. Baum و نویسندگان دیگر در نیمه ۱۹۶۰مطرح گردید. اولین کاربرد آن در شناسایی گفتار بود که در نیمه ۱۹۷۰شروع گردید. درنیمه ۱۹۸۰برای آنالیز رشته های بیولوژیکی بخصوص DNA استفاده گردید. از آن زمان بعنوان زمینه ای از بیوانفورماتیک درنظر گرفته شد.

آندری آندرویچ مارکوف

آندری آندرویچ مارکوف٬ فارغ التحصیل دانشگاه سنت پترزبورگ در سال ۱۸۷۸ بود. وی در سال ۱۸۸۶ مدرک پروفسوری خود را دریافت کرد. کارهای زودهنگام مارکوف در تئوری اعداد٬ آنالیز٬ حدود انتگرال ها٬ همگرایی سری ها٬ دنباله کسرها و … بسیار اساسی بود
بعد از سال ۱۹۰۰ ٬ مارکوف تحت تأثیر استاد خود چبیشف٬ از روش دنباله های کسرها در تئوری احتمالات استفاده کرد.وی هم چنین در مورد رشته های متغیرهای وابسته متقابل٬ مطالعاتی انجام داد.با این امید ثابت کردن قوانین حدی در احتمالات در حالات کلی آنها.او قضیه حد مرکزی را با در نظر گرفتن فرض های کامل آن٬ اثبات کرد
مارکوف به دلیل مطالعاتش پیرامون زنجیرهای مارکوف که رشته هایی از متغیرهای تصادفی هستند٬ معروف است.در زنجیرهای مارکوف٬ متغیر بعدی توسط متغیر کنونی مشخص می شود ولی از راهی که تا کنون طی شده است مستقل است.
مدلهای مخفی مارکوف ابتدا در سال‌های اواخر ۱۹۶۰ و اوایل ۱۹۷۰ معرفی و مورد مطالعه قرار گرفت. روش‌های آماری منبع مارکوف یا مدلسازی مارکوف پنهان بطور روزافزونی در سال‌های اخیر متداول گردید. برای این امر دو دلیل بسیار قوی وجود دارد.

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

اولاً مدل‌ها در ساختمان ریاضی خیلی غنی هستند و در اینصورت می‌توانند مبنائی نظری برای استفاده در محدودهء وسیعی از کاربردها را تشکیل دهند. ثانیا” مدل‌ها، در هنگامی که بطور صحیحی بکار برده می‌شوند، در عمل برای کابردهای مهم خیلی خوب کار می‌کنند..
چرا مخفی؟

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

مثال :
متوجه شدن وضع آب و هوا از طریق جلبک

انواع مدل

    مدلهای قطعی

Deterministic Patterns

    مدلهای غیر قطعی

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

Non-deterministic patterns
مدل مخفی مارکوف

مدل مخفی مارکوف یک سری متناهی از حالتهاست، که با یک توزیع احتمال پیوسته است

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

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

با گرفتن مناسب‌ترین تصمیم, بهترین راه حل برای مسئله مطرح شده را تشخیص داده, و به بهترین حالت بعدی ممکن رسید. این راه حل, بصورت یک تابع ارزش نشان داده می شود که در هر حالت (موجود), بهترین حالت بعدی (مطلوب) توسط آن تعیین می‌شود.
معماری مدل مخفی مارکوف

هر شکل بیضی بیانگر یک مقدار متغیر تصادفی است که مقادیری را می پذیرد. x(t) مقدار متغیر تصادفی است که مقدار تغییرپذیرش در واحد زمان مخفی است. y(t) مقدار متغیر تصادفی است که مقدارش در زمان t قابل مشاهده است.

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

از دیاگرام مشخص است که مقدار x(t) به مقدار  x(t − ۱)  وابسته است.که این را خاصیت مارکوف می نامند.

بطورمشابه، مقدار y(t) نیز به x(t) وابسته است.
فرآیند مارکوف

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

    بردار احتمال حالت اولیه
    ماتریس تغییر حالت
    ماتریس اغتشاش

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

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

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

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

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

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

احتمال یک وضعیت به احتمال وضعیت قبلی آن (از نظر زمانی) بستگی دارد, به بیان دیگر احتمال وضعیت‌های ممکن, مستقل نیستند.

    مدل مارکوف مرتبه M

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

    فرض مارکوف

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

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

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

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

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

    مساله ارزیابی
    مساله کدگشایی
    مساله یادگیری

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

    مدل ارگودیک
    مدل چپ به راست
    مدل موازی چپ به راست

الگوریتم ها

    الگوریتم forward یا پیشرو
    الگوریتم viterbi یا ویتربی
    الگوریتم forward-backward یا

پیشرو- پسرو
کاربردهای  HMM

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

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

محدودیت‌های فرآیند مارکوف

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

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

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

جعبه ابزار مدل مخفی مارکوف در مطلب

این جعبه ابزار یک استنباط ویادگیری را برای HMM با خروجی های گسسته (dhmm’s) ،خروجی های گوسین(ghmm’s) ،یا مخلوطی از خروجی های گوسین(mhmm’s) ساپورت میکند.همچنین ورودی های گسسته را ساپورت میکند.

 

تهیه و تنظیم: سمیرا نصر

کارشناسی ارشد مجازی رشته مدیریت فناوری اطلاعات درپزشکی

09367292276
09367292276
[e-mail]
azsoftir.com09367292276
09367292276
[e-mail]
azsoftir.com

دانشکده مهندسی پزشکی دانشگاه صنعتی امیرکبیر

کاربرد فناوری اطلاعات در پزشکی