شبکه‌های بیزی
یک شبکهٔ بیزی یا «شبکه باور» یا «شبکه باور بیزی» (به انگلیسی: Bayesian network) یک گراف جهت‌دار غیرمدور است که مجموعهای از متغیرهای تصادفی و نحوه ارتباط مستقل آن‌ها را نشان می‌دهد. به عنوان نمونه یک شبکه بیزی می‌تواند نشان دهنده ارتباط بین بیماری‌ها و علائم آن‌ها باشد. پس با داشتن علائم باید بتوان احتمال یک بیماری خاص را در یک بیمار تشخیص داد.
شبکه بیزین یک ابزار نسبتاً جدید برای شناسایی (هویت) روابط احتمالی به منظور پیشگویی یا ارزیابی کلاس عضویت است.[۱]
به‌طور خلاصه می‌توان گفت شبکه بیزین، نمایش بامعنی روابط نامشخص ما بین پارامترها در یک حوزه می‌باشد. شبکه بیزین گراف جهت دار غیر حلقوی از نودها برای نمایش متغیرهای تصادفی و کمانها برای نمایش روابط احتمالی مابین متغیرها به‌شمار می‌رود.
خصوصیات
[ویرایش]شبکه‌های بیزی در زمینه استدلال احتمالی به‌طور گسترده مورد استفاده قرار می‌گیرند و به درخت متصل بر روی احتمالات استدلال شده تبدیل می‌شوند. شبکه‌های بیزین به تجزیه زیرگراف اصلی ماکزیمم درخت متصل تبدیل می‌شوند و بیشتر از درخت‌های متصل کاربرد دارند. شبکه بیزین عموماً به صورت آشکار با مقادیر اولیه قابل قبول و روابط ما بین متغیرها توزیع می‌شود. در مسائل دنیای واقعی بسیار کاربرد دارند. در چندین سال پیش شبکه‌های بیزین توسط افراد مورد توجه قرار گرفتند و به عنوان گروه‌های زیست‌شناسی در روشهای شبکه‌های ژنی توسط افرادی به کار گرفته شدند. شبکه بیزین یک مدل گرافیکی برای نمایش احتمالات مابین متغیرهای موردنظر می‌باشد. از طرفی شبکه‌های بیزین روشی برای نمایش توزیع احتمالی پیوسته بزرگ به صورت نمایی و روش فشرده می‌باشند که اجازه محاسبات احتمالی به‌طور مؤثر را می‌دهند. آن‌ها از ساختار مدل گرافیکی برای ضوابط مستقل مابین متغیرهای تصادفی استفاده می‌کنند. شبکه‌های بیزین اغلب برای شرایط مدل احتمالی استفاده می‌شوند و به استدلالهای تحت شرایط نامشخص (احتمالی، عدم قطعیت) کمک می‌کنند. این شبکه شامل بخش کیفی (مدل ساختاری) است که نمایش بصری از فعل و انفعالات در میان متغیرها و بخش کمی (مجموعهای از مشخصات احتمال محلی) را فراهم می‌کند، که مجاز به استنتاج احتمالات و اندازه‌گیری عددی است که متغیرها یا مجموعهای از متغیرها را تحت تأثیر قرار می‌دهد. بخش کیفی به صورت توزیع احتمالی پیوسته که منحصربه‌فرد می‌باشد بر روی کلیه متغیرها تعریف می‌شود.
جملات مستقل
[ویرایش]فقدان یال‌ها در شبکه بیزین نشانگرمتغیرهای مستقل از هم می‌باشد. رمزگذاری شبکه بیزین مطابق با جملات مستقل در هر متغیر تصادفی است. یک متغیر مستقل به صورت صعودی وضعیت والدین شبکه را نشان می‌دهد. همچنین شبکه بیزین برای نمایش توزیع احتمالی ویژه و اتصال توزیع بر روی همه متغیرها به صورت نودها در گراف نمایش داده می‌شود. این توزیع با یک مجموعه از جدول احتمال شرطی مشخص می‌شود. هر نود به جدول احتمال شرطی منتسب شده و توسط اطلاعات احتمالی کمی مشخص می‌گردد. همانند جدولی احتمالات در وضعیت ممکن از نود در ترکیب ممکن از والدینش مشخص می‌گردد. برای نودهای بدون والد احتمالات بر روی نودهای دیگر بدون قید و شرط می‌باشند که این نودها احتمالات اولیه بر روی متغیرها نامیده می‌شوند.
ساختار
[ویرایش]به عبارت دیگر یک شبکه بیزین گراف جهت دار غیر حلقوی است و شامل موارد زیر می‌باشد:
- گره‌ها (دوایر کوچک): برای نمایش متغیرهای تصادفی
- کمانها (پیکانهای نوک تیز) برای نمایش روابط احتمالی ما بین متغیرها
برای هر نود توزیع احتمال محلی وجود دارد که به نود وابسته‌است و از وضعیت والدین مستقل می‌باشد.[۱]
مثال
[ویرایش]دو رویداد می‌تواند باعث مرطوب شدن چمن شود: یک آبپاش فعال یا باران. باران تأثیر مستقیمی در استفاده از آب پاش دارد (یعنی وقتی باران می‌بارد، آبپاش معمولاً فعال نیست). این وضعیت را می‌توان با یک شبکه بیزی مدل‌سازی کرد (در سمت راست نشان داده شده). هر متغیر دارای دو مقدار ممکن است T (برای true) و F (برای false).
دو رویداد می‌تواند باعث مرطوب شدن چمن شود: یک آبپاش فعال یا باران. باران تأثیر مستقیمی در استفاده از آب پاش دارد (یعنی وقتی باران می‌بارد، آبپاش معمولاً فعال نیست). این وضعیت را می‌توان با یک شبکه بیزی مدل‌سازی کرد (در سمت راست نشان داده شده). هر متغیر دارای دو مقدار ممکن است T (برای true) و F (برای false).
به طوریکه
G = "Grass wet (true/false)", S = "Sprinkler turned on (true/false)", and R = "Raining (true/false)".
این مدل می‌تواند با توجه به وجود معلولی (اصطلاحاً معکوس) مانند "احتمال باران آمدن با توجه به مرطوب بودن علف چقدر است؟" به سوالات مربوط به وجود علت پاسخ دهد. با استفاده از فرمول احتمال شرطی و جمع‌بندی تمام متغیرهای مزاحم:
با استفاده از بسط تابع احتمال مشترک و احتمالات مشروط از جداول احتمال شرطی (CPT) که در نمودار بیان شده‌است، می‌توان هر عبارت را در مجموعهای موجود در صورت و مخرج را ارزیابی کرد؛ مثلاً،
سپس نتایج عددی (مشتق شده توسط مقادیر متغیر مرتبط) چنین هستند
استنتاج و یادگیری در شبکه‌های بیزی
[ویرایش]در شبکه‌های بیزی، استنتاج به سه روش عمده زیر انجام می‌شود:
استنتاج متغیرهای مشاهده‌نشده
[ویرایش]به دلیل اینکه هر شبکه بیزی یک مدل کامل برای متغیرهای خود و روابط بین آن‌هاست، می‌تواند برای پاسخ دادن به پرس‌وجوهای احتمالاتی دربارهٔ متغیرها مورد استفاده قرار گیرد. برای مثال، شبکه بیزی می‌تواند برای به‌روزرسانی اطلاعات ما راجع‌به زیرمجموعه‌ای از متغیرها زمانی که برخی از متغیرهای دیگر مشاهده شده‌اند (متغیرهای گواه) استفاده شود. به این فرایند، استنتاج تصادفی گفته می‌شود. شبکه‌های بیزی سازوکاری برای اعمال خودکار قضیه بیز در مسائل پیچیده تلقی می‌شوند.
از مهم‌ترین روشهای استنتاج قطعی می‌توان به: حذف متغیرها (که متغیرهای مشاهده نشده و پرس‌وجو نشده را با استفاده از جمع کردن تک تک آن‌ها در توزیع نهایی حذف می‌کند)، الگوریتم درخت اتصال (که در آن محاسبات طوری نگه داشته می‌شوند که بتوان دربارهٔ چند متغیر در آن واحد پرس‌وجو کرد و متغیرهای گواه با سرعت بیشتری در آن انتشار یابند)، و شروط بازگشتی و جست‌وجوی AND/OR (که امکان وجود مبادله حافظه-زمان را فراهم می‌کند)، اشاره کرد. همه این روش‌ها دارای پیچیدگی زمانی متناسب با عرض درخت هستند.
یادگیری پارامترها
[ویرایش]برای معین‌کردن کامل یک شبکه بیزی و در نتیجه نمایش کامل توزیع‌های احتمال توأم شبکه، باید توزیع احتمالاتی شرطی برای هر گره X برحسب والدین X تغیین شود. این توزیع شرطی می‌تواند شکل‌های مختلفی داشته باشد، که شایع‌ترین آن‌ها به دلیل ساده‌سازی محسابات توزیع‌های گسسته و توزیع‌های گوسی هستند. گاهی تنها محدودیت‌های توزیع‌های احتمالاتی شناخته شده‌اند؛ در این شرایط می‌توان از اصل حداکثر انتروپی برای محاسبه توزیعی که بیشترین انتروپی با فرض محدودیت‌های مسئله را دارد، استفاده کرد.
این توزیع‌های شرطی معمولاً شامل پارامترهایی هستند که ناشناخته‌اند و باید با استفاده از روش برآورد درست‌نمایی بیشینه تخمین زده شوند. بیشینه‌سازی مستقیم احتمال رخداد (یا احتمال پسین) معمولاً پیچیده‌است، یک روش قدیمی برای حل این مشکل استفاده از الگوریتم امید ریاضی–بیشینه کردن است، که به جای محاسبه مقادیر امید ریاضی متغیرهای مشاهده‌نشده به ازای مقادیر مشاهده‌شده، از بیشینه‌سازی احتمال کامل (احتمال پسین) با فرض صحیح بودن مقادیر محاسبه شده پیشین امید ریاضی استفاده می‌کند. در شرایطی که منظم‌بودن اندک است، این سازوکار به مقادیر احتمال بیشینه پارامترها همگرا می‌شود.
روش دیگری که مبتنی بر رویکرد بیزی نسبت به پارامترها است، در نظر گرفتن آن‌ها به عنوان متغیرهای مشاهده‌نشده دیگر و محاسبه کامل توزیع احتمالات پسین روی همه گره‌ها، و سپس جمع‌کردن پارامترهاست. این روش می‌تواند هزینه‌بر باشد و باعث ایجاد مدل‌هایی با ابعاد بالا شود.
یادگیری ساختار
[ویرایش]در نمونه‌های ساده، یک شبکه بیزی توسط یک کارشناس تعیین می‌شود سپس عملیات استنتاج روی آن صورت می‌گیرد. در کاربردهای دیگر، عملیات تعیین شبکه بیزی برای انسان بسیار پیچیده‌است. در این موارد، ساختار شبکه و پارامترهای توزیع احتمال موضعی باید از روی داده‌ها آموخته شوند.
یادگیری خودکار ساختار یک شبکه بیزی چالشی است که در یادگیری ماشین به آن پرداخته می‌شود. ایده اصلی، به الگوریتم بازیابی طراحی شده توسط رِبِین (اینگلیسی: Rebane) و یودیا پیرل (اینگلیسی: Pearl)[۲] بازمی‌گردد و بر پایه تفاوت بین سه الگوی مختلف قرارگیری مجاز سه گره در یک گراف بدون حلقه (DAG) است:
| الگو | مدل |
|---|---|
| زنجیر | |
| شاخه | |
| برخورددهنده |
که در آن دو الگوی اول وابستگی‌های یکسانی را نمایش می‌دهند ( و با دانستن مستقل‌اند) و درنتیجه غیرقابل‌تمایز هستند. اما الگوی برخورددهنده را می‌توان به‌طور منحصربه‌فرد شناسایی کرد، زیرا و به صورت حاشیه‌ای مستقل‌اند و بقیه زوج‌ها وابسته هستند. در نتیجه با اینکه اسکلت (گراف‌ها بدون در نظر گرفتن جهت یال‌ها) هر سه حالت یکسان است، جهت‌گیری یال‌ها تاحدی قابل تشخیص است. همین تمایز زمانی که و والدین مشتر دارند صحیح است، با این تفاوت که والدین باید ابتدا مشروط شوند. الگوریتم‌هایی برای تعیین سیستماتیک اسکلت گراف، و سپس تعیین جهت یال‌هایی که جهت آن‌ها توسط استقلال شرطی متغیر مشخص می‌شود، طراحی شده‌اند.[۳][۴][۵][۶]
روش دیگری برای یادگیری ساختار شبکه بیزی، استفاده از جست‌وجوهای بر پایه بهینه‌سازی است. این الگوریتم‌ها به تابع امتیازدهی و سیاست جست‌وجو نیاز دارند. یک تابع امتیازدهی متداول، احتمال پسین ساختار با توجه به داده‌های مشاهده‌شده مانند BIC و BDeu است. پیچیدگی زمانی یک جستجوی بروت-فورس که امتیاز را بیشینه می‌کند نسبت به تعداد متغیرها فوق نمایی است. سیاست جستجوی موضعی تغییرات تدریجی در ساختار در جهت بهبود امتیاز ایجاد می‌کند. سیاست جستجوی سراسری مانند Markov chain Monte Carlo می‌تواند از گیر افتادن الگوریتم در کمینه‌های موضعی جلوگیری کند. فریدمن (اینگلیسی: Friedman)[۷][۸] ایده استفاده از اطلاعات مشترک متغیرها و یافتن ساختاری که آن را بیشینه کند را مطرح می‌کند. این کار با محدود کردن والدین کاندیدا برای هر گره به k گره و سپس استفاده از جستجوی بروت-فورس انجام می‌شود.
یک روش بسیار سریع برای یادگیری دقیق شبکه بیزی، تبدیل مسئله به یک مسئله بهینه‌سازی و سپس حل کردن آن به کمک روش بهینه‌سازی خطی عدد صحیح است. شرط بدون دور بودن به صورت روش Cutting Plane به مسئله بهینه‌سازی خطی عدد صحیح اضافه می‌شود.[۹] این روش می‌تواند برای مسائل با بیش از ۱۰۰ متغیر به خوبی عمل کند.
برای حل مسائلی با بیش از ۱۰۰۰ متغیر، به روشهای دیگری نیاز داریم. یکی از روش‌ها نمونه‌برداری یک ترتیب و سپس یافتن شبکه بیزین بهینه با توجه به آن ترتیب است. سپس روی فضای جستجوی ترتیب، جستجو انجام می‌شود که به دلیل کوچک‌تر بودن این فضای جستجو نسبت به فضای جستجوی ساختار گراف، سرعت الگوریتم افزایش قابل توجهی می‌یابد.[۱۰]
روش دیگر، شامل تمرکزکردن روی زیردسته‌های مدل‌های قابل‌تجزیه است که در آن‌ها برآورد درست‌نمایی بیشینه فرم بسته دارد. در این روش امکان یافتن یک ساختار که با صدها متغیر سازگار است، وجود دارد.[۱۱]
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- ↑ ۱٫۰ ۱٫۱ ((بررسی روشهای مربوط به شبکه‌های بیزین و کاربردهای آن
- ↑ Rebane G, Pearl J (1987). "The Recovery of Causal Poly-trees from Statistical Data". Proceedings, 3rd Workshop on Uncertainty in AI. Seattle, WA. pp. 222–228. arXiv:1304.2736.
- ↑ Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 978-0-521-77362-1. OCLC 42291253.
- ↑ Spirtes P, Glymour C (1991). "An algorithm for fast recovery of sparse causal graphs". Social Science Computer Review. 9 (1): 62–72. doi:10.1177/089443939100900106. S2CID 38398322. Archived from the original (PDF) on 16 April 2016. Retrieved 1 February 2023.
- ↑ Spirtes, Peter; Glymour, Clark N.; Scheines, Richard (1993). Causation, Prediction, and Search (1st ed.). Springer-Verlag. ISBN 978-0-387-97979-3.
- ↑ Verma T, Pearl J (1991). "Equivalence and synthesis of causal models". In Bonissone P, Henrion M, Kanal LN, Lemmer JF (eds.). UAI '90 Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. Elsevier. pp. 255–270. ISBN 0-444-89264-8.
- ↑ Friedman, Nir; Geiger, Dan; Goldszmidt, Moises (November 1997). "Bayesian Network Classifiers". Machine Learning. 29 (2–3): 131–163. doi:10.1023/A:1007465528199.
- ↑ Friedman N, Linial M, Nachman I, Pe'er D (August 2000). "Using Bayesian networks to analyze expression data". Journal of Computational Biology. 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139. doi:10.1089/106652700750050961. PMID 11108481.
- ↑ Cussens, James (2011). "Bayesian network learning with cutting planes" (PDF). Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence: 153–160. arXiv:1202.3713. Bibcode:2012arXiv1202.3713C.
- ↑ Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). "Learning Bayesian Networks with Thousands of Variables". NIPS-15: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates. pp. 1855–1863.
- ↑ Petitjean F, Webb GI, Nicholson AE (2013). Scaling log-linear analysis to high-dimensional data (PDF). International Conference on Data Mining. Dallas, TX, USA: IEEE.
Timo Koski, John M. Noble, Bayesian Networks An Introduction.