Κατάλογος Εκδηλώσεων

Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών

Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

ΕΥΑΓΓΕΛΟΣ ΚΑΡΑΤΑΡΑΚΗΣ

με θέμα

Συμπερασμός με Ανταλλαγή Μηνυμάτων ως Κατανεμημένος Υπολογισμός

Message Passing Inference as Distributed Computation

Πέμπτη 11 Ιουλίου 2019, 10 π.μ.

Αίθουσα 145.Π42, Κτίριο Επιστημών, Πολυτεχνειούπολη

Εξεταστική Επιτροπή

Καθηγητής Άγγελος Μπλέτσας (επιβλέπων)

Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης

Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς

Περίληψη

Ο πιθανοτικός συμπερασμός παρέχει ικανά εργαλεία επίλυσης προβλημάτων, όπως η εύρεση μιας οριακής συνάρτησης πυκνότητας πιθανότητας χωρίς διαδοχική ολοκλήρωση ή η λύση συστημάτων γραμμικών εξισώσεων μεγάλων διαστάσεων. Αλγόριθμοι όπως ο Gaussian Belief Propagation (GaBP) εφαρμόζονται με ανταλλαγή μηνυμάτων πάνω σε πιθανοτικά γραφικά μοντέλα. Η υλοποίηση των αλγορίθμων αυτών γίνεται σε ασύγχρονη και σε σύγχρονη εκδοχή, με διαφορετικά πλεονεκτήματα στην καθεμία. Επομένως, είναι απαραίτητη η εύρεση ικανών και αναγκαίων συνθηκών σύγκλισης για καθεμία από τις εκδοχές αυτές. ι ασύγχρονοι αλγόριθμοι έχουν μεγάλο ερευνητικό ενδιαφέρον καθώς χαρακτηρίζονται κυρίως από ικανές (και όχι αναγκαίες) συνθήκες σύγκλισης. Ανταλλαγή μηνυμάτων μπορεί να συμβεί και κατά την ασύγχρονη κατανεμημένη εκδοχή του αλγορίθμου Jacobi, όπου γίνεται χρήση ενός πλήθους επεξεργαστών. αλγόριθμος αυτός, αν και δεν ανήκει στην κατηγορία του πιθανοτικού συμπερασμού, μπορεί να προσφέρει χρήσιμες ιδέες στην μελέτη της ασύγχρονης εκδοχής του GaBP. Σημειώνεται ότι ο αλγόριθμος Jacobi αποτελεί ειδική περίπτωση του αλγορίθμου GaBP, όπως πρόσφατα αναφέρθηκε στην βιβλιογραφία. Συγκεκριμένα, αξιοποιούνται πρόσφατα ευρήματα για τον ασύγχρονο Jacobi, όπου το ελάχιστο μονοπάτι στον γράφο που περιγράφει το χρονοδιάγραμμα ανταλλαγής μηνυμάτων, καθορίζει μετρικές σύγκλισης. Στην εργασία αυτή έγινε αξιοποίηση αυτής της μεθοδολογίας στην μελέτη του ασύγχρονου GaBP, κατόπιν παρατήρησης ότι οι αναδρομικές εξισώσεις ανανέωσης των μηνυμάτων του είναι εν μέρει γραμμικές. Το τελευταίο προέκυψε από πρόσφατες μελέτες, όπου φαίνεται ότι ο αλγόριθμος GaBP μπορεί να περιγραφεί μέσω της επίλυσης ενός προβλήματος βελτιστοποίησης, το οποίο καταλήγει σε ένα σύστημα γραμμικών εξισώσεων.