بایگانی‌های کنترل تردد

بایگانی برچسب برای: کنترل تردد

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

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

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

تاریخچه

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

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

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

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

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

\ P(q_{t}=S_{j}|q_{t-1}=S_{i},q_{t-2}=S_{k},...)=

\ P(q_{t}=S_{j}|q_{t-1}=S_{i})

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

$\ a_{ij}=P(q_{t}=S_{j}|q_{t-1}=S_{i})\qquad i\geq 1,N\geq j$

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

$a_{ij}\geq 0$

$\sum _{j=1}^{N}a_{ij}=1$

فرایند تصادفی فوق را مدل مارکوف قابل مشاهده می‌گویند زیرا خروجی مدل مجموعه‌ای از حالات است که قرار گرفتن در آن‌ها متناظر با یک مشاهده می‌باشد. ما می‌توانیم دنباله مشاهدات مورد انتظار خود را تولید کنیم و احتمال وقوع آن در زنجیره مارکوف را محاسبه نماییم. برای مثال با داشتن دنباله مشاهدات $\ O={q_{1},...,q_{t}}$ احتمال وقوع آن به صورت زیر بیان می‌شود.

$\ P(O|Model)=P({q_{1},q_{2},...,q_{2}}|Model)$

$\ P(q_{1}).P(q_{2}|q_{1}).P(q_{3}|q_{2})...P(q_{t}|q_{t-1})$

یکی دیگر از مواردی که مطرح می‌شود این است که اگر سیستم در حالت $\ q_{i}$ باشد با چه احتمالی به حالت $\ q_{j}$ می‌رود و با چه احتمالی در همان حالت $\ q_{i}$ باقی می‌ماند.

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

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

