سه شنبه 25 تیر 1398 |  عضویت / ورود

مدل مخفی مارکوف چیست؟ (آیا پارس‌خوان ۲ در راه است!؟)


عجب درسی شد این درس «نمایه‌سازی» در ترمی که گذشت! چه چیزها که آموختیم و آموزش دادیم!

به هر حال، یکی از مباحثی که من نام آن‌را در همه زمینه‌ها درگیر دیده‌ام، بحثی است به نام «مدل پنهان مارکوف» یا Hidden Markov Model = HMM

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

مدل مخفی مارکوف چیست؟

مشکل؟

بحث را با یک جمله شروع می‌کنم. این جمله را بخوانید: مادر به فرزندش گفت: کرم را به من بده.

خوب، شما (ای انسان!) وقتی به «کرم» رسیدید این کلمه را چه خواندید؟ kErEm؟ درست است؟ چرا kErm یا kArAm یا kOrOm نخواندید؟

اگر بتوانید جواب سؤال من را بدهید، مدل مخفی مارکوف را درک کرده‌اید.

از لحاظ علمی، دلیل این بود: شما کلمه «مادر» را دیدید (یعنی فعلاً یک چیزهایی در ذهن دارید) و بعد که به کلمه «کاف را میم (کرم)» رسیدید با توجه به آنچه قبل‌ها آموخته‌اید (یعنی طی سال‌ها آموخته‌اید که معمولاً «مادر» kErEm را درخواست می‌کند) و با توجه به اینکه چند لحظه قبل کلمه «مادر» را دیده بودید، با توجه به این دانسته‌ها، آن کلمه را kErEm خواندید... اما من به شما بگویم که: گول خوردید!!! شكلك در آوردن من این جمله را از داستانی گفتم که نام طفلِ شیرخوار یک مادر، kArAm بود که این طفل چند لحظه دست دختر بزرگ خانواده بود که مادر خستگی در کند. حالا که خستگی‌اش را در کرد، بنابراین مادر به فرزندش گفت: کرم را به من بده... (چه جالب! حالا همان کلمه را kArAm خواندید!!)

خوب، ببینید، مشکل ما در بحث جستجو همین است! فرض کنید یک نفر در گوگل جستجو می‌کند: کرم ضد آفتاب. تصور کنید گوگل تصویر و مقاله‌ی یک مشت kErm را به او نشان بدهد!!! خداوکیلی شما باشید دیگر این کلمه را جستجو می‌کنید؟ترسيدن

اما خوب، گوگل (آن ماشین!) بنده‌ی خدا از کجا بفهمد که شما منظورتان kErEm بود و نه kErm ؟

ما دقیقاً همان مشکل را در پارس‌خوان داشتیم و داریم! اگر کسی نوشت «کرم را به من بده» این «کاف را میم» را چه بخوانیم؟ kErEm؟ یا kErm یا kOrOm...؟ (به قول یکی از دانشجوها شاید اصلاً این جمله در یک داستان بوده که یک خانواده رفته‌اند ماهیگیری و مادر به فرزندش گفته kErm را به من بده که بزنم سر قلاب و ماهی بگیرم...)

***

به طور خلاصه مدل مخفی مارکوف به همان چیزی اشاره دارد که در بالا اشاره کردم:

یعنی ما با توجه به دانسته‌های قبلی و با توجه به یک سری داده اولیه یا حالت آغازین، به یک حالت یا State پایانی برسیم.

یک بار دیگر:

یعنی ما با توجه به دانسته‌های قبلی (اینکه شما طی سال‌ها معمولاً کلمه مادر را با kErEm دیده‌اید) و با توجه به یک سری داده اولیه یا حالت آغازین (اینکه چند کلمه قبل از «کرم» کلمه «مادر» دیده شد)، به یک حالت یا State پایانی (یعنی kErEm) برسیم.

 

ویکی‌پدیا یک مقاله (بخوانید ترجمه) نسبتاً جامع در مورد مدل مخفی مارکوف دارد (البته بگذریم که آن‌ها به جای «مخفی» می‌گویند «پنهان» که عربی نباشد اما برای «مدل» که انگلیسی است دنبال معادل نمی‌گردند!). در این مقاله یک مثال انصافاً ملموس و جالب آمده که به درک این موضوع خیلی کمک می‌کند. من روان‌ترش را برایتان تعریف می‌کنم:

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

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

