Universitatea babeş-bolyai cluj-napoca facultatea de matematicǎ Şi informaticǎ specializarea informatică

Rețelele Bayesiene

Rețelele Bayesiene reprezintă modele grafice [17] pentru evidențierea relațiilor probabilistice ale unor variabile în medii incerte. Astfel că fiecare nod al grafului este constituit de o variabilă aleatoare, în timp ce arcele dintre noduri constituie dependențe probabilistice dintre variabilele aleatoare corespunzătoare. Aceste dependențe condiționale din cadrul grafului sunt deseori estimate prin folosirea unor metode computaționale de natură statistică.

Modelele grafice care înlocuiesc prezența arcelor cu cea a muchiilor sunt numite în general Rețele Markov, aceste prezentând o simplă definiție a independenței dintre două noduri distincte. Rețelele Bayesiene corespund unei structuri grafice diferite, denumită și graf aciclic direcționat și sunt deseori utilizate în domenii precum statistica, inteligența artificială sau învățarea automată. Această popularitate se datorează atât fundamentării matematice solide cât și posibilității de înțelegere intuitivă a acestora.

Rețelele Bayesiene obțin o performanță ridicată în cazul în care seturile de date sunt incomplete, eliminând problema predicțiilor inconsistente datorate lipsei corelațiilor dintre variabilele de intrare. De asemenea, acestea permit învățarea relațiilor cauzale care ne sunt utile în momentul în care dorim să înțelegem domeniul problemei, ajutându-ne de asemenea și la obținerea predicțiilor în condiții instabile.

Cu ajutorul tehnicilor de statistică Bayesiene, rețelele Bayesiene contribuie la formarea unui domeniu vast de cunoștințe și informații necesare oricărei analize de natură probabilistică, iar cu ajutorul celorlalte metode Bayesiene și a altor modele ne oferă o abordare eficientă pentru evitarea aglomerării datelor [19].

Pentru a scoate în evidență reprezentarea rețelelor Bayesiene, vom considera că acestea sunt alcătuite din două seturi: setul nodurilor și setul arcelor. Nodurile constituie variabile aleatoare și sunt desenate sub forma unor cercuri etichetate cu numele variabilelelor, în timp ce arcele constituie dependențe directe între aceste variabile și sunt desenate sub forma unor săgeți între noduri.

Considerând concret un arc care pornește din nodul și se termină în nodul , înțelegem faptul că valoarea variabilei depinde de valoarea variabilei , adică influențează . Astfel, nodul este numit și părintele nodului . Similar, nodul este numit și copilul nodului . Dacă abordăm însă o extensie a acestor denumiri, ne referim la setul nodurilor care pot fi obținute prin drumuri directe pornind din nodul curent ca fiind succesorii nodului respectiv, în timp ce setul nodurilor care conduc prin drumuri directe către nodul curent se numesc predecesorii acestuia. Structura unui astfel de graf aciclic, ne garantează faptul că niciunul dintre noduri nu poate fi propriul său succesor sau predecesor, condiție care este de altfel foarte importantă pentru factorizarea probabilității comune a nodurilor.

Pentru completarea acestei structuri, trebuie să specificăm și modul în care sunt descriși parametrii modelului. Aceștia se bazează pe proprietatea Markoviană, conform căreia distribuția probabilităților condiționale pentru fiecare nod în parte depinde doar de părinții acestuia. În ceea ce privește variabilele discrete aleatoare, aceste probabilități condiționale sunt deseori reprezentate sub forma unui tabel care conține pentru fiecare probabilitate locală pe care un nod copil o poate lua, valorile corespunzătoare fiecărei combinații posibile dintre nodurile părinți.

Fie un set arbitrar de variabile aleatoare, unde fiecare variabilă poate lua orice valoare din setul de valori posibile . Definim spațiul comun [13] al setului de variabile ca fiind reprezentat de următorul produs . Astfel, fiecare element din spațiul comun corespunde unei posibile atribuiri de valori din cadrul tuplului de variabile:. Distribuția probabilității peste acest spațiu se mai numește și distribuția comună a probabilităților, fiind reprezentată de către probabilitățile pentru fiecare conexiune posibilă de variabile din cadrul tuplului . Fiecare rețea Bayesiană descrie o astfel de distribuție pentru un anumit set de variabile.

