Αποδοτικοί Αλγόριθμοι Εκμάθησης για Γραμμικά Ενθόρυβα Μοντέλα Label Ranking

Abstract

Στην παρούσα διπλωματική εργασία, μελετάμε το πρόβλημα Label Ranking (LR), ήτοι το επιβλεπόμενο πρόβλημα εκμάθησης μιας συνάρτησης που αντιστοιχίζει παραδείγματα σε κατατάξεις ενός πεπερασμένου συνόλου προκαθορισμένων ετικετών. Το LR κατέχει καίρια θέση στην περιοχή της εκμάθησης προτιμήσεων και συνιστά αντικείμενο αυξανόμενου ενδιαφέροντος λόγω της εμπλοκής του σε μια πληθώρα τομέων, όπως η στοχευμένη διαφήμιση, η βιοπληροφορική και η μετα-μάθηση. Η συντριπτική πλειοψηφία των εργασιών γύρω από το LR, υιοθετεί μια πρακτική προσέγγιση για το εν λόγω πρόβλημα, προτείνοντας αλγορίθμους στη βάση πειραματικής αξιολόγησης και όχι θεωρητικών αποτελεσμάτων. Ως εκ τούτου, μια από τις κύριες προκλήσεις στην περιοχή του LR αφορά στην κατασκευή αλγορίθμων, οι οποίοι να υποστηρίζονται τόσο από στατιστικές εγγυήσεις, διασφαλίζοντας ικανότητα γενίκευσης σε νέα δεδομένα, όσο και από εχέγγυα αποδοτικότητας, εξασφαλίζοντας υπολογιστική διαχειρισιμότητα. Ο σκοπός της παρούσας εργασίας έχει δύο πτυχές. Ο πρώτος μας στόχος σχετίζεται με τη θεωρητική μελέτη του LR και την επέκταση ορισμένων υπαρχόντων βιβλιογραφικών αποτελεσμάτων. Συγκεκριμένα, επικεντρωνόμαστε στη θεμελιώδη κλάση των Γραμμικών Ταξινομητικών Συναρτήσεων (Linear Sorting Functions ή LSFs), η οποία αντιστοιχεί στη γραμμική εκδοχή του LR, και, βασιζόμενοι στη δουλεία των (Fotakis, Kalavasis, Kontonis, Tzamos, NeurIPS 2022), παρέχουμε έναν αποδοτικό, κανονικό (proper) αλγόριθμο εκμάθησης LSFs κατά το μοντέλο PAC. Ο αλγόριθμός μας συνοδεύεται από εχέγγυα υπό το καθεστώς των ισοτροπικών λογαριθμικώς κοίλων κατανομών πιθανότητας, ως προς την απόσταση Tau του Kendall και ως προς μοντέλα θορύβου που επεκτείνουν τα μοντέλα θορύβου δυαδικής ταξινόμησης Massart και Tsybakov στην περίπτωση του LR. Ο δεύτερος στόχος μας είναι να διερευνήσουμε πειραματικώς την επίδοση LR αλγορίθμων βασισμένων σε γραμμικές συναρτήσεις σε σύγκριση με αλγορίθμους, οι οποίοι βασίζονται σε δέντρα απόφασης και τυχαία δάση, δεδομένου, ότι οι τελευταίες μέθοδοι θεωρούνται υπερσύγχρονες στην περιοχή του LR. Η πειραματική μας αξιολόγηση λαμβάνει χώρα τόσο σε θορυβώδη σύνολα εκπαίδευσης προερχόμενα από LSFs, όσο και σε τυπικά σύνολα αναφοράς για το LR.