بایگانی‌های مارکوف

بایگانی برچسب برای: مارکوف

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نوامبر 2, 2019/0 دیدگاه /توسط daliri

زنجیره مارکوف (Markov Approach modeling) قسمت 5

آموزش عمومی پردازش تصویر و بینایی ماشین

نمودار انتقال

چهار حالتی که در بالا به آن رسیده ایم را می توان در نمودار انتقال زیر به تصویر کشید :

این نمودار به سادگی هم سهم بازار هر برند و هم نرخ تغییر کاربران را نشان می دهد. برای اینکه بدانیم در یک ماه آینده این نمودار به چه شکلی در خواهد آمد باید چند تا محاسبه ساده مطابق زیر انجام دهیم :

سهم بازار (t+1) شرکت Pepsi‌ = سهم فعلی بازارPepsi * نرخ ماندگاری مشتریان آن + سهم فعلی بازار Coke‌* نرخ ترک مشتریان Coke

سهم بازار (t+1) شرکت Coke= سهم فعلی بازار Coke * نرخ ماندگاری مشتریان آن + سهم فعلی بازار Pepsi‌* نرخ ترک مشتریان Pepsi‌

این محاسبات را می توانیم با ضرب ماتریس ها به صورت زیر هم انجام دهیم :

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

اگر این ماتریس انتقال در گذر زمان ثابت بماند، می توانیم سهم بازار شرکتها را در بازه های زمانی طولانیتر هم بررسی کنیم .

مثلا در پایان ماه دوم سهم بازار شرکتها از قرار زیر خواهد بود :

محاسبه حالت پایدار

شرکت Soda‌ می خواهد بداند که در نهایت سهم بازار هر شرکت چقدر خواهد شد. سهم شرکت Pepsi همانطور که در محاسبات بالا مشاهده می کنید روبه نزول است اما نهایتا بازار به یک حالت ثابت و پایدار خواهد رسید که در آن تبادل و تغییر مشتریان دو شرکت در میزان سهم بازار آنها تاثیری نخواهد داشت یعنی مجموع مشتریان جداشده از شرکت اول با میزان مشتریان جداشده از شرکت دوم برابر خواهد شد . به این حالت، حالت پایدار می گوییم (Steady State)

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

۱- میزان سهم بازار شرکت Pepsi * ۳۰٪ = میزان سهم بازار شرکت Coke * ۱۰٪

۲- میزان سهم بازار شرکت Pepsi + سهم بازار شرکت Coke‌ = ۱۰۰ ٪

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

۴ * Pepsi = ۱۰۰٪ => سهم شرکت Pepsi = ۲۵٪ و سهم شرکت Coke‌ = ۷۵ ٪

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

ماتریس اولیه * ماتریس انتقال = ماتریس اولیه

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

منبع

آشنايي با تئوري زنجيره‌ ماركوف

زنجيره ماركوف، دنباله‌اي از متغيرهاي تصادفي است كه همگي اين متغيرهاي تصادفي داراي فضاي نمونه‌اي يكسان هستند اما، توزيع احتمالات آنها مي‌تواند متفاوت باشد و در ضمن هر متغير تصادفي در يك زنجيره ماركوف تنها به متغير قبل از خود وابسته است. دنباله متغيرهاي تصادفي را بصورت زير نمايش مي‌دهيم:

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

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

با توجه به تعريف زنجيره ماركوف، دانستن اولين مولفه زنجيره و رابطه‌اي كه مولفه i-ام را از مولفه (i-1)-ام توليد مي‌كند، براي ساختن زنجيره كافيست. اين رابطه را تابع تبديل (T) مي‌گوييم و نحوه بدست آوردن مولفه‌هاي بردار احتمال بوسيله اين تابع عبارتست از:

چنانچه در زنجيره ماركوف، رابطه بين متغيرهاي تصادفي متوالي به موقعيت آنها در زنجيره وابسته نباشد، زنجيره را همگن مي‌گوييم. در يك زنجيره همگن:

مي‌توان روابط گفته‌شده را بصورت رابطه ماتريسي زير خلاصه نمود:

با استفاده مكرر از رابطه بالا، مي‌توان نوشت:

چنانچه دو عنصر متوالي از زنجيره ماركوف همگن، يكسان گردند، تمامي عناصر بعدي نيز يكسان خواهند بود و مي‌گوييم زنجيره همگرا شده است، در اين حالت خواهيم داشت:

