Rete bayesiana

Natura	Modello grafico
Chiamato in riferimento a	Thomas bayes

In informatica e statistica , una rete bayesiana è un modello grafico probabilistico che rappresenta un insieme di variabili casuali sotto forma di un grafo diretto aciclico . Intuitivamente, una rete bayesiana è sia:

un modello di rappresentazione della conoscenza ;
un "calcolatore" di probabilità condizionali
una base per i sistemi di supporto decisionale

Per un dato dominio (ad esempio medico), si descrivono le relazioni causali tra variabili di interesse mediante un grafo . In questo grafico, le relazioni di causa ed effetto tra le variabili non sono deterministiche, ma probabilizzate . Pertanto, l'osservazione di una o più cause non produce sistematicamente l'effetto o gli effetti che da essa dipendono, ma modifica solo la probabilità di osservarli.

Il particolare interesse delle reti bayesiane è che tengono contemporaneamente conto della conoscenza a priori degli esperti (nel grafico) e dell'esperienza contenuta nei dati.

Le reti bayesiane sono utilizzate principalmente per la diagnostica (medica e industriale ), l'analisi dei rischi, il rilevamento dello spam e il data mining .

Intuizione

Un esempio nella modellazione del rischio

Un operatore che lavora su una macchina rischia di ferirsi se utilizzata in modo improprio. Questo rischio dipende dall'esperienza dell'operatore e dalla complessità della macchina. “Esperienza” e “Complessità” sono due fattori determinanti di questo rischio (fig. 1).

Naturalmente, questi fattori non consentono di creare un modello deterministico. Anche se l'operatore è esperto e la macchina semplice, è comunque possibile un incidente. Altri fattori possono avere un ruolo: l'operatore può essere stanco, disturbato, ecc. Il verificarsi del rischio è sempre casuale, ma la probabilità di accadimento dipende dai fattori individuati.

La figura 1 di seguito rappresenta la struttura causale di questo modello (grafico).

La figura 2 rappresenta la probabilità di dipendenza: vediamo che la probabilità di incidente aumenta se l'utente non è molto esperto o se la macchina è complessa.

Vediamo qui come integrare conoscenze specialistiche (i fattori determinanti) e dati (ad esempio, la tabella della probabilità di incidente secondo le determinanti può provenire dalle statistiche).

Costruire reti bayesiane

Costruire una rete bayesiana è quindi:

definire il grafico del modello;
definire le tabelle di probabilità per ciascuna variabile, condizionatamente alle sue cause.

Il grafico è anche chiamato "struttura" del modello e la probabilità ne tabula i "parametri". Struttura e parametri possono essere forniti da esperti o calcolati dai dati, sebbene in generale la struttura sia definita da esperti e i parametri calcolati da dati sperimentali.

Utilizzando una rete bayesiana

L'utilizzo di una rete bayesiana è chiamato " inferenza ". La rete bayesiana è quindi veramente un "calcolatore di probabilità condizionale". Sulla base delle informazioni osservate, viene calcolata la probabilità dei dati non osservati. Ad esempio, a seconda dei sintomi di un paziente, vengono calcolate le probabilità delle varie patologie compatibili con questi sintomi. Possiamo anche calcolare la probabilità di sintomi non osservati e dedurre gli esami aggiuntivi più interessanti.

Definizione formale

Legge della probabilità congiunta

Esistono diversi modi per definire una rete bayesiana. Il più semplice esprime la legge di probabilità congiunta sull'insieme di variabili casuali modellate nella rete. Una rete bayesiana è un grafo diretto aciclico G = (V, E) con V l'insieme dei nodi nella rete ed E l'insieme degli archi. Ad ogni nodo x appartenente a V del grafo è associata la seguente distribuzione di probabilità condizionata:

P (x \, {\ big |} \, \ operatorname {pa} (x)) \,

dove pa (x) rappresenta i genitori immediati di x in V

L'insieme V è quindi un insieme discreto di variabili casuali. Ogni nodo di V è condizionatamente indipendente dai suoi non discendenti, dati i suoi genitori immediati. È così possibile fattorizzare le distribuzioni di probabilità condizionate su tutte le variabili rendendone il prodotto:

{\ displaystyle P (V) = \ prod _ {x \ in V} P {\ big (} x \, {\ big |} \, \ operatorname {pa} (x) {\ big)}}

