Algoritmul arborelui comun

Algoritmul arborelui de articulare  este o tehnică utilizată în învățarea automată pentru a extrage marginalizarea în graficele generale . În esență, algoritmul realizează propagarea încrederii pe un graf modificat numit arbore de joncțiune . Premisa principală a algoritmului este eliminarea ciclurilor prin gruparea lor în noduri.

Algoritm pentru arborele de articulare

Algoritmul programului Hugin [1]

• Dacă graficul este direcționat, atunci îl moralizăm pentru a-l face nedirecționat.
• Formăm informații
• Triangularea graficului pentru a obține un grafic cordal
• Construiți un arbore de articulație dintr-un graf triagulat (vom numi vârfurile arborelui de articulație „supernoduri”)
• Efectuăm propagarea probabilităților de-a lungul arborelui comun (folosind algoritmul de propagare a încrederii )

Rețineți că ultimul pas este ineficient pentru graficele cu lățimi mari de arbore . Calcularea mesajelor transmise între supernoduri necesită o marginalizare precisă la ambele supernoduri. Implementarea algoritmului pe un grafic cu lățimea arborelui k ar necesita calcule care depind exponențial în timp de valoarea lui k.

Algoritmul Schafer-Chenoy

• Triangulăm graficul, făcând excepții într-o ordine arbitrară (dacă este necesar).
• Găsiți clicurile maxime în graficul de acorduri.
• Găsim seturi de separare pentru fiecare pereche de clicuri maxime și construim un grafic de clicuri ponderate.
• Găsiți arborele de greutate maximă pe graficul clicei pentru a obține arborele de articulație.
• Determinăm potențialele pe arborele articulațiilor.
• Calculăm suma produselor de pe arborele articulațiilor. Aceasta este o modalitate de modificare a informațiilor (transmiterea mesajului). Acest pas, de fapt, este cunoscut sub numele de algoritmul Schafer-Chenoy.
• Calculăm marjele.

Timpul total de rulare al algoritmului , unde N  este numărul de vârfuri, D  este dimensiunea celei mai mari clicuri,  este dimensiunea maximă a alfabetului din nod [2]

Rețineți că dimensiunea celei mai mari clicuri D depinde de ordinea eliminării, iar dimensiunea minimă este egală cu lățimea arborelui.

Practic, algoritmul lui Hugin face același lucru, dar pașii 5 și 6 se fac diferit pentru a reduce numărul de înmulțiri [2] .

Fundamente teoretice (pentru algoritmul Hugin)

Primul pas se aplică numai rețelelor bayesiene și procedurii de transformare a unui graf direcționat într-unul nedirecționat. Facem acest lucru pentru că permite algoritmului să fie aplicat universal, indiferent de direcții.

Al doilea pas este setarea variabilelor la valorile lor observabile. Acest lucru este de obicei necesar atunci când dorim să calculăm probabilități condiționate, așa că fixăm valoarea variabilelor aleatoare asupra cărora sunt calculate probabilitățile.

La al treilea pas, facem ca graficele să devină acorde dacă nu sunt deja acorde. Aceasta este prima parte esențială a algoritmului. Pentru aceasta se folosește următoarea teoremă [3] :

Teoremă: Pentru un graf nedirecționat G, următoarele proprietăți sunt echivalente:

• Graficul G este triangulat.
• Graficul clică al lui G are un arbore de articulație.
• Există o ordine de excludere pentru graficul G care nu determină excluderea vreunei muchii adăugate.

Astfel, prin triangularea graficului, ne asigurăm că există arborele de articulație corespunzător. Acest lucru se face de obicei în ordinea în care sunt eliminate nodurile și apoi se rulează algoritmul de eliminare a variabilelor . Acest lucru duce la adăugarea de muchii suplimentare la graficul original, astfel încât rezultatul este un grafic de acorduri. Următorul pas este construirea arborelui de articulare . Pentru a face acest lucru, folosim graficul de la pasul anterior și formăm un grafic de clic [4] . Următoarea teoremă oferă o metodă pentru construirea unui arbore de articulare [3] :

Teorema: Să fie dat un grafic triangulat a cărui greutate a muchiei graficului clicei |A∩B| este dată de cardinalitatea intersecției clicurilor adiacente A și B. Atunci arborele de întindere al greutății maxime a graficului clicei este un arbore de joncțiune.

Astfel, pentru a construi un arbore de articulare, este necesar să se extragă arborele de întindere de greutate maximă din graficul clicei. Acest lucru se poate face eficient, de exemplu, prin modificarea algoritmului lui Kruskal . La ultimul pas, algoritmul de propagare a încrederii este aplicat arborelui de articulare rezultat [5] .

Note

1. ↑ Puteți citi despre programul Hugin la Hugin - cel mai bun program panoramic Arhivat 26 ianuarie 2018 la Wayback Machine
2. ↑ 12 Recitarea 8, 2014 .
3. ↑ 12 Wainwright . _
4. ↑ Clique Graph .
5. ↑ Frizer, 2014 .

Literatură

• Martin Wainwright. Modele grafice, algoritmi de transmitere a mesajelor și metode variaționale: Partea I. Berkeley EECS (31 martie 2008). Data accesului: 16 noiembrie 2016. (nedefinit)
• Faceți clic pe Grafic . Data accesului: 16 noiembrie 2016. (nedefinit)
• David Barber. Modelare și raționament probabilistic, algoritmul arborelui de joncțiune . Universitatea din Helsinki (2014). Data accesului: 16 noiembrie 2016. (nedefinit)
• Steffen L. Lauritzen, David J. Spiegelhalter. Calcule locale cu probabilități pe structuri grafice și aplicarea lor la sistemele experte // Journal of the Royal Statistical Society . Seria B (Metodologic). - Editura Blackwell, 1988. - V. 50 , nr. 2 . — S. 157–224 . — .
• Dawid AP Aplicații ale unui algoritm general de propagare pentru sisteme expert probabilistice // Statistică și Calcul. - Springer, 1992. - Vol. 2 , nr. 1 . — S. 25–26 . - doi : 10.1007/BF01890546 .
• Cecil Huang, Adnan Darwiche. Inferență în rețelele de credință: un ghid de procedură  // Jurnalul internațional de raționament aproximativ. - Elsevier, 1996. - T. 15 , nr. 3 . — S. 225–263 . - doi : 10.1016/S0888-613X(96)00069-2 .
• Mark A. Paskin. Un scurt curs despre modele grafice: 3. Algoritmii arborelui de joncțiune . Arhivat din original pe 19 martie 2015.
• Algoritmi pentru inferență . Institutul de Tehnologie din Massachusetts (2014). Data accesului: 25 septembrie 2017. (nedefinit)