یک مدل مارکوف از مرتبه صفر هیچ حافظه‌ای ندارد و برای هر t و t’ در دنباله سمبل‌ها، $\ pr(X_{t}=S_{i})=pr(X_{t'}=S_{i})$ خواهد بود. مدل مارکوف از مرتبه صفر مانند یک توزیع احتمال چند جمله‌ای می‌باشد.

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

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

$\ pr(X_{t}=S_{i}|X_{t-1}=S_{j}),fori=1..k,j=1..k$

تعریف فوق مانند این است که k مدل مارکوف در مرتبه صفر برای هر $\ S_{j}$ داشته باشیم.

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

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

مثال ۱: برای مثال اگر یک سکه معیوب A داشته باشیم که احتمالات شیر یا خط آمدن برای آن یکسان نباشد، می‌توان آن را با یک مدل مارکوف درجه صفر با استفاده از احتمالات (pr(H و (pr(H توصیف نمود.

pr(H)=0.6, pr(T)=۰٫۴

مثال ۲: حال فرض کنید که سه سکه با شرایط فوق در اختیار داریم. سکه‌ها را با اسامی B, A و C نام‌گذاری می‌نماییم. آنگاه برای توصیف روال زیر به یک مدل مارکوف مرتبه اول نیاز داریم:

فرض کنید سکه X یکی از سکه‌های A یا B باشد.
مراحل زیر را تکرار می‌کنیم.

a) سکه X را پرتاب می‌کنیم و نتیجه را می‌نویسیم.

b) سکه C را نیز پرتاب می‌کنیم.

c) اگر سکه C خط آمد، آنگاه سکه X را تغییر می‌دهیم (A را با B یا B را با A جایگزین می‌کنیم) و در غیر این صورت تغییری در سکه‌ها نمی‌دهیم.

انجام روال فوق مدل مارکوف مرتبه اول زیر را نتیجه خواهد داد.

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

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

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

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

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

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

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

$\ A={a_{ij}}$

$\ A=[a_{ij}]$ ماتریس انتقال حالت:یک مجموعه از احتمالات در بین حالت‌ها

$\ a_{ij}=p(q_{t+1}=j|q_{t}=i),\qquad i\geq 1,N\geq j$

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

$\ a_{ij}\geq 0,\qquad i\geq 1,N\geq j$

$\sum _{j=1}^{N}a_{ij}=1,\qquad 1\leq i\leq N$

برای حالات مدل ارگودیک برای تمامi وjها مقدار $\ a_{ij}$ بزرگتر از صفر است و در موردی که اتصالی بین حالات وجود ندارد $\ a_{ij}=0$ است.

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

$\ B={b_{j}(k)}$

$\ b_{j}(k)=p{o_{t}=v_{k}|q_{t}=j},\qquad 1\leq j\leq N,\qquad 1\leq k\leq M$

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

$\ b_{j}(k)\qquad 1\leq j\leq N,\qquad 1\leq K\leq M$

$\sum _{K=1}^{M}b_{j}(k)=1,\qquad 1\leq j\leq N$

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

$\ b_{j}(o_{t})=\Sigma _{m=1}^{M}c_{jm}\mu (\mu _{jm},\Sigma _{jm},o_{t})$

که در آن $\ \mu _{jm}$ ، $\ C_{jm}$ , $\ \Sigma _{jm}$ , به ترتیب ضریب بردار میانگین، ضریب وزندهی و ماتریس کواریانس می‌باشند. در رابطه فوق مقادیر $\ c_{jm}$ باید شرایط زیر را ارضا نماید:

$\ c_{jm},\qquad 1\leq j\leq N,\qquad 1\leq m\leq M$

$\sum _{m=1}^{M}c_{jm}(k)=1,\qquad j\geq 1,N\geq j$

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

$\ \pi =(\pi _{i})$ که در آن

$\ \pi _{i}=p(q_{1}=i),\qquad 1\leq i\leq N$

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

$\ \lambda =(\mathrm {A} ,\mathrm {B} ,\pi )$

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

$\ \lambda =(\mathrm {A} ,C_{jm},\mu _{jm},\Sigma _{jm},\pi )$

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

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

مدل مخفی مارکوف (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

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

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

تکامل گذرا

احتمال تغییر حالت از حالت iام به حالت jام در n حرکت برابر است با

p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,

این احتمال در یک حرکت برابر است با

p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,

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

$p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)\,$

$p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i)\,$

توجه کنید که برای یک زنجیره مارکوف یکنواخت در زمان، احتمال تغییر حالت از حالت iام به حالت jام در n حرکت معادل است با درایهٔ (i,j) ام ماتریس احتمال انتقال وقتی این ماتریس n بار در خودش ضرب شده‌است:

$p_{ij}^{(n)}=[P^{n}]_{ij}$

در حرکت‌های n تایی احتمالات بدست آمده برابری چپمن-کولموگروف را ارضا می‌کنند. پس برای هر k که ۰ <n> k داریم

p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}

در این رابطه S فضای حالت زنجیره مارکوف است. توزیع حاشیه ای (Pr(X_n = x مربوط به حرکت nام است. توزیع اولیه برابر است با (Pr(X_۰ = x. تعمیم یافته این توزیع برای حرکت‌های بعدی به شکل

$\Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).$

نمایش داده می‌شود که در آن n زیروند است و نه توان.

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

تقلیل‌پذیری

حالت jام را قابل دسترسی از حالت iام می‌نامند (i → j) اگر در سیستمی که از حالت iام شروع شود با احتمال غیر ۰ در نهایت به حالت jام برسد. در واقع اگر عدد صحیح n ≥ ۰ وجود داشته باشد که

\Pr(X_{n}=j|X_{0}=i)=p_{ij}^{(n)}>0.\,

تساوی n با ۰ به معنای در دسترس بودن همه حالات از حالت iام است. حالت iام را مرتبط با حالت jام می‌نامند (i ↔ j) اگر هر دو رابطه i → j و j → i برقرار باشند.

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

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

حالت i را ضروری می‌نامند اگر به ازای همه jهایی که i → j، رابطه j → i نیز برقرار باشد. در غیر این صورت حالت i را غیرضروری می‌نامند.

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

تناوب

حالت i دارای دوره تناوب k است اگر هر مسیر بازگشت به حالت i به طول مضارب k باشد. به زبان دیگر دوره تناوب یک حالت برابر است با

k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}

که در آن gcd بزرگترین مقسوم علیه مشترک است. اگر یک حالت دوره تناوب k داشته باشد ممکن است نتوان به این حالت با k حرکت رسید. به‌طور مثال اگر بتوان به حالت i در {۶, ۸, ۱۰, ۱۲, …} حرکت بازگشت، در این صورت دوره تناوب برابر ۲ خواهد بود حتی اگر ۲ در مقادیر ذکر شده نباشد. اگر k = ۱ باشد، در این صورت به حالت مد نظر غیر متناوب می‌گویند و بازگشت به حالت i در حرکت‌های غیر منظم انجام خواهد گرفت. در غیر این صورت (k > 1)، حالت iدارای دوره تناوب k و متناوب می‌باشد.

بازگشت‌پذیری

فرض کنید f_i احتمال این پیشامد باشد که زنجیر با شروع از وضعیت i بعد از تعداد متناهی تغییر وضعیت به i برگردد. به وضوح $f_{i}=\sum _{n=1}^{\infty }f_{ii}^{n}\,$ . اگر $f_{i}=1$ در این صورت حالت i را بازگشتی یا پایامی‌گوییم. به این ترتیب هر بار که زنجیر در حالت i قرار می‌گیرد فرایند به‌طور احتمالی حرکت خود را از سر شروع می‌کند، لذا اولین بازگشت به i مستلزم بازگشت دوم به i، و الی آخر است؛ بنابراین اگر i حالت بازگشتی باشد، فرایند با احتمال ۱ بینهایت بار به i برمی‌گردد و احتمال اولین بازگشت به این حالت در زمان متناهی برابر ۱ است. اگر امید ریاضی تعداد تغییر وضعیت‌ها تا بازگشت مجدد به i متناهی باشد به i بازگشتی مثبت و در غیر این صورت بازگشتی پوچ می‌گوییم.

حالت i را گذرا می‌نامند هرگاه $f_{i}<1$ ، به این معنی که اگر سیستم از حالت i شروع به کار کند، احتمال این که دیگر به این حالت بازنگردد غیر صفر است. برای حالت گذرای i احتمال این که فرایند با شروع از i دقیقاً بعد از n بار به آن بازگردد برابر است با $(f_{i})^{n}(1-f_{i})$ . پس تعداد بازگشت‌ها به i متغیر تصادفی با پارامتر $1-f_{i}$ می‌باشد، درنتیجه تعداد بازگشت‌ها بینهایت نمی‌شود.

با در نظر گرفتن متغیر تصادفی T_i، زمان اولین بازگشت به حالت i، داریم:

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

عدد $f_{ii}^{(n)}=\Pr(T_{i}=n)$ احتمال بازگشت سیستم به حالت i برای اولین بار در حرکت nام است. در نتیجه حالت i گذرا است اگر

$\Pr(T_{i}<{\infty })=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1$

متوسط زمان بازگشت

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

M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.\,

محاسبه می‌شود.

متوسط تعداد بازگشت‌ها

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

\sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .

چند قضیه مهم

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

حالت‌های مانا

حالت i را جذب‌کننده یا مانا می‌نامند اگر با ورود به این حالت خروج از آن غیرممکن باشد. در نتیجه حالت i مانا است اگر و تنها اگر

p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.

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

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

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

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

تعریف رسمی

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

یک زنجیره مارکوف دنباله‌ای از متغیرهای تصادفی X_۱،X_۲،X_۳،… است که دارای خاصیت مارکوف هستند یعنی:

$\Pr(X_{n+1}=x|X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x|X_{n}=x_{n}).\,$

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

زنجیره مارکوف اغلب توسط دنباله‌ای از گراف‌های جهت‌دار نشان داده می‌شود، که در آن یال‌های گراف n توسط احتمال از رفتن از یک حالت در زمان n به حالت‌های دیگر در زمان n + 1 برچسب گذاری شده‌است. همان اطلاعات در ماتریس انتقال از زمان n به زمان n + 1 درج می‌شود که در آن عنصر سطر i و ستون j، احتمال تغییر وضعیت از حالت i-1 به حالت j-1 است. مجموع عناصر هر سطر برابر یک است اما الزاماً مجموع عناصر هر ستون یک نمی‌شود. در نظریه ماتریس‌ها اگر تمام عناصر ماتریسی نامنفی و مجموع عناصر هر سطر یک باشد، در این صورت آن ماتریس را ماتریس مارکوف می‌گویند. علت آن است که برای چنین ماتریس‌هایی می‌توانیم یک فضای نمونه بسازیم به طوری که عناصر ماتریس، احتمال‌های تغیر وضعیت تمام پیشامدهای فضای نمونه باشند و سپس یک زنجیر مارکوف برای فضای نمونه تعریف کنیم. با این حال، زنجیره‌های مارکوف اغلب به صورت یکنواخت در زمان فرض می‌شوند در این صورت گراف و ماتریس مستقل از n هستند و به این ترتیب به شکل یک توالی ارائه نمی‌شوند.

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

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

زنجیره‌های مارکوف یکنواخت در زمان، یا ایستا، زنجیره‌هایی هستند که در آن‌ها:

$\Pr(X_{n+1}=x|X_{n}=y)=\Pr(X_{n}=x|X_{n-1}=y)\,$

که رابطه بالا برای هر n صحیح است. در واقع احتمال انتقال مستقل از n است. چنین زنجیره‌هایی را می‌توان تنها با یک ماتریس احتمال انتقال $P$ توصیف کرد. ماتریس احتمال انتقال $P$ مستقل از زمان n است و درایهٔ (i,j) ام آن، یعنی $p_{ij}$ ، بیانگر احتمال انتقال از حالت i به حالت j می‌باشد.

زنجیره مارکوف مرتبه m

زنجیره مارکوف مرتبه m (که در آن m متناهی است) فرایندی است که در آن:

${\begin{aligned}{}&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}$

به عبارت دیگر حالت بعدی به m حالت قبلی وابسته‌است. می‌توان یک {Y_n} از {X_n} ساخت به طوری که در فرم کلاسیک خاصیت مارکوف صدق کند؛ که در این صورت Y یک چندتایی مرتب از Xها است یعنی: $Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)$

زنجیره مارکوف افزاینده

یک زنجیره مارکوف افزاینده مرتبه m با رابطه زیر توصیف می‌شود:

$\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m})=\sum _{r=1}^{m}f(x_{n},x_{n-r},r).$

