Deriving Complete Constraints in Hidden Variable Models

Titolo: Derivazione di Vincoli Completi nei Modelli a Variabili Nascoste

1. Il Problema

I modelli grafici con variabili nascoste (latenti) implicano spesso vincoli sulla distribuzione osservabile che vanno oltre le semplici relazioni di indipendenza condizionale. Questi vincoli possono essere:

• Disuguaglianze: Come le "inequazioni strumentali" (Pearl, 1995).
• Uguaglianze complesse: Come i vincoli "Verma" o le indipendenze di Markov nidificate.

Il problema centrale è che, in presenza di variabili non osservate, molti di questi vincoli sono difficili da derivare e spesso non sono completi (cioè non si conoscono tutti i vincoli osservabili possibili). Metodi precedenti, come l'eliminazione algebrica delle variabili (es. Fourier-Motzkin) o la programmazione lineare intensiva (Bonet, 2001), diventano computazionalmente intrattabili per spazi di stati di dimensioni moderate o non garantiscono la completezza dei vincoli derivati. Inoltre, le caratterizzazioni basate sul "Markov nidificato" (Nested Markov) catturano solo vincoli di uguaglianza, trascurando le disuguaglianze.

L'obiettivo del paper è sviluppare un metodo sistematico per derivare l'insieme completo di vincoli osservabili (sia uguaglianze che disuguaglianze) in una classe specifica di modelli, garantendo che nessun vincolo falsificabile venga omesso.

2. Metodologia

Gli autori estendono il metodo di Bonet (2001), originariamente limitato al contesto delle variabili strumentali (IV), a una classe più ampia di modelli definiti come "lineari".

Definizioni Chiave e Pre-requisiti:

• Grafo DAG con variabili nascoste: Il modello è rappresentato da un grafo aciclico diretto $G(W, U)$, dove $W$ sono le variabili osservate (discrete e finite) e $U$ sono le variabili non osservate.
• Condizioni di Struttura: Si assume che le variabili non osservate siano esogene (senza genitori) e che ogni variabile latente abbia almeno due figli osservati distinti.
• Distretti (Districts) e c-grado: Il grafo viene partizionato in "distretti" (o componenti confondibili), ovvero insiemi di variabili osservate connessi da variabili latenti. Il c-grado di un distretto è il numero massimo di variabili latenti che agiscono come genitori comuni per le variabili in quel distretto.
• Classe "Lineare": Il metodo è completo per i grafi in cui ogni distretto ha un c-grado di 1 (cioè, al massimo una variabile latente condivisa per distretto).

L'Algoritmo Proposto:
Il metodo trasforma il problema di caratterizzazione della distribuzione marginale in un problema di geometria computazionale:

1. Identificazione delle Indipendenze: Si elencano tutte le indipendenze condizionali e marginali standard tramite d-separazione.
2. Trasformazione in Variabili di Risposta (Response Function): Per ogni distretto con c-grado 1, si applica una trasformazione che sostituisce le variabili latenti continue/arbitrarie con variabili di risposta discrete ($R_{W_i}$). Questo sfrutta il fatto che le variabili osservate sono discrete, permettendo di esprimere la distribuzione congiunta come combinazione lineare delle probabilità delle variabili di risposta.
3. Vincoli Funzionali Lineari: Si derivano equazioni lineari che collegano le probabilità osservabili (o interventionali) alle probabilità delle variabili di risposta. Questo crea un sistema $p = Br$, dove $p$ è il vettore delle probabilità osservabili, $B$ è una matrice di 0 e 1, e $r$ è il vettore delle probabilità latenti.
4. Conversione Vertice-Spazio (V-to-H): Il sistema lineare definisce un poliedro convesso nello spazio delle probabilità latenti. Utilizzando algoritmi di geometria computazionale (come il metodo della doppia descrizione implementato in librerie come cddlib), si converte la rappresentazione del poliedro da "vertici" (V-representation) a "semispazi" (H-representation).
   • Questo passaggio elimina le variabili latenti ($r$) e produce un sistema di disuguaglianze e uguaglianze lineari che coinvolgono solo le probabilità osservabili ($p$).
5. Identificazione dei Vincoli Non Banali: Si testano i vertici dello spazio delle probabilità non vincolato (il simplex) contro i vincoli derivati. Se un vincolo è violato da almeno un vertice, è considerato "non banale" (cioè impone una restrizione reale sulla distribuzione).

3. Risultati Chiave

• Completezza Teorica: Il paper dimostra che per la classe di modelli con c-grado 1, l'insieme dei vincoli derivati tramite questo algoritmo è completo. Non esistono altri vincoli osservabili (falsificabili) che non siano implicati da questo insieme.
• Vincoli di Uguaglianza e Disuguaglianza: Il metodo produce sia vincoli di uguaglianza (inclusi i vincoli Verma/Markov nidificati) sia vincoli di disuguaglianza (inequazioni strumentali generalizzate).
• Estensione a Grafi con c-grado > 1: Per grafi con c-grado superiore a 1 (es. scenario triangolare), il metodo non garantisce la completezza. Tuttavia, gli autori propongono una strategia di pre-elaborazione che fonde le variabili latenti in un'unica variabile condivisa. Questo riduce il c-grado a 1, permettendo di derivare un sottoinsieme di vincoli validi (necessari ma non sufficienti).
• Equivalenza Osservazionale: Vengono presentati teoremi (basati su lavori precedenti di Evans, Henson-Lal-Pusey, ecc.) che permettono di trasformare grafi con c-grado > 1 in grafi osservazionalmente equivalenti con c-grado 1, estendendo così l'applicabilità del metodo completo.

4. Esempi e Applicazioni

Gli autori illustrano il metodo su diversi scenari:

• Variabili Strumentali Sequenziali: Derivazione di nuove disuguaglianze per modelli IV multipli.
• Modelli Nidificati Equivalenti: Dimostrazione che due grafi possono essere equivalenti secondo il Markov nidificato (stessi vincoli di uguaglianza) ma avere insiemi di disuguaglianze osservabili diversi.
• Grafici di Bell Tripartiti: Applicazione al famoso scenario di Bell nella fisica quantistica. L'algoritmo ha derivato l'insieme completo di 53.894 vincoli (di cui 53.856 disuguaglianze) in meno di 0.5 ore di CPU, confermando risultati noti e fornendo un set completo.
• Scenario Triangolare: Dimostrazione che, anche se il metodo non è completo per il c-grado 3, la fusione delle variabili latenti permette di ottenere vincoli parziali utili.

5. Significato e Implicazioni

• Falsificabilità dei Modelli: Il metodo fornisce un criterio rigoroso per falsificare modelli causali con variabili nascoste che altrimenti sembrerebbero non testabili.
• Inferenza Statistica: I vincoli derivati possono essere utilizzati per migliorare l'efficienza statistica nelle procedure di stima (inferenza vincolata) e per l'identificazione parziale dei parametri.
• Scoperta Causale: Offre una stratificazione più fine delle classi di equivalenza causale rispetto ai soli test di indipendenza o vincoli di uguaglianza, permettendo di distinguere tra modelli che altrimenti sarebbero indistinguibili.
• Strumento Pratico: Gli autori hanno reso disponibile un software open-source su GitHub (meraconstraints) che implementa l'algoritmo, rendendo la metodologia accessibile per l'analisi di dati reali.

In sintesi, il paper rappresenta un avanzamento significativo nella teoria dei modelli causali, colmando il divario tra la caratterizzazione algebrica dei vincoli e la loro derivazione computazionale completa, specialmente per modelli con variabili latenti discrete e strutture a c-grado basso.