Αποδοτικοί Αλγόριθμοι Μάθησης Δυνάμεων Πουασσόν Διωνυμικών Κατανομών

Abstract

ΠερίληψηΣε αυτήν την διπλωματική εργασία εισάγουμε το πρόβλημα της μάθησης όλων των δυνάμεων μιας ΠουασσόνΔιωνυμικής Κατανομής (Poisson Binomial Distribution, PBD). Μια n-PBD είναι η κατανομή του αθροίσματοςX =ni=1Xi, n ανεξάρτητων 0/1 κατανομών Bernoulli, όπου EXi[=] pi. H k-οστή δύναμη της X, για έναk [m], είναι η κατανομή Pk=ni=1X(k)i, όπου EX(k)i[=] (pi)k. O αλγόριθμος μάθησης μπορεί να τραβήξειδείγματα από οποιαδήποτε δύναμη Pkκαι λέμε ότι πετυχαίνει στην ταυτόχρονη εκμάθηση όλων των δυνάμεωνστο εύρος [m] αν με πιθανότητα το λιγότερο 1 - δ: δεδομένου ενός k [m] επιστρέφει μια κατανομή Qkτέτοια ώστε dtv(Pk, Qk) ε.Δείχνουμε αρχικά ένα πληροφοριό-θεωρητικό κάτω φράγμα για την δειγματική πολυπλοκότητα του παρα-πάνω προβλήματος στην περίπτωση που οι παράμετροι pi-s της PBD είναι αρκετά διαχωρισμένες. Το κάτωφράγμα αυτό δείχνει ότι χρειαζόμαστε περίπου έναν σταθερό αριθμό δειγμάτων για κάθε ξεχωριστή παράμετροpi, δηλαδή συνολικά (n) δείγματα για τις δυνάμεις μιας n-PBD. Στη συνέχεια γίνουμε ένα σχεδόν βέλτιστοπάνω φράγμα για την δειγματική πολυπλοκότητα στην περίπτωση που η PBD έχει μορφή παρόμοια με αυτήτου κάτω φράγματός μας.Επεκτείνουμε το κλασικό ορισμό του minimax risk της Στατιστικής και επεκτείνοντας τις τεχνικές μελέτηςτης δειγματικής πολυπλοκότητας για την προσέγγιση συναρτήσεων ακολουθιών κατανομών. Συγκεκριμέναεπεκτείνουμε τις κλασικές μεθόδους των Le Cam και Fano για να παράγουμε κάτω φράγματα στο δικό μαςμοντέλο μάθησης ακολουθιών κατανομών.Μελετούμε το βασικό πρόβλημα της μάθησης των δυνάμεων μιας Διωνυμικής κατανομής και παρέχουμεέναν βέλτιστο αλγόριθμο μάθησης των δυνάμεων χρησιμοποιώντας O(1/eps2) δείγματα από τις δυνάμεις τηςΔιωνυμικής κατανομής. Αποδεικνύουμε ότι ο αλγόριθμός είναι βέλτιστος δείχνοντας ένα κάτω φράγμα (1/ε2)χρησιμοποιώντας το νέο minimax framework μας.Η μάθηση των παραμέτρων piμιας PBD είναι ένα γνωστό δύσκολο πρόβλημα. Οι Διακονικόλας, Kane,και Stewart [COLT’16] έδειξαν ένα εκθετικό κάτω φράγμα (21/ε) δειγμάτων για την μάθηση των piμεαθροιστικό σφάλμα το πολύ ε. Ένα φυσικό ερώτημα, λοιπόν, είναι αν η δυνατότητα δειγματοληψίας τόσο απότην ίδια την PBD όσο και από τις δυνάμεις της βοηθάει στο να μειωθεί η δειγματική πολυπλοκότητα τουπροβλήματος αυτού. Δίνουμε αρνητική απάντηση σε αυτό το ερώτημα δείχνοντας το ίδιο κάτω φράγμα στοδικό μας μοντέλο των δυνάμεων. Τέλος, παρέχουμε έναν σχεδόν βέλτιστο αλγόριθμο παραμετρικής μάθησηςτων piχρησιμοποιώντας δείγματα από τις δυνάμεις μιας PBD.