Formula corespunzătoare acestor probabilități poate fi evidențiată în felul următor:

Aici, se referă la mulțimea predecesorilor imediați ai nodului , din cadrul rețelei, iar valorile vor fi ulterior trecute în tabelele probabilităților condiționale corespunzătoare nodului .

Pentru a putea evidenția mai bine conceptul de independență condițională, vom considera X, Y și Z trei valori discrete aleatoare. Spunem că X este condițional independent de Y, în raport cu Z, dacă distribuția probabilităților corespunzătoare lui X este independentă de valoarea lui Y, luând în considerare o valoare pentru Z.

Astfel, obținem următoarea formulă:, unde . Deseori scriem această formulă sub formă abreviată, astfel: . Desigur, această definiție a independenței condiționale poate fi extinsă și la seturi de variabile. Spunem deci că setul de variabile este condițional independent cu setul de variabile având în vedere setul de variabile dacă: .

Pentru a putea scoate în evidență caracteristicile rețelelor Bayesiene, prezentăm următoarea figură [17]:

P(SC=T)	P(SC=F)
0.8	0.2
P(SPO=T)	P(SPO=F)
0.02	0.98

Sport

Scaun

C	P(P=T|SC)	P(P=F|SC)
T	0.9	0.1
F	0.01	0.99

Durere

Persoană

Spate

SC	SPO	P(SPA=T|SC,SPO)			P(SPA=F|SC,SPO)
T	F	0.9			0.1
T	F	0.2			0.8
T	F	0.9			0.1
T	F	0.01			0.99
SPA			P(D=T|SPA)	P(D=F|SPA)
T			0.7	0.3
F			0. 1	0.9

Ne este prezentată o structură care scoate în evidență posibilitatea ca o anumită persoană să sufere de o afecțiune a spatelui, acest eveniment fiind reprezentat de variabila Spate (SPA). Afecțiunea respectivă poate fi datorată unor activități sportive inadecvate reprezentate de variabila Sport (SPO), precum și unor surse de odihnă neconfortabile reprezentate de variabila Scaun (SC) și poate cauza la rândul ei dureri, evidențiate de variabila Durere (D). În ultimul rând, pentru ca acest scenariu să fie relevant, este necesară prezența unei persoane care să sufere de această afecțiune, evenimentul fiind reprezentat de variabila Persoană (P). Toate aceste variabile sunt binare, adică pot fi ori adevărate, ori false.

Conform conceptului de independență abordat de rețelele Bayesiene, în cadrul figurii de mai sus pot fi observate mai multe astfel de stări. De exemplu, variabilele Scaun și Sport sunt marginal independente, însă dacă luăm în considerare și variabila Spate, atunci acestea vor deveni condițional dependente. Acest principiu conferă o factorizare compactă a distribuției comune a probabilităților, iar numărul de parametrii ai modelului este redus semnificativ, datorită distribuției multinomiale în acest caz, de la la 10.

1. Deducția în rețelele Bayesiene

Rețelele Bayesiene pot fi utilizate în deducția valorilor pentru anumite variabile țintă, în funcție de valorile observate ale altor variabile. Având în vedere faptul că se lucrează cu variabile aleatoare, de cele mai multe ori, asignarea unei singure valori ca rezultat nu va fi corectă. Scopul nostru este acela de a identifica distribuția probabilităților pentru funcțiile țintă și poate fi realizat cu ușurință, în cazul în care cunoaștem toate valorile variabilelor rămase în cadrul rețelei. Vizualizând această problemă într-o manieră mai generală, putem spune că dorim să găsim distribuția probabilităților pentru anumite variabile, luând în considerare doar un subset din variabilele rămase.

De-a lungul timpului, au fost folosite mai multe modalități de inferență, două dintre cele mai cunoscute fiind următoarele [17]:

