Deep dive: inferenza — enumeration vs variable elimination
Companion di
notes.mdsez. 5. Fonti:06_Incertezza.pdfslide 47–49+.
1. Enumeration fattorizzata (l’esempio delle slide)
Query P(B|j,m), nascoste E, A:
P(B|j,m) = α · P(B) · Σe P(e) · Σa P(a|B,e)·P(j|a)·P(m|a)
Il trucco Σe Σa con fattori portati fuori: P(B) esce da tutto, P(e)
esce dalla somma su a. Ma P(a|B,e)·P(j|a)·P(m|a) va ricalcolato per
ogni (e, a): con n nascoste binarie, 2^n prodotti. Spazio O(n),
tempo O(2^n).
2. Variable elimination sullo stesso esempio
Elimina A per prima (dipende solo da fattori con A):
f_A(B,e,j,m) = Σa P(a|B,e)·P(j|a)·P(m|a)
P(B|j,m) = α · P(B) · Σe P(e)·f_A(B,e,j,m)
Il fattore intermedio f_A ha scope {B,e} (4 righe) ed e’ riusato
per entrambi i valori di e senza ricalcolare i prodotti su a. Poi si
elimina E allo stesso modo. Stesso risultato, niente ripetizioni.
3. Diagramma del risparmio
Enumeration: albero di somme con sottoalberi identici ripetuti (stesso
prodotto P(j|a)P(m|a) calcolato per ogni e). VE: grafo con nodi
fattore condivisi — ogni prodotto calcolato una volta sola e referenziato.
Il memo dei fattori e’ l’analogo dei nogood di Graphplan: non ripetere
lavoro gia’ fatto.
4. Scelta dell’ordine e limiti
- Euristiche min-degree/min-fill: minimizzano la dimensione del fattore
intermedio piu’ grande. - Caso peggiore comunque esponenziale nel treewidth: VE non rende
trattabili reti dense; li’ servono approssimazioni (sampling, variational). - MAP/MPE richiedono max al posto di somme (max-product): piu’ dure perche’
max e somma non commutano liberamente.
Vedi anche: deepdive_bayes.md, deepdive_bayes_networks.md.