DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Progetto di ASD, anno accademico 2024/2025 ======

Il progetto consiste nello scrivere un programma in grado di analizzare una rete bayesiana discreta a partire da un file testuale in formato [[https://www.bnlearn.com/bnrepository/|BIF (Bayesian Interchange Format)]], calcolando le **probabilità marginali** per ogni variabile.


Le reti bayesiane sono modelli probabilistici che rappresentano un insieme di variabili aleatorie discrete e le loro dipendenze condizionate tramite un grafo aciclico orientato (DAG). Ogni nodo del grafo corrisponde a una variabile, mentre gli archi indicano relazioni di causalità o dipendenza statistica (tramite CPT = tabelle di probabilità condizionale). La probabilità marginale di un nodo esprime la sua probabilità senza dipendenza. Le reti bayesiane sono ampiamente utilizzate in ambiti come diagnosi automatica, bioinformatica, sistemi esperti, intelligenza artificiale e decision support systems, dove è fondamentale integrare conoscenze a priori con i dati osservati.

===== Obiettivi del progetto =====

  * //Parsing//: Leggere un file `.bif` che descrive una rete bayesiana con variabili aleatorie discrete e loro CPT.
  * //Build//: Costruire il grafo aciclico orientato (DAG) associato alla rete, con i nodi annotati opportunamente per l'analisi.
  * //Analyze//: Per ogni variabile \( X \), calcolare la **probabilità marginale** \( P(X = x) \) per ciascun valore \( x \in \text{dom}(X) \).
  
  Nota: Verificare che la somma delle probabilità marginali di ciascuna variabile sia 1 (entro una tolleranza numerica).

===== Struttura della rete bayesiana =====

{{:matematica:asd:asd_24:gradient.png?400|Rete bayesiana di esempio con 5 variabili}}

Nell'esempio mostrato in figura, la rete bayesiana è composta da 5 variabili:

  * `a` è un nodo sorgente.
  * `b` e `c` dipendono da `a`.
  * `d` dipende da `b` e `c`.
  * `e` dipende da `a`, `c`, e `d`.

Questo corrisponde ai seguenti archi nel grafo:

<code>
a → b
a → c
b → d
c → d
a → e
c → e
d → e
</code>

Nella figura le variabili aleatori discrete sono booleane (`true`, `false`). Le tabelle CPT corrispondenti sono le seguenti (come descritto nel file zip di esempio : {{ :matematica:asd:asd_24:gradient.zip |`gradient.bif`}}):

<code>
P(a):
  true  → 0.5
  false → 0.5

P(b | a):
  a=true:  true → 0.8, false → 0.2
  a=false: true → 0.3, false → 0.7

P(c | a):
  a=true:  true → 0.6, false → 0.4
  a=false: true → 0.2, false → 0.8

P(d | b, c):
  b=true,  c=true:  true → 0.9, false → 0.1
  b=true,  c=false: true → 0.7, false → 0.3
  b=false, c=true:  true → 0.6, false → 0.4
  b=false, c=false: true → 0.1, false → 0.9

P(e | a, c, d):
  a=true,  c=true,  d=true:  true → 0.95, false → 0.05
  a=true,  c=true,  d=false: true → 0.85, false → 0.15
  a=true,  c=false, d=true:  true → 0.75, false → 0.25
  a=true,  c=false, d=false: true → 0.50, false → 0.50
  a=false, c=true,  d=true:  true → 0.80, false → 0.20
  a=false, c=true,  d=false: true → 0.60, false → 0.40
  a=false, c=false, d=true:  true → 0.30, false → 0.70
  a=false, c=false, d=false: true → 0.10, false → 0.90
</code>

===== Calcolo della probabilità marginale =====

Per calcolare la probabilità marginale \( P(e = \text{true}) \), si può usare **l'enumerazione completa**. L'idea è quella di generare tutte le possibili configurazioni delle variabili da cui `e` dipende (direttamente o indirettamente), calcolare la probabilità congiunta per ciascuna, e sommare i contributi in cui `e = true`:

<code>
P(e = true) = ∑_{a,b,c,d}
  P(a) ⋅ P(b | a) ⋅ P(c | a) ⋅ P(d | b,c) ⋅ P(e = true | a,c,d)
</code>

Dove:
  * \( P(a) \) è la probabilità marginale di `a` (senza genitori)
  * \( P(b | a) \), \( P(c | a) \), \( P(d | b,c) \), \( P(e | a,c,d) \) sono le probabilità condizionali lette dalle CPT

//Esempio://

Supponiamo di voler calcolare \( P(e = \text{true}) \). Consideriamo una configurazione:

<code>
a = true, b = true, c = false, d = true, e = true
</code>

Il contributo alla somma sarà:

<code>
P(a) ⋅ P(b | a) ⋅ P(c | a) ⋅ P(d | b, c) ⋅ P(e = true | a, c, d)
= 0.5 ⋅ 0.8 ⋅ 0.4 ⋅ 0.7 ⋅ 0.75
= 0.084
</code>

Si ripete questo calcolo per tutte le 16 combinazioni di (a, b, c, d), calcolando ogni volta il termine \( P(a)⋅P(b|a)⋅P(c|a)⋅P(d|b,c)⋅P(e = true | a,c,d) \), e si somma il totale per ottenere \( P(e = \text{true}) \).

**Passaggi consigliati:**

  - Costruire una funzione `joint_probability(assign)` che calcola la probabilità congiunta di una configurazione.
  - Usare `visita topologica` per ordinare le variabili (a, c, b, d, e, nel nostro esempio) e garantire che ogni `P(X | evidenza )` sia ben definita.
  - Generare tutte le configurazioni delle variabili rilevanti per `e`.
  - Sommare solo quelle in cui `e = true`.

Nota: Se la rete ha n variabili booleane, l’enumerazione completa ha complessità O(2^n). Per ridurre l’overhead computazionale, è consigliato applicare una forma di programmazione dinamica (memoization), calcolando i valori delle variabili nell’ordine topologico del grafo. In questo modo, ogni nodo viene elaborato solo dopo i suoi genitori, evitando la ricorsione esplicita e l’uso dello stack di chiamate.


===== Discussione ad alto livello sulla lettura del file .bif =====

Il file `gradient.bif` descrive una rete bayesiana in formato testuale secondo lo standard BIF. Il parsing deve interpretare due tipi principali di blocchi:

  * **Blocchi `variable`**: dichiarano il nome della variabile e i suoi valori discreti (es. `true`, `false`).
  * **Blocchi `probability`**: descrivono le tabelle di probabilità condizionale (CPT) per una variabile, eventualmente condizionata dai suoi genitori.

Esempio:

<code>
variable a {
  type discrete [2] { true, false };
}

probability (b | a) {
  (true) 0.8, 0.2;
  (false) 0.3, 0.7;
}
</code>

Durante la lettura:
  * Per ogni `variable`, si memorizza:
    - il nome della variabile;
    - il numero e i nomi dei valori discreti.
  * Per ogni `probability`, si memorizzano:
    - la variabile target;
    - i suoi genitori (se presenti, costituiscono l'evidenza);
    - la tabella CPT, che associa a ogni combinazione dei genitori un vettore di probabilità.

Si consiglia di usare una struttura C++ come:

<code>
struct Variable {
    std::string name;
    std::vector<std::string> values;
    std::vector<std::string> parents;
    std::vector<std::vector<double>> cpt;
};
</code>

Le dipendenze tra variabili vanno rappresentate con un **grafo orientato aciclico (DAG)**, costruito a partire dai genitori indicati nei blocchi `probability`. Questo DAG può essere rappresentato con:

<code>
vector<vector<int64_t>> adj;
</code>

dove `adj[u]` contiene i successori della variabile con indice `u`. Per costruire questo grafo è utile mantenere una mappatura da nome a indice tramite:

<code>
unordered_map<string, int64_t> name_to_id;
</code>

Una volta completato il parsing:
  * si esegue una **visita topologica** sul DAG per ordinare le variabili in ordine causale;
  * si possono costruire tutte le configurazioni possibili e calcolare le probabilità congiunte e marginali;
  * ogni configurazione può essere rappresentata con una mappa `{nome → valore}`, e l'accesso alle CPT avviene tramite indice calcolato sulla base dei valori dei genitori.

Questa fase costituisce la base per il calcolo della probabilità marginale come richiesto nel progetto.

===== Estensioni opzionali =====

  * Calcolo di probabilità condizionate: \( P(X = x \mid E = e) \)
  * Aggiunta di evidenza da riga di comando (es. `-e a=true,c=false`)
  * Implementazione dell’eliminazione di variabili (Variable Elimination)
  
===== Materiale utile =====

  * Specifiche formato BIF: https://www.cs.cmu.edu/afs/cs/user/fgcozman/www/Research/InterchangeFormat/
  * File zip di esempio : {{ :matematica:asd:asd_24:gradient.zip |`gradient.bif`}} (basato sull'immagine fornita)
  * Repository di reti bayesiane in vari formati, incluso BIF: [[https://www.bnlearn.com/bnrepository/|repository]]
  * Documentazione: [[https://en.wikipedia.org/wiki/Bayesian_network]]