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:53 (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 8: / Linea 8: @@
 ===== 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) \).
@@ 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]]