Yhteinen puualgoritmi

Artikulaatiopuualgoritmi on koneoppimisessa  käytetty tekniikka marginalisoitumisen erottamiseksi yleisistä kaavioista . Pohjimmiltaan algoritmi suorittaa luottamuksen etenemisen muokatulle kaaviolle, jota kutsutaan liitospuuksi . Algoritmin päälähtökohtana on eliminoida syklit klusteroimalla ne solmuihin.

Artikulaatiopuun algoritmi

Hugin-ohjelman algoritmi [1]

Huomaa, että viimeinen vaihe on tehoton kaavioille, joilla on suuri puunleveys . Supersolmujen välillä välitettyjen viestien laskeminen vaatii tarkan marginalisoinnin molemmissa supersolmuissa. Algoritmin toteuttaminen graafille, jonka puun leveys on k, vaatisi laskelmia, jotka riippuvat eksponentiaalisesti ajallisesti k:n arvosta.

Schafer-Chenoy-algoritmi

Algoritmin kokonaisajoaika , jossa N  on kärkien lukumäärä, D  on suurimman klikkin  koko, on solmun aakkosten maksimikoko [2]

Huomaa, että suurimman klikin D koko riippuu eliminointijärjestyksestä ja minimikoko on yhtä suuri kuin puun leveys.

Periaatteessa Huginin algoritmi tekee saman, mutta vaiheet 5 ja 6 tehdään eri tavalla kertolaskujen määrän vähentämiseksi [2] .

Teoreettiset perusteet (Hugin-algoritmille)

Ensimmäinen vaihe koskee vain Bayesin verkkoja ja menettelyä suunnatun graafin muuttamiseksi suuntaamattomaksi. Teemme tämän, koska se mahdollistaa algoritmin yleisen soveltamisen suunnista riippumatta.

Toinen vaihe on asettaa muuttujat niiden havaittavissa oleviin arvoihin. Tätä tarvitaan yleensä, kun halutaan laskea ehdollisia todennäköisyyksiä, joten kiinnitämme niiden satunnaismuuttujien arvon, joiden perusteella todennäköisyydet lasketaan.

Kolmannessa vaiheessa teemme kaavioista sointuja, jos ne eivät ole jo sointuja. Tämä on algoritmin ensimmäinen olennainen osa. Tätä varten käytetään seuraavaa lausetta [3] :

Lause: Suuntaamattomalle graafille G seuraavat ominaisuudet ovat ekvivalentteja:

Siten kolmioimalla graafin varmistamme, että vastaava artikulaatiopuu on olemassa. Tämä tehdään yleensä siinä järjestyksessä, jossa solmut eliminoidaan, ja sitten ajetaan -muuttujan eliminointialgoritmi . Tämä johtaa siihen, että alkuperäiseen graafiin lisätään ylimääräisiä reunoja siten, että tuloksena on sointugraafi. Seuraava askel on nivelpuun rakentaminen . Tätä varten käytämme edellisen vaiheen kuvaajaa ja muodostamme napsautuskaavion [4] . Seuraava lause antaa menetelmän artikulaatiopuun rakentamiseksi [3] :

Lause: Olkoon kolmiograafi, jonka klikkausgraafin reunapaino |A∩B| saadaan vierekkäisten klikkien A ja B leikkauspisteen kardinaalisuudesta. Tällöin klikkigraafin maksimipainon virittävä puu on liitospuu.

Näin ollen artikulaatiopuun rakentamiseksi on välttämätöntä erottaa maksimipainoinen virittävä puu klikkigraafista. Tämä voidaan tehdä tehokkaasti esimerkiksi muuttamalla Kruskalin algoritmia . Viimeisessä vaiheessa luottamuksen etenemisalgoritmia sovelletaan tuloksena olevaan artikulaatiopuuhun [5] .

Muistiinpanot

  1. ↑ Voit lukea Hugin-ohjelmasta Huginista - paras panoraamaohjelma Arkistoitu 26. tammikuuta 2018 Wayback Machinessa
  2. ↑ 12 Lausunto 8, 2014 .
  3. ↑ 12 Wainwright . _
  4. ↑ Klikkikaavio .
  5. ↑ Parturi, 2014 .

Kirjallisuus