زنجیره مارکوف زمان پیوسته

لامپی را در نظر بگیرید که یا روشن است یا خاموش. اگر لامپ در زمان t روشن باشد X(t) = 1 و اگر خاموش باشد X(t) = 0. در این صورت متغیر تصادفی X زمان گسسته نیست زیرا پس از ورود به حالتی برای یک مدت زمانی که خود نیز متغیری تصادفی است، در آن جا می‌ماند و سپس به حالت دیگری منتقل می‌شود. این قبیل فرایندها را زنجیره مارکوف زمان پیوسته می‌نامیم.

یک زنجیره پیوسته مارکف توسط یک فضای حالت متناهی یا شمارا، یک ماتریس نرخ انتقال Q با ابعادی برابر با فضای حالت است. برای i ≠ j، هر عنصر q_ij غیر منفی است و نرخ انتقال فرایند را از حالت i به حالت j توصیف می‌کند.

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

تعریف حدی

اگر متغیر تصادفی وضعیت زنجیره درلحظهٔ t با X_t نشان دهیم و فرض کنیم زنجیره در زمان t در حالت i قرار دارد. با توجه به این که X_t = i و X_t+h به مقادیر گذشته وابسته نیستند، هنگامی که h → ۰ برای هر j و t داریم:

\Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)

که در این معادله $\delta _{ij}$ دلتای کرونکر است و همچنین از نماد o کوچک استفاده شده‌است. q_ij می‌تواند معیاری از سرعت تغییر حالت از i به j باشد.

تعریف زنجیره پرش یا زمان نگهداری

اگر متغیر تصادفی Y_n نشان‌دهندهٔ nامین پرش (تغییر حالت) در زنجیره باشد و متغیرهای $S_{1},S_{2},S_{3},...$ زمان ایستایی در هر حالت را نشان دهند، هر کدام از S_iها از توزیعی نمایی با پارامتر $q_{Y_{i}Y_{i}}$ پیروی می‌کنند.

تعریف احتمال انتقال

برای هر مقدار $n=0,1,2,...$ و زمان‌های $t_{0},t_{1},t_{2},...$ با حالت‌های $i_{0},i_{1},i_{2},...$ داریم:

\Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})

که در آن p_ij در دو مجموعه معادلات دیفرانسیلی به نام‌های معادلات پیشرو کولموگروف و معادلات پسرو کولموگروف en:Kolmogorov equations صدق می‌کنند.

اکتبر 31, 2019/0 دیدگاه /توسط hgadmin

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

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

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

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

معرفی

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

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

یکی از معروف‌ترین زنجیره‌های مارکوف که موسوم به «پیاده‌روی می خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.

مثالی دیگر عادات غذایی موجودی است که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

او فقط یک بار در روز غذا می‌خورد.
اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.

