نوشته‌ها

مقالات پیرامون تشخیص اعداد و حروف دست نویس فارسی

 

۱٫ ارائه یک روش ساختاری جدید مبتنی بر قطعه بندی تصویر نازک شده برای شناسایی اعداد دست نویس فارسی/عربی

چکیده- در این مقاله، یک روش ساختاری جدید برای استخراج ویژگی از اعداد فارسی/عربی دست نوشته، ارائه شده است. پس از پیش پردازش اولیه و تبدیل تصویر به تصویر باینری، ابتدا رقم دست نوشته، نازک شده و اسکلت آن از تصویر استخراج می شود. سپس نقاط مهم تصویر به دست آمده مشخص می شوند. رقم نازک شده به قطعه خط هایی تقسیم می شود و از هر قطعه، کدهای اولیه استخراج می شود. در نهایت یک بردار ویژگی به دست می آید که طول آن به تعداد قطعه خط ها بستگی دارد. یک مقایسه بین روش ساختاری ارائه شده و روش های آماری دیگر مانند روش های مبتنی بر تبدیل موجک، فرکتال و زرنیک، از نظر زمانی و درصد تشخیص انجام شده است. نتایج نشان می دهند که عملکرد این ویژگیهای ساختاری بسیار بهتر از ویژگی های آماری است. درصد تشخیص با این ویژگی ها و با طبقه بندی کننده مبتنی بر نزدیکترین همسایه، ۹۴/۴۴% به دست آمد. این آزمایشات بر روی دادگانی شامل ۴۸۰ نمونه برای هر رقم انجام شد که ۲۸۰ نمونه برای آموزش و ۲۰۰ نمونه برای آزمایش به کار گرفته شدند.

کلمات کلیدی- روش ساختاری جدید، تشخیص دست نوشته، اعداد فارسی

فایل PDF – در ۷ صفحه- نویسندگان: مجید زیارت بان، کریم فائز، سعید مظفری، مهدی ازوجی

ارائه یک روش ساختاری جدید مبتنی بر قطعه بندی تصویر نازک شده برای شناسایی اعداد دست نویس فارسی یا عربی

پسورد فایل : behsanandish.com


۲٫  بازشناسی برخط حروف مجزای فارسی با شبکه عصبی

چکیده- در این مقاله روشی برای بازشناسی برخط حروف مجزای فارسی با شبکههای عصبی ارائه می شود. پس از بازشناسی علامت های بالا یا پایین حرف ناشناخته، بدنه ی حرف از نظر تعداد نقاط و اندازه نرمالیزه می شود و مختصات نقاط بدنه ی نرمالیزه شده به عنوان ورودی یک شبکه ی عصبی سه لایه در نظر گرفته می شود و بدنه ی حرف ناشناخته بازشناسی می شود. میزان بازشناسی درست برای ۴۱۴۴ حرف، ۹۳/۹% است.

واژه های کلیدی- بازشناسی برخط، حروف مجزا،شبکه ی عصبی

فایل PDF – در ۷ صفحه- نویسندگان: سید محمد رضوی، احسان اله کبیر

بازشناسی برخط حروف مجزای فارسی با شبکه عصبی

پسورد فایل : behsanandish.com


۳٫ کاربرد ترکیب طبقه ها در بازشناسی ارقام فارسی

چکیده- در این تحقیق، برای بهبود بازشناسی ارقام دستنویس از ترکیب طبقه بندی هایی استفاده می شود که از یک الگوریتم یادگیری دو مرحله ای بهره می گیرند. از تصویر هر رقم دستنویس، یک بردار ویژگی با ۸۱ مؤلفه استخراج می شود. به روش تحلیل مؤلفه های اصلی، یک بردار ویژگی با پانزده مؤلفه برای هر رقم انتخاب شده و به سه شبکه عصبی پرسپترون با تعداد نرون های متفاوت در لایه مخفی و وزن های اولیه متفاوت اعمال شده و بازشناسی مستقل در هر طبقه بند صورت می گیرد. در مرحله بعد، نتایج بازشناسی این سه طبقه بند، به یک شبکه عصبی پرسپترون با یک لایه مخفی به عنوان ترکیب کننده اعمال می شود.

پایگاه داده استفاده شده شامل ۲۴۳۰ نمونه است. نرخ بازشناسی شبکه های عصبی پایه بر روی ۵۳۰ نمونه آزمایشی ۸۷% ، ۸۵% و ۸۳% و برای سیستم مرکب ۹۱% است.

واژه های کلیدی- بازشناسی ارقام، ترکیب طبقه بندها، شبکه عصبی پرسپترون، مکان مشخصه، تحلیل مؤلفه های اصلی.

فایل PDF – در ۵ صفحه- نویسندگان: سید حسن نبوی کریزی، رضا ابراهیم پور، احسان اله کبیر

کاربرد ترکیب طبقه ها در بازشناسی ارقام فارسی

