به قلم : تیم تحریریه

فرآیندهای تصادفی، یکی از تئوری‌های مدل‌سازی است که براساس آمار و احتمال شکل گرفته و برای تحلیل داده‌ها به کار می‌رود. در اکثر موارد فرآیندهای تصادفی برحسب زمان فهرست‌بندی یا «اندیس‌گذاری» (Index) شده‌اند. «زنجیره مارکوف» (Markov Chain) یا «فرآیند مارکوف» (Markov Process)، مدلی برای نمایش دنباله‌ای از متغیرهای تصادفی است که در آن احتمال رویداد هر پیشامد فقط به پیشامد قبلی وابسته است. به این ترتیب احتمال رخداد پیشامدها در چنین مدلی فقط به زمان قبل وابسته بوده و بقیه پیشامدها در میزان احتمال دخالت نمی‌کنند. چنین وضعیتی را برای فرایند تصادفی گاهی خاصیت «عدم حافظه» (Memoryless) نیز می‌نامند. این مدل به افتخار ریاضی‌دان روسی «آندری مارکوف» (Andrey Markov) که در سال‌های اولیه قرن بیستم در این زمینه دست به نوآوری زده بود، مدل مارکوف یا زنجیره مارکوف نامیده می‌شود.

از طرفی «مدل پنهان مارکوف» (Hidden Markov Model) یا به اختصار HMM یکی از مدل‌های متداول برای داده‌های موقتی یا مقطعی است. امروزه از این مدل برای بیان خصوصیات چنین داده‌هایی در علم داده استفاده می‌شود. به این منظور برای کسانی که می‌خواهند به عنوان متخصص در تحلیل داده‌ها (Data Scientist) فعالیت کنند، شناخت این مدل و خصوصیات آن ضروری است.

 

قبل از اینکه به معرفی «زنجیره مارکوف» (Markov Chain) و «فرآیند مارکوف» (Markov Process) بپردازیم، باید اصطلاحاتی را در این زمینه معرفی کنیم. همانطور که گفته شد، در فرآیند مارکوف با دنباله‌ای از متغیرهای تصادفی سروکار داریم. بنابراین بهتر است ابتدا متغیر تصادفی، تکیه‌گاه و تابع احتمال و احتمال شرطی را تعریف کنیم.

متغیر تصادفی که به صورت  نشان داده می‌شود، در حقیقت تابعی است از فضای پیشامد و مجموعه‌ای از زیرمجموعه‌های اعداد حقیقی. این عبارت را به زبان ریاضیات به صورت زیر می‌نویسیم.

(Ω,F,P)X−→(R,B,Px)(Ω,F,P)→X(R,B,Px)

به این معنی که متغیر تصادفی X، اعضای فضای نمونه را به اعداد حقیقی، اعضای فضای پیشامد را به مجموعه بورل B از اعداد حقیقی و تابع احتمال مربوط به پیشامد را به احتمال متغیر تصادفی تبدیل می‌کند.

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

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

p(x,y)=P(X=x,Y=y)p(x,y)=P(X=x,Y=y)

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

P(X=xY=y)=P(X=x,Y=y)P(Y=y)P(X=xY=y)=P(X=x,Y=y)P(Y=y)

نکته: اگر متغیر تصادفی P(Y=y)=0P(Y=y)=0 باشد، احتمال شرطی تعریف نخواهد شد.

اگر دو متغیر تصادفی و مستقل باشند، رابطه زیر برحسب تابع احتمال شرطی یا تابع احتمال توام برقرار است.

P(X=xY=y)=P(X=x),P(X=x,Y=y)=P(X=x)P(Y=y)P(X=xY=y)=P(X=x),P(X=x,Y=y)=P(X=x)P(Y=y)

