1. Home page
  2. Search

Distribution learning from truncated samples

This item is provided by the institution :
National Technical University of Athens   

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA   

see the original item page
in the repository's web site and access all digital files if the item*



Μάθηση κατανομών από ελλιπή δείγματα (EL)
Distribution learning from truncated samples (EN)
Μάμαλη, Αικατερίνη (EL)
Mamali, Aikaterini (EN)
ntua (EL)
Φωτάκης, Δημήτρης (EL)
Τζάμος, Χρήστος (EL)
Παγουρτζής, Αριστείδης (EL)
bachelorThesis
2022-02-04
2022-06-09T10:34:24Z
Η παρούσα διπλωματική εργασία ασχολείται με το θεμελιώδες πρόβλημα της εκμάθησης κατανομών από ελλιπή δείγματα. Στο πλαίσιο αυτό στόχος είναι η εκτίμηση μιας κατανο- μής πιθανότητας με βάση ένα σύνολο δειγμάτων που μπορεί να είναι ελλιπές. Αυτό σημαίνει ότι όποια δείγματα της κατανομής δεν ανήκουν σε ένα συγκεκριμένο, άγνωστο σύνολο, που ονομάζουμε σύνολο αποκοπής, αφαιρούνται από το σύνολο των δειγμάτων. Η δυσκολία κλιμα- κώνεται όταν απαιτούμε η εκτίμηση αυτή να δίνεται από έναν αλγόριθμο αποδοτικά, δηλαδή με τη χρήση πολυωνυμικού πλήθους δειγμάτων και μετά από πολυωνυμικό αριθμό επαναλήψεων. Μελετούμε την περίπτωση δύο συγκεκριμένων κατανομών: της Διωνυμικής κατανομής του Poisson και του μοντέλου Mallows για κατανομές κατάταξης. Σκοπός μας είναι η εύρεση εκείνων των συνθηκών για το σύνολο αποκοπής που είναι τόσο αναγκαίες όσο και ικανές για την επιτυχή εκμάθηση των κατανομών. Στην περίπτωση της Διωνυμικής κατανομής Pois- son, αποδεικνύουμε ότι το πρόβλημα είναι, γενικά, αδύνατο, αλλά γίνεται ευκολότερο καθώς η κατανομή πλησιάζει την Κανονική κατανομή. Το γεγονός αυτό δηλώνει μία ενδιαφέρουσα μετάβαση στη δυσκολία του προβλήματος. Στην περίπτωση του μοντέλου Mallows, διατυ- πώνουμε μία ικανή συνθήκη για την επιλυσιμότητα του προβλήματος. (EL)
This thesis is concerned with the fundamental problem of learning distributions from truncated samples. In this setting the purpose is to estimate a probability distribution based only on truncated samples. That means that samples falling outside a specific, unknown set are not available. The challenge becomes greater when we demand that these estimations are given by an efficient -in terms of sample and traditional complexity- algorithm. We study the learnability of two specific distributions in this setting: the Poisson Binomial Distribution and the Mallows Distribution. We are interested in those conditions on the truncation set that care both sufficient and necessary to learn these distributions. In the first case, we are faced with an impossible problem that becomes easier as the distribution gains structure, thus indicating an interesting transition on the difficulty of the problem. For the Mallows Model we give a sufficient condition and recognise the sub-optimality of a well-established method in the field of rank aggregation. (EN)
Μάθηση από ελλιπή δείγματα (EL)
Θεωρία μάθησης (EL)
Μοντέλο Mallows (EL)
Μάθηση κατανομών (EL)
Διωνυμική κατανομή Poisson (EL)
Mallows Model (EN)
Poisson Binomial Distribution (EN)
Learning from Truncated Samples (EN)
Learning theory (EN)
Distribution learning (EN)
English
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (EL)
Default License
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)