Bayesovská síť

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. prosince 2021; kontroly vyžadují 4 úpravy .

Bayesovská síť (nebo Bayesian network , Bayesian faith network , anglicky Bayesian network, faith network ) - graf pravděpodobnosti modelu , což je množina proměnných a jejich pravděpodobnostních závislostí podle Bayese . Bayesovskou síť lze například použít k výpočtu pravděpodobnosti, že pacient má onemocnění na základě přítomnosti nebo nepřítomnosti souboru symptomů, na základě údajů o vztahu mezi symptomy a nemocemi. Matematický aparát bayesovských sítí vytvořil americký vědec Judah Pearl , vítěz Turingovy ceny (2011).

Formálně je Bayesovská síť řízený acyklický graf , jehož každý vrchol odpovídá náhodné proměnné a oblouky grafu kódují podmíněné vztahy nezávislosti mezi těmito proměnnými. Vrcholy mohou představovat proměnné libovolného typu, mohou to být vážené parametry, latentní proměnné nebo hypotézy. Existují účinné metody, které se používají k výpočtu a trénování bayesovských sítí. Pokud jsou proměnné Bayesovské sítě diskrétními náhodnými veličinami, pak se taková síť nazývá diskrétní Bayesovská síť. Bayesovské sítě, které modelují sekvence proměnných, se nazývají dynamické bayesovské sítě . Bayesovské sítě, které mohou mít jak jednotlivé, tak spojité proměnné, se nazývají hybridní Bayesovské sítě . Bayesovská síť, ve které oblouky kromě vztahů podmíněné nezávislosti kódují i vztahy kauzality, se nazývá kauzální bayesovské sítě [ 1] ) .

Definice a provozní principy

Pokud oblouk přechází z vrcholu do vrcholu , pak se nazývá rodič a nazývá se potomek . Pokud existuje řízená cesta od vrcholu k vrcholu , pak se nazývá předek a nazývá se potomek . $A$ $B$ $A$ $B$ $B$ $A$ $A$ $B$ $A$ $B$ $B$ $A$

Množina vertex-rodičů vertexu bude označena jako . $V_i$ $\mathrm {rodiče} (V_{i})=\mathbf {PA} _{i}$

Orientovaný acyklický graf se nazývá Bayesovská síť pro rozdělení pravděpodobnosti definované přes množinu náhodných proměnných , pokud je každý vrchol grafu spojen s náhodnou proměnnou z , a oblouky v grafu splňují podmínku (Markovova podmínka [1] ): jakákoli proměnná from musí být podmíněně nezávislá na všech vrcholech, které nejsou jejími potomky, pokud jsou v grafu , tzn. $G$ $P(\mathbf {v} )$ ${\mathbf {V}}$ ${\mathbf {V}}$ $V_i$ ${\mathbf {V}}$ ${\displaystyle \mathbf {PA} _{i))$ $G$

$\forall V_{i}\in \mathbf {V}$ veletrh: $P(v_{i}\mid \mathbf {pa} _{i},\mathbf {s} )=P(v_{i}\mid \mathbf {pa} _{i}),$

kde je hodnota ; - konfigurace $v_{i}$ $V_i$ ${\mathbf {s))$ [ specifikovat ] ; je množina všech vrcholů, které nejsou potomky ; - konfigurace . $\mathbf {S}$ $\mathbf {S}$ $V_i$ ${\displaystyle \mathbf {pa} _{i))$ ${\displaystyle \mathbf {PA} _{i))$

Kompletní společné rozložení hodnot ve vrcholech pak lze pohodlně zapsat jako rozklad (součin) lokálních rozložení:

\mathrm {P} (V_{1},\ldots ,V_{n})=\prod _{i=1}^{n}\mathrm {P} (V_{i}\mid \operatorname { rodiče} (V_{i})).

Pokud vrchol nemá žádné předky, pak se jeho lokální rozdělení pravděpodobnosti nazývá nepodmíněné , jinak podmíněné . Pokud vrchol - náhodná proměnná obdržela hodnotu (například jako výsledek pozorování), pak se taková hodnota nazývá důkaz . Pokud byla hodnota proměnné nastavena zvenčí (a nebyla dodržena), pak se taková hodnota nazývá intervence ( anglicky action ) nebo intervence ( anglicky interference ) [1] . $V_i$

Podmíněná nezávislost v Bayesovské síti je reprezentována grafickou vlastností d-separace .

d-separace

Cesta se nazývá množina d - separovaných nebo blokovaných vrcholů tehdy a jen tehdy $p$ $Z$

$p$ obsahuje řetězec nebo větev , která patří do , nebo $i\to m\to j$ $i\gets m\to j$ $m$ $Z$
$p$ obsahuje obrácenou vidlici (kolider) takovou, že nepatří a vrchol nemá žádné potomky, které patří do . $i\to m\gets j$ $m$ $Z$ $m$ $Z$