دنباله متغیرهای تصادفی نیز مجموعه‌ای از متغیرهای تصادفی است که براساس اعداد طبیعی اندیس‌گذاری شده‌اند. برای مثال XtXt بیانگر متغیر تصادفی در زمان یا وضعیت است. به این ترتیب دنباله متغیر تصادفی را به صورت {Xt,tT}{Xt,tT} نشان می‌دهند. مجموعه که به آن مجموعه اندیس یا شاخص گفته می‌شود، ممکن است زمان یا مکان در نظر گرفته شود.

فرآیند تصادفی، یک دنباله از متغیرهای تصادفی را یک فرآیند تصادفی گویند اگر هر X(t)X(t) به ازاء ثابت یک متغیر تصادفی باشد. اگر مجموعه tTشامل مقادیر پیوسته باشد، دنباله یا فرآیند تصادفی را پیوسته می‌گویند. در صورتی که مقادیر مجموعه گسسته باشند، فرآیند را در دسته فرآیندهای گسسته قرار می‌دهند.

فضای حالت (State Space) مجموعه مقادیر ممکن برای فرآیند تصادفی {Xt,tT}{Xt,tT} را گویند. می‌توان به نوعی، فضای حالت را مرتبط با تکیه‌گاه متغیرهای تصادفی مربوط به فرآیند در نظر گرفت.

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

زنجیره مارکوف و فرآیند مارکوف زمان-گسسته

دنباله‌ای از متغیرهای تصادفی X1,X2,…X1,X2,… را که احتمال تغییر وضعیت از زمان به t+1t+1 مستقل از وضعیت‌های قبلی باشد را یک زنجیره مارکوف می‌نامند. این گزاره را به بیان متغیرهای تصادفی و تابع احتمال به صورت زیر نشان می‌دهیم.

Pr(Xt+1=xX1=x1,X2=x2,…,Xn=xt)=Pr(Xt+1=xXt=xt)Pr(Xt+1=xX1=x1,X2=x2,,Xn=xt)=Pr(Xt+1=xXt=xt)

نکته: اضح است که در محاسبه این احتمال شرطی باید Pr(X1=x1,…,Xn=xn)>0Pr(X1=x1,…,Xn=xn)>0 باشد در غیر اینصورت امکان محاسبه احتمال شرطی وجود ندارد. این احتمال به معنی طی کردن مسیر X1=x1,…,Xn=xn)X1=x1,…,Xn=xn)) با احتمال مثبت در فرآیند تصادفی است. بنابراین در فرآیند تصادفی مارکوف، امکان رسیدن به نقطه Xt=xtXt=xt از مسیر یاد شده وجود دارد.

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

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

از آنجایی این گراف را می‌توان به صورت یک ماتریس نمایش داد، ماتریس این زنجیره مارکوف نیز به صورت «ماتریس احتمال انتقال» (Transition Probability Matrix) قابل نمایش است. در این حالت عناصر ماتریس که به صورت  pij نوشته می‌شوند، احتمال انتقال از نقطه به را نشان می‌دهد. به این ترتیب ماتریس انتقال برای گراف بالا به ترتیب راس‌ها (مقادیر مربوط به مجموعه فضای حالت) به صورت زیر قابل محاسبه است. واضح است که در اینجا فضای حالت دارای سه عنصر S={a,b,c}S={a,b,c} است.

⎡⎢⎣P11P1200P22P23P310P33⎤⎥⎦[P11P1200P22P23P310P33]

البته در این ماتریس با توجه به اصول احتمال باید k∑j=1pij=1∑j=1kpij=1 باشد. یعنی مجموع احتمالات هر سطر در ماتریس باید برابر با ۱ باشد.

بطور کلی در زنجیره مارکوف، احتمال اینکه از وضعیت به در گام nام برسیم به صورت p(n)ij نشان داده می‌شود. واضح است که به علت وجود خاصیت مارکوفی در زنجیره یا فرآیند مارکوفی داشته باشیم:

p(n)ij=∑rSp(k)irp(n−k)rj,k,0<k<npij(n)=∑rSpir(k)prj(nk),k,0<k<n

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