مي‌توان، انواع مختلفي از زنجيره‌هاي ماركوف تعريف كرد و همگرايي آنها را با استدلالات رياضي بررسي نمود.

زنجيره ماركوف، را ارگوديك مي‌گوييم اگر:

يك زنجيره ماركوف ارگوديك، تنها مي‌تواند به يك توزيع همگرا شود كه توزيع سكون (equilibrium)خوانده مي‌شود و اين مستقل از اولين عنصر زنجيره است. برخي زنجيره‌ها، پريوديك هستند، برخي تضمين همگرايي ندارند و برخي ارگوديك هستند. از اين ميان زنجيره‌هاي ماركوف ارگوديك هستند كه در تئوري نمونه‌برداري كاربرد فراوان دارند.

در اينجا، پرسشي مطرح مي‌شود كه چه موقع يك زنجيره ماركوف ارگوديك است؟ در اين ضمينه قضاياي رياضي وجود دارد كه معروفترين آنها، قضيه اساسي نام دارد. بر طبق اين قضيه يك زنجيره ماركوف همگن، ارگوديك است اگر:

منبع

برای دریافت اطلاعات تکمیلی فایل زیر را دانلود و مشاهده فرمایید.

رمز فایل : behsanandish.com

Markov-Chain

زنجیره مارکوف (Markov Approach modeling) قسمت 1
زنجیره مارکوف (Markov Approach modeling) قسمت 2
زنجیره مارکوف (Markov Approach modeling) قسمت 3
زنجیره مارکوف (Markov Approach modeling) قسمت 4
زنجیره مارکوف (Markov Approach modeling) قسمت 5

نوامبر 2, 2019/3 دیدگاه /توسط hgadmin

زنجیره مارکوف (Markov Approach modeling) قسمت 4

آموزش عمومی پردازش تصویر و بینایی ماشین

زنجیره ارگودیک و زنجیره باقاعده

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

متوسط زمان اصابت

در یک زنجیره ارگودیک زمان اولین بار رسیدن یا اصابت به حالت j در حالی که زنجیر مارکوف در حالت i بوده‌است، زمان اصابت از i به j نامیده می‌شود. زمان اصابت با متغیر تصادفی $T_{ij}$ به صورت زیر توصیف می‌شود:

$T_{ij}=\inf\{n\geq 1:X_{n}=j|X_{0}=i\}.$

متوسط زمان اصابت از i به j، یعنی $H_{ij}=E[T_{ij}]$ ، از رابطهٔ بازگشتی زیر بدست می‌آید:

H_{ij}=\sum _{r\in S}p_{ir}H_{rj}

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

برای یک زنجیر یکنواخت در زمان، بردار ${\boldsymbol {\pi }}$ یک «توزیع ثابت» (یا ایستا) نامیده می‌شود اگر $\pi _{j}$ ‌ها نامنفی و جمع آن‌ها برابر ۱ شود و نیز در رابطه زیر صدق کنند:

$\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}.$

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

$\pi _{j}={\frac {1}{M_{j}}}.\,$

اگر زنجیره باقاعده (غیر تقلیل پذیر و غیر متناوب) باشد آن گاه برای هر i و j داریم:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {1}{M_{j}}}.$

لازم است ذکر شود که هیچ شرطی روی نقطه شروع توزیع وجود ندارد یعنی زنجیره صرف نظر از نقطه شروع به توزیع ثابت میل می‌کند. این π «توزیع تعادل» زنجیره نامیده می‌شود. اگر زنجیره بیش از یک کلاس مرتبط بسته داشته باشد توزیع ثابت آن یکتا نخواهد بود. زنجیره غیر یکنواخت در زمان نیز می‌تواند توزیع تعادل داشته باشد.

در هر صورت اگر حالت j ام غیر متناوب باشد آن گاه:

$\lim _{n\rightarrow \infty }p_{jj}^{(n)}={\frac {1}{M_{j}}}$

و برای هر حالت i دیگر اگر f_ij احتمال این باشد که زنجیره در حالت j قرار گیرد در صورتی که شروع زنجیره از حالت i باشد خواهیم داشت:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {f_{ij}}{M_{j}}}.$

اگر حالت i متناوب باشد با دوره تناوب k > 1 آنگاه حد

$\lim _{n\rightarrow \infty }p_{ii}^{(n)}$

وجود ندارد و نیز حد

$\lim _{n\rightarrow \infty }p_{ii}^{(kn+r)}$

برای هر r صحیح وجود ندارد.

زنجیره وارون پذیر