Dovolit být neprotínající se podmnožiny vrcholů v acyklickém orientovaném grafu . O množině vrcholů se říká, že je d-oddělující právě tehdy , když blokuje všechny cesty z libovolného vrcholu, který patří k libovolnému vrcholu, který patří do , a je označen . Cesta je posloupnost po sobě jdoucích hran (libovolného směru) v grafu [1] . $X,Y,Z$ $G$ $Z$ $X$ $Y$ $Z$ $X$ $Y$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$

D-separační teorém

Pro jakékoli tři nepřekrývající se podmnožiny vrcholů v acyklickém orientovaném grafu a pro všechna rozdělení pravděpodobnosti platí následující : $(X,Y,Z)$ $G$ $P$

if , then , if a jsou Markov kompatibilní a ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $G$ $P$
jestliže vztah podmíněné nezávislosti platí pro všechna rozdělení pravděpodobnosti, která jsou Markovově kompatibilní s , pak to implikuje . ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $G$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$

Jinými slovy, pokud jsou vrcholy d-odděleny, pak jsou podmíněně nezávislé; a pokud jsou vrcholy podmíněně nezávislé ve všech rozděleních pravděpodobnosti kompatibilních s grafem , pak jsou d-separovány [1] . $G$

( znamená, že množiny proměnných a jsou pro danou množinu podmíněně nezávislé .) ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $X$ $Y$ $Z$

Důkazy

Evidence - prohlášení ve tvaru "událost nastala v uzlu x". Například: „počítač se nespustí“ .

Pravděpodobnostní dotazy

Bayesovská síť umožňuje získat odpovědi na následující typy pravděpodobnostních dotazů [2] :

zjištění pravděpodobnosti důkazů,
stanovení apriorních mezních pravděpodobností,
stanovení zadních mezních pravděpodobností, včetně:

předpovídání nebo přímá inference , - stanovení pravděpodobnosti události z pozorovatelných důvodů, diagnostika , nebo reverzní inference ( únos ), - určení pravděpodobnosti příčiny s pozorovanými následky, intercausal (smíšená) inference ( anglicky intercausal inference ) nebo transdukce , - stanovení pravděpodobnosti jedné z příčin události za předpokladu, že dojde k jedné nebo více dalším příčinám této události.

výpočet nejpravděpodobnějšího vysvětlení pozorované události ( anglicky nejpravděpodobnější vysvětlení , MPE ),
výpočet aposteriorního maxima ( angl. maximum a-posteriori, MAP ).

Příklad

Předpokládejme, že mohou existovat dva důvody, proč může tráva zvlhnout (GRASS WET): postřikovač fungoval nebo pršelo. Předpokládejte také, že déšť ovlivňuje činnost sprinkleru (během deště se jednotka nezapne). Pak lze situaci modelovat ilustrovanou Bayesovou sítí. Každá ze tří proměnných může nabývat pouze jedné ze dvou možných hodnot: T (pravda - pravda) a F (nepravda - nepravda), s pravděpodobnostmi uvedenými v tabulkách na obrázku.

Společná pravděpodobnostní funkce:

$\mathrm {P} (G,S,R)=\mathrm {P} (G\mid S,R)\cdot \mathrm {P} (S\mid R)\cdot \mathrm {P} ( R)$

kde tři názvy proměnných znamenají G = Mokrá tráva , S = Sprinkler a R = Déšť .

Model umí odpovědět na otázky typu "Jaká je pravděpodobnost, že pršelo, když je mokrá tráva?" pomocí vzorce podmíněné pravděpodobnosti a sečtením proměnných:

{\mathrm P}({\mathit {R}}=T\mid {\mathit {G}}=T)={\frac {{\mathrm P}({\mathit {G}}=T,{\ mathit {R}}=T)}{{\mathrm P}({\mathit {G}}=T)))={\frac {\sum _{({\mathit {S}}\in \{T ,F\}}}{\mathrm P}({\mathit {G}}=T,{\mathit {S}},{\mathit {R}}=T)}{\součet _{({\mathit {S)),{\mathit {R}}\in \{T,F\}}}{\mathrm P}({\mathit {G}}=T,{\mathit {S}},{\mathit {R}})))}}

={\frac {(0,99\krát 0,01\krát 0,2=0,00198_{TTT})+(0,8\krát 0,99\krát 0,2=0,1584_{TFT})}{0,00198_{TTT}+0,288 TTF}+0,1584_{TFT}+0_{TFF}}}\přibližně 35,77\%.

Pravděpodobnostní závěr