عادات غذایی این موجود را می‌توان با یک زنجیره مارکوف مدل‌سازی کرد به دلیل این که چیزی که فردا می‌خورد (حالت بعدی) تنها به چیزی که امروز خورده‌است (حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی درصد روزهایی است که انگور خورده‌است (در یک دوره طولانی).

مثال‌هایی از زنجیره مارکوف

ورشکستگی قمارباز

ورشکستگی قمارباز مسئله‌ای معروف از زنجیره مارکوف است. در این مسئله دو فرد تاس می‌اندازند و هر بار که سکه شیر آمد شخص A یک دلار از B می‌برد و هر بار سکه خط بیاید، شخص B یک دلار از A می‌برد. در ابتدای بازی A مقدار a دلار و B مقدار b دلار دارد. فرض کنید X_i دارایی A پس از i مرحله بازی باشد. یکی از خواص دنباله {X_i} این است که اگر در مرحلهٔ nام مقدار X_i را بدانیم در این صورت سرمایه A از آن مرحله به بعد تنها به X_n و نه به X₀, X₁, …, X_n-1 وابسته است. یعنی اگر سرمایهٔ A در زمان حال معلوم باشد، سرمایهٔ آیندهٔ او مستقل از پولی است که در هر مرحله از بازی در گذشته برنده شده یا باخته‌است.

فرایند زاد مرگ

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

بازی‌های تخته‌ای با تاس

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

گام‌های تصادفی متمایل به مرکز

یک حرکت تصادفی روی تعدادی خط را در نظر بگیرید، موقعیت کنونی (که x نامیده می‌نامیم) با احتمالات زیر می‌تواند به +۱ (به راست) یا -۱(به چپ) تغییر کند:

(c یک عدد ثابت بزرگتر از ۰ است)

به عنوان مثال اگر عدد ثابت c برابر ۱ باشد، احتمال حرکت به چپ از موقعیت x=-۲,-۱٬۰٬۱٬۲ به ترتیب برابرست با:.

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

یک مدل آب و هوایی بسیار ساده

نمونه‌ای ساده از یک مدل آب‌وهوایی

احتمال وضعیت آب و هوایی که آب و هوا در طول روز را نشان می‌دهد و هم به صورت بارانی و هم آفتابی مدل می‌شود، توسط یک ماتریس انتقال ارائه داده می‌شود. ماتریس P یک مدل آب و هوایی را نشان می‌دهد به‌طوری‌که روز بعد یک روز آفتابی، با احتمال %۹۰ آفتابی است و روز بعد یک روز بارانی، با احتمال %۵۰ آفتابی است. ستونها و سطرها با آفتابی و بارانی برچسب‌گذاری می‌شوند.

(P)_{i j} احتمال این است که هوای امروز از نوع i باشد و فردا از نوع j باشد.

در نظر داشته باشید که حاصل جمع احتمالات سطر P برابر ۱ است.

حالت ثابت آب و هوا

در این مثال، پیش‌بینی هوا در روزهای دور از هم غلط از آب در می‌آید و متمایل به بردار حالت پایدار است. این بردار احتمال هوای آفتابی و بارانی را در همهٔ روزها نشان می‌دهد و مستقل از آب وهوای اولیه است.

بردار حالت ثابت به این صورت تعریف می‌شود: $\mathbf {q} =\lim _{n\to \infty }\mathbf {x} ^{(n)}$

ولی تنها زمانی به یک مقدار منظم همگراست که p یک ماتریس انتقال منظم باشد (بعبارت دیگر حداکثر یک Pⁿ با ورودیهای غیر صفر وجود دارد)

از آنجایی که q مستقل از شرایط اولیه است، زمانی که بوسیلهٔ P ترجمه می‌شود، بایستی بدون تغییر بماند؛ که این باعث می‌شود که q تبدیل به بردار ویژه شود، به این معنی که از P مشتق شود. برای مثال آب و هوا:

${\begin{matrix}P&=&{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}\\\mathbf {q} P&=&\mathbf {q} &{\mbox{(}}\mathbf {q} {\mbox{ is unchanged by }}P{\mbox{.)}}\\&=&\mathbf {q} I\\\mathbf {q} (P-I)&=&\mathbf {0} \\&=&\mathbf {q} \left({\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}-{\begin{bmatrix}1&0\\0&1\end{bmatrix}}\right)\\&=&\mathbf {q} {\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}\end{matrix}}$ ${\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}{\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}={\begin{bmatrix}0&0\end{bmatrix}}$

پس $-0.1q_{1}+0.5q_{2}=0$ و از آنجایی که این دو بردار احتمال هستند، داریم $q_{1}+q_{2}=1$

حل این دو معادله یک توزیع حالت یکنواخت را می‌دهد:

${\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}={\begin{bmatrix}0.833&0.167\end{bmatrix}}$

در نتیجه %۸۳ روزها آفتابی است.

اکتبر 31, 2019/0 دیدگاه /توسط daliri

منطق فازی در هوش مصنوعی

هوش محاسباتی

مقدمه

منطق فازی شاید بیشترین امید به پیشرفت و شتاب در جامعه هوش مصنوعی در تاریخچه اخیر آن باشد. اما چرا بعضی واژه های نامعلوم به درستی پشت واژه « فازی» قرار می گیرند؟ چرا « فازی » موجب پیشرفت هوش مصنوعی می شود؟
پاسخ این سوالات در مقاله زیر داده شده است.

تاریخچه منطق فازی

Fuzzy logic یک نوع منطق است که روش های متنوع نتیجه گیری در مغزبشر را جایگزین الگوهای ساده تر ماشینی می کند. مفهوم منطق فازی نخستین بار درجهان، توسط دانشمند برجسته ایرانی، پروفسور لطفی زاده، پروفسور دانشگاه برکلی در کالیفرنیا در سال 1965 ارائه گردید و نه تنها به عنوان یک متدولوژی کنترل در حوزه هوش مصنوعی ارائه شد، بلکه راهی برای پردازش داده ها، بر مبنای مجاز کردن عضویت گروهی کوچک، به جای عضویت گروهی دسته ای، ارائه کرد.
به عبارتی پروفسورلطفی زاده اینطور استدلال کرد که مغز بشر به ورودی های اطلاعاتی دقیق نیازی ندارد، بلکه قادراست تا کنترل تطبیقی را به صورت بالایی انجام دهد و این در مورد ماشین نیز صادق است.

منطق فازی چیست؟

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

واژگانی از قبیل { کم ، زیاد، خیلی کم ، خیلی زیاد، قدری و … } این واژه ها واژه های زبان شناختی نام دارند، یعنی با مقادیر ریاضی نمی توان مقدار مشخصی را به آنها ربط داد.
اینجاست که منطق فازی وارد عمل می شود و با استفاده از مجموعه های فازی،برای متغیر میزان بارش باران، مجموعه ای را به شکل زیر صورت می دهد:
میزان بارش باران= { کم ، زیاد، خیلی کم ، خیلی زیاد، قدری و … }

باید پذیرفت قواعدی نظیر این زیبا هستند، زیرا این ها قواعد بشری هستند. آنها نمونه خوبی هستند برای اینکه ما چطورفکر می کنیم و چطور نتیجه می گیریم. بیایید به سراغ نمونه دیگری برویم:
ازشما سوال می شود” آیا شغلتان را دوست دارید؟” پاسخ شما لزوماً بله یا خیر نمی باشد؛ بنابراین مجموعه جواب به صورت زیر خواهد بود:
جواب= { تا حدی، نه خیلی، تقریباً، اصلاً ، کم و بیش، خیلی و… }
به هر یک از این مقادیر،مقداری به عنوان ” درجه عضویت” نسبت داده می شود، بدین معنا که مقدار مربوطه تا چه حد در این مجموعه عضو می باشد.

مجموعه های فازی و زبان طبیعی

لازم به ذکر است، در مجموعه های قطعی، یک شیء قطعاً ، یا عضو مجموعه، است یا نیست:

اگر xعضو مجموعه A باشد
اگر X عضو مجموعه A نباشد

اما در مجموعه های فازی، یک شیء می تواند تا حدودی به یک مجموعه متعلق باشد:

که در این حالت تابع عضویت، یک عدد حقیقی است:

بدین معنا که شیء مورد نظر به طور نسبی در یک مجموعه وجود دارد. همچنین مقدار جزئی تابع عضویت، درجه عضویت نامیده می شود.
از سوی دیگر در نظر داشته باشید: مفاهیم ومجموعه های فازی ،عموماً در زبان طبیعی بکار می روند نظیر:
” جان قد بلند است.”
” هوا گرم است.”

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

پایین	قدری	تقریباً
متوسط	کم	بین
بالا	زیاد	به مقدار زیاد
خیلی	بیشتر
اصلاً	بیشترین
کم و بیش	در حدود

دراین تئوری، عضویت اعضای مجموعه از طریق تابع U ( X) مشخص می شود که X نمایانگر یک عضو مشخص و U تابعی فازی است که درجه عضویت X در مجموعه مربوطه را تعیین می کند و مقدار آن بین صفر و یک است:

همچنین به عنوان یک مجموعه متناهی از عناصر، برای عبارت بلند قد می توان زیر مجموعه فازی ذیل را تعریف کرد:
{ ( 8،1 )، ( 1، 705 )، ( 1، 7 )، (875،65 )، ( 05، 6 )،( 0125، 55 )،(0 ، 5 )}= بلند قد
در این مجموعه فازی، علامت “، ” درجه عضویت را از اعداد مربوطه به قد افراد جدا می سازد.

متغیرهای زبانی

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

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

درعین حال متغیرهای زبانی می توانند از الحاق تشکیل شوند که هر کدام از uiها، عباتی تجزیه ناپذیر است. مانند ” تا حدی سرد “، که در مجموع به 4 دسته زیر تقسیم می شود:
عبارات اصلی: که به عنوان برچسب هایی برای مجموعه های فازی در نظر گرفته می شوند و مانند ” سرد” در عبارات بالا، یا عباراتی از قبیل : کوتاه، بلند و … که هر کدام تابع عضویت مخصوص خود را دارند.

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

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

اما چگونه منطق فازی به کار گرفته می شود؟

منطق فازی معمولاً از قوانین ” اگر و آنگاه” ( IF/THEN) استفاده می کند، اما این بررسی ،به صورت بررسی مقادیر خشک منطق کلاسیک نمی باشد، بلکه این بررسی توسط متغیرهای معنایی صورت می گیرد.این قوانین معمولاً به شکل زیر بیان می شود:
اگر( متغیر ) ( حالت ) است، آنگاه ( عملکرد ).

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

منطق کلاسیک

کاربرد هوش مصنوعی

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

قاعده Soft Computing

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

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

زمینه های کاربرد منطق فازی درهوش مصنوعی

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

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

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

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

نتیجه

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

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

منبع

اکتبر 28, 2019/0 دیدگاه /توسط daliri

الگوریتم کلونی مورچه ها قسمت 1

هوش محاسباتی

الگوریتم کلونی مورچه‌ها

الگوریتم کلونی مورچه ها یا ACO همان‌طور که می‌دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.

روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.

مقدمه

الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه‌ها دارای نوعی هوشمندی توده‌ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون (Pheromone) به جا می‌گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویت اند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می‌گذارند؛ و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:

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

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

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم کلونی مورچه‌ها برای حل این مسئله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار؛ و لذا با گذر زمان می‌تواند جواب را به طور زنده تغییر دهد؛ که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدأ بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعاً زیادی می‌برد:

روز۱۰۱۳*۷/۱ = S۱۰۱۶*۴۳۳/۲ = ms۱۰*۱۰۱۸*۴۳۳/۲ =!۲۰

با انجام یک الگوریتم برنامه سازی پویا برای این مسئله، زمان از مرتبه نمایی بدست می‌آید که آن هم مناسب نیست. البته الگوریتم‌های دیگری نیز ارائه شده ولی هیچ‌کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.

مسئله فروشنده دوره گرد

مزیتهای الگوریتم کلونی مورچه ها

<تبخیر شدن فرومون> و <احتمال-تصادف>به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.

کاربردهای الگوریتم کلونی مورچه ها

از کاربردهای الگوریتم کلونی مورچه ها می‌توان به بهینه کردن هر مسئله‌ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:

۱. مسیر یابی داخل شهری و بین شهری.

۲. مسیر یابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا.

۳. مسیر یابی شبکه‌های کامپیوتری. ۴-استفاده ازوب. ۵-استفاده ازACOدربهینه سازی شبکه‌های توزیع آب و…

الگوریتم

پروسهٔ پیدا کردن کوتاه‌ترین مسیر توسط مورچه‌ها، ویژگی‌های بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به تنهایی بی‌اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تأثیر زیادی روی کارایی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرایند تطبیقی است. از آنجا که رفتار هیچ‌کدام از مورچه‌ها معین نیست و تعدادی از مورچه‌ها همچنان مسیر طولانی‌تر را انتخاب می‌کنند، سیستم می‌تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر اینکه این پروسه قابل توسعه است و می‌تواند به اندازهٔ دلخواه بزرگ شود. همین ویژگی‌ها الهام بخش طراحی الگوریتم‌هایی شده‌اند که در مسائلی که نیازمند این ویژگی‌ها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد، الگوریتم ABC بود. چند نمونه دیگر از این الگوریتم‌ها عبارتند از: AntNet,ARA,PERA,AntHocNet.

انواع مختلف الگوریتم بهینه‌سازی مورچگان

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

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

۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاور ان به مقدار فرمون بیشینهمقدار دهی اولیه می‌شوند.

۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است.

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

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

منبع

انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.

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

الگوريتم کلونی مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

الگوريتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلونی مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلونی ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلونی است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلونی) و هوشمندي اجتماعي را روشن کنيم.

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

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

جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :

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

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

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

بهينه سازي مسائل به روش کلونی مورچه ها (ACO) :

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي( Statistical) مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

1-1

2-1

3-1

4-1

مزيت هاي ACO :

همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

کاربردهاي ACO :

از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :

1. مسير يابي داخل شهري و بين شهري
2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا

3. مسير يابي شبکه هاي کامپيوتري

مسير يابي شبکه هاي کامپيوتري با استفاده از ACO :

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلونی مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

منبع

الگوریتم کلونی مورچه ها قسمت 1
الگوریتم کلونی مورچه ها قسمت 2
الگوریتم کلونی مورچه ها قسمت 3

اکتبر 23, 2019/0 دیدگاه /توسط daliri

تشخیص هویت زیست سنجی و بیومتریک قسمت 4

تشخیص هویت زیست سنجی

چكيده

امروزه امنيت فناوري اطلاعات و قابليت ذخيره، انتقال و پردازش اطلاعات بدون هرگونه تغيير توسط كاربران غيرمجاز، بزرگترين چالش در عصر اطلاعات و ارتباطات به شمار مي رود. اين مسئله در مواردي همچون انتخابات، آزمون و بانكداري الكترونيك از اهميت به سزايي برخوردار است. استفاده از راهكاري كه ضمن فراهم نمودن كنترل هاي امنيتي مناسب بتواند از مداخله ساير عوامل خارجي، در دستكاري داده ها و دستبردهاي غيرمجاز به اطلاعات جلوگيري نمايد همواره به عنوان موضوعي مهم، مورد نظر كارشناسان امنيت اطلاعات است. به همين منظور، استفاده از فناوري هايي همچون زيست سنجی به طور جدي مد نظر قرار گرفته اند.
در اين مقاله سعي مي شود تا با بررسي ويژگي هاي مورد استفاده در فناوري زيست سنجی، ضمن بيان ضعف هايي كه ويژگي هاي زيست سنجشي فعلي با آن روبرو هستند، راهكاري اثربخش و كاربردي براي جلوگيري از نفوذ به سيستم ها از طريق فناوري زيست سنجی ارايه گردد.

1- مقدمه

يكي از اساسي ترين مسايل در خدمات الكترونيك و تأمين امنيت در فرآيندهاي الكترونيكي، جلوگيري از دسترسي غيرمجاز به داده ها و اطلاعات است كه اين دسترسي نامجاز معمولاً با اهدافي همچون نفوذ به سيستم ها، شنود غيرقانوني، وقفه در انتقال اطلاعات، تخريب، تغيير و حذف داده ها به منظور بي اعتبارسازي اطلاعات يا ايجاد خلل در ارايه خدمات الكترونيك صورت مي گيرد. بنابراين از آن جا كه چالش اصلي در خدمات الكترونيك و تأمين امنيت اطلاعات در شبكه هاي رايانه اي، اطمينان كافي از دسترسي فرد مجاز و در زمان هاي مجاز به اطلاعات است فرآيند تصديق هويت امن و روش هاي احراز آن از مهم ترين مسايل در برقراري امنيت به حساب مي آيد.
تاكنون روش ها و تجهيزات بسيار مختلفي براي بررسي و شناسايي هويت كاربران، پيشنهاد گرديده است كه در مراكز زيادي نيز مورد استفاده قرار گرفته اند اما متأسفانه هر كدام از اين روش ها داراي معايبي هستند كه موجب كاركرد نادرست آن ها شده است. از اين رو، انتخاب شيوه مناسبي كه علاوه بر احراز هويت كاربران در كوتاهترين زمان ممكن، بتواند امنيت لازم را در سيستم هاي الكترونيكي تضمين نمايد همواره به عنوان يك مسئله اساسي مطرح بوده است.
يكي از روش هايي كه با استفاده از آن سعي مي شود تا با احراز هويت كاربران و جلوگيري از دسترسي افراد نامجاز به داده ها، قابليت اطمينان به اطلاعات همچنان حفظ گردد، بهره گيري از فناوري زيست سنجی براي شناسايي كاربران در هنگام دسترسي به سيستم هاي اطلاعاتي مي باشد.

