Network na Bayesian

Ang isang network na Bayesian (Ingles: Bayesian network, Bayes network, belief network o directed acyclic graphical model) ay isang probabilistikong grapikal na modelo na kumakatawan sa isang hanay ng mga randomang bariabulo at ang mga kondisyonal na dependensiya nito sa pamamagitan ng dinerektang asikling grapo(DAG). Halimbawa, ang isang network na Bayesian ay maaaring kumatawan sa probabilistikong ugnayan sa pagitan ng mga sakit at sintomas. Sa mga ibinigay na sintomas, ang network ay maaaring gamitin upang kwentahin ang mga probabilidad ng pag-iral ng iba't ibang sakit. Sa pormal na paglalawan, ang mga network na Bayesian ay mga mga dinerektang asiklikong grapo na ang mga nodo ay kumakatawan sa mga randomang bariabulo sa kahulugang Bayesian: ang mga ito ay maaaring mapagmamasdang mga kantidad, tagong bariabulo, mga hindi alam na parametro o hipotesis. Ang mga gilid nito ay kumakatawan sa mga kondisyonal na dependensiya; ang mga nodo na hindi magkadugtong ay kumakatawan sa mga bariabulong kondisyonal na independiyente sa bawat isa. Ang bawat nodo ay kaugnay ng punsiyong probalidad na kumukuha ng input ang isang partikular na hanay ng mga halaga para sa mga baribulong magulang ng nodo at nagbibigay ng probabilidad ng bariabulong kinakatawan ng nodo. Halimbawa, kung ang mga magulang ay m na boolean na bariabulo, kung gayon ang punsiyong probabilidad ay maaaring ikatawan ng isang tabla ng 2m entradad na ang bawat entradad sa bawat 2m posibleng mga kombinasyon na ang mga magulang nito ay tama o mali.

Ang mga mahusay na algoritmo ay umiiral upang magsagawa ng inperensiya at pagkatuto sa mga network na Bayesian. Ang mga network na Bayesian na nagmomodelo ng mga sekwensiya ng bariabulo(halimbawa ng mga signal ng pananalita o mga sekwensiya ng protina) ay tinatawag na mga dinamikong network na Bayesian. Ang paglalahat ng mga network na Bayesian na maaaring kumatawan at lumutas ng mga problemang pagpapasya sa ilalim ng katiyakan ay tinatawag na mga diagramang impluwensiya.

Mga depinisyon at konsepto

May ilang magkakatumbas na depinisyon ng isang network na Bayesian. Para sa lahat ng sumusund, itakda ang G = (V,E) bilang isang dinerektang asiklikong grapo(DAG) at itakda ang X = (X_v)_{v ∈ V} bilang isang hanay ng mga randomang bariabulo na may indeks na V.

Depinisyon ng paktorisasyon

Ang X ay isang network na Bayesian sa respeto ng G kung ito ay pinagsanib na punsiyong probabilidad na densidad(sa respeto ng isang sukat produkto) ay maaaring isulat bilang produkto ng mga indbidwal na punsiyong densidad na kondisyonal sa kanilang mga magulang na bariabulo: ^[1]

$p(x)=\prod _{v\in V}p{\big (}x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}{\big )}$

kung saan ang pa(v) ang hanay ng mga magulang ng v(i.e. ang mga berteks na direktang tumuturo sa v sa pamamagitan ng isang gilid).

Para sa anumang hanay ng mga randomang bariabulo, ang probabilidad ng anumang kasapi ng pinagsanib na distribusyon ay maaaring kwentahin mula sa mga kondisyonal na probabilidad gamit ang patakarang kadena ng probabilidad( sa ibinigay na pag-aayos topolohikal ng X) gaya ng sumusunod: ^[1]

$\mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} (X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n})$

Ikumpara ito sa nasa taas na depinisyon na maaaring isulat bilang:

$\mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} (X_{v}=x_{v}\mid X_{j}=x_{j}$ para sa bawat $X_{j}\,$ na magulang ng $X_{v}\,)$

Ang pagkakaiba sa pagitan ng dalawang mga ekspresyon ang kondisyonal na independensiya ng mga bariabulo mula sa anuman sa mga hindi nito inapo kung ibinigay ang mga halaga ng kanilang mga magulang na bariabulo.

Lokal na katangiang Markov

Ang X ay isang network na Bayesian sa respeto ng G kung ito ay sumasapat sa lokal na katangian markov: ang bawat bariabulo ay kondisyonal na independiyente ng mga hindi nito inapo kung ibiniga ang mga magulang na bariabulo nito: ^[2]

X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {de} (v)}\,|\,X_{\operatorname {pa} (v)}\quad {\text{para sa lahat ng}}v\in V

kung saan ang de(v) ang hanay ng mga inapo ng v.

