Bayesove mreže: opredelitev, primeri in načela delovanja

Učinkovitost

Učinkoviti algoritmi lahko izvajajo sklepanje in učenje v Bayesovih omrežjih. Omrežja, ki modelirajo spremenljivke (npr. govorne signale ali proteinska zaporedja), se imenujejo dinamična. Posplošitve Bayesovih omrežij, ki lahko predstavljajo in rešujejo probleme v pogojih negotovosti, se imenujejo diagrami vpliva.

Bistvo je, da

Formalno so Bayesova omrežja skupine dostopnosti do podatkovnih baz, katerih vozlišča predstavljajo spremenljivke v Bayesovem smislu: lahko so opazovane spremenljivke, latentne spremenljivke, neznani parametri ali hipoteze. Zato je zelo zanimiva.

Primer Bayesovega omrežja

Mokro travo lahko povzročita dva dogodka: aktivni razpršilnik ali dež. Dež neposredno vpliva na uporabo škropilnice (ob dežju je namreč škropilnica običajno neaktivna). To situacijo je mogoče modelirati z Bayesovim omrežjem.

Modeliranje

Ker je Bayesovo omrežje popoln model spremenljivk in njihovih odnosov, ga je mogoče uporabiti za odgovarjanje na verjetnostne poizvedbe o njih. Uporablja se lahko na primer za posodobitev znanja o stanju podmnožice spremenljivk, ko se opazujejo drugi podatki (dokazne spremenljivke). Ta zanimiv proces se imenuje verjetnostno sklepanje.

A posteriori daje univerzalno zadostno statistiko za uporabo pri odkrivanju pri izbiri vrednosti za podmnožico spremenljivk. Tako lahko ta algoritem obravnavamo kot mehanizem za samodejno uporabo Bayesovega izreka pri kompleksnih problemih. Na slikah v članku si lahko ogledate primere Bayesovih omrežij zaupanja.

Metode sklepanja

Najpogostejše metode natančnega sklepanja so: izključitev spremenljivk, ki izloči (z integracijo ali seštevanjem) neopazne parametre, ki niso pomembni za poizvedbo, enega za drugim, tako da se vsota porazdeli po produktu.

Razširjanje "drevo" klik, ki izračune predpomni, tako da je mogoče poizvedovati po številnih spremenljivkah naenkrat in hitro razmnoževati nove dokaze; in rekurzivno ujemanje in/ali iskanje, ki je kompromis med prostorom in časom ter ustreza učinkovitosti izključevanja spremenljivk, kadar je prostora dovolj.

Vse te metode imajo posebno zapletenost, ki se eksponentno spreminja z dolžino omrežja. Najpogostejše Algoritmi za sklepanje o bližini so metode, kot so izločanje mini segmentov, krožno širjenje prepričanja, posplošeno zadnje širjenje in variacijske metode.

Delo z omrežji

Da bi v celoti določili Bayesovo omrežje in tako v celoti predstavili skupno porazdelitev verjetnosti, je treba za vsako vozlišče X določiti porazdelitev verjetnosti za X zaradi staršev X.

Porazdelitev X na starše je lahko v kakršni koli obliki. Običajno delamo z diskretnimi ali Gaussovimi porazdelitvami, saj to poenostavi izračun. Včasih so znane samo omejitve porazdelitve. Nato lahko z entropijo določimo posamezno porazdelitev, ki ima največjo entropijo ob upoštevanju omejitev.

Podobno je v posebnem kontekstu dinamičnega Bayesovega omrežja pogojna porazdelitev za časovni razvoj latentnega stanja običajno določena tako, da maksimira stopnjo entropije impliciranega naključnega procesa.

Neposredna maksimizacija največje verjetnosti (ali posteriorne verjetnosti) je zaradi prisotnosti neopazovanih spremenljivk pogosto težavna. To še posebej velja za Bayesovo omrežje sprejemanje odločitev.

Klasični pristop

Klasični pristop k temu problemu je algoritem maksimizacije pričakovanj, ki izmenično izračunava pričakovane vrednosti neopazovanih spremenljivk, ki so odvisne od opazovanih podatkov, in maksimizira splošno verjetnost (ali posteriorno vrednost) ob predpostavki, da so predhodno izračunane pričakovane vrednosti resnične. Pod pogoji zmerne pravilnosti ta proces konvergira k največjim (ali največjim posteriornim) vrednostim parametrov.