• 
  suport predictiv pentru nodul , bazat pe evidența nodurilor conectate la acesta, prin intermediul nodurilor părinte (se mai numește și inferență de jos în sus).
  
• 
  suport diagnostic pentru nodul , bazat pe evidența nodurilor conectate la acesta prin intermediul nodurilor copii (se mai numește și inferență de sus în jos).
  

Dacă ne referim la exemplul prezentat anterior și luăm în considerare inferența de sus în jos în ceea ce privește instalarea unor scaune inconfortabile la biroul unei persoane care ulterior acuză dureri de spate, putem deduce următoarele formule:

unde:

și

Se poate observa faptul că deși ne confruntăm cu o problemă binară, determinarea distribuției comune a probabilităților are complexitatea , unde n reprezintă numărul de noduri. Această însumare a probabilităților crește deci exponențial. Pentru diminuarea acestei dificultăți au fost evidențiați câțiva algoritmi eficienți, care să realizeze o deducție exactă, restricționată doar la anumite clase ale rețelei. Cel mai popular algoritm de acest gen se numește algoritmul de trimitere a mesajelor [17] și reușește să rezolve problema în pași (adică obținem de această dată o complexitate lineară) pentru rețelele în care există cel mult un drum între oricare două noduri.

În literatură, au fost de asemenea abordate metode de inferență aproximată, precum Simplifcarea Monte Carlo care îmbunătățește treptat estimările, pe măsura observării noilor instanțe. Au fost abordate de asemenea și metode corespunzătoare Lanțurilor Markov Monte Carlo, incluzând Simplificarea Gibbs și Algoritmul Metropolis-Hastings. S-au utilizat și metode variaționale, respectiv deducții cu ajutorul buclelor, care aproximează sume mari de variabile aleatoare prin intermediul mediilor acestora.

2. Învățarea Rețelelor Bayesiene

În ceea ce privește învățarea automată, ne interesează dacă putem utiliza rețelele Bayesiene pentru îndeplinirea acestui scop, astfel încât să obținem algoritmi eficienți de învățare, în funcție de problematica abordată. Desigur, există mai multe setări inițiale pe care sistemul le poate primi, astfel încât fie cunoaștem de la început structura rețelei, fie aceasta trebuie dedusă pe baza setului de date de antrenament, iar variabilele rețelei pot fi observate pentru fiecare instanță în parte a setului de date, sau unele dintre acestea pot rămâne neobservate.

În funcție de aceste setări, comportamentul sistemului se schimbă radical, permițând astfel mutiple rezolvări ale problemei, care pot fi observate și în tabelul următor [17]:

Index	Structura rețelei Bayesiene	Observabilitatea	Metoda de învățare propusă
1	Cunoscută	Completă	Estimarea probabilității maxime
2	Cunoscută	Parțială	Algoritmul Expectation-Maximization, Metoda gradientului ascendent, Lanțuri Markov Monte Carlo
3	Necunoscută	Completă	Căutare în domeniul modelului
4	Necunoscută	Parțială	Algoritmul Expectation-Maximization + Căutare în domeniul modelului

În cazul în care cunoaștem de la început structura rețelei, iar variabilele sunt observate în întregime în setul de date, învățarea tabelelor cu probabilități condiționale este foarte simplă, având în vedere faptul că estimarea entităților corespunzătoare tabelelor poate fi realizată în conformitate cu regulile clasificatorului naiv Bayes.

Situația se complică însă, dacă deși cunoaștem structura sistemului, nu există posibilitatea de observare a tuturor variabilelor, în urma consultării instanțelor de antrenare. Această problemă este oarecum similară cu învățarea ponderilor pentru unitățile ascunse din cadrul rețelelor neuronale, unde nodurile de intrare și ieșire sunt date, însă valorile unităților ascunse nu sunt specificate în setul de date de antrenament.