pij=Pr(X1=jX0=i).pij=Pr(X1=jX0=i).

انجام این کار در طی گام برای یک زنجیره مارکوف همگن-زمان، نیز به شکل زیر نوشته می‌شود.

p(n)ij=Pr(Xk+n=jXk=i).pij(n)=Pr(Xk+n=jXk=i).

نکته: اگر رابطه زیر برای زنجیره مارکوف برقرار باشد آن را زنجیره مارکوف همگن-زمان (Time-Homogeneous Markov Chain) می‌گویند.

Pr(Xt+1=x|Xt=y)=Pr(Xt=x|Xt−1=y)Pr(Xt+1=x|Xt=y)=Pr(Xt=x|Xt−1=y)

خصوصیات زنجیره مارکوف

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

زنجیره مارکوف مرتبه k- با حافظه

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

Pr(Xn=xnXn−1=xn−1, Xn−2=xn−2,…,X1=x1)=Pr(Xn=xnXn−1=xn−1,Xn−2=xn−2,…,Xn−k=xn−k), for n>kPr(Xn=xnXn1=xn1,Xn2=xn2,,X1=x1)=Pr(Xn=xnXn1=xn1,Xn2=xn2,,Xnk=xnk), for n>k

زنجیره مارکوف تقلیل‌ناپذیر (Irreducible)

اگر رسیدن از هر نقطه به نقطه دیگر از فضای حالت با احتمال مثبت در زنجیره مارکوف میسر باشد، زنجیره را تقلیل‌ناپذیر گویند. به بیان ریاضی می‌توان تقلیل‌ناپذیر بودن زنجیره مارکوف را به صورت زیر نشان داد.

Pr(Xnij=jX0=i)=p(nij)ij>0.Pr(Xnij=jX0=i)=pij(nij)>0.

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

زنجیره مارکوف تناوبی (Periodic)

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

k=gcd{n>0:Pr(Xn=iX0=i)>0}k=gcd{n>0:Pr(Xn=iX0=i)>0}

توجه داشته باشید که در اینجا منظور از gcd همان بزرگترین مقسوم علیه مشترک است. گراف رسم شده در تصویر شماره ۱، یک زنجیره تناوبی با دوره تناوب ۱ است زیرا در گام‌های {1,3,4,5,6,,}{1,3,4,5,6,,} می‌توان از هر نقطه به همان نقطه رسید.

مدل پنهان مارکوف (Hidden Markov Model)

مدل پنهان مارکوف، درست به مانند یک فرآیند مارکوف است با این تفاوت که فضای حالت در این جا نامعلوم است. به این ترتیب نمی‌توانیم تشخیص دهیم که وضعیت یا حالت با پیشامدها مطابقت دارد. ولی هر وضعیت با یک خروجی همراه است. به این ترتیب قرار است براساس خروجی حدس بزنیم که دنباله مقدارهای فرآیند (وضعیت‌ها) چه بوده است. چنین مدلی بوسیله «لئونارد بام» ریاضی‌دان آمریکایی در سال‌های حدود 1960 تحقیق و مورد بررسی قرار گرفت. یکی از حوزه‌هایی که در آن مدل پنهان مارکوف به کار گرفته شد، «تشخیص گفتار» (Speech Recognition) و دستخط بود که در سال‌های ۱۹۷۰ ابداع و پیاده‌سازی شد. همچنین مدل‌هایی از نوع پنهان مارکف در سال‌های اخیر در شاخه‌های مختلف بیوانفورماتیک نیز به کار گرفته شده‌اند. 

 

ارتباط با ما

آدرس: شهران، بالاتر از فلکه‌دوم، مجتمع تجاری مهدی،

بلوک B، طبقه‌اول، واحد ۱

پست الکترونیک: info@imcs.institute

تلفن: 44355227-021

آپارات    تلفن   ایمیل   لینکدین   اینستاگرام