2- فناوري زيست سنجی

استفاده از خصوصيات فيزيولوژيكي يا رفتاري فرد و تحليل آن به منظور شناسايي آن فرد كه تحت عنوان فناوري زيست سنجی شناخته مي شود به نوع خاصي از روش هاي امنيتي گفته مي شود كه در آن براي كنترل دسترسي و برقراري امنيت، از خواص قابل اندازه گيري بدن انسان يا هر موجود زنده ديگري استفاده مي شود. همان گونه كه از كلمه زيست سنجی برمي آيد در اين روش با استفاده از الگوريتم هاي رياضي، برداشت هاي ثابت و يكتايي از اندام هاي بدن مي شود كه مي توان از آن به عنوان يك كلمه عبور يكسان و غيرقابل تغيير استفاده كرد. بنابراين در روش زيست سنجی، از ويژگي هاي فيزيولوژيكي يا رفتاري يك شخص براي شناسايي و تأييد خودكار هويت او در سيستم استفاده مي شود كه يا نيازمند تماس فيزيكي مستقيم شخص با يك پويشگر زيست سنجشي است (مانند اثر انگشت) و يا به تماس فيزيكي فرد با پويشگر نيازي نيست (مانند شكل صورت، اجزاي چهره، تن صدا و …).
معمولاً ويژگي هاي انسان ها براي آن كه بتواند در فناوري زيست سنجی مورد استفاده قرار گيرد، با 9 پارامتر مورد ارزيابي قرار مي گيرد كه عبارتند از:

* عموميت: هر شخص داراي آن ويژگي باشد.
* يكتايي: چه تعداد نمونه متفاوت را مي توان تفكيك كرد.
* دوام: معياري براي سنجش آن كه يك ويژگي، چه مدت عمر مي كند.
* قابليت ارزيابي: سهولت استفاده براي ارزيابي نمونه هاي متفاوت؛
* كارايي: دقت، سرعت و پايداري روش مورد استفاده؛
* مقبوليت: ميزان پذيرش تكنولوژي؛
* جايگزيني: سهولت در استفاده از جايگزيني؛
* تصديق هويت: در تصديق هويت، مشخصه يك فرد به پايگاه اطلاعات ارسال مي شود و هدف، بررسي آن به منظور تصديق هويت آن فرد مي باشد كه پاسخ سيستم، الزاماً مثبت يا منفي است.
* تشخيص هويت: در سيستم هاي تشخيص هويت، مشخصه زيست سنجی فرد به سيستم ارايه مي شود و سيستم با جستجوي پايگاه اطلاعات، مشخصات فرد را در صورت موجود بودن استخراج مي كند.

براي اين كه يك ويژگي بدن بتواند به عنوان يك وسيله اندازه گيري مطرح شود بايد شرايط خاصي داشته باشد، به عنوان مثال، بايد ثابت باشد. به همين خاطر نمي توان رنگ مو يا وزن را به عنوان يك خاصيت زيست سنجی در نظر گرفت زيرا به طور دايم در حال تغيير و تبديل هستند. در ضمن، خواص انتخاب شده مي بايست نشان دهنده يك انسان خاص بوده و همچنين به سهولت قابل دسترسي باشد يعني بررسي آن نياز به زحمت زيادي نداشته باشد.
به طور كلي، ويژگي هاي زيست سنجی را مي توان به 2 دسته تقسيم نمود:

1. خصوصيات وابسته به فيزيك انسان ها: اين دسته از ويژگي ها به مجموعه اي از خصوصيات همراه انسان اعم از اثر انگشت، عنبيه چشم، چهره، DNA و … اشاره دارد. اين ويژگي ها از بدو تولد انسان و گاهي قبل از تولد، شروع به شكل گيري نموده و تا آخر عمر، به طور ثابت و غيرقابل تغيير در بدن انسان باقي مي مانند.
2. خصوصيات رفتاري انسان ها: اين دسته از ويژگي ها در حقيقت، خصوصيات ناشي از رفتارهاي انسان هاست، همانند چگونگي راه رفتن، نحوه فشردن دكمه ها (مثلاً تلفن همراه) و … كه مي تواند بيانگر مشخصات يك انسان خاص باشد، مانند راه رفتن يك انسان كه گاهي با نگاه كردن آن از پشت سر مي توان تشخيص داد كه وي كدام شخص است.

3- مزاياي استفاده از سيستم هاي امنيتي زيست سنجی

با استفاده از روش هاي زيست سنجی مي توان تقريباً مطمئن شد همان كسي كه انتظارش مي رود، به امكانات و منابع دسترسي دارد. براي مثال، اثر انگشت، همواره يكتا و يكسان است و مشكلاتي مانند فراموش كردن رمز عبور يا گم كردن آن در اين روش وجود ندارد، سرعت بسيار بالايي دارد و براي كاربران عادي نياز به آموزش نمي باشد، امكان سرقت دستگاه هاي زيست سنجی نيز بسيار كم است يا در پاره اي از مواقع، صفر مي باشد. تمام اين مزايا باعث شده است كه امروزه براي تأمين امنيت اكثر سيستم هاي رايانه اي و مبتني بر شبكه، به طور گسترده اي از روش هاي زيست سنجی استفاده شود. البته سيستم هاي زيست سنجی داراي معايب خاص خودشان هستند اما به دليل مزاياي بسيار زيادي كه نسبت به روش هاي سنتي شناسايي افراد دارند، استفاده از آن ها روز به روز در حال افزايش است.

4- معايب استفاده از فناوري زيست سنجی

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

5- روش هاي تعيين هويت در فناوري زيست سنجی و بررسي نقاط ضعف آنها

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

