Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_24:progetto_24 [16/06/2025 alle 18:41 (44 ore fa)] – Roberto Grossi
+++ matematica:asd:asd_24:progetto_24 [16/06/2025 alle 22:14 (40 ore fa)] (versione attuale) – [Materiale utile] Roberto Grossi
@@ Linea 4: / Linea 4: @@
-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 (CPT o 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 dati osservati.
+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 booleane.
+  * //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.
+  * //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) \).
+  * //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).
@@ Linea 37: / Linea 37: @@
 </code>
-===== Calcolo della probabilità marginale =====
+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`}}):
-Per calcolare la probabilità marginale \( P(e = \text{true}) \), si può usare **enumerazione completa**. L'idea è quella di generare tutte le possibili configurazioni delle variabili che influenzano `e`, calcolare la probabilità congiunta per ciascuna, e sommare i casi in cui `e = true`.
+<code>
+P(a):
+  true  → 0.5
+  false → 0.5
-Esempio:
+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>
@@ Linea 50: / Linea 80: @@
 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 lette dalle CPT
+  * \( 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:**
-. Generare tutte le configurazioni booleane per le variabili \{a, b, c, d\}
-. Per ciascuna, calcolare la probabilità congiunta come prodotto dei termini
-. Sommare solo quelle in cui `e = true`
-Nota: Per ogni configurazione si usa un ordine topologico delle variabili, utile per assicurare che ogni probabilità condizionata sia ben definita. Questo permette di applicare una forma di programmazione dinamica (o memoization) dove i valori dei nodi sorgente, sono calcolati prima del nodo destinazione, senza usare la ricorsione esplicita ed evitando lo stack.
+  - 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`.
-===== Requisiti tecnici =====
+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.
-  * Il DAG della rete sarà rappresentato con `vector<vector<int64_t>> adj`.
-  * Le tabelle di probabilità condizionate saranno lette dal file `.bif` e memorizzate in strutture C++ appropriate.
-  * È consigliato l'uso di una visita topologica per ordinare le variabili nella corretta sequenza causale, per evitare la ricorsione.
-  * Il codice dovrà essere leggibile e suddiviso in funzioni coerenti.
 ===== Discussione ad alto livello sulla lettura del file .bif =====
@@ Linea 92: / Linea 136: @@
   * Per ogni `probability`, si memorizzano:
     - la variabile target;
-    - i suoi genitori (se presenti);
+    - i suoi genitori (se presenti, costituiscono l'evidenza);
     - la tabella CPT, che associa a ogni combinazione dei genitori un vettore di probabilità.
@@ Linea 133: / Linea 177: @@
 ===== Materiale utile =====
-  * Specifiche formato BIF: [[https://www.bnlearn.com/bnrepository/BIFformat.pdf]]
+  * 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]]