Ito ay maaari ring ihayag sa mga terminong katulad ng unang depinisyon gaya ng

\mathrm {P} (X_{v}=x_{v}\mid X_{i}=x_{i}

para sa bawat

X_{i}\,

na hindi inapo ng

X_{v}\,)=P(X_{v}=x_{v}\mid X_{j}=x_{j}

para sa bawat

X_{j}\,

na hindi magulan ng

X_{v}\,)

Tandaan na ang hanay ng mga magulang ang pang-ilalim na hanay ng hanay ng mga hindi inapo dahil ang grapo ay asikliko.

Pagbuo ng mga network na Bayesian

Upang bumuo ng isang network na Bayesian, kalimitang unang buoin ang isang DAG na G na sa paraang naniniwala tayong ang X ay sumasapat sa lokal na katangiang Markov sa respeto ng G. Minsan, mito ay ginagawa sa pamamagitan ng sumasanhing(causal) DAG. Atin namang titiyakin ang kondisyonal na mga probabilidad na distribusyon ng bawat bariabulo sa ibinigay nitong mga magulang sa G. Sa maraming mga kaso, sa partikular sa kaso kung saan ang mga bariabulo ay diskreto, kung ating ilalarawan ang pinagsanib na distribusyon ng X na maging produkto ng mga kondisyonal na distribusyong ito, kung gayon, ang X ay isang network na Bayesian sa respeto ng G.^[3]

Blanketang Markov

Ang blanketang Markov ng isang nodo ang hanay nito ng mga kapitbahay na nodo: mga magulang nito, mga anak nito at anumang mga magulang ng mga anak nito. Ang X ay isang network na Bayesian sa respeto ng G kung ang bawat nodo ay kondisyonal na independiyente sa lahat ng iba pang mga nodo sa network sa ibinigay nitong blanketang Markov. ^[2]

paghihiwalay na d

Ang depinisyong ito ay maaaring gawing mas pangkalahatan sa pamamagitan ng paglalarawan ng separasyong "d" ng dalawang mga nodo kung saan ang d ay tumatayo para sa direksiyonal.^[4]^[5] Itakda ang P na maging landas(na maaring tumungo sa anumang direksiyon) mula sa nodong u tungo sa v. Kung gayon ang P ay sinasabing hinihiwalay na d- ng isang hanay ng mga nodong Z kung at tanging kung ang (hindi baba sa) isa sa mga sumusunod ay totoo:

Ang P ay naglalaman ng kadenang u → m → v sa paraang ang gitnang nodong m ay nasa Z
Ang P ay naglalaman ng kadenang u ← m ← v sa paraang ang gitnang nodong m ay nasa Z
Ang P ay naglalaman ng sanga(fork) na u ← m → vsa paraang ang gitnang nodong m ay nasa Z o
Ang P ay naglalaman ng binaligtad na sanga o tagabangga na u → m ← v, sa paraang ang gitnang nodong m ay wala sa Z at walang inapo ng m ang nasa Z

Kaya ang u at v ay sinasabing hinihiwalay na 'd' ng Z kung lahat ng mga landas sa pagitan nila ay hinihiwalay na 'd. Kung ang u at v ay hindi hinihiwalay na d, ang mga ito ay tinatawag na konektadong-d.

Ang X ay isang network na Bayesian sa respeto ng G kung sa bawat dalawang mga nodong u, v:

X_{u}\perp \!\!\!\perp X_{v}\,|\,X_{Z}

kung saan ang Z ay isang hanay na humihiwalay na d sa u at v. Ang blanketang Markov ang minimal na hanay ng mga nodo na humihiwalay na d sa v mula sa lahat ng iba pang mga nodo.

Mga nagsasanhing network

Bagaman ang mga network na Bayesian ay kalimitang ginagamit upang ikatawan ang sinasanhing(causal) mga ugnayan, hindi ito kailangang maging kaso: ang isang dinerektang gilid mula u tungo sa v ay hindi nag-aatas na ang X_v ay sinasanhing dependiyente sa X_u. Ito ay mapapatunayan ng katotohanan ang mga network na Bayesian sa mga grapo na:

a\longrightarrow b\longrightarrow c\qquad {\text{and}}\qquad a\longleftarrow b\longleftarrow c

ay magkatumbas: na ang ibig sabihin ay eksaktong nagtatakda ng parehong mga independiyensang hinihingi.