يكي از ويژگي هاي زيست سنجشي كه معمولاً به صورت گسترده در هنگام شناسايي كاربران مورد استفاده قرار مي گيرد، اثر انگشت است كه از قديمي ترين و رايج ترين روش هاي تشخيص هويت نيز به شمار مي رود. پوست نوك انگشت ها داراي يكسري شيارها و خطوط برآمده اي است كه از يك طرف انگشت به طرف ديگر ادامه دارد و در مجموع به عنوان اثر انگشت شناخته مي شود. اين خطوط داراي يكسري نقاط مشخصي هستند كه به آن ها ويژگي يا مشخصه مي گويند. اين ويژگي ها شامل كمان ها، مارپيچ ها، حلقه ها، انتهاي لبه ها، انشعاب ها، نقطه ها (شيارهاي نزديك به لبه ها)، جزاير (دو انشعاب نزديك به هم)، تقاطع (نقطه تلاقي دو يا چند لبه) و منفذها مي باشند كه در نهايت، از الگوي ايجاد شده توسط آن ها براي تشخيص هويت افراد استفاده مي شود.

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

اولين استفاده از اثر انگشت در مسايل تشخيص هويت به حدود سال 1900 برمي گردد. در ابتدا براي تشخيص يك اثر انگشت از ديگري سعي در تطبيق خطوط آن بود كه به علت وجود خطاي انساني، معمولاً شامل خطاهايي در اين زمينه است. براي رفع اين مشكل، دستگاه هايي براي تشخيص اثر انگشت ايجاد شدند. از ابتدايي ترين اين دستگاه ها مي توان به دستگاه هاي حسگر اثر انگشت نوري اشاره كرد كه در حدود سال 1970 طراحي گرديدند كه بر اساس بازتابش داخلي كار مي كردند. به اين معني كه منبع نور، به سطح شيشه اي كه انگشت روي آن قرار داشت تابيده شده و بازتابش آن جذب مي شود. مقدار اين نور بازتابيده شده بستگي به عمق شيارهاي سطح پوست و بيشترين بازتابش، مربوط به سطح در تماس پوست با شيشه است. مزاياي اين طرح عبارتند از صرف زمان اندك براي شناسايي، مقاوم بودن در مقابل تداخل الكترواستاتيكي و قيمت ارزان علاوه بر وضوح خوب كه در مقابل معايبي همچون اندازه بزرگ دستگاه، امكان جعل بالا و پيچيدگي هاي به كار رفته، قرار دارند.

دستگاه هاي ديگري كه براي ثبت اثر انگشت طراحي گرديدند داراي حسگرهايي از نوع حالت جامد، مانند حسگر اثر انگشت گرمايي بودند. اين نوع حسگرها از تفاوت گرمايي بين شكاف ها و برآمدگي هاي اثر انگشت به عنوان پارامتري تعيين كننده استفاده مي كنند. بدين معني كه جاهايي از پوست دست (برآمدگي ها) كه در تماس با سطح حسگر مي باشند، تفاوت گرمايي را نسبت به نقاطي كه در تماس نيستند (شيارها) احساس مي كنند. مزاياي اين حسگر نيز حجم كم دستگاه، ارزان بودن و امكان يكپارچگي آن ها مي باشد كه البته معايبي چون توان مصرفي بالا، دقت پايين و تأثيرپذيري از دماي محيط را هم دارند.
از حدود سال 1997، استفاده از دانش MEMS در حسگرهاي اثر انگشت آغاز گرديد كه تاكنون چند نمونه از دستگاه هايي كه با اين نوع از حسگرها طراحي و ساخته شده اند روانه بازار گرديده اند كه آخرين نمونه آن ها در سال 2008 ارايه گرديد.در اين دستگاه ها از نوعي حسگر به نام حسگرهاي خازني استفاده شده است كه بر پايه تغييرات خازني كار مي كنند و شامل دو صفحه فلزي مي باشند كه نقش الكترودهاي خازن را دارند. براي ايجاد تغييرات خازني، يكي از صفحه ها بسته به نوع نياز، متحرك و ديگري ثابت است. صفحه متحرك كه ديافراگم ناميده مي شود بر اثر اعمال فشار خارجي جابه جا شده و باعث كم شدن فاصله هوايي بين الكترودهاي خازن گرديده و تغييرات خازني را موجب مي شود.

در حسگرهاي خازني مورد استفاده در حسگر اثر انگشت، صفحه بالايي به عنوان ديافراگم در نظر گرفته مي شود كه بر اثر فشار اعمالي بر اثر تماس با سطح پوست دست (برآمدگي هاي سطح پوست انگشت) جابه جا مي شود. از عوامل مؤثر در عملكرد حسگرهاي اثر انگشت MEMS مي توان مواردي همچون ابعاد ديافراگم، ساختار خازن، مواد تشكيل دهنده ديافراگم كه باعث حساسيت خيلي زياد حسگرها مي شود و همچنين اندازه، شكل و ضخامت ديافراگم را بيان نمود و از آن جا كه ساختار حسگر انگشت بر پايه ساختار اين خازن ها بنا نهاده شده است، با افزايش حساسيت مكانيكي و الكتريكي اين خازن ها، حساسيت حسگر اثر انگشت نيز بهبود پيدا مي كند.

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

از مهمترين مشكلاتي كه سيستم هاي ثبت اثر انگشت با آن مواجه هستند امكان جعل اثر انگشت توسط لايه هاي نازكي از ژلاتين يا خميرهاي سيليكن قابل جعل است. روشي كه مي توان اعتبار اين زيست سنجه را حفظ نمود، استفاده از چند اثر انگشت در هنگام احراز هويت يا اثر انگشت همراه با كارت شناسايي يا اثر انگشت به همراه رمز عبور مي باشد كه از آن ها به عنوان روش هاي شناسايي دو مرحله اي ياد مي شود. روش بهتر ديگري كه مي توان بدون استفاده از ساير تجهيزات جانبي با استفاده از زيست سنجه هاي اثر انگشت به احراز هويت كاربران پرداخت، بهره گيري از عرق و گرماي انگشت به عنوان نشانه هايي از حيات است كه امكان تقلب را كاهش مي دهد. همچنين با تعيين مدت زمان پويش اثر انگشت (مثلاً 2 ثانيه) مي توان از جا زدن افراد به جاي ديگري در اين مدت زمان كم جلوگيري نمود.

استفاده از روش هاي زيست سنجی در فرآيند تصديق هويت از طريق اثر انگشت، داراي چندين نقطه ضعف عمده مي باشد كه در زير به برخي از آن ها اشاره مي شود:

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

تاكنون تحقيق ها و پژوهش هاي بسياري براي جلوگيري از ورود ويژگي هاي زيست سنجی غيرواقعي و ساختگي پيشنهاد شده است كه تا حد قابل قبولي توانسته اند اين سيستم ها را امن نمايند. يكي از راه هايي كه براي غلبه بر ورودي هاي نامعتبر و جعلي در سيستم هاي تشخيص هويت بر پايه اثر انگشت وجود دارد، روش تشخيص زنده نام دارد. بدين معني كه از تأييد اثر انگشت ساختگي و مصنوعي توسط عرق كردن يا حرارتي كه روي انگشتان وجود دارد از نشانه هايي براي تازگي و زنده بودن انگشت استفاده مي شود كه اين ويژگي ها در انگشت مصنوعي يا ساير روش هاي جعل وجود ندارد.