Questo risultato è talvolta indicato con JPD, per la distribuzione di probabilità congiunta. Questa definizione può essere trovata nell'articolo Reti bayesiane: un modello di memoria autoattivata per il ragionamento probatorio , dove Judea Pearl introduce il termine "rete bayesiana".

Nell'esempio riportato in figura 1, la probabilità congiunta è uguale a:

P (esperienza \, operatore) \ times P (complessità \, macchina) \ volte P (incidente \, {\ big |} \, esperienza \, operatore, complessità \, macchina)

Proprietà globale di Markov

Un altro modo per definire una rete bayesiana è valutare se un grafo diretto aciclico G = (V, E) soddisfa la proprietà Markov globale (chiamata qui diretta, a causa della natura di G) data una legge di probabilità P sull'insieme di variabili V Siano X, Y, S tre sottoinsiemi di V, tali che X e Y sono separati da S, denotati (X | S | Y): la proprietà Markov globale esprime l'indipendenza condizionale tra X e Y, cioè X è indipendente da Y condizionale su S. Formalmente, la proprietà in un grafo orientato è la seguente:

\ forall \, X, Y, S \ sottoinsieme Vdisjoints, (X | S | Y) \ Rightarrow X \ perp \! \! \! \ perp Y \, {\ big |} \, S

È opportuno definire d-separazione, per "separazione diretta" o "separazione orientata", in un grafo orientato. I sottoinsiemi X e Y sono separati da S se e solo se una qualsiasi catena di nodi da X a Y è "bloccata" da S. Per tre nodi x appartenenti a X, y appartenenti a Y e s appartenenti a S, un canale è bloccato nei due casi seguenti:

o la stringa contiene una sequenza o ; $x \ rightarrow s \ rightarrow y$ $x \ leftarrow s \ rightarrow y$
o la catena contiene una sequenza in cui z non appartiene a S e nessun discendente di z appartiene a S. $x \ rightarrow z \ leftarrow y$

L'intuizione è che S “blocca” l'informazione tra X e Y.

Infine, l'indipendenza condizionale, annotata sopra , esprime che X è condizionatamente indipendente da Y dato S. Formalmente: $X \ perp \! \! \! \ Perp Y \, {\ big |} \, S$

X \ perp \! \! \! \ Perp Y \, {\ big |} \, S

se e solo se e

P (X \, {\ big |} \, Y, S) = P (X \, {\ big |} \, S)

P (Y \, {\ big |} \, X, S) = P (Y \, {\ big |} \, S)

O se e solo se

X \ perp \! \! \! \ Perp Y \, {\ big |} \, S

P (X, Y \, {\ big |} \, S) = P (X \, {\ big |} \, S) \ times P (Y \, {\ big |} \, S)

Nell'esempio sopra riportato (figura 1), possiamo scrivere che l'esperienza dell'operatore è indipendente dalla complessità della macchina, ma che dipende condizionatamente dalla complessità della macchina dato il rischio di incidente.

In conclusione, un grafo diretto aciclico G = (V, E) è una rete bayesiana se e solo se soddisfa la proprietà di Markov globale orientata data una legge di probabilità P sull'insieme di variabili V.

Inferenza

Definizione e complessità

L' inferenza in una rete bayesiana è il calcolo delle probabilità a posteriori nella rete, date le nuove informazioni osservate. Questo è un problema computazionale perché, grazie alle operazioni di probabilità e al teorema di Bayes , è possibile calcolare tutte le possibili probabilità a posteriori in una rete. Quindi, dato un insieme di evidenze (di variabili istanziate) Y, il problema dell'inferenza in G = (V, E) è quello di calcolare con . Se Y è vuoto (nessuna prova), ciò equivale a calcolare P (X). Intuitivamente, si tratta di rispondere a una domanda di probabilità sulla rete. $P (X | Y)$ $X \ sottoinsieme V, Y \ sottoinsieme V$

