پایان نامه با واژگان کلیدی شبکه های بیزی، بیزین دینامیک، دانش اولیه

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

P_d (i)= ( 〖deg_out〗⁡(i)+λ)/(Nλ+∑_(j=1)^N▒〖deg_out〗⁡(j) )
(3-24)

در این توزیع، 〖deg_out〗⁡(i) تابعی است که درجه خروجی گره iام را بر می گرداند و λ پارامتری است که از احتساب احتمال صفر به گره هایی که هیچ یال خروجی ندارند جلوگیری می کند. باید توجه شود که توزیع احتمالی (3-24) همان توزیعی است که در مدل ارائه شده در بخش (3-5) برای تولید شبکه های جهت داری که در آن ها درجه خروجی از قانون توانی پیروی می کند استفاده شده است.
بر اساس توزیع احتمالی در فرمول (3-24)، می توان به هر مجموعه ای از گره ها که به عنوان والدهای گره iام انتخاب می شوند امتیازی نسبت داد که این امتیاز میزان کیفیت آن مجموعه را به عنوان والدهای این گره نشان می دهد. این تابع امتیازدهی چنین تعریف می شود:

DS(π(Z^i )→Z^i;G_(-i)^’ )=∑_(j∈π(Z^i ))▒log⁡〖P_d (j)〗 -√(├|├ π(Z^i )┤|┤ ) log⁡〖1/N〗
(3-25)

G_(-i)^’ نشان دهنده کل شبکهG^’ بدون در نظر گرفتن یال های ورودی به گره iام است. ترم دوم در سمت راست معادله (3-25) باعث می شود که امتیاز والدها با تعداد گره بیشتر مقداری افزایش یابد. به بیان دیگر، این ترم میزان جریمه را برای مجموعه هایی با تعداد گره های بیشتر کاهش می دهد.
تا اینجا فرض شده بود که تنها منبع برای بازسازی شبکه G از روی شبکه G^’ ساختار فعلی شبکه G^’ است. حال اگر فرض شود که یک سری زمانی تولید شده به وسیله شبکه G در اختیار است، می توان برای بازیابی شبکه G از ترکیب این منبع اطلاعاتی به همراه ساختار شبکه G^’ و احتمالاً دانش قبلی در مورد ساختار شبکه G استفاده کرد. برای این منظور می توان از ترکیب توابع امتیازدهی (3-25) و (3-6) استفاده کرد. تابع جدید برابر است با:

Score(Z^i,π(Z^i );D)=LS(D;π(Z^i )→Z^i )+PS(π(Z^i )→Z^i )+DS(π(Z^i )→Z^i;G_(-i)^’)
(3-26)

نکته قابل توجه دیگر این است که در موقعیتی که در بالا توصیف شده است، می دانیم که یال های شبکه G^’ مطمئناً در شبکه اصلی هم وجود دارند. این فرض باعث می شود که ساختار شبکه G^’ منبع قابل اعتمادی برای بازیابی شبکه اصلی باشد. اما در عمل، ما چنین اطلاعاتی نداریم و مسئله ساختن شبکه G از ابتدا است. در چنین حالتی اضافه کردن یال هایی که اشتباه هستند بسیار محتمل است. زمانی که پیدا کردن بهترین مجموعه والدها برای هر گره از ساختار شبکه مستقل است، اضافه کردن یال های اشتباه تاثیری در بازیابی باقی شبکه ندارند. اما، در روش ارائه شده، اضافه کردن یال های اشتباه بر روی درجه خروجی گره ها تاثیر می گذارند. این تاثیر به نوبه خود باعث تغییر در توزیع (3-24) می شود که این می تواند کل فرآیند بازیابی شبکه را تحت تاثیر قرار دهد.
برای حل این مشکل و کاهش احتمال اضافه کردن یال های اشتباه، حداقل در مراحل ابتدایی فرآیند یادگیری شبکه، الگوریتم ارائه شده یال ها را به صورت افزایشی و طی مراحل مختلف به شبکه اضافه می کند. فرآیند با افزودن یال هایی که باعث ایجاد بیشترین افزایش در امتیاز شبکه می شوند آغاز می شود. بر اساس اطلاعاتی که ما از داده های آموزشی و دانش اولیه داریم، این ها یال هایی هستند که بیشترین اطمینان از وجود آن ها در شبکه اصلی داریم. بعد از افزودن این یال ها، فرض می کنیم که ساختار شبکه ساخته شده در این مرحله حقیقی است و بر اساس این ساختار، احتمال اختصاص یافته به هر گره را در توزیع احتمالی (3-24) دوباره محاسبه می کنیم. در این مرحله دوباره یال هایی که باعث بیشترین افزایش می شوند را به شبکه اضافه کرده، مراحل قبل را تکرار می کنیم.
به صورت دقیق تر فرآیند یاد گیری در الگوریتم ارائه شده بدین صورت است: ابتدا امتیاز مربوط به هر گره، با فرض این که گره ها هیچ والدی ندارند، محاسبه می شود. در گام بعدی بهترین مجموعه والدها برای هر گره بر اساس تابع امتیازدهی (3-26) انتخاب می شود و میزان افزایشی که توسط اضافه کردن یال های مربوطه در امتیاز آن گره ایجاد می شود محاسبه می گردد. بعد از محاسبه میزان تغییر امتیاز برای تمامی گره ها، گره ها بر اساس این میزان افزایش به صورت نزولی مرتب می شوند و 10% گره ها که بیشترین تغییر در امتیاز را دارند انتخاب می شوند.در پایان، یال های مربوط به بهترین والدها برای گره های انتخاب شده به شبکه اضافه می شوند. بعد از افزوده شدن این یال ها احتمال منسوب به هر گره بر اساس (3-24) دوباره محاسبه می شود. در حلقه بعدی الگوریتم، دوباره بهترین مجموعه والدها برای هر گره بر اساس (3-26) محاسبه می شود و مراحل قبل تکرار می گردند. این فرآیند تا جایی تکرار می شود که میزان افزایش امتیاز در آن مرحله از کسر مشخصی از کل افزایش بدست آمده از ابتدای فرآیند کمتر شود. این فرآیند به طور دقیق در تصویر (3-5) ارائه شده است.