Celovitejši Bayesov pristop k parametrom je, da jih obravnavamo kot dodatne neopazovane spremenljivke in izračunamo celotno posteriorno porazdelitev za vsa vozlišča glede na opazovane podatke ter nato integriramo parametre. Ta pristop je lahko drag in vodi do velikih modelov, zato so klasični pristopi določanja parametrov bolj dostopni.

V najpreprostejšem primeru Bayesovo mrežo določi strokovnjak in jo nato uporabi za izvajanje sklepanja. Pri drugih aplikacijah je naloga odkrivanja za človeka pretežka. V tem primeru se je treba strukturo Bayesove nevronske mreže in parametre lokalnih porazdelitev naučiti med podatki.

Alternativna metoda

Alternativna metoda strukturnega učenja uporablja optimizacijsko iskanje. To zahteva funkcijo ocenjevanja in strategijo iskanja. Običajen algoritem za ocenjevanje je posteriorna verjetnost strukture ob upoštevanju podatkov o usposabljanju, kot sta BIC ali BDeu.

Potrebni čas za izčrpno iskanje, ki vrne strukturo, ki maksimizira oceno, je supereksponencialen glede na število spremenljivk. Strategija lokalnega iskanja uvaja postopne spremembe za izboljšanje vrednotenja strukture. Friedman je s sodelavci preučil uporabo vzajemne informacije med spremenljivkami za iskanje prave strukture. Omejijo množico kandidatov za starše na k vozlišč in temeljito iščejo v njih.

Posebej hitra metoda za natančno učenje BN je, da problem predstavimo kot optimizacijski problem in ga rešimo s celoštevilskim programiranjem. Aciklične omejitve se celoštevilskemu programu (IP) dodajo med reševanjem v obliki rezalnih ravnin. Takšna metoda lahko obravnava probleme z do 100 spremenljivkami.

Reševanje problemov

Na naslov reševati težave z več tisoč spremenljivkami, je potreben drug pristop. Eden od njih je, najprej izberete en vrstni red in nato poiščete optimalno strukturo BN glede na ta vrstni red. To pomeni, da je treba delati v iskalnem prostoru možnih vrstnih redov, ki je primeren, ker je manjši od prostora mrežnih struktur. Nato se izbere in oceni več naročil. Ta metoda se je izkazala za najboljšo v literaturi, kadar je število spremenljivk ogromno.

Druga metoda je, da se osredotočimo na podrazred razgradljivih modelov, za katere imajo MLE zaprto obliko. Potem je mogoče najti dosledno strukturo za več sto spremenljivk.

Učenje Bayesovih omrežij z omejeno širino treh vrstic je treba zagotoviti natančno in izvedljivo sklepanje, saj je zahtevnost slednjega v najslabšem primeru eksponentna v dolžini drevesa k (v skladu s hipotezo o eksponentnem času). Vendar pa kot globalna lastnost grafa znatno poveča zapletenost učnega procesa. V tem kontekstu se lahko za učinkovito učenje uporablja drevo K.

Razvoj

Razvoj Bayesovega omrežja zaupanja se pogosto začne z oblikovanjem DAG G, tako da X izpolnjuje lokalno Markovovo lastnost glede na G. Včasih je to vzročna DAG. Ocenjene pogojne verjetnostne porazdelitve vsake spremenljivke glede na njeno starševsko spremenljivko v G. Če je skupna porazdelitev X produkt teh pogojnih porazdelitev, potem v mnogih primerih, zlasti kadar so spremenljivke diskretne, X postane Bayesovo omrežje glede na G.

Markovski "odeja za vozlišča" - je množica vozlišč. Markovova odeja naredi vozlišče neodvisno od ostalih v obliki istega vozlišča in je zadostno znanje za izračun njegove porazdelitve. X je Bayesovo omrežje glede na G, če je vsako vozlišče pogojno neodvisno od vseh drugih vozlišč glede na njegovo markovsko odejo.