Sebbene il problema dell'inferenza dipenda dalla complessità della rete (più semplice è la topologia della rete, più facile è l'inferenza), è stato dimostrato da GF Cooper nel 1987 che nel caso generale si tratta di "un problema NP-difficile " . Inoltre, Dagum e Luby hanno anche dimostrato nel 1993 che trovare un'approssimazione di un problema di inferenza in una rete bayesiana è anche NP-difficile. Come risultato di questi risultati, due categorie principali di algoritmi di inferenza vengono naturalmente: algoritmi di inferenza esatta, che calcolano probabilità a posteriori generalmente in tempo esponenziale, ed euristiche che forniscono piuttosto un'approssimazione delle distribuzioni a posteriori, ma con minore complessità computazionale. Più rigorosamente, gli algoritmi di inferenza esatta forniscono un risultato e la prova che il risultato è esatto, mentre l'euristica fornisce un risultato senza prova della sua qualità (cioè a seconda dell'istanza, un'euristica può anche trovare la soluzione esatta rispetto a un'approssimazione molto approssimativa).

La classificazione del problema di inferenza come NP-hard è quindi un risultato essenziale. Per stabilire la sua dimostrazione, Cooper considera il problema generale P (X = x)> 0: è la probabilità che la variabile X assuma il valore x maggiore di zero in una rete bayesiana? Questo è un problema decisionale (la risposta è sì o no). Cooper mostra innanzitutto che se il problema P (X = x)> 0 è NP-completo, allora P (X = x) è NP-difficile, e quindi il problema di inferenza nelle reti bayesiane è NP- difficile. Per dimostrare la completezza NP di P (X = x)> 0, riduce polinomialmente il problema 3-SAT (un classico problema NP-completo) al problema P (X = x)> 0: in primo luogo, mostra che il la costruzione di una rete bayesiana da un'istanza di 3-SAT, indicata con C, può essere realizzata con complessità polinomiale; quindi, mostra che C è soddisfatto se e solo se P (X = x)> 0 è vero. Ne consegue che P (X = x)> 0 è NP-completo.

Inferenza esatta

Inferenza approssimativa

Apprendimento automatico

L' apprendimento automatico si riferisce a metodi allo scopo di estrarre le informazioni contenute nei dati. Si tratta di processi di intelligenza artificiale perché consentono a un sistema di evolversi in modo autonomo a partire da dati empirici. Nelle reti bayesiane, l'apprendimento automatico può essere utilizzato in due modi: per stimare la struttura di una rete o per stimare le tabelle di probabilità di una rete, in entrambi i casi dai dati.

Parametri di apprendimento

Imparare la struttura

Esistono due famiglie principali di approcci per apprendere la struttura di una rete bayesiana dai dati:

Approcci basati su vincoli. Il principio è testare l'indipendenza condizionale e cercare una struttura di rete coerente con le dipendenze e l'indipendenza osservate.

Approcci utilizzando una funzione di punteggio. In questi approcci, un punteggio è associato a ciascuna rete candidata, misurando l'adeguatezza delle (in) dipendenze codificate nella rete con i dati. Quindi cerchiamo una rete che massimizzi questo punteggio.

Varianti

Rete bayesiana dinamica

Una rete bayesiana dinamica o temporale (spesso nota come RBN, o DBN per Dynamic Bayesian Network ) è un'estensione di una rete bayesiana che consente di rappresentare l'evoluzione di variabili casuali in funzione di una sequenza discreta, ad esempio passi temporali. Il termine dinamico caratterizza il sistema modellato e non la rete che non cambia. Ad esempio, partendo dalla rete data in FIG.1, il sistema potrebbe essere dinamizzato esprimendo che il rischio futuro di incidente dipende dal rischio di incidente passato e presente. L'intuizione è che più si susseguono gli utenti meno esperti, più aumenta il rischio di infortunio; al contrario, un susseguirsi di utenti esperti riduce questo rischio nel tempo. In questo esempio, si dice che la variabile "incidente" sia dinamica, temporale o persistente.

Formalmente, una rete bayesiana dinamica è definita come una coppia . è una classica rete bayesiana che rappresenta la distribuzione a priori (o iniziale) di variabili casuali; detto in modo più intuitivo, è il tempo 0. è una rete bayesiana dinamica con due fasi temporali che descrivono la transizione dalla fase temporale t-1 alla fase temporale t , cioè per qualsiasi nodo appartenente a , in un grafo diretto aciclico come introdotto sopra. La probabilità congiunta di una fase temporale viene quindi scritta: $(B_ {1}, B _ {{2d}})$ $B_1$ $B _ {{2d}}$ $P (x_ {t} \, {\ big |} \, x _ {{t-1}})$ $X$ $V$ $G = (V, E)$

P (V _ {{t}} \, {\ big |} \, V _ {{t-1}}) = \ prod _ {{x \ in V}} P (x _ {{t}} \ , {\ big |} \, \ operatorname {pa} (x _ {{t}})) \,

I genitori di un nodo, annotati per la registrazione , possono quindi essere un genitore diretto nella rete al tempo t o un genitore diretto al tempo t-1 . $\ operatorname {pa} (x _ {{t}})$

La legge di probabilità congiunta fattorizzata viene calcolata “svolgendo” la rete sulla sequenza temporale, a condizione che se ne conosca la lunghezza, che sarà qui annotata . Formalmente, se è la probabilità congiunta della rete iniziale , quindi al passo temporale 0, possiamo scrivere: $T$ $P (V _ {{0}})$ $B_1$

P (V _ {{0: T}}) = P (V _ {{0}}) \ times P (V _ {{1: T}}) = \ prod _ {{x \ in V}} P (x_ {{0}} \, {\ big |} \, \ operatorname {pa} (x _ {{0}})) \ times \ prod _ {{t = 1}} ^ {T} \ prod _ {{x \ in V}} P (x _ {{t}} \, {\ big |} \, \ operatorname {pa} (x _ {{t}}))

Una rete bayesiana dinamica rispetta quindi la proprietà di Markov , che esprime che le distribuzioni condizionate al tempo t dipendono solo dallo stato al tempo t-1 in un processo stocastico . Le reti bayesiane dinamiche sono una generalizzazione di modelli probabilistici di serie temporali come il modello di Markov nascosto , il filtro di Kalman ...

Classificatore bayesiano ingenuo

Un classificatore bayesiano ingenuo è un tipo di classificatore lineare che può invece essere definito come una semplificazione delle reti bayesiane. La loro struttura è infatti costituita da due soli livelli: un primo comprendente un solo nodo, ad esempio notato , e il secondo più nodi aventi un solo genitore . Si dice che questi modelli siano ingenui perché presumono che tutti i fili siano indipendenti l'uno dall'altro. Dati i figli di cui sopra , la legge di probabilità congiunta di un classificatore bayesiano è scritta: $VS$ $VS$ $VS$ ${\ displaystyle F_ {1} ... F_ {n}}$

{\ displaystyle P (C | F_ {1} ... F_ {n})}

Questi modelli sono particolarmente adatti per problemi di classificazione automatica , dove rappresenta le possibili classi non osservate di un dominio e le variabili osservate che caratterizzano ciascuna classe di . Un esempio potrebbe essere quello di ordinare gli individui di una popolazione in due gruppi o classi, "sani" e "malati", in base ai sintomi osservati, come la presenza di febbre, ecc. $VS$ ${\ displaystyle F_ {1} ... F_ {n}}$ $VS$

Diagramma causale

Un diagramma causale è una rete bayesiana in cui i collegamenti tra i nodi rappresentano relazioni causali. I diagrammi causali sono usati per fare inferenza causale .

Strumenti software

Software