مطلب مشابه :  منابع پایان نامه دربارهایده‌آل، گزینه، منفی، راه‌حل

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Procedure BDe+DS

Inputs: a time-series of N variables (D); a threshold (ϵ); the maximum number of parents for each node (L); A regularization constant (λ)
Output: The inter-slice arcs of a DBN (Net)

Net = An empty network

for node from 1 to N
ls = LS(Data;∅→node )
ps = PS(∅→node )
bestScore[node] = ls+ps
bestParent[node] = ∅
scoreDiff[node] = 0

while (condition)
for nPrnt
from 1 to L
for node from 1 to N
P_d = UpdateScore (〖Net〗_(-node))
maxScore = -∞
bestPrnts = ∅
possiblePrnts = All possible parents of node
containing nPrnt nodes.

for i from 1 to |possiblePrnts|
prnts = possiblePrnts[i]
ls=LS(Data;prnts→node )
ps = PS(prnts→ node)
ds = sum(P_d [prnts])-√nPrnt.log⁡〖1/N〗
score = ls+ps+ds
if(score > maxScore)
maxScore = score
bestPrnts = prnts

if (maxScore > bestScore[node]+scoreDiff[node])
scoreDiff[node] = maxScore – bestScore[node]
bestParentTemp[node] = bestPrnts

[sortedValues, sortIndices] = sort(scoreDiff, ‘descend’)
numTopNodes = ⌈0.1*N⌉
improvement = sum(sortedValues[1:numTopNodes])
totalImprovement = improvement+totalImprovement

if (improvement/ totalImprovement) < ϵ)
condition = false

for i from 1 to numTopNodes
node = sortedIndices[i]
bestScore[node] = scoreDiff[node] + bestScore[node]
bestParent[node] = bestParentTemp[node]
update Net based on the values in bestParent

for node from 1 to N
bestParentTemp[node] = bestParent[node]
scoreDiff[node] = 0

Return Net

60

65

function UpdateScore (Net)
degrees = The out-degrees of the nodes
for i from 1 to N
S(i) =min⁡{degrees[i], ⌈0.2*N⌉}+λ
S = S / sum(S)
return log(S)

شکل 3-5- شبه کد الگوریتم ارائه شده برای یاد گیری شبکه های بیزین دینامیک با ساختار scale-free

باید توجه شود که شبکه ای که از آخر به وسیله الگوریتم ارائه شده بازیابی می شود جواب مسئله بیشینه سازی که از ابتدا مشخص باشد نیست. در واقع، الگوریتم ارائه شده فرآیند یادگیری شبکه را به حل چندین مسئله بیشینه سازی تقسیم می کند. در هر مرحله شبکه ای که در آخر بوجود می آید حل مسئله بیشینه سازی تعریف شده برای همان مرحله است. سپس، با توجه به این شبکه، مسئله بیشینه سازی بعدی تعریف می شود. شبکه ای که در آخر باز گردانده می شود شبکه ای است که حل آخرین مسئله بیشینه سازی تعریف شده در طول فرآیند الگوریتم است.
پیچیدگی محاسباتی الگوریتم ارائه شده را می توان چنین بدست آورد: مسئله اصلی به حل K مسئله بیشینه سازی تقسیم می شود. در هر مسئله، بهترین مجموعه والدها برای هر یک از N گره پیدا می شود. برای پیدا کردن بهترین والدها برای هر گره، M = ∑_(i=1)^L▒(N¦i) ~O(N^L) مجموعه مختلف بررسی می شوند (یادآوری می شود که L بیشینه تعداد والدها برای هر گره است) و برای بدست آوردن امتیاز هر مجموعه، سری زمانی یک بار بررسی می شود. بنابراین پیچیدگی محاسباتی الگوریتم ارائه شده برابر با O(N^(L+1) TK) می شود.
با وجود این که پیچیدگی محاسباتی الگوریتم ارائه شده چند جمله ای است، اما این پیچیدگی در مواردی که تعداد گره ها زیاد هستند و بیشینه تعداد والدهای هر گره هم از سه بیشتر است می تواند فرآیند یادگیری را غیر عملی سازد.
مشکل پیچیدگی محاسباتی الگوریتم ارائه شده را می توان با تغییر استراتژی جستجوی الگوریتم برای پیدا کردن بهترین والدها برای هر گره بر طرف کرد. در واقع، با استفاده از استراتژی جستجوی حریصانه به جای جستجوی تمامی مجموعه های ممکن به عنوان والد، پیچیدگی محاسباتی الگوریتم از O(N^(L+1) TK) به O(LN^2 TK) کاهش می یابد. در الگوریتم تغییر یافته، برای هر گره، تنها مجموعه والدهای با طول P بررسی می شوند که شامل بهترین مجموعه والدها برای آن گره با طول P-1 باشند. الگوریتم تغییر یافته با جزئیات کامل در شکل (3-6) نمایش داده شده است.

مطلب مشابه :  شبکه های بیزی، بیزین دینامیک، دانش اولیه

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Procedure BDe+DS

Inputs: a time-series of N variables (D); a threshold (ϵ); the maximum number of parents for each node (L); A regularization constant (λ)
Output: The inter-slice arcs of a DBN (Net)

Net = An empty network

for node from 1 to N
ls = LS(Data;∅→node )
ps = PS(∅→node )
bestScore[node] = ls+ps
bestParent[node] = ∅
scoreDiff[node] = 0

while (condition)
for nPrnt from 1 to L
for node from 1 to N
if(nPrnt ≠|bestPrntTmp|+1 )
continue
P_d = Calculate probabilities for 〖Net〗_(-node) by (6)
maxScore = -∞
bestPrnts = ∅
possiblePrnts = {1, …,N}-bestPrntTmp[node]
for i from 1 to |possiblePrnts|
prnts = {bestPrntTmp[node]∪possiblePrnts[i]}
ls = LS(Data;prnts→node )
ps = PS(prnts→ node)
ds = sum(P_d [prnts])-√nPrnt.log⁡〖1/N〗
score = ls+ps+ds
if(score > maxScore)
maxScore = score
bestPrnts = prnts

if (maxScore > bestScore[node]+scoreDiff[node])
scoreDiff[node] = maxScore – bestScore[node]
bestParentTemp[node] = bestPrnts

[sortedValues, sortIndices] = sort(scoreDiff, ‘descend’)
numTopNodes = ⌈0.1*N⌉
improvement = sum(sortedValues[1:numTopNodes])
totalImprovement = improvement+totalImprovement

if (improvement/ totalImprovement) < ϵ)
condition = false

for i from 1 to numTopNodes
node = sortedIndices[i]
bestScore[node] = scoreDiff[node] + bestScore[node]
bestParent[node] = bestParentTemp[node]
update Net based on the values in bestParent

for node from 1 to N
bestParentTemp[node] = bestParent[node]
scoreDiff[node] = 0

Return Net

60

65

function UpdateScore (Net)
degrees = The out-degrees of the nodes
for i from 1 to N
S(i) =min⁡{degrees[i], ⌈0.2*N⌉}+λ

Leave a Comment