حالا تصور کنید الان آلیس می‌خواهد به باب زنگ بزند و می‌خواهد بداند او خانه است (که مثلاً به تلفنش زنگ بزند) یا بیرون از خانه؟ (که مثلاً به موبایلش زنگ بزند)

پس، اینجا هم همان مشکل را داریم. الان باب بالاخره در خانه است یا بیرون؟ (kErEm یا kArAm یا...؟)

مسأله بالا توسط الگوریتم آقای مارکوف به صورت زیر مدل می‌شود:

http://img.aftab.cc/news/93/hmm.png

حالات کلی: بارانی یا آفتابی بودن هوا

مشاهدات: قدم زدن، خرید کردن، تمیز کردن خانه

احتمالات آغازین (یعنی احتمالاتی که آلیس به مرور و طی مدت‌ها صحبت یاد گرفته): به احتمال ۶۰ درصد هوای محل زندگی باب بارانی است و به احتمال ۴۰ درصد آفتابی.

احتمال انتقال از یک حالت به حالت دیگر: اگر دیشب باب گفته باشد که هوا بارانی است، به احتمال ۷۰ درصد امروز نیز بارانی است و به احتمال ۳۰ درصد آفتابی است و اگر دیشب گفته باشد که هوا آفتابی است، به احتمال ۴۰ درصد امروز آنجا بارانی است و به احتمال ۶۰ درصد همچنان آفتابی است...

احتمال بروز یک کار: اگر بارانی باشد به احتمال ۱۰ درصد باب بیرون قدم می‌زند، به احتمال ۴۰ درصد خرید می‌کند و به احتمال ۵۰ درصد خانه است و خانه را تمیز می‌کند. و اگر هوا آفتابی باشد به احتمال ۶۰ درصد قدم می‌زند، به احتمال ۳۰ درصد خرید است و به احتمال ۱۰ درصد در حال تمیز کردن خانه.

این مدل را می‌شود به صورت گراف زیر نشان داد، خوب به آن دقت کنید:

این نوع گراف‌ها را دانشجویان رشته کامپیوتر در درس «نظریه زبان‌ها و ماشین‌ها» یا «ساختمان‌های گسسته» و... دیده‌اند.

حالا می‌توانید راحت‌تر پاسخ بدهید: آلیس می‌خواهد به باب زنگ بزند، دیشب باب گفته هوا آنجا بارانی بوده. به نظر شما الان باب در حال انجام چه کاری است؟

پاسخ: نگاه کنید به حالت یا State یا همان دایره‌ی Rainy، یال‌هایی که عدد بیشتری دارند را دنبال کنید... به احتمال ۷۰ درصد به خودش می‌رود (یعنی وقتی گفته دیشب بارانی بوده به احتمال ۷۰ درصد امروز هم بارانی است) و به احتمال ۵۰ درصد به Clean می‌رود، پس او در حال نظافت و در خانه است...

 

***

پس، برای اینکه ما بفهمیم کلمه «کرم» را kErEm تلفظ کنیم یا kArAm یا kErm... نیاز به چنین گرافی داریم که از طریق مدل مارکوف به دست می‌آید.

یعنی به طور ساده، ما باید بدانیم کلمه «کرم» در کنار کلمات مختلف، کدام تلفظش را به خودش می‌گیرد؟ مثلاً: اگر کنار کلمه «مادر» بود، به احتمال ۹۰ درصد kErEm تلفظ می‌شود و به احتمال ۵ درصد kArAm به احتمال ۳ درصد kErm و به احتمال ۲ درصد kOrOm

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

می‌دانید این چه دیتابیس بزرگی می‌شود؟ مثلاً در مورد زبان فارسی، باید تمام کلمات فارسی را تک به تک با تمام کلمات دیگر، احتمال انواع تلفظشان را بگویید!! یعنی n به توان n ضرب در تعداد تلفظهای هر کلمه!!!!

