شبکه‌های بیزی (BNs) در چند دهه اخیر به عنوان ابزاری برای استدلال در شرایط عدم قطعیت در زمینه‌های متنوعی مانند پزشکی، زیست‌شناسی، اقتصاد و علوم اجتماعی به طور فزاینده‌ای محبوب شده‌اند. ساخت شبکه بیزی یک چالش بزرگ بوده که راه‌حل آن، ساخت شبکه بیزی به صورت خودکار و براساس داده‌ها یا دانش‌های قبلی و یا ترکیبی از هردو آن‌ها است.
*** در این مطلب تنها با بخشی از پیش‌نیاز‌های موجود در مقاله آشنا می‌شویم و برای آشنایی با هر یک از الگوریتم‌های ساخت شبکه بیزی می‌توانید به مقاله رجوع کنید.
شبکه بیزی: یک مدل گرافی احتمالی است که برای مدل‌سازی سامانه‌های غیرقطعی پیچیده استفاده می‌شود. با استفاده از این گراف، روابط وابستگی موجود بین متغیرها نشان داده می‌شود.
DAG: یک شبکه بیزی فاقد دور جهت‌دار است. شکل زیر یک DAG است:
A→B نشان‌دهنده وجود یک رابطه مستقیم بین A و B است یا به صورت علّی می‌توان گفت که A علتی مستقیم برای B است. یا به عبارت دیگر A والد B است.
یک گره با چندین والد را گره collider می‌نامند. در شکل بالا گره Cancer یک collider است و از آن‌جایی که بین گره‌های Smoker و Pollution هیچ یالی وجود ندارد، آن را v-structure یا unshielded collider می‌نامند.
مدل‌های گرافی احتمالی استقلال شرطی را از طریق مفهوم جداسازی گرافی که آن‌را d-seperation می‌نامند، نشان می‌دهند. برای مثال cancer یک جداکننده برای Xray و Smoker است.
d-seperation: اگر X و Y گره‌های یک DAG باشند، زیرمجموعه گره‌های باقی مانده، S، یک d-seperation است برای X از Y اگر S تمام مسیرهای بین X و Y را مسدود کند. هر مسیر بین X و Y توسط S مسدود می شود اگر حداقل یکی از گره‌های بین X و Y در آن مسیر، یکی از شرایط زیر را داشته باشد:
- یک collider است و نه خودش و نه هیچ یک از فرزندانش در S نیستند.
- یک collider نیست و در S است.
اگر S یک d-seperation برای X و Y باشد آنگاه S را Sepset ،cut-set یا separating set می‌نامند.
شکل زیر، چهار مثال از اعمال قوانین d-seperation را برای بررسی اینکه آیا X و Y از هم جدا شده‌اند یا نه، ارائه می دهد، که در آن مسیرهایی که مسدود نیستند به عنوان مسیرهای فعال شناخته و با فلش‌های سبز نشان داده می‌شوند و مجموعه‌های شرطی که حداقل هستند، صورتی و در غیر این صورت، خاکستری هستند:
Markov Equivalence Class: شامل تمام DAGهایی است که روابط استقلال شرطی یکسانی دارند.
نماد “⟂” به معنای “مستقل از” است.
ساخت شبکه بیزی شامل دو مرحله زیر است که با استفاده از داده‌ها یا دانش‌های قبلی و یا ترکیبی از هردو آن‌ها، انجام می‌گیرد:
- ایجاد ساختار گراف
- تعیین پارامترهای 𝚯
یادگیری ساختار شبکه بیزی یک مساله NP-hard است. و در این مقاله فقط به مرحله ایجاد ساختار گراف پرداخته می‌شود.
الگوریتم‌های یادگیری ساختار به دو دسته زیر تقسیم می‌شوند:
- constraint-based: در این دسته، یال‌ها بر اساس یک سری آزمون‌های استقلال شرطی (CI) حذف و جهت‌دهی می‌شوند.
- score-based: در این دسته هدف جستجو در نمودارهای مختلف با حداکثر کردن یک تابع هدف است.
دسته دیگر از روش‌های یادگیری ساختار، ترکیبی از دو دسته نام برده شده هستند.
تست‌های CI
تست‌های CI بررسی می‌کنند که آیا دو گره A و B تحت مجموعه S={s1,s2,…sq} مستقل هستند یا نه(آیا S برای A و B یک sepset است یا نه).
معروف‌ترین تست‌های CI:
- G2
- X2
- MI
- Z
Kitson N. K. , Constantinou A. C. , Guo Z. , Liu Y. , and Chobtham K. , “A survey of bayesian network structure learning,” Artificial Intelligence Review, vol.56, no.8, pp.8721–8814, 2023