Indice

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 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

Nota: Verificare che la somma delle probabilità marginali di ciascuna variabile sia 1 (entro una tolleranza numerica).

Struttura della rete bayesiana

Rete bayesiana di esempio con 5 variabili

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

Questo corrisponde ai seguenti archi nel grafo: 

a → b
a → c
b → d
c → d
a → e
c → e
d → e

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

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

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`: 

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)

Dove:

Esempio:

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

a = true, b = true, c = false, d = true, e = true

Il contributo alla somma sarà: 

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

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:

  1. Costruire una funzione `joint_probability(assign)` che calcola la probabilità congiunta di una configurazione.
  2. 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.
  3. Generare tutte le configurazioni delle variabili rilevanti per `e`.
  4. 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:

Esempio: 

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

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

Durante la lettura:

Si consiglia di usare una struttura C++ come: 

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

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: 

vector<vector<int64_t>> adj;

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

unordered_map<string, int64_t> name_to_id;

Una volta completato il parsing:

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

Estensioni opzionali

Materiale utile