* كيفيت پايين ورودي: تكنيك هاي تطابق اثر انگشت به 2 صورت ممكن است انجام گيرند: بر پايه جزييات يا بر اساس همبستگي. در تكنيك هاي ويژگي محور، ابتدا نقاط يا ويژگي ها مشخص مي شود و سپس محل نسبي آن روي انگشت نگاشت مي شود. زماني كه كيفيت پايين باشد استخراج دقيق نقاط ويژگي مشكل مي باشد.

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

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

يكي از روش هايي كه براي حفاظت نمونه ها از تقلب و جابه جايي وجود دارد استفاده از الگوريتم ها و كدهاي عددي به جاي مقايسه تصاوير، براي تحليل اطلاعات است يعني استفاده از نسخه تحريف شده سيگنال زيست سنجی يا بردار ويژگي است. همچنين واترماركينگ (واترماركينگ، استگانوگرافي يا نهان نگاري، دانش يا هنر پنهان كردن اطلاعات يا ارتباطات است به گونه اي كه يك پيام در بطن پيام ديگر مخفي مي شود. در اين صورت به پيامي كه قرار است مخفي شود، واترمارك و بهسيگنالي گفته مي شود) و پنهان سازي اطلاعات (Steganography ) از ديگر تكنيك هايي است كه براي افزايش امنيت تصاوير اثر انگشت موجود در پايگاه داده مورد استفاده قرار مي گيرد.

مشكلات عملي زيادي در سيستم هاي شناسايي اثر انگشت وجود دارد. مثلاً هر دفعه كه يك اثر انگشت گرفته مي شود، ممكن است به خاطر قابليت كشساني پوست، تحريف هايي در شكل و محل اثر انگشت ايجاد شود. علاوه بر اين، اطمينان بالا و پردازش بلادرنگ، فاكتورهاي مهم مورد نياز در سيستم خودكار شناسايي اثر انگشت هستند.

از ديگر روش هايي كه امروزه در فناوري زيست سنجی از آن استفاده مي شود انجام برخي از حركات يا رفتارهاي خاص بر روي تجهيزات جمع آوري كننده اطلاعات مي باشد. از نمونه هاي اين روش مي توان به دستگاه هايي اشاره كرد كه از كاربر مي خواهد تا با دست خويش، عمل خاصي را انجام داده يا شكل مشخصي را در صفحه ثبت كننده اطلاعات، ترسيم نمايد. اندازه گيري و ثبت ويژگي هايي همچون اندازه، طول، سرعت، شتاب، انحنا، ميزان فشار وارده، دامنه لرزش اعضاي حركتي بدن، درجه حرارت بدن و … و مقايسه آن ها با اطلاعات از قبل ثبت شده، از كاركردهاي اين دستگاه ها مي باشد. از مشكلات خاص اين روش نيز مي توان به عدم بهره گيري از آن ها در هنگام بيماري افراد در روش ايي كه نيازمند انجام حركات رفتاري خاص هستند يا آموختن بعضي از روش هاي اجرايي حركات و رفتارها اشاره نمود.

يكي ديگر از روش هاي زيست سنجی، تأييد هويت افراد بر اساس كف دست آن ها مي باشد. در اين روش، كف دست به صورت كامل بر روي دستگاه هاي جمع آوري كننده داده ها قرار گرفته و اطلاعات خاصي از آن استخراج مي شود. اين شيوه نيز با مشكلاتي مشابه روش زيست سنجشي اثر انگشت روبرو مي باشد كه مي توان با استفاده از درجه حرارت و رطوبت كف دست كاربر و همچنين شدت فشار آن بر روي صفحه دستگاه، صحت اطلاعات دريافتي را بررسي نمود.
هندسه دست نيز يكي ديگر از روش هاي مورد استفاده در فناوري زيست سنجی است كه مي تواند با مشكلات مربوط به ويژگي زيست سنجی كف دست مواجه گردد كه به كارگيري ويژگي هاي تشخيصي، مي تواند خطاهاي وارده را كاهش دهد.
استفاده از عنبيه چشم در تأييد هويت كاربران، يكي ديگر از روش هاي مورد استفاده در فناوري زيست سنجی مي باشد. مشكلاتي همچون نور كم محيط در هنگام تأييد عنبيه چشم مي تواند باعث تار بودن تصوير شده و در كاهش عملكرد اين روش تأثير بگذارد.
در روش تأييد هويت بر اساس تشخيص چهره كه از شيوه هاي ديگر فناوري زيست سنجی مي باشد افراد مي توانند تصويز يا ويديوهاي جعلي را در مقابل دوربين قرار داده و موجب عدم كارايي اين روش گردند.
نرم افزارهاي مورد استفاده در فناوري زيست سنجی نيز بايد علاوه بر سهولت كاربري و واسط گرافيكي پيشرفته، اثرهاي زيست سنجی جمع آوري شده را به صورت امن ذخيره كرده و قادر به گزارش هاي متنوع و همچنين ثبت خطاها و رويدادها باشد. تجهيزات و دستگاه هاي جمع آوري داده هاي زيست سنجی هم بايد داده هاي دريافتي را به صورت امن ارسال كرده و از روش هاي رمزنگاري قابل اطمينان در طول فرآيند انتقال داده ها استفاده نمايند. همچنين پايگاه هاي داده اي كه اطلاعات زيست سنجی در آن ذخيره مي گردد بايد اطلاعات را به صورت رمزگذاري شده نگهداري نموده و از تكنيك هاي ويژه اي همچون سايه زني و مخفي سازي داده ها بر روي تصاوير و يا الگوريتم هاي رمزنگاري پيشرفته، به منظور تأمين امنيت بيشتر و چلوگيري از تحريف داده ها استفاده نمايند.
امروزه وسايل و تجهيزات زيست سنجی خاصي براي انواع مختلفي از خدمات الكترونيك ابداع شده اند كه در آن ها، تصديق هويت با استفاده از يك عامل امنيتي هوشمند انجام مي شود كه اين عامل هوشمند داراي خاصيت تشخيص زنده بودن فرد است. لازم است كه اين عامل در فعاليت هاي زيست سنجی كه از راه دور انجام مي گيرند به هر فرد يك شناسه به همراه آدرس IP اختصاص دهد به گونه اي كه فرد ديگري قادر به استفاده از آن ها توسط رايانه ديگري نباشد.

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

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

منبع

تشخیص هویت زیست سنجی و بیومتریک قسمت 1
تشخیص هویت زیست سنجی و بیومتریک قسمت 2
تشخیص هویت زیست سنجی و بیومتریک قسمت 3
تشخیص هویت زیست سنجی و بیومتریک قسمت 4
تشخیص هویت زیست سنجی و بیومتریک قسمت 5

اکتبر 22, 2019/0 دیدگاه /توسط daliri