Кіріспе

Графикалық модельдердегі статистикалық қорытындылау алгоритмі

Сенім тарату, сондай-ақ, sum-product message passing деп те аталады, бұл Бейес желілері және Марков кездейсоқ өрістері сияқты графикалық модельдерде қорытындылауды жүзеге асыруға арналған хабар алмасу алгоритмі. Ол кез келген байқалған түйіндерге (немесе айнымалыларға) шартты, байқалмаған әрбір түйіннің (немесе айнымалының) шеттік үлестірілуін есептейді. Сенім тарату жасанды интеллект және ақпарат теориясында кеңінен қолданылады және төмен тығыздықты теңсіздік тексеру кодтары, турбо кодтар, еркін энергияны жуықтау және қанағаттандыру сияқты көптеген қолдануларда эмпирикалық сәттілікке қол жеткізді. Ол ағаштарда нақты қорытындылау алгоритмі ретінде ұсынылды, кейін полиағаштарға дейін кеңейтілді. Алгоритм жалпы графиктерде нақты болмаса да, пайдалы жуықтама алгоритмі болып табылады.

Мотивация

Бірлескен ықтималдық массалық функциясы бар дискретті кездейсоқ айнымалылардың шекті жиынтығы берілген кезде, жиі кездесетін міндет – олардың шекті үлестірімдерін есептеу. Бір айнымалының шегі мысылы, былай анықталады:

мұнда – айнымалының мүмкін мәндерінің векторы, ал белгілеуі – қосынды осылардың арасында, яғни координатасы -қа тең мәндер бойынша алынады. Осы формуламен шекті үлестірімдерді есептеу айнымалылар саны артаған сайын тез арада есептеуге тыйырым салатын болады. Мысалы, 100 екілік айнымалы берілгенде, бір шекті есептеу үшін және жоғарыдағы формула бойынша мәндердің барлық мүмкін комбинацияларын қосу қажет болады. Егер ықтималдық массалық функциясы ыңғайлы түрде жіктелген болса, сенім тарату шектілерді әлдеқайда тиімді есептеуге мүмкіндік береді.

Ағаштар үшін нақты алгоритм

Егер факторлық график ағаш болса, сенім тарату алгоритмі нақты шекті мәндерді есептейді. Сонымен қатар, хабарламаларды жаңартуды дұрыс жоспарлау арқылы, ол ағаш бойынша екі толық айналымнан кейін тоқталады. Бұл оңтайлы жоспарлауды былай сипаттауға болады:

Бастамас бұрын, графты бір түйінды тамыр деп белгілеу арқылы бағдарлау керек; тамыр емес, тек бір түйінмен байланысқан түйін жапырақ деп аталады. Бірінші қадамда хабарламалар ішке қарай жіберіледі: жапырақтардан бастап, әрбір түйін (бірден-бір) қабырға бойымен хабарды тамыр түйініне жібереді. Ағаш құрылымы хабарды жібермес бұрын, барлық басқа да іргелес түйіндерден хабар алуға мүмкіндік береді. Бұл тамыр барлық іргелес түйіндерден хабарлама алғанға дейін жалғасады. Екінші қадам – хабарламаларды кері қайтару: тамырдан бастап, хабарламалар кері бағытта жіберіледі. Алгоритм барлық жапырақтар хабарламаларын алғанда аяқталады.

Жалпы графиктер үшін шамамен алынған алгоритм