طبیعتاً چنین چیزی در نگاه اول محال است! اما خوب، می‌شود این درخت بزرگ را هرس کرد و زائدها را حذف کرد که این خودش یک رساله دکتراست!!

و یا می‌توان در ساده‌ترین حالت، مانند آن دیتابیس همشهری، از ۱۱ سال مطالب روزنامه همشهری یک دیتابیس ساخت و توسط انسان، تعداد تکرار هر کلمه (بسامد کلمه) با تلفظ‌های مختلف را به دست آورد...

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

http://img.aftab.cc/news/93/hmm_parskhan_db.png

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

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

 

کاربردهای مدل مخفی مارکوف:

این مدل در زمینه‌های بسیار زیادی کاربرد دارد:

- تبدیل گفتار به صدا (تشخیص گفتار):

تصور کنید شما در حال خواندن یک متن برای یک نرم افزار هستید که او آن‌را تایپ کند. اگر تلفظ یک کلمه شبیه یک کلمه دیگر باشد مثلاً می‌گویید: Important Object نرم افزار ممکن است Import an Object بشنود... چطور تشخیص دهد که کدام منظور شما بوده؟ با مدل مخفی ماکوف و چیزهایی که قبلاً یادش داده‌اید...

- تشخیص چهره:

مثلاً فکر کنید یک نرم افزار تشخیص چهره، فاصله بین دو مردمک چشم را ملاک شناسایی قرار دهد. اگر برای دو نفر از افراد یک سازمان این فاصله یکسان باشد، کدام یکی الان جلو دستگاه ایستاده؟ با توجه به دانسته‌های دیگر می‌شود فهمید...

- ترجمه ماشینی:

همه با Google Translate کار کرده‌اند و می‌دانند که گاهی چقدر ضایع ترجمه می‌کند! دلیل؟ هنوز دیتابیس مربوط به مدل مخفی مارکوف گوگل کامل نشده. به همین دلیل است که گوگل، Community Help را راه‌اندازی کرده و از شما انسان‌ها خواسته به مرور به آن نرم افزار یاد بدهید که وقتی فلان کلمه کنار فلان کلمه قرار می‌گیرد ترجمه اش چه می‌شود؟

و صدها کاربرد دیگر...

 

حالا فکر می‌کنید پارس‌خوان ۲ (پارس‌خوان هوشمندتر+...) در راه است یا خیر؟ :)

موفق باشید؛
حمید رضا نیرومند