În acest caz, se poate utiliza algoritmul Expectation maximization, pentru identificarea unei estimări locale și optime a probabilității maxime. Lanțurile Markov Monte Carlo reprezintă o abordare alternativă a celei din urmă, fiind folosită pentru estimarea parametrilor din cadrul modelului corespunzător rețelei Bayesiene. Metoda gradientului ascendent [13] reprezintă o procedură de învățare a entităților prezente în tabelele cu probabilități condiționale. Se caracterizează prin procese de căutare în cadrul domeniului ipotezelor corespunzătoare tuturor celulelor din tabele, iar funcția care este maximizată pe parcursul acestei proceduri, este reprezentată de probabilitatea a datelor de antrenament D în raport cu ipoteza h.

În cazul al treilea, când structura rețelei Bayesiene este necunoscută, însă observabilitatea variabilelor este completă, scopul este acela de a învăța un graf aciclic care să reprezinte cât mai bine informațiile, complexitatea problemei fiind însă exponențială. O abordare a rezolvării poate fi constituită de asumarea principiului conform căruia variabilele sunt condițional independente în raport cu o anumită clasă, ceea ce determină existența unui singur nod părinte comun pentru toate celelalte noduri corespunzătoare varibilelor.

În ultimul rând, când nu cunoaștem reprezentarea rețelei, iar observabilitatea variabilelor este parțială, ceea ce rămâne de făcut este să marginalizăm atât nodurile ascunse, cât și parametrii. De cele mai multe ori, acest lucru nu se poate realiza, fapt pentru care este necesară utilizarea unei aproximări asimptotice a probabilităților posterioare, numită și Criteriul de informare Bayesian [17], sau Principiul descrierii lungimii minime. O alternativă ar putea fi reprezentată de îmbinarea căutării locale cu algoritmul Expectation-Maximization, dând naștere unui alt algoritm și anume: Structural Expectation-Maximization.

3. Regula Gradientului Ascendent în Rețelele Bayesiene

Regula gradientului ascendent a fost enunțată de către Rusell (1995) și este constituită de maximizarea lui , prin urmărirea gradientului în raport cu evaluarea parametrilor care definesc tabelele cu probabilități condiționale corespunzătoare rețelei Bayesiene [13].

Fie o entitate corespunzătoare uneia dintre probabilitățile condiționale din tabel. În particular, putem spune că reprezintă probabilitatea condițională pe care variabila o ia pentru valoarea , luând în considerare părinții care au valorile reprezentate de . Gradientul expresiei este dat de către derivatele pentru fiecare . Fiecare derivată poate fi calculată astfel:

În cazul variabilelor neobservate de instanța d din setul de date de antrenament D, probabilitățile condiționale pot fi calculate luând în considerare acele variabile care au fost totuși observate de către d, prin folosirea deducției rețelelor Bayesiene.

Pentru a simplifica puțin notația, vom considera în locul . Scopul nostru este acela de a deriva gradientul definit de setul de derivate pentru fiecare i, j și k. Având în vedere faptul că instanțele d sunt independente, obținem:

După cum se poate observa, ultima expresie a fost obținută datorită ecuației generale . În continuare, vom introduce și valorile variabilelor și , unde , prin însumarea tuturor valorilor posibile ale acestora și .

Având în vedere faptul că , iar singurul termen pentru care este acela pentru care și ,obținem:

Aplicând teorema lui Bayes pentru a rescrie , obținem:

Este necesar ca ponderile să rămână probabilități valide în intervalul [0,1]. De asemenea, suma să fie 1 pentru toate valorile pe care i și j le pot lua. Pentru a satisface aceste condiții, în primul rând vom modifica fiecare pondere prin metoda gradientului ascendent, astfel:

În ecuația de mai sus, reprezintă o constantă mică, numită și rata de învățare. În al doilea rând, vom renormaliza ponderile pentru a ne asigura că acele constrângeri precizate mai sus sunt respectate. Acest proces va converge în cele din urmă la o ipoteză locală de probabilitate maximă pentru probabilitățile condiționale din rețeaua Bayesiană [13].

4. Algoritmul Expectation-Maximization

Algoritmul Espectation-Maximization (EM) are rolul de a estima parametrii din modelele probabilistice care se confruntă cu seturi de date de antrenement incomplete. Ideea generală a acestuia constă în alternarea următorilor pași [20]:

