Blog divulgativo sulla matematica applicata

GDPR, differential privacy e probabilità.

gdpr-quesiti-garante-della-privacy-750x430Se siete lettori di questo blog conoscerete già la competizione organizzata da Netflix con l'obbiettivo di migliorare l'algoritmo per la predizione dei voti degli utenti su film e serie TV disponibili in catalogo. A questo scopo vennero resi pubblici oltre 100 milioni di voti di 500.000 utenti su circa 18.000 film differenti, dove i partecipanti potevano testare e valutare i propri algoritmi. Fu senza dubbio una scelta che ha permesso a Netflix di diventare quello che è adesso, tuttavia non mancarono problemi legati alla privacy degli individui appartenenti al sample di dati.

Infatti, benché non vi fosse alcuna informazione personale, diversi studi mostrano come conoscendo solo una parte delle preferenze degli utenti, sia possibile identificare il singolo individuo, deanonimizzando di fatto il dato. Tali preoccupazioni hanno spinto l'azienda a non pubblicare altri dati per nuove competizioni. Questi ed altri studi hanno dato il via ad interessanti spunti di riflessione sul tema della privacy, su quali tecniche la assicurino e su quali, se utilizzate non correttamente, possano portare a data breach.

Anonimizzazione e GDPR

È indubbio che l'analisi di dati personali sia fondamentale per il business di aziende private e per l'interesse pubblico. Con l'innovazione tecnologica il concetto di privacy si è evoluto: dalla concezione di riservatezza intesa come diritto di essere lasciati soli, the right to be alone, di circa un secolo fa, si è arrivati alla codifica della protezione dei dati personali come un habeas data nella carta di Nizza. Quindi non più la sola tutela dell'individuo nella sua sfera privata, ma il diritto all'autodeterminazione informativa, cioè alla possibilità da parte dell'interessato di seguire il completo ciclo di vita del dato.

Tra i punti cardine del nuovo Regolamento Europeo in materia di protezione dei dati personali, ben più noto come GDPR, c'è proprio quello di trovare il giusto equilibrio tra la tutela dei diritti e delle libertà della persona fisica cui si riferisce il dato, cioè l'interessato, e utilità/usabilità del dato stesso, nonché della libera circolazione di quest'ultimo. Citando Antonello Soro:

"i dati sensibili vengono protetti per garantire non tanto la loro segretezza quanto piuttosto la massima esplicazione in pubblico, senza per ciò esporre l'interessato a discriminazioni."

Si vuole creare un quadro di tutele non rigide che agevolino l'estrazione di insight dai dati e, al tempo stesso, non permettano di dedurre informazioni private sulle singole persone. Il titolare, cioè colui che determina le finalità e i mezzi del trattamento di dati personali, deve quindi applicare garanzie by design e by default rispetto ai rischi che comporta il trattamento stesso, in capo al principio di accountability. La protezione dei dati si sposta quindi da una mera esecuzione di una checklist, alla continua valutazione dei meccanismi, tecnologici e non, finalizzati alla tutela dell'interessato come un vero e proprio investimento.

Tra le tecniche più comuni troviamo:

  •  la generalizzazione: raggruppare elementi simili in uno stesso cluster/gruppo di elementi rimodulando e diluendo gli attributi;
  •  la randomizzazione: aggiungere rumore statistico ai dati tenendone inalterato il valore statistico.

All'interno della seconda famiglia rientra la differential privacy.

Differential Privacy e analisi dei dati

privacy-3

Supponiamo che un'azienda (di cui ci fidiamo) raccolga un certo tipo di informazioni su un gruppo di individui in un database: tipicamente una tabella in cui ogni riga rappresenta determinate informazioni su un individuo. Il database di un'anagrafe sarà costituito, ad esempio, dalle colonne nome, cognome, indirizzo ed ogni riga sarà il nome, cognome e indirizzo di una determinata persona.

Il nostro scopo è quello di proteggere le informazioni sensibili del singolo, permettendo allo stesso tempo analisi statistiche non banali sulla comunità che compone il database. In altre parole vogliamo garantire che un attaccante, ossia un terzo individuo malintenzionato,  analizzando il database nella sua totalità non sia in grado di acquisire conoscenza ulteriore sul singolo.

La soluzione banale di eliminare ogni informazione personale e/o sensibile  non è attuabile perché si perderebbe l'utilità statistica del dato stesso. Praticamente, un dato completamente anonimizzato è inutile dal punto di vista statistico. Il viceversa, ossia lasciare troppe informazioni in chiaro, permette studi statistici più ricchi ma mette in pericolo la privacy della popolazione interessata.

balance

