(3-18)

 

 

 

 

در این فرمول، تابع مقدار اطلاعات متقابل بین یک گره در یک شبکه بیزین و والدهای آن متغیر را بر می گرداند. سطح significance را برای توزیع Chi-square مشخص می کند.
3-3-3- پیچیدگی زمانی یادگیری شبکه های بیزین دینامیک
اگر یال هایی که روابط متغیرها را در یک گام زمانی نشان می دهند در نظر نگیریم و ساختار یک شبکه بیزین دینامیک را به یال هایی که روابط متغیرها در گام های زمانی مختلف نشان می دهند محدود کنیم، برای متغیر، تعداد شبکه بیزین دینامیک یکتا می توان ایجاد کرد. در واقع تعداد شبکه های بیزین دینامیکی که با متغیر می توان ساخت، به صورت فرانمایی[28] با رشد می کند. برای مثال، برای تنها 10 متغیر بیش از شبکه بیزین دینامیک مختلف وجود دارد. چنین فضایی باعث می شود که حتی برای مسائلی با تعداد متغیر کم، پیدا کردن بهترین شبکه امکان پذیر نباشد. به عنوان راه حلی برای این مشکل، معمولاً از روش های جستجوی محلی[29] برای پیدا کردن شبکه ای با امتیاز بیشینه محلی استفاده می شود. روش های جستجوی محلی که برای این منظور استفاده می شوند عبارتند از: Greedy Search، Simulated annealing، Hill climbing و روش های جستجو بر اساس الگوریتم ژنتیک.
با وجود اینکه تعداد شبکه های بیزین دینامیک برای متغیر برابر است، اگر تابعی که برای امتیازدهی شبکه ها استفاده می شود خاصیت ویژه ای را با عنوان تفکیک پذیری[30] دارا باشد، این امکان فراهم می شود که بتوان بهترین شبکه را با جستجو در فضایی بسیار کوچک تر پیدا کرد. یک تابع امتیازدهی زمانی تفکیک پذیر است که شرط زیر را ارضا کند:

 

منبع فایل کامل این پایان نامه این سایت pipaf.ir است

 

 

 

 

 

 

 

 

 

(3-19)

 

با توجه به فرمول (3-19)، یک تابع امتیازدهی زمانی تفکیک پذیر است که امتیازی که به یک شبکه اختصاص می دهد را بتوان به صورت حاصل جمع مقادیری بیان کرد که هر کدام فقط به یکی از متغیرها و والدهای آن متغیر وابسته است. در چنین حالتی، بهترین مجموعه والدها برای یک متغیر از ساختار باقی شبکه مستقل است و می توان والدهای هر متغیر را به صورت مجزا پیدا کرد. در اینجا باید اشاره شود که تمامی توابع امتیازدهی که در بخش (3-3) معرفی شدند توابع امتیازدهی تفکیک پذیر هستند و می توان مقدار نهایی امتیازی را که هر یک از آن ها به یک شبکه اختصاص می دهند به صورت مجموع امتیازاتی که به گره های شبکه اختصاص می دهند در نظر گرفت.
اگر فرض شود که تابع امتیازدهی تفکیک پذیر است، فضای جستجو برای پیدا کردن بهترین شبکه بدین صورت تعیین می شود: برای انتخاب مجموعه والدها هر یک از متغیرمسئله حالت وجود دارد. اما بدلیل اینکه این امکان وجود دارد که والدهای هر متغیر را به صورت مستقل پیدا کنیم، کل فضای جستجو برابر با می شود. در واقع، تفکیک پذیری تابع امتیاز دهی، فضای جستجو را از فضایی شامل حالت به فضایی شامل حالت کاهش می دهد. در این صورت، برای یافتن بهترین شبکه در مسئله ای با 10 متغیر، تعدادی حدود حالت باید بررسی شود.
با وجود اینکه استفاده از توابع امتیازدهی تفکیک پذیر فضای جستجو را برای شبکه با بالاترین امتیاز به شدت کوچک می کند، این فضا هنوز بصورت نمایی با تعداد متغیرها رشد می کند. اما این امکان وجود دارد که با اعمال محدودیت های بیشتر بر روی ساختار شبکه، فضای مسئله را باز هم کوچک تر کرد. یکی از متداول ترین محدودیت هایی که بر روی ساختار شبکه اعمال می شود محدود کردن تعداد والد گره ها در شبکه است. در این حالت، اگر فرض شود تعداد والدها برای هر گره شبکه حداکثر می تواند باشد، تعداد حالات برای انتخاب والدهای هر گره برابر می شود با . بنابر این، با فرض تفکیک پذیری تابع امتیازدهی، تعداد حالات فضای جستجو برابر می شود با: . با اشاره به مثال قبلی، برای شبکه ای با 10 متغیر و محدودیت سه برای تعداد والدهای هر گره، تعداد حالات فضای جستجو برابر با 1760 حالت خواهد بود. برای مقادیر ، داریم: . در این حالت، بزرگی فضای جستجو برابر است با: .
شکل (3-2) قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک را به وسیله روش های جستجو و امتیاز دهی ارائه می دهد.

 

 

 

 

 

 

 

 

 

 

 

 

–

شکل 3-2- قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک

 

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

 

 

 

 

 

 

 

 

yle="box-sizing: inherit; width: 1104px;">