Xarxa bayesiana

Una xarxa bayesiana, xarxa de Bayes, xarxa de creença, model de Bayes és un model en forma de graf probabilístic. Més específicament, és un model de graf estàtic. Aquest representa un conjunt de variables aleatòries i les seves dependències condicionals a través d'un graf acíclic dirigit. Per exemple, una xarxa bayesiana podria representar les relacions probabilístiques entre malalties i símptomes, la xarxa pot ser utilitzada per computar la probabilitat de la presència de diverses malalties. El seu nom deriva del matemàtic anglès del segle xviii, Thomas Bayes.

Formalment, les xarxes bayesianes són grafs dirigits acíclics, els nodes del qual representen variables aleatòries en el sentit de Bayes: aquestes poden ser quantitats observables, variables latents, paràmetres desconeguts o hipòtesis. Les arestes representen dependències condicionals, els nodes no es troben connectats representen variables que són condicionalment independents de les altres. Cada node té associat una funció de probabilitat que pren com entrada un conjunt particular de valors de les variables pares del node i retorna la probabilitat de la variable representada pel node. Per exemple, si els pares són m variables booleanes, aleshores la funció de probabilitat pot ser representada per una taula de 2 entrades: una per cada una de les possibles combinacions (vertader o fals). Idees similars poden ser aplicades a grafs no dirigits, i possiblement també cíclics, com serien les conegudes xarxes de Markov.

Existeixen algorismes eficients que porten a la inferència i l'aprenentatge en xarxes bayesianes. Les xarxes bayesianes que modelen seqüències de variables són anomenades xarxes bayesianes dinàmiques. Les generalitzacions de les xarxes bayesianes que poden representar i resoldre problemes de decisió sota la incertesa són anomenats diagrames d'influència.

Exemple

Suposem que hi ha circumstàncies que provoquen que l'herba estigui humida: que el reg automàtic estigui encès, o que estigui plovent. També suposem que la pluja té un efecte directe sobre l'ús del reg automàtic, de tal manera que quan plou el reg automàtic deixa de funcionar. Aleshores la situació pot ser modelada amb una xarxa bayesiana. Les tres variables tenen dos possibles valors, $T$ per respostes vertaderes, i $F$ per respostes falses. La funció de probabilitat conjunta és:

$P(G,S,R)=P(G|S,R)P(S|R)P(R)$

on els nombres de les variables han sigut abreujats a $G$ = herba humida, $S$ = reg automàtic activat, i $R$ = plovent.

El model pot respondre a preguntes com "Quina és la probabilitat que estigui plovent si l'herba està humida? Fent servir la fórmula de la probabilitat condicional obtenim el següent resultat:

$P(R=T|G=T)={\frac {P(G=T,R=T)}{P(G=T)}}={\frac {\sum _{S\in \{T,F\}}P(G=T,S,R=T)}{\sum _{S\in \{T,F\}}P(G=T,S,R)}}$

$={\frac {0.99\ \cdot \ 0.01\ \cdot \ 0.2\ +\ 0.8\ \cdot \ 0.99\ \cdot \ 0.2}{0.00198\ +\ 0.288\ +\ 0.1584\ +\ 0}}\approx 35.77\%$

Com està senyalat explícitament en el numerador de l'exemple, la funció de probabilitat conjunta és utilitzada per calcular cada iteració de la funció del sumatori.

Si, en canvi, volem donar resposta a la pregunta intermèdia "quina és la probabilitat que plogui si l'herba ja és humida?", la resposta es dona a partir de la post-intervenció de la funció de distribució conjunta $P(S,R|do(G=T))=P(S|R)P(R)$ obtinguda eliminant el factor $P(G|S,R)$ de la distribució de la pre-intervenció. Com era d'esperar, la probabilitat que plogui no es veu afectada per l'herba prèviament humida.