Facciamo un esempio. Supponiamo di avere a disposizione un database pubblico di una università dove, tra gli altri dati, abbiamo quelli sul reddito delle famiglie degli studenti. Possiamo pensare che i dati identificativi siano in qualche modo nascosti al fine di proteggere la privacy degli studenti. Per capire come ciò non sia sufficiente ad eliminare il pericolo di reidentificazione, prendiamo la domanda "quanti studenti iscritti hanno famiglie con reddito reddito superiore ai 100.000 euro? " e pensiamo al seguente scenario: oggi come risultato ottengo uno, ieri avevo zero. Se dal nostro database o altre fonti indirette, riusciamo a dire che nessuno studente abbia lasciato l'università nelle ultime ventiquattro ore, linkando allora l'informazione "c'è un nuovo studente con reddito maggiore ai 100k" ad altri dati, come un post su Facebook o più semplicemente una festa di benvenuto al nuovo arrivato, abbiamo trovato il reddito della famiglia (una stima dal basso, ma è possibile fare di meglio).

La differential privacy garantisce che l'aggiunta o rimozione di una singola entrata in un database non modifichi sostanzialmente il risultato di un'analisi statistica. Nel nostro esempio è sufficiente aggiungere rumore ai risultati della query per non avere più la certezza su quante e quali siano le famiglie con un certo reddito.

Differential privacy: Intro

Vogliamo formalizzare processi e algoritmi che introducano rumore ai risultati delle query al fine di assicurare la privacy degli elementi che compongono una banca dati. Un meccanismo semplice potrebbe essere quello di lasciar rispondere gli intervistati in maniera stocastica in fase di inserimento dati.

Immaginiamo di voler creare un sample di dati sulla diffusione di una malattia in una certa città. Gli intervistati (anonimi), prima di rispondere lanciano una moneta, se esce testa rispondono sinceramente, se esce croce lanciano nuovamente la moneta: se testa rispondoneranno sì, se croce rispondoneranno no. La certezza delle privacy è garantita dalla negabilità di ogni risultato, c'è sempre una probabilità del 25% che la risposta non sia vera. Allo stesso tempo il meccanismo permette di stimare le persone malate partendo dal numero di risposte positive randomizzate: infatti il numero di "sì" attesi è 1/4 per le risposte negative più 3/4 per le risposte affermative.

Il punto di vista matematico

Denotiamo con U un universo astratto di dati. U può essere ad esempio l'insieme degli hobby, l'insieme delle serie TV/film su Netflix oppure un sottoinsieme dei numeri reali positivi per rappresentare gli stipendi annui degli abitanti di una città.

Un database è un multiset (una estensione del concetto di insieme che ammette elementi ripetuti) di n elementi di U. Ogni riga rappresenta le informazioni di un individuo. In astratto può essere pensato come un elemento X\in\mathbb{N}^{|U|}, dove la componente i-esima, x_i\in \mathbb{N}, denota il numero di elementi di tipo i\in U presenti nel database X, schematicamente

X:U\to \mathbb{N}, X(i)=X_i=|\{x\in X : x=i\}|.

Un po' di chiarezza. Un database X è una collezione di n elementi di U, quindi X\subseteq U; la rappresentazione come elemento di \mathbb{N}^{|U|} è detta rappresentazione ad istogramma e ogni componente del vettore rappresenta il numero di occorrenze dell'elemento i nel database.

Introduciamo una distanza d sull'insieme dei database,

