Μάθηση διατάξεων από δείγματα με ελλιπή πληροφορία

Abstract

Αυτή η εργασία αποτελεί μία μελέτη πάνω στην εκμάθηση διατάξεων από θορυβώδη δείγματα τα οποία πιθανώς δεν περιέχουν όλα τα στοιχεία προς ταξινόμηση. Η εκμάθηση διατάξεων είναι ένα επίκαιρο πρόβλημα που συνδέεται στενά με τη Θεωρία Κοινωνικής Επιλογής, τα συστήματα Ψηφοφορίας και, γενικότερα, τη Μηχανική Μάθηση. Το βασικό πρόβλημα είναι η κατασκευή μίας διάταξης που είναι η πλέον ευρέως αποδεκτή, μέσω αξιοποίησης της πληρο- φορίας που περιέχεται σε ένα σύνολο διατάξεων εισόδου που γίνονται αντιληπτές ως ψήφοι ή δείγματα. Η έννοια της καθολικής αποδοχής αποκτά νόημα όταν εισάγεται κάποιο στατιστικό μοντέλο παραγωγής των διατάξεων εισόδου, ως ανεξάρτητα δείγματα. Συγκεκριμένα, ανάμε- σα σε πολλά μοντέλα παραγωγής διατάξεων, επικεντρωνόμαστε στο μοντέλο Mallows, που στηρίζεται στην ιδέα της ύπαρξης μίας κεντρικής διάταξης που χαρατηρίζει την κατανομή της πιθανότητας εμφάνισης μίας διάταξης, μέσω μίας συνάρτησης απόστασης μεταξύ διατάξεων. Η πιθανότητα εμφάνισης μίας διάταξης μειώνεται εκθετικά στην απόσταση της διάταξης από την κεντρική διάταξη. ́Εχουν αναπτυχθεί διάφοροι αλγόριθμοι για την ανακατασκευή της κεντρικής διάταξης ή κάποιας εκτίμησής της από πλήρεις διατάξεις που αποτελούν ανεξάρτητα δείγματα της κατανομής Mallows. Ωστόσο, δεν είναι πάντοτε ρεαλιστική υπόθεση ότι μπορεί κανείς να έχει πρόσβαση σε δείγματα που είναι πλήρεις διατάξεις, καθώς συνήθως το πλήθος των εναλλακτικών είναι πολύ μεγάλο. Στην εργασία αυτή, εκτός από την παρουσίαση βασι- κών θεωρητικών θεμελίων και ορισμένων αποτελεσμάτων σχετιζόμενων με την μάθηση στο μοντέλο Mallows, προτείνεται ένα γενικευμένο μοντέλο για δείγματα που δεν είναι απαραίτη- τα πλήρεις διατάξεις, αλλά διατηρεί την έννοια της κεντρικής διάταξης. Επίσης, παρέχονται αυστηρά φράγματα για τη δειγματική πολυπλοκότητα ανακατασκευής της κεντρικής διάταξης σε ορισμένες παραλλαγές του γενικευμένου μοντέλου και παρουσιάζεται ένας αλγόριθμος για τον αποδοτικό υπολογισμό της εκτίμησης μέγιστης πιθανοφάνειας της κεντρικής διάταξης από θορυβώδη δείγματα με ελλιπή πληροφορία.