Bayesia (commerciale)
Elvira (open source)
GeNie (codice gratuito e proprietario; GeNie è una GUI per la libreria SMILE, anch'essa gratuita e proprietaria)
Hugin (commerciale)
Netica (commerciale)
OpenBUGS (open source)
ProBayes (commerciale)
IBM SPSS (commerciale)
WinBUGS (gratuito)
Weka (gratuito e open source)

Biblioteche

Strumenti di rete bayesiana in Java (open source, libreria per JAVA )
bnlearn and deal (open source, librerie per l'apprendimento in R )
Bayes Net Toolbox for Matlab (codice gratuito per l'ambiente commerciale Matlab)
Pacchetto di apprendimento della struttura (pacchetto per la struttura di apprendimento in aggiunta a Bayes Net Toolbox)
SMILE (codice gratuito e proprietario, C ++ o JAVA)
Visual Numerics (libreria per IMSL )
aGrUM / pyAgrum: modellazione, inferenza, apprendimento, analisi causale di reti ed estensioni bayesiane ( c ++ e python gratuiti e opensource )

Appendici

Bibliografia

Patrick Naïm , Pierre-Henri Wuillemin , Philippe Leray , Olivier Pourret e Anna Becker , reti bayesiane , Eyrolles ,2011, 3 e ed. , 424 p. ( ISBN 978-2-212-04723-3 , leggi online )
(en) Adnan Darwiche , Modeling and Reasoning with Bayesian Networks , Cambridge University Press ,2009, 548 p. ( ISBN 978-0-521-88438-9 , leggi online )
(en) Uffe B. Kjaerulff e Anders L. Madsen , Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis , New York, Springer ,2007, 318 p. ( ISBN 978-0-387-74100-0 , leggi online )
(it) Timo Koski e John Noble , Bayesian Networks: An Introduction , John Wiley & Sons ,2011, 2 ° ed. , 366 p. ( ISBN 978-1-119-96495-7 , leggi in linea )
(it) Richard E. Neapolitan , Learning Bayesian networks , Pearson Prentice Hall,2004( ISBN 978-0-13-012534-7 , leggi online )
(en) Judea Pearl , Ragionamento probabilistico in sistemi intelligenti: reti di inferenza plausibile , Morgan Kaufmann ,1988, 552 p. ( ISBN 978-1-55860-479-7 , leggi in linea )
Stuart Jonathan Russell e Peter Norvig ( tradotto dall'inglese da Fabrice Popineau), Intelligenza artificiale , Parigi, Pearson Education France,2010, 3 e ed. , 1198 p. ( ISBN 978-2-7440-7455-4 , leggi online )

Riferimenti

Lepage, E., Fieschi, M., Traineau, R., Gouvernet, J., & Chastang, C. (1992). Sistema di supporto decisionale basato su un'applicazione del modello di rete bayesiana alla sorveglianza delle trasfusioni . Nuovi metodi di elaborazione delle informazioni in medicina, 5, 76-87.
Jean-Jacques Boreux , Éric Parent e Jacques Bernier , Practice of bayesian calculus , Paris / Berlin / Heidelberg etc., Springer ,2009, 333 p. ( ISBN 978-2-287-99666-5 , leggi online ) , p. 38-39
Naïm et al. 2011 , p. 90-91
(in) Judea Pearl , " Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning " , Atti della 7a Conferenza della Cognitive Science Society ,1985, p. 329–334 ( leggi in linea )
Naïm et al. 2011 , p. 86-87
David Bellot , Data fusion with bayesian networks for the modeling of dynamic systems and its application in telemedicine , University Nancy-I ,2002( leggi in linea ) , p. 68 (tesi)
Naïm et al. 2011 , p. 354-356
Russell e Norvig 2010 , p. 532
Naïm et al. 2011 , p. 93-94
(in) Nevin Lianwen Zhang , " Approccio unidirezionale ai calcoli di rete bayesiana " , Atti della 10a Conferenza canadese è l'intelligenza artificiale ,1994( leggi online )
(en) Gregory F. Cooper , “ probabilistico inferenza Utilizzando Belief Networks è NP-Hard ” , Knowledge Systems Laboratory (relazione) ,1987( leggi online ) ; (en) Gregory F. Cooper , " La complessità computazionale dell'inferenza probabilistica utilizzando reti di credenze bayesiane " , Intelligenza artificiale , vol. 42, n osso 2-3,Marzo 1990, p. 393-405 ( leggi in linea )
Kjaerulff e Madsen 2007 , p. 9
(in) Thomas Dean e Keiji Kanazawa , " A model for reasoning about causation and persistence " , Computational Intelligence , Vol. 5, n o 21989, p. 142-150 ( leggi in linea )
(a) Kevin Patrick Murphy , dinamici Bayesian Networks: Rappresentazione, inferenza e apprendimento , l'Università della California a Berkeley ( leggere online ) , p. 14-15 (tesi)
Roland Donat , Philippe Leray , Laurent Bouillaut e Patrice Aknin , " Dynamic Bayesian Networks for the Representation of Duration Models in Discrete Time ", Francophone Days on Bayesian Networks ,2008( leggi online )
(en) Nir Friedman e Moises Goldszmidt , “ Costruire classificatori usando Bayesian Networks ” , Atti del XIII congresso nazionale sulla intelligenza artificiale ,1996( leggi online )
(in) Judea Pearl , The Book of Why: The New Science of Cause and Effect , Penguin Books ,2019, 432 p. ( ISBN 978-0-14-198241-0 e 0141982411 ).