Protože Bayesovská síť je kompletní model pro proměnné a jejich vztahy, lze ji použít k zodpovězení pravděpodobnostních otázek. Síť lze například použít k získání nových znalostí o stavu podmnožiny proměnných pozorováním jiných proměnných ( evidence variables ). Tento proces výpočtu zadní distribuce proměnných nad proměnnými důkazů se nazývá pravděpodobnostní inference. Tento důsledek nám poskytuje univerzální odhad pro aplikace, kde potřebujeme zvolit hodnoty podmnožiny proměnných, které minimalizují ztrátovou funkci, například pravděpodobnost chybného rozhodnutí. Bayesovskou síť lze také považovat za mechanismus pro automatické vytváření rozšíření Bayesova teorému pro složitější problémy.

K provádění pravděpodobnostní inference v Bayesových sítích se používají následující algoritmy [1] [3] :

Přesný:
- vyvození hrubé síly marginalizací plné společné distribuce;
- variabilní eliminační algoritmy a symbolické výpočty,
- shlukování,
- algoritmy pro šíření (přenos) zpráv mezi uzly sítě,
Přibližné hodnoty založené na metodě Monte Carlo :
- vzorkovací algoritmy s vyloučením,
- metoda vzorkování založená na pravděpodobnosti,
- Algoritmus MCMS ( Ing. Markov chain Monte Carlo ) atd.

Aplikace

Bayesovské sítě se používají pro modelování v bioinformatice ( genetické sítě , struktura proteinů ), medicíně , klasifikaci dokumentů , zpracování obrazu , zpracování dat , strojovém učení a systémech podpory rozhodování .

Další informace

Association for Uncertainty in Artificial Intelligence: http://www.auai.org/ Archivováno 2. června 2007 na Wayback Machine
Úvod do Bayesian Networks: http://www.niedermayer.ca/papers/bayesian/bayes.html Archivováno 21. května 2017 na Wayback Machine
On-line výukový program o Bayesovských sítích a pravděpodobnosti: http://www.dcs.qmw.ac.uk/%7Enorman/BBNs/BBNs.htm Archivováno 4. května 2009 na Wayback Machine
Sergej Nikolenko. Přednášky č. 8 Archivováno 29. prosince 2009 na Wayback Machine , #9 Archivováno 1. ledna 2015 na Wayback Machine a #10 Archivováno 1. ledna 2015 na Wayback Machine , na Bayesiánských sítích víry. Kurz "Samoučící se systémy"

Svobodný a otevřený software

OpenBayes https://github.com/abyssknight/OpenBayes-Fork (obsahuje opravené sestavení OpenBayes z openbayes.org)
RISO: http://sourceforge.net/projects/riso/ Archivováno 4. března 2007 na Wayback Machine (distribuované sítě víry)
BANSY3 Archivováno 20. července 2011 na Wayback Machine - Freeware. Z Laboratoře nelineární dynamiky. Katedra matematiky, Science School, UNAM.
SamIam: http://reasoning.cs.ucla.edu/samiam Archivováno 24. dubna 2007 na Wayback Machine

Komerční softwarové produkty

Síťový nástroj AgenaRisk Bayesian: http://www.agenarisk.com Archivováno 16. března 2022 na Wayback Machine
BayesFusion (GeNIe and SMILE): https://www.bayesfusion.com/ Archivováno 29. listopadu 2018 na Wayback Machine
Bayesovská knihovna síťových aplikací: http://www.norsys.com/netlibrary/index.htm Archivováno 11. června 2007 na Wayback Machine
Bayesia: http://www.bayesia.com Archivováno 8. března 2022 na Wayback Machine
Hugin: http://www.hugin.com Archivováno 30. května 2020 na Wayback Machine
Netica: http://www.norsys.com Archivováno 20. května 2007 na Wayback Machine
BNet: http://www.cra.com/bnet Archivováno 5. července 2008 na Wayback Machine
Dezide: http://www.dezide.com Archivováno 8. března 2022 na Wayback Machine
MSBNx: sada nástrojů zaměřená na komponenty pro modelování a odvození s Bayesian Network (od společnosti Microsoft Research ): https://www.microsoft.com/en-us/download/details.aspx?id=52299 Archivováno 29. listopadu 2018 na Wayback Stroj
Bayes Net Toolbox pro Matlab: http://bnt.sourceforge.net/ Archivováno 10. května 2007 na Wayback Machine
dVelox: http://www.apara.es/en/about-apara-predictive-analytics Archivováno 29. listopadu 2018 na Wayback Machine
SIAM & Causeway: https://web.archive.org/web/20070221060515/http://www.inet.saic.com/

Viz také

Poznámky