d:U\times U\to \mathbb{R^+}, d(X,X^{'}):=\sum_{i=1}^{|U|}|X_i-X^{'}_i|,

che sicuramente qualcuno riconoscerà come la distanza indotta dalla norma l_1. Per semplicità supponiamo X limitato e discreto, in modo da evitare problemi legati alla convergenza della precedente sommatoria. Se U fosse continuo potremmo considerare i database X come funzioni a variabile reale con la distanza indotta dalla norma di Lebesgue L^1(X).

Facciamo un piccolo esempio. Supponiamo che X sia un database contenente dati relativi agli stipendi annui (espressi in migliaia euro). L'insieme universo dei dati è quindi

U=\{1,...,100\}.

Prendiamo allora il sottoinsieme

X=\{36, 40, 50, 100, 40\}\subset U,

nella sua rappresentazione ad istogramma diventa

X=\{0,...,0,1,0,0,0,2,0,...,0,1\}

dove

X_{40}=2, X_{36}=X_{50}=X_{100}=1, X_i=0 per ogni altra i.

Prendiamo poi un altro database, molto simile al precedente,

X=\{36, 40, 50, 100\}\subset U.

ossia

X=\{0,...,0,1,0,0,0,1,0,...,0,1\}.

L'unica differenza è nella coordinata 40. La distanza tra questi due database, calcolata utilizzando la definizione introdotta precedentemente, è

d(X,X^{'})=\sum_{i=1}^{|U|}|X_i-X_i^{'}|=|2-1|+|1-1|+|1-1|+|1-1|+|1-1|=1.

Due database che differiscono per una sola riga, equivalentemente la cui distanza valga uno, si dicono vicini.

Approfondiamo ora il concetto di query. Una query è una interrogazione fatta ad un database, può essere una domanda del tipo "quante sono le persone interessate al calcio e alla lettura", "quali sono gli sport più comuni" oppure "quanti sono gli individui con reddito maggiore di una certa soglia". Nel resto del post considereremo sempre query di conteggio del tipo "quante persone nel database hanno la proprietà P?". Vale a dire funzioni

f:\mathbb{N}^{|X|}\to \mathbb{R}

dove f(X) è il numero di oggetti che hanno tale proprietà P nel database X.

Una funzione di randomizzazione M è un algoritmo applicato in fase di risposta da parte del processo che elabora la query. Definendo \mathcal{Q} l'insieme di tutte le possibili query abbiamo M:\mathbb{N}^{|X|}\times \mathcal{Q} \to R dove R=\mbox{Range}(M). Più precisamente, dato un insieme discreto B, definiamo il simplesso di probabilità su B come

\Delta(B) :=\left\{x\in \mathbb{R}^{|B|}: \forall i,x_i\geq 0 \mbox{ and } \sum_{i=1}^{|B|}x_i=1 \right\}.

Un algoritmo randomizzato M con dominio A e codominio B è un algoritmo associato ad una mappa M:A\to\Delta(B) tale che M(a)=b con probabilità(M(a))_b,\forall b\in B.

Capture

 \varepsilon-Differential Privacy

Un algoritmo di randomizzazione M si dice \varepsilon-privacy differenziabile se, fissato un \varepsilon>0, per ogni coppia di database vicini X,X'\in U e per ogni evento S\subseteq R si ha

Pr(M(X)\in S)\leq e^\varepsilon Pr(M(X^{'})\in S)

Ok, è tutto poco chiaro, abbiate pazienza!

Intuitivamente la definizione si traduce nel fatto che avendo due database simili (X e X'), la probabilità che una query dia un certo risultato (S) su entrambi i database è più o meno (\varepsilon) la stessa. Se i vostri dati impattano notevolmente le statistiche fareste bene a non darli, altrimenti potete stare tranquilli.

Il parametro \varepsilon

Supponiamo che il database X' sia ottenuta da X rimuovendo Bob,
X=X'\cup \{Bob\}.
Il parametro è una sorta di manopola che consente di spostare l'attenzione o verso la privacy garantita a Bob o verso l'accuratezza dell'analisi dei dati. Più \varepsilon è scelto piccolo, vicino a zero, più stiamo richiedendo che i due scenari (con Bob e senza Bob) diano probabilisticamente gli stessi risultati. Nel caso limite in cui \varepsilon sia esattamente zero, stiamo eliminando completamente le informazioni che Bob apporta al database rendendolo, di fatto, trasparente! In ottica di analisi dei dati stiamo sacrificando troppo. Viceversa, al crescere di \varepsilon, sacrifichiamo la privacy di Bob concedendo più dettagli nelle analisi sui due scenari.

Non c'è una regola per la scelta del valore di \varepsilon, dobbiamo basarci sulla valutazione del rischio relativo ad una perdita di privacy caso per caso.

Il meccanismo di risposta casuale visto precedentemente è \varepsilon-differenziabile, con \varepsilon=\ln 3. Un algoritmo per implementarlo può essere il seguente:

RispostaRandom(x)
 begin
 lancia una moneta
     if testa then
         if domanda(x) is true
         then rispondi sì
         else rispondi no
     else
         lancia una moneta
         if testa then rispondi sì
     else rispondi no

Essendo un esempio elementare possiamo calcolare a mano tutte le probabilità per dimostrare la tesi.
Abbiamo

Pr[RispostaRandom=yes | domanda(x)=yes]=\frac34,
Pr[RispostaRandom=yes | domanda(x)=no]=\frac14,

da cui

\frac{Pr[RispostaRandom=yes | domanda(x)=yes]}{Pr[RispostaRandom=yes | domanda(x)=no]}=3

ossia la tesi.

La distribuzione di Laplace

Una funzione di randomizzazione molto utilizzata nelle applicazioni è costruita a partire dalla distribuzione di Laplace. Una variabile aleatoria Y ha distribuzione di Laplace, Y\sim \mbox{Lap}(\mu,b), se ha la seguente densità di probabilità:

 f(x|\mu,b)=\frac{1}{2b} \exp\left({-\frac{|x-\mu|}{b}}\right),

con \mu\in\mathbb{R^+} parametro di posizione e b\in \mathbb{R^+} parametro di scala.

Distribuzione di Laplace

Distribuzione di Laplace

Per proseguire abbiamo bisogno del concetto di sensibilità \Delta(f) di una query f:\mathbb{N}^{|X|}\to \mathbb{R}^k:

 \Delta(f):=\max_{D_1,D_2 | d(D_1,D_2)=1} ||f(D_1)-f(D_2)||_1,

dove ovviamente

 ||f(D_1)-f(D_2)||_1=\sum_{i=1}^{k}|f_i(D_1)-f_i(D_2)|

Notiamo come questo valore dipenda dalla query in sè e non dal database D.

Un esempio: per la query "Quante persone in questa stanza giocano a calcio?" la sensibilità vale 1 poiché rimuovendo, o aggiungendo, una sola persona dalla stanza, il risultato varia al massimo di uno. Stesso discorso per la query "Quante persone hanno gli occhi marroni, quante neri, quanti verdi?". Invece, la query "quante persone in questa stanza giocano a calcio e quante hanno gli occhi marroni?" ha sensibilità due, perché potrebbe darsi che rimuovendo una sola persona il conteggio finale varii di due.

In particolare, la query "Quante persone hanno una determinata proprietà P" ha sensibilità uno. Per semplicità considereremo soltanto questo tipo di query e quindi k=1.

A questo punto siamo pronti per costruire un algoritmo di risposta \varepsilon-privato utilizzando una variabile aleatoria Y\sim \mbox{Lap}(0,\Delta(f)/\varepsilon).
Ad ogni query f su un database X, rispondiamo con il valore perturbato

M_f(X):=f(X)+Y

Questo meccanismo è \varepsilon-privato perché dato un qualsiasi evento S\subseteq \mbox{Range}M, per ogni coppia di database X e X' vicini vale:

\frac{\mbox{Pr}\left[M_f(X)\in S \right]}{\mbox{Pr}\left[M_f(X')\in S\right]}=\frac{\int_{x\in S}\mbox{Pr}\left[M_f(X)=x\right]}{\int_{x\in S}\mbox{Pr}\left[M_f(X')=x\right]}\le\mbox{max}_{x\in S}\frac{\mbox{Pr}\left[M_f(X)=x\right]}{\mbox{Pr}\left[M_f(X')=x\right]}

inoltre per le proprietà della distribuzione di Laplace con parametri b=\frac{\Delta}{\varepsilon} e \mu=0, si ha:

\frac{\mbox{Pr}\left[M_f(X)=x\right]}{\mbox{Pr}\left[M_f(X')=x\right]}=\frac{\mbox{Pr}\left[Y=x-f(X)\right]}{\mbox{Pr}\left[Y=x-f(X')\right]}=\exp\left[{\frac{\varepsilon}{\Delta}\left(|x-f(X')|-|x-f(X)|\right)}\right]\le \exp(\varepsilon)

da cui la tesi.

Un'altra distribuzione molto comune per l'implementazione di algoritmi che soddisfano la definizione di \epsilon-privacy differenziabilità è la gaussiana. Tale distribuzione permette di calcolare la sensibilità secondo la norma l_2, e quindi può essere più adatta nel caso di query con sensibilità l_1 alta; dall'altro lato però ci sono degli svantaggi nella comprensione a posteriori del rumore aggiunto. Tralasciamo i dettagli e vediamo direttamente una applicazione pratica.

Applicazioni reali

In casa Apple applicano la differential privacy per analizzare diversi aspetti relativi all'utilizzo dei dispositivi da parte degli utenti, come ad esempio: suggerimento emoji, impatto di Safari sulla batteria, autocompletamento frasi, app Health.

Apple salva questo tipo di dati per un massimo di tre mesi eliminando ogni dato identificativo dell'utente. Per il suggerimento delle emoji utilizza \varepsilon=4, mentre per i dati relativi all'app Health il parametro \varepsilon è fissato a 2.

La scelta di questi parametri torna con quanto detto in precedenza sulla funzionalità di \varepsilon: su dati più sensibili, quelli sulla salute, è scelto un parametro più piccolo rispetto a dati meno sensibili come quelli sull'utilizzo delle emoji. Potete trovare tutti i dettagli qui.

Spero abbiate trovato interessante questa breve introduzione ad un argomento estremamente vasto, per qualsiasi domanda non esitate a commentare qui sotto. Nel frattempo vi lascio alcuni link per approfondire. L'articolo di Cynthia Dwork (Microsoft) che introduce per la prima volta la differential privacy e relativo brevetto. Una trattazione più analitica dell'argomento. Un interessante legame tra d.p. e machine learning che non abbiamo per nulla trattato, ma meriterebbe un post a parte.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination