Αλγοριθμικές Τεχνικές Μάθησης Πιθανοτικών Κατανομών Και Εφαρμογές Τους Σε Προβλήματα Κοινωνικής Επιλογής

Abstract

Σε αυτή την διπλωματική εργασία, μελετούμε προβλήματα μάθησης πιθανοτικών κατανομών κάτω από το πρίσμα αλγοριθμικών τεχνικών. Μελετούμε μια φυσική γενίκευση του PAC μοντέλου μάθησης μιας άγνωστης διακριτής κατανομής πιθανότητας. Στο πλαίσιο αυτό, ο αλγόριθμος μάθησης λαμβάνει ως είσοδο n ανεξάρτητα δείγματα από μια άγνωστη κατανομή X. Χρησιμοποιώντας αυτά τα δείγματα, ο αλγόριθμος προτείνει με πιθανότητα τουλάχιστον 1-δ μια κατανομή-υπόθεση X τέτοια ώστε η στατιστική απόσταση των δύο κατανομών (TV ): dTV(X,X) να είναι το πολύ , όπου ,δ > 0 είναι οι παράμετροι ακρίβειας και εμπιστοσύνης, τα οποία παρέχονται επίσης ως είσοδο στον χρήστη. Παρουσιάζουμε εκτενώς την προηγούμενη επιστημονική εργασία πάνω σε αυτό το πλαίσιο για τις κλασσικές οικογένειες κατανομών π.χ μονότονες, λογαριθμικά κυρτές, μόνολοφες, παρέχοντας ακριβή άνω και κάτω φράγματα. Εστιάζουμε πάνω σε μια νέα αλγοριθμική τεχνική, στην κατασκευή αραιώς πυκνών καλυμμάτων , τα οποία είναι αραιά ως προς των πληθάριθμο αλλά πυκνά ως προς την μετρικότητα του χώρου της κλάσης των κατανομών που μελετούμε. Η μέθοδος εκμεταλλεύεται την δομή των κατανομών αυτών για να σχεδιάσει αποδοτικά χρονικώς και δειγματικώς αλγορίθμους. Επιπλέον, μελετούμε το πρωτόλειο έργο των [ΔΠ13] και [ΔΔΣ15] στις Poisson Binomial Distribution, το άθροισμα n ανεξάρτητων Bernoulli. Στην συνέχεια αναπτύσσουμε μια παρόμοια προσέγγιση στην αυξανόμενα αναπτυσσόμενη περιοχή της υπολογιστικής θεωρίας κοινωνικής επιλογής και πιο συγκεκριμένα στο τομέα του ςροωδvοτινγ. Βασιζόμενοι στο διάσημο θορυβοποιό μοντελό του Mallow στο οποίο κάθε ψηφοφόρος είναι ένας εκτιμητής της κοινωνικής πραγματικότητας, παρουσιάζουμε την δουλειά μας πάνω σε εκλογικούς κανόνες όπως ο Kemeny/Plurality επεκτείνοντας την προηγούμενη ερευνητική εργασία