Learning Mixtures of Selective Mallows Models

Abstract

Στην παρούσα εργασία µελετάµε το πρόβληµα της εκµάθησης µιγµάτων κατανοµών κατάταξης µε χρήση ϑορυβωδών ελλιπών δειγµάτων. Οι κατανοµές κατάταξης έχουν κερδίσει ενδιαφέρον στα πεδία της ϑεωρίας των κοινωνικών επιλογών και της ϑεωρητικής µηχανικής µάθησης εδώ και δεκαετίες. Πέρα από την εκτεταµένη ϑεωρητική έρευνα, οι κατανοµές κατάταξης έχουν διάφορες εφαρµογές στον πραγµατικό κόσµο, όπως στο crowdsourcing, στα συστήµατα ψηφοφορίας, τα recommendation systems και την αναζήτηση στο διαδίκτυο. Κατά τη συνάθροιση δειγµάτων κατάταξης χρησιµοποιούµε µια συλλογή δειγµάτων που προέρχονται από έναν συγκεκριµένο πληθυσµό και προσπαθούµε να εκτιµήσουµε το υποκείµενο "ground truth" σχετικά µε τις προτιµήσεις του πληθυσµού πάνω σε ένα σύνολο n στοιχείων. Τα δείγµατα είναι είτε πλήρη είτε ελλιπή. Στην πρώτη περίπτωση κάθε δείγµα είναι µια µετάθεση του πλήρους συνόλου των n στοιχείων ενώ στη δεύτερη περίπτωση κάθε δείγµα είναι µια µετάθεση κάποιου υποσυνόλου του πλήρους συνόλου των n στοιχείων. Το πρώτο µας ϐήµα είναι να ϑεωρήσουµε ένα είδος µοντέλου που παράγει τα δείγµατα, ώστε το πρόβληµά µας να είναι καλά διατυπωµένο και να είναι δυνατή η ϐελτιστοποίηση. ∆ηµοφιλή µοντέλα είναι τα Mallows, Plackett Luce και το Repeated Insertion Model. Στην εργασία µας εστιάζουµε στο µοντέλο Mallows και ιδιαίτερα στην selective εκδοχή του, όπου τα δείγµατα είναι ελλιπή. Μια περαιτέρω γενίκευση του κλασικού µοντέλου Mallows είναι να υποθέσουµε ότι η κατανοµή κατάταξης που παράγει τα δείγµατα είναι ένα µείγµα k µοντέλων Mallows και όχι ένα µεµονωµένο. Αυτή η υπόθεση µοντελοποιεί την ετερογένεια των προτιµήσεων ενός πληθυσµού διαιρώντας τον σε πολλές οµάδες (π.χ. γυναίκες και άνδρες). Σε αυτή την εργασία µελετάµε την εφικτότητα εκµάθησης του selective µοντέλου Mallows και προτείνουµε αλγόριθµους για την εκτίµηση της κατανοµής και (όποτε είναι δυνατόν) την εκτίµηση των παραµέτρων. Προτείνουµε αλγόριθµους που λειτουργούν στη γενική περίπτωση και για την ειδική περίπτωση όπου τα κέντρα είναι καλά διαχωρισµένα δείχνουµε ότι υπάρχουν πολύ πιο αποδοτικοί αλγόριθµοι. Παρέχουµε εγγυήσεις για τη συµπεριφορά των προτεινόµενων αλγορίθµων καθώς και πειραµατικά αποτελέσµατα.