یک زنجیره مارکوف وارون پذیر نامیده می‌شود اگر یک توزیع احتمال $\pi$ بر روی حالتها وجود داشته باشد به‌طوری‌که برای تمام زمان‌های n و حالتهای i و j رابطهٔ زیر برقرار باشد:

$\pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)$

برای زنجیره‌های یکنواخت در زمان رابطهٔ بالا به صورت سادهٔ زیر نوشته می‌شود:

\pi _{i}p_{ij}=\pi _{j}p_{ji}\,.

توزیع احتمال $\pi$ در رابطهٔ بالا همان توزیع ثابت در زنجیره‌های ارگودیک می‌باشد.

کاربردها

فیزیک

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

علم اطلاعات

زنجیره مارکوف در نظریه اطلاعات کاربرد دارد. مقاله معروف کلود شانون در سال ۱۹۴۸ با «نظریه ریاضی ارتباطات» که پایه‌گذار نظریه اطلاعات شد با معرفی آنتروپی از طریق مدل‌سازی مارکوف از زبان انگلیسی آغاز می‌شود. چنین مدل‌های ایده‌آلی بسیاری از قواعد آماری سیستم را به دست می‌دهند. حتی بدون داشتن ساختار کامل سیستم این گونه مدل‌سازی‌ها فشرده سازی مؤثر داده‌ها را ممکن می‌سازند.

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

نظریه صف

زنجیره‌های مارکوف اساس رفتار تحلیلی صف ها(نظریه صف) می‌باشد و این امر وجود آن‌ها را برای بهینه‌سازی عملکرد شبکه‌های مخابراتی حیاتی می‌سازد. جایی که پیام‌ها برای منابع محدود (مانند پهنای باند) رقابت می‌کنند. مدل‌های صف بندی بسیاری از زنجیره مارکوف زمان پیوسته استفاده می‌کنند. برای مثال، یک صف M / M / 1 یک CTMC بر روی عدد صحیح غیر منفی است که در آن انتقال از i به i + 1 بر اساس یک فرایند پوآسون با نرخ λ رخ می‌دهد و ورود کار را توصیف می‌کند، در حالی که انتقال از i به i – 1 (برای i> 1) در نرخ μ اتفاق می‌افتد (بار خدمات شغلی از توزیع نمایی پیروی می‌کنند) و خدمات کامل یا همان خروج از صف را نشان می‌دهد.

نمایش سادهٔ شبکه‌ای از چند صفحه که با رتبه صفحه ارزیابی شده‌اند.

کاربرد اینترنتی

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

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

منبع

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

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

یک مثال عملی

فرض کنید دو شرکت Coke و Pepsi تنها شرکتهای تولید کننده یک ماده غذایی در کشور X هستند، شرکت Y قصد انتخاب یک شریک تجاری از بین این دو رقیب را دارد. آنها از یک شرکت تحلیلگر بازار خواسته اند که شرایط بازار را برای هر دو برند بررسی کند .شرکتی که بعد از یکماه بیشترین سهم بازار را داشته باشد، برنده این شراکت خواهد بود .

شرکت تحلیل گر نتایج زیر را بعد از بررسی بازار ارائه داده است :

P(P->P) = 0.7 – احتمال ماندن مشتریان برند Pepsi بعد از یکماه با برند Pepsi

P(P->C) = 0.3 – احتمال تغییر شرکت مشتریان Pepsi بعد از یکماه به برند Coke

P(C->C) = 0.9 – حتمال ماندن مشتریان برند Coke بعد از یکماه با برند Coke

P(C->P) = 0.1 – حتمال تغییر شرکت مشتریان Coke بعد از یکماه به برند Pepsi

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

نوامبر 1, 2019/0 دیدگاه /توسط hgadmin

بایگانی برچسب برای: مارکوف

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

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

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

مسایلی که به کمک مدل مخفی مارکوف حل می‌شود

یادگیری

یک مثال ملموس

زنجیره مارکوف (Markov Approach modeling) قسمت 5

نمودار انتقال

محاسبه حالت پایدار

آشنايي با تئوري زنجيره‌ ماركوف

زنجیره مارکوف (Markov Approach modeling) قسمت 4

زنجیره ارگودیک و زنجیره باقاعده

متوسط زمان اصابت

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

زنجیره وارون پذیر

کاربردها

فیزیک

علم اطلاعات

نظریه صف

کاربرد اینترنتی

یک مثال عملی

تلفن های تماس:

ساعات کاری

پیوند ها :

محصولات :