Ang isang sinasanhing network ay isang network na Bayesian na may hayagang hinihingi na ang mga ugnayan ay sinasanhi. Ang karagdagang mga semantiko ng sinasanhing mga network ay tumutukoy na kung ang nodong X ay aktibong sinanhi na mapunta sa isang ibinigay na estadong x(ang aksiyong isinulat bilang do(X=x)), kung gayon, ang punsiyong probabilidad na densidad ay nagbabago sa isa sa mga network na nakamit sa pamamagitan ng pagputol ng mga ugnayan mula sa mga magulang X' sa X at tinatakda ang X sa sinanhing halagang x.^[6] Kung gagamitin ang mga semantikong ito, maaaring mahulaan ang epekto ng panlabas na panghihimasok mula sa data na nakamit bago ang panghihimasok.

Halimbawa

Ipagpalagay na may dalawang mga pangyayari na maaaring magsanhi sa damo na mabasa: na ang tagatalsik(sprinkler) ay nakabukas o umuulan. Gayundin, ipagpalagay na ang ulan ay may direktang epekto sa paggamit ng tagatalsik(na kung umulan, ang tagatalsik ay karaniwang hindi nakabukas). Kung gayon ang sitwasyon ay maaaring imodelo sa isang modelong Bayesian(Tignan ang http://en.wikipedia.org/wiki/File:SimpleBayesNet.svg). Ang lahat ng mga bariabulo ay may dalawang mga posibleng halaga, T(para sa true o tama) at F (para sa false o mali).

Ang punsiyon ng pinagsanib na distribusyon ay:

\mathrm {P} (G,S,R)=\mathrm {P} (G|S,R)\mathrm {P} (S|R)\mathrm {P} (R)

kung saan ang mga pangalan ng mga bariabulo ay pinaikli sa G = Grass wet(basang damo), S = Sprinkler(tagatalsik), at R = Rain(ulan).

Ang model ay maaaring sumagot ng mga tanong gaya ng "Anong probabilidad na umuulan kung ibinigay na ang damo ay basa? sa pamamagitan ng paggamit ng kondisyonal na probabilidad at pagsusuma(sum) ng lahat ng mga panggulong bariabulo:

\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)}{\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}}}\approx 35.77\%.

Gaya ng sa halimbawa, ang numerador ay tinukoy na hayagana, ang punsiyong pinagsanib na distribusyon ay ginamit upang kwentahin ang bawat iterasyon ng punsiyong sumasyon. Sa numerador pagmamarhinalisa(marginalizing) sa ibabaw ng ${\mathit {S}}$ at sa denomindaor pagmamarhinalisa sa ibabaw ng ${\mathit {S}}$ at ${\mathit {R}}$ .

Kung sa kabilang dako, nais nating sagutin ang panghihimasok na tanong na: "Ano ang pagiging malaman na uulan, kung ibinigay na binasa natin ang damo", ang sagot ay pangangasiwaan ng pagkatapos na panghihimasok na punsiyong pagsasanib na distribusyong $\mathrm {P} (S,R|do(G=T))=P(S|R)P(R)$ na nakamit sa pamamagitan ng pag-aalis ng paktor na $\mathrm {P} (G|S,R)$ mula sa distribusyon na bago ang panghihimasok. Gaya ng inaasahan, ang pagiging malamang ng ulan ay hindi apektado ng aksiyong: $\mathrm {P} (R|do(G=T))=P(R)$ .

Kung sa karagdagan, nais nating hulaan ang epekto ng pagpihit(pagbukas) ng tagtalsik, mayroon tayong $P(R,G|do(S=T))=P(R)P(G|R,S=T)$ na ang terminong $P(S=T|R)$ ay inalis na nagpapakitang ang aksiyon ay may epekto sa damo ngunit hindi sa ulan. Ang mga prediksiyong ito ay hindi posible kung ang ilan sa mga bariabulo nito ay hindi napagmasdan gaya ng sa karamihan sa mga problema ng pagsusuri ng patakaran. Ang epekto ng aksiyong $do(x)$ ay maaari pa ring mahulaan sa tuwing ang criteriong na tinatawag na "likurang pinto"(back-door) ay nasapatan.^[6]^[7]^[8]^[9] Ito ay nagsasaad na kung ang hanay na Z ng mga nodo ay mapagmamasdan na humihiwalay na d(o humaharang) sa lahat ng mga likurang pintong landas mula X tungo sa Y, kung gayon ang $P(Y,Z|do(x))=P(Y,Z,X=x)/P(X=x|Z)$ . Ang isang landas na likurang pinto ay isa na nagwawakas sa pana(arrow) sa X. Ang mga hanay na sumasapat sa criterion na likurang pinto ay tinatawag "sapat" o "matatanggap". Halimbawa, ang hanay na Z=R ay matatanggap sa panghuhula sa epekto ng S=T sa G dahil ang R ay humihiwalay na d(lamang) sa likurang pintong landas na S←R→G. Gayunpaman, kung ang S ay hindi napagmasdan, walang ibang mga hanay na humihiwalay na d sa landas na ito at ang epekto ng pagbukas ng tagatalsik sa (S=T) sa damong (G) ay hindi mahuhulaan sa mga pasibong obserbasyon. Maaari nating sabihin na ang P(G|do(S=T)) ay hindi "natukoy". Ito ay is not "identified." Ito ay nagpapakita ng katotohanang sa kakulangan ng nanghihimasok na data, hindi natin matutukoy kung ang napagmasdanng dependensiya(pagbatay) sa pagitan ng S at G ay sanhi ng nagsasanhing koneksiyon o sanhi ng hindi totoong ugnayan na nilikha ng karaniwang sanhi na R.

