Bayesiansk netværk

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. december 2021; checks kræver 4 redigeringer .

Bayesiansk netværk (eller Bayesiansk netværk , Bayesiansk trosnetværk , engelsk Bayesiansk netværk, trosnetværk ) - graf probabilistisk model , som er et sæt af variabler og deres probabilistiske afhængigheder ifølge Bayes . For eksempel kan et Bayesiansk netværk bruges til at beregne sandsynligheden for, at en patient har en sygdom baseret på tilstedeværelsen eller fraværet af et sæt af symptomer, baseret på data om sammenhængen mellem symptomer og sygdomme. Bayesianske netværks matematiske apparat blev skabt af den amerikanske videnskabsmand Judah Pearl , vinder af Turing Award (2011).

Formelt er et Bayesiansk netværk en rettet acyklisk graf , hvor hvert toppunkt svarer til en tilfældig variabel, og buerne på grafen koder for betingede uafhængighedsrelationer mellem disse variable. Hjørner kan repræsentere variabler af enhver type, være vægtede parametre, latente variabler eller hypoteser. Der er effektive metoder, der bruges til at beregne og træne Bayesianske netværk. Hvis de bayesianske netværksvariable er diskrete tilfældige variable, så kaldes et sådant netværk et diskret bayesiansk netværk. Bayesianske netværk, der modellerer sekvenser af variabler, kaldes dynamiske Bayesianske netværk . Bayesianske netværk, der kan have både diskrete og kontinuerte variabler, kaldes hybride Bayesianske netværk . Et bayesiansk netværk, hvor buerne udover betingede uafhængighedsrelationer også koder kausalitetsrelationer , kaldes kausale bayesianske netværk [ 1] ) .

Definitioner og driftsprincipper

Hvis en bue går fra et toppunkt til et toppunkt , så kaldes det en forælder og kaldes et barn . Hvis der er en rettet vej fra toppunktet til toppunktet , så kaldes det en forfader , og det kaldes en efterkommer . $EN$ $B$ $EN$ $B$ $B$ $EN$ $EN$ $B$ $EN$ $B$ $B$ $EN$

Sættet af vertex-forældre til et toppunkt vil blive betegnet som . $V_i$ $\mathrm {forældre} (V_{i})=\mathbf {PA} _{i}$

En rettet acyklisk graf kaldes et Bayesiansk netværk for en sandsynlighedsfordeling defineret over et sæt af tilfældige variable , hvis hvert hjørne af grafen er forbundet med en tilfældig variabel fra , og buerne i grafen opfylder betingelsen (Markov betingelse [1] ): enhver variabel fra skal være betinget uafhængig af alle hjørner, der ikke er dens efterkommere, hvis alle dens direkte forældre i grafen , dvs. $G$ $P(\mathbf {v} )$ ${\mathbf {V}}$ ${\mathbf {V}}$ $V_i$ ${\mathbf {V}}$ ${\displaystyle \mathbf {PA} _{i))$ $G$

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

hvor er værdien ; - konfiguration $v_{i}$ $V_i$ ${\mathbf {s))$ [ angiv ] ; er mængden af alle toppunkter, der ikke er efterkommere af ; - konfiguration . $\mathbf {S}$ $\mathbf {S}$ $V_i$ ${\displaystyle \mathbf {pa} _{i))$ ${\displaystyle \mathbf {PA} _{i))$

Derefter kan den komplette fælles fordeling af værdier ved toppunkterne bekvemt skrives som en nedbrydning (produkt) af lokale fordelinger:

\mathrm {P} (V_{1},\ldots ,V_{n})=\prod _{i=1}^{n}\mathrm {P} (V_{i}\mid \operatorname { forældre} (V_{i})).

Hvis et toppunkt ikke har nogen forfædre, kaldes dets lokale sandsynlighedsfordeling ubetinget , ellers betinget . Hvis et toppunkt - en tilfældig variabel har modtaget en værdi (for eksempel som følge af observation), så kaldes en sådan værdi bevis . Hvis værdien af variablen blev sat udefra (og ikke observeret), så kaldes en sådan værdi intervention ( engelsk handling ) eller intervention ( engelsk intervention ) [1] . $V_i$

Betinget uafhængighed i et Bayesiansk netværk er repræsenteret af den grafiske egenskab af d-separation .

d-separation

En sti kaldes et d -separeret eller blokeret toppunktsæt hvis og kun hvis $s$ $Z$

$s$ indeholder en kæde eller gren sådan, der hører til , eller $i\to m\to j$ $i\gets m\to j$ $m$ $Z$
$s$ indeholder en omvendt gaffel (collider), sådan at den ikke hører hjemme , og toppunktet har ingen børn, der tilhører . $i\to m\gets j$ $m$ $Z$ $m$ $Z$