Aquestes prediccions no són factibles quan alguna de les variables no són observades, com en la gran majoria de problemes d'avaluació. L'efecte de l'acció $do(x)$ pot mantenir-se predictiu, però cada vegada un criteri anomenat, i que s'explica més endavant, "porta de darrera" és satisfet. Els estats que, si un conjunt $Z$ de nodes pot observar-se que d-separa (o que bloqueja) tots els camins de "porta de darrera" des de $X$ fins a $Y$ aleshores $P(Y,Z|do(x))={\frac {P(Y,Z,X=x)}{P(X=x|Z)}}$ . Un camí de "porta de darrera" és aquell que acaba amb una fletxa cap a la $X$ . Els conjunts que satisfan aquest criteri de "porta de darrera" són anomenats suficients o admissibles. Per exemple, el conjunt $Z=R$ és admissible per predir l'efecte de $S=T$ sobre $G$ , perquè $R$ d-separa l'únic camí de "porta de darrera" $S?R?G$ . Malgrat això, si $S$ no és observat, no hi ha cap altra conjunt que d-separi aquest camí i l'efecte d'encendre els regs automàtics ( $S=T$ ) sobre l'herba no pot ser predit des de cap de les observacions passives. Aleshores es diu que $P(G|do(S=T))$ no està identificat. Això reflexa el fet que, tot i no tenir prous dades, no es podrà determinar si la dependència observada entre $S$ i $G$ és deguda a una connexió casual o degut a una d'artificial creada a partir d'una causa comú, $R$ . Per més exemples, veure l'exemple de la paradoxa de Simpson.

Per determina si una relació causal pot identificar-se des d'una xarxa bayesiana arbitrària amb variables no observades, es poden fer servir les tres regles de "do-calculus" i provar si tots els termes do poden ser eliminats de la expressió de la relació, així conforme de la quantitat desitjada és estimable des de la freqüència de les dades.

Fer servir una xarxa bayesiana pot salvar les quantitats considerables de la memòria, si les dependències en el repartiment conjunt són limitades. per exemple, una manera útil de guardar les probabilitats condicionals de 10 variables amb dos valors com una taula, que requereix l'espai de $2^{10}=1024$ valors, seria comprovar que les distribucions locals de ninguna variable depengui de més de 3 variables pare. Si això es compleix, perquè la representació de la xarxa bayesiana només ha d'emmagatzemar un total de $10\cdot 2^{3}=80$ valors.

Una gran avantatge de fer servir xarxes bayesianes és que són intuïtivament més fàcil per un ésser humà comprendre dependències directes i distribucions locals de la distribució conjunta completa.

Inferència d'aprenentatge

Hi ha tres tasques principals en la inferència per les xarxes bayesianes.

Deducció de variables no observades

Com que una xarxa bayesiana és un model complet de variables i de les seves relacions, pot utilitzar-se per respondre les consultes de les seves probabilitats. Per exemple, una xarxa pot fer-se servir per esbrinar el coneixement actualitzat de l'estat d'un subconjunt de variables quan altres variables s'observen. Aquest procés de càlcul de la distribució posterior de les variables donada l'evidència, la qual s'anomena inferència probabilística. Aquesta última dona un estadístic universal per aplicacions de detecció, quan es vol triar els valors per la variable d'un subconjunt que minimitzen alguna funció de pèrdua esperada. Per exemple, la probabilitat d'error de decisió. D'aquesta manera, una xarxa bayesiana pot considerar-se com un mecanisme per aplicar automàticament el Teorema de Bayes a problemes complexes.

Els mètodes més comuns d'inferència exactes són:

Eliminació de variables, la qual elimina, mitjançant integració o suma, les variables no observades i no consultades una per una mitjançant la distribució de la suma sobre el producte.
Propagació en un arbre cliqué, que emmagatzema en caché el càlcul de manera que moltes variables es puguin consultar en una única vegada, i que una nova evidència es pugui propagar ràpidament.
Coneixement recursiu i búsqueda AND/OR, que permeten un equilibri espai-temps que realitza eficientment l'eliminació de variables quan es fa servir suficient espai.

Tots aquests mètodes tenen una complexitat exponencial pel que respecta a l'amplada de l'arbre. Els algorismes d'inferència aproximada que són més comuns són l'eliminació mini-cub, LBP (Loopy Belief Propagation), GBP (Generalized Belief Propagation), i d'altres mètodes variacionals.

