Κατάλογος Εκδηλώσεων

Περιγραφή:
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

ΒΑΣΙΛΕΙΟΥ ΔΙΓΑΛΑΚΗ

με θέμα

Ανάλυση Δεδομένων με Διαφορική Ιδιωτικότητα
Data Analytics with Differential Privacy

Σάββατο 14 Ιουλίου 2018, 10 π.μ.
Αίθουσα Συνεδριάσεων Σχολής ΗΜΜΥ, Κτίριο Επιστημών, Πολυτεχνειούπολη

Εξεταστική Επιτροπή
Καθηγητής Μίνως Γαροφαλάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Γεώργιος Καρυστινός
Αναπληρωτής Καθηγητής Άγγελος Μπλέτσας

Περίληψη

Στην παρούσα διπλωματική εργασία μελετάμε το πρόβλημα της ανάλυσης με ιδιωτικότητα κατανεμημένων δεδομένων και ροών δεδομένων. Η διαφορική ιδιωτικότητα (differential privacy) αποτελεί τον επικρατέστερο ορισμό της ιδιωτικότητας και «αντιμετωπίζει το παράδοξο του να μην αποκαλύπτεται τίποτα για οποιοδήποτε άτομο ενώ εξάγονται χρήσιμες πληροφορίες για έναν πληθυσμό» (Dwork και Roth). Με άλλα λόγια, η διαφορική ιδιωτικότητα εγγυάται ότι οποιαδήποτε ανάλυση που πραγματοποιείται σε ένα σύνολο ευαίσθητων δεδομένων δεν αποκαλύπτει πληροφορίες για τα άτομα των οποίων τα δεδομένα περιέχονται σε αυτό το σύνολο δεδομένων. Όλοι οι αλγόριθμοι που προτείνουμε προσφέρουν αυτή την ισχυρή εγγύηση ιδιωτικότητας, προσαρμοσμένη στο μοντέλο κατανεμημένων δεδομένων και ροών δεδομένων.
Στο μοντέλο κατανεμημένων δεδομένων, μελετάμε το πρόβλημα της μάθησης με κατανεμημένο τρόπο ενός συνολικού μοντέλου, το οποίο στη συνέχεια μπορεί να χρησιμοποιηθεί για οποιεσδήποτε αναλύσεις. Βασιζόμαστε στον αλγόριθμο PrivBayes, ο οποίος προσεγγίζει με διαφορική ιδιωτικότητα την μεγάλης διάστασης κατανομή ενός συνόλου δεδομένων ως γινόμενο κατανομών μικρότερης διάστασης, χρησιμοποιώντας Bayesian Networks. Εξετάζουμε τρεις προσεγγίσεις για την εκμάθηση ενός συνολικού Bayesian Network από τα κατανεμημένα δεδομένα, διατηρώντας παράλληλα τη διαφορική ιδιωτικότητα όλων των επί μέρους συνόλων δεδομένων. Η εργασία περιλαμβάνει μια λεπτομερή θεωρητική ανάλυση του κατανεμημένου και με διαφορική ιδιωτικότητα εκτιμητή εντροπίας, που χρησιμοποιούμε σε έναν από τους αλγορίθμους μας, καθώς και λεπτομερή πειραματική αξιολόγηση, χρησιμοποιώντας τόσο συνθετικά όσο και πραγματικά δεδομένα.
Στο μοντέλο ροών δεδομένων, εστιάζουμε στο πρόβλημα της εκτίμησης της πυκνότητας μιας ροής χρηστών (ή, γενικότερα, στοιχείων), η οποία εκφράζει το ποσοστό των χρηστών του πληθυσμού που εμφανίζονται στην ροή. Προσφέρουμε μία από τις ισχυρότερες εγγυήσεις προστασίας της ιδιωτικότητας για το μοντέλο ροών δεδομένων (user-level pan-privacy), η οποία διασφαλίζει την προστασία της ιδιωτικότητας οποιουδήποτε χρήστη, ακόμη και έναντι κάποιου που παρατηρεί σε σπάνιες περιπτώσεις την εσωτερική κατάσταση του αλγορίθμου. Αναλύουμε λεπτομερώς έναν υπάρχοντα αλγόριθμο, βασισμένο σε δειγματοληψία, τον οποίο και βελτιώνουμε σημαντικά, τόσο θεωρητικά όσο και πειραματικά.


Abstract

This thesis addresses the problem of performing privacy-preserving analysis of distributed and streaming data. Differential privacy is the state-of-the-art definition for privacy, that “addresses the paradox of learning nothing about an individual while learning useful information about a population” (Dwork and Roth). In other words, differential privacy guarantees that any analysis performed on a sensitive dataset leaks no information about the individuals whose data are contained in this dataset. All the algorithms we propose offer this strong privacy guarantee, adjusted to the distributed and the streaming model.
In the distributed model, we consider the particular problem of learning in a distributed fashion a global model, that can then be used for arbitrary analyses. We build upon PrivBayes, a differentially-private method that approximates the high-dimensional distribution of a centralized dataset as a product of low-order distributions, utilizing a Bayesian Network model. Specifically, we examine three approaches to learning a global Bayesian Network from distributed data, while offering the differential privacy guarantee to all local datasets. Our work includes a detailed theoretical analysis of the distributed, differentially private entropy estimator which we use in one of our algorithms, as well as a detailed experimental evaluation, using both synthetic and real-world data.
In the streaming model, we focus on the problem of estimating the density of a stream of users (or, more generally, elements), which expresses the fraction of all users that actually appear in the stream. We offer one of the strongest privacy guarantees for the streaming model, namely user-level pan-privacy, which ensures that the privacy of any user is protected, even against an adversary that observes, on rare occasions, the internal state of the algorithm. We provide a detailed analysis of an existing, sampling-based algorithm for the problem, and significantly improve it, both theoretically and experimentally, by optimally using all the allocated privacy budget.