Αλγοριθμικές τεχνικές μάθησης πιθανοτικών κατανομών και εφαρμογές τους σε προβλήματα κοινωνικής επιλογής - Βλατάκης Γκαραγκούνης, Εμμανουήλ Βασίλειος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2016)
In this thesis, we study probability distribution learning problems from a computational algorithmic perspective. We work in a natural PAC-style model of learning an unknown discrete probability distribution. In this framework, the learner is provided with the value of n and with independent samples drawn from the unknown distribution X. Using these samples, the learner must with probability at least 1−δ output a hypothesis distribution Xˆ such that the total variation distance dTV (X, Xˆ ) is at most ε, where ε, δ > 0 are accuracy and confidence parameters that are provided to the learner. We present the previous work on that framework for classical classes of probability distributions i.e monotone, log-concave, unimodal distributions giving tight upper and lower sample bounds. We focus on a new algorithmic technique in distribution learning, the construction of covers, that are sparse in cardinality and dense in metric space of a class of distributions. The method exploits that structure in order to design efficient in time and sample complexity learning algorithms. We study the seminal work of [DP10] and [DDS12] on the Poisson Binomial Distribution, the sum of n independent Bernoulli. We develop then a similar approach on an gradually emerging field of computational social choice, crowdvoting. Based on the famous Mallow noise Model in which every voter is an estimator of the social ground truth, we present our work for the Kemeny and Plurality rule extending the previous research results.