Алғашында ациклді графикалық модельдер үшін жасалған болса да, сенім тарату алгоритмі жалпы графтарда қолданылуы мүмкін. Алгоритм кейде «циклдік сенім тарату» деп аталады, өйткені графтарда циклдар немесе тізбектер жиі кездеседі. Алгоритмді бастау және хабарламаларды жаңарту кестесі ациклді графтар үшін бұрын сипатталған кестемен салыстырғанда сәл өзгертілуі керек, себебі графтарда жапырақтар болмауы мүмкін. Оның орнына, барлық айнымалы хабарламалар 1-ге тең деп бастамаланады және жоғарыдағы хабарлама анықтамалары қолданылады, барлық хабарламалар әрбір итерацияда жаңартылады (бірақ белгілі жапырақтардан немесе ағаш тәрізді қосалқы графтардан келетін хабарламаларды жеткілікті итерациялардан кейін жаңарту қажет болмауы мүмкін). Ағашта осы өзгертілген процедураның хабарлама анықтамалары ағаш диаметріне тең итерациялар саны ішінде жоғарыда берілген хабарлама анықтамаларының жиынтығына жақындасады. Циклдік сенім таратудың қандай жағдайларда конвергенцияланатыны әлі толыққанды түсініксіз; бір циклды қамтитын графтарда ол көп жағдайда конвергенцияланады, бірақ алынған ықтималдықтар дұрыс болмауы мүмкін. Циклдік сенім таратудың бірегей тұрақты нүктеге конвергенциялануы үшін жеткілікті (бірақ қажетті емес) бірнеше шарттар бар. Конвергенцияланбайтын немесе көптеген күйлер арасында ауысатын графтар да бар. EXIT диаграммалары сияқты әдістер сенім тарату прогресінің шамамен визуализациясын және конвергенцияның шамамен тестін ұсынуы мүмкін. Вариациялық әдістер мен Монте-Карло әдістері сияқты маргинализацияның басқа да шамамен әдістері бар. Жалпы графтарда дәл маргинализацияның бір әдісі – түйіспе ағашы алгоритмі, ол ағаш болуы кепілденген модификацияланған графқа сенім таратуды жүзеге асырады. Негізгі идея – циклдарды бір түйінге біріктіру арқылы жою.

Алгоритм және күрделілік мәселелері

Бұған ұқсас алгоритм көбінесе Витерби алгоритмі деп аталады, бірақ ол макс өнімі немесе минимум сомасы алгоритмінің ерекше жағдайы ретінде де белгілі, ол максимизация немесе ең ықтимал түсіндірменің байланысты мәселесін шешеді. Маргиналды шешуге тырысудың орнына, мұндағы мақсат – жаһандық функцияны максималдайтын шамаларды табу (яғни, ықтималдық контекстінде ең ықтимал шамалар), және оны arg max арқылы анықтауға болады: Бұл мәселені шешетін алгоритм сенім таратуға өте ұқсас, бірақ анықтамалардағы сомалар максимумдармен алмастырылады. Графикалық модельде маргинализация және максимизация сияқты қорытындылау мәселелерін дәл немесе жуықтап (кем дегенде салыстырмалы қатеге қатысты) шешудің қиындығы NP-қиын екенін атап өту керек. Нақтырақ айтқанда, жоғарыда анықталған маргинализация мәселесі #P-толық, ал максимизация NP-толық. Сенім таратудың жадты пайдалануын Арал алгоритмін қолдану арқылы азайтуға болады (уақыт күрделілігінің сәл өсуімен).

Жалпы сенімнің таралуы (GBP)

Сенім тарату алгоритмдері әдетте факторлық граф бойынша хабарды жаңарту теңдеулері түрінде ұсынылады, олар өзгермелі түйіндер мен олардың көрші факторлық түйіндері арасындағы хабарларды және керісінше қамтиды. Граф ішіндегі аймақтар арасындағы хабарларды қарастыру – сенім тарату алгоритмін жалпылаудың бір жолы және бұл Кикучидің кластерлік вариациялық әдісі деп аталады. Сенім тарату алгоритмдерінің тиімділігін арттыру үшін өрістердің (хабарламалардың) таралуындағы репликалар симметриясын бұзуға да болады. Бұл жалпылау зерттеу тарату (SP) деп аталатын жаңа алгоритмге алып келеді, ол қанағаттандыру және графты бояу сияқты NP-толық проблемаларда өте тиімді болып көрінді. Кластерлік вариациялық әдіс және зерттеу тарату алгоритмдері – сенім таратуға екі түрлі жақсарту. Екі жалпылауды біріктіретін алгоритмге жалпыланған зерттеу таратуы (GSP) атауы берілуі күтілуде.