60
65

The out-degrees of the nodes

شکل 3-6- شبه کد الگوریتم ارائه شده برای یاد گیری شبکه های بیزین دینامیک با ساختار scale-free با استفاده از روش جستجوی حریصانه

پیچیدگی محاسباتی الگوریتم تغییر یافته چنین محاسبه می شود: مسئله اصلی به حل مسئله بیشینه سازی تقسیم می شود. در هر مسئله، بهترین مجموعه والدها برای هر یک از گره پیدا می شود. برای پیدا کردن بهترین والدها برای هر گره، تنها (به طور تقریبی) مجموعه مختلف بررسی می شوند (یادآوری می شود که بیشینه تعداد والدها برای هر گره است)، که به این دلیل است که برای پیدا کردن بهترین مجموعه والدها با طول دو، تنها مجموعه هایی بررسی می شوند که شامل بهترین تک والد برای آن گره باشند. بنابر این تنها کافی است تا تعداد مجموعه بررسی شوند. این مجموعه از ترکیب بهترین تک والد برای آن گره و هر یک ازگره باقیمانده بدست می آیند. این روند برای پیدا کردن بهترین مجموعه والدها به طول سه، چهار و … هم به همین صورت ادامه می یابد. برای بدست آوردن امتیاز هر مجموعه، سری زمانی یک بار بررسی می شود. بنابراین پیچیدگی محاسباتی الگوریتم ارائه شده برابر می شود.
فصل چهارم
نتایج تجربی
مقدمه
در این بخش به ارائه آزمایش های انجام شده برای ارزیابی روش پیشنهادی و مقایسه آن با روش های قبلی پرداخته می شود. اما در ابتدا لازم است به دو نکته اساسی اشاره شود.
نکته اول این است که برای مقایسه روش های بازیابی شبکه نمی توان از ملاک های ارزیابی رایج که در کلاسه بندی استفاده می شوند مانند دقت[32] استفاده کرد. دلیل این امر این است که مسئله بازیابی شبکه بسیار نامتعادل[33] است. بدین معنی که تعداد یال هایی که در شبکه موجودند نسبت به یال هایی که وجود ندارند بسیار کمتر است. برای این گونه مسائل از ملاک های سنجش دیگری استفاده می شود که در ادامه معرفی می شوند.
نکته قابل توجه دوم این است که عموماً برای مقایسه روش های بازیابی شبکه های تنظیمات ژنی از داده های آموزشی که از شبکه های شبیه سازی[34] شده نمونه گیری شده اند، نه از سری های زمانی بیان ژن واقعی، استفاده می شود. این انتخاب به این دلیل است که ساختار واقعی شبکه های تنظیمات ژنی طبیعی مشخص نیستند. به طور مثال اگر در شبکه استنتاج شده به وسیله یک روش بین دو ژن یال باشد، نمی توان مطمئن بود که در شبکه حقیقی چنین یالی وجود دارد یا ندارد. وجود برخی ارتباطات بین ژن ها در آزمایشگاه اثبات شده اند. اما نمی توان نتیجه گرفت که یال هایی که تا کنون برای وجود آن ها مدرکی وجود ندارد قطعاً وجود ندارند. این موضوع مقایسه روش ها را بر اساس شبکه های واقعی غیر ممکن می سازد. روشی که برای تولید شبکه هایی که از آن ها به عنوان مرجع مقایسه در این تحقیق استفاده شده است در ادامه این بخش توضیح داده می شود.
در قسمت اول این بخش روشی که برای شبیه سازی شبکه های بیزین دینامیکی که در آن ها توزیع درجه خروجی از قانون توانی پیروی می کند مشخص می گردد. در قسمت 4-3 ملاک های سنجش و مقایسه ای که برای ارزیابی روش ارائه شده از آن ها استفاده شده است معرفی می گردند. در قسمت های بعدی این بخش، آزمایش های انجام شده در این تحقیق و نتایج بدست آمده از آن ها ارائه می گردند.
 
روش های تولید شبکه های Scale-free
در این تحقیق، برای شبیه سازی شبکه های بیزین دینامیکی که درجه خروجی در آن ها از قانون توانی پیروی می کند و تعداد یال های ورودی به هر گره تعداد محدودی است، از روش زیر استفاده شده است:
ساختار یک شبکه بیزین با دو قطعه زمانی (2TBN) را در نظر بگیرید که در هر کدام از قطعه های زمانی آن گره وجود دارد. برای هر کدام از گره های قطعه زمانی اول، تعداد یال های خروجی از توزیع احتمالی زیر انتخاب می شود: