Πειραματική αξιολόγηση αλγορίθμων εκμάθησης αποκομμένων πολυδιάστατων Γκαουσσιανών κατανομών

Abstract

Το πρόβλημα της εκμάθησης αποκομμένων κανονικών κατανομών έχει ιστορία τριών αιώνων. Το φαινόμενο της αποκοπής στην περίπτωση μίας d-διάστατης κανονικής κατανομής παρατηρείται όταν τα δείγματα αποκαλύπτονται μόνο εάν ανήκουν σε κάποιο σύνολο S ⊆ R d . Διαφορετικά παραμένουν κρυφά και ο λόγος τους προς τον συνολικό παραμένει άγνωστος. Συναντάται στην πράξη σε διάφορους τομείς: από την προστασία ευαίσθητων προσωπικών δεδομένων σε οικονομικές εφαρμογές μέχρι την αδυναμία καταγραφής ακραίων τιμών που εμφανίζουν τα όργανα μέτρησης πειραματικών διατάξεων. Το 2018, οι Daskalakis et al. παρουσίασαν τον πρώτο αλγόριθμο που εκτιμάει τις παραμέτρους της αποκομμένης κατανομής με αυθαίρετη ακρίβεια σε πολυωνυμικό χρόνο. Μοναδικές προϋποθέσεις η πρόσβαση μέσω μαντείου στο σύνολο S, το οποίο να έχει μη τετριμμένο μέτρο υπό την άγνωστη κατανομή. Η καινοτομία τους αφορούσε στην εισαγωγή ενός συνόλου προβολής με κατάλληλες ιδιότητες ώστε ο αλγόριθμος Στοχαστικής Κατάβασης Κλίσης(Stochastic Gradient Descent) να επιτυγχάνει (πρακτικά βέλτιστη) πολυωνυμική πολυπλοκότητα, τόσο δειγματική όσο και υπολογιστική. Στην παρούσα διπλωματική παρουσιάζουμε μία πειραματική υλοποίηση και αξιολόγηση του αλγορίθμου και ελέγχουμε εάν η πράξη συμφωνεί με την θεωρία, και έαν ναι υπό ποιες συνθήκες αυτό επιτυγχάνεται. Συγκεκριμένα, προσαρμόζοντας τον ρυθμό μάθησης του αλγορίθμου επιβεβαιώνουμε τα θεωρητικά αποτελέσματα αναφορικά με την διάσταση του προβλήματος, το μέτρο αποκοπής και την ακτίνα προβολής. Αφήνουμε ένα ανοικτό ερώτημα σχετικά με τη φύση του συνόλου αποκοπής και προτείνουμε μια ευρεστική μέθοδο που επιτυγχάνει ταχύτατη σύγκλιση στην πράξη.