Aprenentatge de Paràmetres

Per especificar completament una xarxa bayesiana, i per tant poder representar del tot la distribució de probabilitat conjunta, és necessari especificar per cada node de $X$ la seva distribució de probabilitat condicionada donats els seus pares. La distribució de $X$ condicionada donats els seus pares pot tenir qualsevol forma. És comú treballar amb distribucions discretes o gaussianes, ja que simplifica el càlcul. A vegades només les restriccions sobre una distribució són conegudes; un pot aleshores fer servir el principi de màxima entropia per determinar una distribució única. Anàlogament, en el context específic d'una xarxa bayesiana dinàmica, una que comúnment especifica la distribució condicional per l'evolució temporal de l'estat ocult per maximitzar la taxa d'entropia del procés estocàstic implícit. Sovint, aquestes distribucions condicionals inclouen paràmetres que són desconeguts i han d'estimar-se a partir de les dades, a vegades fent servir l'enfocament de màxima probabilitat. La maximització directa de la probabilitat (o de la probabilitat posterior) és sovint complexa quan hi ha variables no observades. Un mètode clàssic d'aquest problema és l'algorisme d'expectació-maximització, el qual alterna els valors esperats computats de les variables condicionals no observades a dades observades, amb la maximització de la probabilitat total (o posterior) suposant que prèviament els valors esperats hagin estat calculats correctament. Aquesta seria una visió més Bayesiana de tractar els paràmetres com variables no observades addicionals i per calcular la distribució posterior completa sobre tots els nodes condicionals de les dades observades, després, integrals els paràmetres. Aquest enfocament pot ser costós i portar a models de dimensions molt grans, i és per això que a la pràctica mètodes d'ajust de paràmetres clàssics són més comuns.

Aprenentatge d'Estructures

En el cas més simple, una xarxa bayesiana s'especifica per un expert i es fa servir aleshores per realitzar inferència. En altres aplicacions, la feina de definir una xarxa és massa complexa pels éssers humans. En aquest cas, l'estructura de la xarxa i dels paràmetres de les distribucions locals ha de ser apresa per les dades.

L'aprenentatge automàtic de l'estructura gràfica d'una xarxa bayesiana és un repte dins de l'aprenentatge d'una màquina. La idea és bàsicament es basa en un algorisme de recuperació desenvolupat per Rebane i Pearl l'any 1987, i es basa en la distinció entre els tres tipus possibles de triples adjacents permesos en un gràfic acíclic dirigit.

$1.X\rightarrow Y\rightarrow Z$

$2.X\leftarrow Y\rightarrow Z$

$3.X\rightarrow Y\leftarrow Z$

El tipus 1 i 2 representen les mateixes dependències, ja que $X,Z$ són independents donada $Y$ , i no són, per tant, diferenciables. El tipus 3, però, pot ser identificat de forma única, ja que $X,Z$ són independents, i tots els altres parells són dependents. Així, mentre els grafs sense fletxes són idèntics, la direccionalitat de les fletxes és parcialment identificable. La mateixa distinció s'aplica quan $X,Z$ tenen pares comuns, excepte quan un ha de condicionar primer en aquells pares. S'ha desenvolupat algorismes per determinar sistemàticament l'esquelet del graf subjacent i, a continuació, orientar totes les fletxes, direcció de les quals està dictada per les independències condicionals observades.

Un mètode alternatiu d'aprenentatge estructural utilitza l'optimització basada en cerques. Requereix d'una funció de puntuació i d'una estratègia de cerca. Una funció de puntuació comú és la probabilitat posterior de l'estructura donades unes dades d'entrenament. El requisit del temps d'una cerca exhaustiva retornant una estructura que maximitzi la puntuació és super-exponencial en el nombre de variables. Una estratègia de cerca local fa canvis incrementals destinats a millorar la puntuació de l'estructura. Un algorisme de cerca global, com la cadena de Markov Monte Carlo, pot evitar quedar atrapat en mínims locals. Friedman parla sobre l'ús de la informació mútua entre les variables i trobar una estructura que maximitza això. Es fa a mitjançant la restricció del conjunt de pares candidats a k nodes i exhaustivament busquen en el mateix.

Aplicacions

Les xarxes bayesianes es fan servir per modelar el coneixement de biologia computacional i bioinformática (xarxes reguladores de gens, l'estructura de la proteïna, la expressió de gens d'anàlisis, l'aprenentatge de epistasis a partir de conjunts de dades de GWAS), la medicina, classificació de documents, recuperació d'informació, cerca semàntica, processament d'imatges, fusió de dades, sistemes de suport de decisions, enginyeria, jocs i per la llei.

Altres aplicacions actuals és a la ciència de dades, ja que s'ajuda de taules de probabilitats condicionals respecte als nodes i ajuda als procediments i anàlisis de les dades.

Programari

En el cas del desenvolupament del Software, podem veure les següents aplicacions:

WinBUGS
OpenBUGS
GeNIe&SMILE, SMILE és una llibreria de C++ per BN e ID, i GeNIe és una GUI per ella.
Samlam
Xarxes de creencia i de decisió en Alspace.
Hugin
Netica
dVelox

Història

El terme "xarxes bayesianes" va ser encunyat per la Judea Pearl en 1985 per a posar l'accent en tres aspectes:

El caràcter sovint subjectiu de la informació d'entrada.
La dependència de condicionament de Bayes com a base per a l'actualització de la informació.
La distinció entre les maneres causals i probatori de raonament, la qual cosa subratlla Thomas Bayes en un document publicat pòstumament en 1763.

A la fi de 1980 els textos seminals anomenats Raonament Probabilístic en Sistemes Intel·ligents i Raonament Probabilístic en Sistemes Experts resumeix les propietats de les xarxes Bayesianes i va ajudar a establir les mateixes com un camp d'estudi.

Variants informals d'aquesta mena de xarxes es van utilitzar per primera vegada pel jurista John Henry Wigmore, en forma de grafs de Wigmore, per a analitzar l'evidència en un judici en 1913. Una altra variant, anomenada diagrama de rutes, va ser desenvolupada pel genetista Sewall Wright i utilitzat en ciències de la conducta i socials (en la seva majoria amb models paramètrics lineals).

Bibliografia

P. Naïm, P. Wuillemin, P. Leray, O. Pourret, A. Becker, Les réseaux bayésiens Eyrolles 2004 (en francès)
Ben-Gal, Irad (2007). Bayesian Networks (PDF). En Ruggeri, Fabrizio; Kennett, Ron S.; Faltin, Frederick W, ed. «Encyclopedia of Statistics in Quality and Reliability». Encyclopedia of Statistics in Quality and Reliability. John Wiley & Sons. ISBN 978-0-470-01861-3. doi:10.1002/9780470061572.eqr089.
Bertsch McGrayne, Sharon (2011). The Theory That Would not Die. Yale.
Borgelt, Christian; Kruse, Rudolf (marzo de 2002). Graphical Models: Methods for Data Analysis and Mining. Chichester, UK: Wiley. ISBN 0-470-84337-3.
Borsuk, Mark Edward (2008). «Ecological informatics: Bayesian networks». En Jørgensen, Sven Erik, Fath, Brian, ed. Encyclopedia of Ecology. Elsevier. ISBN 978-0-444-52033-3.
Castillo, Enrique; Gutiérrez, José Manuel; Hadi, Ali S. (1997). «Learning Bayesian Networks». Expert Systems and Probabilistic Network Models. Monographs in computer science. Nueva York: Springer-Verlag. pp. 481–528. ISBN 0-387-94858-9.
Comley, Joshua W.; Dowe, David L. (October 2003). «Minimum Message Length and Generalized Bayesian Nets with Asymmetric Languages». Escrito en Victoria, Australia. En Grünwald, Peter D.; Myung, In Jae; Pitt, Mark A., eds. Advances in Minimum Description Length: Theory and Applications. Neural information processing series. Cambridge, Massachusetts: Bradford Books (MIT Press) (publicado el April 2005). pp. 265-294. ISBN 0-262-07262-9. (This paper puts decision trees in internal nodes of Bayes networks using Minimum Message Length (MML). An earlier version is Comley and Dowe (2003), [1])
Dowe, David L. (2010). MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness, in Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics), Elsevier, ISBN 978-0-444-51862-0, pp 901-982.
Fenton, Norman; Neil, Martin E. (November 2007). Managing Risk in the Modern World: Applications of Bayesian Networks – A Knowledge Transfer Report from the London Mathematical Society and the Knowledge Transfer Network for Industrial Mathematics. Londres (Reino Unido): London Mathematical Society.
Fenton, Norman; Neil, Martin E. (23 de julio de 2004). «Combining evidence in risk analysis using Bayesian Networks» (PDF). Safety Critical Systems Club Newsletter 13 (4) (Newcastle upon Tyne, England). pp. 8-13. Archivado desde el original el 27 de septiembre de 2007.
Andrew Gelman; Donald B Rubin; Hal S Stern (2003). «Part II: Fundamentals fo Bayesian Data Analysis: Ch.5 Hierachical models». Bayesian Data Analysis. CRC Press. pp. 120-. ISBN 978-1-58488-388-3.
Heckerman, David (1 de marzo de 1995). «Tutorial on Learning with Bayesian Networks». En Jordan, Michael Irwin, ed. Learning in Graphical Models. Adaptive Computation and Machine Learning. Cambridge, Massachusetts: MIT Press (publicado el 1998). pp. 301-354. ISBN 0-262-60032-3.. :También aparece como Heckerman, David (marzo de 1997). «Bayesian Networks for Data Mining». Data Mining and Knowledge Discovery (Netherlands: Springer Netherlands) 1 (1): 79-119. ISSN 1384-5810. doi:10.1023/A:1009730122752.:Una versión reciente aparece como Technical Report MSR-TR-95-06, Microsoft Research, March 1, 1995. The paper is about both parameter and structure learning in Bayesian networks.
Jensen, Finn V; Nielsen, Thomas D. (6 de junio de 2007). Bayesian Networks and Decision Graphs. Information Science and Statistics series (2nd edición). Nueva York: Springer-Verlag. ISBN 978-0-387-68281-5.
Korb, Kevin B.; Nicholson, Ann E. (December 2010). Bayesian Artificial Intelligence. CRC Computer Science & Data Analysis (2nd edición). Boca Raton, Florida: Chapman & Hall (CRC Press). ISBN 1-58488-387-1. doi:10.1007/s10044-004-0214-5.
Lunn, D.; et al., D; Thomas, A; Best, N (2009). «The BUGS project: Evolution, critique and future directions». Statistics in Medicine 28 (25): 3049-3067. PMID 19630097. doi:10.1002/sim.3680.
Neil, Martin; Fenton, Norman E.; Tailor, Manesh (agosto de 2005). «Using Bayesian Networks to Model Expected and Unexpected Operational Losses» (pdf). En Greenberg, Michael R., ed. Risk Analysis: an International Journal (John Wiley & Sons) 25 (4): 963-972. PMID 16268944. doi:10.1111/j.1539-6924.2005.00641.x.
Pearl, Judea (septiembre de 1986). «Fusion, propagation, and structuring in belief networks». Artificial Intelligence (Elsevier) 29 (3): 241-288. ISSN 0004-3702. doi:10.1016/0004-3702(86)90072-X.
Pearl, Judea (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Representation and Reasoning Series (2nd printing edición). San Francisco: Morgan Kaufmann. ISBN 0-934613-73-7.
Pearl, Judea; Russell, Stuart (noviembre de 2002). «Bayesian Networks». En Arbib, Michael A., ed. Handbook of Brain Theory and Neural Networks. Cambridge, Massachusetts: Bradford Books (MIT Press). pp. 157-160. ISBN 0-262-01197-2.
Zhang, Nevin Lianwen; Poole, David (mayo de 1994). «A simple approach to Bayesian network computations». Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference (AI-94). (Banff, Alberta): 171-178. This paper presents variable elimination for belief networks.