↑ 1 2 3 4 5 6 Judea Pearl. Kauzalita: Modely, uvažování a vyvozování. - 2. vydání. - Cambridge University Press, 2009. - 464 s. — ISBN 9780521895606 .
↑ Adnan Darwiche. Modelování a uvažování s Bayesovskými sítěmi. - Cambridge University Press, 2009. - 526 s. — ISBN 978-0521884389 .
↑ Stuart Russell, Peter Norvig. Umělá inteligence: Moderní přístup (AIMA): [přel. z angličtiny]. - 2. vyd. - M.: Williams, 2005. - 1424 s.

Odkazy

Jensen, Finn V. Bayesovské sítě a rozhodovací grafy . — Springer , 2001.
Judea Pearl, Stuart Russell. Bayesovské sítě. UCLA Cognitive Systems Laboratory, Technická zpráva (R-277), listopad 2000.
Judea Pearl, Stuart Russell. Bayesian Networks, v M. A. Arbib (ed.), Příručka teorie mozku a neuronových sítí , str. 157-160, Cambridge, MA: MIT Press , 2003, ISBN 0-262-01197-2 .
Neil M, Fenton N, Tailor M, "Using Bayesian Networks k modelování očekávaných a neočekávaných provozních ztrát", Analýza rizik: An International Journal, Vol 25(4), 963-972, 2005. http://www.dcs.qmul .ac.uk/~norman/papers/oprisk.pdf Archivováno 27. září 2007 na Wayback Machine
Enrique Castillo, José Manuel Gutierrez a Ali S. Hadi. Expertní systémy a pravděpodobnostní síťové modely . New York: Springer-Verlag , 1997. ISBN 0-387-94858-9
Fenton NE a Neil M, "Kombinování důkazů v analýze rizik pomocí Bayesian Networks." https://web.archive.org/web/20070927153751/https://www.dcs.qmul.ac.uk/~norman/papers/Combining%20evidence%20in%20risk%20analysis%20using%20BNs.pdf
Judea Pearl. Fúze, propagace a strukturování v sítích přesvědčení. Umělá inteligence 29 (3): 241-288, 1986.
Pearl, Judea . Pravděpodobnostní usuzování v inteligentních systémech . - Morgan Kaufmann , 1988. - ISBN 0-934613-73-7 .
Judea Pearl. kauzalita. 2000.
JW Comley a DL Dowe archivovali 12. února 2006 na Wayback Machine , „ Minimální délka zprávy, MDL a zobecněné bayesovské sítě s asymetrickými jazyky archivované 4. srpna 2016 na Wayback Machine “, kapitola 11 (str . 265 Archivováno 27. září 2016 na Wayback Machine - 294 Archivováno 27. září 2016 ve Wayback Machine ) v P. Grunwald, MA Pitt a IJ Myung (eds.), Pokroky v minimální délce popisu: Teorie a aplikace Archivováno 19. června 2006 ve Wayback Machine , Cambridge, MA: MIT Press , duben 2005, ISBN 0-262-07262-9 . (Tento článek vkládá rozhodovací stromy do interních uzlů Bayesových sítí pomocí minimální délky zprávy Archivováno 9. února 2006 na Wayback Machine ( MML ). Starší verze je Comley a Dowe (2003) Archivováno 4. srpna 2016 na Wayback Machine , . pdf Archivováno 10. února 2006 na Wayback Machine .)
Christian Borgelt a Rudolf Kruse. Grafické modely – metody pro analýzu dat a těžbu archivované 10. června 2007 na Wayback Machine , Chichester, UK: Wiley , 2002, ISBN 0-470-84337-3
Korb, Kevin B.; Ann E Nicholsonová. Bayesovská umělá inteligence . - CRC Press , 2004. - ISBN 1-58488-387-1 . Archivováno 10. dubna 2007 na Wayback Machine
Nevin Lianwen Zhang Archivováno 7. června 2007 na Wayback Machine a David Poole Archivováno 10. června 2007 na Wayback Machine , Jednoduchý přístup k bayesovským síťovým výpočtům Archivováno 17. dubna 2007 na Wayback Machine , Proceedings of the Tenth Biennial Conference Canadian Artificial Intelificial -94), Banff, květen 1994, 171-178. Tento článek představuje eliminaci proměnné pro sítě přesvědčení.
David Heckerman Archivováno 30. května 2007 na Wayback Machine , Výukový program pro učení s Bayesian Networks Archivováno 19. července 2006 na Wayback Machine . In Learning in Graphical Models, M. Jordan, ed. MIT Press, Cambridge, MA, 1999. Také se objevuje jako technická zpráva MSR-TR-95-06, Microsoft Research, březen 1995. Dřívější verze se objevuje jako Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, 1:79- 119, 1997. Článek je o učení parametrů i struktury v Bayesovských sítích.

Slovníky a encyklopedie	velká čínština Britannica (online)

Grafové pravděpodobnostní modely
Bayesovská síť Kauzální Bayesovská síť Markovská síť Skrytý Markovův model

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-síť Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG