Τεχνικές Εκμάθησης Κατανομών Κατάταξης

Abstract

Οι κατανομές κατάταξης είναι ένα πεδίο που παραδοσιακά έχει προσελκύσει το ενδιαφέρον τόσο της κοινότητας των στατιστικολόγων, όσο και των ακαδημαϊκών που εργάζονται στο πεδίο της θεωρίας κοινωνικής επιλογής. Τα τελευταία χρόνια, έχουν επίσης τραβήξει την προσοχή αυτών που εργάζονται στους τομείς της θεωρητικής πληροφορικής και της μηχανικής μάθησης. Σε αυτή τη διπλωματική εργασία, εξετάζουμε προβλήματα μάθησης κατανομών στο πεδίο των κατανομών κατάταξης και, συγκεκριμένα, στο μοντέλο του Mallows. Ξεκινάμε εισάγοντας το τυπικό πλαίσιο της μάθησης κατανομών, καθώς και το απαραίτητο υπόβαθρο για την κατανόηση των θεμελιωδών τεχνικών της μάθησης κατανομών. Ακολουθεί μία εισαγωγή στη θεωρία των μεταθέσεων και στα μοντέλα κατατάξεων, με έμφαση στο μοντέλο του Mallows. Ύστερα, παρουσιάζουμε τις εργασίες των Καραγιάννη et. al. και Busa-Fekete et. al., που παρείχαν βέλτιστα ως προς την δειγματική πολυπλοκότητα αποτελέσματα για την εκτίμηση παραμέτρων και τη μάθηση κατανομών στο μοντέλο Kendall-Mallows. Μετά, προσαρμόζουμε αυτές τις τεχνικές προκειμένου να πάρουμε έναν αλγόριθμο πολυωνυμικού χρόνου που ανακτά την κεντρική κατάταξη στο μοντέλο Cayley-Mallows με μεγάλη πιθανότητα. Τέλος, εξετάζουμε πιθανές κατευθύνσεις έρευνας.