Lade være ikke-skærende delmængder af toppunkter i en acyklisk rettet graf . Et sæt toppunkter siges at være d-adskillende , hvis og kun hvis det blokerer alle stier fra ethvert toppunkt, der hører til ethvert toppunkt, der tilhører , og er betegnet med . En sti er en sekvens af på hinanden følgende kanter (i enhver retning) i grafen [1] . $X,Y,Z$ $G$ $Z$ $x$ $Y$ $Z$ $x$ $Y$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$

d-adskillelsessætningen

For alle tre ikke-overlappende delmængder af hjørner i en acyklisk rettet graf og for alle sandsynlighedsfordelinger gælder følgende : $(X,Y,Z)$ $G$ $P$

hvis , så , hvis og er Markov-kompatible, og ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $G$ $P$
hvis forholdet mellem betinget uafhængighed gælder for alle sandsynlighedsfordelinger, der er Markov-kompatible med , så indebærer dette . ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $G$ ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G))$

Med andre ord, hvis hjørnerne er d-adskilte, så er de betinget uafhængige; og hvis hjørnerne er betinget uafhængige i alle sandsynlighedsfordelinger, der er kompatible med grafen , så er de d-separerede [1] . $G$

( betyder, at sæt af variabler og er betinget uafhængige for et givet sæt .) ${\displaystyle (\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P))$ $x$ $Y$ $Z$

Beviser

Evidens - udsagn af formen "en hændelse fandt sted ved node x". For eksempel: "computeren vil ikke starte" .

Probabilistiske forespørgsler

Det Bayesianske netværk giver dig mulighed for at få svar på følgende typer af sandsynlighedsforespørgsler [2] :

finde sandsynligheden for beviser,
bestemmelse af a priori marginale sandsynligheder,
bestemmelse af posteriore marginale sandsynligheder, herunder:

forudsigelse eller direkte slutning , - bestemmelse af sandsynligheden for en begivenhed af observerbare årsager, diagnosticering eller omvendt slutning ( abduktion ), - bestemmelse af sandsynligheden for en årsag med observerede konsekvenser, intercausal (blandet) inferens ( engelsk intercausal inference ) eller transduktion , - bestemmelse af sandsynligheden for en af årsagerne til en begivenhed, forudsat at en eller flere andre årsager til denne begivenhed forekommer.

beregning af den mest sandsynlige forklaring på den observerede hændelse ( engelsk most probable forklaring , MPE ),
beregning af a posteriori maksimum ( eng. maximum a-posteriori, MAP ).

Eksempel

Lad os antage, at der kan være to årsager til, at græsset kan blive vådt (GRASS WET): Sprinkleren har virket, eller det har regnet. Antag også, at regn påvirker driften af sprinkleren (under regn tænder enheden ikke). Så kan situationen modelleres af det illustrerede Bayesianske netværk. Hver af de tre variable kan kun tage én af to mulige værdier: T (sand - sand) og F (falsk - falsk), med de sandsynligheder, der er angivet i tabellerne i illustrationen.

Fælles sandsynlighedsfunktion:

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

hvor de tre variabelnavne betyder G = Græs vådt , S = Sprinkler og R = Regn .

Modellen kan besvare spørgsmål som "Hvad er sandsynligheden for, at det regnede, hvis græsset er vådt?" ved at bruge den betingede sandsynlighedsformel og summere variablerne:

{\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}}\i \{T ,F\}}}{\mathrm P}({\mathit {G}}=T,{\mathit {S}},{\mathit {R}}=T)}{\sum _{({\mathit {S)),{\mathit {R}}\in \{T,F\}}}{\mathrm P}({\mathit {G}}=T,{\mathit {S}},{\mathit {R}})))}}

={\frac {(0,99\times 0,01\times 0,2=0,00198_{TTT})+(0,8\times 0,99\times 0,2=0,1584_{TFT})}{0,00198_{TTT}+0,288_ TTF}+0,1584_{TFT}+0_{TFF}}}\ca. 35,77\%.

Probabilistisk slutning

Fordi det bayesianske netværk er en komplet model for variabler og deres relationer, kan det bruges til at besvare sandsynlighedsspørgsmål. Netværket kan for eksempel bruges til at opnå ny viden om tilstanden af en delmængde af variabler ved at observere andre variable ( evidensvariable ). Denne proces med at beregne den bageste fordeling af variable over evidensvariable kaldes probabilistisk inferens. Denne konsekvens giver os et universelt estimat for applikationer, hvor vi skal vælge værdierne af en delmængde af variabler, der minimerer tabsfunktionen, for eksempel sandsynligheden for en fejlagtig beslutning. Det Bayesianske netværk kan også opfattes som en mekanisme til automatisk at bygge en udvidelse af Bayes' sætning til mere komplekse problemer.

