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 21:52 (23 ore fa)] – Roberto Grossi
+++ matematica:asd:asd_24:progetto_24 [16/06/2025 alle 22:14 (23 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 (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 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>
-Le variabili 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`}}):
+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>
@@ Linea 71: / Linea 71: @@
 ===== Calcolo della probabilità marginale =====
-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 da cui `e` dipende (direttamente o indirettamente), calcolare la probabilità congiunta per ciascuna, e sommare i contributi in cui `e = true`:
+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 80: / 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://
@@ Linea 101: / Linea 101: @@
 **Passaggi consigliati:**
-. Costruire una **funzione `joint_probability(assign)`** che calcola la probabilità congiunta di una configurazione.
-. Usare **visita topologica** per ordinare le variabili e garantire che ogni `P(X | parents)` 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) \). Conviene 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 141: / 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 182: / 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]]