پسورد فایل : behsanandish.com


۴٫ بازشناسی حروف برخط فارسی با استفاده از مدل مخفی مارکوف

چکیده- در این مقاله، روشی برای بازشناسی حروف برخط فارسی که به صورت تنها نوشته شده اند، معرفی شده است. با توجه به شکل و ساختار بدنه اصلی، حروف فارسی به ۱۷ گروه تقسیم می شوند. ابتدا، با استفاده از روش آماری مدل مخفی مارکوف به بازشناسی بدنه اصلی پرداخته شده است. در گام بعدی، بازشناسی نهایی در هر گروه با توجه به موقعیت علائم، نقاط و مدل مخفی مارکوف آن ها انجام شده است. روش پیشنهادی بر روی مجموعه داده “حروف برخط دانشگاه تربیت مدرس” اجرا شده و گروه بندی درست با دقت ۹۶% و بازشناسی حروف با دقت ۹۴% به دست آمده است.

کلمات کلیدی- دستنوشته برخط، فارسی، بازشناسی، مدل مخفی مارکوف.

فایل PDF – در ۶ صفحه- نویسندگان: وحید قدس، احسان اله کبیر

بازشناسی حروف برخط فارسی با استفاده از مدل مخفی مارکوف

پسورد فایل : behsanandish.com


۵٫بازشناسی ارقام دستنویس فارسی مقاوم در برابر چرخش و تغییر مقیاس توسط طبقه بندی کننده SVM فازی مبتنی بر خوشه بند K-means

چکیده- در این مقاله روشی را برای تشخیص این ارقام معرفی کردیم که در برابر چرخش و تغییر مقیاس تا حد قابل قبولی مقاوم می باشد. در این مقاله هم برای استخراج ویژگی و هم برای طبقه بندی از دو روش مجزا استفاده کردیم. در مرحله اول برای استخراج ویژگی از آنالیز اجزای اصلی (PCA) استفاده کرده و در نوع دیگری از استخراج ویژگی از آنالیز تفکیک کننده ی خط (LDA) که برای کاهش ابعاد LDA، از تکنینک PCA استفاده کردیم. این ویژگی ها را با طبقه بندی کننده ی MLP و Fuzzy SVM به صورت جداگانه کلاسه بندی کردیم و نتایج را با هم مقایسه کردیم. برای نمایش اینکه روشمان در برابر چرخش و تغییر مقیاس مقاوم می باشد، ۳۰ درصد کل ارقام پایگاه داده مان که متشکل از ۸۶۰ رقم برای هر کدام از ارقام ۰ تا ۹ می باشد را با زاویه های مختلف به صورت تصادفی در جهت یا خلاف جهت عقربه ساعت چرخانه و نتایج به دست آمده را با حالت بدون چرخش مقایسه کردیم. نرخ بازشناسی روش پیشنهادی بر روی ۷۶۰۰ نمونه آزمایشی در حالت بدون چرخش، ۹۷/۳% به دست آمده که نسبت به نرخ بازشناسی همین پایگاه داده، در [۱] و [۲] به ترتیب ۱۵/۴% و ۱/۹% بهبود را نشان می دهد.

کلمات کلیدی- ارقام دستنویس، PCA-LDA، Fuzzy SVM، MLP، PCA

فایل PDF – در ۶ صفحه- نویسنده: مهدی صالح پور

بازشناسی ارقام دستنویس فارسی مقاوم در برابر چرخش و تغییر مقیاس توسط طبقه بندی کننده SVM فازی مبتنی بر خوشه بند K-means

پسورد فایل : behsanandish.com


۶٫ بررسی تأثیر ارتقاء تصویر و اصلاح شیب در بهبود نرخ بازشناسی ارقام جدا شده از اسناد دست نویس فارسی

چکیده- در این مقاله برای اولین بار میزان تأثیر ارتقاء تصویر و اصلاح شیب موجود در ارقام دست نویس فارسی، بر بهبود نرخ بازشناسی ارقام مورد بررسی قرار گرفته است. در ابتدا به دلیل اینکه جداسازی ارقام از تصاویر اسناد دست نویس منجر به ایجاد شکاف هایی در تصاویر ارقام جدا شده می شود، از عنصر ساختاری مناسبی برای ارتقاء تصاویر استفاده شده است. در گام بعدی، شیب موجود در ارقام، تخمین زده شده و اصلاح می گردد. بانک اطلاعاتی استفاده شده در این مقاله شامل ارقام جدا شده (۴۰۹۶ رقم در مجموعه آموزشی و ۱۵۳۲ رقم در مجموعه آزمایشی) از فرم هایی با پس زمینه ی رنگی است که توسط ۵۰۰ نویسنده پر شده اند. آزمایشات انجام شده نشان می دهد که ارتقاء تصویر و اصلاح شیب در مرحله پیش پردازش، به طور میانگین نرخ بازشناسی را به میزان ۳/۳ درصد افزایش می دهد که نشان دهنده ی کارآمدی گام های پیشنهادی( ارتقاء تصویر و اصلاح شیب) در مرحله پیش پردازش است.