[ارسال شده در مورخه : جمعه، 12 دی، 1393 توسط Hamid]
[ #دانستني‌هاي IT]



بازدیدها از این مطلب: 8261 بار   امتیاز متوسط :   تعداد آراء: 1   امتیاز دهید:

نظرات طرح شده

نام: [ کاربر جدید ]
ایمیل:

نظر:


اجازه استفاده از تگهای HTML را ندارید


جمع عدد 8 با 7 را در كادر زیر وارد نمایید:
(این كار برای جلوگیری از فعالیت موتورهای اسپمر است)


* توجه: نظر شما بعد از بررسی، نمایش داده خواهد شد.

یک معلم زبان (امتیاز : 0)(لینک نظر)
توسط یک معلم زبان در مورخه : جمعه، 12 دی، 1393


سلام.

هرچند خیلی بحث رایانه ای بود ولی آن هایی که زبان شناسی خواندن هم ازین بحث ها دارند. شاید کتاب هایی در حوزه Pragmatics یا معناشناسی کمی اطلاعات جالب تری به شما بدهد و در مورد ارتباطات میان کلمه ای چیز های بیشتری ب هذهنتان بیاید که به شما کمک کند و یک کتاب هم هست به نام "معنا شناسی " که همه ترجمه شده اش و هم تالیفی اش در بازار موجود است...





البته مسایل خیلی پیشرفته تر و جالب تری هم هست ولی فکر نکنم که الان مورد نیاز باشد. مثلا garden pathing! که به نوعی بحث می کند در مورد این که چرا معناهای بعضی جمله ها را اشتباه می فهمیم یا در مسیر غلط ترجمه می کنیم...


[ ارسال جوابیه ]


فرهاد (امتیاز : 0)(لینک نظر)
توسط فرهاد در مورخه : جمعه، 12 دی، 1393
سلام

جالب بود

امکان دارد احتمال اولیه 60 ، 40 بعدا تغییر کنید به مثلا 30 ، 70 ؟

یعنی حالت اولیه امکان تغییر دارد یا فقط یکبار تعریف می گردد؟


[ ارسال جوابیه ]


حمید                توسط حمید در مورخه : جمعه، 12 دی، 1393(لینک نظر)
من حالا بهتره یه خاطره ای در مورد این نرم افزار رو بگم که یکی که داشت فارسی یاد میگرفت میگفت نرم افزاری واسه این کار وجود نداره ولی من که با سایت شما آشنا بودم نرم افزار رو بهش دادم و تعجب کرد ولی در نهایت گفت که خیلی "روبوتی"" هست و میگفت که این سایت فوروو رو که طبیعی هست ترجیح میده !

اما در مورد گوگل ترانسلیت مطمئنید تلفظ رو بررسی میکنه ؟ آخه فکر کنم منظورتون ترجمه بوده البته واسه بعضی زبان ها تلفظ داره ولی واسه فارسی ترجمس فقط


[ ارسال جوابیه ]


imanmoodi                توسط imanmoodi در مورخه : جمعه، 12 دی، 1393(لینک نظر)
واقعاً جالب بود، ممنون


[ ارسال جوابیه ]


مریم قلی زاده (امتیاز : 0)(لینک نظر)
توسط مریم قلی زاده در مورخه : پنجشنبه، 31 اردیبهشت، 1394
سلام و با تشکر از توضیحات بسیار روان و زیبا اقای نیرومند در خصوص مدل مخفی مارکوف خیلی عالی توضیح دادید من لذت بردم. تشکر


[ ارسال جوابیه ]


ایمان (امتیاز : 0)(لینک نظر)
توسط ایمان در مورخه : جمعه، 4 دی، 1394
خیلی خوب بود ممنون


[ ارسال جوابیه ]


شیرخانی                توسط شیرخانی در مورخه : پنجشنبه، 19 فروردین، 1395(لینک نظر)
توضیحات جالب و روان و قابل فهم ، واقعا ممنون


[ ارسال جوابیه ]


الهه                توسط الهه در مورخه : شنبه، 24 مهر، 1395(لینک نظر)
عالی بود، ممنون از توضیحات بسیار خوب و روانی که دادید.


[ ارسال جوابیه ]


فرزاد واشقانی فراهانی (امتیاز : 0)(لینک نظر)
توسط فرزاد واشقانی فراهانی در مورخه : شنبه، 6 آذر، 1395
سلام. مطلب جالب و خواندنی نوشته بودید. استفاده کردم.


[ ارسال جوابیه ]


سولماز (امتیاز : 0)(لینک نظر)
توسط سولماز در مورخه : شنبه، 2 اردیبهشت، 1396
با تشکر از شما خیلی واضح توضیح دادید


[ ارسال جوابیه ]


شادان (امتیاز : 0)(لینک نظر)
توسط شادان در مورخه : یکشنبه، 10 اردیبهشت، 1396
تو عمرم همچین مطلب اموزش با بیان ساده ندیدم..واقعا ازتون ممنونم خیلی ممنونم دمتون گرمممممممممممم


[ ارسال جوابیه ]


محمود                توسط محمود در مورخه : یکشنبه، 10 اردیبهشت، 1396(لینک نظر)
توضیحات خیلی خوب و ساده و روان بودن
مرسی


[ ارسال جوابیه ]


منوچهر                توسط منوچهر در مورخه : دوشنبه، 6 شهریور، 1396(لینک نظر)
مطلبی بسیار عالی. تشکر بسیار فراوان


[ ارسال جوابیه ]


رضا (امتیاز : 0)(لینک نظر)
توسط رضا در مورخه : جمعه، 8 تیر، 1397
مرسی عزیزم عااااااااااااااالی بود


[ ارسال جوابیه ]


فرهاد (امتیاز : 0)(لینک نظر)
توسط فرهاد در مورخه : پنجشنبه، 4 بهمن، 1397
خیلی عالی بود، تشکر


[ ارسال جوابیه ]