• 
  Ghicirea distribuției probabilităților pentru datele care lipsesc din modelul curent (se mai numește și Pasul E – „estimation” – în general, nu este necesară identificarea distribuției probabilistice explicit, ci se dorește găsirea unor statistici previzibile suficiente);
  
• 
  Reestimarea parametrilor modelului utilizând completările obținute în pasul precedent (se mai numește și Pasul M – „maximization” – procesul putând fi văzut ca o maximizarea a logaritmului probabilității).
  

Acest algoritm a fost introdus inițial de către Ceppellini în anul 1950, în contextul estimării frecvenței genelor, fiind aprofundat ulterior de către Hartley și Baum în contextul Modelelor Markov ascunse, unde este cunoscut ca Algoritmul Baum-Welch. Reprezintă o generalizare naturală a estimării probabilității maxime, în cazul seturilor de date incomplete.

În continuare, vom considera următoarele notații: reprezintă datele observate dintr-un set de m instanțe independente, elementele neobservate din același set de instanțe, iar setul complet de date. Elementele din Z pot fi văzute ca niște variabile aleatoare a căror distribuție probabilistică depinde de parametrii necunoscuți și de datele observate din . Vom folosi h pentru a reprezenta valorile ipotetice curente ale parametrilor și h’ pentru reprezentarea valorilor reestimate la fiecare iterație a algoritmului.

Algoritmul Expectation-Maximization caută ipoteza cu probabilitatea maximă h’ care maximizează expresia .

Pentru a înțelege concret semnificația acestei expresii, știm deja că este probabilitatea setului de date Y în raport cu ipoteza h’ . Întrucât dorim să găsim acea ipoteză h’ care maximizează o anumită funcție pentru datele existente, acest lucru poate fi obținut prin maximizarea logaritmului probabilității, adică .

În continuare, vom introduce conceptul de valoare așteptată , deoarece setul de date în sine reprezintă o variabilă aleatoare. Având în vedere faptul că Y conține și date care nu au fost observate, adică Z, este necesar să determinăm o evaluare a posibilelor valori ale lui Z în funcție de probabilitățile acestora. Cu alte cuvinte, valoarea este calculată în funcție de distribuția probabilistică peste setul de variabile aleatoare Y.

În general, această distribuție probabilistică nu este cunoscută, deoarece este determinată tocmai de către parametrii pe care încercăm să îi estimăm. În aceste sens, algoritmul Expectation-Maximization folosește ipoteza curentă h în locul parametrilor pentru estimarea distribuției. Fie ce reprezintă expresia sub forma unei funcții pentru h’, considerând că și având în vedere setul de date observate X din Y [13].

Astfel, putem relua pașii generali ai algoritmului EM prezentați anterior, abordându-i într-o manieră matematică:

• 
  Pasul E: se calculează folosind ipoteza curentă h și datele observate X pentru estimarea distribuției probabilistice peste Y:
  

• 
  Pasul M: se înlocuiește ipoteza h cu ipoteza h’ în vederea maximizării funcției:
  

În cazul în care funcția este continuă, algoritmul va converge către un punct fix al funcției probabilistice , iar dacă această funcție are un singur maxim, EM va converge către maximul global al estimării probabilității pentru . În caz contrar, ne este garantată doar convergența către un punct de maxim local.

Algoritmul Expectation-Maximization este deseori folosit în domeniul bio-informaticii, abordând probleme precum: învățarea profilelor proteice și a familiilor de ARN, descoperirea modulelor transcripționale, identificarea proteinelor și a imagisticii medicale, șamd. În fiecare caz în parte, acest algoritm oferă o modalitate simplă, ușor de implementat și eficientă pentru învățarea parametrilor unui model. Din momentul în care acești parametrii sunt cunoscuți, poate fi utilizată deducția probabilistică pentru identificarea diverselor caracteristici ale modelului (de exemplu: Cărei grupări îi aparține o anumită genă?). Astfel, EM ne oferă un mecanism simplist de învățare a parametrilor modelului, prin construirea și antrenarea unui sistem probabilistic puternic.

3.