کلمات کلیدی- ارتقاء تصویر، عنصر ساختاری، اصلاح شیب، ماتریس شکاف، بازشناسی ارقام دست نویس فارسی.

فایل PDF – در ۵ صفحه- نویسندگان: یونس اکبری، محمدجواد جلیلی، عاطفه فروزنده، جواد صدری

بررسی تأثیر ارتقاء تصویر و اصلاح شیب در بهبود نرخ بازشناسی ارقام جدا شده از اسناد دست نویس فارسی

پسورد فایل : behsanandish.com

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

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

تاریخچه

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

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

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

فرایند مارکوف گسسته

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

 

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

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

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

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

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

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

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

یک مدل مارکوف از مرتبه صفر هیچ حافظه‌ای ندارد و برای هر t و t’ در دنباله سمبل‌ها،  خواهد بود. مدل مارکوف از مرتبه صفر مانند یک توزیع احتمال چند جمله‌ای می‌باشد.

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

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

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

۳- مدل مارکوف مرتبه 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 باشد.

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

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

مدل مخفی مارکوف (HMM)

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

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

 

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

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

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

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

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

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

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

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

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

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

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

 که در آن

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

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

مدل مخفی مارکوف (Hidden Markov Model) قسمت ۱
مدل مخفی مارکوف (Hidden Markov Model) قسمت ۲
مدل مخفی مارکوف (Hidden Markov Model) قسمت ۳
مدل مخفی مارکوف (Hidden Markov Model) قسمت ۴

مدل مخفی مارکوف (به انگلیسی: Hidden Markov Model) یک مدل مارکوف آماری است که در آن سیستم مدل شده به صورت یک فرایند مارکوف با حالت‌های مشاهده نشده (پنهان) فرض می‌شود. یک مدل پنهان مارکوف می‌تواند به عنوان ساده‌ترین شبکه بیزی پویا در نظر گرفته شود.

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

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

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

مثالی از پارامترهای احتمالاتی یک مدل مخفی مارکوف
x — حالت‌ها
y — مشاهده‌های ممکن
a — احتمال‌های انتقال بین حالت‌ها
b — احتمال‌های خروجی‌ها

 

شرح ازنظر مسائل ظرف‌ها

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

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

شکل زیر معماری کلی یک نمونه HMM را نشان می‌دهد. هر شکل بیضی یک متغیر تصادفی است که می‌تواند هر عددی از مقادیر را انتخاب کند. متغیر تصادفی یک حالت پنهان در زمان t و متغیر تصادفی مشاهده در زمان است. فلش‌ها به معنای وابستگی‌های شرطی می‌باشند. از شکل مشخص است که توزیع احتمال شرطی متغیر پنهان ، در همهٔ زمان هایt مقداری را برای x ارائه می‌دهد که فقط به مقدار متغیر پنهان وابسته است: مقادیر در زمان‌های t-2 و قبل‌تر از آن هیچ اثری ندارند. این مشخصهٔ مارکف نامیده می‌شود. به‌طور مشابه، مقدار متغیر مشاهده‌ای تنها به مقدار متغیر پنهان (هر دو در زمان خاص t) بستگی دارد. در حالت استاندارد مدل مخفی مارکوف که در اینجا در نظر گرفته شده‌است، فضای حالت متغیرهای پنهان گسسته است؛ درحالی‌که متغیرهای مشاهده‌ای می‌توانند گسسته یا پیوسته (از توزیع گوسین) باشند.

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

فضای حالت پنهان شامل N مقدار ممکن برای حالات است. متغیر پنهان در زمان t می‌تواند هر یک از این مقادیر را اختیار کند. احتمال جابجایی احتمال این است که در زمان t در حالت k (یکی از حالات ممکن) و در زمان t+1 در حالت k1 باشیم. بنابرین در کل احتمال جابجایی وجود دارد. (مجموع احتمالات جابجایی از یک حالت به تمام حالتهای دیگر ۱ است)

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

اگر تعداد اعضای مجموعهٔ متغیرهای مشاهده‌ای برابر 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و به صورت خاص موردی از الگوریتم exception-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 نمایانگر این است که باب علاقه دارد که در هر هوایی چه کار کند به‌طور مثال در هوای بارانی با احتمال ۵۰٪ آپارتمانش را تمیز کرده یا در هوای آفتابی با احتمال ۶۰٪در پارک قدم می‌زند.

 

HMMGraph

 
 

 

مدل مخفی مارکوف (Hidden Markov Model) قسمت ۱

مدل مخفی مارکوف (Hidden Markov Model) قسمت ۲

مدل مخفی مارکوف (Hidden Markov Model) قسمت ۳

مدل مخفی مارکوف (Hidden Markov Model) قسمت ۴