For at udføre probabilistisk inferens i Bayesianske netværk bruges følgende algoritmer [1] [3] :

Præcis:
- brute force - slutning ved at marginalisere fuld fælles distribution;
- variable elimineringsalgoritmer og symbolske beregninger,
- klyngedannelse,
- algoritmer til udbredelse (transmission) af meddelelser mellem netværksknuder,
Approksimationer baseret på Monte Carlo-metoden :
- prøveudtagningsalgoritmer med udelukkelse,
- sandsynlighedsbaseret prøveudtagningsmetode,
- MCMS - algoritme ( Eng. Markov-kæden Monte Carlo ) osv.

Ansøgninger

Bayesianske netværk bruges til modellering inden for bioinformatik ( genetiske netværk , proteinstruktur ), medicin , dokumentklassificering , billedbehandling , databehandling , maskinlæring og beslutningsstøttesystemer .

Yderligere information

Association for Uncertainty in Artificial Intelligence: http://www.auai.org/ Arkiveret 2. juni 2007 på Wayback Machine
Introduktion til Bayesian Networks: http://www.niedermayer.ca/papers/bayesian/bayes.html Arkiveret 21. maj 2017 på Wayback Machine
Online vejledning om Bayesianske net og sandsynlighed: http://www.dcs.qmw.ac.uk/%7Enorman/BBNs/BBNs.htm Arkiveret 4. maj 2009 på Wayback Machine
Sergei Nikolenko. Foredrag #8 Arkiveret 29. december 2009 på Wayback Machine , #9 Arkiveret 1. januar 2015 på Wayback Machine og #10 Arkiveret 1. januar 2015 på Wayback Machine , på Bayesianske trosnetværk. Kursus "Selvlæringssystemer"

Gratis og open source-software

OpenBayes https://github.com/abyssknight/OpenBayes-Fork (indeholder en patched build af OpenBayes fra openbayes.org)
RISO: http://sourceforge.net/projects/riso/ Arkiveret 4. marts 2007 på Wayback Machine (distribuerede trosnetværk)
BANSY3 Arkiveret 20. juli 2011 på Wayback Machine - Freeware. Fra Non Linear Dynamics Laboratory. Matematisk afdeling, Naturvidenskabsskolen, UNAM.
SamIam: http://reasoning.cs.ucla.edu/samiam Arkiveret 24. april 2007 på Wayback Machine

Kommercielle softwareprodukter

AgenaRisk Bayesiansk netværksværktøj: http://www.agenarisk.com Arkiveret 16. marts 2022 på Wayback Machine
BayesFusion (GeNIe og SMILE): https://www.bayesfusion.com/ Arkiveret 29. november 2018 på Wayback Machine
Bayesiansk netværksapplikationsbibliotek: http://www.norsys.com/netlibrary/index.htm Arkiveret 11. juni 2007 på Wayback Machine
Bayesia: http://www.bayesia.com Arkiveret 8. marts 2022 på Wayback Machine
Hugin: http://www.hugin.com Arkiveret 30. maj 2020 på Wayback Machine
Netica: http://www.norsys.com Arkiveret 20. maj 2007 på Wayback Machine
BNet: http://www.cra.com/bnet Arkiveret 5. juli 2008 på Wayback Machine
Dezide: http://www.dezide.com Arkiveret 8. marts 2022 på Wayback Machine
MSBNx: et komponentcentreret værktøjssæt til modellering og inferens med Bayesian Network (fra Microsoft Research ): https://www.microsoft.com/en-us/download/details.aspx?id=52299 Arkiveret 29. november 2018 på Wayback Maskine
Bayes Net Toolbox til Matlab: http://bnt.sourceforge.net/ Arkiveret 10. maj 2007 på Wayback Machine
dVelox: http://www.apara.es/en/about-apara-predictive-analytics Arkiveret 29. november 2018 på Wayback Machine
SIAM & Causeway: https://web.archive.org/web/20070221060515/http://www.inet.saic.com/

Se også

Noter

↑ 1 2 3 4 5 6 Judæa Perle. Kausalitet: Modeller, ræsonnement og slutning. - 2. udgave. - Cambridge University Press, 2009. - 464 s. — ISBN 9780521895606 .
↑ Adnan Darwiche. Modellering og ræsonnement med Bayesian Networks. - Cambridge University Press, 2009. - 526 s. — ISBN 978-0521884389 .
↑ Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach (AIMA): [oversat. fra engelsk]. - 2. udg. - M .: Williams, 2005. - 1424 s.