Ang paggamit ng isang network na Bayesian ay maaaring makatipid ng malaking halaga ng memorya kung ang ang mga dependiyensiya sa pinagsanib na distribusyon ay kalat. halimbawa ang isang simpleng paraan ng pag-iimbak ng mga kondisyonal na probabilidad ng 10 may dalawang halagang mga bariabulo bilang isang tabla ay nangangailangan ng espasyong pag-iimbak para sa mga halagang $2^{10}=1024$ . Kung ang lokal na mga distribusyon ng hinding bariabulo ay nakasalig sa higit sa tatlong mga magulang na bariabulo, ang pagkakatawan ng network na Bayesian ay nangangailangan lamang mag-imbak nang pinakamataas na mga halagang $10*2^{3}=80$ .

Ang isang kalamangan ng mga network na Bayesian ay ito ay dahil intuitibong mas madali para sa tao na unawain ang (isang kalat na hanay) ng mga direktang dependiyensiya at mga lokal na distribusyon kesa sa buong pinagsanib na distribusyon.

Sanggunian

↑ ^1.0 ^1.1 Russell & Norvig 2003, p. 496.
↑ ^2.0 ^2.1 Russell & Norvig 2003, p. 499.
↑ Neapolitan, R.E.,Learning Bayesian Networks, Prentice Hall, Upper Saddle River, NJ, 2004
↑ Geiger, Dan; Verma, Thomas and Pearl, Judea (1990). "Identifying independence in Bayesian Networks" (PDF). Networks. 20: 507–534. Nakuha noong 6 Oktubre 2011.{{cite journal}}: CS1 maint: date auto-translated (link) CS1 maint: multiple names: mga may-akda (link)
↑ Richard Scheines, D-separation
↑ ^6.0 ^6.1 Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 0-521-77362-8.{{cite book}}: CS1 maint: date auto-translated (link)
↑ P. Spirtes and C. Glymour, "An algorithm for fast recovery of sparse causal graphs", Social Science Computer Review, Vol. 9, pages 62–72, 1991.
↑ P. Spirtes, C. Glymour, and R. Scheines, Causation, Prediction, and Search, New York: Springer-Verlag, 1993
↑ T. Verma and J. Pearl, "Equivalence and Synthesis of Causal Models," Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, (July, Cambridge, MA), pages 220–227, 1990. Reprinted in P. Bonissone, M. Henrion, L. N. Kanal and J. F. Lemmer (editors), Uncertainty in Artificial Intelligence 6, Amsterdam: Elsevier Science Publishers, B.V., pages 225–268, 1991

[FOOTNOTERussellNorvig2003496-1] 1.0 ^1.1 Russell & Norvig 2003, p. 496.

[FOOTNOTERussellNorvig2003499-2] 2.0 ^2.1 Russell & Norvig 2003, p. 499.

[3] Neapolitan, R.E.,Learning Bayesian Networks, Prentice Hall, Upper Saddle River, NJ, 2004

[4] Geiger, Dan; Verma, Thomas and Pearl, Judea (1990). "Identifying independence in Bayesian Networks" (PDF). Networks. 20: 507–534. Nakuha noong 6 Oktubre 2011.{{cite journal}}: CS1 maint: date auto-translated (link) CS1 maint: multiple names: mga may-akda (link)

[5] Richard Scheines, D-separation

[pearl2000-6] 6.0 ^6.1 Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 0-521-77362-8.{{cite book}}: CS1 maint: date auto-translated (link)

[7] P. Spirtes and C. Glymour, "An algorithm for fast recovery of sparse causal graphs", Social Science Computer Review, Vol. 9, pages 62–72, 1991.

[8] P. Spirtes, C. Glymour, and R. Scheines, Causation, Prediction, and Search, New York: Springer-Verlag, 1993

[9] T. Verma and J. Pearl, "Equivalence and Synthesis of Causal Models," Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, (July, Cambridge, MA), pages 220–227, 1990. Reprinted in P. Bonissone, M. Henrion, L. N. Kanal and J. F. Lemmer (editors), Uncertainty in Artificial Intelligence 6, Amsterdam: Elsevier Science Publishers, B.V., pages 225–268, 1991

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]