Айнымалы жою - Variable elimination - Wikipedia

Айнымалы жою (VE) - қарапайым және жалпы нақты қорытынды алгоритмі ықтималдық графикалық модельдер, сияқты Байес желілері және Марков кездейсоқ өрістер.[1] Оны қорытынды жасау үшін пайдалануға болады максимум - постериори (MAP) күйі немесе бағасы шартты немесе шекті үлестірулер айнымалылардың жиынтығы бойынша. Алгоритм уақыттың экспоненциальды күрделілігіне ие, бірақ практика жүзінде тиімділігі төменкеңдік егер тиісті жою тәртібі қолданылса, графиктер.

Факторлар

Алгоритмдік күрделіліктің негізгі төмендетілуіне мүмкіндік беру, фактор , сонымен бірге потенциал, айнымалылар деп аталады әрбір инстанциясы арасындағы қатынас болып табылады айнымалылар теріс санға, әдетте ретінде белгіленеді .[2] Фактордың белгілі бір түсіндірмесі болуы шарт емес. Ықтималдықты бөлу немесе шартты үлестіру сияқты әр түрлі көріністердің факторлары бойынша операциялар жасауға болады.[2] Бірлескен үлестірулер көбінесе өте үлкен болады, өйткені бұл операцияның күрделілігі экспоненциалды болады. Осылайша, факторизацияланған объектілерді есептеу кезінде айнымалы жою мүмкін болады.

Негізгі операциялар

Айнымалы қорытынды

Соминация (SO) немесе маргинализация деп аталатын 1 алгоритм бір айнымалыны жояды жиынтықтан факторлардың,[3] және алынған факторлар жиынтығын қайтарады. Жинаққа қатысты алгоритм осы факторларды жай қайтарады айнымалы қатысады .

1-алгоритм қорытынды (,)

= сәйкес келетін факторларды жинау
= барлық факторлардың көбейтіндісі


қайту

Мысал

Міне, бізде ықтималдықтың бірлескен таралуы. Айнымалы, жиынтығы бар инстанциялардың жиынтығы арасында қорытынды жасауға болады кем дегенде қалған айнымалылар туралы келісу керек. Мәні жиынтықталатын айнымалы болған кезде маңызды емес. [2]

шыншыншынжалғанжалған0.80
жалғаншыншынжалғанжалған0.20

Жойғаннан кейін , оның сілтемесі алынып тасталады және бізге тек қалған айнымалылар мен әр сәттің қосындысы бойынша үлестіру қалады.

шыншынжалғанжалған1.0

Қорытынды операциясынан кейін пайда болатын үлестіру тек аталмаған сұрақтарға жауап беруге көмектеседі .[2] Сондай-ақ, қорытындылау операциясы ауыстырымды болып табылады.

Факторды көбейту

Өнімді бірнеше факторлар арасында есептеу әр фактордағы бір инстанциямен үйлесімді факторға әкеледі.[2]

2-алгоритм көп факторлар (,)[2]

= Факторлар көбейтіндісі арасындағы барлық айнымалылардың бірлігі
= коэффициент аяқталды қайда барлығына
Үшін әр сәтте
Үшін 1-ден
айнымалылардың инстанциясы үйлесімді
қайту

Факторды көбейту тек коммутативті ғана емес, сонымен қатар ассоциативті болып табылады.

Қорытынды

Сұраудың ең көп таралған түрі - формада қайда және бөлінбеген ішкі жиындар болып табылады , және мән алуы байқалады . P (X | E = e) есептеудің негізгі алгоритмі деп аталады айнымалы жою (VE), алдымен шығарылған.[1]

Алынған,[1] бұл алгоритм есептейді В дискретті Байес желісінен B. айнымалыларды бір-бірлеп жою үшін SO шақырады. Нақтырақ айтсақ, 2-алгоритмде, - бұл В үшін шартты ықтималдықтар кестесінің жиынтығы (бұдан әрі «КҚТ»), - сұраныстың айнымалы тізімі, - бақыланатын айнымалылар тізімі, - бақыланатын мәндердің сәйкес тізімі, және - айнымалыларды жою тәртібі , қайда білдіреді .

Айнымалы жою алгоритмі VE ()

Факторларды тиісті CPT-мен көбейтіңіз, ал σ бос емес
Бірінші айнымалыны алып тастаңыз бастап
= қорытынды
= барлық факторлардың көбейтіндісі

қайту

Тапсырыс беру

Айнымалыларды жоюдың оңтайлы ретін табу NP қиын мәселе болып табылады. Тапсырыс бойынша өнімділікті жақсарту үшін эвристика бар:

  1. Ең төменгі дәреже: Мүмкін болатын ең кіші факторды құруға әкелетін айнымалыны жою.[2]
  2. Минималды толтыру: барлық CPT-мен көрсетілген айнымалы қатынастарды көрсететін бағытталмаған график құру арқылы, жойылғаннан кейін ең аз шеттер қосылатын айнымалыны жойыңыз.[2]

Әдебиеттер тізімі

  1. ^ а б c Zhang, N.L., Poole, D.: Bayesian Network Computations қарапайым тәсілі. Жасанды интеллект бойынша 7-ші канадалық конференция, б. 171-178. Спрингер, Нью-Йорк (1994)
  2. ^ а б c г. e f ж сағ Дарвиче, Аднан (2009-01-01). Bayesian желілерімен модельдеу және дәлелдеу. дои:10.1017 / cbo9780511811357. ISBN  9780511811357.
  3. ^ Коллер, Д., Фридман, Н.: Ықтимал графикалық модельдер: принциптер мен әдістер. MIT Press, Кембридж, MA (2009)