Links

Jensen, Finn V. Bayesian Networks and Decision Graphs . — Springer , 2001.
Judea Pearl, Stuart Russell. Bayesianske netværk. UCLA Cognitive Systems Laboratory, teknisk rapport (R-277), november 2000.
Judea Pearl, Stuart Russell. Bayesian Networks, i M.A. Arbib (Ed.), Handbook of Brain Theory and Neural Networks , pp. 157-160, Cambridge, MA: MIT Press , 2003, ISBN 0-262-01197-2 .
Neil M, Fenton N, Tailor M, "Using Bayesian Networks to model Expected and Unexpected Operational Losses", Risk Analysis: An International Journal, Vol 25(4), 963-972, 2005. http://www.dcs.qmul .ac.uk/~norman/papers/oprisk.pdf Arkiveret 27. september 2007 på Wayback Machine
Enrique Castillo, José Manuel Gutierrez og Ali S. Hadi. Ekspertsystemer og probabilistiske netværksmodeller . New York: Springer-Verlag , 1997. ISBN 0-387-94858-9
Fenton NE og Neil M, "Kombinering af beviser i risikoanalyse ved hjælp af Bayesian Networks." https://web.archive.org/web/20070927153751/https://www.dcs.qmul.ac.uk/~norman/papers/Combining%20evidence%20in%20risk%20analysis%20using%20BNs.pdf
Judæa perle. Fusion, udbredelse og strukturering i trosnetværk. Artificial Intelligence 29 (3):241-288, 1986.
Perle, Judæa . Probabilistisk ræsonnement i intelligente systemer . - Morgan Kaufmann , 1988. - ISBN 0-934613-73-7 .
Judæa Perle. kausalitet. 2000.
JW Comley og DL Dowe Arkiveret 12. februar 2006 på Wayback Machine , " Minimumsmeddelelseslængde, MDL og generaliserede Bayesian Networks with Asymmetric Languages Archived 4 August 2016 at the Wayback Machine ", kapitel 11 (s . 265 Arkiveret 27. september 2016 på Wayback Machine - 294 Arkiveret 27. september 2016 på Wayback Machine ) i P. Grunwald, MA Pitt og IJ Myung (red.), Advances in Minimum Description Length: Theory and Applications Arkiveret 19. juni 2006 på Wayback Machine , Cambridge, MA: MIT Press , april 2005, ISBN 0-262-07262-9 . (Dette papir sætter beslutningstræer i interne knudepunkter i Bayes-netværk ved hjælp af Minimum Message Length Arkiveret 9. februar 2006 på Wayback Machine ( MML ). En tidligere version er Comley og Dowe (2003) Arkiveret 4. august 2016 på Wayback Machine , . pdf Arkiveret 10. februar 2006 på Wayback Machine .)
Christian Borgelt og Rudolf Kruse. Grafiske modeller - Metoder til dataanalyse og minedrift Arkiveret 10. juni 2007 på Wayback Machine , Chichester, UK: Wiley , 2002, ISBN 0-470-84337-3
Korb, Kevin B.; Ann E Nicholson. Bayesiansk kunstig intelligens . - CRC Press , 2004. - ISBN 1-58488-387-1 . Arkiveret 10. april 2007 på Wayback Machine
Nevin Lianwen Zhang Arkiveret 7. juni 2007 på Wayback Machine og David Poole Arkiveret 10. juni 2007 på Wayback Machine , En simpel tilgang til Bayesianske netværksberegninger Arkiveret 17. april 2007 på Wayback Machine , Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference (AI) -94), Banff, maj 1994, 171-178. Dette papir præsenterer variabel eliminering for trosnetværk.
David Heckerman Arkiveret 30. maj 2007 på Wayback Machine , A Tutorial on Learning with Bayesian Networks Arkiveret 19. juli 2006 på Wayback Machine . I Learning in Graphical Models, M. Jordan, red. MIT Press, Cambridge, MA, 1999. Vises også som Technical Report MSR-TR-95-06, Microsoft Research, marts, 1995. En tidligere version vises som Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, 1:79- 119, 1997. Artiklen handler om både parameter- og strukturlæring i Bayesianske netværk.

Ordbøger og encyklopædier	stor kinesisk Britannica (online)

Grafer sandsynlighedsmodeller
Bayesiansk netværk Kausalt Bayesian Network Markov netværk Skjult Markov-model

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG