Differentially Private Data-Driven Markov Chain Modeling

Titolo

Modellazione di Catene di Markov basata su Dati con Privacy Differenziale

1. Problema e Contesto

Le catene di Markov sono strumenti fondamentali per modellare una vasta gamma di comportamenti utente, dall'uso domestico del tempo ai modelli di traffico e alla navigazione su internet. Tuttavia, la costruzione di modelli accurati richiede l'analisi di grandi quantità di dati utente sensibili.
Il problema centrale affrontato dagli autori è il compromesso tra accuratezza del modello e privacy:

• Per generare le probabilità di transizione di una catena di Markov, è necessario contare le transizioni tra stati nei dati utente.
• Condividere il modello risultante (la matrice di transizione) senza protezioni può rivelare informazioni sensibili sui dati sottostanti, permettendo di inferire comportamenti individuali (es. orari di presenza in casa o abitudini di acquisto) anche dai dati aggregati.
• Le tecniche di privacy standard (come i meccanismi di Laplace o Gaussiano) sono inadatte per i vettori stocastici (vettori con entrate non negative che sommano a 1) perché il rumore aggiunto ha supporto infinito, rischiando di violare i vincoli di somma unitaria e non negatività. Proiettare tali vettori sul simplex unitario porta invece a una scarsa accuratezza.

2. Metodologia

Gli autori propongono un framework basato sulla Privacy Differenziale (DP) per proteggere i database utilizzati per calcolare le probabilità di transizione, preservando al contempo l'utilità del modello.

A. Meccanismo di Dirichlet per Query sul Simplex

Per privatizzare i vettori stocastici (le righe della matrice di transizione), gli estendono il meccanismo di Dirichlet (originariamente introdotto da Gohari et al., 2021).

• Input: Un vettore di conteggio sensibile $C(D, \rho)$ derivato dal database.
• Output: Un vettore privatizzato $\tilde{C}$ campionato da una distribuzione di Dirichlet centrata su $k \cdot C(D, \rho)$, dove $k$ è un parametro di privacy.
• Vantaggio: A differenza dei meccanismi additivi, il meccanismo di Dirichlet garantisce che l'output rimanga naturalmente all'interno del simplex unitario (somma a 1, entrate $\ge 0$), evitando proiezioni che degradano l'accuratezza.
• Privacy: Viene dimostrato che questo approccio soddisfa la Privacy Differenziale $(\epsilon, \delta)$ convenzionale, estendendo il concetto di "privacy differenziale probabilistica" per gestire i vincoli del simplex.

B. Composizione Parallela per Matrici Stocastiche

Per modellare l'intera catena di Markov, il framework privatizza ogni riga della matrice di transizione $P(D, \rho)$ individualmente.

• Utilizzando la proprietà di composizione parallela, la privacy dell'intera matrice è garantita dai parametri $(\max \epsilon_i, \max \delta_i)$ delle singole righe, poiché le righe sono calcolate su sottoinsiemi disgiunti del database.
• Questo permette di generare una matrice di transizione privata $\tilde{P}$ che è a sua volta una matrice stocastica valida.

C. Analisi di Accuratezza e Stabilità

Gli autori derivano limiti analitici rigorosi per quantificare l'impatto della privacy sulle proprietà dinamiche della catena:

1. Divergenza KL: Viene calcolato il limite superiore della divergenza di Kullback-Leibler tra il vettore originale e quello privatizzato.
2. Distribuzione Stazionaria: Viene derivato un limite per la variazione della distribuzione stazionaria ($\pi$) tra il modello non privato e quello privato, utilizzando la norma $L_1$ e la matrice fondamentale $Z = (I - P + \mathbf{1}\pi^T)^{-1}$.
3. Coefficiente di Ergodicità: Viene analizzato il cambiamento nel coefficiente di ergodicità (una proxy per il tasso di convergenza alla distribuzione stazionaria), dimostrando che la privacy influisce sul tasso di convergenza in modo controllabile.

3. Contributi Chiave

1. Framework di Privatizzazione: Sviluppo di un metodo per privatizzare query i cui output sono vettori stocastici (Teorema 1) e matrici stocastiche (Teorema 3).
2. Garanzie di Privacy Rigorose: Dimostrazione che il meccanismo di Dirichlet esteso soddisfa la privacy differenziale $(\epsilon, \delta)$ convenzionale per query su database, fornendo una privacy a livello di evento.
3. Limiti di Accuratezza: Derivazione di limiti analitici per la divergenza KL attesa (Teorema 2) e per le variazioni nella distribuzione stazionaria e nel tasso di convergenza (Teoremi 4 e 5). Questi limiti permettono agli utenti di sintonizzare i parametri di privacy in base all'accuratezza desiderata.
4. Validazione Empirica: Applicazione del metodo su due dataset reali: distribuzione dei voti universitari e dati di spostamento dei taxi di New York City.

4. Risultati Sperimentali

Gli esperimenti confermano che il metodo offre un'alta accuratezza anche con livelli di privacy significativi:

• Dataset Voti: Utilizzando dati pubblici di un corso di Calcolo (98 studenti), il metodo ha prodotto distribuzioni privatizzate con una divergenza KL molto bassa.
• Dataset Taxi NYC: Su un dataset di quasi 3 milioni di viaggi (Gennaio 2025), il modello di catena di Markov privatizzato ha mostrato una differenza minima nella distribuzione stazionaria rispetto al modello non privato.
  • Con parametri di privacy $(\epsilon=3.73, \delta=3 \times 10^{-6})$, l'errore nella distribuzione stazionaria è stato inferiore al 2%.
  • Anche con la privacy più forte testata, la distribuzione stazionaria del modello privato rimaneva fedele a quella reale, indicando che il modello cattura accuratamente il comportamento del sistema.

5. Significato e Impatto

Questo lavoro è significativo perché:

• Colma un divario tecnico: Risolve il problema specifico della privatizzazione di dati che devono rispettare vincoli di somma unitaria (simplex), un caso d'uso comune ma difficile per i meccanismi di rumore standard.
• Garantisce l'utilità: Fornisce garanzie matematiche che l'aggiunta di privacy non distrugge le proprietà dinamiche fondamentali delle catene di Markov (come la convergenza e la distribuzione a lungo termine).
• Applicabilità Pratica: Dimostra che è possibile condividere modelli di comportamento utente (es. per la pianificazione urbana o il marketing) senza compromettere la privacy degli individui, rendendo la privacy differenziale praticabile per l'analisi di sistemi stocastici complessi.
• Futuro: Apre la strada a ricerche su privacy a livello di utente (user-level privacy) e per processi decisionali di Markov (MDP) basati su dati.

In sintesi, gli autori hanno sviluppato un metodo robusto e teoricamente fondato per generare modelli di Markov basati su dati sensibili che sono sia differenzialmente privati che statisticamente accurati.